广义菌群优化算法

第40卷，第3期计算机科学Vol. 40 No. 32013年3月Computer ScienceMar 2013广义菌群优化算法陈建超'胡桂武1.2.3 杜小 勇°3(广东商学院数学与计算科学学院 广州510320)1(教育部数据工程与知识工程重点实验室北京 100872)2 (中国人民大学信息学院 北京 100872)*摘要为提高菌群优化算法的性能,将群体聚集机制和自适应策略集成到趋药性操作中,取消聚集操作,构造出新的趋化操作,在趋化循环中引入自适应扩散机制,提高其克服“早熟”的能力,重新定义健康度,减少计算复杂性,得到了一种新的群体智能优化方法一广 义菌群优化算法(GBFO, Generalized Bacterial Foraging Optimization)。通过10个复杂Benchmark函数的计算进行算法性能测试，并与几个典型的算法进行了实验比较,结果表明,GBFO算法在搜.索能力和稳定性、求解质量和效率等方面优于其他典型算法的比率分别达到80%~90%,70%~80%,验证了该算法的优越性能。关键词菌群优化算法,聚集,趋化操作,扩散中图法分类号TP301. 06文献标识码AGeneralized Bacterial Foraging OptimizationCHEN jian-chao' HU Gui-wul-23 DU Xiao yong".(School of Mathematics & Computational Science,Guangdong University of Business Studies ,Guangzhou 510320,China)2(Key Laboratory of Data Engineer and Knowledge Engineer for the Ministry of Education, Bejing 100872 ,China)2(School of Information, Rennin University of China, Beiing 100872 ,China)3Abstract In order to improve the performance of Bacterial Foraging Optimization (BFO) ,a new swarm intelligence op-timization algorithm, called the generalized bacterial foraging optimization (GBFO) was proposed, which has new chemotactic operation, is only composed of chemotaxis with group aggregation mechanism and adaptive strategy, and swarming is cancelled. The chemotactic loop with adaptive diffusion mechanism can improve ability of overcoming the " pre-mature' " ,and healthiness is redefined to reduce the computational complexity. 10 complex Benchmark functions weretested. The simulation shows that the GBFO has better search ability and stability, solution quality and eficiency thanother typical algorithm up to 80% ~90% ,70% ~ 80% among test functions. The comparisons also show GBFO has ex-cellent performance.Keywords Bacterial foraging optimization, Aggregation,Chemotactic operation, Diffusion鉴于以上情况,将群体聚集机制和自适应策略集成到趋1引言药性操作中,在趋化循环中引人自适应扩散机制,重新定义健菌群优化算法(Bacteria Foraging Optimization, BFO)是康度,减少计算的复杂性，得到了--种新的群体智能优化方Kevin M. PassinoL基于Ecoli大肠杆菌在人体肠道内吞噬食法一广 义菌群优化算法(GBFO,Generalized Bacterial Fora-物的觅食行为而提出的一种新型群体智能优化算法,该算法ging Optimization)。 相关实验表明GBFO算法具有优良的性具有良好的优化性能,吸引了众多研究者对该算法进行探能。讨[2-5]。相关研究表明，BFO算法的复制操作和迁徙操作在本文第2节是基本菌群优化算法和分析;第3节提出了算法设计方面没有新意,其性能主要由趋化操作(包含趋药性广义菌群优化算法;第4节是实验;最后总结全文。操作和聚集操作)决定,趋药性操作中的步长是- - 个核心的问2基本菌 群优化算法题，明显存在缺乏自适应性和无差异性的不足,不能很好地体现群体之间的协同和智能性。聚集操作带来的明显问题是参简单地说, BFO算法可以通过趋药性操作(Chemotaxis) .数多,在求解不同优化问题时,不同问题对其中的函数- -致性聚集操作(Swarming)(趋药性操作和聚集操作组合成为趋化设计存在挑战。总体来说,到现在为止还没有从算法结构上操作)、复制操作(Reproduction)和迁徒操作( Elimination and进行改进的研究。Dispersal)[4个优化过程来实现。中国煤化工到稿日期2012-05-11返修 日期:2012-08-03本 文受国家自然科学基金(60873017),国YHC N M H G1130183)资助。陈建超(1979-),男,博士,主要研究方向为智能计算、数据挖掘等, E-mail; cjcat126@ 126. com;胡桂武(1970-),男,博士后,教授,CCF高级会员,主要研究方向为数据挖掘、优化计算等;杜小勇男 ,教授，博士生导师。●251●.2.1趋药性操作理论支撑,类似的函数选择空间很大,群体间的相互作用是基BFO中的趋药性操作可描述如下:于类距离的,在求解不同优化问题时,其中的函数-致性设计0(j+1,k,l)=0(j,k,l)>+C(i)φ(j)(1)存 在挑战。式中,0(j;k,l)即个体i的位置,j,k,l分别表示趋药性循环、复制操作是基于健康度的行为,健康度是根据式(3)和式复制循环、迁移循环的代数, φ(j)表示单位方向向量,C(i)表(4)计算的， 在算法执行的晚期明显会引起不正常的震荡,容示前进的步长。易误判真实的局部最优解,式(3)中的简单加法在度量不一-致2.2 聚集操作时会影响算法的效能,简单地使用健康度高的生存、低的淘对于最小值问题，设第i个细菌个体的信息为0=(0，汰,从 自然真实情况或统计理论上来分析不一定科学。% ,.. ,),则BFO的聚集操作的数学表达式为: .迁徙操作是模仿实际环境中的细菌被外力杀死或者被驱Ja (O* ,P(j,k,l))散到新的区域中去的- -种现象， 显然具有随机搜索的优点和不足。=它J (O,0(j,k,D)3.2广义 菌群优化算法=2[-damuwexp(- -umm乌(6 - :)2)]+点鉴于以上分析,本文从以下几个方面进行了尝试,首先从[hplum xp(-wplu艺(一%)》)(2总体结构上进行了设计:删除聚集操作,结构上简化趋化操作。其次是按照式(5)重新设计步长,将群体聚集机制和自适式中,dracar ,Warecton为引力的深度和宽度,hpelan,w。为斥力的高度和宽度,0为个体i的第m个分量。此公式的应策略集成到趋药性操作中,同时在趋化循环中引人邻域自含义为整个细茵群体在细菌i所处位置0处所产生的作用力适应扩散机制，以提高算法的搜索性能,最后是重新定义健康度为适应值之和，以减少计算复杂性。之和,此时第i个个体的适应度的计算公式变为:定义1(协同步长)每 个细菌的步长C(i)由其周囿邻居J(0)= J(0)+Jx (θ ,P(j,k,l))(3与它的距离(聚集程度)决定,不再依赖于初始值,实现群体的因此聚集操作就是对适应值J(θ )进行修正，以达到使聚集和自适应。具体设计如式(5)所示。细菌聚集的目的。2.3 复制操作C()=f(1IA-B. ,I/N(i))在执行完指定步数的趋化操作之后，根据各个细菌的健式中,N()是个体 Q最近的邻居数目参数,f(.)是-一个单调康度进行排序。健康度根据相应细菌在它的生命过程中所吸递碱非负函数(最小值可以设计足够小),1I0.- -0_ll是个体收到的营养值的多少来计算。健康度定义为:0.与第j个最近邻居0. ;之间的距离。定义2(邻居平均距离)个体 A.的邻居平均距离定义如Heah()=J式中, Heath(i)表示第i个细菌的当前健康度,J表示第i个式(6)所示。细菌的适应度函数值,mum表示到当前位置时,第i个细菌所mean. _dis:=Z1I0-O_ .1l/N(i)(6)完成的趋化操作的数目。先对整个菌群按照健康度进行排式中,N(i)是个体0:最近的邻居数目。序,健康度较高的细菌有权利进行繁殖行为,生成子代。子代定义3(局部超邻域)称式(7)描述的集合为高维超空的位置、步长以及其它信息都与父代完全相同。健康度不高间中位置o;的局部超邻域。的细菌将死亡，以此来维持菌群的规模不变。算法通常的操sQ2={|0|lo:-θ≤rn}作是:式中,r。是局部超邻域的半径,为可选参数。群体中要被淘汰的个体个数设为S, = S/2(S为群体的定义4(自适应扩散)在趋化操作中 ,群体会聚集,聚集规模),首先对群体中的个体按其优劣进行排序,然后将排在到一定程度时,邻居平均距离会足够小，导致停滞,为了改变较靠后的S,个个体删除,剩下的S,个个体进行自身的复制。这种局面，当所有个体的邻居平均距离都小于daffuin (称为2.4迁徙操作“聚集距离最小值”,可初始化为20)时,进行如下操作:在执行完指定次数的复制操作之后,对整个群体中的各步骤1按照式(8)重新修正 dsfwimo个个体进行有选择的迁徙操作。迁移操作是按照给定的概率dasfuiom = hu Xmax{mean_ dis:}8)Ps发生的，如果某个体满足迁移操作的条件,那么就将此个式中,入是-一个选自区间(0,1)的系数,例如0.15,S是种群体删除,重新生成一-个新的个体,相当于将原来的个体移到了规模。一个新的位置。步骤2依次对每个个体O ,找出离0:最近的N(i)个最3广义菌群优化算法近的邻居,按式(9)计算此N(i)个个体的虚拟中心,记为0;。3.1菌群优化算法分析o;=' S0J/N(i) .9)趋药性操作是对大肠杆菌趋药性行为的两个基本动作前步骤3对于个体 0: ,在o;的局部超邻域Q内重新生成进(Swim)和翻转(Tumble)的模仿,其数学模型是式(1),步长0:C(i)不能自动反映个体在不同时候的差别以及群体的协同性中国煤化工完整描述如和智能性,针对不同问题的初始值也无理论依据。下:聚集操作是模拟菌群寻取食物的过程中,细菌个体之间步骤1初MHCNMHG通过相互间的作用而实现群体的聚集行为,式(2)是其数学模步骤2令 l=0,开始迭代次数为Na的迁徙循环，在循型。模型中的明显问题是参数多,模型中的函数选择无任何环的每次迭代中 ,递增1,循环体包含了步骤3至步骤8。●252●.步骤3令k=0,开始迭代次数为Nw的复制循环,在循环的每次迭代中,先让k递增1,健康度都初始化为0,循环体10()=- 20Xxep[- -.2√5xx1]-xp[言x器包含了步骤4至步骤7。cos(2x)]+20+e步骤4令j=0,开始迭代次数为N.的趋化循环,在循- 32