维普资讯 http://www.cqvip.com 第３４卷第５期 电子科技大学学报 Ｊｏｕｒｎａｌ ｏｆ ＵＥＳＴ ｏｆ Ｃｈｉｎａ Ｖｏ１．３４ ＮＯ．５ ２００５年１Ｏ月 Ｏｃｔ．２００５ 粒子群优化算法及其与遗传算法的比较 沈艳 ，郭 兵２，古天祥 成都６１００５４，２．四川大学计算机学院成都６１００４１） （Ｉ．电子科技大学机械电子－Ｉ－程学院【摘要】粒子群优化算法是根据乌群觅食过程中的迁徙和群集模型而提出的用于解决优化问题。该文讨论 粒子群优化算法的基本原理和实现步骤，分析了该算法中各参数的设置。通过一个测试函数，对粒子群优化算法 与遗传算法进行了比较，结果表明粒子群优化算法在找寻最优解效率上好于遗传算法。 关键词群集智能；粒子群：遗传算法：优化 ０２２４ 文献标识码Ａ 中图分类号Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ｃｏｍｐａｒｉｓｏｎ ｗｉｔｈ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ＳＨＥＮＹａｎ‘，ＧＵＯＢｉｎｇ２，ＧＵＴｉａｎ—ｘｉａｎｇ‘ （１．Ｓｃｈｏｏｌ ｏｆＥｌｅｃｔｒｏｍｅｃｈａｎｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，ＵＥＳＴ ｏｆＣｈｉｎａ Ｃｈｅｎｇｄｕ ６１００５４，２．Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ，Ｓｉｃｈｕａｎ Ｕｎｉｖａｒｃｉｔｙ Ｃｈｅｎｇｄｕ ６１００４１） Ａｂｓｔｒａｃｔ Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ，ｒｏｏｔｉｎｇ ｆｒｏｍ ｓｉｍｕｌａｔｉｏｎ ｏｆ ｓｗａｒｍ ｏｆ ｂｉｒｄ，ｓｏｌｖｅｓ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ．Ｆｉｒｓｔｌｙ，ｄｉｓｃｕｓｓｅｓ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｐｒｉｎｃｉｐｌｅ ａｎｄ ｓｔｅｐ ｏｆ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，ａｎｄ ｔｈｅｎ ａｎａｌｙｚｅｓ ｅａｃｈ ｏｆ ｐａｒａｍｅｔｅｒ．Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｃｏｍｐａｒｅｓ ｗｉｈ ｇｅｎｅｔｉｔｃ ａｌｇｏｒｉｔｈｍ ｔｈｒｏｕｇｈ ｔｈｅ ｓａｍｅ ｍａｔｈｅｍａｔｉｃ ｆｕｎｃｔｉｏｎ．Ｔｈｅ ｃｏｍｐａｒａｔｉｖｅ ｒｅｓｕｌｔ ｉｎｄｉｃａｔｅｓ ｔｈａｔ Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｃａｎ ｏｂｔａｉｎ ｔｈｅ ｏｐｔｉｍｕｍ ｓｏｌｕｔｉｏｎｓ ｍｏｒｅ ｅａｓｉｌｙ ｔｈａｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｔ ｉｓ ａ ｇｏｏｄ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｅｔｈｏｄ ｗｉｈ ｓ￣ｏｎｇ ｃｏｍｐｅｔｉｔｔｉｏｎ． Ｋｅｙ ｗｏｒｄｓ ｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ；ｐａｒｔｉｃｌｅ ｓｗａｒｍ，ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｏｐｔｉｍｉｚａｔｉｏｎ 自然界经过数万年的演化，以最优的方式及其规律存在。“师法自然”，人们受自然界的运行发展机制 的启发，建立和发展了一系列的优化算法，如遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，ＧＡ）、模拟退火、人工神经网络 等，这些算法已广泛应用于工程中，解决许多研究过程中遇到的困难。 随着人们对鸟类的群集（Ｆｌｏｃｋｉｎｇ）行为的研究，如大雁飞行自动排成人字形、蝙蝠在洞穴中快速飞行却 互不相碰等。１９９５年，文献【ｌ，２】对鸟群觅食过程中的迁徙和群集进行模拟：鸟群觅食时，从一地到另一地 的迁徙过程中，总是有一只鸟对食源的大致方向具有较好的洞察力，同时，在找寻食源的途中，它们通过 套自己独有的方式随时相互传递着信息，特别是较好的信息。在“好消息”的指引下，导致鸟群“一窝 蜂”的奔向食源，达到在食源的群集。粒子群优化算法从中得到启示并用于解决优化问题。 １粒子群优化算法 １．１基本原理 在粒子群优化（Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｍｉｉｚａｔｉｏｎ，ＰＳＯ）算法中，一只鸟称为“粒子”，解群相当于一个鸟群， 地到另一地的迁徙相当于解群的进化，“好消息”相当于解群每代进化中的最优解，食源相当于全局最 收稿日期：２００３—１０—２９ 作者简介：沈艳（１９７３一），女，博士，讲师，主要从事人工智能、智能化、网络化测控技术方面的研究． 维普资讯 http://www.cqvip.com 第５期 沈艳等： 粒子群优化算法及其与遗传算法的比较 ６９７ 优解。 假设在一个ＪⅣ维目标搜索空间中，有ｍ个粒子组成一个群落，其中第价粒子在Ⅳ圣隹空间里的位置 ＝ ｘｏ，…， 。ｆ：１，２，…， ；飞行速度 （ ｌ， ，…， ，ｊ＝１，２，…， ；适应￣ｆｉｔｎｅｓｓｆ＝厂 ），则Ｐ６ 和 ＝ ， ， ， 胁，…， 分别为第ｉ个粒子曾经达到的最大适应值及其对应的位置。Ｇ６ ｆ为在群 体所有粒子经历过的最好位置，其索引号为ｇ。则对每一代，其第雄根据如下方程变化： Ｖｉｄ＝ｗｖｆｄ＋ｑ （ 一 ）＋ｃ ｒ２（ 蓦耐一 ） Ｘ ＝Ｘ『ｄ＋Ｖｔｄ（１） （２） 式中 为粒子ｉＺ行速度矢量的第雠分量；Ｘｉｄ为粒子ｉ位置矢量的第ｄ维分量：，．，，ｒ２为【０，１】之间的随机 一 ）项为“认知项 一 ）项为“社会项（Ｓｏｃｉａｌ Ｔｅｒｍ）”，它代表粒子 数；ｃ。，Ｃ２为加速度系数；Ｗ为惯性权重。式（１）中，首项为粒子先前的速度：ｃｌ （ （Ｃｏｇｎｉｔｉｖｅ Ｔｅｒｍ）”，该项与粒子的认知经验相关；ｃ２ｒ２（ １．２实现步骤 间的信息共享与合作。式（２）为粒子ｆ的新坐标位置。它们共同决定粒子ｉ下一步的运动位置。 粒子群优化算法的实现步骤为：（１）初始化粒子群。设群体规模为ｍ，在允许的范围内随机设置粒子的 初始位置和速度；（２）评价每个粒子的适应值，即计算每个粒子的目标函￣ｆｉｍｅｓｓ，；（３）对所有的ｆ∈｛１，２，…， ｍ），如果触 ６巴 ，则令，彳仂缁 ６ ， ，如￣ｆｉｍｅｓｓｒ＞ｇｂｅｓｔ，则重新设置ｇｂｅｓｔ的索引号ｇ；（４）根 据式（１）、（２）调整每一个粒子的位置和速度；（５）检查终止条件。如果达到最大迭代次数ｇ 一或最好解停 滞不再变化，终止迭代，否则返回（２ 。 粒子群优化算法主要包括［３】：（１）粒子以随机的方式在整个问题空间中流动并且可以对自己所处的环境 进行评价（计算适应度）。（２）每个粒子均可以记忆自己到过的最好位置和感知邻近粒子已达到的最好位置。 （３）在改变速度的时候同时考虑自己到过的最好位置和邻近粒子已达到的最好位置。 １．３参数分析 ＰＳＯ算法参数包括：群体规模ｍ，惯性权重ｗ，加速度系数 ，ｃ２，最大代数ｇ （１）惯性权重ｗ－－它使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。如果ｗ＝０， 由于速度本身没有记忆性，只取决于粒子当前位置和其历史最好位置尸６ 和 巴 ，所以，粒子群将收缩到 当前的全局最好位置，更像一个局部算法；如果ｗ：／：０，微粒有扩展搜索空间的趋势，即有全局搜索能力。 因此，对于较大的Ｗ值有利于跳出局部极小点，而较小的Ｗ值有利于算法收敛。（２）加速度系数ｃ 、ｃ：：该 项参数用于调整粒子的自身经验与社会经验在其运动中所起的作用，表示将每个粒子推向尸６鲫Ｉ和 位置 的统计加速项的权重。低的值允许粒子在被拉回前可以在目标区域外徘徊，而高的值则导致粒子突然冲向 或越过目标区域。如果ｃ．＝０，则粒子没有认知能力。在粒子的相互作用下，不仅能到达新的搜索空间，但 也容易陷入局部极值点：如果Ｃ２＝０，粒子间没有社会信息共享，其算法变成一个多起点的随机搜索；如果 ｃ。＝ｃ２＝０，粒子将一直以当前的速度飞行，直到到达边界。通常ｃ。、ｃ２的范围在０＂－＇４之间。（３）粒子个数和维 数：粒子个数一般取２０＂－＇４０，对于大部分的问题１０个粒子已经足够取得好的结果，对于比较难的问题或者 特定类别的问题，粒子数可以取￣ＵＩＯ０或２００。 ２举例与比较 ２．１测试函数 本文采用测试函数 ）＝ｘｓｉｎ（１０ｍｃ）＋１．０，ＩＥ［＿＿１，２】，测试函数如图１所示。图中， 它在区间ｆ－１，２】上的最优解为：ｘ＝１．８５１ ５， ）＝２．８５１ ２。 是一个多峰函数， ２．２参数对粒子群优化算法影响 （１）ｃｌ、 的不同取值对ＰＳＯ的影响如图２所示，图中，ｃｌ＝Ｃ２＝０．５，最优解出现在２４代；ｃｌ＝ｃ２＝１，最优解 出现在２３代；ＣＩ＝Ｃ２＝１，最优解出现在２０代；ｃｌ＝Ｃ２＝２，最优解出现在１７代；ｃｌ＝Ｃ２＝２．５，最优解出现在２７代； ｃ１＝ｃ２＝４，最优解没有出现。（２）惯性权重Ｗ的不同取值对ＰＳＯ的影响如图３所示，图中，ｗ＝１．０５时，粒子群 优化算法的搜索效率和搜索精度高。 维普资讯 http://www.cqvip.com ６９８ 电子科技大学学报 ３．０ 第３４卷 菩 亘 羽 。． ｌ ！三 Ｉ ２．５ ２．０ １．５ ０ ｌ０２０３０４０ ５０ 籁 ｇｅｎ ｇｅｎ ｇｅｎ 图１测试函数图 图２ ｃｌ、ｃ２的不同取值对ＰＳＯ的影响 弘譬最墓面 图３ ｗ不同取值对ＰＳＯ的影响 ２．３粒子群优化算法与遗传算法比较 遗传算法的控制参数设定如下：群体规模大ｄｘ２０，个体串长度为２２；杂交概率０．９，变异概率为０．０１； 最大遗传代数１００；粒子群优化算法的控制参数设定为：群体规模大ｄｘ２０，最大进化代数：５０，ｃ。＝ｃ２＝２； 遗传算法与粒子群优化算法的解随进化代数的变化情况如图４、５所示，比较结果如图６所示。由图４～６， 粒子群优化算法的最优解出现在１７代，而遗传算法的最优解出现在４９代，粒子群优化算法在找寻最优解效 率上要好于遗传算法。 ｂ ｇｅｎ＝１５ 图４遗传算法的解随进化代数的变化情况 ａ ｇｅｎ＝３ Ｃ ｇｅｎ＝５０ 图５粒子群优化算法的解随进化代数的变化情况 维普资讯 http://www.cqvip.com 第５期 沈艳等： 粒子群优化算法及其与遗传算法的比较 ６９９ 由此可见，虽然粒子群优化算法和遗传算法有很多共同之处：两者都随机初始化种群，都使用评价函 数来衡量个体的优劣程度，并根据由评价函数得到的适应值来进行一定的随机搜索。但粒子群优化算法搜 索速度快，在搜索性能上好于遗传算法，这是因为：（１）粒子群优化算法没有遗传操作，如交叉（Ｃｒｏｓｓｏｖｅｒ） 和变异（Ｍｕｔａｔｉｏｎ），而是利用个体在解空间中的随机速度来改变个体，其解群相对进化代数而言，表现出更 强的随机性，其计算复杂度比遗传算法低。（２）粒子具有“记忆”的特性，它们通过“自我”学习和向“他 人”学习，使其下一代解有针对性的从“先辈”那里继承更多的信息，从而能在较短的时间内找到最优解。 （３）与遗传算法相比，粒子群优化算法的信息共享机制是很不同的：在遗传算法中，染色体互相共享信息， 所以整个种群的移动是比较均匀的向最优区域移动：在粒子群优化算法中，信息流动是单向的，即只￣ｆｆｇｂｅｓｔ 将信息给其他的粒子，这使得整个搜索更新过程跟随当前最优解。 从以上实验及分析可以看出粒子群优化算法在多数的情况下，比遗传算法更快的收敛于最优解。 图６粒子群优化算法与遗传算法的比较 ３结束语 粒子群优化算法是通过粒子间的相互作用发现复杂搜索空间中的最优区域，是一类随机全局优化技 术。其优势在于简单容易实现而又功能强大。目前，粒子群优化算法最成功地运用是在进化神经网络方面， 但对其的研究才刚起步，相对其他较成熟的进化算法，还没有形成系统的分析方法和一定的数学基础，且 应用范围较小。随着研究的进一步深入，该算法将会应用到越来越多的领域中。 本文研究工作得到电子科技大学青年基金（ｊｘ０４０３ ８）资助，在此表示感谢。 参考文献 ［１】Ｋｅｎｎｅｄｙ Ｊ，Ｅｂｅｒｈａｒｔ Ｒ Ｃ．Ｐａｒｔｉｃｌｅ ＳＷ￣／１ ｏｐｔｉｍｉｚａｔｉｏｎ［ｃ】．Ｐｒｏｃ．ＩＥＥＥ ｈａｔ．Ｃｏｎｆ．．ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ，Ｐｅｒｔｈ，ＷＡ， Ａｕｓｔｒａｌｉａ，１９９５．１ ９４２－１ ９４８ ［２】Ｅｂｅｒｈａｒｔ Ｒ Ｃ，Ｋｅｎｎｅｄｙ Ｊ Ａ．Ａ ｎｅｗ ｏｐｔｉｍｉｚｅｒ ｕｓｉｎｇ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｔｈｅｏｒｙ［Ｃ］．Ｐｒｏｃ．Ｔｈｅ Ｓｉｘｔｈ Ｉｎｔ．Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｍｉｃｒｏ Ｍａｃｈｉｎｅ ａｎｄ Ｈｕｍａｎ Ｓｃｉｅｎｃｅ，Ｎａｇｏｙａ，Ｊａｐａｎ，１ ９９５．３９－４３ ［３】Ｋｅｎｎｅｄｙ Ｊ，Ｅｂｅｒｈａｒｔ Ｒ Ｃ，Ｓｈｉ Ｙ Ｓｗａｒｍ ｉｎｔｅｌｌｉｇｅｎｃｅ［Ｍ］．Ｓａｎ Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ Ｐｕｂｌｉｓｈｅｒｓ，２００ １ ［４】Ｄａｕｔｅｎｈａｈｎ Ｋ．Ｂｏｏｋ ｒｅｖｉｅｗ：Ｓｗａｒｍ ｎｉｔｅｌｌｉｇｅｎｃｅ［Ｊ］．Ｇｅｎｅｔｉｃ Ｐｒｏｇｒａｍｍｉｎｇ ａｎｄ Ｅｖｏｌｖａｂｌｅ Ｍａｃｈｉｎｅｓ，２００２，３（１）：９３－ ９７ 编辑漆蓉