1、信息与计算科学专业毕业设计I粒子群优化算法及其参数设置摘 要粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，粒子群优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。论文介绍了粒子群优化算法的基本原理，分析了其特点。论文中围绕粒子群优化算法的原理、特点、参数设置与应用等方面进行全面综述，重点利用单因子方差分析方法，分析了粒群优化算法中的惯性权值，加速因子的设置对算法基本性能的影响，给出算法中的经验参数设置。最后对其未来的研究提出了一些建议及研究方向的展望。关键词
2、：粒子群优化算法；参数；方差分析；最优解 粒子群优化算法及其参数设置IIParticle swarm optimization algorithm and its AbstractParticle swarm optimization is an emerging global based on swarm intelligence heuristic search algorithm, particle swarm optimization algorithm competition and collaboration between particles to achieve in comp
3、lex search space to find the global optimum. It has easy to understand, easy to achieve, the characteristics of strong global search ability, and has never wide field of science and engineering concern, has become the fastest growing one of the intelligent optimization algorithms. This paper introdu
4、ces the particle swarm optimization basic principles, and analyzes its features. Paper around the particle swarm optimization principles, characteristics, parameters settings and applications to conduct a thorough review, focusing on a single factor analysis of variance, analysis of the particle swa
5、rm optimization algorithm in the inertia weight, acceleration factor setting the basic properties of the algorithm the impact of the experience of the algorithm given parameter setting. Finally, its future researched and prospects are proposed.Key word：Particle swarm optimization; Parameter; Varianc
6、e analysis; Optimal solution信息与计算科学专业毕业设计III目 录摘 要 .IIAbstract.III1.引言.11.1 研究背景和课题意义.11.2 参数的影响.11.3 应用领域.21.4 电子资源.21.5 主要工作.22.基本粒子群算法.32.1 粒子群算法思想的起源.32.2 算法原理.42.3 基本粒子群算法流程.52.4 特点.62.5 带惯性权重的粒子群算法.72.7 粒子群算法的研究现状.83.粒子群优化算法的改进策略.93.1 粒子群初始化.93.2 邻域拓扑.93.3 混合策略.124.参数设置.144.1 对参数的仿真研究.144.2 测试
7、仿真函数.154.3 应用单因子方差分析参数对结果影响.334.4 对参数的理论分析.345 结论与展望.39致谢.43附录.44信息与计算科学专业毕业设计11.引言1.1 研究背景和课题意义“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容：1、研究如何利用计算技术研究生物现象。2、研究如何利用生物技术研究计算问题。现在已经有很多源于生物现象的计算技巧。 例如，人工神经网络是简化的大脑模型。遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统- 社会系统。也可称做“群智能”(swarm intelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群
8、体行为。粒子群优化算法(PSO) 也是起源对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程。但后来发现 PSO 是一种很好的优化工具。优化是科学研究、工程技术和经济管理等领域的重要研究课题。粒子群优化算法 1 (简称PSO)是由Kennedy和Eberhart通过对鸟群、鱼群和人类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法。虽然PSO算法发展迅速并取得了可观的研究成果,但其理论基础仍相对薄弱，尤其是算法基本模型中的参数设置和优化问题还缺乏成熟的理论论证和研究。鉴于PSO的发展历史尚短，它在理论基础与应用推广上都还存在一些缺陷，有待解决。本文通过对PSO算法的步骤的归纳、特点
9、的分析，利用统计中的方差分析，通过抽样实验方法，论证了该算法中关键参数因子:惯性权值、加速因子对算法整体性能的影响效果，并提出了参数设置的指导原则，给出了关键参数设置，为PSO算法的推广与改进提供了思路。1.2 参数的影响标准粒子群算法中主要的参数变量为 （惯性权值） ， ， （加速因子） ，w1c2，本文重点对参数 ， ， 做数据统计实验。包括 不变的情况下通过maxvw1c2 w， 变化找出加速因子对算法的影响。还有保持 ， 不变对 分别取不同值1c2 1c2分析其对算法结果影响。粒子群优化算法及其参数设置21.3 应用领域近年来，PSO快速发展，在众多领域得到了广泛应用。本文将应用研究分
10、典型理论问题研究和实际工业应用两大类。典型理论问题包括：组合优化、约束优化、多目标优化、动态系统优化等。实际工业应用有：电力系统、滤波器设计、自动控制、数据聚类、模式识别与图像处理、化工、机械、通信、机器人、经济、生物信息、医学、任务分配、TSP等等。1.4 电子资源 身处信息和网络时代的我们是幸运的，丰富的电子资源能让我们受益匪浅。如果想较快地对PSO有一个比较全面的了解，借助网络空间的电子资源无疑是不二之选。对一些初学者而言，哪里能下载得到PSO的源程序，是他们很关心的话题；即使对一些资深的读者，为了验证自己提出的新算法或改进算法，如果能找到高级别国际期刊或会议上最近提出的算法源程序，那也
11、是事半功倍的美事。这里介绍当今PSO研究领域较有影响的一个网址： Maurice Clerc 博士(Maurice.ClercWriteM) 的PSO 主页：http:/clerc.maurice.free.fr/pso/该主页主要介绍Maurice Clerc博士带领的PSO研究小组的研究成果。除了从中可以得到他们近几年公开发表的相关文献和源代码，还可以下载一些未公开发表的文章。这些未公开发表的文章往往是Maurice Clerc博士的一些设想，而且在不断更新，如“Back to random topology”、“Initialisations for particle swarm opt
12、imization”、“Some ideas about PSO”等等，对PSO研究人员很有启发。 1.5 主要工作论文内容介绍了基本粒子群算法，用 matlab 实现标准粒子群算法算法，对两个不同类型函数做具体分析，然后对其参数 （惯性权值） ， ， （加速因子）w1c2测试。分别对其利用单因子方差分析法，说明不同参数水平对算法速率性能的影响。并且通过公式计算准确判断参数对算法影响。最后说明粒子群优化算法在实际中的应用以及对未来展望，最后总结了算法的优缺点，附录里面附有测试程序和测试函数。信息与计算科学专业毕业设计32.基本粒子群算法2.1 粒子群算法思想的起源粒子群优化(Particle
13、Swarm Optimization, PSO)算法 1是Kennedy 和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法，1995年IEEE国际神经网络学术会议发表了题为“Particle Swarm Optimization”的论文，标志着PSO算法诞生( 注：国内也有很多学者译为“ 微粒群优化 ”)。它与其他进化算法一样，也是基于“种群”和“ 进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索；同时，PSO又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群体(swarm)中的个体
14、看作是在 D维搜索空间中没有质量和体积的粒子(particle)，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置pbest和邻域历史最佳位置 聚集，实现对候选解的进化。PSO算法具有很好的生物社会背景 2而易pbest理解、参数少而易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛关注 3-10。自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域之一是探索自然界生物的群体行为，从而在计算机上构建其群体模型。自然界中的鸟群和鱼群的群体行为一直是科学家的研究兴趣，生物学家Craig Reynolds在1987年提出了一个非常有影响的鸟群聚集模
15、型 7，在他的仿真中，每一个个体遵循：(1) 避免与邻域个体相冲撞；(2) 匹配邻域个体的速度；(3) 飞向鸟群中心，且整个群体飞向目标。仿真中仅利用上面三条简单的规则，就可以非常接近的模拟出鸟群飞行的现象。1990年，生物学家Frank Heppner也提出了鸟类模型 8，它的不同之处在于：鸟类被吸引飞到栖息地。在仿真中，一开始每一只鸟都没有特定的飞行目标，只是使用简单的规则确定自己的飞行方向和飞行速度（每一只鸟都试图留在鸟群中而又不相互碰撞） ，当有一只鸟飞到栖息地时，它周围的鸟也会跟着飞向栖息地，这样，整个鸟群都会落在栖息地。1995年，美国社会心理学家James Kennedy和电气工
16、程师Russell Eberhart共同提出了粒子群算法，其基本思想是受对鸟类群体行为进行建模与仿真的研究结果粒子群优化算法及其参数设置4的启发。他们的模型和仿真算法主要对Frank Heppner的模型进行了修正，以使粒子飞向解空间并在最好解处降落。Kennedy在他的书中描述了粒子群算法思想的起源。自20世纪30年代以来，社会心理学的发展揭示：我们都是鱼群或鸟群聚集行为的遵循者。在人们的不断交互过程中，由于相互的影响和模仿，他们总会变得更相似，结果就形成了规范和文明。人类的自然行为和鱼群及鸟群并不类似，而人类在高维认知空间中的思维轨迹却与之非常类似。思维背后的社会现象远比鱼群和鸟群聚集过程
17、中的优美动作复杂的多：首先，思维发生在信念空间，其维数远远高于3；其次，当两种思想在认知空间会聚于同一点时，我们称其一致，而不是发生冲突。2.2 算法原理PSO 从这种模型中得到启示并用于解决优化问题。PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值( fitness value) ，每个粒子还有一个速度决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索 1。PSO 初始化为一群随机粒子( 随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称
18、为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。假设在一个 维的目标搜索空间中，有 个粒子组成一个群落，其中第 个DNi粒子表示为一个 维的向量， 。),(21iDii xX,21第 个粒子的“飞行 ”速度也是一个 维的向量，记为i， 。),21i iivV，（ 3,第 个粒子迄今为止搜索到的最优位置称为个体极值，记为i， 。),(21iDibest ppN,21整个粒子群迄今为止搜索到的最优位置为全局极值，记为),(21gDgbest pg信息与计算科学专业毕业设计5在找到这两个
19、最优值时，粒子根据如下的公式(2.1)和( 2.2)来更新自己的速度和位置 12：(2.1)(21 idgidiidid xprcxprcvw(2. 2)iiiv其中： 和 为学习因子，也称加速常数(acceleration constant) ， 和 为0，1 范1c2 1r2围内的均匀随机数。式(2.1)右边由三部分组成，第一部分为“惯性(inertia)”或“动量(momentum)”部分，反映了粒子的运动“习惯 (habit)”，代表粒子有维持自己先前速度的趋势；第二部分为“认知(cognition)”部分，反映了粒子对自身历史经验的记忆(memory) 或回忆(remembrance
20、) ，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为“ 社会 (social)”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势，根据经验，通常 。 。 是粒子的速度， ，21cDi,1 idv ,maxvvid是常数，由用户设定用来限制粒子的速度。 和 是介于 之间的随机maxv 1r210数 25。2.3 基本粒子群算法流程算法的流程如下： 初始化粒子群，包括群体规模 ，每个粒子的位置 和速度NixiV 计算每个粒子的适应度值 ；iFt 对每个粒子，用它的适应度值 和个体极值 比较，如果it ）（ ipbest，则用 替换掉 ；)(ipi
21、Fbesttit）（bestp 对每个粒子，用它的适应度值 和全局极值 比较，如果iFtbestg则用 替 ；)(iibestt iFtbestg 根据公式（2.1），（2.2）更新粒子的速度 和位置 ；ivix粒子群优化算法及其参数设置6 如果满足结束条件(误差足够好或到达最大循环次数)退出，否则返回。图2.1. PSO 算法流程图2.4 特点1、式(2.1)中第 1部分可理解为粒子先前的速度或惯性；第2部份可理解为粒子的“认知”行为，表示粒子本身的思考能力；第3部分可理解为粒子的“社会”行为，表示粒子之间的信息共享与相互合作。公式(2.2) 表示了粒子在求解空间中，由于相互影响导致的运动位置调整。整个求解过程中，惯性权重 、加速因w子 和 和最大速度 共同维护粒子对全局和局部搜索能力的平衡。1c2maxv输出结果根据方程 (2.2)对粒子的位置进行进化根据方程 (2.1)对粒子的速度进行进化求出整个群体的全局最优值求出每个粒子的个体最优计算每个粒子的适应值初始化每个粒子的速度和位置是否满足结束条件是否开 始
