一種自適應(yīng)骨干細(xì)菌覓食優(yōu)化算法

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

(1.北京郵電大學(xué) 理學(xué)院，北京 100876；2.北京郵電大學(xué) 計(jì)算機(jī)學(xué)院，北京 100876)

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

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

1 標(biāo)準(zhǔn)細(xì)菌覓食優(yōu)化算法

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

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

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

(1)

(2)

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

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

(3)

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

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

2 骨干粒子群算法

粒子群算法PSO是一種基于種群搜索的智能算法[20]，是通過模仿鳥群覓食的行為而產(chǎn)生的一種仿生算法.PSO算法中每一個(gè)個(gè)體稱為一個(gè)粒子，代表一個(gè)潛在解，每個(gè)粒子通過追蹤當(dāng)前種群中的全局最優(yōu)解GBest和個(gè)體最優(yōu)解PBest來(lái)產(chǎn)生新的粒子，從而實(shí)現(xiàn)搜尋問題的最優(yōu)解.設(shè)群體規(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))，粒子迄今搜索到的個(gè)體歷史最優(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]上均勻分布的隨機(jī)數(shù).

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

(6)

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

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

3.1 自適應(yīng)步長(zhǎng)

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

(7)

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

3.2 基于骨干思想的BFO

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

(8)

(9)

(10)

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

3.3 算法流程

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文提出的基于骨干思想的自適應(yīng)細(xì)菌覓食算法(BBBFO)的性能，選取測(cè)試函數(shù)采取CEC2014測(cè)試函數(shù)集[22]將BBBFO與標(biāo)準(zhǔn)的BFO和PDBFO進(jìn)行對(duì)比分析.

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

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

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

4.2 實(shí)驗(yàn)數(shù)據(jù)對(duì)比

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

表1 3種算法數(shù)值實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

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

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

4.3 收斂速度對(duì)比分析

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

圖1 3種算法收斂曲線圖

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

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

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

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

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

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

5 結(jié) 論

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

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