离散粒子群算法的发散性分析及其改进研究  

Research on Divergence Analysis of Discrete Particle Swarm Optimization Algorithm and Its Modification

作　　者：许金友[1] 李文立[1] 王建军[1] 

机构地区：[1]大连理工大学系统工程研究所,大连116023

出　　处：《系统仿真学报》2009年第15期4676-4681,共6页Journal of System Simulation

基　　金：国家自然科学基金资助项目(70572099);辽宁省自然科学基金资助项目(1050349)

摘　　要：针对粒子群优化算法无法有效地解决离散及组合优化问题,首先从微观角度对粒子状态的变化轨迹进行分析,得出进化过程中单维粒子表现出聚散结构以及多维粒子整体呈现无规则的发散性,这导致粒子搜索的盲目性以及无法深入地进行局部搜索。然后,从粒子间的位置运算和粒子的位置转移两个方面对粒子运动方程进行修正,进而提出一种改进的离散粒子群算法。最后,以经典的背包问题为例进行验证,结果表明该算法有效地降低了粒子搜索的发散度,解的质量明显优于相关算法。Particle swarm optimization （PSO） has been applied to many practical continuous optimization problems. However, it could not be extended to solve discrete and combinatorial optimization problems effectively. By analyzing the change of particles＇ states in the process of evolution from microscopic view, the work found that one-dimensional particle exhibits an aggregation-divergence structure while multi-dimensional particle as a whole exhibits a state of ruleless divergence. This causes that particles search blindly and can not carry out local search deeply. So, a modified discrete PSO （MDPSO） algorithm is proposed by amending particle-movement equation by amending particle-movement equation from redefining both the position operation and the position transfer of particles. Finally, MDPSO is tested by the classical 0-1 knapsack problem. The result shows the searching divergent degree of particles is reduced and the quality of the algorithm is better than other related algorithms.

关 键 词：离散粒子群优化算法 粒子发散性 粒子运动轨迹 背包问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]