粒子群优化(Particle Swarm Optimization, PSO)是由Kennedy和Eberhart于1995年提出的一种进化计算技术,其源于对鸟群捕食行为的研究。作为一种基于群体的随机算法,PSO采用速度——位置模型,避免了复杂的遗传操作,利用群体内个体间的合作与竞争实现寻优。由于思想简单、操作方便,该算法受到了人们广泛关注并成功应用于很多领域。然而,粒子群优化的研究还很不成熟,其理论研究较薄弱,易出现早熟收敛,且搜索精度有限,应用还存在局限性。本文从邻居拓扑结构、算法改进以及在离散优化问题中的应用三个方面对粒子群优化进行了深入研究。论文取得的主要成果与创新工作概括如下:①深入研究了邻居拓扑结构的图属性特征及其对PSO算法性能的影响。引入图属性(直径、平均路径长度、聚类系数和平均度)研究了典型的静态邻居拓扑结构(全互连、环形和冯诺依曼结构),给出了它们的图属性特征;分析了图属性特征对算法性能的影响以及图属性特征之间的关系;首次讨论了粒子的邻居分布对算法性能的影响以及聚类系数与邻居分布的关系。分析指出在平均度相同的情况下,聚类系数低的邻居拓扑结构通常具有较均衡的邻居分布和较短的直径与平均路径长度。②设计了一种新的静态邻居拓扑结构——无团邻居拓扑结构。无团邻居拓扑结构在给定的平均度下保持最小的聚类系数,具有较均衡的邻居分布。通过对具有相同平均度、不同聚类系数邻居结构的PSO算法的实验测试验证了聚类系数的作用和无团邻居拓扑结构的优越性,并且分析了无团邻居拓扑结构的平均度与群规模的关系。③研究提出了静态邻居结构上的一种新的信息共享机制——局部精英信息共享策略。首先分析了静态邻居结构上的信息共享机制,探讨了邻居结构间的关联性对算法的影响,提出粒子群中的“富人节点”和“富人俱乐部”现象,并指出粒子群中的“富人俱乐部”现象可能导致算法陷入局部最优;在此思想基础上,定义了局部影响因子和局部精英粒子,提出了局部精英信息共享策略。通过测试函数和群体多样性测量的实验说明,与其它不同共享机制的PSO算法比较,局部精英共享策略在邻居结构变化下性能表现出较好的稳定性,能较好地保持粒子多样性,但寻优速度较慢。④设计了两类基于编号的自适应邻居扩充PSO算法——基于自适应动态邻居结构的PSO算法(PSOSADN)和受约束的动态邻居扩充PSO算法(PSODNE)。两类算法利用粒子的自身特性和邻居状态,在环形结构的基础上通过不断扩充邻居来提高性能。在PSOSADN算法中根据粒子和邻居最优位置的关系,定义了粒子的扩充概率来自适应地调整粒子的扩充速度;同时,利用无团邻居拓扑结构的性质提出了三种邻居扩充策略,由此得到三个不同的PSO算法(PSOSADN1、PSOSADN2和PSOSADN3)。PSODNE算法则基于控制“富人节点”影响力的思想,通过定义粒子邻居扩充因子和邻居扩充与约束策略来调整粒子的邻居扩充行为和扩充速度。与基于不同邻居结构的PSO算法的比较实验,结果表明:PSOSADN1算法具有较快的收敛速度,PSOSADN2算法具有较好的平衡性能,而PSOSADN3和PSODNE算法在全局寻优能力方面表现较好。实验还分析了扩充行为对算法性能的影响。⑤设计了一种基于动态子群的混合粒子群优化算法(HPSODS)。HPSODS算法依据粒子的适应值特性,采用层次聚类将粒子动态地分为多个子群;并按照各子群的性能,将它们归为四类;每类采用不同作用的进化策略,合作实现优化任务。算法引入种群熵控制聚类频率,引入高斯变异和分段线性混沌映射设计出四种不同的进化策略,实现了不同区域、不同目的的寻优。通过实验分析了子群数和四种进化策略对算法的影响,给出了子群数的选择范围。与其它著名的PSO算法对比实验,结果表明:HPSODS算法在典型的单模和多模测试函数中均显示出更强的全局搜索能力、更高的求解精度、更快的收敛速度以及更好的稳定性。⑥建立了一种新的解决集合组合优化问题的离散粒子群优化模型(SDPSO),并由此设计出背包问题的集合解决方法。SDPSO模型将集合概念和运算引入到粒子群优化中,定义了一个可变集合搜索空间,重新定义了粒子的位置、速度及作用于此空间的运算规则。采用四个不同规模的背包实例进行测试,实验结果显示基于该模型的算法具有较强的寻优能力和较快的收敛速度明显优于传统的二进制PSO算法,说明所提离散模型的可行性和有效性。