基于混合蛙跳算法的研究

葛 鵬，李冬林，楊俊勝，方棟澤，代永強

（甘肅農業大學信息科學技術學院計算機科學與技術專業，甘肅 蘭州 730070）

0 引言

混合蛙跳算法是由Eusuff和Lansey為解決組合優化問題于2003年首次提出的，目的就是為了找出最優組合[1]，混合蛙跳算法的特點為概念簡單明了，需要調整的參數少，魯棒性強，解決問題時計算速度快，尋找最優解的能力比普通算法強以及最為重要的易于實現的特點。

混合蛙跳算法的背景是在一片沼澤地里青蛙利用沼澤地中離散分布的石塊去尋找更多食物，每只青蛙個體之間都進行信息的交流[2]，通過整個種群的信息交流，來使每只青蛙得到最多的食物。轉換為算法的思想，即為使得每個解都達到最優，最終使整個算法達到最優解，即由局部最優到全局最優的過程。蛙跳算法對于解決算法當中的n后問題和最短路徑問題等有顯著效果。

1 混合蛙跳算法的實現過程

Step0：對每一個個體初始化，確定試驗次數，混合迭代次數，個體總數，族群數，個體維數，族群內更新次數的值，并調用測試函數對初始化所產生的解進行優化。

Step1：以 main函數進入算法，按照適應度降序對全部個體進行排序和族群劃分[3]，同時對解進行排序、分組為M，每個組內有I個個體。

Step2：對某個群組中的個體進行重新排序，對排序分組的族群進行局部更新尋找局部最優pb，局部最差pw[4]。

Step3：重復Step2，直至所有族群均被更新。

Step4：從局部最優中尋找全局最優并將值賦給px，將 pop[M][I]（排序后的族群）復制到 individual。

Step5：對結果求平均極值及標準差，輸出標準差及平均值極值，得到最終的實驗結果。

圖1 混合蛙跳算法流程圖Fig.1 Mixed frog jump algorithm flowchart

2 測試函數

表1 測試函數Tab.1 Test functions

3 算法各參數的改變對函數的影響

3.1 族群內更新次數對各函數平均極值的影響

圖2 族群內更新次數對平均極值的影響Fig.2 The effects of the number of updates in the population on the mean extremum

圖3 族群內更新次數對平均極值的影響Fig.3 The effects of the number of updates in the population on the mean extremum

圖4 族群內更新次數對平均極值的影響Fig.4 The effects of the number of updates in the population on the mean extremum

圖5 族群內更新次數對平均極值的影響Fig.5 The effects of the number of updates in the population on the mean extremum

3.2 維度對各函數平均極值的影響

圖6 維度對平均極值的影響Fig.6 The effect of dimensions on the mean extremum

圖7 維度對平均極值的影響Fig.7 The effect of dimensions on the mean extremum

圖8 維度對平均極值的影響Fig.8 The effect of dimensions on the mean extremum

圖9 維度對平均極值的影響Fig.9 The effect of dimensions on the mean extremum

3.3 維度對各函數標準差的影響

圖10 維度對標準差的影響Fig.10 The effect of dimension on standard deviation

圖11 維度對標準差的影響Fig.11 The effect of dimension on standard deviation

圖12 維度對標準差的影響Fig.12 The effect of dimension on standard deviation

圖13 維度對標準差的影響Fig.13 The effect of dimension on standard deviation

3.4 族群內更新次數對各函數標準差的影響

圖14 族群內更新次數對標準差的影響Fig.14 The effect of the number of population updates on the standard deviation

圖15 族群內更新次數對標準差的影響Fig.15 The effect of the number of population updates on the standard deviation

圖16 族群內更新次數對標準差的影響Fig.16 The effect of the number of population updates on the standard deviation

4 結論

在保持試驗次數，混合迭代次數，個體總數，族群數，族群中的個體數不變時，利用四種測試函數對算法進行研究，通過測試發現不同函數對于算法優化有著不同的效果。圖2至圖9中表明：當族群內更新次數增大時，f1、f3和f4函數的平均極值逐級遞減，向理論最優值靠攏，算法優化效果較好。而當維度數增大時，f1、f3函數的平均極值增大，f4函數遞減。從圖10至圖17中表明：維度增大時，f1、f3、f4三種函數的標準差均增加。族群內更新次數增大時，f1、f3函數標準呈遞減趨勢，f4函數總體遞減但中間產生突變。但是，無論是維度增大還是族群內更新次數的增加，f2函數對算法的平均極值和標準差保持不變。本實驗的不足之處在于僅僅只是研究了混合蛙跳算法兩個相關參數的改變對混合蛙跳算法的影響，試驗次數相對較少，后續會繼續改進。

5 結束語

圖17 族群內更新次數對標準差的影響Fig.17 The effect of the number of population updates on the standard deviation

數據無處不在，對于數據的處理和整合以成為現實生活中不可避免的問題，混合蛙跳算法則是在對各類數據的整合過程中尋求其對于解決問題的最好方式之一。當今世界，和平與發展是時代主旋律，面對各種資源分配不均導致地區經濟發展的不平衡，以及資源的分配不均，應用普通的優化算法例如像梯度算法，Hessian矩陣，拉格朗日乘數，單純形法[6]，梯度下降法等一系列算法已經不能解決對于各類數據處理整合優化的需要。因此，需要尋找優化性能更為強大的算法。相對于普通的優化算法，混合蛙跳算法具有設置參數少，簡單易于理解，魯棒性強的特點[7]，對于解決多種數據的實時變化和最優解的尋求問題有著明顯的優勢。