廣義菌群優(yōu)化算法

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