群體智能優(yōu)化算法-細菌覓食算法

第十四章細菌覓食優(yōu)化算法14.1介紹Passino等人⑴于2002年通過模擬人體內(nèi)大腸桿菌的覓食行為，提出了一種新型智能優(yōu)化算法：細菌覓食優(yōu)化算法(BacterialForagingOptimizationAlgorithm，BFOA)。細菌覓食優(yōu)化算法通過細菌群體之間的競爭與協(xié)作實現(xiàn)優(yōu)化，是一種基于細菌群體的搜索技術(shù)。在群智能算法中，GA、ACO、PSO、AFSA都是基于高等生物作為啟發(fā)對象，而BFOA算法則是模擬微生物的行為而形成的一種較新的優(yōu)化方法。14.2BFOA的基本原理與流程BFOA算法是一種全局隨機搜索的算法，其具有簡單、收斂速度快，并且在優(yōu)化過程中無需優(yōu)化對象的梯度信息的特點。BFOA模擬細菌群體的過程包括趨向性(Chemotaxis)、復(fù)制(Reproduction)、遷徙(Elimination-dispersal)三個步驟。14.2.1趨向性操作細菌向有利于自身環(huán)境的區(qū)域移動稱為趨向運動，其中，一次趨向性操作包括翻轉(zhuǎn)運動和游動運動。細菌向任意方向移動單位步長稱為旋轉(zhuǎn)運動；細菌沿著上一步的運動放向移動單位步長稱為游動運動。通常，細菌在環(huán)境差的區(qū)域(如：有毒區(qū)域)會較頻繁地旋轉(zhuǎn)，在環(huán)境好的區(qū)域(如：食物豐富的區(qū)域)會較多地游動。大腸桿菌的整個生命周期就是在游動和旋轉(zhuǎn)這兩種基本運動之間進行變換，游動和旋轉(zhuǎn)的目的是尋找食物并避開有毒物質(zhì)。設(shè)細菌種群大小為S,細菌所在的位置標(biāo)示問題的一個候選解，細菌i的信息用D維向量標(biāo)示為9i=r9i,9i,L,ei],i=l,2,...,S,鮒,k,l)表示細菌i在第j次趨向性操作、第12Dk次復(fù)制操作和第l次遷徙操作后的位置。細菌i通過式(1)更新其每一步趨向性操作后的位置。1)9i(j+1,k,l)=9i(j,k,l)+C(i)①(j1)其中C(i)>0表示向前游動的步長，①j)表示旋轉(zhuǎn)后隨機選擇的單位方向向量。如果在0(j+1,k,l)處的適應(yīng)度優(yōu)于Hj+l,k,l)處，則保持①不變繼續(xù)在該方向游動，直至找到適應(yīng)度最佳的位置或達到設(shè)定的趨向性次數(shù)；否則產(chǎn)生新的①，進行下一次旋轉(zhuǎn)運動。設(shè)Ns是趨向性操作中在一個方向上前進的最大步數(shù)(用m進行索引)，初始時該值為0，BFOA趨向性操作的流程圖如圖1所示。開始

圖1趨向性操作流程圖目前的討論主要是針對不考慮細菌間相互吸引的情況，實際上每個細菌個體除按照自己的方式搜索食物外，還收到種群中其他個體發(fā)出的吸引力信號，即個體會游向種群中心。第ih個細菌的細菌間吸引力用Ji i(j,k,l)),i=1,2,S表示，dttt=0.1表示細thccattract菌釋放的吸引量多少(深度)，wttt=0.2用于度量吸引信號的寬度(量化化學(xué)物質(zhì)的擴attract散率)。同時也會收到附近個體發(fā)出的排斥力信號，以保持個體與個體之間的安全距離，因為細菌消耗附近的營養(yǎng)物質(zhì)，在物理上不可能在同一位置有兩個細菌，對此，令hllt=dttt表示排斥力的高度(排斥影響程度)，wllt=10度量了排斥力的寬度。repellantattract repellant令Jcc(3,P(j,k,l))表示同時考慮了細菌間吸引力和排斥力的綜合影響，其計算公式如2)。J(0,P(j,k,l))=^JLJ(0,P(j,k,l))=^JL(e,oi(j,k,l))ccc￡i=1=YS-dattactexp-w2)i=1attract mmm=1i=1hrepelantexp一w Y(0-0i)i=1hrepelantIrepellinatm=1其中P(j,k,l)表示在第j次趨向性操作、第k次復(fù)制操作和第l次遷徙操作后，種群S中每個細菌的位置，6=[0],...,0°卩是優(yōu)化域上的一個點，Oim是第i個細菌位置&的第m個元素。3)P(j,k,l)=《i(j,k,l)1i=1,2,S}3)因此考慮上述兩個因素對細菌行為的影響，執(zhí)行一次趨向性操作后細菌i的新適應(yīng)度函數(shù)值為：J(i,j+1,k,l)=J(i,j,k,l)+J(0i(j+1,k,l),P(j+1,k,l)) (4)cc這樣這些細胞會試圖尋找營養(yǎng)物質(zhì)，避免有毒物質(zhì)，同時試圖向其他細胞移動，但又不會靠得太近。14.2.2復(fù)制操作生物進化過程的規(guī)律是優(yōu)勝劣汰。經(jīng)過一段時間的食物搜索過程后，部分尋找食物能力弱的細菌會被自然淘汰掉，為了維持種群規(guī)模，剩余的細菌會進行繁殖。在細菌覓食優(yōu)化算法中將這種現(xiàn)象稱為復(fù)制行為(Reproduction)。在BFOA中，經(jīng)過復(fù)制操作后算法的種群大小不變。設(shè)淘汰掉的細菌個數(shù)為S=S/2,首先按照細菌位置的優(yōu)劣排序，然后把排在后面的sr個細菌淘汰掉，剩余的sr個細菌進行自我復(fù)制，各自生成一個與自己完全相同的新個體，即生成的新個體與原個體有相同的位置，或者說具有相同的覓食能力。初始時設(shè)i=0,復(fù)制操作流程圖如圖2所示。開始結(jié)束圖2復(fù)制操作流程圖14.2.3遷徙操作細菌個體生活的局部區(qū)域可能會突然發(fā)生變化(如：溫度的突然升高)或者逐漸變化(如：食物的消耗)，這樣可能會導(dǎo)致生活在這個局部區(qū)域的細菌種群集體死亡，或者集體遷徙到一個新的局部區(qū)域。在細菌覓食優(yōu)化算法中將這種現(xiàn)象稱為遷徙行為(Elimination-dispersal)。遷徙操作以一定概率發(fā)生，給定概率Ped如果種群中的某個細菌個體滿足遷徙發(fā)生的概率，則這個細菌個體滅亡，并隨機地在解空間的任意位置生成一個新個體，這個新個體與滅亡的個體可能具有不同的位置，即不同的覓食能力。遷徙操作隨機生成的這個新個體可能更靠近全局最優(yōu)解，這樣更有利于趨向性操作跳出局部最優(yōu)解和尋找全局最優(yōu)解。初始時設(shè)i=0，rand()是［0,1］區(qū)間上均勻分布的隨機數(shù)，遷徙操作流程如圖3所示。圖3遷徙操作流程圖14.3BOFA算法初始化：確定參數(shù)D,S,Nc,Ns,Nre,Ned,ped和C(i),i=l,2,...,S,如果利用了細菌的群聚性，則還需要選擇細菌間吸引函數(shù)。此外還要對夕進行初始化，j、k和l初始時均為0。注意，對夕進行更新會自動更新P。遷徙操作循環(huán)loop：l=l+1賦值循環(huán)loop：k=k+l趨向循環(huán)loop：j=j+1fori=1,2,...,S,對細菌i按如下步驟進行趨向性操作。計算J(ijk,l)。令J(ij,k,l)=J(ij,k,l)+Jcc(Hj,k,l),Pj,k,l))。令J[ast=J(ij,k,l)，將該值保存，用于比較適應(yīng)度值。旋轉(zhuǎn)：生產(chǎn)一個隨機向量A(i)GRD，其每個元素Am(i)(m=1,2,...,D)為[-1,1]上的隨機數(shù)。移動：執(zhí)行式(1)從而使得細菌i在旋轉(zhuǎn)方向上移動了C(i)步長。計算J(ij+1,k,l)。令J(ij+1,k,l)=J(ij+1,k,l)+Jcc(Hj+1,k,l),Pj+1,k,l))。游動。令m=0。Whilem<Ns?令m=m+1.?ifJ(ij+1,k,l)vJlast(對于最小化問題)，令Jlast=J(ij+1,k,l),再執(zhí)行式(1),使用H(j+1,k,l)計算新的J(ij+1,k,l)。?Else，令m=N，結(jié)束While循環(huán)s如果i#S轉(zhuǎn)到第(i+1)個細菌，即b)步。ifjvNc，跳轉(zhuǎn)至3),繼續(xù)執(zhí)行趨向性操作。復(fù)制：a） 給定k和l,對于每個i=l,2,...,S，令Ji =営1J（i,j,k,l） （5）healthj=1表示細菌i的健康度（度量其整個生命周期內(nèi)獲得了多少營養(yǎng)以及在避免有毒物質(zhì)方面有多成功），按Jheaith的升序?qū)毦挖呄蛐詤?shù)C（i）進行排序。b） 淘汰Sr個具有最大Jheakh的細菌，其余的Sr個具有最優(yōu)值的細菌進行分裂（新的副本具有和父代相同的位置）。6） ifk<Nre，跳轉(zhuǎn)到2）。7） 遷徙：Fori=1,2,...,S，以概率ped，對每個細菌進行消除或分散，如果某細菌個體滅亡，并隨機地在解空間的任意位置生成一個新個體。8） ifl<Ned，跳轉(zhuǎn)到1），否則終止。參考文獻1.Passino,K.M.,Biomimicryofbacterialforagingfordistributedoptimizationandcontrol.IEEEControlSystemsMagazine,2002.22(3):p.52-67.初始化：確定參數(shù)D,S,Nc,Ns,Nre,Ned,ped和C(i),i=l,2”..,S,如果利用了細菌的群聚性，則還需要選擇細菌間吸引函數(shù)。此外還要對少進行初始化，j、k和l初始時均為0。注意，對侏進行更新會自動更新P。遷徙操作循環(huán)loop：l=l+l賦值循環(huán)loop：k=k+l趨向循環(huán)loop：j=j+1fori=1,2”..,S,對細菌i按如下步驟進行趨向性操作。計算J(ij,k,l)。令J(ij,k,l)=J(ij,k,l)+J“(Mj,k,l),Pj,k,l))。令Jlast=J(ij,k,l),將該值保存，用于比較適應(yīng)度值。旋轉(zhuǎn)：生產(chǎn)一個隨機向量△(i)WRD，其每個元素Am(i)(m=1,2,...,D)為[-1,1]上的隨機數(shù)。移動：執(zhí)行式(1)從而使得細菌i在旋轉(zhuǎn)方向上移動了C(i)步長。計算J(i,j+1,k,l)。令J(i,j+1,k,l)=J(ij+1,k,l)+Jcc(M(y+1,k,l),Pj+1,k,l))。游動。令m=0。Whilem<Ns?令m=m+1.?ifJ(i,