自適應細菌覓食算法在優(yōu)化問題中的應用

肖文顯，褚鐳酈，王俊閣，劉 震，馬孝琴

細菌覓食算法［1－2］（bacterial f oraging al gorith m，簡稱BFA）是由 K.M.Passino于2002年根據(jù)生物學中人類腸道內大腸桿菌或者粘細菌在覓食過程中體現(xiàn)出的智能行為，經(jīng)過人工抽象而提出的一種智能隨機搜索算法.算法雖然起步較晚，但是應用比較廣泛［3－6］.盡管BFA算法在求解低維優(yōu)化問題時具有較好的搜索性能，但是隨著問題維數(shù)的上升和復雜程度的加大，固定的步長和固定的驅散概率使算法在后期容易陷入局部最優(yōu)解而產(chǎn)生早熟現(xiàn)象［7－9］.針對該問題，作者提出自適應步長策略，通過動態(tài)調整步長，使趨向操作能夠不斷調整并適應算法的進化程度.作者提出自適應驅散概率策略，避免BFA算法固定驅散概率帶來的優(yōu)質解流失問題，確保算法在后期不但保有較好種群多樣性而且具有穩(wěn)定的收斂能力.

1 細菌覓食算法

BFA算法模擬細菌覓食中一邊感應周邊事物濃度變化一邊進行趨近或者遠離的機制，分別設計了趨向、聚集、復制和驅散4種行為［10－12］.

1.1 趨 向

趨向行為是模擬大腸桿菌依靠鞭毛旋轉方式表現(xiàn)出的兩種不同的位置移動方式，分別為翻轉和游動.翻轉是指尋找新的方向，游動是指保持方向不變的前進.具體操作如下：首先朝某隨機方向游動一個單位步長，如果新位置的適應值比之前增加，則繼續(xù)沿著該方向游動；如果新位置的適應值比之前降低，則進行旋轉操作，朝另一個隨機方向游動.當達到最大嘗試次數(shù)后，停止趨向操作.細菌趨向操作表示如式（1）所示

其中：θi（j，k，l）為第i個細菌的位置，j、k、l分別表示細菌個體完成趨向、復制和驅散的次數(shù)；C（i）為第i個細菌進行游動的步長；Δ（i）為分量在［－1，1］之間的隨機向量.

1.2 聚 集

細菌群落在覓食過程中，會通過調整細胞與細胞之間的引力和斥力，從而使細菌在具有聚集特性的情況下又保持各自相對獨立的位置.引力使細菌聚集在一起，而斥力使得細菌分散在相對獨立的位置上獲取食物.BFA算法模擬這種聚集行為，數(shù)學表達式如下

其中：P（j，k，l）＝｛θi（j，k，l）i＝1，2，…，S｝為細菌群落；JCC（θ，P（j，k，l））為細菌群落之間傳遞信號的影響值；da為引力深度；wa引力寬度；dr為斥力高度；wr為斥力寬度.

在趨向循環(huán)中加入聚集操作后，第i個細菌的適應值應疊加傳遞信號影響值JCC，具體計算公式為

1.3 復 制

在細菌群落進化到一定程度后，根據(jù)自然選擇的“優(yōu)勝劣汰”理論，部分覓食能力較弱的細菌會被自然淘汰.同時，細菌群落會通過繁殖來保證種群規(guī)模的穩(wěn)定.BFA算法以復制操作來模擬細菌群落的這種生物現(xiàn)象.

對于確定的k、l以及每個細菌i＝1，2，…，S，定義細菌i的能量函數(shù)為

通過細菌的能量函數(shù)值來衡量細菌的覓食能力.Jienergy越大，說明細菌i的覓食能力越強；反之，細菌i的覓食能力越弱.將細菌按其能量Jienergy從大到小進行排列，淘汰掉后一半能量較小的細菌個體，然后將前一半能量較大的細菌群落中的每個個體均復制，從而生成與原細菌群落規(guī)模一致的新的具有較強覓食能力的細菌群落.

1.4 驅 散

在算法經(jīng)過若干代復制后，細菌以給定的概率進行驅散操作，被選中的細菌會隨機重新分配到新的位置.即若細菌群落中的某個細菌個體滿足驅散發(fā)生的概率，則這個個體失去原有覓食位置，在解空間中隨機選中一個新位置，由此形成了一個嶄新個體.

2 自適應細菌覓食算法

2.1 自適應趨向步長

趨向操作使BFA算法具有局部搜索能力，但是固定的步長又使算法存在一定缺陷：首先，步長的大小不易確定.步長太大，雖然算法收斂速度較快，但是搜索的跳躍性太大，算法不易找到最優(yōu)解.步長太小，算法雖然局部搜索精度較高，但算法的尋優(yōu)過程將非常漫長.

針對該問題，文獻［13］等提出采用自適應的方式調整步長，取細菌個體的步長等于周圍臨近個體中最大距離和最小距離的平均值與隨機數(shù)的乘積.但是，這種調整方式僅僅依賴最大距離和最小距離兩個細菌個體信息，步長調整的導向作用不明顯.因此，作者綜合考慮細菌個體的覓食能力（能量函數(shù)）和最大、最小距離個體對細菌個體的影響，并將上述參數(shù)進行耦合，提出步長調整參數(shù)A，如式（5）所示

其中：Ji為第i個細菌的適應值；Xmax、Xmin為變量的邊界值.

自適應調整算法在運行過程中的趨向步長，從而達到局部搜索和全局尋優(yōu)的平衡.步長自適應調整如式（6）所示

其中：Iteri、Itermax分別為迭代次數(shù)和最大迭代次數(shù).

2.2 自適應驅散概率

BFA算法中的驅散操作以一個固定的概率P將細菌群體中的部分個體進行重新位置分配，借此改善細菌群落的種群多樣性.但是，對于那些位置靠近全局最優(yōu)值的優(yōu)秀個體而言，驅散操作很可能使其丟失原有位置，被驅散至較差的一個新位置.這樣的算法進化過程實質上是一種退化.

因此，論文提出一個自適應驅散概率Pself，所有細菌個體均按照式（7）的動態(tài)概率進行自適應驅散

其中：Jienergy、Jmaxenergy、Jminenergy分別為細菌i的能量值、能量上限、能量下限.

2.3 自適應細菌覓食算法求解步驟

綜上所述，對于最小化的優(yōu)化問題，自適應BFA算法的執(zhí)行步驟如下：

第1步：參數(shù)初始化.

第2步：初始化細菌位置.在問題可行域內隨機生成初始解，計算細菌個體的適應值.

第3步：驅散循環(huán)、復制循環(huán)、趨向循環(huán).

第4步：執(zhí)行趨向操作.按式（5）、（6）自適應調整趨向步長，當適應值上升時，保持游動方向，當適應值下降時，進行旋轉，重新選定方向.若達到趨向操作次數(shù)上限，則跳出趨向循環(huán)，并執(zhí)行第5步.

第5步：執(zhí)行復制操作.

第6步：執(zhí)行驅散操作.按式（7）所示動態(tài)概率進行自適應驅散.

第7步：判斷算法是否滿足收斂條件，若收斂，則輸出結果并結束；若不滿足收斂條件，則返回第3步.

3 算 例

3.1 測試函數(shù)

為驗證改進算法的可行性和有效性，論文采用如下測試函數(shù)對上述算法進行對比測試.

（1）Sphere函數(shù)

（2）Rosenbr ock函數(shù)

（3）Rastrigrin函數(shù)

（4）Griewank函數(shù)

（5）Ackley函數(shù)

實驗設置的參數(shù)如下：

（1）函數(shù)維數(shù)N分別取5、10、20、30、50維5種方案，由于篇幅限制在此僅列出50維時的模擬計算結果；

（2）細菌總數(shù)S＝50；趨向次數(shù)為50；復制次數(shù)為3；驅散次數(shù)為2；初始游動步長C＝0.001R（R為優(yōu)化區(qū)間寬度）；驅散概率P＝0.25.

上述5個標準測試函數(shù)的理論最優(yōu)值均為0.論文分別采用BFA和自適應BFA算法對上述5個測試函數(shù)進行50次優(yōu)化計算，取優(yōu)化結果的平均值作為衡量指標.同時，為驗證論文提出改進算法的有效性，以遺傳算法對上述5個標準測試函數(shù)進行50次求解，取其平均值作為算法之間的橫向比較，結果如表1所示.

表1 函數(shù)優(yōu)化結果對比Tab.1 Comparison of results of benchmark functions

對比表1中的平均值和最優(yōu)值，可以看出：改進的BFA算法所得到的平均值、最優(yōu)值均小于標準BFA算法.由此可見，通過引入自適應動態(tài)步長和自適應調整驅散概率，改進BFA算法能夠尋找到更加優(yōu)秀的解.對比表1中的標準差，可以看出改進BFA算法結果的標準差同樣小于標準BFA算法，可見改進后的算法在求解的穩(wěn)定性方面也優(yōu)于標準BFA.對比改進BFA算法與GA算法的計算結果可見，改進BFA算法求解得到的平均值和最優(yōu)值優(yōu)于GA算法，同時前者多次求解結果的標準差也小于后者，說明論文提出的改進BFA算法的全局尋優(yōu)能力優(yōu)于GA等智能優(yōu)化算法.

將BFA算法和改進BFA算法求解上述5個測試函數(shù)的迭代過程記錄并進行對比，如圖1所示，其中迭代過程取值為多次計算的平均值.

由圖1可見，改進的BFA算法在求解測試函數(shù)時，可以以更少的計算消耗得到質量更高的尋優(yōu)結果，并且在迭代計算后期，改進的BFA算法能夠保持繼續(xù)探索新空間的能力，避免了陷入局部最優(yōu)解.

3.2 TSP問題

為進一步驗證論文提出的改進BFA算法的有效性和適用性，對于Oliver TSP30個城市（已知最優(yōu)解為423.74）和TSP50個城市（已知最優(yōu)解為427.86），分別采用標準BFA算法和改進BFA算法進行求解，參數(shù)設置與3.1中相同，取50次計算結果的平均值作為衡量指標，結果如表2所示.

表2 TSP30和TSP50問題運行結果Tab.2 Results of TSP30 and TSP50

對比表2中兩種算法所得的最優(yōu)解可見，改進的BFA算法能夠搜索到更加優(yōu)秀的解.對比平均值可見，改進BFA算法的求解性能的穩(wěn)定性要高于標準BFA算法.隨著城市數(shù)量的增加，問題變得更加復雜，對比TSP50的計算結果可見，改進BFA算法在求解復雜程度高的問題時，尋優(yōu)效果要優(yōu)于標準BFA算法.上述結論與3.1測試函數(shù)得到的結果一致，再次證明了論文提出的改進BFA算法的可行性和有效性.

4 結束語

為解決BFA算法固定趨向步長和固定驅散概率所帶來的缺陷，論文采取自適應調整趨向步長的策略，隨著搜索的不斷深入，趨向步長逐漸變小，算法得以在更精細的范圍內進行搜索.同時，論文提出驅散概率的自適應調整，將細菌進行驅散的概率的大小與其具有的能量對應，在保證種群多樣性的基礎上，進一步避免了優(yōu)秀個體的流失.通過4個測試函數(shù)的模擬計算和在TSP30、TSP50中的應用，驗證了論文提出的改進算法的可行性和有效性，改進的BFA算法性能優(yōu)于標準BFA算法，適用于求解復雜優(yōu)化問題.

［1］ Dong H K，Ajith A，Jae H C.A hybrid genetic algorith m and bacterial f oraging approach f or global opti mization［J］.Infor mation Sciences，2007，177（2）：3918－3937.

［2］ Swagatam D，Arijit B，Sambarta D.Bacterial foraging opti mization algorith m：theoretical foundations，analysis，and applications［J］.Foundations of Computer，2009，3：23－55.

［3］ 馬溪原，吳耀文，方華亮，等.采用改進細菌覓食算法的風／光／儲混合微電網(wǎng)電源優(yōu)化配置［J］.中國電機工程學報，2011，31（25）：17－25.

［4］ 崔靜靜，孫延明，車蘭秀.改進細菌覓食算法求解車間作業(yè)調度問題［J］.計算機應用研究，2011，28（9）：3324－3326.

［5］ 李丹，唐普英.基于細菌覓食的盲源分離算法研究［J］.通信技術，2011，44（12）：150－152.

［6］ 王雪松，程玉虎，郝名林.基于細菌覓食行為的分布估計算法在預測控制中的應用［J］.電子學報，2010（2）：333－339.

［7］ 肖文顯，許利軍，馬孝琴.混沌差分進化算法在復雜優(yōu)化問題中的應用研究［J］.安徽大學學報：自然科學版，2014，38（3）：32－36.

［8］ 鄭慧濤，梅亞東，胡挺，等.雙層交互混合差分進化算法在水庫群優(yōu)化調度中的應用［J］.水力發(fā)電學報，2013，32（1）：54－62.

［9］ 周雅蘭.細菌覓食優(yōu)化算法的研究與應用［J］.計算機工程與應用，2010，46（20）：16－21.

［10］ 劉小龍.細菌覓食優(yōu)化算法的改進及應用［D］.廣州：華南理工大學工商管理學院，2011.

［11］ 胡潔.細菌覓食優(yōu)化算法的改進及應用研究［D］.武漢：武漢理工大學理學院，2012.

［12］ 許鑫.細菌覓食優(yōu)化算法研究［D］.長春：吉林大學計算機科學與技術學院，2012.

［13］ 李珺，黨建武，卜鋒.自適應步長的細菌覓食優(yōu)化算法研究［J］.蘭州交通大學學報，2013，32（6）：10－14.