改进的细菌群体趋药性算法及应用

杨凡 宋洪儒

（铜陵学院，安徽铜陵244000）

改进的细菌群体趋药性算法及应用

杨凡 宋洪儒

（铜陵学院，安徽铜陵244000）

为使细菌群体趋药性(BCC)算法中细菌群体初始种群在解空间足够均匀，文章提出改进的BCC算法，利用均匀设计方法优选出合适的初始种群，以充分利用解空间的信息；将改进的算法，应用于函数优化上，结果表明改进后的算法在函数进化代数和寻优成功率上都有较大的提高，说明改进的方式能提高BCC算法整体运行性能。

细菌群体趋药性；均匀设计；函数优化

源于大自然生物过程的启迪，例如生物的进化过程，昆虫觅食行为等，发展出了遗传算法、蚁群算法等智能优化方法。Miiler及其同事们模拟细菌在引诱剂环境下的应激机制，于2002年提出了细菌趋药性（Bacterial Chemotaxis，BC）算法[1]。浙江大学的李威武等人在BC算法的基础上，利用群体智能的思想，于2005年提出了细菌群体趋药性（Bacterial Colony Chemotaxis，BCC）算法[2]。BC/BCC算法及其改进算法已经成功应用于函数优化[3]、电力系统无功优化[4]等领域，预示着其良好的应用前景。

随着研究的深入，该算法的优化性能瓶颈成为制约其应用的核心问题，许多学者致力于算法改进工作。

目前，BCC算法对初始种群的分布一般采用随机选取的方式，难以在算法开始运行时提供有效的解空间信息。为了较好的表征解空间，利用均匀设计生成初始菌群，会对BCC算法的性能提高有一定作用。

1.细菌趋药性算法（BC）描述

该算法的步骤如下[1]：

（1）确定细菌初始位置，初始收敛精度，最终收敛精度，进化精度更新策略，系统参数T0、τc、b。

（2）计算细菌在新方向上的移动时间τ；计算新运动方向[1]。

1）τ的数值由概率分布决定：

2）新方向与原来轨迹的夹角根据新向左或向右偏转分别服从下面两个高斯概率分布：

其中，它们的期望和方差分别按参考文献1的方式给出。

（3）计算细菌在变量空间中新的位置：

2.细菌群体趋药性算法(BCC)

BC算法是基于单个细菌的搜索，通过不断感受它周围的环境的变化和利用它过去的经验来寻找最优点，其寻优能力尚不及其他群体智能优化算法；李威武等人提出了细菌群体趋药性（BCC）算法[2]。在寻优过程中细菌充分利用个体信息和群体的信息，使算法的性能有了很大的提高。

算法步骤如下[2]：

（1）确定群体细菌算法中，细菌的个数，依据BC算法步骤（1）和（2）确定各参数及计算运动时间和方向。

（2）对处在移动步数k的细菌i，感知其周围有更好位置的其他细菌，并确定它们的中心点Cente（r）和一个假定的朝这个中心方向移动的长度len=rand(·)dis(,Center())，确定位置；

（3）对处在移动步数k的细菌i，同时根据它自己记忆的上几步的位置信息按BC算法步骤(3)确定在步数k+1时的新位置；

（5）重复步骤2-4，直至中止条件满足。

采用全体参数更新策略进行参数更新和细菌的迁徙动作，并引入精英保留策略。

3． BCC算法的改进

BCC算法由于细菌的运动表现出一定的趋同性，增加了群体陷入局部最优的可能性。为了进一步提高算法鲁棒性、效率和有效性，提出均匀设计初始种群的改进方式。

均匀设计是一种可以用最少的信息来获得空间最多信息的一种方法，它已经成功地应用于遗传算法的初始种群与操作参数的设计，并且取得了良好的效果[5]。借鉴于遗传算法初始种群的优化，本文将引入均匀设计的思想，对BCC算法的初始种群进行设计。

对初始分布点进行均匀设计，实验次数20次，2个因素，对应空间2维坐标，采用实数进行编码，即U20(202)；均匀设计表的方法很多，这里采用好格子方法，均匀性度量函数中心化L2偏差，得到多个均匀化偏差值最小的均匀设计表，表1。

表1 U20（202）

4.BCC算法及改进算法在函数中的应用

为验证函数的有效性，设计如下测试方案：初始菌群由均匀设计生成，细菌之间操作步骤仍然遵循BCC算法方法；测试函数如下：

函数F1中有全局最小值F(-0.9095537，-0.9505717)=34.0402425；和一个局部最小值F(1，1)=74；该函数易陷入局部最小，很少能够找到全局最小值。

函数F2的局部极小点为在区间范围存在大量的局部极小点。如图1所示:

图1 F2(x,y)函数空间图

为比较不同初始菌群生成方法对算法性能的影响，对BCC及改进BCC算法进行测试，参数设置如下，细菌个数20个，初始精度设为10-2，收敛精度10-10，精度下降梯度1.15；以为例进行寻优，使用随机方法和均匀设计方法产生初始菌群的情况分别如图2和图3所示，其进化曲线如图4所示。

图2 随机分布点图

图3 均匀分布点图

图4 BCC与改进BCC的寻优结果

通过运行算法100次并统计结果可知，为找到最优解，BCC算法需进化37代左右，而改进的BCC算法在进化20代后，所有细菌都能达到最优值，并且当细菌寻找到最小值后，所有细菌将聚集在最小点处。

表2 两种方式在F2(x，y)上性能比较

从表2可以看出，BCC算法的初始分布点由随机分布方式改为均匀分布方式后，最终点位置的精度维持不变，运行所需的时间有所增加，但找到最小值的成功率大幅度提升。

5． 结论

BCC算法是一种群体智能优化算法，针对该算法的性能瓶颈，提出使用均匀设计生成初始菌群，对原算法进行了改进。通过函数仿真实验表明，改进算法在进化代数上有较大的减少、且对函数寻优的成功率较高，具有一定的应用前景。

［1］Müller Sibylle D.,Marchetto Jarno,Airaghi Stefano.Optimization Based on Bacterial Chemotaxis[J].IEEE Transaction of Evolutionary Computation,2002,6(1):16-29.

［2］李威武，王慧，邹志君等.基于细菌群体趋药性的函数优化方法[J].电路与系统学报,2005,10(1):58-63.

［3］刘文霞，刘晓茹，张建华等.基于微分进化和混沌迁移的细菌群体趋药性算法[J].控制理论与应用,2009,26(4):353-357.

［4］吕慧显.基于微细菌群体趋药性的函数优化算法[J].青岛大学学报（工程技术版）,2009,24(1):19-25.

［5］何大阔，王福利，贾明兴.遗传算法初始种群与操作参数的均匀设计[J].东北大学学报，2009，26(9):828-831.

TP18

A

1672-0547（2010）06-0061-02

2010-11-06

杨凡（1978-），女，辽宁营口人，铜陵学院数学与计算机科学系助教，硕士，研究方向：进化计算。

安徽省高等学校省级自然科学研究项目《细菌群体趋药性算法的改进与应用》(编号：KJ2010B458)阶段性成果。