智能优化算法理论与应用-细菌群的趋向性操作

假定要求J（θ）的最小值，其中，且梯度∇J（θ）无法测量也不能仅分析描述。为了求解无梯度优化问题，BFO算法模拟了真实的细菌系统中的四个主要操作：趋向、聚集、复制和迁徙。实际上，每个真实的细菌可以看成是优化问题的一个为寻找最优解而移动在函数曲面上的测试解，如图6.2所示。

为了模拟实际细菌的行为，首先引入以下记号：j表示趋向性操作，k表示复制操作，l表示迁徙操作。此外，令：

p：搜索空间的维数，

S：细菌种群大小；

Nc：细菌进行趋向性行为的次数；

Ns：趋向性操作中在一个方向上前进的最大步数；

Nre：细菌进行复制性行为的次数；

Ned：细菌进行迁徙性行为的次数；

Ped：迁徙概率；

C（i）：向前游动的步长。

设P（j，k，l）=｛θi（j，k，l）|i=1，2，…，S｝表示种群中个体在第j次趋向性操作、第k次复制操作和第l次迁徙操作之后的位置，J（i，j，k，l）表示细菌i在第j次趋向性操作、第k次复制操作和第l次迁徙操作之后的适应值函数值。

图6.2　位于多模态目标函数曲面上的细菌群

1.趋向性操作（Chemotaxis）

大肠杆菌在整个觅食过程中有两个基本运动：游动（swim）和旋转（tumble）。游动是沿与上一步相同的方向运动，而旋转是找一个新的方向运动。细菌的趋向性操作就是对这两种基本动作的模拟。通常，细菌在环境差的区域（如食物匮乏区域）会较频繁地旋转，而在环境好的区域（如食物丰富的区域）会较多地游动。其操作方式如下：朝某随机方向游动一步；如果该方向上的适应值不再优于上一步所处位置的适应值，则进行旋转，朝另外一个随机方向游动；如果达到最大尝试次数，则停止该细菌的趋向性操作，跳转到下一个细菌执行趋向性操作。大肠杆菌的整个生命周期一直在游动和旋转这两个基本运动中进行变换，游动和旋转的目的是寻找食物。在BFO算法中模拟这种现象称为趋向性操作。

细菌i的每一步趋向性操作表示如下

(www.xing528.com)

其中Δ表示随机方向上的一个单位向量。

2.聚集性操作（Swarming）

在菌群寻觅食物的过程中，细菌个体通过相互之间的作用来达到聚集行为。细胞与细胞之间既有引力又有斥力。引力使细菌聚集在一起，甚至出现“抱团”现象。斥力使每个细胞都有一定的位置，令其能在该位置上获取能量，来维持生存。在BFO算法中模拟这种行为称为聚集性操作。细菌间聚集行为的数学表达式为

其中，dattractant为引力的深度，wattractant为引力的宽度，hrepellant为斥力的高度，wrepellant为斥力的宽度为细菌i的第m个分量，θm为整个菌群中其他细菌的第m个分量。式（6.2）的含义为：整体菌群在细菌i所处位置处所产生的作用力之和。一般情况下，取dattractant=hrepellant。

由于Jcc（θ，P（j，k，l））表示种群细菌之间传递信号的影响值，所以在趋向性循环中引入聚集操作后，第i个细菌的适应值的计算公式变为

从而，聚集操作通过式（6.3）来对适应值进行修正，使得细菌达到聚集的目的。

3.复制性操作（Reproduction）

生物进化过程一直是优胜劣汰。经过一段时间的觅食过程后，部分觅食能力弱的细菌会被自然淘汰，而为了维持种群规模不变，剩余的寻找食物能力强的细菌会进行繁殖。在BFO算法中模拟这种现象称为复制性操作。

对给定的k，l以及每个i=1，2，…，S，定义

为细菌i的健康度函数（或能量函数），以此来衡量细菌所获得的能量。越大，表示细菌i越健康，其觅食能力越强。将细菌能量Jhealth按从小到大的顺序排列，淘汰掉前Sr=S/2个能量值较小的细菌，选择后Sr个能量值较大的细菌进行复制，使其各自生成一个与自己完全相同的新个体，即生成的新个体所处的位置与原个体相同，或者说新旧个体具有相同的觅食能力。

4.迁徙性操作（Elimination and dispersal）

实际环境中的细菌个体所生活的局部区域可能会突然发生变化（如温度突然升高等）或者逐渐变化（如食物的消耗）。这样可能会导致生活在这个局部区域的细菌种群集体被外力杀死或者被迁徙到新的区域中去。在BFO算法中模拟这种现象称为迁徙性操作。

迁徙操作虽然破坏了细菌的趋向性过程，但是细菌也可能会因此寻找到食物更加丰富的区域。所以从长远来看，这种迁徙操作是有利于菌群觅食的。为模拟这一事件，在算法中菌群经过若干代复制后，细菌以给定概率Ped执行迁徙操作，被随机重新分配到寻优区间。即：若种群中的某个细菌个体满足迁徙发生的概率，则这个细菌个体灭亡，并随机的在解空间的任意位置生成一个新个体，新个体与原个体可能具有不同的位置，即不同的觅食能力。迁徙行为随机生成的这个新个体可能更靠近全局最优解，从而更有利于趋向性操作跳出局部最优解，进而寻找全局最优解。