朱永杰，李冰曉，萬睿之，趙新超*，左興權(quán)

(1.北京郵電大學 理學院，北京 100876；2.北京郵電大學 計算機學院，北京 100876)

細菌覓食優(yōu)化算法(Bacterial Foraging Optimization,BFO)是由Passion提出[1]，是一種簡單有效的隨機全局優(yōu)化算法，不但有良好的局部搜索能力，算法中的遷徙操作還可以避免算法陷入局部最優(yōu).該算法因群體并行性及易跳出局部最優(yōu)等優(yōu)點，已經(jīng)成為群體智能研究領(lǐng)域的一個重要分支.BFO近幾年在算法設計、理論分析與應用研究方面取得長足發(fā)展.2009年Shao和Chen[2]通過協(xié)作方法提出了一個BFO算法變種，即合作細菌覓食優(yōu)化(CBFO)算法;Chen等[3]提出了自適應細菌覓食優(yōu)化算法，采用自適應搜索策略顯著提高了原算法的性能；劉小龍等[4]通過引入分布估計思想以及對細菌賦予自適應遷徙概率，提出了一種基于高斯分布估計的細菌覓食優(yōu)化算法；Jarraya等[5]提出了一種簡單的方案來適應細菌覓食優(yōu)化算法的趨化步長，然后將新的適應方法與粒子群優(yōu)化和差分進化結(jié)合構(gòu)成在一種新的混合方法，采用差分進化策略進行自適應趨化細菌群覓食優(yōu)化；Dasgupta等[6]從經(jīng)典梯度下降搜索的角度提出了對BFOA趨化步驟的理論分析，并且為了加快接近全局最優(yōu)解的細菌群的收斂速度，提出了兩種簡單方案調(diào)整趨化步長；Wang等[7]采用近似局部最優(yōu)和自適應突襲的漸進式開發(fā)策略，提出了一種新的BFO算法變種；楊大煉等[8]通過改進細菌種群大小、細菌運動步長、引進迭代終止條件改進原有細菌覓食算法，然后將其應用到支持向量機的參數(shù)優(yōu)化問題；劉小龍等人[9]通過賦予細菌靈敏度的概念，對細菌游動的步長進行調(diào)節(jié)以提高收斂速度，采用免疫算法中的克隆選擇思想，對精英細菌群體進行克隆、高頻變異和隨機交叉，引導算法提高搜索精度；李珺等[10]根據(jù)菌群的進化代數(shù)提出改變遷徙操作的作用范圍，避免逃逸發(fā)生，提出在復制操作中，按照細菌個體當前適應度值的優(yōu)劣進行復制，更準確地實現(xiàn)了細菌個體的優(yōu)勝劣汰，進一步提高收斂速度；Kim等[11]提出了一種混合遺傳算法和細菌覓食算法的函數(shù)優(yōu)化方法；Datta 等[12]根據(jù)自適應增量調(diào)制原理提出了自適應趨化步長的 BFO 算法；Tang等[13]通過在細菌覓食優(yōu)化算法中引入PSO算法基本思想，提出了快速細菌群算法;Dasgupta等[14]將差分進化算法的交叉與變異操作引入BFO算法，提出一種混合型全局優(yōu)化算法.細菌覓食算法也廣泛應用于多目標優(yōu)化領(lǐng)域.Guzman等[15]提出一種基于大腸桿菌趨藥性過程的多目標優(yōu)化算法，該算法利用快速非支配排序過程、群體成員之間的通信和簡單的趨化策略來改變細菌的位置，以探索搜索空間來尋找多個最優(yōu)解；Niu等[16-18]先后提出將細菌覓食算法應用于多目標優(yōu)化問題中.

本文第1節(jié)介紹標準細菌覓食優(yōu)化算法；第2節(jié)簡單介紹骨干粒子群算法；第3節(jié)詳細介紹提出的新算法的結(jié)構(gòu)框架和簡要分析；第4節(jié)在CEC2014測試函數(shù)集上，對提出的基于骨干思想的自適應細菌覓食優(yōu)化(BBBFO)算法與標準細菌覓食優(yōu)化(BFO)算法和文獻[19]中具有協(xié)同差分進化的細菌覓食優(yōu)化算法(PDBFO)進行仿真對比試驗；第5節(jié)給出結(jié)論和進一步的可能問題.

1 標準細菌覓食優(yōu)化算法

細菌覓食優(yōu)化(BFO)算法是一種基于種群的隨機搜索算法.該算法主要模擬人體腸道中大腸桿菌搜索食物的過程，主要包括三個運動行為：趨化、繁殖和遷徙行為.BFO算法對以上生物行為仿真建模，解決復雜非線性優(yōu)化問題.

趨化性操作：趨化主要包括兩個行為，翻轉(zhuǎn)和游動.細菌向任意方向移動單位步長為翻轉(zhuǎn)；細菌沿著上一步的運動方向移動單位步長為游動.細菌在營養(yǎng)物質(zhì)豐富的環(huán)境中聚集或在有毒物質(zhì)的環(huán)境中逃避的過程中，首先向任意方向移動單位步長到達新位置，如果到達的新位置適應值不如上一次位置的適應值，那么細菌就沿任意方向翻轉(zhuǎn)；否則，就沿相同方向持續(xù)移動，直至適應值不再改善或達到最大游動次數(shù).新位置的更新公式如下：

θi(j+1，k，l)=θi(j，k，l)+C(i)φ(j)

(1)

(2)

其中θi(j，k，l)為第i個細菌在第j次趨化，第k次復制，第l次遷徙時的位置，C(i)為游動的步長，φ(j)為翻轉(zhuǎn)后隨機選擇的單位方向向量，△(i)為翻轉(zhuǎn)時方向調(diào)整后選定的方向向量，向量中的元素在區(qū)間[0,1].

復制性操作：趨化操作完成后，通過模擬細菌運動行為中的繁殖現(xiàn)象，提出了復制操作，對每個細菌在生命周期內(nèi)的適應度值進行累加獲得細菌能量.細菌能量公式如下：

(3)

其中Jihealth表示第i個細菌的能量，Nc表示趨化次數(shù).細菌適應度值越大，能量越大，表示細菌越健康，覓食能力越強.所以將細菌能量按從小到大的順序，淘汰掉前一半能量小的細菌，保留后一半能量大的細菌，并且復制后一半細菌，生成與后一半細菌完全相同的子代細菌.

遷徙性操作：復制操作完成后，對種群中細菌i，給定概率Ped，生成一個區(qū)間為(0，1)的隨機數(shù)r，如果滿足r

2 骨干粒子群算法

粒子群算法PSO是一種基于種群搜索的智能算法[20]，是通過模仿鳥群覓食的行為而產(chǎn)生的一種仿生算法.PSO算法中每一個個體稱為一個粒子，代表一個潛在解，每個粒子通過追蹤當前種群中的全局最優(yōu)解GBest和個體最優(yōu)解PBest來產(chǎn)生新的粒子，從而實現(xiàn)搜尋問題的最優(yōu)解.設群體規(guī)模為N，粒子維數(shù)為m.第t代粒子i的位置為Xi(t)=(xi1(t)，xi2(t)，…，xij(t)，…，xim(t))，i=1，2，…，N，速度為Vi(t)=(vi1(t)，vi2(t)，…，vij(t)，…，vim(t))，粒子迄今搜索到的個體歷史最優(yōu)值為PBesti(t)=(Pbesti1(t)，Pbesti2(t)，…，Pbestij(t)，…，Pbestim(t))，全局最優(yōu)為GBesti(t)=(gbest1(t)，gbest2(t)，…，gbestj(t)，…，gbestm(t)).于是，粒子按式(4)、(5)更新位置和速度：

vij(t+1)=wvij(t)+c1r1j(pbestij(t)-xij(t))+c2r2j(gbestj(t)-xij(t))

(4)

xij(t+1)=xij(t)+vij(t+1)

(5)

其中，w為慣性權(quán)重，c1和c2為加速算子，r1j和r2j是在[0,1]上均勻分布的隨機數(shù).

Kennedy等人[21]在2003年提出了骨干粒子群(BBPSO)算法，將PSO的速度和位置更新公式改進為一個無參數(shù)公式：

(6)

粒子的位置隨機地以pbestij(t)和gbestj(t)的平均值為均值，以兩者的歐氏距離為標準差進行高斯變異.在優(yōu)化初期，粒子散布于解空間中，標準差較大，算法傾向于全局搜索，優(yōu)化后期，標準差逐漸減小，算法傾向于局部搜索.并且每個新解產(chǎn)生的中心和方差依賴于自己的歷史最優(yōu)位置，從而新解產(chǎn)生具有動態(tài)自適應調(diào)整的優(yōu)勢.

3 基于骨干思想的自適應細菌覓食優(yōu)化算法

3.1 自適應步長

用細菌覓食算法求解最優(yōu)化問題時，每個細菌采用固定步長進行游動，若固定步長較大，則可能導致后期細菌跳離最優(yōu)解所在鄰域，出現(xiàn)收斂速度慢、精度低的問題；若固定步長較小，結(jié)果精度較高，但收斂速度太慢，易陷入局部極值而難以跳出.因此，算法搜索過程中需要選取合適的游動步長以保證其收斂速度、結(jié)果精度以及防止其陷入局部最優(yōu)鄰域無法跳出.因此本文設置細菌第m次游動的步長如式(7)所示：

(7)

其中Ns為細菌游動的最大次數(shù)，Xmax和Xmin分別是變量的上下邊界，λ是根據(jù)問題的搜索區(qū)域進行設置.該適應性動態(tài)調(diào)整的步長公式在算法初期取值相對較大，從而具有勘探整個搜索空間的可能性；隨著算法進行，步長逐漸適應性減小，從而對先前發(fā)現(xiàn)的優(yōu)秀鄰域進行小范圍開發(fā)，具有較快的新解生成收斂速度.

3.2 基于骨干思想的BFO

由于基本BFO的復制操作使得種群多樣性大大降低，受骨干粒子群算法的啟發(fā)，將骨干思想融入復制操作.具體操作描述如下：將細菌能量Jhealth按從大到小的順序排列X1，…，XS，淘汰掉后S/2個能量值較小的細菌，后Sr個細菌新位置是以前S/2個細菌的重心為均值μ，以X1與XS/2的歐氏距離為標準差δ，通過高斯采樣逐個得到.后S/2個細菌新位置更新公式如下:

(8)

(9)

(10)

該組細菌新位置的公式有如下優(yōu)點，一是較為充分的利用了群體優(yōu)質(zhì)解的信息，從而產(chǎn)生優(yōu)質(zhì)數(shù)據(jù)驅(qū)動的進化動力；二是利用半種群優(yōu)質(zhì)解作為新解產(chǎn)生中心而不是利用單個最優(yōu)解，避免了有可能的局部陷阱的吸引；三是新位置產(chǎn)生的高斯公式的標準差的動態(tài)調(diào)整契合了算法前期大范圍勘探、后期小范圍搜索的一般規(guī)律.

3.3 算法流程

本文沿用經(jīng)典的細菌覓食優(yōu)化算法模型，基于骨干思想的自適應調(diào)整機制嵌入標準的細菌覓食算法趨化操作和復制操作中，新算法的主要實現(xiàn)步驟描述如下.

Step1 參數(shù)初始化.細菌規(guī)模數(shù)S，趨化次數(shù)Nc，復制次數(shù)Nre，遷徙次數(shù)Ned，游動次數(shù)Ns，遷移概率Ped.

Step2 初始化細菌位置.采用公式X=Xmin+rand·(Xmax-Xmin)產(chǎn)生初始化位置，計算細菌的初始化適應值J.

Step3 遷移循環(huán)l=1:Ned；復制循環(huán)k=1:Nre；趨化循環(huán)j=1:Nc.

Step4 執(zhí)行細菌趨化循環(huán)

(1)翻轉(zhuǎn)：按照公式(1)、(2)更新細菌位置.

(2)游動：如果翻轉(zhuǎn)的適應值得到改善，則細菌按照翻轉(zhuǎn)的方向以公式(7)作為游動步長繼續(xù)向前游動，直至適應值不再改善或者達到設定的最大游動次數(shù)Ns.

Step5 繁殖循環(huán).趨化周期完成后，按照公式(3)對每個細菌在生命周期內(nèi)的適應值進行累加得到細菌能量，按照細菌能量排序，淘汰掉能量小的半數(shù)細菌，對能量大的半數(shù)細菌按照公式(8)進行高斯變異，替換淘汰掉的半數(shù)細菌，保持細菌總數(shù)不變.

Step6 遷徙循環(huán).繁殖算子完成后，生成一個隨機概率，并將它與固定的遷徙概率Ped進行比較，如果小于Ped細菌進行遷徙，在解空間的定義域內(nèi)隨機初始化.

Step7 循環(huán)結(jié)束條件判斷，滿足則結(jié)束，輸出結(jié)果.

4 仿真實驗與結(jié)果分析

為了驗證本文提出的基于骨干思想的自適應細菌覓食算法(BBBFO)的性能，選取測試函數(shù)采取CEC2014測試函數(shù)集[22]將BBBFO與標準的BFO和PDBFO進行對比分析.

4.1 測試函數(shù)與參數(shù)設置

在CEC2014測試函數(shù)集[22]的各類函數(shù)中選出代表性算例構(gòu)成本文的基準測試函數(shù)集，所有測試函數(shù)均為高維可伸縮的函數(shù).選取 CEC2014 函數(shù)簡介如下，f2，f3為單峰函數(shù)，f5，f6，f10，f11，f15為多峰函數(shù)，f20，f21，f22為混合函數(shù)，為了方便起見，將這些函數(shù)重新標記為F1～F10.這些測試函數(shù)詳細信息見文獻[22].

算法對比實驗的具體參數(shù)設置如下：細菌規(guī)模數(shù)S=40，搜索空間維度D=30，趨化次數(shù)Nc=40，復制次數(shù)Nre=4，遷徙次數(shù)Ned=6，游動次數(shù)Ns=4，遷徙概率Ped=0.3，最大評估次數(shù)FES=900000.對比算法的參數(shù)設置均參照文獻[19].

4.2 實驗數(shù)據(jù)對比

算法BFO、PDBFO、BBBFO的數(shù)值統(tǒng)計結(jié)果見表1，該統(tǒng)計結(jié)果包括30次獨立運行最終結(jié)果的最優(yōu)值Min、平均值Mean、標準差Std，三個指標中最優(yōu)結(jié)果用黑體表示.

表1 3種算法數(shù)值實驗結(jié)果統(tǒng)計

從表1直觀來看，(1)在10個測試函數(shù)中BFO、PDBFO和BBBFO在30次最終結(jié)果統(tǒng)計的最優(yōu)值上分別有1個、2個和7個最優(yōu)結(jié)果；(2)BFO、PDBFO、BBBFO在10個測試函數(shù)上最終結(jié)果統(tǒng)計在平均值上分別有0個、0個、10個最優(yōu)結(jié)果；(3)BFO、PDBFO、BBBFO在10個測試函數(shù)上最終結(jié)果統(tǒng)計在標準差上分別有4個、0個、6個最優(yōu)結(jié)果.

因此綜合表1結(jié)果和相應分析可以看出，在CEC2014的測試函數(shù)上BBBFO得到的3個指標結(jié)果均有明顯的優(yōu)勢，最優(yōu)值和平均值統(tǒng)計結(jié)果也比BFO和PDBFO表現(xiàn)的更好.

4.3 收斂速度對比分析

為了考察新算法的收斂速度和綜合在線性能，圖1給出了3種算法經(jīng)過30次運行得出每一次迭代的平均適應值對應的收斂曲線圖，其中橫坐標是函數(shù)值計算次數(shù)，縱坐標是30次獨立運行中每一個進化代的平均適應值.選取代表性收斂圖，單峰函數(shù)F1、F2，多峰函數(shù)F3、F4、F5、F7，混合函數(shù)F8、F9.

圖1 3種算法收斂曲線圖

對比3個算法在求解CEC2014測試函數(shù)的收斂性能，(1)BBBFO收斂速度明顯優(yōu)于BFO和PDBFO；(2)對于多峰函數(shù)，BBBFO在F3、F4上的收斂速度和精度遠優(yōu)于其他兩種算法，在F5、F7略優(yōu)于其他算法，可以分析出當求解多峰函數(shù)時BBBFO的性能比其他算法優(yōu)勢較明顯；(3)在求解單峰函數(shù)時，BBBFO收斂優(yōu)勢不太顯著，但后期放大來看BBBFO仍然優(yōu)于其他算法；(4)在求解混合函數(shù)時，BBBFO算法也具有較為明顯的競爭優(yōu)勢.總之，在這些復雜函數(shù)優(yōu)化上的綜合性能表現(xiàn)，本文提出的BBBFO算法表現(xiàn)出優(yōu)異的優(yōu)化性能和潛力.

4.4 最終結(jié)果離散度對比

為進一步考查3種算法在多次運行最終結(jié)果中的離散程度，圖2給出了3種算法經(jīng)過30次運行得出最優(yōu)結(jié)果的箱型圖，箱型圖中橫坐標為3個算法，縱坐標為函數(shù)適應值，其中5條線從上到下分別為：最大值、上四分位數(shù)、中位數(shù)、 下四分位數(shù)和最小值，同樣選擇函數(shù)F1、F2、F3、F4、F5、F7、F8、F9為代表.

圖2 3種算法最終結(jié)果箱型圖

從圖2來看，(1)在中位數(shù)上，BFO、PDBFO和BBBFO分別取得0個、1個、7個最優(yōu)結(jié)果；(2)從上下四分位距上來看，BFO、PDBFO和BBBFO分別取得4個、1個、3個；(3)對于多峰函數(shù)和混合函數(shù)，BBBFO在F3、F4、F5、F7、F8和F9上的中位數(shù)與其他算法的中位數(shù)值相差較大，可以看出在求解多峰函數(shù)和混合函數(shù)時BBBFO的性能顯著優(yōu)于其他兩種算法.

綜合可以看出，本文提出的算法BBBFO中位數(shù)結(jié)果最優(yōu)，因此新算法具有較好的性能表現(xiàn)，且具有較好的穩(wěn)定性和魯棒性，特別針對多峰函數(shù)和混合函數(shù)的復雜優(yōu)化問題上具有較為明顯的優(yōu)勢.

5 結(jié) 論

本文受骨干算法的啟發(fā)，充分利用算法中骨干思想的優(yōu)質(zhì)解鄰域隨機生成新解的策略，在繁殖操作中引入基于動態(tài)高斯變異的骨干操作，在保持精英鄰域搜索的基礎(chǔ)上增加了種群多樣性，提高了求解精度.另外趨化操作是細菌覓食算法的核心操作，其中游動步長是趨化操作中具有重要影響的一個，將固定的游動步長通過自適應改進，使得算法在前期搜索范圍廣、后期逐漸縮小搜索范圍，這樣使得算法在求解問題時的不同階段對全局和局部搜索有所偏重，總體保持平衡.選用CEC2014基準測試函數(shù)，對本文提出的基于骨干思想的自適應細菌覓食優(yōu)化算法與同類算法進行對比仿真實驗，結(jié)果表明本文提出的算法總體性能更好，具有更好的收斂速度和精度，并且具有良好的穩(wěn)定性和魯棒性.

對于細菌覓食優(yōu)化算法的研究還有許多問題，我們可以嘗試將貪婪替換或競技搜索引入算法中，還可以將本文的新思想與其他智能算法相結(jié)合.