Nelder-Mead蜂群混合優(yōu)化算法及其收斂性分析與性能比較

1、Nelder-Mead 蜂群混合優(yōu)化算法及其收斂性分析與性能比較蜂群混合優(yōu)化算法及其收斂性分析與性能比較楊晨光楊晨光1, 陳杰陳杰2, 涂緒彥涂緒彥21 中國船舶工業(yè)集團公司船舶系統(tǒng)工程部，北京，100362 北京理工大學信息科學技術學院自動控制系，北京，100081關鍵詞關鍵詞：蜂群優(yōu)化算法，Nelder-Mead 方法，馬爾科夫鏈，基于 Nelder-Mead 方法的蜂群優(yōu)化算法，旅行商問題.摘要摘要蜂群優(yōu)化算法是一種新的群智能優(yōu)化算法，但具有收斂速度慢和計算過程復雜等不足。通過改變蜂群優(yōu)化算法的結構，利用 Nelder-Mead 方法改善其局部搜索能力，提出一種新的優(yōu)化算法?；隈R爾科夫

2、鏈理論，分析了所提出算法的收斂能力。通過解決旅行商問題進行仿真優(yōu)化，對所提出的算法與其他優(yōu)化算法進行比較，仿真結果表明改進的蜂群優(yōu)化算法具有更好的熟練能力和優(yōu)化性能。Keywords: Marriage in honey bees optimization (MBO), Nelder-Mead Method, Markov chain, Nelder-Mead Marriage in Honey Bees Optimization (NMMBO), Traveling Salesman Problem (TSP).AbstractMarriage in Honey Bees Optimizat

3、ion (MBO) is a new swarm-intelligence method, but it has the shortcomings of low speed and complex computation process. By changing the structure of MBO and utilizing the Nelder-Mead method to perform the local characteristic, we propose a new optimization algorithm. The global convergence character

4、istic of the proposed algorithm is proved by using the Markov Chain theory. And then some simulations are done on Traveling Salesman Problem (TSP) and several public evaluation functions. Comparing the proposed algorithm with MBO, Improved MBO (IMBO) and Genetic Algorithm (GA), simulation results sh

5、ow that the proposed algorithm has better convergence performance.1 引言引言群智能是一個新興熱門研究領域，重點關注群居動物的社會習性，抽象出模型，用于解決優(yōu)化問題。近年來，基于蜂群繁育過程所提出的蜂群優(yōu)化算法引起了注意。蜂群優(yōu)化算法（Marriage in Honey Bees Optimization -MBO）由 Jason Teo 和 Hussein A. Abbass1,2所提出，并由 Jason Teo、 Hussein A. Abbass 3 和 Omid Bozorg Haddad 4,5 等人進行了改進。本文將

6、進一步分析蜂群優(yōu)化算法的計算能力，并結合Nelder-Mead 方法對基本的蜂群優(yōu)化算法進行了改進，并利用馬爾科夫理論分析收斂性。下文中，將首先對蜂群優(yōu)化算法和馬爾科夫鏈理論進行介紹，然后對蜂群優(yōu)化算法進行分析，提出改進的蜂群優(yōu)化算法，并進行仿真比較。2 蜂群優(yōu)化算法蜂群優(yōu)化算法蜂群的行為特點不僅與遺傳能力有關，還與生態(tài)環(huán)境、生理環(huán)境及外界條件，以及這些因素的相互影響有關1,2，表現(xiàn)出很強的社會性行為，例如合作、交流等，已引起了學者們的廣泛興趣，近年來，有越來越多的研究圍繞此而展開。蜂群優(yōu)化算法就是其中的一項研究成果，它模擬了蜂群的繁育過程，包括以下主要步驟：多個雄蜂通過競爭獲得與蜂后交配的機

7、會；強壯的雄蜂將會有較大的概率勝出；未能交配的雄蜂將被蜂群淘汰；幼蜂將由工蜂來照顧。3 馬爾科夫鏈理論馬爾科夫鏈理論馬爾可夫鏈是一種無后效性的隨機過程，下一時刻的狀態(tài)只取決于當前時刻的狀態(tài)和轉移概率，而與過去時刻的狀態(tài)無關。馬爾可夫鏈被廣泛應用于分析收斂性問題，例如通過遺傳算法構造成一個馬爾可夫過程來研究遺傳算法的收斂性。定義定義 16 ：已知方陣ijn nAa ,1,:0,( 0);i jnaAAij如果則稱是正的* MERGEFORMAT (1) ,1,:0, ( 0);.i jnaAAij如果則稱為非負的 0 and :0,; mAmAA 如果則為正則的 0 and 1, :1,1nAi

8、naAijj 如果則是隨機的。定義定義 26 如果狀態(tài)空間是有限集，即，且SSn一步轉移概率與時間 無關，即 ptijt* ,ijiji jSu vpupvMERGEFORMAT (2)則稱這樣的馬爾可夫鏈為齊次有限馬爾可夫鏈。式中，為在時刻 ，由狀態(tài)到狀態(tài)的一步轉移概 ptijti Sj S率。定理定理 16齊次有限馬爾可夫鏈，其轉移概率矩陣為，如果()ijPp* MERGEFORMAT (3):0mmP則稱此馬爾可夫鏈是遍歷的，且極限分布是該齊次有限馬爾可夫鏈的平穩(wěn) lim, ,ijjtptp i jS分布。定理定理26 設是可約化隨機矩陣。是階隨機PCm正矩陣，則0,0RT* 1000l

9、imlim0kkkik ikkkiCCPPT RCTRMERGEFORMAT (4)4 基于基于 Nelder-Mead 方法的蜂群優(yōu)化算法方法的蜂群優(yōu)化算法 蜂群優(yōu)化算法優(yōu)于遺傳算法的重要特點是它在每次迭代都進行局部搜索。但是，MBO 選擇的是簡單、隨機的局部搜索算法，例如工蜂即啟發(fā)式搜索應用的是Random Walk、Random New1等算法，它們效率較低，性能較差，可以考慮應用較好的局部搜索算法代替它們扮演工蜂角色，從而增進算法性能。Nelder-Mead 方法是一種非線性優(yōu)化算法，由Nelder 和 Mead8提出。該方法使用直接搜索策略，其特點是對初始值并不敏感，不受限于目標函數

10、是否連續(xù)或可微。所以，我們將利用 Nelder-Mead 方法來替代基本蜂群優(yōu)化算法中的工蜂進行局部搜索。在作者的相關工作中，已對如何提高 MBO 的收斂速度進行了分析，并提出了一種改進算法（Improved Marriage in Honey Bees Optimization IMBO）。作為本文改進算法的基礎，這里簡單介紹一下。在 MBO 算法中，雄蜂與蜂后交配的概率是一個退火函數1，不僅計算過程復雜，而且用于計算的元素也需要由其他復雜的計算過程得來。所以，整個過程計算量很大。另一方面，我們發(fā)現(xiàn)，MBO 需要足夠的迭代次數來達到優(yōu)化結果，但是 MBO 中如能量、速度都不能保證這一點。隨著

11、迭代次數的增加，蜂后的飛行速度越小，鑒于蜂后與雄蜂適應度差異帶有隨機性，其交配概率，越到后期就越小。這會使得算法后期跳出局部極值的能力越來越小，很容易陷入局部極值點。所以，基于基本的 MBO 算法，我們采用如下方法簡化計算過程，即每步按比例隨機生成雄蜂，限制迭代條件，與有限數量的蜂后進行交配。這里，我們利用前述的兩個方面策略，對基本蜂群優(yōu)化算法進行改進，提出基于 Nelder-Mead 方法的蜂群優(yōu)化算法（algorithm of Nelder-Mead Marriage in Honey Bees Optimization -NMMBO）。NMMBO 計算過程如下：定義 Q: 蜂后數量D:

12、雄蜂數量M: 受精囊大小用啟發(fā)式算法隨機初始化工蜂隨機初始化蜂后基因類型應用 Nelder-Mead 方法改進蜂后基因類型 如果循環(huán)條件不被滿足時 (例如循環(huán)次數小于最大循環(huán)次數，或沒有得到滿意解)循環(huán)蜂后循環(huán)受精囊隨機產生雄蜂雄蜂和蜂后交叉變異，產生受精卵受精卵基因變異用 Nelder-Meade 作為工蜂進行啟發(fā)式搜索如果新生成的幼蜂優(yōu)于最差的蜂后， 用新生成的幼蜂替代最差的蜂后； 按照適應度刷新蜂后列表。圖 1: 基于 Nelder-Mead 方法的蜂群優(yōu)化算法計算流程在圖 1 中，NMMBO 比 MBO 算法的計算過程簡單，參數個數減少，避免了復雜的概率計算，從而提高了整體的計算速度。

13、在 NMMBO 中，本文定義了三個算子，即交叉算子、變異算子和啟發(fā)式算子。交叉因子和變異因子與遺傳算法中的定義相似，啟發(fā)式因子由本文定義。交叉算子：通過基因重組產生更優(yōu)的個體變異算子：以一定概率改變基因個體啟發(fā)式算子：對一些新個體進行優(yōu)化，進行局部搜索5 NMMBO 算法收斂性分析算法收斂性分析本節(jié)將利用馬爾科夫鏈鏈理論分析 NMMBO 算法的收斂性能。定義定義 3 NMMBO 的狀態(tài)空間集合是：* 12, ,0,1 ,1,NiXxt tttiNMERGEFORMAT (5)式中，是二進制位簇。12,Nt tt在集合上，定義適應度函數為，則適應度X f x集合為Y* ,Yy yf x x XM

14、ERGEFORMAT (6)則有：* MERGEFORMAT (7),0 xX y 定義，則有如下有序集合gY* 1212,ggyyyyyyMERGEFORMAT (8)交叉因子、變異因子、啟發(fā)因子會引起狀態(tài)空間中的狀態(tài)轉移，所以利用三個轉移矩陣、和來分CMH別表示它們的影響。定義NMMBO算法馬爾可夫鏈的轉移矩陣為，即Tr* MERGEFORMAT TrC M H(9)定理定理4 NMMBO是一個齊次有限馬爾可夫過程。證明：NMMBO算法所有群體集合是有限的，則由構成的12,Mxxx12,Mxxx馬爾可夫鏈是有限的。構成狀態(tài)空間集合中。如果，則在第X,ijX步，從狀態(tài)轉移到狀態(tài)的概率僅僅依賴

15、于狀態(tài)tij而與時間無關。所以，NMMBO 算法的馬爾可夫鏈i是齊次的。所以，NMMBO 是一個齊次有限馬爾可夫過程。定理定理5 ：NMMBO算法中，交叉概率轉移矩陣和啟發(fā)概率轉移矩陣都是隨機的。CH證明 對于交叉概率轉移矩陣，Cijn nCc* 1,1,:01,:1nijijji jncandinc MERGEFORMAT (10)所以是隨機的。C對于啟發(fā)概率轉移矩陣，Hijn nHh* 1,1,:01,:1nijijji jnhandinh MERGEFORMAT (11)所以是隨機的。H定理定理6 NMMBO算法中，變異概率轉移矩陣是M隨機且正的。證明 對于變異概率轉移矩陣， ijn n

16、Mm* 1,1,:01,:1nijijji jnmandinm MERGEFORMAT (12)所以，是隨機的。M因為變異過程對狀態(tài)向量的每個元素都有影響，所以很容易得到，將變異為的概率大于零，ixjx。所以，到的轉移概率為正。因此，,ijx xXixjx轉移概率矩陣是正的。定理定理7 NMMBO算法的馬爾可夫鏈是各態(tài)歷經Tr的，具有有限分布函數. lim0, ,ijjttrttri jX證明 依據定理 5、定理 6 和公式* MERGEFORMAT 錯誤！未找到引用源。錯誤！未找到引用源。，NMMBO算法的馬爾可夫鏈是正的。又根據定理 1，則定理 7 的結論即被證明。定義定義4 一代中的適應

17、度是這袋中所有個體中適應度最大的值，即 121,2,.,maxKiiKfx xxfx* MERGEFORMAT (13)定義，121212,iKKiKXx xxfx xxy x xxX是由* MERGEFORMAT 錯誤！未找到引用源。錯誤！未找到引用源。定iy義的，即在集合中，所有個體的適應度都等于。iXiy定義定義5 對于任意一個初始代，是最大的適X(0)1y應度值，即* 1limPr( ()1( )tf XytMERGEFORMAT (14)則這個算法具有全局收斂性。定理定理8 NMMBO收斂到全局最優(yōu)解。證明 定義* iTXX iNMERGEFORMAT (15)根據定義 4 和定理

18、4，是一個馬爾可夫鏈。定義TX* ()iiP XP iXXMERGEFORMAT (16)在(12)中定義。則、。iX()0iP X1()1niiP X定義為狀態(tài)到狀態(tài)的概率，則(,)ijP XXiXjX* 11(,),(,)jiNNijninjniinjjninjP XXxXxXP xxMERGEFORMAT (17)由于 NMMBO 在每次迭代都保留的最優(yōu)個體，所以1111(,)(,)(,)(,)nnnnP XXP XXPP XXP XX21221100(,)(,)0(,)(,)nnnP XXP XXP XXP XX* MERGEFORMAT (18)對于定理 3222121(,)0(,)

19、1,(,)(,)(,)nnnnP XXP XXCTRP XXP XXP XX* MERGEFORMAT (19)* 1000limlim0kkkikikkkiCCPPT RCTRMERGEFORMAT (20)對于定理 7 和定理 1，是穩(wěn)定的隨機矩陣，P所以，即1R* 211lim(,)1lim1lim(,)kkkknkP XXkRRP XX MERGEFORMAT (21)所以，在迭代步數足夠多的情況下， 的狀態(tài)都會轉TX到。1X6 仿真仿真為了驗證 NMMBO 的收斂性能，我們選擇與基本MBO、IMBO 和遺傳算法和不應用 Nelder-Mead 進行比較。這里應用復雜測試函數和 TSP

20、 問題作為優(yōu)化問題。6.1 應用評價函數應用評價函數評價函數 1: Sphere 模型 * 21( ),100iiif xxxMERGEFORMAT (22)01020304050607080012345678stepvalue GAMBOIMBONMMBO圖 2: NMMBO、IMBO、MBO 和 GA 對評價函數 1 的優(yōu)化結果評價函數 2: Schwefel 問題 1303011( ),10iiiiif sxxx* MERGEFORMAT (23)05010015020025002468101214161820stepvalue GAMBOIMBONMMBO圖 3: NMMBO、IMBO

21、、MBO 和 GA 對評價函數 2 的優(yōu)化結果評價函數 3: 廣義 Rosenbrock 函數22211( )100()(1),30iiiiif xxxxx* MERGEFORMAT (24)050100150200250020040060080010001200stepvalue GAMBOIMBONMMBO圖 4: NMMBO、IMBO、MBO 和 GA 對評價函數 3 的優(yōu)化結果評價函數 4: Step 函數3021( )0.5,100iiif xxx* MERGEFORMAT (25)020406080100120140160180010203040506070stepvalue GA

22、MBOIMBONMMBO圖 5: NMMBO、IMBO、MBO 和 GA 對評價函數 4 的優(yōu)化結果評價函數 5: 廣義 Rastrigin 函數21( )10 cos(2) 10 ,5.12iiiif xxxx* MERGEFORMAT (26)05010015020025005101520253035404550stepvalue GAMBOIMBONMMBO圖 6: NMMBO、IMBO、MBO 和 GA 對評價函數 5 的優(yōu)化結果評價函數 6: Ackley 函數2111( )cos() 1,6004000iiiiixf xxxi* MERGEFORMAT (27)0501001500

23、5101520253035stepvalue GAMBOIMBONMMBO圖 7: NMMBO、IMBO、MBO 和 GA 對評價函數 6 的優(yōu)化結果6.2 旅行商問題旅行商問題旅行商（Traveling Salesman Problem -TSP）問題是一個典型的 NP 問題，已經成為測試優(yōu)化算法有效性的標準。為了說明問題，下面將對比標準遺傳算法、原始蜂群算法和作者提出的改進蜂群優(yōu)化算法，采用TSPLIB 數據集。010020030040050060065707580859095100105110115stepdistance(km) GAMBOIMBONMMBO圖 8: NMMBO、IMB

24、O、MBO 和 GA 對 16 個城市的TSP 問題優(yōu)化結果01002003004005006007000.70.80.911.11.21.3x 105stepdistance(km) GAMBOIMBONMMBO圖 9: NMMBO、IMBO、MBO 和 GA 對 48 個城市的TSP 問題優(yōu)化結果6.3 分析分析從以上結果可以看出，無論是對于復雜的評價函數還是對于不同規(guī)模的 TSP 問題，NMMBO 的計算性能都很穩(wěn)定。具體而言，NMMBO 不僅收斂，而且收斂速度快，盡管有的評價函數具有多個局部最優(yōu)點，但是NMMBO 都能給出較好的優(yōu)化結果。NMMBO 的性能不僅優(yōu)于基本的蜂群優(yōu)化算法和遺

25、傳算法，也優(yōu)于不采用 Nelder-Mead 方法的 IMBO 算法。收斂速度快，尤其在初始階段，尤其對于初始條件差于其他三種算法的時候，NMMBO 仍能迅速收斂。對于 MBO 算法，從結果可見，有時 MBO 優(yōu)于遺傳算法，有時則很差，性能表現(xiàn)并不穩(wěn)定。由于其計算過程復雜和較差的局部搜索能力，所以 MBO 的性能并不是很好，有時長期維持在某個局部極值無法跳出。7 結論結論本文提出一種改進的蜂群優(yōu)化算法，即基于Nelder-Mead 方法的蜂群優(yōu)化算法?；痉淙簝?yōu)化算法參數多、計算量大，而NMMBO 算法不僅通過隨機生成一定數量的雄蜂與蜂后交配，避免了陷入局部極值，并且提高的計算速度；并且利用優(yōu)

26、化的局部搜索性能取得更好的優(yōu)化能力。基于馬爾科夫鏈理論，NMMBO 算法的收斂性也得到了證明。仿真結果也驗證了無論是優(yōu)化 TSP 問題還是復雜的評價函數，NMMBO 的優(yōu)化性能都優(yōu)于基本蜂群優(yōu)化算法和遺傳算法，并驗證了采用 Nelder-Mead 方法改進局部搜索能力的有效性。另一方面，NMMBO 算法還有很多可以深入研究的地方，作者將在今后的工作中繼續(xù)討論。參考文獻參考文獻1H.A. Abbass, “Marriage in Honey Bees Optimization (MBO): a haplometrosis polygynous swarming approach”, Congress on Evolutionary Computation, CEC2001, Korea, pp. 207-214, (2001).2H.A. Abbass, “A single queen single worker honey-bees approach to 3-SAT”, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO2001, USA, pp.807-814, (2001).3Jason Teo and H.A.