基于免疫算法的细菌觅食算法优化研究

马 宁，廖慧惠

(1.安徽广播电视大学,安徽 合肥 230022; 2.安徽工业经济职业技术学院,安徽 合肥 230051)

基于免疫算法的细菌觅食算法优化研究

马 宁1，廖慧惠2

(1.安徽广播电视大学,安徽 合肥 230022; 2.安徽工业经济职业技术学院,安徽 合肥 230051)

细菌觅食算法BFA(Bacterial Foraging Algorithm)作为一种理论新颖、搜索机制独特的新型算法，广泛应用于各种智能优化问题.但是细菌觅食算法经常出现的速度较慢、步长一致的缺陷，提出在BFA的趋向性操作环节中调节细菌游动的步长，将步长逐步减小，以提高收敛速度.引入免疫算法中的克隆选择思想对细菌觅食算法中的复制操作进行替代；并通过实例对优化后的算法进行验证，结果表明：优化后的算法更加精确，寻优能力更强，稳定性更佳.

细菌觅食算法；免疫算法；优化

引言

参考自然界生物群体行为，人们相继研究出多种群体智能优化算法.其中Kenned、Eberhart两位学者在20世纪90年代中期根据鸟群捕食行为研制出PSO算法，即粒子群优化算法[1]，这一算法的应用范围极广，在各领域均发挥着重要作用[2～4]，除了各项实践问题；Passino学者依据人体肠道内大肠杆菌吞噬食物的实际过程，构建出BFA算法，即细菌觅食算法[5]，掀起了生物运算领域的研究热潮.从整体上来看，不同算法的特征各不相同，具有一定的优势和不足，BFA算法的收敛精度、搜索性能较差，但便于跳出局部极限的约束，收敛速度相对较快.很多学者开展了大量研究，一起提高BFA算法的性能，并整合了该算法和其他算法，这些整合算法主要包括分布估计算法、粒子群算法等.储颖学者[6]就参考粒子群优化算法的信息共享机制，优化改进了细菌觅食算法的群体感应机制；DasguptaA学者[7]等将交叉、变异操作引入到原算法内，构建了混合细菌觅食算法；KimDH学者[8]研究出GA-BFO算法；Biswas A学者[9]在细菌觅食算法的趋化算子中融入粒子群法，形成了新型算法，无需借助趋化操作；以Kim[10]为代表的学者们在BFO算法内融入变异算子及交叉算子，形成了GABFO算法；Luh学者[11]基于细菌进化的层面，构建了BEA算法(细菌进化算法)；刘小龙[12]等多位学者在繁殖算子中融入分布估计算法思路，分布估计再生的半数细菌，这些细菌都具有良好的细菌能量，对细菌自适应迁移率进行了分析，指定随机迁移了能量不良的细菌，希望改善细菌寻优性能，若在低概率下迁移能量良好的细菌，从本质上迁移即为退化解的过程，降低了寻优专区恶性，切寻优速度大大降低；Biswas学者[13]讲粒子群法引入到细菌趋化算子内，确保细菌对全局极值的感知性，借助迭代公式来更新细菌位置，弱化了趋化算子的功能性，使时间复杂性增大；Dasgupta学者[13]等将变异和交叉算子都融合到细菌进化内，丰富了种群类型，然而也存在优良个体的缺失问题.

鉴于以上情况，本文通过利用免疫算法中的克隆选择思想对筛选出来的最优细菌进行繁殖变异,随着克隆细菌群落的变异以及随机交叉，进而替换细菌群落中适应度最差个体，指引算法提升搜索的精准度，并且通过调节细菌游动的步长来提高细菌觅食优化算法的收敛速度，实例证明免疫算法可以使细菌群体的搜索精度以及适应度有效提高.

1 细菌觅食优化算法的基本原理分析

基于BFO算法下，模型赢编码待优化问题，对其解在搜索空间内细菌的具体状态进行定义.在处理实际问题的过程中，可以划分为以下几步：形成初始解群体、对评价函数值进行运算、借助群体彼此影响、作用机制实施迭代优化，在这个过程中应对趋化、繁殖及迁移三大算子进行循环式的执行操作，从而得到最优解.在算法模型内，对细菌实现最有觅食的行为进行模拟可以形成趋化算子，体现为在游动、翻转作用下，细菌能够游动并集中到营养较为丰富的位置，进行有目标化的运动，探索出最优路径.在细菌觅食优化算法下，细菌在不同方向上的移动单位步长即为翻转，而游动为若翻转后细菌适应值有所改善，需要继续沿此方向进行移动，实现适应值的最优化.细菌单个完整生命周期就是算法定义趋化周期，若结束生命周期，细菌会在遵循生物生存法则进行淘汰式繁殖.执行细菌觅食优化算法的过程中，应注重低等生物自身的繁殖性能及其对环境的适应能力，Passino学者将非常规的觅食策略融入到该算法的执行中，认为细菌能量就是趋化时细菌的适应值的总和，半数细菌(能量较差)在单个生命周期中死亡，且半数细菌繁殖(能量良好)变为两个子细菌，则母代细菌生物特点会被子细菌所继承.

趋化算子能够使子细菌局部搜索准确性得到明显改善，细菌快速收敛性借助繁殖算子能够大大增加.如果需要解决的NP问题相对繁琐和复杂，要想不出现局部极小的状况，使算法全局寻优性能增大，就要结合算法限定，在细菌结束繁殖操作后，在搜索空间随意位置，按照特定概率对其进行迁移.

由此得知，细菌局部搜索性能在BFO算法下的实现，依靠的是趋化算子能够随机搜索领域，也能够结合适应度调控方向.因为没有发挥群体周边细菌信息运用机制应用的作用，所以使算法收敛速度降低，出现局部最优的状况.完成趋化周期后，结合细菌能量，算法能够执行繁殖操作，这就能够改善寻优准确性，然而由于算法具有局部最优的缺陷，所以也会出现一系列的不熟和早熟等现象.

2 基于免疫算法的细菌觅食优化算法的实现过程

建立在免疫系统基础上的免疫算法处于一种学习算法，涵盖于人工免疫系统研究领域.20世纪70年代，Jerne学者[14]就构建出免疫系统模型和免疫系统数学框架，之后Pereslon对上述研究成果进行完善，提出独特型网络的概率描述法[15]，并将该算法用于机器人运动路径规划领域内，并取得了明显的进步.免疫算法能够形成求解复杂系统优化问题法，与问题具体领域并没有较大的联系，在问题类型方面具有良好的鲁棒性，在不同学科中均发挥着极其重要的作用，包括控制工程领域、建筑结构设计领域及函数设计领域等.免疫算法原理相对繁琐，结合相关调查分析显示，免疫算法融合性较强[16]，能够有效融合蚁群算法、鸟群算法和主流遗传算法等，然而当前很少有研究学者分析免疫算法同细菌觅食优化算法的整合.

Mori学者[17]就针对免疫算法进行了研究，认为免疫算法对抗体剑亲和度的关注程度较低，只是分析抗原、抗体剑的亲和度，其借助良好的搜索性能，能够在网络安全[18]、路径规划[19～20]等方面发挥重要作用.本研究主要针对免疫算法的克隆选择卢纶，开展其同细菌觅食算的复制融合研究，希望能够改善算法的搜索精度和整体性能.

基于免疫算法的细菌觅食优化算法的实现过程为：

针对细菌种群开展趋化操作.

1)形成单位向量Ψ(j)，细菌进行翻转.

2)对细菌的种群位置进行改善.细菌个体要结合灵敏度开展群游操作，若适应度增大到最大值，表示完成操作，则灵敏度表示成：

(1)

公式内灵敏度算子是Ddlta，其数值同适应度函数变化范围有直接的联系.细菌群游式表示成：

Xnew(j)=X(j)+VΨ(j)

(2)

公式内趋化周期是j.

3)细菌进行繁殖再生，结束趋化操作，依次按照克隆、变异、交叉和选择的顺序处理当前细菌群体.

4)根据适应度加和对细菌排序，精英细菌就是待克隆群体，为Sr个细菌(适应度较强).细菌群个数的半数为精英细菌，Sr=S/2.

5)克隆繁殖精英细菌，克隆群体表示为Sc， 那么

best_fit=best_fit/max(best_fit)

(3)

(4)

结合公式(3)，对适应度进行标准化处理，结合公式(4)对精英细菌的数量进行运算，得出，克隆繁殖数Sc_size，细菌个体的适应度与克隆群体的数量成正比，度量细胞抗原和抗体的亲和度递增函数表示为β.

Sc(i)=Sc(i)+δrand()X_best

(5)

δ=exp(-best_fit(St-I+1))

(6)

参考公式(5)进行高频变异，变异概率为δ，细菌个体适应度与变异概率越大两者呈正比关系，而且适应度越强大表示搜索空间更加广阔.

Cross_X=Sc(k1)-Sc(k2)+Sc(k3)-Sc(k4)

(7)

Sn=Sc+Si

(8)

结合公式(7)进行随机交叉，克隆群体内随意对差异化的细菌个体进行选择，得到k1,k2,k3,k4，免疫细胞为Si个，按照公式(8)将其融入在克隆群体内，构建出Sn，即克隆繁殖细菌群.

在Sn内对适应度最强的细菌个体进行挑选，数量为Sr个，将其替换板书细菌个体(适应度不强).

6)执行细菌驱散操作，在增强算法全局搜索性能的过程中，要结合驱散概率，驱散适应度不强的细菌.

迁移标准细菌模式算法时，算法能够对概率ped进行确定，在解空间内对细菌个体进行随意性的迁移，如果概率ped比随机数要大，那么需要求迁移该细菌，借助该方式来提升细菌跳出局部极值的概率.鉴于算法内细菌迁移的概率一致，很可能会迁移全局最优值周边或寻优能力相对较强的细菌，就等同于细菌丢失探寻最优解的可能，迁移就会转变为退化解的过程，根本起不到改善寻优精度和加快寻优速度的效果.

改进细菌的迁移操作后，就不应驱散适应度相对较强的细菌，要结合概率来对细菌执行驱散操作，这样能够消除细菌在处于全局最优化附近而被驱散现象的发生，也能够使细菌群摆脱局部最优限制的约束.

7)对循环结束进行判断，若达到结束条件就应结束循环，可以将结果进行输出.

结合算法基本原理，对免疫优化下细菌觅食优化算法实现流程进行归纳，结果详见图1：

图1 基于免疫优化的细菌觅食优化算法流程

3 对免疫细菌觅食优化算法收敛性的验证

在DASGUPTA文章中分析BFA算法的收敛性时[13],对细菌觅食算法进行模拟菌群中每个细菌个体相互发生的影响没有进行充分的考虑.由于文中提到的融合免疫算法结合并入，因此对于融合免疫算法的收敛性需要重新进行验证.按照学者李涛的研究[14]：抗体种群为Aο，抗体空间几何I*，V(A(k))通过计算得出最优解个数B*，

(9)

进行简化,可得

(10)

由此可以得到此算法进行收敛直到最优解集的概率为1.如果算法迭代数量达到一定上限时，就会进行一定的收敛.在融合免疫算法中的抗体种群用A0表示,如下:

(11)

其中，Ai(k)表示细菌i在第k次操作的时候所在的位置，而Ai(k)是由Ai(k-1)经过克隆、变异而得.马尔克失链可对这一过程进行描述.

为了方便表述，标记：

(12)

由贝叶斯条件概率公式有：

(13)

(14)

由免疫算法的特征可知：

(15)

则有

(16)

又因为

(17)

P{v(A(k+1))≥1|v(A(k))=0}≥ζ≻0

(18)

所以

P{v(A(k+1))=0|v(A(k))=0}=1-P{v(A(k+1))≠1|v(A(k))=0}≤1-ζ1

(19)

故而

0≤P0(k+1)≤…≤(1-ζ)k+1P0(0)

(20)

因为

(21)

0≤P0(0)≤1

(22)

所以

(23)

所以

(24)

综上所述，GBFA以概率1收敛.

4 GBFA的性能分析

选取Sphere函数f1=(x1)、Griewank函数f2=(x2)、Rastrigrin函数f3=(x3)作为测试函数：

(25)

图2 Sphere函数的寻优曲线(左为传统BFA，右为GBFA)

图3 Griewank函数的寻优曲线(左为传统BFA，右为GBFA)

图4 Rastrigrin函数的寻优曲线(左为传统BFA，右为GBFA)

从图2～图4，可以看出：图2中，对于Sphere函数的寻优曲线，GBFA仅需要12次迭代便可以寻找出最优值，而传统BFA需要22次迭代才可以寻找出最优值，迭代次数为GBFA的2.67倍；Griewank函数具有很强的震荡性质，一般无法找到它们的最优解.从图3可以看出，传统BFA无法找到Griewank函数的最优解，但GBFA搜索到的最优解为0，说明GBFA的搜索能力远大于传统BFA.图4中，对于Rastrigrin函数的寻优曲线，GBFA仅仅需要23次迭代便可以寻找出最优值，而传统BFA需要53次迭代才可以寻找出最优值，迭代次数为GBFA的2.30倍.简而言之，GBFA的搜索能力和搜索速度远大于传统BFA.

GBFA和传统BFA收敛精度的比较见表1.

表1 GBFA和传统BFA收敛精度

通过表1，对于Sphere函数f1(x1)、Griewank函数f2(x2)、Rastrigrin函数f3=(x3)，融合免疫算法的精度远大于传统BFA，寻优能力更强.并且，融合免疫算法的方差均小于传统BFA的方差，说明融合免疫算法的稳定性更好.

5 结论

本文针对BFA算法的三个操作环节(复制操作环节、趋向性操作环节和迁移操作环节)，免疫算法克隆选择思想的相关思想，提出BFA的一种融合免疫算法.并利用Sphere函数f1(x1)、Griewank函数f2(x2)、Rastrigrin函数f3(x3)作为实例进行验证，发现融合免疫算法的搜索能力和搜索速度远大于传统BFA，寻优能力更强、稳定性更好.

[1]黄少荣．粒子群优化算法综述[J]．计算机工程与设计，2009(8):1977-1980.

[2]付志军，冯丽，杜伟宁，等．离散粒子群优化算法在流水作业调度问题中的应用[J]．吉林大学学报: 理学版，2014，52(3):561-564.

[3]任贝，韩飞，吴坚．基于遗传算法的摄像机标定[J].吉林大学学报: 信息科学版,2013(4) : 432-436.

[4]张杭悦，陈谋．基于混合优化鱼群算法的近空间飞行器控制分配[J]．吉林大学学报: 信息科学版，2014(4):369-376． [5]周雅兰．细菌觅食优化算法的研究与应用[J].计算机工程与应用,2010,46(20):16-21． [6]储颖，糜华，纪震，等.基于粒子群优化的快速细菌群游算法[J]．数据采集与处理，2010，25(4) : 442-448． [7]DasguptaA,DasguptaS,DasS,etal.Asynergyofdifferentialevolutionandbacterialforagingoptimization.forglobaloptimization[J].NeuralNetworkWord,2007,17(6): 607-626.

[8]KimDH,AbrahamA,ChoJH.Ahybridgeneticalgorithmandbacterialforagingapproach[J].InformationSciences, 2007, 177(18): 3918-3937.

[9]BiswasA,DasguptaS,DasS,etal.SynergyofPSOandbacterialforagingop-timization:Acomparativestudyonnumericalbenchmarks[C].Procofthe2ndIntSymposiumonHybridArtificialIntelligentSystems.Salamanca, 2007:255-263.

[10]NAYAGAMAVLG，MURALIKRISHNANS，SIVARAMANG．Multi-criteriadecision-makingmethodbasedoninterval-valuedintuitionisticfuzzysets[J]．ExpertSystemswithApplications，2011，38(3) : 1464-1467． [11]NAYAGAMAVLG，SIVARAMANG．Rankingofintervalvaluedintuitionisticfuzzysets[J]．AppliedSoftComputing，2011，11(4) : 3368-3372.

[12]刘小龙，李荣钧，杨萍．基于高斯分布估计的细菌觅食优化算法[J]．控制与决策，2011，26(8) : 1233-1238.

[13]BISWASA，DASGUPTAS，DASS，etal．SynergyofPSOandbacterialforagingoptimization—Acomparativestudyonnumericalbenchmarks[EB/OL]．[2010-05-10]．http: //www．softcomputing．net/hais072．pdf.

[14]Jerne.N.K.TowardsaNetworkTheoryoftheImmuneSystem.AnnualImmunology, 1974,125C:373-389.

[15]Perelson.A.S.ImmuneNetworkTheory.ImmunologicalReview,1989,10:5-36.

[16]莫宏伟．人工免疫系统原理与应用[M]．哈尔滨: 哈尔滨工业大学出版社，2002.

[17]MORIK，TSUKIYAMAM，FUKUDAT．ImmuneAlgorithmwithSearchingDiversityandItsApplicationtoResourceAllocationProblem[J]．Transactions-InstituteofElectricalEngineersofJapan，1993，113C(10) : 872-878.

[18]刘丽峰，张树清，李新红．人工免疫算法路径规划在林火救援中的应用[J]．吉林大学学报: 信息科学版，2012，30(4):433-440.

[19]江超，王海燕，陈磊，等．基于生物免疫原理的新型无线传感器网络安全算法[J]．吉林大学学报: 理学版，2013，50(6):1204-1208.

[20]胡亮，王程明，赵阔，等．基于人工免疫模型的入侵检测系统中检测器生成算法的分析与改进[J]．吉林大学学报:理学版，2010，48(1) : 67-72．

On Bacterial Foraging Algorithm Optimization based on Immune Algorithm

MA Ning1, LIAO Hui-hui2

(1.Anhui Radio and Television University, Hefei Anhui 230022，China;2. Anhui Technical College of Industry and Economy, Hefei Anhui 230051, China)

BFA (Bacterial Foraging Algorithm) is a new algorithm with novel theory and unique search mechanism widely used to solve intelligent optimization problems, but with low speed and uniform step length. In this paper, the step length of bacterial swimming is adjusted in the directional operation of BFA and reduced gradually to improve the convergence speed and the idea of clonal selection in immune algorithm is introduced to replace the copy operation in bacterial foraging algorithm. Case verification results show that optimized algorithm is more accurate, more powerful and more stable.

bacterial foraging algorithm; immune algorithm; optimization

1673-2103(2017)02-0019-07

2016-12-08

安徽省优秀青年基金重点项目支持(2013SQRL097ZD)；安徽省高校优秀青年人才支持计划重点项目支持(gxyqZD2016454)

马宁(1983-)，男，安徽亳州人，硕士，讲师，研究方向：数据挖掘，云计算、模式识别及算法研究.

Q93;TP18

A