肖輝輝

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

?

基于單純形法的蝙蝠算法

肖輝輝1,2

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

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

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

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

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

1　BA算法

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

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)個體并對其進(jìn)行隨機(jī)擾動得到一個新的局部個體解。

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

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

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

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

2　SMBA算法

2.1單純形法

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

單純形法的步驟如下：

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

Step2生成反射點nx：找出m個較差的點r，其適應(yīng)度值為f(r)，并對r點進(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為得到的壓縮點，δ為收縮系數(shù)，其取值與壓縮系數(shù)β一致，若分f(nw)

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

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

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

SMBA算法的具體實施步驟如下：

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

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

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

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

Step5若f(Xx)

Step6若f(Xx)

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

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

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

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

3　實驗仿真與分析

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

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

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

(3)Ackley函數(shù)：

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

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

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

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

本文實驗的參數(shù)設(shè)置為：種群個數(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。

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

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

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

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

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

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

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

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

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

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

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

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

4　結(jié)束語

蝙蝠算法是一種新的群智能算法，但其亦存在早熟收斂、收斂精度較低、算法后期收斂速度慢等不足。為此，本文算法引入單純形法策略，提高了局部搜索能力，進(jìn)而提高算法的整體尋優(yōu)性能。通過6個CEC2005 benchmark測試函數(shù)的測試，仿真結(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)度問題中的應(yīng)用研究[J].工業(yè)工程,2013,16(1):119-124.

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

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

[6] 賴錦輝.基于部落結(jié)構(gòu)的多種學(xué)習(xí)機(jī)制蝙蝠優(yōu)化算法 [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] 趙新超,劉國蒞,劉虎球,趙國帥. 基于非均勻變異和多階段擾動的粒子群優(yōu)化算法[J]. 計算機(jī)學(xué)報, 2014,37(9): 2058-2070.

[9] 劉挺,王聯(lián)國. 基于云模型的入侵雜草優(yōu)化算法[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ī)仿真, 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ī)與信息工程學(xué)院副教授、實驗師，主要研究方向：智能計算、情感分析。

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

2015-11-20