连续优化问题的细菌觅食改进算法

戴秋萍， 马 良， 郗 莹

（上海理工大学 管理学院，上海 200093）

经典的优化算法在函数优化问题中，常常要求函数连续可微，因此在求解过程中需要借助一些基于梯度信息的数学技巧，并且在接近最优解时容易出现锯齿现象，造成收敛速度缓慢［1］.20世纪50年代中期，人们从生物进化的机理中得到启发，创立了仿生学，并提出了许多解决复杂优化问题的智能方法，如神经网络、遗传算法［2］、进化策略、蚂蚁算法［3］等，这些方法在连续函数优化问题中取得了较好的结果.本文提出了一种新的智能优化算法——细菌觅食算法对连续函数优化问题进行求解.

细菌觅食算法（bacterial foraging optimization，BFO）是由Passino［4］于2002年提出来的一种仿生随机搜索算法，该算法具有群体智能性，并可进行并行搜索.目前，BFO 已被用于车间调度问题、自适应控制领域、噪声干扰下的谐波估计问题和PID（proportional integral derivative）控制器的设计等方面，并获得了较好的效果［5－6］.本文对细菌觅食算法操作步骤进行了改进，有效地改善了该算法极易陷入局部最优的缺点，使其在解决复杂连续优化问题时，全局搜索能力大大增强.另外，通过大量仿真实验验证了该算法的有效性.

1 细菌觅食算法介绍

细菌觅食算法是基于大肠杆菌在觅食过程中体现出来的智能行为的一种新型仿生优化算法，其具有群体智能性、并行性等特点.细菌觅食算法包括趋化操作（chemotaxis）、复制操作（reproduction）和迁徙（elimination and dispersal）操作.这3种操作方式是模仿细菌觅食的趋向行为、复制行为和迁移行为的抽象［7－8］.

a.趋化操作 大肠杆菌在寻找食物源的过程中，其运动是通过表层的鞭毛实现的.当鞭毛全部逆时针摆动时，大肠杆菌将会向前行；当鞭毛全部顺时针摆动时，它会减速至停止.鞭毛的摆动对应着细菌个体对当前适应值的判断，并决定是否对其位置进行调整和确定调整的方向和力度.趋化操作模拟了大肠杆菌的这个运动过程，包括游动和翻转两个操作.

设pi（j，k，l）表示细菌个体i的当前位置，j表示第j 次趋化行为，k 表示第k 次复制行为，l表示第l次迁徙行为.则

其中，φ（j）表示游动的方向； C（i） 表示前进步长.

b.复制操作 设群体规模为S，在完成设定次数的趋向操作之后，将群体中的个体按照其适应度值进行排序，将排在后面S／2 的个体删除，剩下的个体进行自我复制，保证群体规模的稳定性.

c.迁徙操作 迁徙操作按照预先设定的一个概率发生，若某一个个体满足迁徙操作发生的条件，那么即将此个体删除，并生成一个新的个体代替.相当于将原来个体重新分配到一个新的位置，即以一定的概率将个体随机驱散到搜索空间.

2 算法改进

2.1 初始化操作改进

在细菌觅食算法中，细菌种群的大小直接影响细菌寻求最优解的能力.种群数量越大，其初始覆盖区域越大，靠近最优解的概率就越大，能避免算法陷入局部极值，但同时增加了算法的计算量.因此，本文将初始化操作进行了改进.改进后，在细菌规模较小的情况下，能比较有效地改善初始化后细菌群体的覆盖范围（见图1、图2）.确定群体规模S 之后，将群体搜索的空间分成S个区域，每个细菌个体的初始位置为S个区域的中心点，随即细菌将在各自区域内搜索.

图1 改进前细菌初始化状态Fig.1 Initialization state of bacteria before improved

图2 改进后细菌个体初始化状态Fig.2 Initialization state of bacteria after improved

由图1可知，细菌个体随机生成时，菌群可能在搜索空间内分布不均，在搜索最优解过程中，极有可能在限定的游动步长内无法找到最优解而陷入局部最优.

2.2 趋化操作改进

细菌觅食算法中，趋化操作是细菌觅食过程中最重要的一个步骤.基本细菌觅食算法在进行趋化操作时，细菌个体是根据历史信息按固定步长朝着食物源方向游动.在解决连续函数优化问题，尤其是多峰函数优化问题时，传统的操作方式易使得细菌个体错过最优解，本文对趋化搜索方式进行了改进.

将细菌个体所在区域切分为n×n块，每个细菌在进行翻转操作时，仅在细菌周围的8个方向中随机选取，游动过程中每游动一次前进步长缩短为原来步长的0.8倍， C（i） ＝0.8 C（i） .当细菌个体游动次数并未达到设定游动次数时，细菌将再进行一次翻转操作.

趋化操作步骤：

a.确定细菌个体i，确定游动方向φ（j）.

c.判断当前位置是否更优，是则个体i被新个体取代，继续步骤b，步长 C（i）变为0.8 C（i） .

d.判断是否达到设定游动次数，未达到转步骤a，达到游动次数细菌个体i趋化操作结束.

2.3 复制操作改进

细菌觅食过程中，一段时间后，细菌会根据个体位置的适应度值进行优劣排序.排在后面的S／2个细菌死亡，而排在前面的S／2个细菌进行自我复制，随即细菌往较小范围聚集.在求解多峰连续优化问题时，菌群极有可能跳过最优解而陷入局部最优.

本算法将细菌个体首先随机与邻域周围的一个细菌进行交叉变异，变异后的细菌个体适应度值若优于原个体，原个体将被替代.通过一次改进后的复制操作后，整个菌群完成一次更新，菌群规模不变，每个细菌个体仅在各自区域及邻域内进行变异和适应度值比较，从而有效地防止了菌群向较小范围内聚集.改进后的复制操作不再只是觅食能力强的细菌个体单纯的自我繁殖过程，整个菌群群体都朝着更优的方向游动，提高了菌群整体的寻优能力.改进后复制操作过程如图3所示.

3 实验仿真与结果分析

前述细菌觅食算法采用Matlab 7予以实现，在PC系列机的Windows 7 系统环境下运行通过.本文通过大量实例验证了此改进算法的有效性，下面给出4个算例及求解结果分析（见图4～7，图5～7见下页）.算法相关参数设定：细菌规模为225，趋向操作数为10，复制操作数为4，迁徙操作数为2.

算例1

图3 改进后复制操作示意图Fig.3 Operation schematic diagram of improved reproduction process

图4 算例1函数示意图Fig.4 Function schematic diagram of example 1

由函数示意图可知，该函数最优解处于中间区域，周围有很多局部极值围绕着最优解，用传统的细菌觅食算法陷入局部最优的可能性非常大.元胞蚁群算法、混沌算法均可得到最优解1，LINGO 软件得到的最优解为0.646 848 8，Matlab优化工具得到的结果为0.990 3.

算例2

该问题的最优解被最差解包围，4个局部值点为（－5.12，5.12）、（－5.12，－5.12）、（5.12，5.12）、（5.12，－5.12），函数值均为2 748.78.运行改进后的细菌觅食算法求解该问题能够有效地获得最优解.

算例3

该函数在（1，1）处有最小值0，且在最优解附近存在病态，用常规方法容易陷入局部最优，难以搜索到最优解.

图5 算例2函数示意图Fig.5 Function schematic diagram of example 2

图6 算例3函数示意图Fig.6 Function schematic diagram of example 3

算例4

图7 算例4函数示意图Fig.7 Function schematic diagram of example 4

该算例可看出是典型的多峰函数，运用传统算法求解最优解相当困难.遗传算法目前所求最优解为38.827 533，运行LINGO 软件与Matlab得到的解均小于38.

表1为该算法求解上述函数运行30次后的结果分析.其中平均偏差率为算法运行30次解的平均值与最优解的比值.

4 结束语

首先对细菌初始化操作进行了改进，改变了传统的细菌觅食算法中的初始方式，使得菌群规模较小的情况下，能有较大的覆盖面.此外，本算法对细菌个体的搜索方式也进行了适当改进，增强了个体的局部搜索能力.为防止菌群在复制操作中过快地向小范围聚集而陷入局部最优，菌群进行变异性复制，不仅保证了菌群整体朝更优方向游动，同时大大提高了此算法的全局搜索能力.通过实验表明，改进后的细菌觅食算法在求解连续优化问题时，稳定性好，能够快速有效地找到最优解.

表1 结果分析Tab.1 Results analysis

通过与其它算法相比可得出以下结论：

a.改进后的细菌觅食算法改进了传统细菌觅食算法的缺点，有效地改善了传统算法的收敛速度和全局寻优能力，所获最优解质量得到改善.

b.改进后的细菌觅食算法能够有效解决连续优化问题，为连续优化问题提供一种新的解决方法.

［1］马良，朱刚，宁爱兵.蚁群优化算法［M］.北京：科学出版社，2008.

［2］张惠珍，马良.基于变尺度混沌优化策略的混合遗传算法及在神经网络中的应用［J］.上海理工大学学报，2007，29（3）：215－219.

［3］邱模杰，马良.约束平面选址问题的蚂蚁算法［J］.上海理工大学学报，2000，22（9）：61－62.

［4］Passino K M.Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Systems Magazine，2002，22（3）：52－67.

［5］梁艳春，吴春国，时小虎，等.群体智能优化算法理论与应用［M］.北京：科学出版社，2009.

［6］张娜.细菌觅食优化算法求解车间调度问题的研究［D］.吉林：吉林大学，2007.

［7］胡海波，黄友锐.混合粒子群算法优化分数阶P／D 控制参 数 研 究［J］.计 算 机 应 用，2009，29（9）：2483－2486.

［8］李亚楠.菌群优化算法的研究［D］.哈尔滨：哈尔滨工业大学，2009.