一種具有量子行為的細菌覓食優化算法

章國勇 伍永剛 譚宇翔

(華中科技大學水電與數字化工程學院 武漢 430074)

1 引言

細菌覓食優化[1](Bacterial Foraging Optimization, BFO)算法是由Passino在Breg等人的研究成果基礎上，從微生物的行為機制出發，通過模擬大腸桿菌覓食行為提出的一種新的全局優化進化算法，現已成功應用于電力系統優化與控制[2]、函數優化[3]、圖像處理[4]等中。相比Muller等人提出的基于單個細菌運動行為的細菌趨藥性(BC)算法，BFO通過細菌群體的競爭與協作來實現優化，是一種基于群體的搜索技術。但Tang等人[5]的仿真實驗指出，在現行的BFO群體感應機制下，細菌游動時不進行群體內通信時在收斂速度和精度上反而優于存在群體感應機制的BFO。同時，現有仿真實例表明，對于多維復雜優化問題，細菌的覓食機制容易引起算法早熟收斂[3]，較難獲得全局最優。

為克服BFO算法的上述缺陷，學者們從算法參數和算法融合上進行了研究。針對趨化步長對算法搜索能力的影響，Mishra[6]提出用TS模糊機制選取最優步長的模糊細菌覓食算法；Das等人[7]提出一種隨適應度值自適應變化的趨化步長控制策略；Chen等人[8]提出用自適應增量調制來控制趨向性步長；Tang等人[9]將PSO進化機制引入到BFO趨化操作中。在不增加算法復雜性的前提下，上述方法有效地提高了算法收斂速度。根據 Abraham 等人[10]對BFO中繁殖操作效果的數學分析表明，繁殖操作是算法的主要驅動因子，而現行BFO中采用的直接復制方法大大降低了種群的多樣性。根據NFL(無免費午餐)定理，文獻[11-13]分別結合差分進化、分布估計和免疫算法對BFO進行改善，結合各自算法的優點取得了不錯的效果，但對于多峰高維函數的優化過程中表現出了尋優精度較低、成功率不高等缺陷。

從現行BFO的相關研究可以看出，細菌覓食機制側重于個體的局部搜索而缺乏全局空間尋優能力[14]。Sun等人[15]從量子力學的角度出發，提出一種具有量子行為的粒子群(QPSO)算法。相比粒子群算法，QPSO基于群體信息建立了量子空間下概率分布模型，使得個體能以某一概率出現在整個可行搜索空間的任意位置，表現出了更強的全局搜索性能和更大的種群隨機性。基于此，本文在細菌的繁殖階段引入量子行為的概念，充分利用細菌群體的共享信息構建量子空間下細菌群的Delta勢阱模型，通過蒙特卡羅隨機采樣完成對細菌群的繁殖；同時，針對細菌趨化步長提出了一種動態縮進控制策略，增加了種群的多樣性和全局尋優幾率。通過理論分析和仿真實驗驗證了所提出算法的有效性。

2 具有量子行為的細菌覓食優化算法設計

2.1 QBFO原理描述

由BFO算法的基本原理可知，細菌個體尋優由趨化、繁殖和遷移 3個操作通過 3層嵌套循環完成[16]。通過細菌的趨化操作實現個體自身較強的局部搜索能力，而細菌的繁殖算子相當于進化算法的選擇操作，通過淘汰覓食能力差的個體最終實現算法的收斂。BFO中繁殖算子將提高細菌的收斂速度和精度[12]，但由于細菌移動步長過小、進化過程中個體間缺乏有效的信息共享機制等因素，采用直接個體復制的繁殖操作將導致種群多樣性的缺乏，算法容易因此陷入局部最小區域。另外，在BFO趨化算子的游動和翻轉中，細菌游動步長C是控制種群多樣性和收斂性的重要參數。一般對于C的取值不應小于某一特定數值，這樣能夠有效避免算法過早收斂；但當C太大時會明顯降低算法的收斂速度，丟失尋找到最優解的機會[16]。標準BFO中采用固定步長的控制方式，但實際操作中難以確定C的取值。

基于上述問題, 本文將量子行為引入到細菌群繁殖算子中，形成具有量子行為的細菌覓食優化(QBFO)算法。QBFO 的設計思想是：在繁殖階段通過利用細菌群共享信息建立量子空間下細菌個體的概率密度函數，由蒙特卡洛隨機采樣完成各細菌個體位置的更新，進而實現種群的繁殖操作，避免因直接復制導致的種群多樣性丟失。由文獻[15]對量子系統中個體的收斂分析可知，在QBFO中，需對群體建立一個量子化的勢阱來束縛個體，使得群體具有聚集態，處于量子束縛態的個體能以一定的概率密度出現在空間任意點，且滿足當粒子與中心的距離趨向無窮時概率趨近0。現假設在一個D維的搜索空間中，t時刻第i個體的位置表示為xi(t)=[xi1(t),xi2(t),…,xiD(t)]T，個體最好位置為Pi(t)=[Pi1(t),Pi2(t),…,PiD(t)]T，全局最好位置為Pg(t)=[Pg1(t),Pg2(t),…,PgD(t)]T，其中g為全局最優位置下標。根據Clerc等人[17]對個體運行軌跡的分析表明，要保證算法的收斂性，個體i第d維變量的位置必須收斂于其自身局部吸引子Pd，并滿足以下條件：

其中Y=xid-Pd，表示個體所處位置xid與吸引子的距離。將其代入量子力學中Schrodinger方程(式3)，可得個體每一維的波函數ψ(Y,t)(式4)和概率密度函數Q(Y)(式5)，其中L為Delta勢阱的特征長度。

其中參數β為收縮-擴張系數，必須滿足β＜1.782以保證算法收斂[15]，通常采用隨著進化代數t從β1線性改變至β2的方式(式8)；mbest為種群最好位置向量的平均值，如式(9)所示：

由QBFO的更新方程(式6)可知，細菌位置更新過程中的每一維變量xid服從一個以吸引子Pd為中心，L為范圍的概率分布。細菌群位置在測量前沒有既定的規程，采用概率分布函數更新細菌個體位置使其能以一定的概率分布出現在任意位置，達到全局搜索。相比傳統進化算法，QBFO是統計理論與隨機優化的結合，具有更大的隨機性和更強的全局搜索能力。

2.2 QBFO執行步驟

針對標準BFO趨化操作中固定步長的缺陷，該文提出了一種動態縮進控制策略，在保證細菌收斂性的同時增大細菌個體尋優空間。據此，該文提出的QBFO算法具體實現步驟如下：

步驟 1參數初始化。包括細菌個體數s，遷移次數Ned，繁殖次數Nre，趨化次數Nc，游動次數Ns，遷移概率ped。

步驟 2 種群初始化。在解空間中隨機生成s個獨立的細菌個體向量xi。

步驟 3 計算各細菌個體適應度函數值J。

步驟 4 開始循環操作。遷移循環l=1 :Ned；繁殖循環k=1 :Nre；趨化循環j=1 :Nc。

步驟 5 執行趨化操作循環。forj=1 :Nc，對每個細菌i按如下步驟執行：

(a)翻滾：產生一個隨機向量Δ∈Rn進行方向調整，向量Δ的每一個元素為區間[-1,1]的隨機數。對個體變量xid(d=1,2,…,D)按式(10)更新細菌位置，其余的D-1個變量保持不變。

其中C(i,j)表示向前游動的步長單位，φ(i)表示旋轉后選擇的隨機前進方向。

(b)游動：評價xi(j+1,k,l)適應度，若優于xi(j,k,l)，則將xi(j,k,l)替換為xi(j+1,k,l)，并按照此翻轉的方向進行游動，直至適應值不再改善或者達到最大前進步數。

(c)d=d+1，若d=D轉步驟5(d)，否則轉步驟(a)繼續對下一變量進行操作。

(d)j=j+1 ，按式(13)動態縮進策略改變細菌個體游動步長，其中A為動態縮進系數。

步驟6基于量子行為的細菌繁殖操作。經過一個完整的趨化循環后，更新當前群體的個體最好位置和全局最優位置。根據式(9)計算種群的平均最好位置向量mbest，并按照式(6)更新群體位置。

步驟7細菌遷徙。將所有細菌按照能量進行排序，對適應度較低的部分細菌(s·Ped)按照隨機初始化的方法進行遷徙。

步驟8循環結束判斷，滿足則結束。

3 算法特性及收斂性說明

在 BFO 算法中，細菌趨化操作對應細菌覓食過程中的游動和方向調整策略，決定了BFO的收斂性。為了提高細菌趨化行為的效率和種群多樣性，本文提出一種動態縮進步長控制策略。將趨化初始步長取變量最大尋優范圍，隨著趨向迭代運行動態縮進，逐步對趨化步長進行縮小，在保證細菌收斂性的同時拓寬了細菌個體尋優空間，增強了細菌個體全局尋優能力。在細菌的趨化循環完成后，進入繁殖階段，QBFO結合了量子空間下種群的概率進化機制，利用細菌群共享信息建立各細菌個體概率密度函數，通過蒙特卡洛隨機采樣完成對細菌群的繁殖，使其能以一定概率對整個空間進行搜索，將有效避免算法陷入早熟收斂。

針對 BFO的收斂性分析，Das等人[7]做了相應的證明，本文在他的基礎上從Solis等人[18]提出的收斂準則入手，給出QBFO的收斂性說明。對于最小化問題，給定一個目標函數f,S是f(x)的解空間(S∈?n)，假如算法在最優化區域Rε={z∈S|f(z)＜φ+s}找到了一點z，則這個點即為被找到的全局最小值的一個可接受近似值。現在需考慮一個算法是否能夠在搜索空間中到達最優化區域。

假設1對于S的任意Borel子集A，若其測度v|A|＞0，則有

其中μt[A]是由測度μt得到A的概率。這表明對于測度大于0的任意一個集合A而言，如果采用隨機取樣的方法，則其無窮多次重復錯過集合A的概率必定為0。由Solis準則, 可得到下面的定理：

定理1假定算法在每一步都有最優解，且目標函數f是可測函數，區域S是?n的可測子集，且滿足假設1，設 {zk}k∞=0表示算法生成的空間位置向量，則可得

其中P[zk∈Rε]表示第k步算法生成的解θk∈Rε的概率。

4 仿真實驗結果與分析

4.1 仿真設計

本節的仿真中，引入了 5個標準函數來測試QBFO的總體性能(見表1)。這些函數理論最小值均為 0，由于其全局最優解通常在一個狹小的地帶，采用常規的優化方法較難獲取最優值，且優化的難度隨著函數維數的增加而急劇上升。對于單峰低維函數，BFO可以得到滿意的優化結果，但對于多峰高維函數，其優化效果難以令人滿意。因此，本文測試函數的維度均設置為30維。文中設計了6組算法對比測試實驗，包括標準BFO[1]及幾種改進算法：EDA-BFO[12], IBFO[13], BSO[9], DEBFO[11]和GAQPSO[19]，算法參數參照相應文獻。本文提出的QBFO 算法中種群個數取 40；收縮-擴張系數：β1=1,β2=0.5；遷移概率0.25；遷移次數Ned=2；繁殖Nre=5；趨化Nc=30；游動Ns=4；動態縮進系數A=0.7。考慮到 Schwefel函數尋優空間較復雜，Ned取 3,Nc取 20。算法趨化操作迭代總次數MAXIER=Ned·Nre·Nc為300次。

4.2 仿真結果及分析

5個測試函數分別運行20次所得的目標函數最優解的均值和標準差如表 2所示，可以看出，針對函數f2,f3和f4，現有的一些改進算法基本上能獲得較好的尋優結果但精度不高，本文提出的QBFO算法較其他大多數改進算法能獲得較高的收斂精度，且在提高精度的同時保持最優解的標準差較小，表現出了較好的穩定性。由于上述函數最優值所在區域較平坦，在進化后期不需要優化算法對解空間進行大范圍的探索，本文求解精度較文獻[13]中的IBSO稍低。但從表2中可以看出，QBFO已達到較高的全局收斂精度且性能穩定，而對于IBFO，由于進化后期群體多樣性較小，細菌個體在較小區域進行集中搜索以達到較高的收斂精度，但當函數最優值所在區域較狹窄時將可能導致算法陷入早熟收斂，其對函數f1和f5的測試結果充分說明了這點。同時，通過調整QBFO中控制趨化步長的動態層進系數可以增大算法對該類問題的求解精度，關于不同參數下算法性能的比較在本文4.5節有詳細分析。

針對函數f1和f5而言，由于最優值附近存在陡峭區域，極易發生早熟收斂，要求種群具有較大的搜索空間。相關改進算法在上述函數中測試結果并不理想，有些算法或者不針對f5進行比較，而已有改進算法大都是通過增加迭代次數來提高算法獲取全局最優的概率，其優化結果通常表現為最優解較好、平均值較差，算法尋優成功率不高。從表2中可以看到QBFO在f1和f5上的隨機測試中平均最優值均在1.0e-4數量級，相比其他改進算法具有非常高的收斂精度，且在20次的測試中，函數最優值的標準差較小，每次的測試結果均在1.0e-4附近，充分體現了其較強的的穩定性和全局收斂能力。

表1 標準測試函數

表2 標準函數算法測試的平均最優值及標準差

4.3 算法性能評價

為進一步評估不同算法的時間復雜度，本文采用固定進化代數下算法最優解收斂過程以及到達確定閾值的平均進化代數、成功率兩項來評價不同優化算法的優化性能。前者在一定程度上反映出算法的收斂速度，而平均進化代數體現出算法的進化速度，成功率可以體現算法的可靠性[14]。表 3給出了在給定閾值下不同算法的成功率及平均進化代數，函數設置同上。計算迭代次數中將細菌游動次數記為4，當迭代次數達到1000代而仍未滿足給定值則認為算法已陷于局部最優解。從表 3可以看出，由于文中選取的函數在整個取值區間內均有無數局部極值點，QPSO和BSO算法成功率不高，但QBFO算法均能達到100%的成功率。對于函數f3和f4, QPSO和BSO算法也取得了一定成功率，但算法達到成功的進化代數均明顯增多，且成功率較低，算法可靠性不高。針對函數f1和f2而言，由于函數最優值附近有陡峭的區域，極易發生早熟收斂，而函數f5的復雜性取決于遠離全局最優解的局部最優解， QPSO和BSO算法很難搜索到函數的全局極值，難以實現函數優化目標。因此，本文認為QBFO針對該類多峰高維問題具有較高的適用性且能夠較穩定地獲得全局最優。

算法的收斂性也是檢測算法性能的重要指標，圖1給出了QBFO迭代過程中函數最優值和種群平均值的收斂曲線。可以看出，基于量子行為概率分布的繁殖算子使得種群平均值與最優值之間保持了較大的距離，尤其是在對函數f1和f5的求解過程中，QBFO保持了較高的種群多樣性，使得細菌群能夠對整個空間進行搜索。同時，動態縮進游動步長控制策略使得細菌個體在每次迭代開始時都能從一個較大的尋優空間進行搜索，繼而進行動態縮進，保證了算法較好的搜索精度和較快的收斂速度。因此，從總體上看，QBFO算法借助上述機制在全局收斂性、進化代數和尋優結果質量上均優于其他2種算法。

表3 運行20次尋優成功率與平均迭代次數

圖1 算法收斂測試曲線

4.4 算法種群多樣性分析

在仿生優化算法的研究中，為了避免算法的過早收斂，許多學者提出了通過控制種群的多樣性來提高算法總體性能。為比較BFO和QBFO算法中種群多樣性的變化過程，本文選取Sphere(單峰函數)和Griewank(多峰函數)進行優化求解，采用平均粒距來評價D維函數的種群多樣性[19]。

式(16)中L為變量搜索空間范圍，M為種群大小，xij為個體i第j維變量，為細菌種群第j維變量的平均值。式(16)表明，種群的多樣性值越小說明種群聚集在一個狹小的空間，此時可提高算法收斂精度但容易陷入局部最優；相反，種群的多樣性越大時細菌群分散在較大的尋優空間，但此時算法收斂速度較慢。兩種算法分別獨立運行20次，變量維數為 30，趨化迭代總次數MAXIER=Ned·Nre·Nc約250次，其他設置同上。記錄每次迭代的div(x)，其隨算法迭代次數變化的曲線如圖2所示。可以看出，BFO通過復制來完成繁殖操作將使得種群的平均粒距迅速下降，一旦種群中部分個體得到改善，其他較差個體受復制操作的影響將被替代，種群的多樣性大大減少。對于單峰 Sphere函數而言，尋優過程較簡單，BFO和QBFO中種群的平均粒距最終均較小，有利于提高算法收斂精度。而對于多峰Griewank函數，其全局最優解較難找到，平均粒距過小將導致算法過早陷入局部最優。相比標準BFO, QBFO通過對種群的概率分布模型進行蒙特卡洛隨機采樣使得處于量子束縛態的個體以一定的概率密度出現在空間任意點，保持了種群的多樣性，增加了算法全局尋優的幾率。

4.5 算法參數靈敏度分析

圖2 BFO和QBFO種群多樣性比較

對于標準 BFO 和收縮-擴張系數β的參數分析在相關文獻已有討論[16,20]，本文重點討論動態縮進系數A對算法性能的影響。A越小，搜索步長縮減越快，游動步長越小，此時可提高趨化操作后期的收斂精度，但算法會因此過快陷入小范圍局部尋優，且算法的時間復雜度也隨之增加；反之，A較大可使細菌趨化操作步長衰減速度較慢，細菌個體保持較大的尋優空間，但也將因此降低算法的收斂精度。本文選擇不同動態縮進系數分別進行20次優化，函數的維度均為30，優化結果如表4所示。可以看出，對于求解過程較簡單的函數f3和f4，借助BFO自身較強的局部尋優能力，取A=0.60左右時較為理想，此時算法能獲取較高的收斂精度，且保證算法具有較強的穩定性。而對于較復雜的函數f1,f2和f5，由于全局最優的范圍較狹窄，且距離局部最優值很遠。當A較小時，搜索步長縮減較快，算法難以跳出局部最優值所在區域；而當A較大時細菌游動步長一直保持較大值，個體將因此而跳過最優解區域，導致算法難以收斂到最優解區域附近。

表4 動態縮進系數敏感性分析

綜合上述，通常取0.60-0.70時優化結果較為理想，此時算法能找出測試函數的全局最優且性能穩定，函數最優平均適應度值較好，在實際工程問題可根據具體情況適當調整參數以獲取最優解。

5 結束語

本文將細菌個體放在量子空間中描述，充分利用量子空間下種群概率進化機制的全局搜索性能及細菌覓食行為機制的局部優化能力，提出了一種具有量子行為的細菌群覓食優化算法。文中引入了基于細菌群信息的量子概率分布模型進行種群繁殖操作，同時提出一種動態縮進的細菌游動步長控制策略，使得個體能夠在局部尋優的基礎上對整個空間進行搜索。仿真結果表明，對于多峰高維函數，QBFO較其他改進算法具有更高的適用性且能夠較穩定地獲得全局最優。后續研究主要是探討不同勢阱模型下的收斂情況，并將該方法應用于解決高維復雜工程的相應優化問題。

[1]Passino K M. Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine,2002, 22(3): 52-67.

[2]Saber A Y. Economic dispatch using particle swarm optimization with bacterial foraging effect[J].Electrical Power and Energy Systems, 2012, 34(1): 38-46.

[3]Chatzis S P and Koukas S. Numerical optimization using synergetic swarms of foraging bacterial populations[J].Expert Systems with Applications, 2011, 38(12): 15332-15343.

[4]Verma P O, Hanmandlu M, Kumar P,et al.. A novel bacterial foraging technique for edge detection[J].Pattern Recognition Letters, 2011, 32(8): 1187-1196.

[5]Tang W J, Wu Q H, and Saunders J R. Bacterial foraging algorithm for dynamic environment[C]. Proceedings of IEEE Conference on Evolutionary Computation, Canada, 2006:4467-4473.

[6]Mishra S. A hybrid least square-fuzzy bacteria foraging strategy for harmonic estimation[J].IEEE Transactions on Evolutionary Computation, 2005, 9(1): 61-73.

[7]Das S, Biswas A, Dasgupta S,et al.. Bacterial foraging optimization algorithm: theoretical foundations, analysis,and applications[J]. FoundationsofComputational Intelligence, 2009, 203: 23-55.

[8]Chen H N, Zhu Y L, and Hu K Y. Adaptive bacterial foraging optimization[J].Abstract and Applied Analysis, 2011, 2011(1):1-27.

[9]Tang W J and Wu Q H. A bacterial swarming algorithm for global optimization[C]. Proceedings of IEEE Conference on Evolutionary Computation, Singapore, 2007: 1207-1212.

[10]Abraham A, Biswas A, Dasqupta S,et al.. Analysis of reproduction operator in bacterial foraging optimization algorithm[C]. Proceedings of IEEE Congress on Evolutionary Computation, Hong Kong, 2008: 1476-1483.

[11]Biswas A, Dasgupta S, Das S,et al.. A synergy of differential evolution and bacterial foraging algorithm for global optimization[J].Neural Network World, 2007, 17(6): 607-626.

[12]劉小龍, 李榮鈞, 楊萍. 基于高斯分布估計的細菌覓食優化算法[J]. 控制與決策, 2011, 26(8): 1233-1238.

Liu Xiao-long, Li Rong-jun, and Yang Ping. Bacterial foraging optimization algorithm based on estimation of distribution[J].Control and Decision, 2011, 26(8): 1233-1238.

[13]劉小龍, 趙奎領. 基于免疫算法的細菌覓食優化算法[J]. 計算機應用, 2012, 32(3): 634-637, 653.

Liu Xiao-long and Zhao Kui-ling. Bacterial foraging optimization algorithm based on immune algorithm[J].Journal of Computer Applications, 2012, 32(3): 634-637, 653.

[14]王雪松, 程玉虎, 郝名林. 基于細菌覓食行為的分布估計算法在預測控制中的應用[J]. 電子學報, 2010, 38(2): 333-339.

Wang Xue-song, Cheng Yu-hu, and Hao Ming-lin. Estimation of distribution algorithm based on bacterial foraging and its application in predictive control[J].Acta Electronic Sinica,2010, 38(2): 333-339.

[15]Sun J, Feng B, and Xu W B. Particle swarm optimization with particles having quantum behavior[C].Proceedings of the IEEE Congress on Evolutionary Computation, USA,2004: 325-331.

[16]周雅蘭. 細菌覓食優化算法的研究與應用[J]. 計算機工程與應用, 2010, 46(20): 16-21.

Zhou Ya-lan. Research and application on bacteria foraging optimization algorithm[J].Computer Engineering and Applications, 2010, 46(20): 16-21.

[17]Clerc M and Kennedy J. The particle swarm: explosion,stability, and convergence in a multi-dimensional complex space[J].IEEE Transactions on Evolutionary Computation,2002, 6(1): 58-73.

[18]Solis F J and Wets R J B. Minimization by random search techniques[J].Mathematics of Operations Research, 1981,6(1): 19-30.

[19]Sun J, Fang W, Palade V,et al.. Quantum-behaved particle swarm optimization with gaussian distributed local attractor point[J].Applied Mathematics and Computation, 2011, 218(7):3763-3775.

[20]方偉, 孫俊, 謝振平, 等. 量子粒子群優化算法的收斂性分析及控制參數研究[J]. 物理學報, 2010, 59(6): 3686-3694.

Fang Wei, Sun Jun, Xie Zhen-ping,et al.. Convergence analysis of quantum-behaved particle swarm optimization algorithm and study on its control parameter[J].Acta Physica Sinica, 2010, 59(6): 3686-3694.