第40卷，第3期計(jì)算機(jī)科學(xué)Vol. 40 No. 32013年3月Computer ScienceMar 2013廣義菌群優(yōu)化算法陳建超'胡桂武1.2.3 杜小 勇°3(廣東商學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 廣州510320)1(教育部數(shù)據(jù)工程與知識(shí)工程重點(diǎn)實(shí)驗(yàn)室北京 100872)2 (中國(guó)人民大學(xué)信息學(xué)院 北京 100872)*摘要為提高菌群優(yōu)化算法的性能,將群體聚集機(jī)制和自適應(yīng)策略集成到趨藥性操作中,取消聚集操作,構(gòu)造出新的趨化操作,在趨化循環(huán)中引入自適應(yīng)擴(kuò)散機(jī)制,提高其克服“早熟”的能力,重新定義健康度,減少計(jì)算復(fù)雜性,得到了一種新的群體智能優(yōu)化方法一廣 義菌群優(yōu)化算法(GBFO, Generalized Bacterial Foraging Optimization)。通過(guò)10個(gè)復(fù)雜Benchmark函數(shù)的計(jì)算進(jìn)行算法性能測(cè)試，并與幾個(gè)典型的算法進(jìn)行了實(shí)驗(yàn)比較,結(jié)果表明,GBFO算法在搜.索能力和穩(wěn)定性、求解質(zhì)量和效率等方面優(yōu)于其他典型算法的比率分別達(dá)到80%~90%,70%~80%,驗(yàn)證了該算法的優(yōu)越性能。關(guān)鍵詞菌群優(yōu)化算法,聚集,趨化操作,擴(kuò)散中圖法分類號(hào)TP301. 06文獻(xiàn)標(biāo)識(shí)碼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鑒于以上情況,將群體聚集機(jī)制和自適應(yīng)策略集成到趨1引言藥性操作中,在趨化循環(huán)中引人自適應(yīng)擴(kuò)散機(jī)制,重新定義健菌群優(yōu)化算法(Bacteria Foraging Optimization, BFO)是康度,減少計(jì)算的復(fù)雜性，得到了--種新的群體智能優(yōu)化方Kevin M. PassinoL基于Ecoli大腸桿菌在人體腸道內(nèi)吞噬食法一廣 義菌群優(yōu)化算法(GBFO,Generalized Bacterial Fora-物的覓食行為而提出的一種新型群體智能優(yōu)化算法,該算法ging Optimization)。 相關(guān)實(shí)驗(yàn)表明GBFO算法具有優(yōu)良的性具有良好的優(yōu)化性能,吸引了眾多研究者對(duì)該算法進(jìn)行探能。討[2-5]。相關(guān)研究表明，BFO算法的復(fù)制操作和遷徙操作在本文第2節(jié)是基本菌群優(yōu)化算法和分析;第3節(jié)提出了算法設(shè)計(jì)方面沒(méi)有新意,其性能主要由趨化操作(包含趨藥性廣義菌群優(yōu)化算法;第4節(jié)是實(shí)驗(yàn);最后總結(jié)全文。操作和聚集操作)決定,趨藥性操作中的步長(zhǎng)是- - 個(gè)核心的問(wèn)2基本菌 群優(yōu)化算法題，明顯存在缺乏自適應(yīng)性和無(wú)差異性的不足,不能很好地體現(xiàn)群體之間的協(xié)同和智能性。聚集操作帶來(lái)的明顯問(wèn)題是參簡(jiǎn)單地說(shuō), BFO算法可以通過(guò)趨藥性操作(Chemotaxis) .數(shù)多,在求解不同優(yōu)化問(wèn)題時(shí),不同問(wèn)題對(duì)其中的函數(shù)- -致性聚集操作(Swarming)(趨藥性操作和聚集操作組合成為趨化設(shè)計(jì)存在挑戰(zhàn)?？傮w來(lái)說(shuō),到現(xiàn)在為止還沒(méi)有從算法結(jié)構(gòu)上操作)、復(fù)制操作(Reproduction)和遷徒操作( Elimination and進(jìn)行改進(jìn)的研究。Dispersal)[4個(gè)優(yōu)化過(guò)程來(lái)實(shí)現(xiàn)。中國(guó)煤化工到稿日期2012-05-11返修 日期:2012-08-03本 文受國(guó)家自然科學(xué)基金(60873017),國(guó)YHC N M H G1130183)資助。陳建超(1979-),男,博士,主要研究方向?yàn)橹悄苡?jì)算、數(shù)據(jù)挖掘等, E-mail; cjcat126@ 126. com;胡桂武(1970-),男,博士后,教授,CCF高級(jí)會(huì)員,主要研究方向?yàn)閿?shù)據(jù)挖掘、優(yōu)化計(jì)算等;杜小勇男 ,教授，博士生導(dǎo)師?！?51●.2.1趨藥性操作理論支撐,類似的函數(shù)選擇空間很大,群體間的相互作用是基BFO中的趨藥性操作可描述如下:于類距離的,在求解不同優(yōu)化問(wèn)題時(shí),其中的函數(shù)-致性設(shè)計(jì)0(j+1,k,l)=0(j,k,l)>+C(i)φ(j)(1)存 在挑戰(zhàn)。式中,0(j;k,l)即個(gè)體i的位置,j,k,l分別表示趨藥性循環(huán)、復(fù)制操作是基于健康度的行為,健康度是根據(jù)式(3)和式復(fù)制循環(huán)、遷移循環(huán)的代數(shù), φ(j)表示單位方向向量,C(i)表(4)計(jì)算的， 在算法執(zhí)行的晚期明顯會(huì)引起不正常的震蕩,容示前進(jìn)的步長(zhǎng)。易誤判真實(shí)的局部最優(yōu)解,式(3)中的簡(jiǎn)單加法在度量不一-致2.2 聚集操作時(shí)會(huì)影響算法的效能,簡(jiǎn)單地使用健康度高的生存、低的淘對(duì)于最小值問(wèn)題，設(shè)第i個(gè)細(xì)菌個(gè)體的信息為0=(0，汰,從 自然真實(shí)情況或統(tǒng)計(jì)理論上來(lái)分析不一定科學(xué)。% ,.. ,),則BFO的聚集操作的數(shù)學(xué)表達(dá)式為: .遷徙操作是模仿實(shí)際環(huán)境中的細(xì)菌被外力殺死或者被驅(qū)Ja (O* ,P(j,k,l))散到新的區(qū)域中去的- -種現(xiàn)象， 顯然具有隨機(jī)搜索的優(yōu)點(diǎn)和不足。=它J (O,0(j,k,D)3.2廣義 菌群優(yōu)化算法=2[-damuwexp(- -umm烏(6 - :)2)]+點(diǎn)鑒于以上分析,本文從以下幾個(gè)方面進(jìn)行了嘗試,首先從[hplum xp(-wplu藝(一%)》)(2總體結(jié)構(gòu)上進(jìn)行了設(shè)計(jì):刪除聚集操作,結(jié)構(gòu)上簡(jiǎn)化趨化操作。其次是按照式(5)重新設(shè)計(jì)步長(zhǎng),將群體聚集機(jī)制和自適式中,dracar ,Warecton為引力的深度和寬度,hpelan,w。為斥力的高度和寬度,0為個(gè)體i的第m個(gè)分量。此公式的應(yīng)策略集成到趨藥性操作中,同時(shí)在趨化循環(huán)中引人鄰域自含義為整個(gè)細(xì)茵群體在細(xì)菌i所處位置0處所產(chǎn)生的作用力適應(yīng)擴(kuò)散機(jī)制，以提高算法的搜索性能,最后是重新定義健康度為適應(yīng)值之和，以減少計(jì)算復(fù)雜性。之和,此時(shí)第i個(gè)個(gè)體的適應(yīng)度的計(jì)算公式變?yōu)?定義1(協(xié)同步長(zhǎng))每 個(gè)細(xì)菌的步長(zhǎng)C(i)由其周囿鄰居J(0)= J(0)+Jx (θ ,P(j,k,l))(3與它的距離(聚集程度)決定,不再依賴于初始值,實(shí)現(xiàn)群體的因此聚集操作就是對(duì)適應(yīng)值J(θ )進(jìn)行修正，以達(dá)到使聚集和自適應(yīng)。具體設(shè)計(jì)如式(5)所示。細(xì)菌聚集的目的。2.3 復(fù)制操作C()=f(1IA-B. ,I/N(i))在執(zhí)行完指定步數(shù)的趨化操作之后，根據(jù)各個(gè)細(xì)菌的健式中,N()是個(gè)體 Q最近的鄰居數(shù)目參數(shù),f(.)是-一個(gè)單調(diào)康度進(jìn)行排序。健康度根據(jù)相應(yīng)細(xì)菌在它的生命過(guò)程中所吸遞堿非負(fù)函數(shù)(最小值可以設(shè)計(jì)足夠小),1I0.- -0_ll是個(gè)體收到的營(yíng)養(yǎng)值的多少來(lái)計(jì)算。健康度定義為:0.與第j個(gè)最近鄰居0. ;之間的距離。定義2(鄰居平均距離)個(gè)體 A.的鄰居平均距離定義如Heah()=J式中, Heath(i)表示第i個(gè)細(xì)菌的當(dāng)前健康度,J表示第i個(gè)式(6)所示。細(xì)菌的適應(yīng)度函數(shù)值,mum表示到當(dāng)前位置時(shí),第i個(gè)細(xì)菌所mean. _dis:=Z1I0-O_ .1l/N(i)(6)完成的趨化操作的數(shù)目。先對(duì)整個(gè)菌群按照健康度進(jìn)行排式中,N(i)是個(gè)體0:最近的鄰居數(shù)目。序,健康度較高的細(xì)菌有權(quán)利進(jìn)行繁殖行為,生成子代。子代定義3(局部超鄰域)稱式(7)描述的集合為高維超空的位置、步長(zhǎng)以及其它信息都與父代完全相同。健康度不高間中位置o;的局部超鄰域。的細(xì)菌將死亡，以此來(lái)維持菌群的規(guī)模不變。算法通常的操sQ2={|0|lo:-θ≤rn}作是:式中,r。是局部超鄰域的半徑,為可選參數(shù)。群體中要被淘汰的個(gè)體個(gè)數(shù)設(shè)為S, = S/2(S為群體的定義4(自適應(yīng)擴(kuò)散)在趨化操作中 ,群體會(huì)聚集,聚集規(guī)模),首先對(duì)群體中的個(gè)體按其優(yōu)劣進(jìn)行排序,然后將排在到一定程度時(shí),鄰居平均距離會(huì)足夠小，導(dǎo)致停滯,為了改變較靠后的S,個(gè)個(gè)體刪除,剩下的S,個(gè)個(gè)體進(jìn)行自身的復(fù)制。這種局面，當(dāng)所有個(gè)體的鄰居平均距離都小于daffuin (稱為2.4遷徙操作“聚集距離最小值”,可初始化為20)時(shí),進(jìn)行如下操作:在執(zhí)行完指定次數(shù)的復(fù)制操作之后,對(duì)整個(gè)群體中的各步驟1按照式(8)重新修正 dsfwimo個(gè)個(gè)體進(jìn)行有選擇的遷徙操作。遷移操作是按照給定的概率dasfuiom = hu Xmax{mean_ dis:}8)Ps發(fā)生的，如果某個(gè)體滿足遷移操作的條件,那么就將此個(gè)式中,入是-一個(gè)選自區(qū)間(0,1)的系數(shù),例如0.15,S是種群體刪除,重新生成一-個(gè)新的個(gè)體,相當(dāng)于將原來(lái)的個(gè)體移到了規(guī)模。一個(gè)新的位置。步驟2依次對(duì)每個(gè)個(gè)體O ,找出離0:最近的N(i)個(gè)最3廣義菌群優(yōu)化算法近的鄰居,按式(9)計(jì)算此N(i)個(gè)個(gè)體的虛擬中心,記為0;。3.1菌群優(yōu)化算法分析o;=' S0J/N(i) .9)趨藥性操作是對(duì)大腸桿菌趨藥性行為的兩個(gè)基本動(dòng)作前步驟3對(duì)于個(gè)體 0: ,在o;的局部超鄰域Q內(nèi)重新生成進(jìn)(Swim)和翻轉(zhuǎn)(Tumble)的模仿,其數(shù)學(xué)模型是式(1),步長(zhǎng)0:C(i)不能自動(dòng)反映個(gè)體在不同時(shí)候的差別以及群體的協(xié)同性中國(guó)煤化工完整描述如和智能性,針對(duì)不同問(wèn)題的初始值也無(wú)理論依據(jù)。下:聚集操作是模擬菌群尋取食物的過(guò)程中,細(xì)菌個(gè)體之間步驟1初MHCNMHG通過(guò)相互間的作用而實(shí)現(xiàn)群體的聚集行為,式(2)是其數(shù)學(xué)模步驟2令 l=0,開始迭代次數(shù)為Na的遷徙循環(huán)，在循型。模型中的明顯問(wèn)題是參數(shù)多,模型中的函數(shù)選擇無(wú)任何環(huán)的每次迭代中 ,遞增1,循環(huán)體包含了步驟3至步驟8?！?52●.步驟3令k=0,開始迭代次數(shù)為Nw的復(fù)制循環(huán),在循環(huán)的每次迭代中,先讓k遞增1,健康度都初始化為0,循環(huán)體10()=- 20Xxep[- -.2√5xx1]-xp[言x器包含了步驟4至步驟7。cos(2x)]+20+e步驟4令j=0,開始迭代次數(shù)為N.的趨化循環(huán),在循- 32