王曉彬，鄒海榮

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

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

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

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

1 SFLA

1.1 算法原理

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

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

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

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

圖1 SFLA流程

1.2 改進的SFLA

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

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

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

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

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

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

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

2 仿真實驗及結(jié)果分析

2.1 實驗設(shè)置

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

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

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

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

2.2 加速因子確值實驗

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

圖2 加速因子確值實驗結(jié)果

圖3 達到收斂精度的時間記錄圖

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

2.3 算法收斂精度實驗

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

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

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

表2 算法收斂精度的實驗結(jié)果

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

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

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

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

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

2.4 算法迭代次數(shù)比較實驗

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

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

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

3 結(jié) 論

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