稿混沌蜂群算法

1、混沌蜂群算法摘要 :人工蜂群算法是一種新的模擬蜜蜂采蜜行為的元啟發(fā)式算法 .本文提出一種新的 ABC 算法，利用混沌映射，提高算法的收斂速度，并防止 ABC 陷入局部最優(yōu) .ABC 算法需要使用 的隨機(jī)數(shù)，通過隨機(jī)數(shù)發(fā)生器產(chǎn)生 .該算法提出了七個新混沌映射，在基準(zhǔn)函數(shù)中分析了不 同混沌映射的性能 , 提高了解的質(zhì)量 .實(shí)驗(yàn)表明，所提出的方法能夠有效提高解的質(zhì)量，既能 防止陷入局部最優(yōu)，又能提高全局搜索能力 .關(guān)鍵字 : 人工蜂群算法 ;全局?jǐn)?shù)值優(yōu)化 ; 混沌 ;Chaotic bee colony algorithmsAbstract : Artificial bees colony algo

2、rithm is a kind of new simulation behavior of meta heuristic algorithm. New ABC algorithm is proposed in this paper, using the chaos mapping, improves the rate of convergence of the algorithm, and prevent the ABC into a local optimum. ABC algorithm needs to use a random number, generated by random n

3、umber generator. The algorithm puts forward seven new chaos mapping of chaotic mapping in benchmark function analysis of different performance, improves the quality of knowledge. Experimental results show that the proposed method can improve the quality of the solution, which can prevent falls into

4、local optimum, and can improve the global search ability.Keywords: Bee colony algorithm;Chaos;Global numerical optimization引言優(yōu)化問題可以用傳統(tǒng)算法建立模型來處理， 需要幾個假設(shè)， 但這些假設(shè)在許多情況下不 容易驗(yàn)證 . 這些參數(shù)的假設(shè)（舍入的變量、約束軟化等）肯定會影響解的質(zhì)量 . 如果在優(yōu)化模 型中需要建立整型或離散的決定變量， 那么顯然是不行的， 也就是說，傳統(tǒng)優(yōu)化算法不靈活， 不能更好的解決優(yōu)化問題 .此外，首先傳統(tǒng)的求解策略通常取決于目標(biāo)函數(shù)和約束函數(shù)的類型（線

5、性，非線性等） 以及建模問題中使用變量的類型（整形，實(shí)型等） . 他們的效率也依賴于解空間的大小、用 于建模的變量、約束的數(shù)量和解空間的結(jié)構(gòu)（凸，凹等） . 也就是說，他們不提供通用的解決方案。然而，大部分的優(yōu)化問題，需要在它的規(guī)劃策略中制定變量、目標(biāo)函數(shù)和約束函數(shù) 的類型 .其次，原始優(yōu)化算法在解決大規(guī)模和高維非線性的問題上，效率很低，迫使研究者 尋找更靈活、 適應(yīng)性更強(qiáng)、問題和模型獨(dú)立的通用啟發(fā)式算法， 這種通用的啟發(fā)式算法高效、 靈活，它們可以視問題的特定要求，來進(jìn)行調(diào)整修改 .圖 1所示的啟發(fā)式算法的分類 .圖 1 啟發(fā)式算法近年來，基于生物學(xué)的群體智能啟發(fā)式算法已成為許多學(xué)者的研究興

6、趣之一 . 粒子群優(yōu) 化算法、蟻群優(yōu)化算法和蜂群算法可以視為群體智能的幾個分支領(lǐng)域 . 最近提出的人工蜂群 智能算法（ ABC）受到了蜜蜂智能行為的啟發(fā)，同時被證明是全局?jǐn)?shù)值優(yōu)化問題的更好的解 決辦法.在許多文獻(xiàn)中，混沌映射都具有確定性、遍歷性和隨機(jī)性 . 近年來，用混沌序列代替 偽隨機(jī)序列并應(yīng)用于相關(guān)程序中， 在許多算法中已經(jīng)表現(xiàn)出一些有效的好的結(jié)果， 它們也 可以與一些啟發(fā)式優(yōu)化算法一起使用來表示優(yōu)化變量 . 由于混沌序列的不可預(yù)測性，理論上 講，混沌序列的選擇是合理的 .在本文中，用混沌系統(tǒng)生成的不同序列代替 ABC參數(shù)的隨機(jī)數(shù)， 這是一個隨機(jī)選擇的過 程. 為此，我們已提出用不同的混沌

7、映射代替?zhèn)坞S機(jī)序列的方法 .通過這種方式， 它可以加強(qiáng) 全局優(yōu)化，防止陷入局部最優(yōu) . 但是，一般情況下，如果他們不遵循均勻分布，很難去估計 哪些通過應(yīng)用統(tǒng)計測試的混數(shù)發(fā)生器更好 . 仿真結(jié)果表明，應(yīng)用確定性混沌信號代替隨機(jī)序 列是提高 ABC性能的一種策略 .本文的其余結(jié)構(gòu)，如下所示：第 1節(jié)中回顧了 ABC的相關(guān)內(nèi)容；第 2章介紹了所提出的方法、 混沌蜂群算法，簡稱 CBCA；s 第 3節(jié)介紹了用于提出的方法進(jìn)行比較的測試函數(shù)；第 4節(jié)，測 試所提出的方法；第 5節(jié)通過基準(zhǔn)問題和模擬結(jié)果進(jìn)行對比，得出結(jié)論 .1. 人工蜂群算法在標(biāo)準(zhǔn) ABC算法中人工蜂群包括引領(lǐng)蜂 , 守望蜂和偵查蜂三個組

8、成部分。每個引領(lǐng)蜂有 一個確定的食物源（每個食物源的位置代表優(yōu)化問題的一個可行解） ，引領(lǐng)蜂的個數(shù)與食物 源的個數(shù)相等，食物源的花蜜量是由相應(yīng)解的適應(yīng)度值來決定的。初始化之后，引領(lǐng)蜂根據(jù) 記憶中的局部信息產(chǎn)生一個新的位置并檢查新位置的花蜜量。若新位置的花蜜量比原來的 多，則該蜜蜂更新記憶并記住新的位置。所有的引領(lǐng)蜂搜索完之后，將花蜜源信息通過在舞 蹈區(qū)跳舞的方式傳遞給守望蜂。 守望蜂根據(jù)引領(lǐng)蜂所找的食物源的花蜜量按概率選擇一只引 領(lǐng)蜂并跟隨它， 在這只引領(lǐng)蜂所在的食物源附近再重新搜索找到新的位置， 并檢查新候選位 置的花蜜量。若新位置優(yōu)于原來的位置，則更新記憶并記住新的位置。算法的偽代碼見圖

9、2.在初始化步驟后搜索的周期包括三個步驟： 將引領(lǐng)蜂引到食物源并計算其花蜜量； 將守 望蜂引到食物來源并計算出花蜜量；確定偵查蜂，并把它們引到可能的食物源 . 一個食物源 代表著優(yōu)化問題的一個可行解 . 食物源的花蜜量對應(yīng)著可行解的質(zhì)量 . 每個引領(lǐng)蜂再在它當(dāng) 前的食物源附近區(qū)域內(nèi)確定一個新的食物源，并估算它的花蜜量. 如果新的花蜜量較高，蜜蜂更新記憶并記住新的食物源 . 守望蜂根據(jù)引領(lǐng)蜂所找的食物源的花蜜量，按概率選擇其中 一只引領(lǐng)蜂，并跟隨它 .蜂群的每個偵查蜂都被視為種群的探險者，不能發(fā)表任何指導(dǎo)意見，只是負(fù)責(zé)尋找食物 . 他們負(fù)責(zé)尋找任何種類的食物源 . 也是由于它們的這種行為，偵查蜂

10、一般是只能找到低成本 和低平均質(zhì)量的食品源 .偶爾，偵查蜂也可以意外發(fā)現(xiàn)豐富的食物源 . 在人工蜂群中， 偵查蜂 能快速發(fā)現(xiàn)其中的可行解 . 在 ABC中，引領(lǐng)蜂是選定歸類為偵察蜂的來源之一 . 選擇是由參數(shù) limit 控制. 如果預(yù)定次數(shù)的實(shí)驗(yàn)沒有提高食物源解的質(zhì)量，那食物源就會被發(fā)現(xiàn)它的引領(lǐng) 蜂遺棄，而這個食物源的引領(lǐng)蜂會成為一名偵查蜂 . 釋放食物源的試驗(yàn)次數(shù)等于 ABC 重要控 制參數(shù)的 limit 值. 在強(qiáng)大的搜索過程中勘探和開發(fā)過程是平衡的 . 在 ABC算法種，當(dāng)守望蜂 和引領(lǐng)蜂進(jìn)行搜索空間的開發(fā)過程時， 需要由偵查蜂來控制探索過程 . 這三個步驟不斷重復(fù)， 直到滿足終止條件

11、為止 .圖 3中所給的是 ABC算法的流程圖 .2. 混沌蜂群算法在復(fù)雜模擬現(xiàn)象中，取樣、數(shù)值分析、決策，尤其是啟發(fā)式優(yōu)化算法需要長時間和良好 均勻性的隨機(jī)序列 .此外，算法非常依賴它的初始條件和參數(shù) . 混沌的本質(zhì)是隨機(jī)的、 不可預(yù) 測的，它顯然也擁有元素的規(guī)律 . 在數(shù)學(xué)上，混沌是一個簡單的確定性的隨機(jī)動力系統(tǒng)，混 沌系統(tǒng)可以看作是隨機(jī)性的來源 .一種混沌映射是離散動力系統(tǒng)Xk 1 f（Xk）; 0 Xk 1; k = 0, 1, 2,. . 在混沌狀態(tài)下運(yùn)行 . 混沌序列 x k： k =0 ，1，2，. . . 可以作為隨機(jī)編號來生成擴(kuò)頻序列 . 混沌序列被證明可以簡單快速的生成和存儲

12、，但是對于長序列的存儲沒有幫助 . 長序列只是 需要幾個函數(shù)（混沌映射）和幾個參數(shù)（初始條件） . 此外，通過更改其初始條件可以簡單 生成很多不同的序列，并且這些序列都具有確定性和可再生性 .最近，通過了混沌序列，而不是隨機(jī)序列，并且混沌序列在許多應(yīng)用程序中已經(jīng)顯 現(xiàn)出一些有效的，好的結(jié)果如信息安全、非線性電路、 DNA計算和圖像處理 . 由于混沌序列 的不可預(yù)測性，理論上講，混沌序列的選擇是合理的 .初始化問題參數(shù)圖 2.ABC 掃描的偽代碼初始化算法參數(shù)構(gòu)建初始引領(lǐng)蜂群解評估每只蜜蜂的適應(yīng)值i=0 RepeatN=0RepeatK 為 在 i 附近的一個解Y 為-1,1 范圍內(nèi)的一個隨機(jī)數(shù)

13、字產(chǎn)生新的解 （ 食物源位置 ）Ui,j 表示在 Xi,j 附近的引領(lǐng)蜂， 使用下面的公式初始 化算 法和在新迭代的初始化步驟中， ABC隨機(jī)初始化和限制參數(shù)可以調(diào)整，但不能改變，這會影 響算法性能的收斂速度 . 本文在 ABC中提供了新的方法，引入具有遍歷性、非規(guī)范性和隨機(jī) 屬性的混沌映射，來提高全局收斂性，避免陷入局部最優(yōu)問題.在 ABC中使用混沌序列，可以更容易擺脫局部最優(yōu)值，比通過原來的 ABC的方法更有效 . 混沌映射所要選擇的 （0，1）的 混沌數(shù)字，已列于表 1. 新混沌 ABC算法可以分類描述如下：2.1. 混沌 ABC1(CABC1) 原始人工蜂群是由所選定的混沌映射循環(huán)迭代

14、直到達(dá)到蜂群大小，如圖4所示.N 是問題維度； i是種群成員數(shù)目； j是的維度； Xi,j 是第i 個成員的第 j 個維度表 1 所運(yùn)用混沌映射的定義定義名稱物流映射Xn 14Xn(1 X n圈映射Xn1X n 1.2高斯映射X n 10,Henon 映射X n 11 1.4Xn2正弦的迭代器X n 1sin( X n )竇映射Xn12.3(Xn )2sin(帳篷映射Xn1Xn /0.7)(0.5/2)sin(2X n ) mod(1)Xn)0.3Xn1Xn0,X n 0.710/3Xn(1 Xn) ，otherwise2.2. 混沌 ABC2(CABC2)在這種算法，如果代表食物源的一個解進(jìn)

15、行 limit/2 測試后并沒有得到改進(jìn)，那這個食物源會被它的引領(lǐng)蜂遺棄，且此引領(lǐng)蜂的偵查蜂開始 limit/2 混沌迭代搜索 . Xi,j是第 i 個成 員的第j個維度， Ci,j是對第 i個成員的第 j 個維度通過亂數(shù)發(fā)生器生成的混沌數(shù) .圖5描述了蜜蜂混沌搜索的偽代碼 .CI 為 混沌迭代的最大數(shù)目圖4，由 CABC偽1 代碼改變的原始 ABCRepeat 初始化用一第蜜個一蜂混個沌混變沌量變2.3R.e混pRe沌aetp A e B aCt 3(CABC3) 生成C 成混沌 沌搜索迭代產(chǎn)生混沌映射 ABC3.cmi, j 映射回周圍半徑iu,nj til (i CS)評價新 X i 的

16、適應(yīng)值，也量 的偽代碼就變是量說，c為m防止沒有獲得改進(jìn)，由所選的混沌映射 量 cmi ,jr 原始值的范圍其中， CS為種群規(guī)模大小3. 測試問題以數(shù)學(xué)函數(shù)為基礎(chǔ)的基準(zhǔn)函數(shù)可用于作為衡量和測試優(yōu)化方法性能的目標(biāo)函數(shù). 這些基準(zhǔn)函數(shù)的本質(zhì)、 復(fù)雜性和其他屬性可以很容易地從它們的定義中獲得， 大多數(shù)基準(zhǔn)函數(shù)高難 度水平的問題也可通過設(shè)置參數(shù)來調(diào)節(jié) . 文獻(xiàn)中基準(zhǔn)問題可用的一組標(biāo)準(zhǔn)中，有三個重要的 函數(shù)，其中之一是單峰的，另外兩個是多峰的，它們用來測試所提出方法的效果. 表2顯示了所選定的基準(zhǔn)函數(shù)在實(shí)驗(yàn)中所使用的的主要屬性 .表 2 性能測試問題， lb 指示下限， ub 指示上限，選擇指示最佳點(diǎn)

17、函數(shù)編碼 函數(shù)名性1 Rosenbrock2 Griewangk3 Rastriqin4. 實(shí)驗(yàn)仿真與結(jié)果定義f1(x)N100(X i 1 Xi12 2 2i2)2 (1 Xi )2單峰f 2(x)N(Xi2 / 4000)i1N X i cos( ) i 1 i多峰f3(x)N10 N(X i2i110 cos(2 X i )多峰選定的三個基準(zhǔn)問題通過模擬的 ABC、CABC1和 CABC2的算法解決 . 兩個標(biāo)準(zhǔn)用于終止算 法的仿真：達(dá)到設(shè)置為常數(shù)的最大迭代次數(shù)，第二個標(biāo)準(zhǔn)是達(dá)到最小誤差 .100NTsuccessfulNTall2)所有 ABC被初始化都會做出公正的評價包括全局最優(yōu) .

18、 為了配合他們的隨機(jī)屬性， 該算法 運(yùn)行了 100 次. 在這個實(shí)驗(yàn)中，最大迭代數(shù)被設(shè)置為 500，目標(biāo)不是找到全局的最優(yōu)值，而 是找出算法的潛力最優(yōu)值 . 公式 (2) 定義了算法的成功率，已被用于比較不同 ABC算法.NTsuccessful是測試的次數(shù)，是在允許的最大迭代次數(shù)和條件Qlevel 中找到解的測試次 數(shù). NTall 是所有測試的數(shù)目 . Qlevel是停止算法的終止條件，直到超出 Qlevel所限制的終止條件，算法結(jié)束.蜂群算法的種群規(guī)模選定為 20.ABC的限制參數(shù)定為 40. 表3描述了 ABC算法測試功能的成功率.Rosenbrock 函數(shù)使用不同的混沌映射后， CA

19、BC算法的成功率如表 4所示.CABC算法某種程度上表現(xiàn)出比 ABC算法的測試函數(shù)更好的性能 .尤其是，所有由算法 CABC和2 CABC獲3得的結(jié)果都比算法 ABC的要好些 .表 3 ABC 算法的測試功能的成功率1.e-5 013751.e-6 01360表 4Rosenbrock ( N2）使用不同的混沌映射的 CABC 算法的成功率物流映射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

20、.e-50661.e-6045表 5Griewangk (N10) 使用不同的混沌映射的 CABC 算法的成功率物流映射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-6 13 15 16表6 Rastrigin (N 10) 使用不同的混沌映射的 CABC算法的成功率物流映射918589691.e-

21、51.e-6圈映射69591.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所示. 類似于測試函數(shù) Rosenbrock所獲得的結(jié)果， CABC算法在某種程度上表現(xiàn)出具有比 ABC 算法更好的性能 .特別是，算法 CABC和2

22、 CABC的3 所有結(jié)果都比 ABC算法的好 .5. 結(jié)論本文通過嵌入不同的混沌映射來適應(yīng) ABC算法的參數(shù) . 提出了三種新的混沌 ABC算法，在 基準(zhǔn)函數(shù)中分析了七個混沌映射 . 實(shí)驗(yàn)結(jié)果表明這些方法提高了解的質(zhì)量，這也在一定程度 上避免了陷入局部最優(yōu)，從而改進(jìn)了全局搜索能力 . 對ABC算法的性能做了很大改善。文獻(xiàn)1 李海生 . 一類基于蜜蜂采集模型的智能算法 J. 計算機(jī)與現(xiàn)代化 , 2010,1: 7-11.2 胡中華 ; 趙敏 ; 基于人工蜂群算法的 TSP仿真J; 北京理工大學(xué)學(xué)報 ;2009 年 11期3 張超群 ; 鄭建國 ; 王翔; 蜂群算法研究綜述 J; 計算機(jī)應(yīng)用研究

23、;2011 年09期4 王輝; 改進(jìn)的蜂群算法 J; 計算機(jī)工程與設(shè)計 ;2011年11期5 畢曉君，王艷嬌. 改進(jìn)人工蜂群算法 J; 哈爾濱工程大學(xué)學(xué)報 ;2012 ，33（1）： 117-1236 龔純, 王正林.精通MATLAB最 優(yōu)化計算M. 北京:電子工業(yè)出版社 ,2009.7 Kennedy J,Eberhart R.Particle Swarm OptimizationC/Proceedings of IEEE International Conference onNeural Networks,Perth, Australia,1995:1942- 1948.8 Zhu Guopu,SamK wong.Gbest-guided artificialbee colony algorithm fornumerical function optimizationJ.Applied Mathematics andComputation,2010,217:3166-3173.9 Karaboga D,Basturk B.Artificial bee colony (ABC)optimization algori