一種基于二分法查找的改進(jìn)混合蛙跳算法

王曉彬，鄒海榮

（上海電機(jī)學(xué)院電氣學(xué)院，上海 201306）

群體智能優(yōu)化算法是通過模仿自然界中群居生物的覓食或生活行為，研究其中的原理，并應(yīng)用數(shù)學(xué)方法建模嘗試解決大量實(shí)際工程應(yīng)用中的難題。由于其通用性強(qiáng)、原理簡(jiǎn)單、實(shí)現(xiàn)方便，最重要的是能有效解決各種傳統(tǒng)方法不易解決的復(fù)雜的組合優(yōu)化問題，通過多次迭代自我適應(yīng)、學(xué)習(xí)和發(fā)展，最終得到一個(gè)復(fù)雜問題的最優(yōu)解，受到了眾多專家學(xué)者的青睞，開拓了許多新興研究熱點(diǎn)，取得了顯著成功。

混合蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）通過模擬青蛙覓食行為［1］，進(jìn)行元啟發(fā)式搜索，從而得到問題的最優(yōu)解。SFLA最早由Eusuff等[2]提出，相較于其他智能優(yōu)化算法，其顯著特點(diǎn)是采取局部搜索和全局信息搜索融合的協(xié)同搜索策略。該算法具有模因算法（Memetic Algorithm，MA）搜索效率和容錯(cuò)率高的優(yōu)點(diǎn)，也有粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）通用性強(qiáng)的優(yōu)點(diǎn)，是兩者優(yōu)點(diǎn)的結(jié)合體。SFLA參數(shù)少，更便于使用編程實(shí)現(xiàn)。目前已廣泛應(yīng)用于模式識(shí)別、函數(shù)優(yōu)化、信號(hào)與信息處理等領(lǐng)域中，并取得了成功。

雖然SFLA優(yōu)點(diǎn)眾多，但會(huì)出現(xiàn)求解精度不高、算法易陷入局部最優(yōu)等問題。針對(duì)這些問題，近年來，許多國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行研究、改進(jìn)。高建瓴等［3］引入自適應(yīng)同步因子，改變局部搜索蛙跳規(guī)則，從而增加種群的多樣性。趙紅星等［4］對(duì)青蛙的覓食機(jī)制和更新迭代公式重新定義，提高了SFLA的全局和局部搜索能力。王聯(lián)國(guó)等［5］對(duì)初始種群引入Tent混沌改進(jìn)，在最差個(gè)體更新中引入擾動(dòng)的柯西因子，提高算法的尋優(yōu)能力。戴月明等［6］在全局搜索中采取精英群自學(xué)進(jìn)化機(jī)制，對(duì)精英空間進(jìn)行精細(xì)搜索，提升全局搜索能力。上述文獻(xiàn)雖然通過一些方法提升了算法的尋優(yōu)能力和收斂精度，但效果不是很理想，并沒有考慮更優(yōu)個(gè)體可能存在于其附近空間［7］。因此，本文提出一種基于二分法查找的改進(jìn)SFLA，以最差蛙之外的其他個(gè)體的平均值作為中間因子，加強(qiáng)最差蛙與其他個(gè)體的交流，增強(qiáng)算法尋優(yōu)能力和收斂精度；在標(biāo)準(zhǔn)蛙跳算法步長(zhǎng)更新的基礎(chǔ)上引入加速因子，提高算法的收斂速度；最后通過測(cè)試函數(shù)驗(yàn)證改進(jìn)算法的有效性。

1 SFLA

1.1 算法原理

SFLA的背景是在一片沼澤地里，青蛙利用沼澤地中離散分布的石塊去尋找更多食物［8］，每只青蛙個(gè)體之間通過交流來交換信息，通過整個(gè)種群的信息交流，使每只青蛙得到最多的食物。轉(zhuǎn)換為算法的思想，即為了每個(gè)解都達(dá)到最優(yōu)，最終使整個(gè)算法達(dá)到最優(yōu)解，即由局部最優(yōu)到全局最優(yōu)的過程［9］。

由上述背景可得SFLA的基本思想：隨機(jī)生成M只青蛙個(gè)體，組成初始種群P=｛X1，X2，…，X M｝，s維解空間中的第i只青蛙可表示為Xi=（x i1，x i2，…，x is）。在生成初始種群之后，首先對(duì)青蛙個(gè)體進(jìn)行排序，即求解種群內(nèi)所有青蛙個(gè)體的適應(yīng)度值，并按照大小降序排列，將種群中最優(yōu)適應(yīng)度值（最小值）記為Xglo。然后將種群依據(jù)規(guī)則分成一個(gè)個(gè)小的子種群，平均分成m個(gè)，每個(gè)子種群包含n只個(gè)體，它們的關(guān)系M=m×n。其中，第1只青蛙分入第1個(gè)子種群組，第2只青蛙分入第2個(gè)子種群組，繼續(xù)分配，第m只青蛙分入第m個(gè)子種群組，第m+1只青蛙重新分入第1個(gè)子種群組，以此類推，平均分配[10]。將每個(gè)子種群中的最好適應(yīng)度（最小值）的青蛙記為Xb，最差適應(yīng)度的青蛙記為Xw。最后根據(jù)分好的子種群組，依據(jù)更新策略進(jìn)行位置的更新，即對(duì)子種群組中的Xw循環(huán)進(jìn)行局部搜索操作。其更新方式為

式中：rand（）函數(shù)表示產(chǎn)生0～1之間均勻分布隨機(jī)實(shí)數(shù)；Stmin、Stmax為最差蛙所允許改變步長(zhǎng)的下限和上限。

算法經(jīng)過上式更新后，若得到的蛙Xnew優(yōu)于原來的蛙Xw，則取代原來子種群組中的蛙；若沒有改進(jìn)，用Xglo取代Xb，算法再次更新最差蛙的位置；若此次更新后，適應(yīng)度仍然比更新前的值差，則隨機(jī)取種群中任意一個(gè)青蛙個(gè)體來取代原來的Xw。當(dāng)局部搜索次數(shù)達(dá)到所允許的上限時(shí)，將所有子種群組內(nèi)的青蛙重新混合，重復(fù)上述優(yōu)化過程［11］。如此反復(fù)，直至達(dá)到全局最大收斂次數(shù)為止。圖1為SFLA流程。

圖1 SFLA流程

1.2 改進(jìn)的SFLA

從SFLA的基本思想來看，SFLA以子種群中最差蛙為更新基礎(chǔ)，將最優(yōu)和最差蛙之間的位置差值作為更新的步長(zhǎng)，更新最差蛙向食物靠近。最差蛙的每一次位置的更新只與子種群內(nèi)或者種群內(nèi)的最優(yōu)青蛙個(gè)體交換信息，并沒有與其他個(gè)體進(jìn)行充分的信息交換，忽視了與其他蛙的信息交流，使得交流趨向單一化，導(dǎo)致青蛙個(gè)體之間的互異性減小，縮減了解的搜索空間，導(dǎo)致種群易陷入局部最優(yōu)而早熟收斂，達(dá)不到所要求的精度［12］。

在種群個(gè)體位置更新過程中，基于數(shù)學(xué)中二分法查找的思想，引入中間因子和加速因子。通過引入中間因子，調(diào)控青蛙個(gè)體在尋優(yōu)過程中的步長(zhǎng)，擴(kuò)大算法的局部搜索范圍，從而保持青蛙種群的多樣性；引入加速因子，加快蛙的搜索速度。

1.2.1 引入中間因子二分法查找是一種高效的搜索方法，其基本原理是：數(shù)據(jù)按升序（或者降序）排列，對(duì)于一個(gè)給定值X，從序列的中間位置開始比較，若當(dāng)前位置的值等于X，則查找成功；若X小于當(dāng)前位置值，則在數(shù)列的前半段中查找；若X大于當(dāng)前位置值，則在數(shù)列的后半段中繼續(xù)查找，直到找到為止［13］。

基于二分法查找的思想，針對(duì)SFLA的缺點(diǎn)，提出如下改進(jìn)：在對(duì)蛙群排序后，除最差蛙之外的其他個(gè)體的平均值作為中間因子Xa。之后重新混合，將其分為兩個(gè)子種群mX1、mX2，記種群mX1的平均值為Xave1，種群mX2的平均值為Xave2。若將Xave1與中間因子比較，適應(yīng)度比中間因子所對(duì)應(yīng)的適應(yīng)度差時(shí)，則淘汰該種群，選擇未淘汰的種群更新最差蛙。之后在未淘汰的種群內(nèi)重復(fù)上述操作，具體的位置更新策略如下：

式中：Xi為青蛙種群中不同于Xw的青蛙個(gè)體；C為加速因子。

引入中間因子Xa調(diào)整最差蛙，向Xb進(jìn)化，不忽略其他潛在優(yōu)秀個(gè)體的信息。當(dāng)系統(tǒng)突然受到外界干擾時(shí)，因其群體數(shù)量多且均參與其中，使系統(tǒng)的穩(wěn)定性得到提升［14］。

1.2.2 引入加速因子在算法中，步長(zhǎng)的大小會(huì)影響算法的性能。若步長(zhǎng)過小，會(huì)減弱算法搜索的能力；若步長(zhǎng)過大，則會(huì)跳過真正的最優(yōu)解，陷入局部最優(yōu)。在SFLA中，如式（1）所示，步長(zhǎng)是rand（）函數(shù)產(chǎn)生的0～1的隨機(jī)數(shù)與位置差值的乘積。本文改進(jìn)算法引入大于1的加速因子C，如式（4）所示，在SFLA的步長(zhǎng)基礎(chǔ)上增大步長(zhǎng)，加快局部收斂速度。選擇合適的加速因子，使算法在搜索時(shí)能以合適的變化率平穩(wěn)地進(jìn)行［15］。

2 仿真實(shí)驗(yàn)及結(jié)果分析

2.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證改進(jìn)混合蛙跳算法（Improved Shuffled Frog Leaping Algorithm，ISFLA）的有效性，選取以下6個(gè)典型測(cè)試函數(shù)，對(duì)ISFLA的性能進(jìn)行仿真研究。各函數(shù)的表達(dá)式如下：

各函數(shù)的參數(shù)設(shè)置見表1。

表1 測(cè)試函數(shù)參數(shù)設(shè)置

本文將6個(gè)測(cè)試函數(shù)的解空間的維數(shù)都固定為30維，設(shè)計(jì)了3個(gè)實(shí)驗(yàn)［16］。首先是加速因子確值實(shí)驗(yàn)，改變加速因子的值，觀察數(shù)值的大小對(duì)算法收斂速度的影響；其次是算法收斂精度實(shí)驗(yàn)，固定算法最大迭代次數(shù)為500次，比較算法獨(dú)立運(yùn)行后的收斂精度和運(yùn)行時(shí)間；最后是算法迭代次數(shù)比較實(shí)驗(yàn)，指定各函數(shù)收斂精度，對(duì)兩種算法的進(jìn)化次數(shù)進(jìn)行對(duì)比［17］。

2.2 加速因子確值實(shí)驗(yàn)

加速因子雖然能夠加快收斂速度，但不是越大越好。為了確定不同加速因子對(duì)算法收斂速度的影響，在改進(jìn)蛙跳算法的基礎(chǔ)上，分別記錄加速因子不同的值達(dá)到最大迭代次數(shù)所用的時(shí)間以及達(dá)到收斂精度所用的時(shí)間，確定加速因子最佳值并應(yīng)用于算法收斂精度實(shí)驗(yàn)。加速因子確值實(shí)驗(yàn)結(jié)果如圖2所示。對(duì)函數(shù)f1～f6，加速因子分別取不同的值，算法在達(dá)到最大迭代次數(shù)時(shí)記錄的時(shí)間如圖3所示。

圖2 加速因子確值實(shí)驗(yàn)結(jié)果

圖3 達(dá)到收斂精度的時(shí)間記錄圖

由圖2可知，當(dāng)加速因子小于3時(shí)，時(shí)間均在30 s以內(nèi)（除了函數(shù)f6），時(shí)間較短；當(dāng)加速因子超過3，且迭代次數(shù)在子種群所允許的最大迭代次數(shù)內(nèi)，時(shí)間均在32 s上下且變化基本不大。由此可知，加速因子的取值應(yīng)該控制在1～3之間。由圖2、圖3可知，當(dāng)加速因子C位于1～3時(shí)，算法達(dá)到最大迭代次數(shù)所花時(shí)間與取其他值相比所花時(shí)間短，而且當(dāng)加速因子C取1.5時(shí)，除函數(shù)f2和f6，此時(shí)算法達(dá)到收斂精度所花的時(shí)間是最短的，故綜合考慮，加速因子C的取值確定為1.5，并應(yīng)用于算法收斂精度實(shí)驗(yàn)和算法迭代次數(shù)比較實(shí)驗(yàn)。

2.3 算法收斂精度實(shí)驗(yàn)

算法收斂精度實(shí)驗(yàn)設(shè)置青蛙種群個(gè)體總數(shù)P=200，子種群數(shù)量m=20，每個(gè)子種群中青蛙個(gè)體n=10，子種群內(nèi)最大進(jìn)化迭代次數(shù)為10次，全局最大進(jìn)化迭代次數(shù)為500，最優(yōu)解空間的維數(shù)為30，算法獨(dú)立運(yùn)行30次，得到的實(shí)驗(yàn)結(jié)果如表2所示，函數(shù)平均值進(jìn)化曲線如圖4～圖9所示［18］。

圖4 函數(shù)f1平均值的進(jìn)化曲線

圖9 函數(shù)f6平均值的進(jìn)化曲線

表2 算法收斂精度的實(shí)驗(yàn)結(jié)果

圖5 函數(shù)f2平均值的進(jìn)化曲線

圖6 函數(shù)f3平均值的進(jìn)化曲線

圖7 函數(shù)f4平均值的進(jìn)化曲線

圖8 函數(shù)f5平均值的進(jìn)化曲線

從表2可以看出，ISFLA對(duì)6個(gè)測(cè)試函數(shù)的尋優(yōu)精度均優(yōu)于SFLA和蟻獅算法（Ant Lion Optimizer，ALO）；與SFLA相比，對(duì)函數(shù)f1、f3、f4、f5、f6的收斂精度明顯提高；對(duì)函數(shù)f2雖然沒有明顯數(shù)量級(jí)上的提升，但是無論是收斂精度最小值還是平均最優(yōu)值都有近1倍的減少，且優(yōu)于SFLA和ALO。從標(biāo)準(zhǔn)差來看，ALO算法標(biāo)準(zhǔn)差較大且不穩(wěn)定；改進(jìn)后的算法標(biāo)準(zhǔn)差相對(duì)較小，在穩(wěn)定程度上要優(yōu)于SFLA和ALO。從圖4～圖9可以看出，雖然ALO算法收斂速度快，但是收斂精度卻達(dá)不到要求；ISFLA在迭代前期可能速度較慢，但是在進(jìn)化50次左右后，收斂速度明顯比SFLA快，且能較快地得到最優(yōu)解。

2.4 算法迭代次數(shù)比較實(shí)驗(yàn)

實(shí)驗(yàn)指定6個(gè)函數(shù)所要達(dá)到的收斂精度。設(shè)置子種群內(nèi)青蛙數(shù)n=10，子種群內(nèi)最大進(jìn)化次數(shù)為10，全局最大進(jìn)化迭代次數(shù)仍然設(shè)置為500。若算法迭代到所要求的最大迭代次數(shù)后，仍沒有達(dá)到指定的精度，則認(rèn)為算法該次沒有收斂，算法同樣獨(dú)立運(yùn)行30次［19］。表3為算法迭代次數(shù)比較實(shí)驗(yàn)的結(jié)果（成功率=達(dá)到指定精度的收斂次數(shù)/總實(shí)驗(yàn)次數(shù)）。

表3 迭代次數(shù)比較實(shí)驗(yàn)的結(jié)果

從表3可以看出，對(duì)函數(shù)f2的求解，ALO、SFLA和ISFLA均沒有在固定迭代次數(shù)達(dá)到收斂精度，但是由算法收斂精度實(shí)驗(yàn)可知，ISFLA在有限迭代次數(shù)里得到的最優(yōu)解要比SFLA優(yōu)1倍；對(duì)函數(shù)f1的求解，雖然ALO和SFLA也能達(dá)到收斂精度，但是成功率較低；對(duì)于其他函數(shù)的求解，ISFLA達(dá)到收斂精度的迭代次數(shù)明顯比SFLA和ALO低，成功率明顯高于SFLA和ALO。

3 結(jié) 論

本文在提出的ISFLA基礎(chǔ)上，引入了中間因子和加速因子，解決了標(biāo)準(zhǔn)算法在優(yōu)化過程中出現(xiàn)的求解精度不高、收斂速度慢等缺陷。在局部搜索的尋優(yōu)過程中，改變步長(zhǎng)更新策略，增加種群的多樣性，拓寬了最優(yōu)解的搜索范圍。通過使用6個(gè)30維測(cè)試函數(shù)，分別設(shè)置算法收斂精度實(shí)驗(yàn)和算法迭代次數(shù)比較實(shí)驗(yàn)進(jìn)行對(duì)比分析，并與ALO算法比較，表明改進(jìn)的算法在收斂精度和收斂速度方面更加突出，尋優(yōu)性能相較于標(biāo)準(zhǔn)算法也有較大提升。