改進(jìn)的細(xì)菌群體趨藥性算法及應(yīng)用

楊凡 宋洪儒

（銅陵學(xué)院，安徽銅陵244000）

改進(jìn)的細(xì)菌群體趨藥性算法及應(yīng)用

楊凡 宋洪儒

（銅陵學(xué)院，安徽銅陵244000）

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

細(xì)菌群體趨藥性；均勻設(shè)計；函數(shù)優(yōu)化

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

隨著研究的深入，該算法的優(yōu)化性能瓶頸成為制約其應(yīng)用的核心問題，許多學(xué)者致力于算法改進(jìn)工作。

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

1.細(xì)菌趨藥性算法（BC）描述

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

（1）確定細(xì)菌初始位置，初始收斂精度，最終收斂精度，進(jìn)化精度更新策略，系統(tǒng)參數(shù)T0、τc、b。

（2）計算細(xì)菌在新方向上的移動時間τ；計算新運(yùn)動方向[1]。

1）τ的數(shù)值由概率分布決定：

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

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

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

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

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

算法步驟如下[2]：

（1）確定群體細(xì)菌算法中，細(xì)菌的個數(shù)，依據(jù)BC算法步驟（1）和（2）確定各參數(shù)及計算運(yùn)動時間和方向。

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

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

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

采用全體參數(shù)更新策略進(jìn)行參數(shù)更新和細(xì)菌的遷徙動作，并引入精英保留策略。

3． BCC算法的改進(jìn)

BCC算法由于細(xì)菌的運(yùn)動表現(xiàn)出一定的趨同性，增加了群體陷入局部最優(yōu)的可能性。為了進(jìn)一步提高算法魯棒性、效率和有效性，提出均勻設(shè)計初始種群的改進(jìn)方式。

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

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

表1 U20（202）

4.BCC算法及改進(jìn)算法在函數(shù)中的應(yīng)用

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

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

函數(shù)F2的局部極小點(diǎn)為在區(qū)間范圍存在大量的局部極小點(diǎn)。如圖1所示:

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

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

圖2 隨機(jī)分布點(diǎn)圖

圖3 均勻分布點(diǎn)圖

圖4 BCC與改進(jìn)BCC的尋優(yōu)結(jié)果

通過運(yùn)行算法100次并統(tǒng)計結(jié)果可知，為找到最優(yōu)解，BCC算法需進(jìn)化37代左右，而改進(jìn)的BCC算法在進(jìn)化20代后，所有細(xì)菌都能達(dá)到最優(yōu)值，并且當(dāng)細(xì)菌尋找到最小值后，所有細(xì)菌將聚集在最小點(diǎn)處。

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

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

5． 結(jié)論

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

［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］李威武，王慧，鄒志君等.基于細(xì)菌群體趨藥性的函數(shù)優(yōu)化方法[J].電路與系統(tǒng)學(xué)報,2005,10(1):58-63.

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

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

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

TP18

A

1672-0547（2010）06-0061-02

2010-11-06

楊凡（1978-），女，遼寧營口人，銅陵學(xué)院數(shù)學(xué)與計算機(jī)科學(xué)系助教，碩士，研究方向：進(jìn)化計算。

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