改進混合蛙跳算法的研究

高建瓴，潘成成，吳建華，陳婭先，王 許

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025)

蛙跳算法(Shuffled Frog Leading Algorithm)是一種啟發(fā)式算法，通過啟發(fā)式函數(shù)進行啟發(fā)式搜索，從而找到組合最優(yōu)問題的解?；旌贤芴惴ǖ倪\行原理從仿生上來說可以這么認為[1]：在一個池塘，有若干塊石頭，青蛙可以落在石頭上，每塊石頭上可以獲取到的食物數(shù)量是不同的，在池塘中有很多只青蛙，也有很多塊石頭，青蛙間可以交流，這樣所有青蛙就都會往自己所在蛙群中所知道的最多食物的方向跳，或往全部青蛙中食物最多的方向跳，最終在池塘中找到最多食物的石頭。他結(jié)合了以遺傳為基礎(chǔ)的memetic算法和以社會行為為基礎(chǔ)的粒子群優(yōu)化算法的優(yōu)點[2],其顯著特點是具有局部搜索與全局信息混合的協(xié)同搜索策略，尋優(yōu)能力強，易于編程實現(xiàn)。

雖然混合蛙跳算法具有概念簡單，調(diào)整的參數(shù)少，全局搜索尋優(yōu)能力強，易于實現(xiàn)的特點。但是該算法與其他群智能優(yōu)化算法類似也存在著一些缺點，求解精度不高、收斂速度慢、算法易陷入局部最優(yōu)的問題。針對這些問題，近年來也有不少的國內(nèi)外學(xué)者對其進行研究改進，張新明等[3]提出了將每次只更新組內(nèi)最差青蛙的方式改為更新組內(nèi)所有青蛙的方式，增大了獲得優(yōu)質(zhì)解的概率，提高可操作性和優(yōu)化效率。趙紅星等[4]提出了對青蛙的覓食機制和更新迭代公式重新定義，青蛙的第一步向組內(nèi)其它蛙搜索，第二步向組內(nèi)最優(yōu)蛙搜索，第三步向全局最優(yōu)蛙搜索，提高混合蛙跳算法的全局和局部搜索能力。戴月明等[5]提出一種新的協(xié)同進化混合蛙跳算法，在局部搜索中對最差蛙的更新引入平均值，擴大青蛙搜索空間；在全局搜索中采取精英群自學(xué)進化機制，對精英空間進行精細搜索，提升全局搜索能力。李敏楠等[6]提出通過引入自適應(yīng)同步因子，改變局部搜索蛙跳規(guī)則，從而增加種群的多樣性。周林錦[7]提出對初始種群引入Tent混沌來改進，在最差個體更新中引入擾動的柯西因子，提高算法的尋有能力。雖然以上文獻在一定程度上提升了算法的優(yōu)化能力，但隨著更多復(fù)雜優(yōu)化問題和嚴格實時性要求的提出，需要求解精度更高、優(yōu)化性能更好的混合蛙跳算法，因此，對于混合蛙跳算法的改進仍然有較大空間。本文在傳統(tǒng)算法的基礎(chǔ)上，通過引入自適應(yīng)同步算子和慣性權(quán)重系數(shù)，提出一種新的混合蛙跳算法，改變個體青蛙更新公式，提高算法的求解精度、收斂速度、避免陷入局部最優(yōu)。

1 標準混合蛙跳算法

在混合蛙跳算法中，種群被分為若干個子群(memeplex)，每一個子群包括一定數(shù)量的青蛙。不同的子群具有不同的文化，分別進行局部搜索。在每個子群中，每只青蛙都有自己的想法，并且受到其他青蛙想法的影響，通過文化進化來發(fā)展。這樣經(jīng)過一定的文化進化以及跳躍過程，這些想法思路就在各個子群中傳播開來，然后局部搜索和跳躍，直到收斂或滿足標準為止。

(1)

式中：Di表示該子群中適應(yīng)度最差解xw的第i次更新步長，Dmax是青蛙移動的最大步長，其中rand()為0-1之間的隨機數(shù)。通過對最差解xw的更新得到新解xnew，即跟新最差青蛙的位置，如果新解的適應(yīng)度值優(yōu)于原來的最差解，就用xnew代替xw，否則，就用全局最優(yōu)解xg替代式(1)中的局部最優(yōu)解xb得到新的更新式(2)，對最差解進行更新。

(2)

如果新位置xnew優(yōu)于原來的解xw，就用xnew替代xw，否則，隨機生成一個新解xnew代替xw；不斷循環(huán)以上操作，直到滿足局部迭代次數(shù)，再對下一組子群進行更新。對所有子群都完成局部搜索后，將全部的青蛙個體重新混合、排序和分組，進行下一輪的局部搜索，直到滿足全局混合迭代次數(shù)G，進化結(jié)束，輸出全局最優(yōu)值[10]。

2 改進的混合蛙跳算法

2.1 自適應(yīng)同步因子

在混合蛙跳算法中種群進行局部搜索是算法尋優(yōu)的核心步驟，在局部搜索過程中，青蛙移動距離的大小對于算法的運算速度和搜索精度十分重要[11]。步長較小有利于精細搜索，但尋優(yōu)速度比較慢且容易陷入局部最優(yōu)值；步長較大可使青蛙容易在全局范圍內(nèi)展開搜索，提高搜索速度，但同時容易在搜索過程中跳過全局最優(yōu)解所在位置。在標準混合蛙跳算法中，最差解的移動步長是隨機更新的，這種隨機的跳躍距離使最優(yōu)解的引導(dǎo)作用無法充分發(fā)揮，容易使算法陷入局部極值或跳過全局極值[12]。因此，本文在算法局部搜索時，引入了動態(tài)自適應(yīng)同步因子；當自適應(yīng)移動因子為增函數(shù)時，在更新初始階段移動距離比較小，對周圍進行精細搜索，保持種群的多樣性，在更新迭代中后期，移動步長增大，保持算法的全局搜索能力，避免算法陷入局部極值。

在標準混合蛙跳算法更新公式中的移動因子為rand()，是0～1之間的隨機數(shù)，所以采用余弦函數(shù)為模型，設(shè)計了動態(tài)自適應(yīng)移動因子如下：

(3)

其中N表示子種群中最大進化代數(shù)，k表示子種群內(nèi)當前進化代數(shù)，用自適應(yīng)移動因子w1替代標準蛙跳算法更新公式中的rand()。w1在[-π/2,0]范圍內(nèi)逐漸遞增，且在青蛙搜索接近結(jié)束時，保持平緩的變化率，有助于算法在搜索完成時速度以較小的變化率平穩(wěn)進行搜索。

2.2 慣性權(quán)重系數(shù)

為了拓展搜索空間，提高算法的尋優(yōu)能力以及收斂速度，在標準混合蛙跳算法局部搜索的基礎(chǔ)上，引入上一次的移動步長的慣性權(quán)重系數(shù)，表示對過去經(jīng)驗的記憶[13]，調(diào)節(jié)青蛙移動步長，在擴大青蛙的搜索區(qū)域的同時也加快了收斂速度，具體的慣性權(quán)重系數(shù)如式(4)所示：

ω2=(ωmax-ωmin)k/N

(4)

其中wmax和wmin是權(quán)重系數(shù)的最大值和最小值，k為子群當前進化次數(shù)，N為子群最大迭代數(shù)。如果w2較大，則算法全局搜索能力較好，反之，如果w2較小，則有利于算法局部搜索能力，因此w2的大小至關(guān)重要。經(jīng)過實驗表明，本文的wmax和wmin分別取值0.9和0.4。如果上一次的移動距離比較理想就保留，反之，就消除歷史不良影響，去掉上一次的移動距離，使收斂速度加快。且慣性權(quán)重系數(shù)在初始階段變化率大，有助于提升算法局部搜索的效率；在中后期階段慣性權(quán)重系數(shù)變化率小，使算法進行精細的搜索，利于找到最優(yōu)解。

2.3 改進混合蛙跳算法流程

本文改進混合蛙跳算法流程如下：

Step1：隨機初始化青蛙種群和移動步長。在可行解空間生成F個維度為S的青蛙{x1,x2,…，xF}，隨機初始化移動距離Di′，Di′∈[-Dmin,Dmax]。

Step2：劃分子群。計算每一個解的適應(yīng)度值，將其降序排列，并將排序后的最優(yōu)適應(yīng)度的解記為xg。按照規(guī)則劃分子群，標記群內(nèi)最優(yōu)可行解xb和最差可行解xw。

Step3：局部搜索。按式(5)對子群內(nèi)的xw進行更新：

(5)

如果產(chǎn)生的新解優(yōu)于舊解，就用新解替換子種群中最差解；否則，就用式(6)對最差解進行迭代更新，式中不包括上一次的移動步長，因為根據(jù)式(5)更新后的解沒有憂于原解，說明上一次的移動距離不夠理想，所以要去除歷史不好影響，加快收斂速度，使青蛙迅速移到最優(yōu)解附近。

(6)

如果新解優(yōu)于舊解，就用產(chǎn)生新的解替換子種群中最差解，否則，隨機產(chǎn)生一個新解替換原來最差解，并隨機生成Di'，Di'∈[-Dmax,Dmax]。

Step4：當所有子種群更新完成后，對所有子種群的青蛙重新進行混合，形成新的族群，返回Step2，直到達到設(shè)定的全局最大迭代次數(shù)，算法終止，輸出最后的全局最優(yōu)解 。如圖1所示，為改進蛙跳算法的程序流程圖。

3 實驗結(jié)果與分析

3.1 實驗設(shè)置

為了驗證改進混合蛙跳算法(ISFLA)的收斂性能，本文選用6個15維的測試函數(shù)進行實驗分析，并與標準混合蛙跳算法(SFLA)進行對比實驗。各函數(shù)的表達式、搜索范圍以及理論最優(yōu)值如表1所示[14]。表中f1(x)和f2(x)為單峰函數(shù)，通常用來考察算法的收斂速度，f3(x) 到f6(x)這四個測試函數(shù)為復(fù)雜多峰函數(shù)，可以檢驗算法的搜索性能，六個測試函數(shù)的理想最優(yōu)值都為0。

圖1 程序流程圖Fig.1 Program flow char

本文為了提高實驗的可比較性，設(shè)置相同的實驗參數(shù)，具體如下：種群青蛙總數(shù)為F=400，子群數(shù)目為m=20，子種群中青蛙數(shù)目為n=20，局部更新迭代數(shù)目為N=30，全局更新迭代次數(shù)為G=300，最大移動步長為Dmax=1。軟件使用Matlab，操作系統(tǒng)為Windows10，硬件配置CPU為4 G，硬盤容量1000 G。

3.2 結(jié)果分析

為了使實驗結(jié)果更加客觀準確，使算法單獨運行30次，取30次實驗結(jié)果的最好值、最差值、平均值作為參照指標進行對比分析[15]，如表2所示。同時為了可以直觀的看出兩種算法的尋優(yōu)能力，給出如圖2所示各測試函數(shù)的進化曲線圖。

表1 測試函數(shù)Tab.1 Test function

表2 測試函數(shù)的尋優(yōu)結(jié)果Tab.2 Optimization results of test functions

通過表2可以看出，在相同的設(shè)置參數(shù)下，本文算法在最差值、最好值、平均值都優(yōu)于標準混合蛙跳算法；在表2中，最好值是運行算法30次結(jié)果中最優(yōu)的一次，最差值為運行算法30次中結(jié)果最差的一次，平均值則是對30次結(jié)果求平均，表1中的6個測試函數(shù)的最優(yōu)值為0，ISFLA在六個測試函數(shù)中無論是最好值、最差值還是平均值都比SFLA更接近理想值0；且在f3(x)函數(shù)運行的30次結(jié)果中最好值達到了函數(shù)的最優(yōu)值，在f6(x)函數(shù)的運行結(jié)果中每次均能收斂到最優(yōu)解，而SFLA在各個測試函數(shù)中都出現(xiàn)了早熟收斂，在6個測試函數(shù)中30次運行結(jié)果沒有一次是收斂到最優(yōu)值0，通過表2的對比，可以明顯看出ISFLA比SFLA的收斂精度高，尋優(yōu)效果好。圖2 是SFLA和ISFLA在6個測試函數(shù)中的進化曲線圖，縱坐標表示函數(shù)最優(yōu)解，橫坐標表示種群的總進化代數(shù)，從圖2中可以很直觀的發(fā)現(xiàn)，ISFLA在f1(x)到f5(x)五個測試函數(shù)中進化曲線一開始就體現(xiàn)出比SFLA跟優(yōu)秀的尋優(yōu)能力，尋優(yōu)值都幾乎接近函數(shù)最優(yōu)值0，并且收斂速度快，在f6(x)函數(shù)中雖然ISFLA剛開始的尋優(yōu)精度沒有SFLA好，但是當進化到50代左右時，ISFLA的尋優(yōu)精度變得比SFLA好并且迅速找到最優(yōu)解，SFLA則在各個測試函數(shù)中都出現(xiàn)了不同程度的早熟收斂，因此本文改進的混合蛙跳算法在求解精度、收斂速度上比標準混合蛙跳算法有了大幅度的提高。這是因為在傳統(tǒng)蛙跳算法中加入自適應(yīng)移動因子和慣性權(quán)重系數(shù)之后，保持了種群的多樣性，擴大搜索范圍，提升算法搜索效率以及搜索能力，說明本文對傳統(tǒng)混合蛙跳算法的改進是有效的。

圖2 各測試函數(shù)的優(yōu)化對比結(jié)果圖Fig.2 Optimization comparison results of each test function

4 結(jié)論

本文提出的一種基于自適應(yīng)移動因子、慣性權(quán)重系數(shù)的混合蛙跳算法，有效地改善算法在優(yōu)化過程中出現(xiàn)的求解精度不高、收斂速度慢、易陷入局部最優(yōu)等缺陷。在局部搜索過程中改變蛙跳策略，擴大算法的局部搜索范圍，保持種群多樣性，通過6個15維測試函數(shù)的實驗對比分析，表明本文改進的算法較傳統(tǒng)混合蛙跳算法尋優(yōu)精度更高，算法尋優(yōu)性能更好。