基于蝙蝠算法的改進雜草算法研究

劉元苗，高曉智，2（.上海海事大學信息工程學院，上海20306；2.阿爾托大學自動化與系統技術系，芬蘭赫爾辛基FI-00076）

基于蝙蝠算法的改進雜草算法研究

劉元苗1，高曉智1，2
（1.上海海事大學信息工程學院，上海201306；2.阿爾托大學自動化與系統技術系，芬蘭赫爾辛基FI-00076）

提出了一種新型的混合算法并命名為混合雜草蝙蝠算法（Hybridize Invasive Weed Optimization with Bat Algorithm，IWOBA），該算法在雜草算法的基礎上利用蝙蝠算法的回聲定位來解決每代種子逐步尋優的問題。其原理是利用種群速度和位置的不斷更新，增加種群的多樣性，從而達到提高種群的全局收斂性。最后利用6個測試函數對該算法和標準雜草算法進行測試比較。仿真結果表明，IWOBA能夠有效克服原算法早熟、易陷入局部最優的缺點，可加快算法收斂速度，具有良好的魯棒性。

雜草算法；蝙蝠算法；回聲定位

0 引言

入侵雜草算法（Invasive Weed Optimization，IWO）是由德黑蘭大學的Mehrabian等在2006年提出來的，它是一種模擬自然界雜草入侵的新型的數值優化算法。該算法具有很強的魯棒性和適應性，并且具有易于理解及實現等特點。近幾年來，在很多學者的研究下，雜草算法已經成功應用到圖像聚類、工程約束設計以及DNA編碼等眾多領域中[1-2]。

與其他智能算法相比較，標準雜草算法本身存在易于陷入局部最優解和收斂精度不高的不足，這些不足都影響著算法的尋優效果。因此，Hajimirsadeghi和Lucas提出了一種IWO和PSO融合的算法[3]，利用位置和速度的更新，使得算法避免了局部最優解；Zhang Xuncai等人在標準IWO算法中引入了交叉算子，避免算法早熟，提高了全局最優解[4]；張玉等人將遺傳算法中的選擇機制加入到標準IWO算法中，從而提高算法的多樣性[5]。

而本文是將蝙蝠算法中的回聲定位原理應用到雜草算法中。通過回聲定位的特性，對種子個體的位置和速度進行不斷地更新，使其避免出現早熟和陷入局部最優解的情況。且改進后的算法有更高的收斂精度。為了驗證改進后算法的有效性，本文通過6個常用的標準測試函數進行仿真實驗。

1 算法介紹

1.1 標準雜草優化算法

在雜草優化中，雜草通過繁殖產生種子，種子經過空間的擴散、生長和競爭排除，從而得到適應度較高的個體。其過程如下[6]：

（1）初始化種群和參數：在D維數下產生N個可行解。

（2）種群的生長繁殖：適應度高的雜草會產生更多的子代，適應度小的會慢慢消失。其計算公式：

式中，f是當前種群適應度；fmax和fmin分別是種群的最大和最小適應度；smax和smin分別表示種群的最大規模和最小規模。

（3）空間擴散：種群所產生的種子按平均值為0、標準差為δ的正態分布方式和步長Step∈[-δ，δ]分布在D維空間。在迭代初期標準差δ較大，隨著δ逐漸減小，迭代步長也在逐漸減小。其公式如下：

（4）競爭排除：種群經過多次繁殖之后，其種群規模達到最大數量Pmax時，將種群中的個體根據適應度的大小進行排列，保留適應度前Pmax個個體。適應度差的個體將被淘汰。

1.2 蝙蝠算法

蝙蝠算法是受蝙蝠利用回聲定位來撲捉獵物和蔽障的啟發所提出的啟元式算法[7]。其原理是蝙蝠通過調整頻率的大小來不斷更新其位置和速度從而達到撲捉獵物的目的。其速度和位置更新公式為：

式中，β∈[0，1]是一個隨機變量，x*是當前最佳位置。在波長不變的情況下，fmin=0，fmax=100；開始每只蝙蝠的頻率都是隨機分配的。在進行局部搜索時，每只蝙蝠的最新解都是從現有的解集中選擇的：

其中，ε∈[-1，1]是一個隨機數，A是平均響度；隨著迭代的進行，蝙蝠在捕捉時脈沖所發的速率和響度也在不斷更新。更新公式為：

1.3 雜草算法與蝙蝠算法的融合算法BAIWO

利用回聲定位的方法來更新雜草種群中個體的位置和速度[8]，具體實施步驟如下：

（1）初始化BAIWO的參數，并隨機產生N0個個體的種群；

（2）計算種群個體的適應度函數值，確定當前最優值和最優解；

（3）種群個體進行繁殖、生長：

①對種群中每個種子利用式（3）～式（5）進行位置和速度更新；

②根據當前解集隨機產生一個新解，并對該新解進行約束；

③通過條件（rand

（4）判斷種群是否達到最大規模，若未達到，轉到步驟（3），若達到，則繼續執行；

（5）對種群個體的適應度值進行排序，保留前最大規模數的個體；

（6）判斷是否達到最大迭代數，若否，轉到步驟（3），若是，輸出最優值和最優解。

從上述BAIWO算法的描述過程可知，BAIWO算法中的個體并不是在每次迭代過后直接進入下一代繁殖、生長，而是在種群中個體進行位置和速度更新后找出更優的個體進行下一代繁殖。這樣，在迭代初期可以使得種群有著更強的全局搜索能力，到達迭代后期時，種群的尋優步長在不斷變小，使得其具有更強的局部搜索能力。所以，BAIWO算法是將BA算法和IWO算法的各自優點融合起來，使得改進后的算法在初期擁有很好的全局搜索能力，到達后期對局部搜索更精確。從而克服了IWO算法前期陷入局部搜索，以及后期收斂精度不高和速度慢等缺陷[9-10]。

1.4 BAIWO算法時間復雜度分析

根據上述的BAIWO算法的流程步驟來對該算法進行時間復雜度分析，設n為種群個體的數目，d為目標函數的維數，T為最大迭代次數。時間復雜度如表1所示。

表1 BAIWO的時間復雜度

2 BAIWO算法仿真實驗

2.1 實驗的初始參數設置

該算法的最優參數設計：初始種群個體M0=30，最大種群個體Max=50，最大種子數為Smax=5，最小種子數為Smin=2，調和指數n=3，方差最大值和最小值分別為10和0.001，最大響度A=0.25，最大脈沖率R0=0.5，脈沖響度范圍為[0，2]，脈沖衰減系數為0.9；6個不同的測試函數[11]f1～f6最大迭代次數分別為500，500，200，500，500，500。函數參數如表2所示。

表2 用于測試改進算法的函數參數

2.2 測試函數

在本實驗中選取了6個標準測試函數分別對標準雜草算法和改進后雜草算法進行性能測試。

（1）Sphere函數

上述6個基準測試函數中，除了f1是單峰函數以外，其余的都是多峰函數。圖1和圖2分別是應用Rastrigin函數和Griewank函數對這兩種算法在不同迭代次數下測試所得到的收斂曲線。

圖1 Rastrigin函數優化測試

圖2 Griewank函數優化測試

2.3 仿真結果分析

通過以上函數優化測試曲線可以看出，在迭代初期，BAIWO算法相較于標準IWO算法就具有較好的收斂效果，隨著迭代次數的增加，到達迭代后期時，BAIWO算法也能得到更好的收斂值。說明改進后的算法提高了標準IWO算法的性能。

實驗結果如表3所示，可以看出，無論在單峰還是多峰函數下，改進后算法結果都優于IWO算法，在求解函數f1（x）～f6（x）時，改進后的算法都能獲得精確度較高的最優值，以及較好的平均值和方差。而IWO算法在求解這6個函數時，起始值較大，收斂速度很慢，很容易陷入局部最優解。總體而言，改進后的算法能夠獲得與理論值較近的值，以及很好的魯棒性。

表3 六種基準函數的測試結果

3 結束語

本文針對雜草算法存在早熟現象和易陷入局部最優解等缺點，提出了利用蝙蝠算法中回聲定位原理來對種群個體進行更新。從而使得種群前期擁有很好的全局收斂特性，后期可以使其避免陷入局部最優。從仿真結果看出，BAIWO算法在很大程度上提高了雜草算法的收斂性和尋優精度。然而，如何改變IWO算法中種群多樣性來提高它的收斂性是今后要進一步研究的方向。

[1]張氫，陳丹丹，秦仙蓉，等.雜草算法收斂性分析及其在工程中的應用[J].同濟大學學報（自然科學版），2010，38（11）：1689-1693.

[2]彭斌，胡常安，趙榮珍.基于混合雜草算法的神經網絡優化策略[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]張玉，蔣海榮，胡進，等.基于改進雜草優化算法的DFCW參數估計[J].現代雷達，2013，35（7）：20-23.

[6]賈盼龍，田學民.基于自適應小生境的改進入侵性雜草優化算法[J].上海電機學院學報，2012，15（4）：225-231.

[7]Yang Xinshe.Nature-inspired Metaheuristic Algorithms[M]. Beckington：Luniver Press，2010.

[8]李枝勇，馬良，張惠珍.蝙蝠算法收斂性分析[J].數學的實踐與認識，2013，43（12）：182-191.

[9]肖輝輝，段艷明.基于DE算法改進的蝙蝠算法的研究以及應用[J].計算機仿真，2014，31（1）：272-280.

[10]陳歡，周永權.入侵雜草算法的改進分析及研究[D].南寧：廣西民族大學，2013.

[11]MEHRABIA A R，LUCAS C.A novel numerical optimization algorithm inspired from weed coloniz[J].Ecological Information，2006，1（4）：355-366.

Research of im proved invasive w eed optim ization algorithm base on bat algorithm

Liu Yuanmiao1，Gao Xiaozhi1，2
（1．Information Engineering Institute of Shanghai Maritime University，Shanghai 201306，China；2.Department of Automation and Systems Technology，Aalto University，Helsinki FI-00076，Finland）

A novel hybrid algorithm is proposed in this paper named hybridize invasive weed optimization with bat algorithm（IWOBA）.It is based on invasive weed optimization（IWO）and uses the echo-location of bat algorithm to solve optimization problem of each seeds steps of steps.The principle is the constantly update of the speed and position of population，and increase the diversity of the population，to enhance the global convergence of population.Finally six test functions were used to validate the algorithm and the standard of invasive weed algorithm（IWO）.The simulation results indicate that the IWOBA can effectively overcome the shortcoming of local optimum and the original in puberty，and accelerate the algorithm convergence speed and have good robustness.

invasive weed optimization algorithm；bat algorithm；echo-location

TP301

A

1674-7720（2015）03-0075-03

2014-10-03）

劉元苗（1987-），男，碩士研究生，主要研究方向：最優化理論應用及其研究。

高曉智（1972-），男，教授，阿爾托大學博士生導師，主要研究方向：軟計算理論及其應用。