基于細(xì)菌覓食的函數(shù)優(yōu)化算法

孫夏麗，李士心，王 坤，劉清清

（天津職業(yè)技術(shù)師范大學(xué)電子工程學(xué)院，天津300222）

2002年，Passino[1]根據(jù)大腸桿菌覓食規(guī)律，提出了一種智能隨機(jī)搜索算法——細(xì)菌覓食優(yōu)化算法（bacterial foraging algorithm，BFO）。該算法主要由趨向操作、復(fù)制操作和遷徙操作3個(gè)步驟組成，具有魯棒性強(qiáng)、易搜索的優(yōu)點(diǎn)，但趨向性操作的固定步長(zhǎng)使算法在后期易陷入局部最優(yōu)解而產(chǎn)生早熟問(wèn)題；復(fù)制操作采用精英策略，保留個(gè)體前50%，后50%通過(guò)復(fù)制精英個(gè)體得到，種群的多樣性受限。為了提高BFO算法的性能，近年來(lái)，相關(guān)學(xué)者針對(duì)此算法做了大量研究。針對(duì)趨向操作中的游動(dòng)步長(zhǎng)，姜建國(guó)等[2]采用非線性遞減的自適應(yīng)游動(dòng)步長(zhǎng)改善算法的局部搜索能力；王新剛等[3]對(duì)趨化操作的步長(zhǎng)和方向進(jìn)行改進(jìn)；杜鵬楨等[4]提出混合蜂群算法的自適應(yīng)細(xì)菌覓食算法，其設(shè)計(jì)了一種新的雇傭蜂趨化方式，將固定步長(zhǎng)改為自適應(yīng)步長(zhǎng)，提高全局搜索能力；曹天問(wèn)等[5]提出在復(fù)制操作中對(duì)剩下的50%個(gè)體采用Levy飛行進(jìn)行位置更新，增強(qiáng)算法隨機(jī)搜索能力，提升收斂速度；陳東寧等[6]用粒子群優(yōu)化算法（particle swarm optimization algorithm，PSO）中粒子速度的更新公式替代BFO算法中的方向向量，使細(xì)菌具有尋優(yōu)能力；董海等[7-8]采用高斯分布更新細(xì)菌個(gè)體位置，利用情緒智能突變改變步長(zhǎng)，且對(duì)遷徙操作中的固定概率采用線性和非線性的概率分布進(jìn)行改進(jìn)，改進(jìn)后的算法收斂性得到提高，后又提出基于激素調(diào)節(jié)機(jī)制的情緒化細(xì)菌覓食算法，利用激素控制細(xì)菌個(gè)體情緒，通過(guò)情緒感知因子判斷細(xì)菌個(gè)體情緒狀態(tài)，更新運(yùn)行速率；王鈺婷等[9]在趨向和復(fù)制操作中使用差分策略來(lái)更新細(xì)菌位置，保持種群多樣性；李偉等[10]融合蟻群算法的正反饋機(jī)制與細(xì)菌覓食的復(fù)制操作和趨向操作來(lái)求解無(wú)線Mesh網(wǎng)絡(luò)（wireless mesh networks，WMN）中多約束QoS路由模型，收斂性和穩(wěn)定性得到了提高。本文針對(duì)細(xì)菌覓食優(yōu)化算法易陷入局部最優(yōu)和全局搜索能力差問(wèn)題，在趨向操作中的游動(dòng)步長(zhǎng)C上采用非線性正弦學(xué)習(xí)因子，并融合正余弦思想來(lái)更新細(xì)菌個(gè)體的位置，以保證種群的多樣性，減少早熟問(wèn)題的發(fā)生。

1 標(biāo)準(zhǔn)的細(xì)菌覓食算法

細(xì)菌覓食算法是一種基于大腸桿菌的覓食行為而提出來(lái)的智能隨機(jī)搜索算法，主要包括趨向性、復(fù)制性和遷徙3個(gè)步驟。

1.1 趨向性操作

大腸桿菌的覓食過(guò)程主要由旋轉(zhuǎn)和游動(dòng)2個(gè)過(guò)程組成。旋轉(zhuǎn)是改變覓食的方向，游動(dòng)是覓食保持原方向的運(yùn)動(dòng)，但其處于算法的內(nèi)層，執(zhí)行次數(shù)多，加強(qiáng)了算法的局部搜索能力，易使算法陷入局部最優(yōu)值。每次趨向操作后細(xì)菌位置更新為

式中：P（i，j，k，l）為細(xì)菌i在第j次趨向、第k次復(fù)制、第l次遷徙操作后的位置；C（i）為細(xì)菌的趨化步長(zhǎng)；Δ為單位隨機(jī)方向向量。

1.2 復(fù)制操作

復(fù)制操作即為“優(yōu)勝劣汰”的過(guò)程，細(xì)菌在覓食中，對(duì)于覓食能力弱的個(gè)體會(huì)淘汰，為了保持種群總數(shù)不變，故需要覓食能力強(qiáng)的個(gè)體進(jìn)行分裂，這一過(guò)程為復(fù)制操作。

若細(xì)菌總數(shù)為S，先按照個(gè)體目標(biāo)適應(yīng)度值從小到大進(jìn)行排序，排在前50%的個(gè)體保留，后50%的個(gè)體由前50%的個(gè)體復(fù)制得到。

1.3 遷徙操作

若細(xì)菌生存的環(huán)境發(fā)生突變，為保存實(shí)力，細(xì)菌被迫轉(zhuǎn)移，這一過(guò)程為細(xì)菌遷徙。遷徙按照給定的概率進(jìn)行，在[0，1]內(nèi)隨機(jī)產(chǎn)生一隨機(jī)數(shù)，若此概率大于產(chǎn)生的隨機(jī)數(shù)，在空間內(nèi)隨機(jī)生成一個(gè)新的個(gè)體代替原細(xì)菌個(gè)體。

2 改進(jìn)的細(xì)菌覓食算法

2.1 趨向性操作的改進(jìn)

游動(dòng)步長(zhǎng)C控制種群的收斂性和多樣性。步長(zhǎng)太大，可提高搜索效率，但易陷入局部最優(yōu)；步長(zhǎng)太小，效率低、易陷入早熟或不熟，但精度高。故融合正弦余弦算法[11]思想，并引入非線性正弦學(xué)習(xí)因子[12]，在搜索前期，步長(zhǎng)具有較大的值，有助于全局探索，在搜索后期，其具有較小的值，有助于提升局部開(kāi)拓能力，提高精度。游動(dòng)步長(zhǎng)C和改進(jìn)后的細(xì)菌i的位置公式為

式中：NC為趨化次數(shù)；Cmax與Cmin分別為游動(dòng)步長(zhǎng)C的最大值和最小值；r1為[0，2π]的隨機(jī)數(shù)；r2為[0，2]的隨機(jī)數(shù)；r3為[0，1]的隨機(jī)數(shù)。

2.2 復(fù)制操作的改進(jìn)

將趨化后的大腸桿菌個(gè)體的能量大小按照從大到小的順序進(jìn)行排序，將能量較大的前50%的細(xì)菌個(gè)體進(jìn)行復(fù)制，淘汰后50%的細(xì)菌個(gè)體，此過(guò)程可提高算法的收斂速度，但種群多樣性受限易陷入局部最優(yōu)值。本文保留能量值前50%的細(xì)菌，對(duì)后50%的細(xì)菌進(jìn)行t分布變異[13-14]，利用被選中細(xì)菌的信息擾動(dòng)，使得細(xì)菌跳出局部極值點(diǎn)的束縛并收斂于全局極值點(diǎn)，提高收斂速度。對(duì)后50%的細(xì)菌個(gè)體采用式（4）進(jìn)行位置更新

式中：t為迭代次數(shù)；xit為細(xì)菌i在t代的位置。

2.3 改進(jìn)的BFO算法流程

綜上所述，改進(jìn)后的細(xì)菌覓食算法流程如下：

①初始化參數(shù)。S為細(xì)菌種群數(shù)，NC、NS、Nre、Ned和Ped分別為趨向操作次數(shù)、趨化最大步長(zhǎng)、復(fù)制次數(shù)、遷徙次數(shù)和遷徙概率；最大和最小游動(dòng)步長(zhǎng)分別為Cmax和Cmin。②種群位置初始化。隨機(jī)初始化細(xì)菌位置。③設(shè)置循環(huán)變量。設(shè)置趨向循環(huán)、復(fù)制循環(huán)、遷徙循環(huán)變量。④趨向操作。按照式（2）計(jì)算游動(dòng)步長(zhǎng)，搜索前期有較大值，搜索后期有較小值；按照式（3）更新細(xì)菌的位置。⑤復(fù)制操作。按照式（4）更新排在能量后50%的細(xì)菌個(gè)體的位置。⑥遷徙操作。⑦判斷算法是否滿足收斂條件，若收斂，則輸出結(jié)果并結(jié)束；若不符合條件，則返回③繼續(xù)執(zhí)行，直到滿足條件。

3 仿真測(cè)試與結(jié)果分析

3.1 測(cè)試函數(shù)選取

為驗(yàn)證改進(jìn)后算法的性能，本文采用基準(zhǔn)測(cè)試函數(shù)對(duì)上述算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，測(cè)試函數(shù)如表1所示。

表1 基準(zhǔn)測(cè)試函數(shù)

Sphere函數(shù)為非線性對(duì)稱單峰函數(shù)；Rastrigrin函數(shù)為典型的具有大量局部最優(yōu)點(diǎn)的復(fù)雜可分離的多峰函數(shù)，是一種典型的非線性多模態(tài)函數(shù)；Griewank函數(shù)為不可分割的多峰函數(shù)，搜索范圍廣，局部極小值點(diǎn)多；Schaffer函數(shù)為二維復(fù)雜函數(shù)，具有強(qiáng)烈的震蕩性，很難找到全局最優(yōu)解，在（0，0）點(diǎn)處取到最優(yōu)值為0。

3.2 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

在Inter（R）Core（TM）i7-4700HQ CPU@2.40 GHz，內(nèi)存8.00 GB，Window 7系統(tǒng)和Matlab R2019b下對(duì)算法進(jìn)行仿真實(shí)驗(yàn)。

BFO算法參數(shù)較多，參數(shù)的選取對(duì)算法的性能影響較大，需要根據(jù)實(shí)際情況設(shè)定合適的控制參量，通過(guò)大量文獻(xiàn)和實(shí)驗(yàn)驗(yàn)證，本文取BFO算法中的細(xì)菌種群S=100，趨向次數(shù)Nc=50，游動(dòng)步數(shù)Ns=4，復(fù)制次數(shù)Nre=4，遷徙次數(shù)Ned=2，遷徙概率Ped=0.25，Cmax、Cmin為測(cè)試函數(shù)變量取值的最大值和最小值。

3.3 測(cè)試結(jié)果分析

比較標(biāo)準(zhǔn)BFO算法和改進(jìn)后的BFO算法，在4個(gè)測(cè)試函數(shù)[15]上均進(jìn)行20次獨(dú)立測(cè)試實(shí)驗(yàn)，評(píng)價(jià)標(biāo)準(zhǔn)包括測(cè)試實(shí)驗(yàn)中的最小值、最大值、平均值、平均運(yùn)行時(shí)間，測(cè)試結(jié)果如表2所示。

由表2可知，IBFO算法在各個(gè)測(cè)試函數(shù)上表現(xiàn)優(yōu)良，求解精度得到了提高，而且運(yùn)行速率加快。如在Rastrigrin函數(shù)的20次獨(dú)立試驗(yàn)中，IBFO算法搜尋到的最優(yōu)解比BFO精確8個(gè)數(shù)量級(jí)，最差解比BFO精確7個(gè)數(shù)量級(jí)，但I(xiàn)BFO算法運(yùn)行的時(shí)間只為BFO算法運(yùn)行時(shí)間的59.8%。在算法運(yùn)行時(shí)間上提升最為明顯的是Schaffer函數(shù)的優(yōu)化，IBFO算法的運(yùn)行時(shí)間為BFO算法的61.98%。IBFO在Sphere和Griewank函數(shù)上的均值相較BFO而言，提高了10個(gè)數(shù)量級(jí)，平均優(yōu)化精度最高，且運(yùn)行時(shí)間分別為BFO算法的60.23%和59.45%。

表2 2種BFO算法在測(cè)試函數(shù)上的優(yōu)化對(duì)比

檢測(cè)算法性能的另一個(gè)指標(biāo)是算法的收斂性，IBFO算法在各個(gè)函數(shù)上的收斂曲線如圖1—圖4所示。由圖4可知，改進(jìn)后的BFO算法尋得最優(yōu)解的能力得到了提高，且在全局搜索上有了很大程度的提高。圖1和圖4中改進(jìn)后的BFO算法在10代左右找到最優(yōu)解，但是因t分布變異，增加種群的多樣性后在200代時(shí)找到全局最優(yōu)解；圖2和圖3中原BFO算法在200代時(shí)找到最優(yōu)解，改進(jìn)后的BFO算法在10代左右找到最優(yōu)解。由圖2（a）、3（a）可知，BFO算法前期隨著迭代次數(shù)的增加，函數(shù)的適應(yīng)度值逐漸下降，直到找到最優(yōu)解，但I(xiàn)BFO可直接找到最優(yōu)解，尋優(yōu)能力更強(qiáng)，速度更快。

圖1 Sphere函數(shù)收斂曲線圖

圖2 Rastrigrin函數(shù)收斂曲線圖

圖3 Griewank函數(shù)收斂曲線圖

圖4 Schaffer函數(shù)收斂曲線圖

4 結(jié)語(yǔ)

本文針對(duì)細(xì)菌覓食算法易陷入局部最優(yōu)和全局搜索能力差的問(wèn)題，提出了一種融合正余弦學(xué)習(xí)因子和自適應(yīng)t分布的細(xì)菌覓食優(yōu)化算法。為協(xié)調(diào)全局搜索與局部搜索，在細(xì)菌覓食的趨向性操作中引入非正弦學(xué)習(xí)因子，并利用正余弦思想更新細(xì)菌個(gè)體；在復(fù)制操作中，對(duì)排名后50%的個(gè)體采用t分布的方式更新細(xì)菌個(gè)體位置，加強(qiáng)搜索范圍。實(shí)驗(yàn)結(jié)果表明，本文提出的方法是有效的，不僅能提高尋優(yōu)的精度值，還能縮短運(yùn)行時(shí)間。