基于正态云模型的自适应细菌觅食优化算法

杜文军，孙 斌

(东北电力大学 教务处，吉林 吉林 132012)

杜文军，孙 斌

(东北电力大学 教务处，吉林 吉林 132012)

在研究细菌觅食算法趋化、复制、迁徙操作等相关理论的基础上，将云模型和遗传算法相关理论引入，对细菌觅食算法进行优化和改进，在趋化操作中运用X条件云发生器自适应调整细菌灵敏度，控制游动步长，提高了算法的收敛速度；在复制操作中利用遗传算法交叉编译原理，设计交叉算子和遗传算子对算法的复制操作改进，提高算法的局部搜索能力和种群的多样性；在迁徙操作中，利用正向正态云发生器，修正非线性自适应的迁移概率，增强了算法全局寻优能力。最后将改进后的算法应用于自动组卷系统，并与遗传算法进行实验结果比较分析。

细菌觅食优化算法；正态云模型；自动组卷

细菌觅食优化算法(Bacterial Foraging Optimization Algorithm BFOA)是由Passing[1]等人由大肠杆菌的群体觅食行为所启发于2002年提出是一种群集智能优化算法，具有较强的局部搜索能力及全局搜索能力，因其在解决实际应用领域中优化问题的高效性被广泛应用，成为仿生算法研究领域的热点。ZHOU Y L[2，3]等人采用余弦函数的递减性对算法的趋化操作的游动步长进行改进，提高了算法的局部搜索能力；李珺[4，5]等人设计了自适应动态步长调整函数，自适应调整步长，提高了算法的收敛精度；童雅林[6]在算法的复制操作中引入了轮盘赌选机制，提高算法的收敛速度；周文宏[7]等人在算法迁徙操作中引入方差理论，更新菌群的群体适应度，防止算法陷入局部最优，提高算法的灵活性和全局搜索能力；程翔[8]等人引入维度自适应学习算法，提高了解的精度和搜索效率；LIU X Z[9]等人将免疫理论引入算法，设计了一种免疫算法与菌群算法结合的细菌觅食优化算法。总之，来自不同领域的学者对BFOA进行了一系列改进优化，广泛应用于车间调度[10]、图像处理[11]、PID控制器设计[12]、电网规划[13]、故障诊断[14]等领域中。目前针对BFOA的研究对细菌觅食过程中自然环境的随机性和模糊信息的处理尚未有充分的考虑，对细菌觅食算法在自动组卷系统的应用研究还不成熟。

本文在研究细菌觅食算法相关理论的基础上，将云模型理论中正态云发生器和X条件云发生器引入算法，结合遗传算法交叉、变异理论，设计了一种基于云模型的自适应细菌觅食优化算法。

1 相关理论研究

1.1 细菌觅食算法[15-18]

细菌觅食算法的思想源于大肠杆菌的觅食行为，大肠杆菌表面遍布着鞭毛，在觅食过程中通过鞭毛来移动和旋转，当鞭毛沿逆时针方向转动时，大肠杆菌向前游动，当鞭毛沿顺时针方向转动时，大肠杆菌在原地旋转(翻转)，通常大肠杆菌在食物较多的环境中较多的游动，而在食物匮乏的区域较多的翻转。大肠杆菌的觅食过程主要包括寻找食物源区域、在区域中寻找食物、根据食物的消耗决定是否迁徙。细菌觅食算法正式利用大肠杆菌的这一觅食过程而提出的一种仿生搜索算法。趋化(Chemotaxis)、复制(Reproduction)和迁徙-消亡(Elimination-Dispersal)操作是BFOA算法的主要步骤。

(1)趋化操作

θi(j+1，k，l)=θi(j，k，l)+C(i)φ(i，j)，

(1)

(2)

其中：θi(j+1，k，l)为细菌个体i在第j次趋向性操作、第k次复制操作和第l次迁徙操作之后的位置；φ(i，j)为随机方向上的单位向量。

(2)复制操作

复制操作模拟了细菌种群优胜劣汰的繁殖过程，大肠杆菌在进行一段觅食过程后，部分寻找食物能力弱的细菌(适应度或健康度)会被淘汰，剩余适应能力强的细菌为了维持群体的规模将进行繁殖。在细菌觅食算法中细菌的觅食能力强弱描述为健康度或适应度。数学表示为适应度函数

(3)

适应度函数值越大表示细菌的觅食能力越强，按照适应度值的优劣对细菌排序，淘汰适应度值差的Sr=S/2个细菌，复制Sr个觅食能力强的细菌，保持细菌的总体规模不变。

(3)迁徙操作

由于细菌的生活区域受环境变化和其他外力的影响可能导致细菌群体迁移到新的区域或集体死亡。在BFOA算法中描述为迁徙操作，迁徙通常以一定的概率发生。表述为Ped。如果个体满足迁徙发生的概率则这个细菌个体灭亡，并在解空间区域的任意位置随机地生成一个新个体。在BFOA算法中以给定的迁徙概率Ped和[0，1]的随机数r对菌群中的每一个个体循环操作，达到使一些细菌被以很小概率的随机地灭亡，同时新细菌在搜索空间的随即位置被初始化。

1.2 云模型

云模型思想由李德毅[19，20]院士等于1995年提出，云模型实现了定性概念与定量数值之间的转换，正态云模型在知识表达时模糊中带有确定性、稳定中带有变化的规律，能够将定性概念的模糊性和随机性有机地结合在一起。

(1)云模型

李德毅院士的云模型是用语言值表示的某个定性概念与定量表示之间的不确定性转换模型。期望Ex(Expected Value)、熵En(Entropy)和超熵He(Hyper Entropy)是云模型的3个数字特征，表示为C(Ex，En，He)。期望是定性概念的点，是概念量化的样本；熵是定性概念的不确定性度量；超熵是熵的不确定量度。

(2)正太云发生器

云发生器是云生成的实现，正向云发生器(Forward Cloud Generator)是从定性概念到其定量表示的映射，它根据云的数字特征(Ex，En，He)产生云滴，每个云滴都是该概念的一次具体实现。正向正态云发生器的算法表述见文献[21]，条件云发生器是正向正态云发生器的一种。

1.3 遗传算法交叉变异理论

遗传算法(Genetic Algorithm)由J.Holland[22]75年首先提出，又叫基因进化算法，属于启发式搜索算法一种。具有内在的隐并行性和全局寻优能力，能自动优化的搜索空间，自适应地调整搜索方向，已被人们广泛地应用于过程控制和人工智能等领域[23]。交叉和变异操作是遗传算法的核心步骤，交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作以提高算法的搜索能力；变异是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动以提高算法的局部搜索能力。

2 细菌觅食优化算法的改进

基于上述研究，本文在BFOA算法中引入正向云发生器和X条件云发生器，依据生物学理论，提出细菌活性的概念，利用X条件云发生器调整和控制细菌游动步长，改进趋化操作，提高算法的自适应性和收敛速度；引入遗传算法交叉变异理论，改进算法的复制操作，在算法的复制操作中增加杂交算子和变异算子，使算法跳出局部最优和提高细菌种群的多样性；引入正向正态云发生器动态调整算法的迁徙概率，提高算法的全局寻优能力。

2.1 趋化操作的改进

趋化操作步骤主要是翻转和游动，李荣[24，25]等人采用线性递减的方法调整细菌灵敏度，本文在此基础上，利用X条件云发生器控制细菌的游动步长，使其以正向正态云的形状递减，以提高算法的收敛和防止陷入局部最优。

(1)细菌活性初始值

(4)

式中：V0为细菌活性初值；Xmax、Xmin为变量的边界；fi为细菌i的适应度；fmax为种群的最大适应度值；r为[0，1]之间的随机数。

(2)翻转操作定义

θi(j+1，k，l)=θi(j，k，l)+C(i)φ(i，j)，

(5)

式中：θi(j+1，k，l)为第i个细菌在进行第j次趋化操作、第k次复制操作以及第l次迁移操作后的位置；C(i)>0为细菌i当前游动的步长；φ(i，j)为细菌i翻转后选择的随机单位方向。

(3)游动操作

Ex=Sa，

(6)

En=(Smax-Smin)/m1，

(7)

(8)

(9)

(10)

其中：Sa为游动次数的平均值；Si为当前细菌游动的次数；V为游动步长；m1、n1为控制参数。

2.2 复制操作的改进

BFOA算法的复制包括选择策略和复制策略，引入遗传算法的杂交和变异理论，通过杂交算子将当前最差的一半细菌个体与当前优秀细菌个体进行杂交，让最差的一半细菌个体向着最好的位置前进；变异算子对当前搜索到的适应度函数值最好的半数细菌在其自身位置周围进行微小的位置扰动，从而避免算法陷入早熟。杂交算子的公式为

X′(i，k)=λX(i，k)+(1-λ)X(best，k)k=1，2，…，p,

(11)

其中：λ为[0，1]之间的均匀分布的随机数；X(best，k)为到目前为止菌群中搜索到的最优位置。变异算子如下所示：

X′(i)=X(i)+N(0，1).

(12)

2.3 迁徙操作的改进

引入正向正态云发生器动态调整细菌的迁移概率Pe，随机选择一个个体的适应度作为正态云发生器的期望，以种群适应度两级差值为搜索边界生成云滴，适应度值大的细菌生成较多的云滴，适应度值小的细菌生成较少的云滴。

Ex=fa，

(13)

(14)

(15)

(16)

(17)

其中：fa为个体的适应度(健康度)值；fmax、fmin和fav分别为适应度(健康度)值的最大值、最小值和平均值；m2、n2为控制参数。迁移操作随机生成新个体：

Ex=Xa，

(18)

En=Q/m3，Q=t3(Xfmax-Xfmin)，

(19)

(20)

(21)

(22)

(23)

3 试验及分析

将改进算法应用于实践是验证算法改进有效途径，为验证本文改进的细菌觅食优化算法的有效性，将改进后的应用于智能组卷系统，通过与遗传算法的实验数据进行比较分析。崔金玲[26，27]等人对智能组卷系统的数学模型进行了详细的论述，本文在此基础上构建试卷的数学模型和实验算法。

3.1 试卷模型

试卷中的试题主要包含以下属性：(1)试题编号(试题的唯一标识)；(2)题型编号(1-单选题，2-多选题，3-判断题，4-填空题，5-问答题)；(3)试题难度系数(学生的失分率)；(4)试卷区分度(区分学生水平能力)；(5)考试时间；(6)题分。

将一份试卷映射为一个细菌个体，试卷中每道试题由上述6个属性约束，构成一个属性向量(题号a1，题型a2，难度a3，区分度a4，时间a5，题分a6)，含有m道试题的试卷可以看作m×6矩阵A。

其中：aij表示第i道试题的第j个属性。试卷模型的约束条件如下：

3.2 约束函数

表1 收敛精度比较

3.3 算法步骤

步骤1 编码。本文采用二进制编码，将一份试卷映射为一个细菌个体，将试题编号作为细菌个体基因，按照不同题型分段编码。

步骤2 初始化参数。各参数设置如表1所示。

步骤3 适应度函数：f=e-βF，β=0.03；

步骤4 初始化种群；

步骤5 迁移循环：l=l+1；

步骤6 复制循环：K=k+1；

步骤7 趋化循环：j=j+1：

(1)根据公式(1)计算fi，fmax求得V0。

(2)翻转。从相应的题型的试题库中随机挑选试题替换，对细菌i随机产生题型编号Q1，随机产生Q1种题型的题数Q2做为新个体。

(3)游动。根据公式(5)至公式(9)计算游动步长C。

步骤8 若j>Nc，则转向步骤7。

步骤9 复制操作。选出适应度值最大的个体做为精英细菌，对适应度值较小的一半按公式(10)进行变异操作，对另一半通过精英细菌按公式(11)进行杂交操作。

步骤10 若k

步骤11 迁徙操作。比较fa与fav，根据公式(12)至公式(16)计算迁移率Pe，若需要生成新的个体，则根据公式(17)至公式(22)更新个体。

步骤12 若l

图1 试验结果

3.3 结果及分析

本文所使用的实验环境为matlab7.1(作为仿真软件)，SQL Server2008数据库。试题库中测试题目数为1 000，设置单选题、多选题，填空题，判断题、问答题等五种题型，各题型的测试数目为200。分别运行算法，对其收敛精度、收敛时间进行比较分析，可见改进后的BFOA算法应用于智能组卷系统中，其收敛精度优于遗传算法，可以较快收敛至最优解，组卷成功率较高。

4 总 结

本文将云模型及遗传算法的相关理论融入到细菌觅食算法的改进中，提出了一种基于云模型的自适应细菌觅食优化算法，在算法趋化操作中，采用云模型正态云发生器中的X条件云发生器动态自适应控制游动步长，提高了算法的收敛速度；在复制操作中，引入交叉算子和变异算子，提高了算法搜索全局最优的能力，避免了算法早熟，提高了解的精度；在迁徙操作中利用正向正态云发生器提高适应度值较大个体的迁移概率，提高算法的全局搜索速度。最后将改进后的算法应用于智能组卷系统，通过实验分析证明算法改进的效果和价值。

[1] J.R.Koza.Genetic programming：on the programming of computers by means of natural evolution[M].Boston：MIT Press，1992.

[2] Y.L.Zhou.Research and application on bacteria foraging optimization algorithm[J].Computer Engineering and Applications，2010，46(20)：16-21.

[3] 姜建国，周佳薇，郑迎春.一种自适应细菌觅食优化算法[J].西安电子科技大学学报，2015，42(1)：75-81.

[4] 李珺，党建武，卜锋.自适应步长的细菌觅食优化算法研究[J].兰州交通大学学报，2013，32(6)：10-14.

[5] C.J.Chen，W.G.Hu，Y.X.Du.Adaptive variable step size bacterial foraging optimization[J].Commputer Engineering and Applications，2012，48(33)：29-33.

[6] 童雅林.基于自适应的细菌觅食优化算法研究[D].合肥：合肥工业大学，2015.

[7] 周文宏，雷欣，姜建国，等.变概率混合细菌觅食优化算法[J].系统工程与电子技术，2016，38(4)：960-964.

[8] 程翔，刘升.云自适应混合细菌觅食优化算法[J].微电子学与计算机，2015，32(5)：111-117.

[9] X.Y.Liu，L.K.Zhao.Bacteriaforging optimization algorithm based on immune algorithm[J].Journal of Computer Applications，2012，32(3)：634-637.

[10] 崔静静，孙延明，车兰秀.改进细菌觅食算法求解车间作业调度问题[J].计算机应用研究，2011，28(9)：3324-3326.

[11] 马苗，梁建慧，郭敏.基于细菌觅食算法的SAR图像阈值分割[J].西安电子科技大学学报：自然科学版，2011，38(6)：152-158.

[12] 谢平平，李银红，刘晓娟，等.基于社会学习自适应细菌觅食算法的互联电网AGC最优PI/PID控制器设计[J].中国机电工程学报，2016，36(20)：5540-5548.

[13] 刘波，贺志佳，金昊.风力发电现状与发展趋势[J].东北电力大学学报，2016，36(2)：7-13.

[14] 李杰，彭月英，元昌安，等.基于细菌觅食优化算法的自适应阈值边缘检测[J].计算机工程，2012，38(21)：179-181.

[15] 车伟伟.菌群优化算法的研究与应用[D].南京：南京理工大学，2012.

[16] 匡芳君.群智能混合优化算法及其应用研究[D].南京：南京理工大学，2014.

[17] 冯春时.群智能优化算法及其应用[D].合肥：中国科学技术大学，2009.

[18] 汪定伟，王俊伟，王洪峰，等.智能优化方法[M].北京，高等教育出版社，2007.

[19] 李德毅，孟海军，史雪梅.隶属云和隶属云发生器[J].计算机研究与发展，1995，32(6)：15-20.

[20] 李德毅，刘常昱.论正态云模型的普适性[J].中国工程科学，2004，6(8)：28-34.

[21] 张光卫，何锐，刘禹.基于云模型的进化算法[J].计算机学报，2008，31(7)：1082-1091.

[22] J.H.Holland.Adaption in Natural and Artificial System[M].Boston：MIT Press，1975：10-56.

[23] 王迪，吴鑫强，王振浩.基于改进遗传算法的含分布式电源配电网故障定位[J].东北电力大学学报，2016，36(1)：1-6.

[24] 许鑫.细菌觅食优化算法的研究[D].长春：吉林大学，2012.

[25] 李荣，简献忠，陈青.基于免疫进化细菌觅食优化算法的无功优化[J].上海理工大学学报，2014，36(3)：245-249.

[26] 牛辉.智能组卷的数学模型[D].武汉：华中科技大学，2013.

[27] 崔金玲，吴迪.基于免疫进化细菌觅食优化算法的无功优化[J].河南师范大学学报：自然科学版，2014，44(2)：148-156.

Abstract：On the basis of studying the process of chemotaxis，reproduction，migration theories of Bacteria Foraging Optimization Algorithm，the theory of cloud model and genetic algorithm is introduced into the improvement.Firstly，adjusted by the X-conditional cloud generator for controlling swim steps in the operation of chemotaxis，the convergence rate is improved by this method.Secondly，In the reprodurtion operation，give both the cross operator and mutation operator to improve the local search ability and population diversity.then，in the operation of elimination and dispersal，the adaptive and norrlincar probability of elimination and dispersal is adopted by the forward normal cloud generator，which improves the global-optimization capability.Finally，this algorithm is used to the system of automatic test，compared and analyzed with the experiment of Ucnetic Algorithm.

Keywords：Bacteria foraging optimization algorithm；Normal cloud model；Automatic test

TheAdaptiveBacteriaForagingOptimizationAlgorithmBasedonNormalCloudModel

DuWenjun，SunBin

(Teaching Affairs Department，Northeast Electric Power University，Jilin Jilin 132012)

TP29

A

2017-05-12

杜文军(1982-)，男，硕士，助教，主要研究方向：计算机理论与应用.

电子邮箱：114339185@qq.com(杜文军)；358538315@qq.com(孙斌)

1005-2992(2017)05-0102-07