改進(jìn)混合蛙跳算法的研究

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

摘要：針對傳統(tǒng)混合蛙跳算法（SFLA）在優(yōu)化過程中出現(xiàn)的求解精度不高、收斂速度慢、算法易陷入局部最優(yōu)的問題，本文經(jīng)過改變種群個(gè)體的位置更新公式，提出一種改進(jìn)混合蛙跳算法（IS，F(xiàn)LA）。在種群個(gè)體位置更新公式中，引入自適應(yīng)同步因子和慣性權(quán)重系數(shù)。通過引入自適應(yīng)同步因子，控制青蛙尋優(yōu)過程中的移動(dòng)步長，改進(jìn)算法的局部搜索范圍，保持種群的多樣性。通過引入慣性權(quán)重系數(shù)，加入上一次的移動(dòng)距離，表示對過去的經(jīng)驗(yàn)記憶，加快搜索速度。通過對6個(gè)測試函數(shù)的實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的混合蛙跳算法相較于傳統(tǒng)混合蛙跳算法具有較好的尋優(yōu)性能。

關(guān)鍵詞：混合蛙跳算法：自適應(yīng)同步因子：慣性權(quán)重系數(shù)：局部搜索

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A

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

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

1標(biāo)準(zhǔn)混合蛙跳算法

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

2改進(jìn)的混合蛙跳算法

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

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

3.2結(jié)果分析

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

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

4 結(jié)論

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