摘 要： 提出了一種新型的混合算法并命名為混合雜草蝙蝠算法（Hybridize Invasive Weed Optimization with Bat Algorithm，IWOBA），該算法在雜草算法的基礎(chǔ)上利用蝙蝠算法的回聲定位來解決每代種子逐步尋優(yōu)的問題。其原理是利用種群速度和位置的不斷更新，增加種群的多樣性，從而達到提高種群的全局收斂性。最后利用6個測試函數(shù)對該算法和標準雜草算法進行測試比較。仿真結(jié)果表明，IWOBA能夠有效克服原算法早熟、易陷入局部最優(yōu)的缺點，可加快算法收斂速度，具有良好的魯棒性。
關(guān)鍵詞： 雜草算法；蝙蝠算法；回聲定位
0 引言
入侵雜草算法（Invasive Weed Optimization，IWO）是由德黑蘭大學(xué)的Mehrabian等在2006年提出來的，它是一種模擬自然界雜草入侵的新型的數(shù)值優(yōu)化算法。該算法具有很強的魯棒性和適應(yīng)性，并且具有易于理解及實現(xiàn)等特點。近幾年來，在很多學(xué)者的研究下，雜草算法已經(jīng)成功應(yīng)用到圖像聚類、工程約束設(shè)計以及DNA編碼等眾多領(lǐng)域中[1-2]。
與其他智能算法相比較，標準雜草算法本身存在易于陷入局部最優(yōu)解和收斂精度不高的不足，這些不足都影響著算法的尋優(yōu)效果。因此，Hajimirsadeghi和Lucas提出了一種IWO和PSO融合的算法[3]，利用位置和速度的更新，使得算法避免了局部最優(yōu)解；Zhang Xuncai等人在標準IWO算法中引入了交叉算子，避免算法早熟，提高了全局最優(yōu)解[4]；張玉等人將遺傳算法中的選擇機制加入到標準IWO算法中，從而提高算法的多樣性[5]。
而本文是將蝙蝠算法中的回聲定位原理應(yīng)用到雜草算法中。通過回聲定位的特性，對種子個體的位置和速度進行不斷地更新，使其避免出現(xiàn)早熟和陷入局部最優(yōu)解的情況。且改進后的算法有更高的收斂精度。為了驗證改進后算法的有效性，本文通過6個常用的標準測試函數(shù)進行仿真實驗。
1 算法介紹
1.1 標準雜草優(yōu)化算法
在雜草優(yōu)化中，雜草通過繁殖產(chǎn)生種子，種子經(jīng)過空間的擴散、生長和競爭排除，從而得到適應(yīng)度較高的個體。其過程如下[6]：
?。?）初始化種群和參數(shù)：在D維數(shù)下產(chǎn)生N個可行解。
?。?）種群的生長繁殖：適應(yīng)度高的雜草會產(chǎn)生更多的子代，適應(yīng)度小的會慢慢消失。其計算公式：
式中，f是當(dāng)前種群適應(yīng)度；fmax和fmin分別是種群的最大和最小適應(yīng)度；smax和smin分別表示種群的最大規(guī)模和最小規(guī)模。
?。?）空間擴散：種群所產(chǎn)生的種子按平均值為0、標準差為δ的正態(tài)分布方式和步長Step∈[-δ，δ]分布在D維空間。在迭代初期標準差δ較大，隨著δ逐漸減小，迭代步長也在逐漸減小。其公式如下：
?。?）競爭排除：種群經(jīng)過多次繁殖之后，其種群規(guī)模達到最大數(shù)量Pmax時，將種群中的個體根據(jù)適應(yīng)度的大小進行排列，保留適應(yīng)度前Pmax個個體。適應(yīng)度差的個體將被淘汰。
1.2 蝙蝠算法
蝙蝠算法是受蝙蝠利用回聲定位來撲捉獵物和蔽障的啟發(fā)所提出的啟元式算法[7]。其原理是蝙蝠通過調(diào)整頻率的大小來不斷更新其位置和速度從而達到撲捉獵物的目的。其速度和位置更新公式為：
式中，?茁∈[0，1]是一個隨機變量，x*是當(dāng)前最佳位置。在波長不變的情況下，fmin=0，fmax=100；開始每只蝙蝠的頻率都是隨機分配的。在進行局部搜索時，每只蝙蝠的最新解都是從現(xiàn)有的解集中選擇的：
Xnew=Xold+εAt（6）
其中，ε∈[-1，1]是一個隨機數(shù)，A是平均響度；隨著迭代的進行，蝙蝠在捕捉時脈沖所發(fā)的速率和響度也在不斷更新。更新公式為：
其中，?琢和?酌一般都為0.9，隨著迭代的進行，脈沖響度 A趨向于0，脈沖速率r趨向于r；通過脈沖頻率速度和響度的不斷更新，使每個蝙蝠飛向最優(yōu)解。
1.3 雜草算法與蝙蝠算法的融合算法BAIWO
利用回聲定位的方法來更新雜草種群中個體的位置和速度[8]，具體實施步驟如下：
?。?）初始化BAIWO的參數(shù)，并隨機產(chǎn)生N0個個體的種群；
?。?）計算種群個體的適應(yīng)度函數(shù)值，確定當(dāng)前最優(yōu)值和最優(yōu)解；
（3）種群個體進行繁殖、生長：
?、賹ΨN群中每個種子利用式（3）~式（5）進行位置和速度更新；
?、诟鶕?jù)當(dāng)前解集隨機產(chǎn)生一個新解，并對該新解進行約束；
?、弁ㄟ^條件（rand<Ai & f（xi）<f（xi））來判斷是否接受該新解，以及是否更新ri和Ai；
（4）判斷種群是否達到最大規(guī)模，若未達到，轉(zhuǎn)到步驟（3），若達到，則繼續(xù)執(zhí)行；
?。?）對種群個體的適應(yīng)度值進行排序，保留前最大規(guī)模數(shù)的個體；
?。?）判斷是否達到最大迭代數(shù)，若否，轉(zhuǎn)到步驟（3），若是，輸出最優(yōu)值和最優(yōu)解。
從上述BAIWO算法的描述過程可知，BAIWO算法中的個體并不是在每次迭代過后直接進入下一代繁殖、生長，而是在種群中個體進行位置和速度更新后找出更優(yōu)的個體進行下一代繁殖。這樣，在迭代初期可以使得種群有著更強的全局搜索能力，到達迭代后期時，種群的尋優(yōu)步長在不斷變小，使得其具有更強的局部搜索能力。所以，BAIWO算法是將BA算法和IWO算法的各自優(yōu)點融合起來，使得改進后的算法在初期擁有很好的全局搜索能力，到達后期對局部搜索更精確。從而克服了IWO算法前期陷入局部搜索，以及后期收斂精度不高和速度慢等缺陷[9-10]。
1.4 BAIWO算法時間復(fù)雜度分析
根據(jù)上述的BAIWO算法的流程步驟來對該算法進行時間復(fù)雜度分析，設(shè)n為種群個體的數(shù)目，d為目標函數(shù)的維數(shù)，T為最大迭代次數(shù)。時間復(fù)雜度如表1所示。
2 BAIWO算法仿真實驗
2.1 實驗的初始參數(shù)設(shè)置
該算法的最優(yōu)參數(shù)設(shè)計：初始種群個體M0=30，最大種群個體Max=50，最大種子數(shù)為Smax=5，最小種子數(shù)為Smin=2，調(diào)和指數(shù)n=3，方差最大值和最小值分別為10和0.001，最大響度A=0.25，最大脈沖率R0=0.5，脈沖響度范圍為[0，2]，脈沖衰減系數(shù)為0.9；6個不同的測試函數(shù)[11]f1~f6最大迭代次數(shù)分別為500，500，200，500，500，500。函數(shù)參數(shù)如表2所示。
2.2 測試函數(shù)
在本實驗中選取了6個標準測試函數(shù)分別對標準雜草算法和改進后雜草算法進行性能測試。
（1）Sphere函數(shù)
上述6個基準測試函數(shù)中，除了f1是單峰函數(shù)以外，其余的都是多峰函數(shù)。圖1和圖2分別是應(yīng)用Rastrigin函數(shù)和Griewank函數(shù)對這兩種算法在不同迭代次數(shù)下測試所得到的收斂曲線。
2.3 仿真結(jié)果分析
通過以上函數(shù)優(yōu)化測試曲線可以看出，在迭代初期，BAIWO算法相較于標準IWO算法就具有較好的收斂效果，隨著迭代次數(shù)的增加，到達迭代后期時，BAIWO算法也能得到更好的收斂值。說明改進后的算法提高了標準IWO算法的性能。
實驗結(jié)果如表3所示，可以看出，無論在單峰還是多峰函數(shù)下，改進后算法結(jié)果都優(yōu)于IWO算法，在求解函數(shù)f1（x）~f6（x）時，改進后的算法都能獲得精確度較高的最優(yōu)值，以及較好的平均值和方差。而IWO算法在求解這6個函數(shù)時，起始值較大，收斂速度很慢，很容易陷入局部最優(yōu)解?？傮w而言，改進后的算法能夠獲得與理論值較近的值，以及很好的魯棒性。
3 結(jié)束語
本文針對雜草算法存在早熟現(xiàn)象和易陷入局部最優(yōu)解等缺點，提出了利用蝙蝠算法中回聲定位原理來對種群個體進行更新。從而使得種群前期擁有很好的全局收斂特性，后期可以使其避免陷入局部最優(yōu)。從仿真結(jié)果看出，BAIWO算法在很大程度上提高了雜草算法的收斂性和尋優(yōu)精度。然而，如何改變IWO算法中種群多樣性來提高它的收斂性是今后要進一步研究的方向。
參考文獻
[1] 張氫，陳丹丹，秦仙蓉，等.雜草算法收斂性分析及其在工程中的應(yīng)用[J].同濟大學(xué)學(xué)報（自然科學(xué)版），2010，38（11）：1689-1693.
[2] 彭斌，胡常安，趙榮珍.基于混合雜草算法的神經(jīng)網(wǎng)絡(luò)優(yōu)化策略[J].振動，測試與診斷，2013，33（4）：634-639.
[3] HAJIMIRSADEGHI H， LUCAS C.A hybrid IWO/PSO algorithm for fast and global optimization[J]. IEEE EUROCON 2009. Piscataway： IEEE， 2009：1964-1971.
[4] Zhang Xuncai，Niu Ying， Gui Gangzhao， et al. A modified invasive weed optimization with crossoever operation[C]. The 8th world Congress on Intelligent Control and Automation，2010：11-14.
[5] 張玉，蔣海榮，胡進，等.基于改進雜草優(yōu)化算法的DFCW參數(shù)估計[J].現(xiàn)代雷達，2013，35（7）：20-23.
[6] 賈盼龍，田學(xué)民.基于自適應(yīng)小生境的改進入侵性雜草優(yōu)化算法[J].上海電機學(xué)院學(xué)報，2012，15（4）：225-231.
[7] Yang Xinshe. Nature-inspired Metaheuristic Algorithms[M]. Beckington： Luniver Press， 2010.
[8] 李枝勇，馬良，張惠珍.蝙蝠算法收斂性分析[J].數(shù)學(xué)的實踐與認識，2013，43（12）：182-191.
[9] 肖輝輝，段艷明.基于DE算法改進的蝙蝠算法的研究以及應(yīng)用[J].計算機仿真，2014，31（1）：272-280.
[10] 陳歡，周永權(quán).入侵雜草算法的改進分析及研究[D].南寧：廣西民族大學(xué)，2013.
[11] MEHRABIA A R， LUCAS C. A novel numerical optimization algorithm inspired from weed coloniz[J]. Ecological Information， 2006，1（4）：355-366.