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

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

2、夫鏈理論，分析了所提出算法的收斂能力。通過解決旅行商問題進(jìn)行仿真優(yōu)化，對(duì)所提出的算法與其他優(yōu)化算法進(jìn)行比較，仿真結(jié)果表明改進(jìn)的蜂群優(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 Optimiza

3、tion (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 characte

4、ristic 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 s

5、how that the proposed algorithm has better convergence performance.1 引言引言群智能是一個(gè)新興熱門研究領(lǐng)域，重點(diǎn)關(guān)注群居動(dòng)物的社會(huì)習(xí)性，抽象出模型，用于解決優(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 等人進(jìn)行了改進(jìn)。本文

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

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

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

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

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

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

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

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

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

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

16、n nMm* 1,1,:01,:1nijijji jnmandinm MERGEFORMAT (12)所以，是隨機(jī)的。M因?yàn)樽儺愡^程對(duì)狀態(tài)向量的每個(gè)元素都有影響，所以很容易得到，將變異為的概率大于零，ixjx。所以，到的轉(zhuǎn)移概率為正。因此，,ijx xXixjx轉(zhuǎn)移概率矩陣是正的。定理定理7 NMMBO算法的馬爾可夫鏈?zhǔn)歉鲬B(tài)歷經(jīng)Tr的，具有有限分布函數(shù). lim0, ,ijjttrttri jX證明 依據(jù)定理 5、定理 6 和公式* MERGEFORMAT 錯(cuò)誤！未找到引用源。錯(cuò)誤！未找到引用源。，NMMBO算法的馬爾可夫鏈?zhǔn)钦?。又根?jù)定理 1，則定理 7 的結(jié)論即被證明。定義定義4 一代中

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

18、定理 4，是一個(gè)馬爾可夫鏈。定義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)個(gè)體，所以1111(,)(,)(,)(,)nnnnP XXP XXPP XXP XX21221100(,)(,)0(,)(,)nnnP XXP XXP XXP XX* MERGEFORMAT (18)對(duì)于定理 3222121(,)0

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

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

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

22、e GAMBOIMBONMMBO圖 5: NMMBO、IMBO、MBO 和 GA 對(duì)評(píng)價(jià)函數(shù) 4 的優(yōu)化結(jié)果評(píng)價(jià)函數(shù) 5: 廣義 Rastrigin 函數(shù)21( )10 cos(2) 10 ,5.12iiiif xxxx* MERGEFORMAT (26)05010015020025005101520253035404550stepvalue GAMBOIMBONMMBO圖 6: NMMBO、IMBO、MBO 和 GA 對(duì)評(píng)價(jià)函數(shù) 5 的優(yōu)化結(jié)果評(píng)價(jià)函數(shù) 6: Ackley 函數(shù)2111( )cos() 1,6004000iiiiixf xxxi* MERGEFORMAT (27)505010

23、015005101520253035stepvalue GAMBOIMBONMMBO圖 7: NMMBO、IMBO、MBO 和 GA 對(duì)評(píng)價(jià)函數(shù) 6 的優(yōu)化結(jié)果6.2 旅行商問題旅行商問題旅行商（Traveling Salesman Problem -TSP）問題是一個(gè)典型的 NP 問題，已經(jīng)成為測(cè)試優(yōu)化算法有效性的標(biāo)準(zhǔn)。為了說明問題，下面將對(duì)比標(biāo)準(zhǔn)遺傳算法、原始蜂群算法和作者提出的改進(jìn)蜂群優(yōu)化算法，采用TSPLIB 數(shù)據(jù)集。010020030040050060065707580859095100105110115stepdistance(km) GAMBOIMBONMMBO圖 8: NMMB

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

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

26、并且利用優(yōu)化的局部搜索性能取得更好的優(yōu)化能力?；隈R爾科夫鏈理論，NMMBO 算法的收斂性也得到了證明。仿真結(jié)果也驗(yàn)證了無論是優(yōu)化 TSP 問題還是復(fù)雜的評(píng)價(jià)函數(shù)，NMMBO 的優(yōu)化性能都優(yōu)于基本蜂群優(yōu)化算法和遺傳算法，并驗(yàn)證了采用 Nelder-Mead 方法改進(jìn)局部搜索能力的有效性。另一方面，NMMBO 算法還有很多可以深入研究的地方，作者將在今后的工作中繼續(xù)討論。參考文獻(xiàn)參考文獻(xiàn)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.