基于蝙蝠算法的改進(jìn)雜草算法研究

劉元苗，高曉智，2（.上海海事大學(xué)信息工程學(xué)院，上海20306；2.阿爾托大學(xué)自動(dòng)化與系統(tǒng)技術(shù)系，芬蘭赫爾辛基FI-00076）

基于蝙蝠算法的改進(jìn)雜草算法研究

劉元苗1，高曉智1，2
（1.上海海事大學(xué)信息工程學(xué)院，上海201306；2.阿爾托大學(xué)自動(dòng)化與系統(tǒng)技術(shù)系，芬蘭赫爾辛基FI-00076）

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

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

0 引言

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

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

而本文是將蝙蝠算法中的回聲定位原理應(yīng)用到雜草算法中。通過(guò)回聲定位的特性，對(duì)種子個(gè)體的位置和速度進(jìn)行不斷地更新，使其避免出現(xiàn)早熟和陷入局部最優(yōu)解的情況。且改進(jìn)后的算法有更高的收斂精度。為了驗(yàn)證改進(jìn)后算法的有效性，本文通過(guò)6個(gè)常用的標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)。

1 算法介紹

1.1 標(biāo)準(zhǔn)雜草優(yōu)化算法

在雜草優(yōu)化中，雜草通過(guò)繁殖產(chǎn)生種子，種子經(jīng)過(guò)空間的擴(kuò)散、生長(zhǎng)和競(jìng)爭(zhēng)排除，從而得到適應(yīng)度較高的個(gè)體。其過(guò)程如下[6]：

（1）初始化種群和參數(shù)：在D維數(shù)下產(chǎn)生N個(gè)可行解。

（2）種群的生長(zhǎng)繁殖：適應(yīng)度高的雜草會(huì)產(chǎn)生更多的子代，適應(yīng)度小的會(huì)慢慢消失。其計(jì)算公式：

式中，f是當(dāng)前種群適應(yīng)度；fmax和fmin分別是種群的最大和最小適應(yīng)度；smax和smin分別表示種群的最大規(guī)模和最小規(guī)模。

（3）空間擴(kuò)散：種群所產(chǎn)生的種子按平均值為0、標(biāo)準(zhǔn)差為δ的正態(tài)分布方式和步長(zhǎng)Step∈[-δ，δ]分布在D維空間。在迭代初期標(biāo)準(zhǔn)差δ較大，隨著δ逐漸減小，迭代步長(zhǎng)也在逐漸減小。其公式如下：

（4）競(jìng)爭(zhēng)排除：種群經(jīng)過(guò)多次繁殖之后，其種群規(guī)模達(dá)到最大數(shù)量Pmax時(shí)，將種群中的個(gè)體根據(jù)適應(yīng)度的大小進(jìn)行排列，保留適應(yīng)度前Pmax個(gè)個(gè)體。適應(yīng)度差的個(gè)體將被淘汰。

1.2 蝙蝠算法

蝙蝠算法是受蝙蝠利用回聲定位來(lái)?yè)渥将C物和蔽障的啟發(fā)所提出的啟元式算法[7]。其原理是蝙蝠通過(guò)調(diào)整頻率的大小來(lái)不斷更新其位置和速度從而達(dá)到撲捉獵物的目的。其速度和位置更新公式為：

式中，β∈[0，1]是一個(gè)隨機(jī)變量，x*是當(dāng)前最佳位置。在波長(zhǎng)不變的情況下，fmin=0，fmax=100；開(kāi)始每只蝙蝠的頻率都是隨機(jī)分配的。在進(jìn)行局部搜索時(shí)，每只蝙蝠的最新解都是從現(xiàn)有的解集中選擇的：

其中，ε∈[-1，1]是一個(gè)隨機(jī)數(shù)，A是平均響度；隨著迭代的進(jìn)行，蝙蝠在捕捉時(shí)脈沖所發(fā)的速率和響度也在不斷更新。更新公式為：

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

利用回聲定位的方法來(lái)更新雜草種群中個(gè)體的位置和速度[8]，具體實(shí)施步驟如下：

（1）初始化BAIWO的參數(shù)，并隨機(jī)產(chǎn)生N0個(gè)個(gè)體的種群；

（2）計(jì)算種群個(gè)體的適應(yīng)度函數(shù)值，確定當(dāng)前最優(yōu)值和最優(yōu)解；

（3）種群個(gè)體進(jìn)行繁殖、生長(zhǎng)：

①對(duì)種群中每個(gè)種子利用式（3）～式（5）進(jìn)行位置和速度更新；

②根據(jù)當(dāng)前解集隨機(jī)產(chǎn)生一個(gè)新解，并對(duì)該新解進(jìn)行約束；

③通過(guò)條件（rand

（4）判斷種群是否達(dá)到最大規(guī)模，若未達(dá)到，轉(zhuǎn)到步驟（3），若達(dá)到，則繼續(xù)執(zhí)行；

（5）對(duì)種群個(gè)體的適應(yīng)度值進(jìn)行排序，保留前最大規(guī)模數(shù)的個(gè)體；

（6）判斷是否達(dá)到最大迭代數(shù)，若否，轉(zhuǎn)到步驟（3），若是，輸出最優(yōu)值和最優(yōu)解。

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

1.4 BAIWO算法時(shí)間復(fù)雜度分析

根據(jù)上述的BAIWO算法的流程步驟來(lái)對(duì)該算法進(jìn)行時(shí)間復(fù)雜度分析，設(shè)n為種群個(gè)體的數(shù)目，d為目標(biāo)函數(shù)的維數(shù)，T為最大迭代次數(shù)。時(shí)間復(fù)雜度如表1所示。

表1 BAIWO的時(shí)間復(fù)雜度

2 BAIWO算法仿真實(shí)驗(yàn)

2.1 實(shí)驗(yàn)的初始參數(shù)設(shè)置

該算法的最優(yōu)參數(shù)設(shè)計(jì)：初始種群個(gè)體M0=30，最大種群個(gè)體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個(gè)不同的測(cè)試函數(shù)[11]f1～f6最大迭代次數(shù)分別為500，500，200，500，500，500。函數(shù)參數(shù)如表2所示。

表2 用于測(cè)試改進(jìn)算法的函數(shù)參數(shù)

2.2 測(cè)試函數(shù)

在本實(shí)驗(yàn)中選取了6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)分別對(duì)標(biāo)準(zhǔn)雜草算法和改進(jìn)后雜草算法進(jìn)行性能測(cè)試。

（1）Sphere函數(shù)

上述6個(gè)基準(zhǔn)測(cè)試函數(shù)中，除了f1是單峰函數(shù)以外，其余的都是多峰函數(shù)。圖1和圖2分別是應(yīng)用Rastrigin函數(shù)和Griewank函數(shù)對(duì)這兩種算法在不同迭代次數(shù)下測(cè)試所得到的收斂曲線。

圖1 Rastrigin函數(shù)優(yōu)化測(cè)試

圖2 Griewank函數(shù)優(yōu)化測(cè)試

2.3 仿真結(jié)果分析

通過(guò)以上函數(shù)優(yōu)化測(cè)試曲線可以看出，在迭代初期，BAIWO算法相較于標(biāo)準(zhǔn)IWO算法就具有較好的收斂效果，隨著迭代次數(shù)的增加，到達(dá)迭代后期時(shí)，BAIWO算法也能得到更好的收斂值。說(shuō)明改進(jìn)后的算法提高了標(biāo)準(zhǔn)IWO算法的性能。

實(shí)驗(yàn)結(jié)果如表3所示，可以看出，無(wú)論在單峰還是多峰函數(shù)下，改進(jìn)后算法結(jié)果都優(yōu)于IWO算法，在求解函數(shù)f1（x）～f6（x）時(shí)，改進(jìn)后的算法都能獲得精確度較高的最優(yōu)值，以及較好的平均值和方差。而IWO算法在求解這6個(gè)函數(shù)時(shí)，起始值較大，收斂速度很慢，很容易陷入局部最優(yōu)解?？傮w而言，改進(jìn)后的算法能夠獲得與理論值較近的值，以及很好的魯棒性。

表3 六種基準(zhǔn)函數(shù)的測(cè)試結(jié)果

3 結(jié)束語(yǔ)

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

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

[2]彭斌，胡常安，趙榮珍.基于混合雜草算法的神經(jīng)網(wǎng)絡(luò)優(yōu)化策略[J].振動(dòng)，測(cè)試與診斷，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]張玉，蔣海榮，胡進(jìn)，等.基于改進(jìn)雜草優(yōu)化算法的DFCW參數(shù)估計(jì)[J].現(xiàn)代雷達(dá)，2013，35（7）：20-23.

[6]賈盼龍，田學(xué)民.基于自適應(yīng)小生境的改進(jìn)入侵性雜草優(yōu)化算法[J].上海電機(jī)學(xué)院學(xué)報(bào)，2012，15（4）：225-231.

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

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

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

[10]陳歡，周永權(quán).入侵雜草算法的改進(jì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.

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，F(xiàn)inland）

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-），男，碩士研究生，主要研究方向：最優(yōu)化理論應(yīng)用及其研究。

高曉智（1972-），男，教授，阿爾托大學(xué)博士生導(dǎo)師，主要研究方向：軟計(jì)算理論及其應(yīng)用。