粒子群优化算法大作业.doc

粒子群优化算法综述尹兆杰（内蒙古民族大学 数学学院 内蒙古 通辽 028000）摘要 粒子群优化( PSO) 算法是一种基于群智能方法的演化计算技术，通过粒子间的相互作用发现复杂搜索空间中的最优区域，优势在于简单容易实现而且功能强大。由于它简单易操作的特点，PSO 一提出，立刻引起演化计算等领域学者们的广泛关注，并在函数优化、神经网络训练、工业系统优化和模糊系统控。制等领域得到了广泛的应用。 本文从粒子群优化算法的理论分析切入,阐述了PSO 算法的基本原理、若干类改进的PSO 算法及其应用。关键词 粒子群算法 算法改进 应用1 引言 Kennedy和Eberhart1、2于1995 年提出粒子群优化算法( Particle Swarm Optimization，PSO) ，它是一种基于种群智能方法的演化计算技术。因受鸟类捕食行为的启发，设想有一群鸟在随机搜寻一块食物，则找到食物的最简单有效的方法就是搜寻距离食物最近的鸟的周围区域。PSO 从这种模型中得到启示并用于优化问题。PSO 一提出，其简单易操作的特点立刻引起演化计算等领域学者们的广泛关注。PSO 在解决许多GO 问题上被证明是一种有效的方法; 在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。 2. 算法原理在粒子群优化算法中,每个个体称为一个“粒子”,其实每个粒子代表着一个潜在的解。例如,在一个D 维的目标搜索空间中,每个粒子看成是空间里的一个点。设群体由m 个粒子构成。M 也被称为群体规模,过大的m 会影响算法的运算速度和收敛性。设为第个粒子的维位置矢量,根据事先设定的适应值函数(与要解决的问题有关)计算当前的适应值, 即可衡量粒子位置的优劣; 为粒子的飞行速度,即粒子移动的距离; 为粒子位置迄今为止搜索到的最优位置；为整个粒子群迄今为止搜索到的最优位置。在每次迭代中,粒子根据以下式子更新速度和位置: 其中是迭代次数，为之间的随机数,这两个参数是用来保持群体的多样性。为学习因子,也称为加速因子,使粒子具有自我总结和向群体中优秀个体学习的能力, 从而向自己的历史最优点以及群体历史最优点靠近。这两个参数对粒子群算法的收敛起的作用不是很大,但如果适当调整这两个参数,可以减少局部最小值的困扰,当然也会使收敛速度变快。由于粒子群算法中没有实际的机制来控制粒子速度,所以有必要对速度的最大值进行限制,但速度超过这个阈值时,设其为这个参数被证明是非常重要的,因为值太大会导致粒子跳过最好解, 但太小的话容易导致对搜索空间的不充分搜索。此外速度最小取值为位置的取值范围为式的第二项是“认知”部分,代表了粒子对自身的学习。而公式的第三项是“社会”部分,代表着粒子间的协作。式正是粒子根据它上一次迭代的速度、它当前位置和自身最好经验与群体最好经验之间的距离来更新速度。然后粒子根据式飞向新的位置。从此可得到粒子群优化算法是主要遵循了五个基本原则，定义为：邻近原则：粒子必须能够执行简单的空间和实践计算；品质原则：粒子群必须能够对周围环境的品质因素有所反应；多样性反应原则：粒子群不应该在过于狭窄的范围内活动；定性原则：粒子群不应该在每次环境改变的时候都改变自身的行为；适应性原则：在能够接受的计算量下，粒子群能够在适当的时候改变他们的行为。简单来说，粒子群优化算法的流程可表示为：Step 1,依照初始化过程，对微粒群的随机位置和速度进行初始设定；Step 2,计算每个 微粒的适应值；Step 3,对于每个微粒，将其适应值与所经历过的最好位置的适应值进行比较，若较好，则将其作为当前的最好位置；Step 4, 对每个微粒，将其适应值与所经历过的最好位置的适应值进行比较，若较好，则将其作为当前的全局最好位置；Step 5, 根据方程式、式对微粒的速度和位置进行进化；Step 6, 如未达到结束条件，同城为足够好的适应值或达到一个预设最大代数，则返回step 2。由于PSO 算法需要用户确定的参数并不多，而且操作简单。但是它的缺点是易陷入局部极小点，搜索精度不高，因此研究者们对其进行了各种各样的改进。3 改进的粒子群优化算法3.1 收敛文献3通过对算法的研究，证明采用收敛因子能够确保算法的收敛。在收敛因子模型中速度的更新公式为:其中，通常取由此计算得改进后的公式被称为标准。3.2 基于拓扑结构的PSO文献4在研究了领域拓扑结构对粒子群算法性能的影响后，设计了两种动态邻域生成策略，验证不同的邻域拓扑结构和不同的算法模型能够影响粒子群算法的性能。文献5提出了一种该改进的PSO 算法PSO DSF。引进有向类无标度网作为粒子群寻优的拓扑结构，提出作为粒子邻域拓扑的有向网络动态变化机制，从而提高算法的多样性，避免过早陷入局部最优的情况。文献6提出基于KRTG 的动态拓扑结构的粒子群算法研究。从粒子间的拓扑结构出发，动态地调整种群的拓扑结构，增加种群的多样性，使算法收敛于全局最优解。文献7提出了一种动态拓扑结构改进PSO 算法。在这种结构中，用了两种方法改进邻居的拓扑结构: 随机边缘移植( Random Edge Migration，REM) 、邻居重组( Neighborhood Restructuring，NR) 。随机边缘移植是指随机选取一个邻居数目大于1 的粒子节点，移去一个邻居节点，并把这个邻居节点和另一个随机选取的未满的粒子节点相连接。邻居重组保持粒子的邻居结构在一段时间内固定，然后重新构造粒子邻居的结构。通过对六个基准函数的实验表明这种方法是一种好的策略，对每一个函数的测试都取得了令人满意的结果。研究基于拓扑结构的PSO 算法一直在持续，是一个值得研究的方向。3.3 混合PSO文献8针对带障碍约束的空间聚类，提出了一种改进的蚁群算法( IACO) 和混合粒子群算法（ HPSO） 。首先，使用蚁群算法获得最短的障碍距离，然后设计了一个带障碍约束的遗传K 中心空间聚类分析算法。文献9中，使用交叉算子和变异算子，并结合混合粒子群优化算法以及遗传算法解决柔性作业调度问题，并提出混合整数编程模型。3.4 统一PSOPSO 算法的性能依赖于全局搜索和局部搜索之间( Exploration and Exploitation) 的平衡能力，即搜索空间的全局搜索能力和快速收敛于有希望的区域的能力，分别对应全局变量和局部变量。根据这一思想，文献10提出了一种新的PSO 结构UPSO( UnifiedParticle Swarm Optimization) 。为达到全局搜索和局部搜索的平衡，UPSO 将全局变量和局部变量合在一个公式里，从而更新粒子的位置:其中，u 是统一因子，在0，1之间取值，用来平衡全局和局部搜索。u = 0 和1 分别对应着局部PSO 和全局PSO。Gn + 1id表示在全局PSO 变量中粒子xi的速度更新，Ln + 1id表示在局部PSO 变量中粒子的速度更新，它们分别用下式计算:其中，k 是迭代次数，g( 全局变量) 是整个粒子群目前找到的粒子最优位置的下标，gi(局部部变量)是xi的邻居目前找到的粒子最优位置的下标。4 结束语PSO 是一种新兴的有潜力的基于群智能的演化计算技术。自从2002 年PSO 算法被引进国内27，已经有很多学者对PSO 进行了研究。虽然已经取得了一些研究成果，但是仍然有许多问题值得关注。PSO 算法在实际应用中已被证明是一种有效的优化工具，已广泛的应用于科学研究和工程实践，但是其内部机理仍不明确，PSO 算法缺乏数学理论支持。PSO 的改进算法及其应用也都停留在实验阶段。文献4，5对算法的收敛做了一定的分析，但是对于这样一个年轻有潜力的算法，还远远不够。所以开展一些理论研究，不仅可以加深对PSO 算法内部机理的认识，而且对于扩展PSO 的应用领域也有深远意义。参考文献1 Kennedy J，Eberhart R. Particle swarm optimizationC IEEE Int 1 Conf on Neural Networks，Perth，Australia，1995: 1942-19482 Eberhart R，Kennedy J. A new optimizer using particleswarm theoryC Proc of the sixth international symposiumon Micro Machine and Human Science，Nagoya， Japan，1995: 39-433 Clerc M. The swarm and the Queen: Towards a deterministic and adaptive particle swarm optimizationC Proc of the Congress of Evolutionary Computation，1999: 1951-19574 韩立娜，熊盛武. 基于动态领域的粒子群算法的研究J 计算机工程与应用， 2009， 45( 6) : 60-655 姚灿中，杨建梅. 一种基于有向动态网络拓扑的粒子群优化算法J 计算机工程与应用， 2009， 45( 27) : 15-176 田玉玲，杨朋樽. 基于KRTG 的动态拓扑结构的粒子群算法研究J 计算机与数学工程， 2010， 38( 2) : 25-277 Arvind Mohais ，Rui Mendes ，Christopher Ward ，Christian Postoff. Neighborhood Re structuring in Particle Swarm Optimization C Australian Conference on Artificial Intelligence 2005: 776-7858 Zhang Xueping，Wang Jiayao，Zhang Dexian，Fang Zhongshan. An IACO and HPSO method for spatial clustering with obstacles constraints C The 4th International Conference on Intelligent Computing， ICIC 2008， 2008: 848-8568 Lingli Zeng，Fengxing Zou，Xiaohong Xu. Mathematical model and hybrid particle swarm optimization for flexible job shop scheduling problem C Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation，Shanghai，China， 2009: 731-7369 K. E. Parsopoulos and M. N. Vrahatis. UPSO: A unified particle swarm optimization scheme. Proc of the International Conference of Computational Methods in Sciences and Engineering 2004:868-873