基于細菌覓食與粒子群的改進混合算法

梁櫻馨，田浩杉

(蘭州交通大學 電子與信息工程學院，甘肅 蘭州 730070)

基于細菌覓食與粒子群的改進混合算法

梁櫻馨，田浩杉

(蘭州交通大學 電子與信息工程學院，甘肅 蘭州 730070)

針對粒子群優(yōu)化算法(PSO)在優(yōu)化過程中易陷入局部極值而產生“早熟”現(xiàn)象，文中提出一種基于細菌覓食與粒子群的改進混合算法。粒子群優(yōu)化算法與細菌覓食優(yōu)化算法的結合，增強了算法的全局搜索能力，使算法具有全局搜索能力強的優(yōu)點。選用Matlab進行仿真實驗，實驗結果進一步顯示了改進混合算法的優(yōu)化能力優(yōu)于基本PSO算法和基本BFO算法，收斂速度快，且具有較好的魯棒性。

粒子群優(yōu)化算法；細菌覓食優(yōu)化算法；改進混合算法

群體智能(Swarm Intelligence, SI)的概念最早由Beni、Hackwood和Wang在分子自動機系統(tǒng)中提出，通過揭示和模擬自然現(xiàn)象而產生的一系列群體智能優(yōu)化算法，該算法在模式識別、圖像處理、工程等眾多領域得到廣泛的應用[1]。粒子群算法(Particle Swarm Optimization，PSO)是一種智能優(yōu)化算法，最早由美國的Knnedy和Eberhart教授提出，其思想來源于人工生命和進化計算理論，是以模擬鳥群覓食行為為特征，以求解連續(xù)變量優(yōu)化問題為背景的一種優(yōu)化算法[2-3]。自PSO算法提出以來，由于它的計算快速性和算法本身的易實現(xiàn)性，引起了國際上相關領域眾多學者的廣泛關注和研究，經過短短幾年時間的發(fā)展，已廣泛應用于函數(shù)優(yōu)化、人工神經網絡訓練、模糊系統(tǒng)控制等許多領域。然而，在應用過程中由于PSO算法種群多樣性低，局部搜索能力差，搜索精度不夠高，易陷入局部極值，造成收斂速度慢，計算復雜度高，最終解不精確的問題。

本文提出一種基于細菌覓食優(yōu)化算法和PSO算法結合的混合算法。細菌覓食算法是基于大腸桿菌細菌覓食行為過程而提出的一種仿生隨機搜索算法。該算法由于搜索時方向的隨機變換，且細菌通過擇優(yōu)復制后以一定的概率遷徙到新的覓食區(qū)域中，增加了種群的多樣性，降低了收斂于局部最優(yōu)的概率，提高了找到最優(yōu)解的概率，局部搜索能力強。仿真結果表明，改進混合算法的收斂速度比基本PSO算法快、優(yōu)化效果更好，具有較好的魯棒性。

1 粒子群優(yōu)化算法

在粒子群優(yōu)化算法中，可以將每個優(yōu)化問題的潛在解看作是n維搜素空間上的一個點，稱為“粒子”或“微?！?，并假定其是沒有體重和重量的。所有的粒子均有一個被目標函數(shù)所決定的適應值，和一個決定其位置和飛行方向的速度，然后粒子們就以該速度追隨當前的最優(yōu)粒子在解空間中進行搜索，其中，粒子的飛行速度根據個體的飛行經驗和群體的飛行經驗進行動態(tài)調整。

假設Xi=(xi,1,xi,2,…,xi,n)是微粒i的當前位置，Vi=(vi,1,vi,2,…,vi,n)是微粒i的當前飛行速度，則粒子群優(yōu)化算法的進化方程如下

(1)

xi,j(t+1)=xi,j(t)+vi,j(t+1)

(2)

其中，w稱為慣性權重系數(shù)；t表示迭代次數(shù)；pi,j(t)表示微粒i迄今為止經歷的歷史最好位置；pg,j(t)是當前粒子群搜索到的最好位置；c1、c2為學習因子，分別稱為認知學習因子c1和社會學習因子c2，在0～2間取值。r1(t)和r2(t)是在[0，1]上的兩個相互獨立的隨機數(shù)。

式(1)的第1部分為粒子的慣性部分，代表粒子的慣性行為；第2部分為粒子的“認知”部分，表示粒子個體對于自身的學習；第3部分為粒子的“社會”部分，表示粒子間的信息共享與相互合作。

2 改進細菌覓食算法

細菌覓食優(yōu)化(Bacterial Foraging Optimization，BFO)算法是由K.M.Passion在2002年基于Ecolic大腸桿菌在人體腸道內吞噬食物覓食行為提出的一種新型仿生類優(yōu)化算法[4]。細菌覓食優(yōu)化算法是一種全局隨機搜索算法，具有并行搜索等優(yōu)點，該算法主要包括趨向、復制和遷徙3個步驟[5-7]。

2.1 趨向操作

趨向操作是細菌向食物源豐富區(qū)域聚集的一種行為，它包括細菌在覓食過程中的兩個基本運動：旋轉和游動。細菌先向某隨機方向游動一步，若該方向上的適應值比上一步所處位置的適應值低，則進行旋轉，朝另外一個隨機方向游動；反之，則沿該隨機方向向前移動[8]。

設細菌種群大小為S，細菌覓食算法中趨化行為具體描述如下

(3)

其中，θi(j,k,l)為細菌i在第j次趨向性操作、第k次復制操作和第l次遷徙操作后的位置；C(i)為細菌i的游動步長；Δ為隨機方向上的一個單位向量。

由于在標準BFO算法中采用固定步長C(i)，若將步長C(i)的值設置較大時，則細菌的收斂速度快，但易錯過最優(yōu)解或使算法陷入局部極小值而造成 “早熟”現(xiàn)象；反之，將步長C(i)的值設置較小時，雖然算法計算精度較高易找到最優(yōu)解但降低了計算效率，算法收斂速度降低[9-11]。因此，每個細菌的步長大小均起著主要作用，本文通過改進細菌的游動步長C(i)在提高算法計算精度的同時保證算法的收斂速度，使得算法跳出局部極小值，如式(4)所示

C′(i)=C(i)×e-t

(4)

其中，t表示迭代次數(shù)。

BFO算法起始階段，大部分細菌個體離全局最優(yōu)點較遠，為了增加算法的全局搜索能力，初始游動步長C′(i)的值較大；隨著細菌迭代次數(shù)的增加，較多的細菌個體離全局最優(yōu)越來越接近，且游動步長C′(i)的值也逐漸減小以便提高細菌個體的局部搜索能力，避免算法陷入局部極值而導致“早熟”現(xiàn)象的發(fā)生。

2.2 復制操作

一旦細菌生命周期結束，即到達臨界趨化次數(shù)，細菌將進行繁殖。細菌的繁殖過程遵循自然界“優(yōu)勝略汰，適者生存”原則。以趨化過程中各細菌適應值累加和為標準，較差的細菌死亡，較好的細菌分裂成兩個子細菌。子細菌將繼承母細菌生物特性，具有與母細菌相同的位置及步長[11-12]。

2.3 遷徙操作

實際環(huán)境中的細菌所生活的局部區(qū)域可能會發(fā)生逐漸變化，這樣可能會導致生活在這個局部區(qū)域的細菌種群被遷徙到新的區(qū)域中去，在BFO算法中模擬這種現(xiàn)象稱為遷徙性操作。

BFO算法中菌群經過若干代復制后，細菌以給定概率執(zhí)行遷徙操作，被隨機重新分配到尋優(yōu)區(qū)間。遷徙操作使得細菌可能更靠近全局最優(yōu)解，從而有利于跳出局部最優(yōu)解，進而尋找全局最優(yōu)解[13-16]。

3 改進細菌覓食與粒子群混合算法

粒子群算法與細菌覓食算法在優(yōu)化問題中均具有較好的優(yōu)化性能，也均存在各自的缺點。雖PSO算法參數(shù)設置少，全局搜索能力強，但在實際應用過程中算法缺乏粒子多樣性，在算法后期容易陷入局部最優(yōu)值；BFO算法中的趨向操作具有變換方向的搜索特性，可根據適應值的變化決定是否繼續(xù)沿該方向繼續(xù)搜索，提高了局部搜索能力，具有較高的搜索精度，但是BFO算法全局搜索能力不強，沒有對菌群最優(yōu)信息的記憶能力。本文將兩種算法相互結合并加以改進，取長補短，提高了算法的性能和效率，如式(5)所示。

式(7)中，去除了式(1)PSO算法速度更新公式中的個體認識部分，利用PSO算法對于群體信息共享的記憶功添加到改進的BFO算法位置更新方程中，更好的提高BFO算法的全局搜索能力和搜索效率。

算法主要實現(xiàn)步驟如下：

步驟1 初始化參數(shù)S，Ned，Nre，Nc，Ns，Ped，ω，c1，c2，r1，r2其中，S為細菌種群大??；Ned為最大遷徙代數(shù)；Nre為最大復制代數(shù)；Nc為最大趨向代數(shù)；Ns為游動的最大步長；Ped為遷徙概率；w為PSO算法中的慣性權重系數(shù)；c1和c2為PSO算法中0～2之間學習因子，r1和r2是PSO算法中[0，1]上兩個相互獨立的隨機數(shù)；

步驟2 隨機初始化菌群位置，并計算每個細菌的初始化適應度函數(shù)值J；

步驟3 遷徙循環(huán)l=l+1；

步驟4 復制循環(huán)k=k+1；

步驟5 趨化循環(huán)j=j+1。

(1)計算細菌適應度函數(shù)J(i,j,k,l)，記細菌i目前最優(yōu)適應值。Jlast=J(i,j,k,l)；

(2)旋轉：產生一個隨機向量Δ(i)∈Rn，其中每一個元素Δx(i)，(x=1,2,3,…,n)是分布在[-1，1]上的隨機數(shù)；

(3)游動：當mJlast，則保存當前細菌適應度值到Jlast。直至n=Ns時，計算下一個細菌i+1；

步驟6 若j

步驟8 若k

步驟9 每個細菌按照遷徙概率Ped被隨機分布到尋優(yōu)空間中。若l

圖1 改進混合算法流程圖

4 仿真實驗與分析

4.1 測試函數(shù)

為了驗證改進細菌覓食和粒子群混合算法的性能，選用仿真工具Matlab對其進行仿真模擬[17]，并將其與標準BFO、標準PSO算法進行比較。本文選取的測試函數(shù)如表1所示。

表1 測試函數(shù)

如表1所示，上述4個函數(shù)均是典型的測試函數(shù)，均可取到全局極小值0。基本細菌覓食算法可以優(yōu)化低維單峰函數(shù)，且得到較好的結果，但對于高維且多峰的函數(shù)問題，優(yōu)化結果并不理想。為了驗證改進后的混合算法對高維多峰函數(shù)的優(yōu)化性能，將4個函數(shù)的維度均設置為30。

4.2 參數(shù)設置

設在上述算法中細菌種群大小S=100，最大遷徙代數(shù)Ned=2，最大復制代數(shù)Nre=4，最大趨向代數(shù)Nc=10，游動的最大步長Ns=4，遷徙概率Ped=0.25，慣性權重系數(shù)w=0.75，社會學習因子c2=2 。

4.3 實驗結果

為了測試改進混合算法的性能，本文用改進混合算法分別對上述四個函數(shù)獨立運行30次尋優(yōu)，并與標準的BFO和標準的PFO算法的測試結果進行比較。實驗結果如表2所示，改進混合算法在函數(shù)f1、f2、f3、f4中運行其求解精度明顯優(yōu)于基本的BFO和PFO算法，表現(xiàn)出良好的性能。

此外，以 函數(shù)為例，對算法的收斂速度加以比較，比較結果如圖2所示，改進混合算法可增加算法的收斂速度，使算法在較少的迭代次數(shù)內就準確的收斂到全局最優(yōu)點，其表現(xiàn)優(yōu)于基本BFO和基本PSO算法。

表2 實驗結果

圖2 基于f3的3種算法收斂曲線圖

5 結束語

本文在基本細菌覓食算法和粒子群算法的基礎上，將兩種算法相互結合并加以改進。結果表明，改進的混合算法在收斂速度、計算精度及魯棒性方面均優(yōu)于基本算法，更能有效的避免算法陷入局部最優(yōu)值，同時表現(xiàn)出較好的全局搜索能力，適用于求解復雜優(yōu)化問題。

[1] 王枚,朱云龍,何小賢.群體智能研究綜述[J].計算機工程,2005,31(22):194-196.

[2] Kennedy J,Eberhart R C.Particle swarm optimization[C].UT,USA:Proceedings of IEEE International Conference on Neural Networks,1995.

[3] Eberhart R C,Kenndy J.A new optimizer using particle swarm theory[C].Japan: Proceeding of the 6th International Symposium on Micro Machine and Human Science,1995.

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

[5] Sasithradevi A, Singh N N. Synergy of adaptive bacterial foraging algorithm and Particle Swarm Optimization algorithm for image segmentation[C].MA,USA:International Conference on Circuit, Power and Computing Technologies (ICCPCT), IEEE, 2015.

[6] 章國勇,伍永剛,譚宇翔.一種具有量子行為的細菌覓食優(yōu)化算法[J].電子信息學報,2013,35(3):614-621.

[7] 肖文顯,褚鐳酈,王俊閣,等.自適應細菌覓食算法在優(yōu)化問題中的應用[J].安徽大學學報:自然科學版,2015(4):31-36.

[8] 姜建國,周佳薇,鄭迎春,等.一種自適應細菌覓食優(yōu)化算法[J].西安電子科技大學學報:自然科學版,2015,42(1):75-81.

[9] 胡愛策,任明侖,王浩.粒子群與細菌覓食相結合的案例聚類算法[J].計算機技術與發(fā)展,2013,23(10):44-47.

[10] 張學良,劉麗琴.智能優(yōu)化算法及其在機械工程中的應用[M].北京:國防工業(yè)出版社,2012.

[11] Dasgupta S, Das S, Abraham A, et al. Adaptive computational chemotaxis in bacterial foraging optimization: an analysis[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(4):919-941.

[12] Raj J S,Vasudevan V.Smart bacterial foraging optimization algorithm for scheduling in grid[J].European Journal of Scientific Research,2013,94(2):253-260.

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

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

[15] Kim D H,Abraham A,Cho J H.A hybrid genetic algorithm and bacterial foraging approach for gobal optimization[J].Information Sciences,2007,177(18):3918-3937.

[16] Kn L, Reddy B R, Kalavathi M S. Adaptive bacterial foraging oriented particle swarm optimization algorithm for solving optimal reactive power dispatch problem[J]. Chronexus Org, 2014,3(1)：1-6.

[17] 劉衛(wèi)國. Matlab程序設計與應用[M].2版.北京:高等教育出版社,2006.

Improved Hybrid Algorithm Based on Bacterial Foraging and Particle Swarm Optimization

LIANG Yingxin，TIAN Haoshan

(School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

Aiming at the phenomenon that the particle swarm optimization algorithm is easy to fall into the local extremum in the optimization process, an improved hybrid algorithm based on bacterial foraging and particle swarm optimization is proposed. Particle swarm optimization algorithm and the bacterial foraging optimization algorithm combined, the enhanced algorithm Alto global searching ability. The algorithm has the advantages of strong global search ability. Matlab simulation experiment, the results show that the improved hybrid algorithm is better than the basic PSO algorithm and the basic BFO algorithm, the convergence rate is fast, and has good robustness.

particle swarm optimization; bacterial foraging algorithm; hybrid algorithm

2016- 05- 10

梁櫻馨(1992-)，女，碩士研究生。研究方向：無線通信等。田浩杉(1992-)，男，碩士研究生。研究方向：無線通信。

10.16180/j.cnki.issn1007-7820.2017.04.020

TP301.6

A

1007-7820(2017)04-079-04