一種改進的細菌覓食優化算法

劉　珍,　孫京誥

(華東理工大學信息科學與工程學院,上海 200237)

一種改進的細菌覓食優化算法

劉珍,孫京誥

(華東理工大學信息科學與工程學院,上海 200237)

摘要：針對細菌覓食優化算法存在收斂速度慢、尋優精度低、易陷入局部最優等缺點,提出了一種改進的細菌覓食優化算法。改進原有固定步長的游動方式,引入自適應步長調整策略,提出了基于非線性遞減的余弦自適應步長;改進細菌位置的更新方式,借鑒人工蜂群的方法,采用混合的更新方式;改進優勝劣汰的選擇標準,保留最優個體,對復制后的父代個體引入雜交算子;改進遷徙方式,提出種群進化因子,防止進化停滯不前。將本文算法用于經典函數以及PID參數整定測試,仿真實驗結果驗證了該算法的有效性。

關鍵詞：細菌覓食優化算法; 自適應步長; 位置更新方式; 雜交算子; 種群進化因子

20世紀40年代以來,實際工程問題呈現出越來越多的復雜性,包括多極值、強非線性、多約束性和高維度等。傳統的優化方法已經不能解決諸多實際生產、生活中所面臨的復雜問題,智能優化算法應運而生。細菌覓食優化算法[1]作為一種新型的智能優化算法具有良好的全局優化能力、魯棒性強以及算法簡單等優點,受到了不同領域的關注[2-4]。

針對步長固定的問題,Chen等[5]提出了自適應搜索的細菌覓食優化算法;劉小龍等[6]提出了靈敏度的概念,對細菌的游動步長加以調節;Niu等[7-8]在驗證了步長大小的選取對全局收斂的快速性和全局最優解的獲得具有重要影響的基礎上,提出了線性遞減與指數非線性遞減的自適應步長;Mishra[9]提出了基于TS模糊機制來選取最優步長。算法融合方面,Biswas等[10]提出了一種基于差分算法和BFO(Bacterial Foraging Optimization)算法的混合全局優化算法,除此之外,與BFO算法相結合的算法還有粒子群算法[11]、遺傳算法[12]等。細菌覓食算法已經在電氣控制、模式識別、生產調度等方面得到廣泛應用。

本文針對細菌覓食優化算法存在收斂速度慢、尋優精度低、易陷入局部最優等缺點,改進了原有固定步長的前進方式,引入了自適應步長調整策略;位置更新方面,借鑒蜂群的方法,采用了混合的更新方式;改進了復制操作中優勝劣汰的選擇機制,并對復制后除當前最優父代外的其他父代細菌除引入了交叉算子;在遷徙操作中引入了種群進化因子,提出了一種改進的細菌覓食優化算法用于經典函數以及PID參數整定測試,仿真實驗結果驗證了該算法的有效性。

1細菌覓食優化算法

1.1概述

細菌覓食優化算法是根據大腸桿菌的覓食行為提出的。大腸桿菌根據所處的環境來改變身體表面鞭毛的旋轉方向,使其進行翻轉與游動,以期尋找到豐富的食物源,避開有毒區域。

同其他細菌一樣,經過一段時間后,根據優勝劣汰的自然選擇機制,部分大腸桿菌會淘汰、消亡,而存留下來的大腸桿菌會進行自我繁殖。此外,所處環境的變化,也會導致該區域細菌的消亡或增生。細菌游動和翻轉如圖1所示。

圖1　細菌游動和翻轉示意圖

通過模擬大腸桿菌的覓食行為,細菌覓食優化算法主要由趨向性操作、復制操作和遷徙操作組成。

1.2趨向性操作

趨向性操作是算法的核心操作,模擬的是大腸桿菌游動和翻轉的覓食行為。在環境較差的區域,細菌會翻轉得比較頻繁,而在環境較好的區域,細菌則會較多地游動。設細菌的種群規模為S,維度為n,則細菌i的位置用維度為n的向量表示。細菌覓食優化算法采用隨機初始化的方式初始化細菌的位置,初始化公式如下:

(1)

細菌i的趨向性操作可用式(2)、式(3)表示:

θ(i,j+1,k,l)=θ(i,j,k,l)+C(i)×φ(i,j)

(2)

(3)

其中:θ(i,j,k,l)表示細菌i在第j次趨向性操作、第k次復制操作和第l次遷徙操作時的位置,代表著所在優化區間內的一個可行解;C(i)為細菌i的趨向性步長;φ(i)為細菌i翻轉時在隨機方向上的一個隨機單位方向向量；Δ(i)為一個隨機向量。

1.3復制操作

根據優勝劣汰的自然機理,經過一段時間后,覓食能力弱的細菌最終會被淘汰,而覓食能力強的細菌則會繁衍后代,維持種群的規模。通過模擬此現象,提出了復制操作。

根據細菌覓食能力的強弱,選擇適當的評價指標函數,即適應度函數。通過對細菌i在趨向性操作中經歷的所有位置的適應度總和進行優劣排序,淘汰排在后面的占50%種群數的細菌。對于保留下來的細菌進行復制操作,各自生成的新個體與自身完全相同,具有相同的覓食能力、相同的位置。復制操作維持了種群規模的不變性。

1.4遷徙操作

當細菌所處周圍環境由于各種原因而突然發生變化或者逐漸改變時,可能會使此局部區域的細菌群集體死亡或集體遷移。通過模擬此現象,提出了遷徙操作。

遷徙操作以一定的概率發生,當細菌個體滿足遷徙發生的概率時,則這個細菌個體死亡,并在解空間的任意位置上隨機產生一個新的個體,這個細菌個體可能會擁有與原細菌不同的細菌覓食能力,有利于跳出局部最優解,促進全局最優解的尋找。設遷徙概率為Ped,種群規模為S,則細菌遷徙操作的流程如圖2所示。

設細菌執行趨向性操作、復制操作和遷徙操作的次數分別為Nc、Nre、Ned,用參數j、k、l分別對其計數,計數參數初始時設置為0,細菌覓食優化算法的流程圖如圖3所示。

2改進的細菌覓食算法

2.1概述

針對BFO算法收斂速度慢、易陷入局部最優的缺點,本文提出ABFO(Adaptive Bacterial Foraging Optimization)算法,從以下幾個方面改進BFO算法:

圖2　遷徙操作流程圖

圖3　細菌覓食優化算法流程圖

(1)改進趨向性操作。引入自適應策略,將固定步長改為自適應步長,隨著迭代次數的增加而減少,同時借鑒蜂群的方法,采用混合的位置更新方式對細菌進行趨化操作。

(2)改進復制操作。改進優勝劣汰的選擇機制,根據細菌當前適應度值的優劣進行排序,同時對于復制后的半數細菌,保留其中的精英個體,并對此半數細菌剩下的細菌引進交叉算子。

(3)改進遷徙操作。引入種群進化因子,防止種群進化不前,陷入局部最優。

2.2趨向性操作的改進

2.2.1趨向性步長的改進步長的選擇對于細菌覓食優化算法的性能有直接的影響,較大的步長易于全局搜索、尋找最優解,但精度不夠,可能會由于步長過大而錯失全局最優解;較小的步長可以提高精度,但全局收斂速度慢,同時也可能會陷入局部最優;固定的步長難以平衡全局搜索與局部搜索的要求。因此,為了配合BFO算法初期的全局搜索以及后期的局部搜索對步長的要求,本文提出了一種基于余弦的自適應步長,改進原有的固定步長。由于余弦函數在區間(0,π)的函數值是遞減的,步長C隨著迭代次數的增加而非線性遞減,使得算法在初期以較大的步長進行全局搜索,縮小最優解可能所在的區域,在算法后期則用較小的步長對縮小的區域范圍進行局域搜索,這一規律與覓食行為相符合?；谟嘞业淖赃m應步長C的計算公式如下:

(4)

其中:Cmin≤C≤Cmax;gen為當前迭代次數;genm為最大迭代次數。

2.2.2位置更新方式的改進算法的融合是算法改進的重要方向,細菌覓食算法和人工蜂群算法具有不同的產生新個體的方式,擁有不同的尋優效果,本文借鑒蜂群算法,采用混合的位置更新方式來更新細菌的位置。假設種群規模為S,其中的半數細菌s1按照原BFO算法中的方式更新位置,剩下的半數細菌s2則按照人工蜂群的更新方式更新位置。因此,菌群s1、s2的位置更新方式分別為式(5)、式(6)。θ(i,j+1,k,l)=θ(i,j,k,l)+C×φ(i,j)

(5)

θ(i,j+1,k,l)=

θ(i,j,k,l)+rand×(θ(i,j,k,l)-θ(r,j,k,l))

(6)

其中:r為在當前種群S中隨機選擇的一個不等于i的細菌,即r≠i,且r∈{1,2,…,S}。式(6)中θ(i,j,k,l)-θ(r,j,k,l)在本質上相當于步長向量,隨著迭代次數的增加,搜索空間縮小,θ(i,j,k,l)與θ(r,j,k,l)之間的距離減小,即步長向量長度減小,步長的動態調整有利于算法精度的提高。采用不同的更新方式,使得細菌位置更新得多樣化,又不失去算法分析的合理性?；旌系母路绞接欣诜N群多樣化的保持以及最優解的獲得。

此外,為了防止進化停滯,加強細菌趨向性的有效性,引入相應的計數參數trail，用于記錄個體位置連續未得到改善的次數,當細菌對應的trail達到一定的數值時,根據迭代次數,對該細菌的位置進行重新初始化或擾動。

2.3復制操作的改進

原有的BFO算法是對細菌趨向性操作經過的所有位置的適應度值的和進行優劣排序,由于細菌位置是在趨向性操作下逐步加強改善的,是細菌所經歷的歷史最優值,細菌的當前位置更能反映細菌的覓食能力,而且采用細菌的當前位置能夠降低算法的復雜度,因此,本文采用當前細菌位置的適應度值進行優劣排序,對優秀的半數細菌S/2進行復制,復制后的子代替換原細菌種群中較差的S/2細菌。

由于復制后的新種群規模為S的細菌群中,每個父代都有一個與其相同的子代,降低了種群的多樣性。因此,為了增加種群的多樣性以及防止最優個體的丟失,本文對父代個體(除了最優父代外)引入了雜交算子,與最優個體進行雜交,雜交公式如下:

(7)

2.4遷徙操作的改進

遷徙操作的存在有利于跳出局部最優解,尋找全局最優解。BFO算法按照給定的固定概率進行遷徙,沒有考慮種群的進化情況。根據種群的進化情況進行遷徙,有利于算法尋優的有效性。當種群進化程度較快時,種群群體處在快而有效的尋優狀態,以較低的遷徙概率進行遷徙,可以保留當前有利的位置信息;當種群進化程度較慢時,種群群體很大程度上陷入了局部最優,需要以較高的遷徙概率進行遷徙,跳出局部最優解,防止種群進化不前。本文改進了原有BFO算法中的遷徙操作,引入了種群進化因子f。

(8)

其中:fgen代表第gen代的最優適應度值;rand作用是防止分母為0。當f=0時,進化停滯;當01時,進化加速。本文算法用(1-f)替代原算法中的Ped,當滿足遷徙發生的條件時,讓種群中的部分細菌進行遷徙。

2.5ABFO算法流程

(1) 初始化參數,生成初始種群

(2) Forl=ltoNedDo

(3)Fork=ktoNreDo

(4) Forj=jtoNcDo

(5)Fori=itos1Do

(6) 自適應步長,細菌位置原更新方式

(7)End For

(8)Fori=s1+1 toSDo

(9) 自適應步長,細菌位置新更新方式

(10)End For

(11) End For

(12) 改進的復制操作

(13) End For

(14) 基于種群進化因子的遷徙操作

(15)End For

3仿真實驗與分析

3.1函數測試

本文采用表1所示的8個標準測試函數對BFO、DBFO[13]以及ABFO的性能分別進行測試對比。這些函數的全局最優解采用常規的方法通常較難獲得,而且隨著函數維數的升高,優化難度會急劇增加。

表1　標準測試函數

本文算法的參數選取參考文獻[13],將測試函數的維度設為30,細菌種群規模為40,固定步長為0.01×區間長度,趨化次數Nc=40,游動次數Ns=5,復制次數Nre=5,遷徙次數Ned=5,遷徙概率Ped=0.25。BFO、DBFO和ABFO 3種算法在每個測試函數上的運行次數均為20次。測試結果的精度達到10-15等級時,以0代替,測試結果見表2。BFO、DBFO以及ABFO 3種算法的運行時間經四舍五入保留一位小數點后的數據如表3所示。其中,DBFO算法在表中的實驗結果均參照文獻[13],由于原文獻并未給出標準差,因此,本文在此項中用*號表示。

表2　函數測試運行結果

由表2可以看出,在8個標準測試函數中,除了ABFO與DBFO算法對于測試函數f2所求得的最優解持平之外,ABFO算法所求得的最優解均優于DBFO算法和BFO 算法,并且在易陷入早熟收斂的Rosenbrock函數f5、較難獲得全局最優解的Rastrigrin函數f6和Acklley函數f7中,ABFO算法的最優解精度達到了0,提高了尋優精度和尋找全局最優解的能力,突破了BFO算法易陷入局部最優解的缺點。但是由最差解和平均解可知,ABFO算法尋優的整體水平還有待提高。

由表3可知,ABFO算法的時間復雜度最低、收斂速度最快。在DBFO算法中,由于雙種群的存在,其種群規模為80,若將其時間折半,考慮到趨向性操作中最大游動步數的存在,可以認為DBFO算法運行所需要的時間與BFO算法運行所需要的時間相差無幾,具有相同的時間復雜度。

算法的收斂性是檢測算法性能的重要指標,選取測試函數f7、f8加以測試。算法收斂性能曲線如圖4所示。測試結果表明,本文的改進算法針對測試函數f7、f8最優解的尋優均能較快收斂,驗證了算法的收斂性能。

由表2、表3可知,本文改進的ABFO算法無論在尋優精度、運行速度,還是全局優化能力方面,均優于BFO算法和DBFO算法。圖4所示的收斂性能測試曲線也表明了該算法良好的收斂性能。函數測試的仿真實驗結果表明ABFO算法的有效性。

3.2應用實例

PID控制器是目前應用最為廣泛的控制器,PID控制器的參數整定是控制系統設計的核心內容。PID控制系統框圖如圖5所示。

表3　函數測試運行時間

圖4　算法收斂性能測試曲線

圖5　PID控制系統框圖

圖中，r(t)為系統輸入;e(t)為系統偏差,也為控制器輸入;u(t)為控制器輸出;y(t)為系統輸出。設PID控制的傳遞函數C(s)的表示形式為

(9)

其中,Kp、Ti、Td分別表示比例系數、積分時間常數和微分時間常數,三者都是可調的參數。PID控制器的輸出信號u(t)為

(10)

參照文獻[2],選取被控對象的傳遞函數G(s)為

(11)

本文將BFO算法、DBFO算法、ABFO算法分別用于PID參數整定。PID參數的優化整定就是在Kp、Ti、Td的可行域內尋找到一組控制參數,在滿足系統穩定的前提下,使選取的性能指標最優[14],使系統擁有較優的控制品質[15]。針對BFO算法、DBFO算法以及ABFO算法,本文選取常用的性能指標ITAE作為優化算法的適應度評價函數J,如式(12)所示。

(12)

BFO算法、DBFO算法、ABFO算法整定PID控制器的框圖如圖6所示。

圖6　BFO、DBFO、ABFO優化PID系統框圖

本文采用MATLAB軟件進行仿真。在simulink仿真實驗中,采用單位階躍函數作為系統輸入,設置simulink系統模塊仿真時間為10 s。優化算法通過調用simulink系統模塊,將尋優參數賦值給系統模塊,經過系統每次仿真得出結果,計算系統性能評價函數,根據得出的性能評價函數來指導算法的尋優,如此循環往復,直到達到算法的最大迭代次數,算法尋優結束,從而得出一組最優的PID參數。

在PID參數整定優化中,BFO算法、DBFO算法以及ABFO算法的基本參數設置為:種群規模S=20,維度n=3,Ns=5,Ped=0.25。根據算法參數對算法性能的影響,選取Nc、Nre、Ned3個參數為三因素,選用正交表L9(34)安排試驗。通過正交試驗,得出三參數在BFO、DBFO、ABFO中取值的優化方案分別為(15,4,4)、(15,2,6)、(15,4,6)。PID參數整定方法有很多,為了更好地測試ABFO算法的PID參數整定效果,本文還加入了工程整定方法中的衰減曲線法進行PID參數整定。

BFO、DBFO、ABFO算法分別運行10次所得的PID控制系統參數,以及衰減曲線法所得到的控制系統參數如表4所示,相應的單位階躍響應曲線如圖7所示。其中,J、Jm、Jw分別表示算法在運行的10次中所求得的適應度值的最優值、平均值和最差值;算法BFO、DBFO、ABFO中的Kp、Ti、Td為最優適應度J時相應的值,σ、tr、ts分別表示相應的超調量、上升時間、穩定時間。

表4　控制系統參數

圖7　階躍響應曲線

由表4及圖7可知,ABFO算法尋優所得的評價函數的適應度值最好,DBFO算法次之;衰減曲線法整定PID參數時,所得系統階躍響應的超調量最大,穩定時間最長,而ABFO算法的穩定時間最短,與DBFO算法相當;ABFO算法所得系統的階躍響應速度與DBFO、BFO算法相當,僅次于衰減曲線法的響應速度。因此,在PID整定方面,相比于BFO算法、DBFO算法以及衰減曲線法,ABFO算法對控制器參數整定的綜合控制效果最好,具有更好的控制品質。

為了進一步驗證ABFO算法的性能,本文在PID參數整定過程中加入了一個干擾,采用幅值為0.2的階躍信號作為擾動信號,并在20 s時開始對系統進行干擾。將BFO算法、DBFO算法、ABFO算法以及衰減曲線法用于具有擾動系統的PID參數整定,算法尋優所得的最優解及相應的性能指標如表5所示,其相應的系統階躍響應曲線如圖8所示。

表5　基于擾動的控制系統參數

由表5及圖8可知,ABFO算法求得的適應度值性能指標的最優值和平均值均最小,DBFO算法次之,BFO算法最差;當系統具有擾動時,用衰減曲線法求解的PID參數整定效果依然最差;ABFO算法、DBFO算法、BFO算法相對應系統的階躍響應曲線相差無幾。因此,對具有輸出擾動的系統進行PID參數整定時,ABFO算法依然具有最好的綜合控制性能。

圖8　基于擾動的階躍響應曲線

4結論

本文通過對BFO算法的介紹與分析,針對其收斂速度慢、尋優精度低以及易陷入局部最優解的特點,改進了BFO算法。在趨向性操作中,將固定步長改為隨迭代次數增加而逐漸減少的自適應步長,提高了算法的局部搜索能力,同時改進了細菌位置的更新方式,采用了混合的位置更新方式,有利于種群的多樣性的保持;在復制操作中,按照細菌當前位置的適應度值排序,替代原BFO算法趨向性操作中所有的適應度和排序,減少了算法的復雜度,并更加準確地反映了細菌覓食的能力,同時在保留最優個體的情況下,對復制后的父代引入雜交算子,提高了種群的多樣性;在遷徙操作中,引入種群進化因子,替代固定的遷徙概率,有利于細菌尋優的有效性,防止種群進化停滯不前。函數仿真測試以及PID參數整定的仿真實驗結果表明,本文提出的改進的細菌覓食優化算法(ABFO算法),提高了尋優精度、收斂速度以及全局尋優的能力。

參考文獻：

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

[2]呂振,沈建國.改進的細菌覓食優化算法[J].計算機系統應用,2014,23(5):182-187.

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

[4]李娜,雷秀娟.細菌覓食優化算法的研究進展[J].計算機技術與發展,2014,24(8):39-44.

[5]CHEN Hanning,ZHU Yunlong,HU Kunyuan.Self-adaptation in bacterial foraging optimization algorithm[C]//2008 3th International Conference on Intelligent System and Knowledge Engineering(ISKE 2008).Xiamen:IEEE,2008:1026-1031.

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

[7]NIU Ben,FAN Yan,ZHAO Pei.A novel bacterial foraging optimizer with linear decreasing Chemotaxis step[C]//2nd International Workshop on Intelligent Systems and Applications (ISA).Wuhan:IEEE,2010:1-4.

[8]NIU Ben,WANG Jingwen,WANG Hong.Bacterial-inspired algorithms for solving constrained optimization problems[J].Neurocomputing,2015,148(9):54-62.

[9]MISHRA S.A hybrid least square-fuzzy bacterial foraging strategy for harmonic estimation[J].IEEE Transaction on Evolutionary Computation,2005,9(1):6l-73.

[10]BISWAS A,DASGUPTA S,DAS S,etal.A synergy of differential evolution and bacterial foraging algorithm for global optimization[J].Neural Network World,2007,17(6):607-626.

[11]田亞菲,張范勇,閻石.基于粒子群優化的細菌覓食優化算法[J].控制工程,2012,19(6):993-996.

[12]KIM D H,ABRAHAM A,CHO J H.A hybrid genetic algorithm and bacterial foraging approach for global optimization[J].Information Sciences,2007,177(18):3918-3937.

[13]姜建國,周佳薇,鄭迎春,等.一種雙菌群細菌覓食優化算法[J].深圳大學學報(理工版),2014,31(1):43-51.

[14]湛鋒,魏星,郭建全,等.基于改進粒子群優化算法的PID參數整定[J].繼電器,2005,33(19):23-27.

[15]任子武,傘冶,陳俊風.改進PSO算法及在PID參數整定中應用研究[J].系統仿真學報,2006,18(10):2870-2873.

An Improved Bacterial Foraging Optimization Algorithm

LIU Zhen,SUN Jing-gao

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

Abstract:Aiming at the shortcomings in bacterial foraging optimization algorithm,e.g.,slower convergence speed,lower precision,easily falling into the local optimal solution,this paper proposes an improved bacterial foraging optimization algorithm.The fixed step adjusting is replaced by an adaptive step adjusting strategy via decreasing nonlinearly.By means of the idea of artificial bee colony,a mixed updating method on the bacterial position is introduced.The fittest selection criterion is improved and the crossover operator is introduced into the reproduced parents while retaining the best individual.The population evolution factor is proposed in order to prevent the stop of the evolution.Finally,the proposed algorithm is tested on the classic functions and the tuning of PID parameters,which shows their effectiveness.

Key words:bacterial foraging optimization algorithm; adaptive step;position update mode; crossover operator; population evolution factor

收稿日期：2015-03-19

作者簡介：劉珍(1989-),女,山東人,碩士生,研究方向為細菌覓食優化算法與控制理論。E-mail:liuzhen10704@163.com 通信聯系人：孫京誥,E-mail:sunjinggao@126.com

文章編號：1006-3080(2016)02-0225-08

DOI:10.14135/j.cnki.1006-3080.2016.02.012

中圖分類號：TP273

文獻標志碼：A