二稿混沌蜂群算法

-.z.混沌蜂群算法摘要:人工蜂群算法是一種新的模擬蜜蜂采蜜行為的元啟發(fā)式算法.本文提出一種新的ABC算法，利用混沌映射，提高算法的收斂速度，并防止ABC陷入局部最優(yōu).ABC算法需要使用的隨機(jī)數(shù)，通過(guò)隨機(jī)數(shù)發(fā)生器產(chǎn)生.該算法提出了七個(gè)新混沌映射，在基準(zhǔn)函數(shù)中分析了不同混沌映射的性能,提高了解的質(zhì)量.實(shí)驗(yàn)說(shuō)明，所提出的方法能夠有效提高解的質(zhì)量，既能防止陷入局部最優(yōu)，又能提高全局搜索能力.關(guān)鍵字:人工蜂群算法;全局?jǐn)?shù)值優(yōu)化;混沌;ChaoticbeecolonyalgorithmsAbstract:Artificialbeescolonyalgorithmisakindofnewsimulationbehaviorofmetaheuristicalgorithm.NewABCalgorithmisproposedinthispaper,usingthechaosmapping,improvestherateofconvergenceofthealgorithm,andpreventtheABCintoalocaloptimum.ABCalgorithmneedstousearandomnumber,generatedbyrandomnumbergenerator.Thealgorithmputsforwardsevennewchaosmappingofchaoticmappinginbenchmarkfunctionanalysisofdifferentperformance,improvesthequalityofknowledge.E*perimentalresultsshowthattheproposedmethodcanimprovethequalityofthesolution,whichcanpreventfallsintolocaloptimum,andcanimprovetheglobalsearchability.Keywords:Beecolonyalgorithm;Chaos;Globalnumericaloptimization引言優(yōu)化問(wèn)題可以用傳統(tǒng)算法建立模型來(lái)處理，需要幾個(gè)假設(shè)，但這些假設(shè)在許多情況下不容易驗(yàn)證.這些參數(shù)的假設(shè)〔舍入的變量、約束軟化等〕肯定會(huì)影響解的質(zhì)量.如果在優(yōu)化模型中需要建立整型或離散的決定變量，則顯然是不行的，也就是說(shuō)，傳統(tǒng)優(yōu)化算法不靈活，不能更好的解決優(yōu)化問(wèn)題.此外，首先傳統(tǒng)的求解策略通常取決于目標(biāo)函數(shù)和約束函數(shù)的類型〔線性，非線性等〕以及建模問(wèn)題中使用變量的類型〔整形，實(shí)型等〕.他們的效率也依賴于解空間的大小、用于建模的變量、約束的數(shù)量和解空間的構(gòu)造〔凸，凹等〕.也就是說(shuō)，他們不提供通用的解決方案。然而，大局部的優(yōu)化問(wèn)題，需要在它的規(guī)劃策略中制定變量、目標(biāo)函數(shù)和約束函數(shù)的類型.其次，原始優(yōu)化算法在解決大規(guī)模和高維非線性的問(wèn)題上，效率很低，迫使研究者尋找更靈活、適應(yīng)性更強(qiáng)、問(wèn)題和模型獨(dú)立的通用啟發(fā)式算法，這種通用的啟發(fā)式算法高效、靈活，它們可以視問(wèn)題的特定要求，來(lái)進(jìn)展調(diào)整修改.圖1所示的啟發(fā)式算法的分類.啟發(fā)式算法啟發(fā)式算法物理根底社會(huì)根底音樂(lè)根底生物學(xué)根底混合根底單點(diǎn)靜態(tài)目標(biāo)函數(shù)靜態(tài)鄰域不保存記憶多點(diǎn)動(dòng)態(tài)目標(biāo)函數(shù)動(dòng)態(tài)鄰域保存記憶圖1啟發(fā)式算法近年來(lái)，基于生物學(xué)的群體智能啟發(fā)式算法已成為許多學(xué)者的研究興趣之一.粒子群優(yōu)化算法、蟻群優(yōu)化算法和蜂群算法可以視為群體智能的幾個(gè)分支領(lǐng)域.最近提出的人工蜂群智能算法〔ABC〕受到了蜜蜂智能行為的啟發(fā)，同時(shí)被證明是全局?jǐn)?shù)值優(yōu)化問(wèn)題的更好的解決方法.在許多文獻(xiàn)中，混沌映射都具有確定性、遍歷性和隨機(jī)性.近年來(lái)，用混沌序列代替?zhèn)坞S機(jī)序列并應(yīng)用于相關(guān)程序中，在許多算法中已經(jīng)表現(xiàn)出一些有效的﹑好的結(jié)果，它們也可以與一些啟發(fā)式優(yōu)化算法一起使用來(lái)表示優(yōu)化變量.由于混沌序列的不可預(yù)測(cè)性，理論上講，混沌序列的選擇是合理的.在本文中，用混沌系統(tǒng)生成的不同序列代替ABC參數(shù)的隨機(jī)數(shù)，這是一個(gè)隨機(jī)選擇的過(guò)程.為此，我們已提出用不同的混沌映射代替?zhèn)坞S機(jī)序列的方法.通過(guò)這種方式，它可以加強(qiáng)全局優(yōu)化，防止陷入局部最優(yōu).但是，一般情況下，如果他們不遵循均勻分布，很難去估計(jì)哪些通過(guò)應(yīng)用統(tǒng)計(jì)測(cè)試的混數(shù)發(fā)生器更好.仿真結(jié)果說(shuō)明，應(yīng)用確定性混沌信號(hào)代替隨機(jī)序列是提高ABC性能的一種策略.本文的其余構(gòu)造，如下所示：第1節(jié)中回憶了ABC的相關(guān)內(nèi)容；第2章介紹了所提出的方法、混沌蜂群算法，簡(jiǎn)稱CBCAs；第3節(jié)介紹了用于提出的方法進(jìn)展比擬的測(cè)試函數(shù)；第4節(jié)，測(cè)試所提出的方法；第5節(jié)通過(guò)基準(zhǔn)問(wèn)題和模擬結(jié)果進(jìn)展比照，得出結(jié)論.1.人工蜂群算法在標(biāo)準(zhǔn)ABC算法中人工蜂群包括引領(lǐng)蜂,守望蜂和偵查蜂三個(gè)組成局部。每個(gè)引領(lǐng)蜂有一個(gè)確定的食物源〔每個(gè)食物源的位置代表優(yōu)化問(wèn)題的一個(gè)可行解〕，引領(lǐng)蜂的個(gè)數(shù)與食物源的個(gè)數(shù)相等，食物源的花蜜量是由相應(yīng)解的適應(yīng)度值來(lái)決定的。初始化之后，引領(lǐng)蜂根據(jù)記憶中的局部信息產(chǎn)生一個(gè)新的位置并檢查新位置的花蜜量。假設(shè)新位置的花蜜量比原來(lái)的多，則該蜜蜂更新記憶并記住新的位置。所有的引領(lǐng)蜂搜索完之后，將花蜜源信息通過(guò)在舞蹈區(qū)跳舞的方式傳遞給守望蜂。守望蜂根據(jù)引領(lǐng)蜂所找的食物源的花蜜量按概率選擇一只引領(lǐng)蜂并跟隨它，在這只引領(lǐng)蜂所在的食物源附近再重新搜索找到新的位置，并檢查新候選位置的花蜜量。假設(shè)新位置優(yōu)于原來(lái)的位置，則更新記憶并記住新的位置。算法的偽代碼見(jiàn)圖2.在初始化步驟后搜索的周期包括三個(gè)步驟：將引領(lǐng)蜂引到食物源并計(jì)算其花蜜量；將守望蜂引到食物來(lái)源并計(jì)算出花蜜量；確定偵查蜂，并把它們引到可能的食物源.一個(gè)食物源代表著優(yōu)化問(wèn)題的一個(gè)可行解.食物源的花蜜量對(duì)應(yīng)著可行解的質(zhì)量.每個(gè)引領(lǐng)蜂再在它當(dāng)前的食物源附近區(qū)域內(nèi)確定一個(gè)新的食物源，并估算它的花蜜量.如果新的花蜜量較高，蜜蜂更新記憶并記住新的食物源.守望蜂根據(jù)引領(lǐng)蜂所找的食物源的花蜜量，按概率選擇其中一只引領(lǐng)蜂，并跟隨它.蜂群的每個(gè)偵查蜂都被視為種群的探險(xiǎn)者，不能發(fā)表任何指導(dǎo)意見(jiàn)，只是負(fù)責(zé)尋找食物.他們負(fù)責(zé)尋找任何種類的食物源.也是由于它們的這種行為，偵查蜂一般是只能找到低本錢和低平均質(zhì)量的食品源.偶爾，偵查蜂也可以意外發(fā)現(xiàn)豐富的食物源.在人工蜂群中，偵查蜂能快速發(fā)現(xiàn)其中的可行解.在ABC中，引領(lǐng)蜂是選定歸類為偵察蜂的來(lái)源之一.選擇是由參數(shù)limit控制.如果預(yù)定次數(shù)的實(shí)驗(yàn)沒(méi)有提高食物源解的質(zhì)量，那食物源就會(huì)被發(fā)現(xiàn)它的引領(lǐng)蜂遺棄，而這個(gè)食物源的引領(lǐng)蜂會(huì)成為一名偵查蜂.釋放食物源的試驗(yàn)次數(shù)等于ABC重要控制參數(shù)的limit值.在強(qiáng)大的搜索過(guò)程中勘探和開(kāi)發(fā)過(guò)程是平衡的.在ABC算法種，當(dāng)守望蜂和引領(lǐng)蜂進(jìn)展搜索空間的開(kāi)發(fā)過(guò)程時(shí)，需要由偵查蜂來(lái)控制探索過(guò)程.這三個(gè)步驟不斷重復(fù)，直到滿足終止條件為止.圖3中所給的是ABC算法的流程圖.2.混沌蜂群算法在復(fù)雜模擬現(xiàn)象中，取樣、數(shù)值分析、決策，尤其是啟發(fā)式優(yōu)化算法需要長(zhǎng)時(shí)間和良好均勻性的隨機(jī)序列.此外，算法非常依賴它的初始條件和參數(shù).混沌的本質(zhì)是隨機(jī)的、不可預(yù)測(cè)的，它顯然也擁有元素的規(guī)律.在數(shù)學(xué)上，混沌是一個(gè)簡(jiǎn)單確實(shí)定性的隨機(jī)動(dòng)力系統(tǒng)，混沌系統(tǒng)可以看作是隨機(jī)性的來(lái)源.一種混沌映射是離散動(dòng)力系統(tǒng);;k=0,1,2,..在混沌狀態(tài)下運(yùn)行.混沌序列{*k：k=0，1，2，...｝可以作為隨機(jī)編號(hào)來(lái)生成擴(kuò)頻序列.混沌序列被證明可以簡(jiǎn)單快速的生成和存儲(chǔ)，但是對(duì)于長(zhǎng)序列的存儲(chǔ)沒(méi)有幫助.長(zhǎng)序列只是需要幾個(gè)函數(shù)〔混沌映射〕和幾個(gè)參數(shù)〔初始條件〕.此外，通過(guò)更改其初始條件可以簡(jiǎn)單生成很多不同的序列，并且這些序列都具有確定性和可再生性.最近，通過(guò)了混沌序列，而不是隨機(jī)序列，并且混沌序列在許多應(yīng)用程序中已經(jīng)顯現(xiàn)出一些有效的，好的結(jié)果如信息平安、非線性電路、DNA計(jì)算和圖像處理.由于混沌序列的不可預(yù)測(cè)性，理論上講，混沌序列的選擇是合理的.——初始化問(wèn)題參數(shù)—初始化算法參數(shù)—構(gòu)建初始引領(lǐng)蜂群解—評(píng)估每只蜜蜂的適應(yīng)值—i=0—Repeat—N=0—RepeatK為在i附近的一個(gè)解Y為[-1,1]范圍內(nèi)的一個(gè)隨機(jī)數(shù)字—產(chǎn)生新的解(食物源位置)Ui,j表示在*i,j附近的引領(lǐng)蜂，使用下面的公式—在*和UI中應(yīng)用鄰域選擇過(guò)程—一只引領(lǐng)蜂選取食物源依賴于一個(gè)相關(guān)于食物源的概率值Pi，由下面表達(dá)式計(jì)算:—守望蜂根據(jù)引領(lǐng)蜂所找的食物源的花蜜量按概率Pi對(duì)引領(lǐng)蜂*i來(lái)進(jìn)展評(píng)估For所有守望蜂Do為引領(lǐng)蜂在*i和Ui中適用貪婪的選擇過(guò)程Iffit(BestOnlooker)<fit(Employed)用守望蜂解代替引領(lǐng)蜂解EndIfEndDoIffit(BestFeasibleOnlooker)<fit(Best)找到最正確可行的守望蜂，替換最正確解決方案EndIfn=n+1Until(n=引領(lǐng)蜂數(shù)量)如果存在，確定被遺棄的解〔食物源〕，并用一個(gè)新的隨機(jī)產(chǎn)生的解*i取代，此處的引領(lǐng)蜂成為偵查蜂，用下面公式—偵查蜂只有一個(gè).如果偵查蜂的解比引領(lǐng)蜂的解更好，引領(lǐng)蜂的解將被替換為偵查蜂的解.否則其他引領(lǐng)蜂的解就會(huì)沒(méi)有任何變化地被轉(zhuǎn)到下一個(gè)周期—Until(i=最大迭代數(shù))圖2.ABC掃描的偽代碼確定到鄰居食品的位置放置的旁觀者蜂確定到鄰居食品的位置放置的旁觀者蜂為旁觀蜂選擇一個(gè)食物來(lái)源計(jì)算花蜜量初始化算法和問(wèn)題參數(shù)找到廢棄食物源記憶最正確食物源位置是計(jì)算花蜜量是否所有守望蜂被放于食物源處確定將引領(lǐng)蜂放置在新食物源位置找到用盡食物源的新位置是否滿足終止條件最終的食物位置否是確定將守望蜂放置在相鄰食物源位置不為守望蜂選擇一個(gè)食物源圖3.ABC算法的流程圖在新迭代的初始化步驟中，ABC隨機(jī)初始化和限制參數(shù)可以調(diào)整，但不能改變，這會(huì)影響算法性能的收斂速度.本文在ABC中提供了新的方法，引入具有遍歷性、非標(biāo)準(zhǔn)性和隨機(jī)屬性的混沌映射，來(lái)提高全局收斂性，防止陷入局部最優(yōu)問(wèn)題.在ABC中使用混沌序列，可以更容易擺脫局部最優(yōu)值，比通過(guò)原來(lái)的ABC的方法更有效.混沌映射所要選擇的(0，1)的混沌數(shù)字，已列于表1.新混沌ABC算法可以分類描述如下：2.1.混沌ABC1(CABC1)原始人工蜂群是由所選定的混沌映射循環(huán)迭代直到到達(dá)蜂群大小，如圖4所示.N是問(wèn)題維度；i是種群成員數(shù)目；j是的維度；*i,j是第i個(gè)成員的第j個(gè)維度表1所運(yùn)用混沌映射的定義名稱定義物流映射圈映射高斯映射Henon映射正弦的迭代器竇映射帳篷映射,，2.2.混沌ABC2(CABC2)在這種算法，如果代表食物源的一個(gè)解進(jìn)展limit/2測(cè)試后并沒(méi)有得到改良，那這個(gè)食物源會(huì)被它的引領(lǐng)蜂遺棄，且此引領(lǐng)蜂的偵查蜂開(kāi)場(chǎng)limit/2混沌迭代搜索.是第個(gè)成員的第j個(gè)維度，是對(duì)第個(gè)成員的第個(gè)維度通過(guò)亂數(shù)發(fā)生器生成的混沌數(shù).圖5描述了蜜蜂混沌搜索的偽代碼.CI為CI為混沌迭代的最大數(shù)目Repeat隨機(jī)初始化第一個(gè)混沌變量Repeat根據(jù)選定的映射生成混沌變量其中，CS為種群規(guī)模大小圖4，由CABC1偽代碼改變的原始ABC初始化用于搜索的第一個(gè)混沌變量初始化用于搜索的第一個(gè)混沌變量Repeat生成循環(huán)選定的映射的混沌變量映射回周圍半徑r原始值的范圍評(píng)價(jià)新的適應(yīng)值如果找到更好的方法，用更好的方法代替有關(guān)的維度，轉(zhuǎn)換到另一種維度圖5，蜜蜂混沌搜索的偽代碼2.3.混沌ABC3(CABC3)CABC1和CABC2相結(jié)合產(chǎn)生，也就是說(shuō)，為防止沒(méi)有獲得改良，由所選的混沌映射、混沌搜索迭代產(chǎn)生混沌映射ABC3.3.測(cè)試問(wèn)題以數(shù)學(xué)函數(shù)為根底的基準(zhǔn)函數(shù)可用于作為衡量和測(cè)試優(yōu)化方法性能的目標(biāo)函數(shù).這些基準(zhǔn)函數(shù)的本質(zhì)、復(fù)雜性和其他屬性可以很容易地從它們的定義中獲得，大多數(shù)基準(zhǔn)函數(shù)高難度水平的問(wèn)題也可通過(guò)設(shè)置參數(shù)來(lái)調(diào)節(jié).文獻(xiàn)中基準(zhǔn)問(wèn)題可用的一組標(biāo)準(zhǔn)中，有三個(gè)重要的函數(shù)，其中之一是單峰的，另外兩個(gè)是多峰的，它們用來(lái)測(cè)試所提出方法的效果.表2顯示了所選定的基準(zhǔn)函數(shù)在實(shí)驗(yàn)中所使用的的主要屬性.表2性能測(cè)試問(wèn)題，lb指示下限，ub指示上限，選擇指示最正確點(diǎn)函數(shù)編碼函數(shù)名定義屬性1Rosenbrock單峰2Griewangk多峰3Rastriqin多峰4.實(shí)驗(yàn)仿真與結(jié)果選定的三個(gè)基準(zhǔn)問(wèn)題通過(guò)模擬的ABC、CABC1和CABC2的算法解決.兩個(gè)標(biāo)準(zhǔn)用于終止算法的仿真：到達(dá)設(shè)置為常數(shù)的最大迭代次數(shù)，第二個(gè)標(biāo)準(zhǔn)是到達(dá)最小誤差.所有ABC被初始化都會(huì)做出公正的評(píng)價(jià)包括全局最優(yōu).為了配合他們的隨機(jī)屬性，該算法運(yùn)行了100次.在這個(gè)實(shí)驗(yàn)中，最大迭代數(shù)被設(shè)置為500，目標(biāo)不是找到全局的最優(yōu)值，而是找出算法的潛力最優(yōu)值.公式(2)定義了算法的成功率，已被用于比擬不同ABC算法.〔2〕是測(cè)試的次數(shù)，是在允許的最大迭代次數(shù)和條件中找到解的測(cè)試次數(shù).是所有測(cè)試的數(shù)目.是停頓算法的終止條件，直到超出所限制的終止條件，算法完畢.蜂群算法的種群規(guī)模選定為20.ABC的限制參數(shù)定為40.表3描述了ABC算法測(cè)試功能的成功率.Rosenbrock函數(shù)使用不同的混沌映射后，CABC算法的成功率如表4所示.CABC算法*種程度上表現(xiàn)出比ABC算法的測(cè)試函數(shù)更好的性能.尤其是，所有由算法CABC2和CABC3獲得的結(jié)果都比算法ABC的要好些.表3ABC算法的測(cè)試功能的成功率1.e-5013751.e-601360表4使用不同的混沌映射的算法的成功率物流映射1.e-50661.e-6044圈映射1.e-51541.e-6144高斯映射1.e-51671.e-6156Henon映射1.e-52451.e-6133正弦的迭代器1.e-50441.e-6023竇映射1.e-50651.e-6055帳篷映射1.e-50661.e-6045表5使用不同的混沌映射的算法的成功率物流映射1.e-51626251.e-6102322圈映射1.e-51418171.e-6141617高斯映射1.e-51826231.e-682321Henon映射1.e-51828281.e-6132126正弦的迭代器1.e-51925231.e-6141820竇映射1.e-51628271.e-681919帳篷映射1.e-51723231.e-6131516表6使用不同的混沌映射的算法的成功率物流映射1.e-56991891.e-6598569圈映射1.e-56890881.e-6618481高斯映射1.e-57695911.e-6588482Henon映射1.e-56589891.e-6468286正弦的迭代器1.e-57288891.e-6707986竇映射1.e-52692921.e-6258186帳篷映射1.e-57288871.e-6567979為Griewangk和Rastrigin函數(shù)使用不同的混沌映射的CABC算法的成功率分別如表5和表6所示.類似于測(cè)試函數(shù)Rosenbrock所獲得的結(jié)果，CABC算法在*種程度上表現(xiàn)出具有比ABC算法更好的性能.特別是，算法CABC2和CABC3的所有結(jié)果都比ABC算法的好.5.結(jié)論本文通過(guò)嵌入不同的混沌映射來(lái)適應(yīng)ABC算法的參數(shù).提出了三種新的混沌ABC算法，在基準(zhǔn)函數(shù)中分析了七個(gè)混沌映射.實(shí)驗(yàn)結(jié)果說(shuō)明這些方法提高了解的質(zhì)量，這也在一定程度上防止了陷入局部最優(yōu)，從而改良了全局搜索能力.對(duì)ABC算法的性能做了很大改善。文獻(xiàn)[1]李海生.一類基于蜜蜂采集模型的智能算法[J].計(jì)算機(jī)與現(xiàn)代化,2010,1:7-11.[2]胡中華;趙敏;基于人工蜂群算法的TSP仿真[J];理工大學(xué)學(xué)報(bào);2009年11期[3]張超群;*建國(guó);王翔;;蜂群算法研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2011年09期[4]王輝;改良的蜂群算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2011年11期[5]畢曉君，王艷嬌.改良人工蜂群算法[J];**工程大學(xué)學(xué)報(bào);2012，33〔1〕：117-123[6]龔純,王正林."精通MATLAB最優(yōu)化計(jì)算"[M].:電子工業(yè),2009.[7]KennedyJ,EberhartR.ParticleSwarmOptimization[C]//ProceedingsofIEEEInternationalConferenceonNeuralNetworks,Perth,Australia,1995:1942-1948.[8]ZhuGuopu,SamKwong.