粒子群算法的研究

I目录目录...........................................................................................................I摘要..........................................................................................................II前言.........................................................................................................III2引言......................................................................................................12.1背景研究和课题意义....................................................................................12.2应用领域......................................................................................................13基本粒子群算法.....................................................................................23.1粒子群思想的起源.......................................................................................23.2算法原理......................................................................................................33.3带权重的粒子群算法....................................................................................34粒子群算法的改进策略...........................................................................44.1粒子群初始化...............................................................................................44.2领域拓扑......................................................................................................44.3混合策略......................................................................................................45测试结果...............................................................................................55.1参数设置......................................................................................................55.2实验结果......................................................................................................56总结......................................................................................................7致谢..........................................................................................................8附录代码...................................................................................................9II摘要粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域广泛关注，已经成为发展最快的智能优化算法之一。论文介绍了粒子群优化算法的基本原理，分析了其特点。论文中围绕粒子群优化算法的原理、特点、参数设置与应用等方面进行全面综述，重点利用单因子方差分析方法，分析了粒群优化算法中的惯性权值，加速因子的设置对算法基本性能的影响，给出算法中的经验参数设置。最后对其未来的研究提出了一些建议及研究方向的展望。关键词：粒子群优化算法；参数；方差分析；最优解III前言群体智能算法(SwarmIntelligenceAlgorithm,SIA)的研究开始于20世纪90年代,其基本思想是模拟自然界生物的群体行为来构造随机优化算法[1,2,3],通常单个自然界的生物并不是智能的,但是整个生物群体却表现出处理复杂问题的能力,群体智能算法就是模仿这些生物的团体行为并把它应用在人工智能问题中,其中粒子群优化算法(ParticleSwarmOptimization,PSO)就是群体智能算法的一种,它是由美国社会心理学家JamesKennedy和电气工程师RussellEberhart在1995年提出的,其基本思想是对鸟群、鱼群的觅食过程中的迁徙和聚集的行为模拟,并利用了生物学家FrankHeppner的生物群体模型[4,5,6]。PSO算法是一类基于群体智能的随机优化技术,相对遗传算法而言,二者都是基于群体的迭代搜索,但是PSO算法没有交叉、变异算子,粒子群优化算法是通过个体之间的协作来搜寻最优解,它利用了生物群体中信息共享的思想,其概念简单、易于实现,同时又有深刻的智能背景,既适合科学研究,又特别适合工程应用。因此,PSO一提出,就引起了众多学者的关注,并在短短几年的时间里出现了大量的研究成果12引言2.1背景研究和课题意义现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型。遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统-社会系统。也可称做“群智能”(swarmintelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为。粒子群优化算法(PSO)也是起源对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程。但后来发现PSO是一种很好的优化工具。优化是科学研究、工程技术和经济管理等领域的重要研究课题。粒子群优化算法[1](简称PSO)是由Kennedy和Eberhart通过对鸟群、鱼群和人类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法。鉴于PSO的发展历史尚短，它在理论基础与应用推广上都还存在一些缺陷，有待解决。本文通过对PSO算法的步骤的归纳、特点的分析，利用统计中的方差分析，通过抽样实验方法，论证了该算法中关键参数因子:惯性权值、加速因子对算法整体性能的影响效果，并提出了参数设置的指导原则，给出了关键参数设置，为PSO算法的推广与改进提供了思路。2.2应用领域近年来，PSO快速发展，在众多领域得到了广泛应用。本文将应用研究分典型理论问题研究和实际工业应用两大类。典型理论问题包括：组合优化、约束优化、多目标优化、动态系统优化等。实际工业应用有：电力系统、滤波器设计、自动控制、数据聚类、模式识别与图像处理、化工、机械、通信、机器人、经济、生物信息、医学、任务分配、TSP等等。23基本粒子群算法3.1粒子群思想的起源粒子群优化(ParticleSwarmOptimization,PSO)算法[1]是Kennedy和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法，1995年IEEE国际神经网络学术会议发表了题为―ParticleSwarmOptimization‖的论文，标志着PSO算法诞生(注：国内也有很多学者译为―微粒群优化‖)。它与其他进化算法一样，也是基于―种群‖和―进化‖的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索；同时，PSO又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群体(swarm)中的个体看作是在D维搜索空间中没有质量和体积的粒子(particle)，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置pbest和邻域历史最佳位置pbest聚集，实现对候选解的进化。PSO算法具有很好的生物社会背景[2]而易理解、参数少而易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛关注。自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域之一是探索自然界生物的群体行为，从而在计算机上构建其群体模型。自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣，生物学家CraigReynolds在1987年提出了一个非常有影响的鸟群聚集模型[7]，在他的仿真中，每一个个体遵循：(1)避免与邻域个体相冲撞；(2)匹配邻域个体的速度；(3)飞向鸟群中心，且整个群体飞向目标。33.2算法原理粒子群优化算法的实现步骤如下：假设在一个D维的搜索空间中，有m个粒子组成一个群落，其中第i个粒子表示为一个D维的向量),...,,(21iDiiixxxX。即第I个粒子在D维搜索空间的位置是iX。换言之，每个粒子的位置就是一个潜在的解。将iX代入一个目标函数就可以计算出其适应值，根据适应值的大小衡量解的优劣。第i个粒子的“飞翔”速度也是一个D维向量记为),...,,(21iDiiivvvV。记第i个粒子迄今为止搜索到的最优位置为),...,,(21iDiiipppP，整个粒子群迄今为止搜索到的最优位置为),...,,(21gDgggpppP。3.3带权重的粒子群算法探索是偏离原来的寻优轨迹去寻找一个更好的解，探索能力是一个算法的全局搜索能力。开发是利用一个好的解，继续原来的寻优轨迹去搜索更好的解，它是算法的局部搜索能力。如何确定局部搜索能力和全局搜索能力的比例，对一个问题的求解过程很重要。1998年，YuhuiShi[9]提出了带有惯性权重的改进粒子群算法。其进化过程为：tkxprctkxprckwvkvigiiii/))((/))((),(()1(2211tkvkxkxiii）1()()1(其中，w为惯性权重，其值可取为常数，也可以自适应调整，例如随迭代次数的增加而线性地减少,c1和c2为调节Pi和Pg相对重要性的参数；r1和r2是介于0和1之间的随机数；是时间间隔，通常取为单位时间；通常附加限制，其中是常数，可根据具体问题设定。44粒子群算法的改进策略4.1粒子群初始化研究表明，粒子群初始化对算法性能产生一定影响。为了初始种群尽可能均匀覆盖整个搜索空间，提高全局搜索能力，Richard和Ventura提出了基于centroidalvoronoitesse