基于單純形法的蝙蝠算法

肖輝輝

(1.河池學(xué)院　計(jì)算機(jī)與信息工程學(xué)院， 廣西　宜州　546300; 2.江西財(cái)經(jīng)大學(xué)　信息管理學(xué)院， 江西　南昌　330013)

?

基于單純形法的蝙蝠算法

肖輝輝1,2

(1.河池學(xué)院計(jì)算機(jī)與信息工程學(xué)院， 廣西宜州546300; 2.江西財(cái)經(jīng)大學(xué)信息管理學(xué)院， 江西南昌330013)

針對(duì)蝙蝠算法局部搜索能力低、迭代后期收斂速度較慢的缺陷，提出基于單純形法的蝙蝠算法。該算法對(duì)進(jìn)入下一次迭代前對(duì)部分較差個(gè)體采用單純形法的擴(kuò)張、收縮/壓縮操作，提高局部搜索能力，進(jìn)而提高算法的尋優(yōu)能力。對(duì)6個(gè)CEC2005 benchmark測(cè)試函數(shù)進(jìn)行測(cè)試比較，仿真結(jié)果表明，改進(jìn)算法的收斂速度、收斂精度、魯棒性等尋優(yōu)性能明顯優(yōu)于基本的蝙蝠算法和參考文獻(xiàn)對(duì)比算法。

蝙蝠算法；尋優(yōu)性能；單純形法；適應(yīng)度值

2010年，Xinshe Yang提出一種新型的元啟發(fā)式群智能算法—蝙蝠算法(Bat Algorithm, BA)[1]，該算法主要針對(duì)蝙蝠在尋找食物時(shí)利用聲吶回聲來(lái)確定食物的位置及其對(duì)障礙物的避躲進(jìn)行模擬，具有分布性、實(shí)現(xiàn)簡(jiǎn)單及并行性等優(yōu)點(diǎn)。蝙蝠算法已經(jīng)在工程科學(xué)和自然科學(xué)領(lǐng)域中得到廣泛的應(yīng)用，如多目標(biāo)優(yōu)化[2]、PFSP調(diào)度問(wèn)題[3]、大規(guī)模優(yōu)化問(wèn)題[4]等。但是，蝙蝠算法與粒子群等群智能算法一樣，也存在局部搜索能力低，迭代后期收斂速度慢等不足，尤其對(duì)于多局部極值、高維的較復(fù)雜優(yōu)化問(wèn)題。為此，國(guó)內(nèi)外不少學(xué)者對(duì)算法進(jìn)行了改進(jìn)：謝健等人提出了一種基于Lévy飛行軌跡的蝙蝠算法(LBA)[5]，該算法在蝙蝠位置的更新公式中引入具有隨機(jī)性的Lévy飛行機(jī)制，提升算法的性能；賴(lài)錦輝提出了基于部落結(jié)構(gòu)的多種學(xué)習(xí)機(jī)制蝙蝠優(yōu)化算法(GDBA)[6]，該算法將蝙蝠群體劃分成部落，在各部落間建立相互學(xué)習(xí)機(jī)制，提高了算法的局部搜索能力。上述這些改進(jìn)在一定程度上避免了局部極值，提高了算法的尋優(yōu)能力，仍未使算法完全避免陷入局部極值，其收斂精度、穩(wěn)定性、收斂速度等方面仍有待改進(jìn)。

針對(duì)蝙蝠算法的局限性，本文提出了一種基于單純形法的蝙蝠算法(SMBA算法)，該算法在進(jìn)入下一次迭代前，對(duì)部分蝙蝠較差個(gè)體進(jìn)行單純形法操作，利用其擴(kuò)張、收縮/壓縮操作產(chǎn)生的較優(yōu)蝙蝠取代最差蝙蝠，提高局部搜索能力。通過(guò)6個(gè)CEC2005 benchmark測(cè)試函數(shù)的仿真實(shí)驗(yàn)結(jié)果，驗(yàn)證了改進(jìn)算法的有效性和優(yōu)越性，SMBA算法較BA算法在較大程度上有效地避免了過(guò)早收斂，增強(qiáng)了算法的局部搜索能力，提高了算法的收斂速度、穩(wěn)定性及收斂精度等性能。

1　BA算法

蝙蝠算法是模擬蝙蝠利用本身特有的聲吶功能進(jìn)行探測(cè)、定位物體的行為的搜索方法。該算法中將蝙蝠個(gè)體與求解問(wèn)題搜索的可行解進(jìn)行對(duì)應(yīng)，把蝙蝠個(gè)體搜索獵物和向獵物移動(dòng)的過(guò)程對(duì)比為算法的搜索和優(yōu)化迭代過(guò)程，蝙蝠個(gè)體位置的好與差由函數(shù)的適應(yīng)度值來(lái)決定，即算法的優(yōu)化迭代過(guò)程即為蝙蝠個(gè)體由差的位置向好的位置靠近的過(guò)程。

BA算法的基本步驟如下：

Step1初始化參數(shù)：種群數(shù)n，最大脈沖音量A，最大脈沖率r，音量的衰減系數(shù)α，搜索頻率的增強(qiáng)系數(shù)γ，搜索精度ε或最大迭代次數(shù)N。

Step2隨機(jī)初始化蝙蝠的位置xi，并求解當(dāng)前最優(yōu)解x*。

Step3按如下公式更新蝙蝠的搜索脈沖頻率、速度和位置：

fi=fmin+(fmax-fmin)×β， (1)

Step4得到隨機(jī)數(shù)R，若R>ri，則求出當(dāng)前最優(yōu)個(gè)體并對(duì)其進(jìn)行隨機(jī)擾動(dòng)得到一個(gè)新的局部個(gè)體解。

Step5產(chǎn)生隨機(jī)數(shù)rand，若rand

Step6計(jì)算蝙蝠種群的適應(yīng)度值，保存當(dāng)前的最優(yōu)值及其最優(yōu)解。

Step7判斷迭代執(zhí)行條件，若不滿(mǎn)足則程序結(jié)束，并保存全局最優(yōu)值及對(duì)應(yīng)的最優(yōu)解，否則，轉(zhuǎn)Step3。

Step8輸出全局最優(yōu)值和最優(yōu)解。

2　SMBA算法

2.1單純形法

單純形法是一種局部搜索能力較強(qiáng)的搜索方法[7]，具有計(jì)算簡(jiǎn)單、搜索速度快的優(yōu)點(diǎn)。單純形法的基本思想為：在一個(gè)d維的空間構(gòu)造一個(gè)d+1個(gè)頂點(diǎn)的多面體，求出該多面體的d+1個(gè)頂點(diǎn)的適應(yīng)度值，對(duì)比適應(yīng)度值求解出最優(yōu)個(gè)體、次優(yōu)個(gè)體及最差個(gè)體，然后對(duì)最差個(gè)體進(jìn)行反射、擴(kuò)張、壓縮/收縮操作使其轉(zhuǎn)為較好個(gè)體，形成新的多面體。因此，單純形法是通過(guò)比較單純多面體頂點(diǎn)的適應(yīng)度值，來(lái)對(duì)單純多面體最差個(gè)體進(jìn)行改進(jìn)，逐步向最優(yōu)值靠近的搜索方法。該方法中的反射操作能使最差個(gè)體隨機(jī)地向重心的反方向搜索，搜索解空間中的所有可行解；擴(kuò)張操作能使新生成的最優(yōu)值個(gè)體繼續(xù)向距最差個(gè)體更遠(yuǎn)的反方向搜索。這樣，若當(dāng)前最優(yōu)值個(gè)體是局部極小點(diǎn)，則擴(kuò)張操作能使該個(gè)體跳出局部極小值區(qū)；收縮操作能使生成的較差的反射點(diǎn)收縮調(diào)整到更好位置。

單純形法的步驟如下：

Step1初始化：計(jì)算所有點(diǎn)的適應(yīng)度值，找出最優(yōu)點(diǎn)ng，次優(yōu)點(diǎn)np，其對(duì)應(yīng)的適應(yīng)度值分別為f(ng)和f(np)，中心位置nc=(ng+np)/2。

Step2生成反射點(diǎn)nx：找出m個(gè)較差的點(diǎn)r，其適應(yīng)度值為f(r)，并對(duì)r點(diǎn)進(jìn)行反射：nx=nc+?(nc-r)，?為反射系數(shù)。

Step3擴(kuò)張操作：若f(nx)

Step4壓縮操作：若f(nx)

Step5收縮操作：若f(nr)>f(nx)>f(np)，則進(jìn)行收縮操作，nw=nc-δ(r-nc)，nw為得到的壓縮點(diǎn)，δ為收縮系數(shù)，其取值與壓縮系數(shù)β一致，若分f(nw)

本文提出在BA算法中引入單純形法，在蝙蝠種群進(jìn)入下一次迭代前，對(duì)多個(gè)較差的蝙蝠個(gè)體利用單純形法搜索策略進(jìn)行優(yōu)化，增強(qiáng)了BA算法的局部搜索能力。

2.2SMBA算法的實(shí)現(xiàn)步驟

針對(duì)BA算法易陷入局部極值、局部搜索能力低、進(jìn)化后期收斂慢等不足，本文采用單純形法策略，提出了SMBA算法，改進(jìn)算法中利用2.1小節(jié)的單純形法策略作用于BA算法，使蝙蝠種群中較差的部分個(gè)體在進(jìn)入下一次迭代前進(jìn)行反射、擴(kuò)張、壓縮/收縮操作使其轉(zhuǎn)為較好蝙蝠個(gè)體，在很大程度上提高了算法的尋優(yōu)性能。

SMBA算法的具體實(shí)施步驟如下：

Step1 初始化SMBA算法的參數(shù):種群數(shù)n，轉(zhuǎn)換概率p，最大脈沖音量A，最大脈沖率R，音量的衰減系數(shù)α，搜索頻率的增強(qiáng)系數(shù)γ，搜索精度ε或最大迭代次數(shù)N，最差個(gè)體數(shù)m，反射系數(shù)?，擴(kuò)張系數(shù)φ，壓縮系數(shù)β，收縮系數(shù)δ。

Step2執(zhí)行BA算法的Step2～Step5。

Step3計(jì)算所有解的適應(yīng)度值，找出最優(yōu)點(diǎn)Xg，次優(yōu)點(diǎn)Xp，及其對(duì)應(yīng)的適應(yīng)度值(Xg)和f(Xp)，中心位置Xc。

Step4對(duì)較差蝙蝠Xr進(jìn)行反射，得到反射點(diǎn)Xx。

Step5若f(Xx)

Step6若f(Xx)

Step7若f(Xr)>f(Xx)>f(Xp)，執(zhí)行收縮操作得到收縮點(diǎn)Xw，若f(Xw)

Step8重復(fù)執(zhí)行 次Step6～Step9來(lái)更新m個(gè)較差蝙蝠的位置。

Step9計(jì)算蝙蝠種群的適應(yīng)度值，并更新全局最優(yōu)值和全局最優(yōu)解。

Step10判斷迭代執(zhí)行條件，若不滿(mǎn)足則退出程序，并保存當(dāng)前最優(yōu)值及對(duì)應(yīng)的最優(yōu)解，否則，轉(zhuǎn)Step2。

3　實(shí)驗(yàn)仿真與分析

為了驗(yàn)證本文算法的正確性和有效性，通過(guò)對(duì)6個(gè)包括單峰、多峰、低維、高維的測(cè)試函數(shù)進(jìn)行仿真來(lái)驗(yàn)證算法的改進(jìn)效果，測(cè)試函數(shù)選用CEC2005 benchmark測(cè)試函數(shù)中的一部分，測(cè)試函數(shù)如下：

該函數(shù)是一個(gè)單峰函數(shù)，函數(shù)在x*=(0,0,…,0)處取得全局min(f1(x))=0。

該函數(shù)是一個(gè)多峰函數(shù)，函數(shù)在x*=(0,0,…,0)處取得全局min(f2(x))=0。

(3)Ackley函數(shù)：

該函數(shù)是一個(gè)多峰函數(shù)，在x*=(0,0,…,0)處取得全局最小值min(f3(x))=0。

該函數(shù)是一個(gè)多峰函數(shù)，在x*=(0,0,…,0)處取得全局最小值min(f4(x))=0。

該函數(shù)是一個(gè)單峰函數(shù)，在x*=(0,0,…,0)處取得全局最小值min(f5(x))=0。

該函數(shù)的是一個(gè)二維多峰函數(shù)，在x*=(0,0)處取得全局最小值min(f6(x))=-1。

本文實(shí)驗(yàn)的參數(shù)設(shè)置為：種群個(gè)數(shù)n=20，維數(shù)d=10(函數(shù)f6的維數(shù)d=2)，最大迭代次數(shù)N=200。另外，SMBA算法中，較差蝙蝠數(shù)m=6，反射系數(shù)?=0.9，擴(kuò)張系數(shù)φ=1.2，壓縮系數(shù)β=1.5，收縮系數(shù)δ=1.5。

為了驗(yàn)證本文改進(jìn)算法的尋優(yōu)性能、可行性及正確性，仿真實(shí)驗(yàn)方法為：(1)固定算法的迭代次數(shù)，測(cè)試2種算法的尋優(yōu)性能；(2)給定函數(shù)的收斂精度，測(cè)試SMBA、PSO和BA算法的穩(wěn)定性和收斂性；(3)與參考文獻(xiàn)算法對(duì)比，測(cè)試本文算法的魯棒性和尋優(yōu)精度，并進(jìn)一步驗(yàn)證SMBA算法的尋優(yōu)精度。

3.1固定迭代次數(shù)的性能分析

本小節(jié)設(shè)置固定迭代次數(shù)N=200，為了避免算法的偶然性帶來(lái)的性能比較上的誤差，比較算法均對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行25次，計(jì)算其最優(yōu)值、優(yōu)化均值、最差值和標(biāo)準(zhǔn)方差，實(shí)驗(yàn)結(jié)果見(jiàn)表1，其中，尋優(yōu)成功率=(找到最優(yōu)解的次數(shù))/總運(yùn)行次數(shù)。在實(shí)驗(yàn)中，假定：|實(shí)際求解的最優(yōu)值-理論最優(yōu)值|<0.001，則認(rèn)為算法成功地找到最優(yōu)值。

從表1中可以看出，對(duì)于所有測(cè)試函數(shù)，本文提出的SMBA算法的尋優(yōu)性能在很大程度上均優(yōu)于基本BA算法。對(duì)于所有測(cè)試函數(shù)，BA算法的尋優(yōu)成功率都為0，而SMBA算法，函數(shù)f1、f3、f4的尋優(yōu)成功率都為100%，其它3個(gè)函數(shù)的尋優(yōu)成功率也較高；對(duì)于函數(shù)f1～f5，SMBA算法的最優(yōu)值、優(yōu)化均值、最差值和標(biāo)準(zhǔn)方差均較BA算法有較大的提高，最多相差11個(gè)數(shù)量級(jí)；對(duì)于二維函數(shù)f6，SMBA算法能找到最優(yōu)值，而B(niǎo)A算法不能。為了便于觀察改進(jìn)算法及基本蝙蝠算法的尋優(yōu)收斂效果，圖1是該兩種算法求解6個(gè)測(cè)試函數(shù)收斂圖，形象地展示了SMBA算法和BA算法的對(duì)比適應(yīng)度值的迭代下降過(guò)程和全局最優(yōu)解的收斂速度。從圖1中可得出，對(duì)于6個(gè)測(cè)試函數(shù)，SMBA算法的收斂精度和收斂速度均較BA算法要好。這表明，本文提出SMBA算法具有更好的尋優(yōu)能力，其收斂速度、優(yōu)化精度明顯優(yōu)于BA算法。

表1　2種算法在固定迭代次數(shù)下的尋優(yōu)性能比較

圖1　2種算法在函數(shù)f1～f6上的收斂曲線

3.2固定收斂精度的性能分析

為了驗(yàn)證本文算法的收斂程度，在給定的固定精度下，對(duì)所有測(cè)試函數(shù)獨(dú)立運(yùn)行25次，SMBA算法、BA和PSO算法分別對(duì)比其最小收斂次數(shù)、平均收斂次數(shù)及收斂率，其中，收斂率=達(dá)到固定精度的迭代次數(shù)/總運(yùn)行次數(shù)，其結(jié)果如表2所示，表中“-”表示尋優(yōu)失敗。本小節(jié)的3種算法的種群數(shù)為25，最大迭代次數(shù)為2 000，當(dāng)前迭代次數(shù)超過(guò)最大代次數(shù)時(shí)，則認(rèn)為尋優(yōu)不成功。從表2可知，對(duì)于函數(shù)f1～f6， BA算法都無(wú)法收斂，SMBA算法的收斂率都為100%，遠(yuǎn)遠(yuǎn)高于對(duì)比算法，同時(shí)其最小收斂次數(shù)及平均收斂次數(shù)也明顯低于對(duì)比算法。實(shí)驗(yàn)數(shù)據(jù)證明，本文改進(jìn)算法在收斂性、魯棒性性能上得到明顯的提高。

表2　固定精度下的最小收斂次數(shù)、平均收斂次數(shù)和收斂率對(duì)比

3.3與參考文獻(xiàn)算法性能比較

為了進(jìn)一步驗(yàn)證本算法較好的穩(wěn)定性和較高的尋優(yōu)精度，證明本文改進(jìn)算法的優(yōu)勢(shì)，限于篇幅，只選用函數(shù)f2～f5與參考文獻(xiàn)中的CPSO[8]、CLIWO[9]、LDWPSO[10]、ABCMSS[11]算法對(duì)比，為了文中前后數(shù)據(jù)的一致性，本小節(jié)中的SMBA數(shù)據(jù)來(lái)自3.1小節(jié)，其結(jié)果如表3所示。其中，本文算法的迭代次數(shù)為200、種群數(shù)為20，除參考文獻(xiàn)[9]的迭代次數(shù)為200、種群數(shù)為15外，其他參考文獻(xiàn)的迭代次數(shù)和種群數(shù)均較大，分別為6 000(30)、2 000(300)和2 000(100)，括號(hào)中的為種群數(shù)。由表3可知，在測(cè)試參數(shù)較參考文獻(xiàn)要嚴(yán)格的條件下，SMBA算法的優(yōu)化性能(優(yōu)化均值、標(biāo)準(zhǔn)方差)都能較參考文獻(xiàn)中的其他群智能優(yōu)化算法有較大的提高。對(duì)于函數(shù)f2～f5，SMBA的優(yōu)化均值、標(biāo)準(zhǔn)方差都在較大程度上好于其他參考文獻(xiàn)算法。其中，優(yōu)化均值的性能最大相差8個(gè)數(shù)量級(jí)，標(biāo)準(zhǔn)方差的性能最大相差9個(gè)數(shù)量級(jí)。種群數(shù)和迭代次數(shù)這兩個(gè)參數(shù)值是影響算法尋優(yōu)性能的主要因素，且這兩個(gè)參數(shù)值與算法的時(shí)間復(fù)雜度成正比例關(guān)系。仿真結(jié)果表明，本文SMBA算法的收斂精度和穩(wěn)定性均得到較大的提高，進(jìn)而說(shuō)明SMBA算法是可行的和有效的。

表3　SMBA算法與參考文獻(xiàn)算法的優(yōu)化均值和標(biāo)準(zhǔn)方差比較

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

蝙蝠算法是一種新的群智能算法，但其亦存在早熟收斂、收斂精度較低、算法后期收斂速度慢等不足。為此，本文算法引入單純形法策略，提高了局部搜索能力，進(jìn)而提高算法的整體尋優(yōu)性能。通過(guò)6個(gè)CEC2005 benchmark測(cè)試函數(shù)的測(cè)試，仿真結(jié)果表明，改進(jìn)算法是可行和有效的，單純算法使BA算法的整體性能得到一定程度地提高。

[1] Yang X S. A new metaheuristic bat-inspired algorithm[C]∥ Nature Inspired Cooperative Strategies for Optimization(NISCO 2010)，Studies in Computational intelligence 284.Berlin Eidelberg: Sprin-Verlag,2010:65-74.

[2] YANG X S. Bat algorithm for multi-objective optimisation [J].Int.J.Bio-Inspired Computation, 2011,3(5):267-274.

[3] 盛曉華,葉春明.蝙蝠算法在PFSP調(diào)度問(wèn)題中的應(yīng)用研究[J].工業(yè)工程,2013,16(1):119-124.

[4] 黃光球,趙魏娟,陸秋琴.求解大規(guī)模優(yōu)化問(wèn)題的可全局收斂蝙蝠算法[J].計(jì)算機(jī)應(yīng)用研究, 2013,30(5):1323-1328.

[5] 謝健,周永權(quán),陳歡.一種基于Lévy飛行軌跡的蝙蝠算法[J].模式識(shí)別與人工智能, 2013,26(9):829-837.

[6] 賴(lài)錦輝.基于部落結(jié)構(gòu)的多種學(xué)習(xí)機(jī)制蝙蝠優(yōu)化算法 [J].計(jì)算機(jī)應(yīng)用研究,2015, 32(2):364-367.

[7] NELDER J A,MEAD R. A simplex method for function minimization[J].Computer journal, 1965,7(4):308-313.

[8] 趙新超,劉國(guó)蒞,劉虎球,趙國(guó)帥. 基于非均勻變異和多階段擾動(dòng)的粒子群優(yōu)化算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2014,37(9): 2058-2070.

[9] 劉挺,王聯(lián)國(guó). 基于云模型的入侵雜草優(yōu)化算法[J].計(jì)算機(jī)工程,2014,40(12):156-160.

[10] 喬俊飛,傅嗣鵬,韓紅桂.基于混合變異策略的改進(jìn)差分進(jìn)化算法及函數(shù)優(yōu)化[J].控制工程,2013,20(5):943-947.

[11] 王志剛.一種改進(jìn)搜索策略的人工蜂群算法[J].計(jì)算機(jī)仿真, 2014,31(10):291-295.

[Abstract]Bat algorithm based on simplex method was presented to overcome the poor capacity in local searching and low speed of convergence of bat algorithm. The algorithm uses the expansion and contraction/compression operation of simplex method to enter the next iteration of individuals to enhance the capacity of global optimization, and to improve the convergence speed. The six CEC2005 benchmark functions were tested and compared and the simulation results show that the proposed algorithm has the advantages of better global searching ability, faster convergence and more precise convergence than those of the basic bat algorithm and the reference comparison algorithm.

[Key words]bat algorithm; optimization ability; simplex method; fitness

[責(zé)任編輯劉景平]

Bat Algorithm Based on Simplex Method

XIAO Hui-hui1,2

(1. School of Computer and Information Engineering, Hechi University, Yizhou, Guangxi 546300, China;2. School of Information and Technology, Jiangxi University of Finance and Economics,Nanchang, Jiangxi 330013, China)

TP301.6

A

1672-9021(2016)02-0060-07

肖輝輝(1977-)，男，江西永新人，河池學(xué)院計(jì)算機(jī)與信息工程學(xué)院副教授、實(shí)驗(yàn)師，主要研究方向：智能計(jì)算、情感分析。

廣西高?？蒲谢鹳Y助項(xiàng)目(KY2015LX332, KY2015LX334)；河池學(xué)院科研基金資助項(xiàng)目(XJ2015QN003)；河池學(xué)院“計(jì)算機(jī)網(wǎng)絡(luò)與軟件新技術(shù)”重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(院科研〔2013〕3號(hào))；江西省研究生創(chuàng)新基金資助項(xiàng)目(YC2015-B054)；河池學(xué)院教改基金資助項(xiàng)目(2014EB002)。

2015-11-20