广义粒子群优化模型

General Particle Swarm Optimization Model

粒子群优化算法提出至今一直未能有效解决的离散及组合优化问题.针对这个问题,文中首先回顾了粒子群优化算法在整数规划问题的应用以及该算法的二进制离散优化模型,并分析了其缺陷.然后,基于传统算法的速度-位移更新操作,在分析粒子群优化机理的基础上提出了广义粒子群优化模型(GPSO),使其适用于解决离散及组合优化问题.GPSO模型本质仍然符合粒子群优化机理,但是其粒子更新策略既可根据优化问题的特点设计,也可实现与已有方法的融合.该文以旅行商问题(TSP)为例,针对遗传算法(GA)解决该问题的成功经验,使用遗传操作作为GPSO模型中的更新算子,进一步提出基于遗传操作的粒子群优化模型,并以Inver over算子作为模型中具体的遗传操作设计了基于GPSO模型的TSP算法.与采用相同遗传操作的GA比较,基于GPSO模型的算法解的质量与收敛稳定性提高,同时计算费用显著降低.

Particle swarm optimization （PSO） is generic heuristic algorithm based on swarm intelligence. It has been applied to many practical continuous optimization problems. However, due to the limitation of its velocity-displacement search model, it could not be extended to solve discrete and combinatorial optimization problems effectively. To solve this problem, this paper first reviews the applications of PSO algorithm in integer programming problems and its binary version discrete model, in which their corresponding limitations are analyzed. Then based on traditional velocity-displacement operator, mechanism of PSO algorithm is studied and general particle swarm optimization （GPSO） model is proposed. Thus, PSO algorithm developed on this general model can be naturally extended to solve discrete and combinatorial optimization problems. GPSO model is still based on PSO mechanism, but the updating operator could integrate with other solutions such as GA, simulated annealing and taboo search easily. Travel salesman problem （TSP） is used to demonstrate this extension. In view of the success of GA in this problem, this paper uses genetic operator as the updating operator in GPSO model and further proposes genetic operator based PSO model, and selects Inver over operator as the genetic operator in this model. Finally the corresponding PSO algorithm for TSP is presented. In contrast to the GA with the same genetic operator, GPSO based algorithm converges consistently with better TSP solutions and saves computational cost significantly.