改進的細菌群體趨藥性算法及應用

楊凡 宋洪儒

（銅陵學院，安徽銅陵244000）

改進的細菌群體趨藥性算法及應用

楊凡 宋洪儒

（銅陵學院，安徽銅陵244000）

為使細菌群體趨藥性(BCC)算法中細菌群體初始種群在解空間足夠均勻，文章提出改進的BCC算法，利用均勻設計方法優選出合適的初始種群，以充分利用解空間的信息；將改進的算法，應用于函數優化上，結果表明改進后的算法在函數進化代數和尋優成功率上都有較大的提高，說明改進的方式能提高BCC算法整體運行性能。

細菌群體趨藥性；均勻設計；函數優化

源于大自然生物過程的啟迪，例如生物的進化過程，昆蟲覓食行為等，發展出了遺傳算法、蟻群算法等智能優化方法。Miiler及其同事們模擬細菌在引誘劑環境下的應激機制，于2002年提出了細菌趨藥性（Bacterial Chemotaxis，BC）算法[1]。浙江大學的李威武等人在BC算法的基礎上，利用群體智能的思想，于2005年提出了細菌群體趨藥性（Bacterial Colony Chemotaxis，BCC）算法[2]。BC/BCC算法及其改進算法已經成功應用于函數優化[3]、電力系統無功優化[4]等領域，預示著其良好的應用前景。

隨著研究的深入，該算法的優化性能瓶頸成為制約其應用的核心問題，許多學者致力于算法改進工作。

目前，BCC算法對初始種群的分布一般采用隨機選取的方式，難以在算法開始運行時提供有效的解空間信息。為了較好的表征解空間，利用均勻設計生成初始菌群，會對BCC算法的性能提高有一定作用。

1.細菌趨藥性算法（BC）描述

該算法的步驟如下[1]：

（1）確定細菌初始位置，初始收斂精度，最終收斂精度，進化精度更新策略，系統參數T0、τc、b。

（2）計算細菌在新方向上的移動時間τ；計算新運動方向[1]。

1）τ的數值由概率分布決定：

2）新方向與原來軌跡的夾角根據新向左或向右偏轉分別服從下面兩個高斯概率分布：

其中，它們的期望和方差分別按參考文獻1的方式給出。

（3）計算細菌在變量空間中新的位置：

2.細菌群體趨藥性算法(BCC)

BC算法是基于單個細菌的搜索，通過不斷感受它周圍的環境的變化和利用它過去的經驗來尋找最優點，其尋優能力尚不及其他群體智能優化算法；李威武等人提出了細菌群體趨藥性（BCC）算法[2]。在尋優過程中細菌充分利用個體信息和群體的信息，使算法的性能有了很大的提高。

算法步驟如下[2]：

（1）確定群體細菌算法中，細菌的個數，依據BC算法步驟（1）和（2）確定各參數及計算運動時間和方向。

（2）對處在移動步數k的細菌i，感知其周圍有更好位置的其他細菌，并確定它們的中心點Cente（r）和一個假定的朝這個中心方向移動的長度len=rand(·)dis(,Center())，確定位置；

（3）對處在移動步數k的細菌i，同時根據它自己記憶的上幾步的位置信息按BC算法步驟(3)確定在步數k+1時的新位置；

（5）重復步驟2-4，直至中止條件滿足。

采用全體參數更新策略進行參數更新和細菌的遷徙動作，并引入精英保留策略。

3． BCC算法的改進

BCC算法由于細菌的運動表現出一定的趨同性，增加了群體陷入局部最優的可能性。為了進一步提高算法魯棒性、效率和有效性，提出均勻設計初始種群的改進方式。

均勻設計是一種可以用最少的信息來獲得空間最多信息的一種方法，它已經成功地應用于遺傳算法的初始種群與操作參數的設計，并且取得了良好的效果[5]。借鑒于遺傳算法初始種群的優化，本文將引入均勻設計的思想，對BCC算法的初始種群進行設計。

對初始分布點進行均勻設計，實驗次數20次，2個因素，對應空間2維坐標，采用實數進行編碼，即U20(202)；均勻設計表的方法很多，這里采用好格子方法，均勻性度量函數中心化L2偏差，得到多個均勻化偏差值最小的均勻設計表，表1。

表1 U20（202）

4.BCC算法及改進算法在函數中的應用

為驗證函數的有效性，設計如下測試方案：初始菌群由均勻設計生成，細菌之間操作步驟仍然遵循BCC算法方法；測試函數如下：

函數F1中有全局最小值F(-0.9095537，-0.9505717)=34.0402425；和一個局部最小值F(1，1)=74；該函數易陷入局部最小，很少能夠找到全局最小值。

函數F2的局部極小點為在區間范圍存在大量的局部極小點。如圖1所示:

圖1 F2(x,y)函數空間圖

為比較不同初始菌群生成方法對算法性能的影響，對BCC及改進BCC算法進行測試，參數設置如下，細菌個數20個，初始精度設為10-2，收斂精度10-10，精度下降梯度1.15；以為例進行尋優，使用隨機方法和均勻設計方法產生初始菌群的情況分別如圖2和圖3所示，其進化曲線如圖4所示。

圖2 隨機分布點圖

圖3 均勻分布點圖

圖4 BCC與改進BCC的尋優結果

通過運行算法100次并統計結果可知，為找到最優解，BCC算法需進化37代左右，而改進的BCC算法在進化20代后，所有細菌都能達到最優值，并且當細菌尋找到最小值后，所有細菌將聚集在最小點處。

表2 兩種方式在F2(x，y)上性能比較

從表2可以看出，BCC算法的初始分布點由隨機分布方式改為均勻分布方式后，最終點位置的精度維持不變，運行所需的時間有所增加，但找到最小值的成功率大幅度提升。

5． 結論

BCC算法是一種群體智能優化算法，針對該算法的性能瓶頸，提出使用均勻設計生成初始菌群，對原算法進行了改進。通過函數仿真實驗表明，改進算法在進化代數上有較大的減少、且對函數尋優的成功率較高，具有一定的應用前景。

［1］Müller Sibylle D.,Marchetto Jarno,Airaghi Stefano.Optimization Based on Bacterial Chemotaxis[J].IEEE Transaction of Evolutionary Computation,2002,6(1):16-29.

［2］李威武，王慧，鄒志君等.基于細菌群體趨藥性的函數優化方法[J].電路與系統學報,2005,10(1):58-63.

［3］劉文霞，劉曉茹，張建華等.基于微分進化和混沌遷移的細菌群體趨藥性算法[J].控制理論與應用,2009,26(4):353-357.

［4］呂慧顯.基于微細菌群體趨藥性的函數優化算法[J].青島大學學報（工程技術版）,2009,24(1):19-25.

［5］何大闊，王福利，賈明興.遺傳算法初始種群與操作參數的均勻設計[J].東北大學學報，2009，26(9):828-831.

TP18

A

1672-0547（2010）06-0061-02

2010-11-06

楊凡（1978-），女，遼寧營口人，銅陵學院數學與計算機科學系助教，碩士，研究方向：進化計算。

安徽省高等學校省級自然科學研究項目《細菌群體趨藥性算法的改進與應用》(編號：KJ2010B458)階段性成果。