連續優化問題的細菌覓食改進算法

戴秋萍， 馬 良， 郗 瑩

（上海理工大學 管理學院，上海 200093）

經典的優化算法在函數優化問題中，常常要求函數連續可微，因此在求解過程中需要借助一些基于梯度信息的數學技巧，并且在接近最優解時容易出現鋸齒現象，造成收斂速度緩慢［1］.20世紀50年代中期，人們從生物進化的機理中得到啟發，創立了仿生學，并提出了許多解決復雜優化問題的智能方法，如神經網絡、遺傳算法［2］、進化策略、螞蟻算法［3］等，這些方法在連續函數優化問題中取得了較好的結果.本文提出了一種新的智能優化算法——細菌覓食算法對連續函數優化問題進行求解.

細菌覓食算法（bacterial foraging optimization，BFO）是由Passino［4］于2002年提出來的一種仿生隨機搜索算法，該算法具有群體智能性，并可進行并行搜索.目前，BFO 已被用于車間調度問題、自適應控制領域、噪聲干擾下的諧波估計問題和PID（proportional integral derivative）控制器的設計等方面，并獲得了較好的效果［5－6］.本文對細菌覓食算法操作步驟進行了改進，有效地改善了該算法極易陷入局部最優的缺點，使其在解決復雜連續優化問題時，全局搜索能力大大增強.另外，通過大量仿真實驗驗證了該算法的有效性.

1 細菌覓食算法介紹

細菌覓食算法是基于大腸桿菌在覓食過程中體現出來的智能行為的一種新型仿生優化算法，其具有群體智能性、并行性等特點.細菌覓食算法包括趨化操作（chemotaxis）、復制操作（reproduction）和遷徙（elimination and dispersal）操作.這3種操作方式是模仿細菌覓食的趨向行為、復制行為和遷移行為的抽象［7－8］.

a.趨化操作 大腸桿菌在尋找食物源的過程中，其運動是通過表層的鞭毛實現的.當鞭毛全部逆時針擺動時，大腸桿菌將會向前行；當鞭毛全部順時針擺動時，它會減速至停止.鞭毛的擺動對應著細菌個體對當前適應值的判斷，并決定是否對其位置進行調整和確定調整的方向和力度.趨化操作模擬了大腸桿菌的這個運動過程，包括游動和翻轉兩個操作.

設pi（j，k，l）表示細菌個體i的當前位置，j表示第j 次趨化行為，k 表示第k 次復制行為，l表示第l次遷徙行為.則

其中，φ（j）表示游動的方向； C（i） 表示前進步長.

b.復制操作 設群體規模為S，在完成設定次數的趨向操作之后，將群體中的個體按照其適應度值進行排序，將排在后面S／2 的個體刪除，剩下的個體進行自我復制，保證群體規模的穩定性.

c.遷徙操作 遷徙操作按照預先設定的一個概率發生，若某一個個體滿足遷徙操作發生的條件，那么即將此個體刪除，并生成一個新的個體代替.相當于將原來個體重新分配到一個新的位置，即以一定的概率將個體隨機驅散到搜索空間.

2 算法改進

2.1 初始化操作改進

在細菌覓食算法中，細菌種群的大小直接影響細菌尋求最優解的能力.種群數量越大，其初始覆蓋區域越大，靠近最優解的概率就越大，能避免算法陷入局部極值，但同時增加了算法的計算量.因此，本文將初始化操作進行了改進.改進后，在細菌規模較小的情況下，能比較有效地改善初始化后細菌群體的覆蓋范圍（見圖1、圖2）.確定群體規模S 之后，將群體搜索的空間分成S個區域，每個細菌個體的初始位置為S個區域的中心點，隨即細菌將在各自區域內搜索.

圖1 改進前細菌初始化狀態Fig.1 Initialization state of bacteria before improved

圖2 改進后細菌個體初始化狀態Fig.2 Initialization state of bacteria after improved

由圖1可知，細菌個體隨機生成時，菌群可能在搜索空間內分布不均，在搜索最優解過程中，極有可能在限定的游動步長內無法找到最優解而陷入局部最優.

2.2 趨化操作改進

細菌覓食算法中，趨化操作是細菌覓食過程中最重要的一個步驟.基本細菌覓食算法在進行趨化操作時，細菌個體是根據歷史信息按固定步長朝著食物源方向游動.在解決連續函數優化問題，尤其是多峰函數優化問題時，傳統的操作方式易使得細菌個體錯過最優解，本文對趨化搜索方式進行了改進.

將細菌個體所在區域切分為n×n塊，每個細菌在進行翻轉操作時，僅在細菌周圍的8個方向中隨機選取，游動過程中每游動一次前進步長縮短為原來步長的0.8倍， C（i） ＝0.8 C（i） .當細菌個體游動次數并未達到設定游動次數時，細菌將再進行一次翻轉操作.

趨化操作步驟：

a.確定細菌個體i，確定游動方向φ（j）.

c.判斷當前位置是否更優，是則個體i被新個體取代，繼續步驟b，步長 C（i）變為0.8 C（i） .

d.判斷是否達到設定游動次數，未達到轉步驟a，達到游動次數細菌個體i趨化操作結束.

2.3 復制操作改進

細菌覓食過程中，一段時間后，細菌會根據個體位置的適應度值進行優劣排序.排在后面的S／2個細菌死亡，而排在前面的S／2個細菌進行自我復制，隨即細菌往較小范圍聚集.在求解多峰連續優化問題時，菌群極有可能跳過最優解而陷入局部最優.

本算法將細菌個體首先隨機與鄰域周圍的一個細菌進行交叉變異，變異后的細菌個體適應度值若優于原個體，原個體將被替代.通過一次改進后的復制操作后，整個菌群完成一次更新，菌群規模不變，每個細菌個體僅在各自區域及鄰域內進行變異和適應度值比較，從而有效地防止了菌群向較小范圍內聚集.改進后的復制操作不再只是覓食能力強的細菌個體單純的自我繁殖過程，整個菌群群體都朝著更優的方向游動，提高了菌群整體的尋優能力.改進后復制操作過程如圖3所示.

3 實驗仿真與結果分析

前述細菌覓食算法采用Matlab 7予以實現，在PC系列機的Windows 7 系統環境下運行通過.本文通過大量實例驗證了此改進算法的有效性，下面給出4個算例及求解結果分析（見圖4～7，圖5～7見下頁）.算法相關參數設定：細菌規模為225，趨向操作數為10，復制操作數為4，遷徙操作數為2.

算例1

圖3 改進后復制操作示意圖Fig.3 Operation schematic diagram of improved reproduction process

圖4 算例1函數示意圖Fig.4 Function schematic diagram of example 1

由函數示意圖可知，該函數最優解處于中間區域，周圍有很多局部極值圍繞著最優解，用傳統的細菌覓食算法陷入局部最優的可能性非常大.元胞蟻群算法、混沌算法均可得到最優解1，LINGO 軟件得到的最優解為0.646 848 8，Matlab優化工具得到的結果為0.990 3.

算例2

該問題的最優解被最差解包圍，4個局部值點為（－5.12，5.12）、（－5.12，－5.12）、（5.12，5.12）、（5.12，－5.12），函數值均為2 748.78.運行改進后的細菌覓食算法求解該問題能夠有效地獲得最優解.

算例3

該函數在（1，1）處有最小值0，且在最優解附近存在病態，用常規方法容易陷入局部最優，難以搜索到最優解.

圖5 算例2函數示意圖Fig.5 Function schematic diagram of example 2

圖6 算例3函數示意圖Fig.6 Function schematic diagram of example 3

算例4

圖7 算例4函數示意圖Fig.7 Function schematic diagram of example 4

該算例可看出是典型的多峰函數，運用傳統算法求解最優解相當困難.遺傳算法目前所求最優解為38.827 533，運行LINGO 軟件與Matlab得到的解均小于38.

表1為該算法求解上述函數運行30次后的結果分析.其中平均偏差率為算法運行30次解的平均值與最優解的比值.

4 結束語

首先對細菌初始化操作進行了改進，改變了傳統的細菌覓食算法中的初始方式，使得菌群規模較小的情況下，能有較大的覆蓋面.此外，本算法對細菌個體的搜索方式也進行了適當改進，增強了個體的局部搜索能力.為防止菌群在復制操作中過快地向小范圍聚集而陷入局部最優，菌群進行變異性復制，不僅保證了菌群整體朝更優方向游動，同時大大提高了此算法的全局搜索能力.通過實驗表明，改進后的細菌覓食算法在求解連續優化問題時，穩定性好，能夠快速有效地找到最優解.

表1 結果分析Tab.1 Results analysis

通過與其它算法相比可得出以下結論：

a.改進后的細菌覓食算法改進了傳統細菌覓食算法的缺點，有效地改善了傳統算法的收斂速度和全局尋優能力，所獲最優解質量得到改善.

b.改進后的細菌覓食算法能夠有效解決連續優化問題，為連續優化問題提供一種新的解決方法.

［1］馬良，朱剛，寧愛兵.蟻群優化算法［M］.北京：科學出版社，2008.

［2］張惠珍，馬良.基于變尺度混沌優化策略的混合遺傳算法及在神經網絡中的應用［J］.上海理工大學學報，2007，29（3）：215－219.

［3］邱模杰，馬良.約束平面選址問題的螞蟻算法［J］.上海理工大學學報，2000，22（9）：61－62.

［4］Passino K M.Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Systems Magazine，2002，22（3）：52－67.

［5］梁艷春，吳春國，時小虎，等.群體智能優化算法理論與應用［M］.北京：科學出版社，2009.

［6］張娜.細菌覓食優化算法求解車間調度問題的研究［D］.吉林：吉林大學，2007.

［7］胡海波，黃友銳.混合粒子群算法優化分數階P／D 控制參 數 研 究［J］.計 算 機 應 用，2009，29（9）：2483－2486.

［8］李亞楠.菌群優化算法的研究［D］.哈爾濱：哈爾濱工業大學，2009.