第 ２８ 卷第 １０ 期 ２０１１ 年 １０ 月　 计 算 机 应 用 研 究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏｌ畅２８ Ｎｏ畅１０ Ｏｃｔ畅２０１１ 倡 基 于 细 菌 觅 食 趋 化 算 子 的 PSO 算 法 杨　萍ａ， 孙延明ａ， 刘小龙ａ， 车兰秀ｂ （ 华南理工大学 ａ．工商管理学院； ｂ．科技开发公司， 广州 ５１０６４０） 摘　要： ＰＳＯ 算法是模拟鸟群觅食的一种解决优化问题的仿生算法，为了避免其在优化过程中过快陷入局部极 值的缺陷，提出一种新的基于细菌觅食趋化算子 ＰＳＯ 算法。 结合细菌觅食算法的局部搜索优势，将其趋化思想 引入到 ＰＳＯ 算法中。 通过典型函数优化测试表明，该算法可以有效弥补 ＰＳＯ 算法精度不高、容易陷入局部最优 的缺陷。 新算法是一种全局优化算法，适用于解决复杂特别是多峰不规则的函数优化。 关键词： 粒子群优化算法； 细菌觅食； 趋化； 全局优化 中图分类号： ＴＰ３０１．６　　　文献标志码： Ａ　　　文章编号： １００１唱３６９５（２０１１）１０唱３６４０唱０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１唱３６９５．２０１１．１０．００８ Ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ｂａｓｅｄ ｏｎ ｃｈｅｍｏｔａｘｉｓ ｏｐｅｒａｔｉｏｎ ｏｆ ｂａｃｔｅｒｉａｌ ｆｏｒａｇｉｎｇ ａｌｇｏｒｉｔｈｍ ＹＡＮＧ Ｐｉｎｇａ， ＳＵＮ Ｙａｎ唱ｍｉｎｇａ， ＬＩＵ Ｘｉａｏ唱ｌｏｎｇａ， ＣＨＥ Ｌａｎ唱ｘｉｕｂ （a．School of Business Administration， b．Technology Development Company， South China University of Technology， Guangzhou ５１０６４０， China） Abstract： ＰＳＯ ｉｓ ａ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ．Ｔｏ ａｖｏｉｄ ｆａｌｌ ｉｎｔｏ ｔｈｅ ｌｏｃａｌ ｍｉｎｉｍｕｍ ｉｎ ｔｈｅ ｓｔａｎｄａｒｄ ＰＳＯ ａｌ唱 ｇｏｒｉｔｈｍ， ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｄ ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｔｈｅ ｏｐｅｒａｔｏｒ ｏｆ ｃｈｅｍｏｔａｘｉｓ ｉｎ ｔｈｅ ｂａｃｔｅｒｉａｌ ｆｏｒａｇｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ａｌｇｏ唱 ｒｉｔｈｍ ｍａｄｅ ｕｓｅ ｏｆ ｔｈｅ ａｄｖａｎｔａｇｅ ｔｈａｔ ｔｈｅ ｂａｃｔｅｒｉａｌ ｆｏｒａｇｉｎｇ ａｌｇｏｒｉｔｈｍ ｗａｓ ｅａｓｙ ｔｏ ｓｅａｒｃｈ ｆｏｒ ｔｈｅ ｏｐｔｉｍａｌ ｖａｌｕｅ ｉｎ ｒｅｇｉｏｎ．Ｔｅｓｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｃａｎ ｃｏｍｐｅｎｓａｔｅ ｆｏｒ ｔｈｅ ｄｅｆｅｃｔｓ ｏｆ ｌｏｗ ｐｒｅｃｉｓｉｏｎ ａｎｄ ｆａｌｌｉｎｇ ｉｎｔｏ ｌｏｃａｌ ｍｉｎｉｍｕｍ．Ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｃｏｍｐｌｅｘ ｆｕｎｃｔｉｏｎｓ． Key words： ＰＳＯ； ｂａｃｔｅｒｉａｌ ｆｏｒａｇｉｎｇ； ｃｈｅｍｏｔａｘｉｓ； ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ 杆菌在人体肠道内吞噬食物的觅食行为而提出的一种新型仿 式上引入周围极值，在演化过程中粒子以一种递增方式进行扩 散操作，使得种群信息得到更加充分的利用，同时通过非线性 调整惯性权重、扩散操作引导极值变化来增强群体对信息的利 用能力。 1　基于细菌觅食趋化算子的 PSO 算法 1畅1　细菌觅食算法 　　２０ 世纪４０ 年代以来，人们一直在利用生物系统的灵感来 解决高维度、多峰值、非线性且不可微分的工程实际问题，进而 构造和设计出了许多仿生优化算法。 Ｋｅｎｎｅｄｙ 和 Ｅｂｅｒｈａｒｔ 于 １９９５ 年提出的粒子群优化算法（ＰＳＯ） 就是其中一种基于迭代 的模拟鸟群觅食行为的优化算法，它通过粒子的自我认知和群 体认知能力，经过多次的迭代更新从而找到全局最优解。 该算 法不需要梯度信息，可调参数少，容易实现且运行效率高。 现 在，粒子群算法已经在函数优化、工程系统控制和车间调度等 细菌觅食算法（ＢＦＡ）是 Ｐａｓｓｉｎａ 于２００２ 年基于 Ｅｃｏｌｉ 大肠 领域中成功应用。 但随着函数维度的增加，算法很容易陷入局 部最优解。 为了克服算法的这一缺陷，众多研究者对该算法进 生类优化算法。 在 ＢＦＡ 模型中，优化问题的解对应搜索空间 行了探讨和改进。 中细菌的状态。 算法包括趋化、复制和驱散三个步骤。 趋化操 将寿命的思想融入到 ＰＳＯ 中，即给全局最优 ［１］ Ｚｈａｎｇ 等人 作包括翻转和游动；复制则根据“ 优胜劣汰，适者生存” 的原 粒子设置了一个生命周期，当生命周期结束时重新选择全局最 则，在细菌生命周期结束时，以趋化过程中各细菌适应度值累 优粒子，此方法能较好地解决 ＰＳＯ 算法容易落入局部最优的 加和为标准，较差半数细菌死亡，较好的一半分裂成两个，从而 缺点。 高鹰等人 取代另一半；为了减小陷入局部极小值的机会，ＢＦＡ 引入驱散 异的 ＰＳＯ 算法中，有效避免了算法陷入局部最优。 李鹏等 操作。 在细菌完成一定次数的复制后，以一定概率将其随机驱 ［３］ 散到搜索空间。 算法，此算法改变了粒子的更新方式，减少了粒子对初值的信 在 ＢＦＡ 算法中，趋化步骤是细菌实现最优觅食最重要的 赖，增强了算法跳出局部最优的能力。 许小丽 一个步骤。 它首先定义细菌向任意方向移动的单位步长为翻 带交叉因子的改进粒子群优化算法，新算法提高了全局搜索能 转，当细菌完成一次翻转后，若适应度值得到改善，将沿同一方 力，但同时也增加了搜索时间。 任小波等人 ［５］ 　　收稿日期： ２０１１唱０１唱２７； 修回日期： ２０１１唱０３唱１４　　基金项目： 高等院校博士学科点专项科研基金资助项目（２００６０５６１００２）；国家自然科学 基金资助项目（５０６７５０６９） 作者简介： 杨萍（１９８６唱），女，广东揭阳人，硕士研究生，主要研究方向为工业工程和过程控制（４７４４１９４６９＠ｑｑ．ｃｏｍ）；孙延明（１９６８唱） 男，教授， 博导，主要研究方向为现代制造信息系统、复杂系统；刘小龙（１９７７唱），男，博 士 研 究 生，主 要 研 究 方 向 为 复 杂 系 统、智 能 算 法 与 管 理 决 策；车 兰 秀 （１９６８唱） 女，工程师，主要研究方向为大气污染控制及科研开发管理． 把粒子群算法和郭涛算法结合起来提出的一种新的混合 把模拟退火思想引入到具有杂交和高斯变 ［２］ ［４］ 提出了一种 在粒子更新方 人 

杨　萍，等：基于细菌觅食趋化算子的 ＰＳＯ 算法 ２ 所示。 ·１４６３· 　　　 ΔT（i）Δ（i） φ（i） ＝ Δ（i） 优化的趋化步骤实质就是细菌在解空间中对可行解的邻域进 P（i，j ＋１，k，l） ＝P（i， j， k， l） ＋C（i）φ（i） 第 １０ 期 向继续移动若干步，直至适应度值不再改善或达到预定的移动 步数，此过程定义为游动。 细菌觅食算法中的趋化行为可具体 描述如下： 设细菌每个个体代表解空间的一个解，P（i， j， k， l） 表示 细菌 i 的空间位置向量。 其中：j 表示第 j 代趋化循环，k 表示 第 k 代繁殖循环，l 表示第 l 代迁移循环，用式（２）调整方向。 （１） （２） 其中：C（i）表示按选定的方向游动的单位步长，Δ（i）是生成的 随机向量，φ（i） 表示进行方向调整后选定的方向。 细菌觅食 行搜索，并通过适应度函数判定是继续在该方向游动还是重新 对方向进行调整。 趋化算子保证了细菌单体总可以找到其所 在邻域内的最优值。 1畅2　粒子群优化算法 １９９５ 年提出了 ＰＳＯ 算法；１９９８ 年，Ｓｈｉ 等人对经典 ＰＳＯ 算 法进行了修改，提出了目前广泛使用的标准 ＰＳＯ 算法：设在一 个 D 维的目标搜索空间中， 由 N 个粒子组成一个群体，其中第 i 个粒子的位置表示为一个 D 维向量 Xi ＝（xi１，xi２，…，xiD）， i ＝１，２，…，N，即每个粒子的位置就是一个潜在的解。 第 i 个 粒子的飞行速度也是 D 维向量，记为 Vi ＝（vi１，vi２，…，viD）。 ＰＳＯ 初始化一群随机粒子，然后通过迭代找到最优解。 在每一 次迭代中，粒子通过跟踪两个极值来更新自己的位置。 第一个 就是粒子目前自身所找到的最优解，这个解叫做个体极值 Pb； 另一个极值是整个种群目前找到的最优解，这个极值是全局极 值 Pg。 则可用下式对粒子的速度和位置进行更新： vid（t ＋１） ＝wvid（t） ＋c１ r１（pid（t） －xid（t）） ＋ xid（t ＋１） ＝xid（t） ＋vid（t ＋１） 文结合了细菌觅食算法中细菌单体总可以找到其所在邻域内 （３） （４） 其中：i ＝１，２，…，N；d ＝１，２，…，D；w 为惯性权重；学习因子 c１ 和 c２ 是非负常数；r１ 和 r２ 是两个相互独立的在区间［０，１］ 上 均匀分布的伪随机数；速度上限｜vid｜≤vｍａｘid。 1畅3　基于细菌觅食趋化算子的 PSO 算法 由 ＰＳＯ 算法原理可以看出，惯性权重 w 虽然可以使粒子 在算法初期有较大的探索能力，而在后期有较大的开发能力。 但由于粒子速度过大，在探索过程中，粒子很容易飞过最优解 所在的局部区域而没有发现最优值，从而陷入局部最优。 为了避免粒子在探索过程中错过了更优解所在的区域，本 最优值的优势，在适当的时机使用趋化算子调整 ＰＳＯ 算法中 粒子的位置，使得粒子在到达新的区域后能找到所在区域中的 最优解，从而避免粒子在探索过程中错过更优解。 而适当的时 机是指在迭代过程中需要更新全局最优解时，因为这个时候粒 子所在的邻域出现更优解的可能性很大。 另外在局部搜索过程中，应当重视细菌趋化算子的步长。 步长过长，粒子同样容易错过最优值；步长过短，虽能精确找到 局部最优解但会倍数级地增加计算量。 因此对于不同的测试 函数需要采用不同的步长值，后面进行测试的函数会采用不同 步长进行，这些步长都是经过测试而选定的。 改进后的 ＰＳＯ 算法，不仅保留了 ＰＳＯ 原有算法的优点，并 且更适合于优化多峰测试函数。 实验结果表明了该算法的优 越性能，整个算法的流程描述如图１ 所示，局部搜索流程如图 c２ r２（pgd（t） －xid（t）） 2　实验仿真与结果分析 2畅1　检验函数 实验函数采用 Ｒｏｓｅｎｂｒｏｃｋ、Ｒａｓｔｒｉｇｉｎ、Ｇｒｉｅｗａｎｋ 和 Ａｃｋｌｅｙ 四 个标准测试函数。 ａ）Ｒｏｓｅｎｂｒｏｃｋ 函数 f１。 f１（x） ＝∑n －１ i ＝１［１００（xi ＋１ －x２ 该单峰函数全局最优为 ０，最优解为 X（１， １，…， １）。 该 函数在靠近最优点的区域为香蕉状，并且变量之间具有很强的 相关性，且梯度信息经常误导算法的搜索方向。 i ）２ ＋（xi －１）２］　xi∈［ －５，１０］ i －１０ ｃｏｓ（２πxi） ＋１０］　xi∈［ －５畅１２，５畅１２］ ｂ）Ｒａｓｔｒｉｇｉｎ 函数 f２。 f２（x） ＝∑n 该多峰函数全局最优为０，最优解为 Ｘ（０， …， ０）。 该多 峰函数具有大量按正弦拐点排列的、很深的局部最优点，优化 算法很容易在通往全局最优点的路径上陷入一个局部最优点。 ｃ）Ｇｒｉｅｗａｎｋ 函数 f３。 f３（x） ＝ １ ４０００　∑n i －∏n i ＝１x２ 该多峰函数全局最优为０，最优解为 X（０， …， ０）。 该函 数是一个复杂的多峰函数，存在大量的局部最小点和高大障碍 物，由于各变量点显著相关，优化算法很容易陷入局部最优。 ＋１　xi∈［ －６００，６００］ i ＝１［x２ i ＝１ｃｏｓ xi i ｄ）Ａｃｋｌｅｙ 函数 f４。 １ i ＝１x２ f４（x） ＝２０ ＋ｅ －２０ｅ i － n ∑n －１ i ＝１ｃｏｓ（２πxi）　xi∈［ －１５，３０］ n ∑n ｅ －１５ 该多峰函数全局最优为０，最优解为 X（０， …， ０）。 该函数 是一个具有大量局部最优点的多峰函数，优化非常困难，算法很 容易陷入通向全局最优点的局部最优上。 以上四个测试函数，即使采用传统的优化方法也很难优 化，且优化的难度会随着测试函数的维数增加而急剧上升。 对于低维单峰函数，粒子群优化算法可得到满意的优化结 果；但对于高维的多峰函数问题，粒子群优化算法的优化效 果难以令人满意。 基于此，四个测试函数的维度设置为３０ 维 和５０ 维。 为了测试新算法的性能，本文同时对细菌觅食算法 ＢＦＡ、 粒子群算法 ＰＳＯ、本文提出的基于细菌觅食趋化算子的粒子群 算法 ＢＦＡ唱ＰＳＯ 在上述四个高维多峰函数中进行了测试。 

计 算 机 应 用 研 究 　 第 ２８ 卷 适应度值呈直线形式下降，说明趋化算子找到的局部最优值给 全局寻优提供了很大的帮助，大大减少了陷入局部最优的机 会，同时加快了收敛速度。 ·２４６３· 2畅2　对比实验参数设置 对于标准粒子群算法，粒子个数 N ＝４０，w ＝wｍａｘ －（（wｍａｘ － wｍｉｎ） ／M）t，其中 wｍａｘ ＝０畅９，wｍｉｎ ＝０畅４，学习因子 c１ ＝c２ ＝２。 迭代次数为１ ０００ 次；对于单纯的细菌觅食算法，主要参数有细 菌数 s ＝５０，迁移次数 Nｅｄ ＝２，繁殖次数 Nｒｅ ＝４，趋化次数 Nｃ ＝ ４０，游动次数 Nｓ ＝３，迁移概率 Pｅｄ ＝０畅２５，游动步长 C ＝０畅００１R （R 为优化区间的宽度）。 对于混合算法中的参数，粒子数 N ＝ ４０，wｍａｘ ＝０畅９，wｍｉｎ ＝０畅４，学习因子 c１ ＝c２ ＝２，而细菌趋化算子 中的最大趋化次数为５０，迭代次数为１ ０００， 步长参数 C 随测 试函数的不同而不同。 经测试函数 f１ 的步长为 ０畅０１，函数 f２ 的步长为０畅０７５，函数 f３ 的步长为１，函数 f４ 的步长为０畅５。 当 然，如果想得到更精确的值可以把步长再设小点，本文是综合 考虑了精确度和计算时间而选择的步长。 2畅3　实验结果与分析 将三种算法在以上四个函数上测试５０ 次，测试结果如表 １ 所示。 其中，优化均值是指所有优化结果中的平均值；标准 差是成功搜索５０ 次的最优值标准差；最优值是指５０ 次测试中 得到的最好值。 表 １　测试结果 f２ f３ f４ f１ ３０ ５０ ３０ ５０ ３０ 函数 维度 测试项目 最优值 优化均值 （ 标准差） 最优值 优化均值 （ 标准差） 最优值 优化均值 （ 标准差） 最优值 优化均值 （ 标准差） 最优值 优化均值 （ 标准差） 优化均值 （ 标准差） ＢＦＡ ．１０４ｅ ＋０２ ２ （３８．７７） １．３１９０ｅ ＋０２ ．７５１８ｅ ＋０２ ２ （２０．４５０９） ２．３３７４ｅ ＋０２ １ ．０２１８ｅ ＋０２ （５．７１８３） ９．０４８０ｅ ＋０１ ．０２７５ｅ ＋０２ ２ （９．６５４４） １．７２２９ｅ ＋０２ ７ ．５２ｅ ＋０１ （１３．０２４３） ５．９５８７ｅ ＋０１ ２ ．６３ｅ ＋０２ （３４．４７３９） １．８０５４ｅ ＋０２ ．８８ｅ ＋０１ １ （０．２６３７） １．８１ｅ ＋０１ ．９２６４ｅ ＋０１ （０．１３７５） １．８９ｅ ＋０１ ＰＳＯ ．２２２ｅ ＋０２ ３ （１４２．７） ６．７５８２ｅ ＋０１ ．２２０４ｅ ＋０２ ３２ （９９．７０３０） ９．５３２８ｅ ＋０１ １ ．０６６６ｅ ＋０２ （１７．３６５６） ７．０４３６ｅ ＋０１ ２ ．４３８２ｅ ＋０２ （３５．１２７１） １．９８４０ｅ ＋０２ １ ．０３９７ｅ ＋０１ （３．３０４７） ４．５７０７ ４ ．２３５３ｅ ＋０１ （１１．８５５６） ２．２７０５ｅ ＋０１ ．１１７２ｅ ＋０１ １ （１．６６４３） ８．００７０ １ ．３５ｅ ＋０１ （９．６８ｅ －０１） １．１１ｅ ＋０１ ＢＦＡ唱ＰＳＯ ９ ．６９４１ｅ －０４ （５．３７４７ｅ －０４） ２．７２８４ｅ －０４ ６ ．１０１４ｅ －０３ （１．５７４６ｅ －０３） ２．４３９５ｅ －０３ ．１６１０ｅ ＋０１ １ （２．９７７２） ２．９８６７ ．９３３７ｅ ＋０１ ４ （８．８４０６） ２．９９８２ｅ ＋０１ １ ．６４ｅ －０３ （１．９４０８ｅ －０３） ２．８３ｅ －０４ ４ ．５８ｅ －０３ （３．４３７２ｅ －０３） １．３６０１ｅ －０３ ．６７６６ｅ －０２ ３ （９．９５０３ｅ －０３） ３．６７６６ｅ －０２ ．１１２８ ０ （０．０１１１） １．００ｅ －０１ 　　由表１ 结果可以看出，改进的 ＰＳＯ 算法在四个测试函数 的优化结果均比标准的 ＰＳＯ 算法和 ＢＦＡ 算法好，不管是优化 均值还是最优值。 算法的稳定性也很显著，即标准差普遍较 小。 新算法在 f１、f３ 和 f４ 的优化效果很明显，基本上达到精度 的要求。 由于 f２ 函数的局部最优值密度大而且很深，优化难 度很大，在新算法中适当加大粒子数能达到更好的结果，但效 果有限。 总之，不管对于单峰函数 f１ 还是多峰函数 f２、f３ 和 f４， 新算法在收敛速度、计算精度和算法的稳定性上都有显著 提高。 由图３ 和４ 的收敛效果可知，标准粒子群算法进化到一定 代数后，会出现停滞状态或以很慢的速度迭代，新算法提出用 细菌趋化思想来进行局部搜索，收敛速度非常快，有些地方的 最优值 优化均值 （ 标准差） 最优值 优化均值 （ 标准差） 最优值 ５０ ３０ ５０ １ 可以在一定程度防止粒子由于速度过快而飞过最优值存在的 3　结束语 本文通过将细菌觅食算法中的趋化算子嵌入粒子群算法， 在粒子群算法的全局最优改变时，对粒子位置进行局部搜索， 从而找出粒子所在区域的最优值，以确保粒子不会错过已搜索 的区域的最优值，在局部区域做到了精细搜索。 这种改进方法 区域。 实验数据表明，改进后的粒子群算法，无论在搜索精度 还是算法稳定性上，均显著优于单一的粒子群算法和细菌觅食 算法，从而也证实了改进算法的有效性。 后续研究的方向是对 该 ＢＦＡ 与 ＰＳＯ 结合的参数设置进行更深入的讨论，以及探讨 将该方法应用于工程实例。 参考文献： ［１］ ＺＨＡＮＧ Ｊｕｎ，ＬＩＮ Ｙｉｎｇ．Ａ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚｅｒ ｗｉｔｈ ｌｉｆｅｓｐａｎ ｆｏｒ ｇｌｏｂａｌ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｎ ｍｕｌｔｉｍｏｄａｌ ｆｕｎｃｔｉｏｎｓ［Ｃ］ ／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｃｏｎ唱 ｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ．２００８：２４３９唱２４４５． ［２］ 高鹰，谢胜利．基于模拟退火的粒子群优化算法［Ｊ］．计算机工程 与应用，２００４，40（１）：４７唱５０． ［３］ 李鹏，全惠云．改 进 的 混 合 粒 子 群 算 法［Ｊ］．计 算 机 工 程 与 应 用， ２０１０，46（１１）：２９唱３１． ［４］ 许小丽．一种新的交叉粒子群算法［Ｊ］．四川理工学院学报：自然 科学版，２０１０，23（１）：１９唱２２． ［５］ 任小波，于东，杨忠秀，等．一种信息充分交流的扩散粒子群算法 ［Ｊ］．大连海事大学学报，２０１０，36（１）：１５９唱１６１．