葛 鵬，李冬林，楊俊勝，方棟澤，代永強(qiáng)

（甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)，甘肅 蘭州 730070）

0 引言

混合蛙跳算法是由Eusuff和Lansey為解決組合優(yōu)化問(wèn)題于2003年首次提出的，目的就是為了找出最優(yōu)組合[1]，混合蛙跳算法的特點(diǎn)為概念簡(jiǎn)單明了，需要調(diào)整的參數(shù)少，魯棒性強(qiáng)，解決問(wèn)題時(shí)計(jì)算速度快，尋找最優(yōu)解的能力比普通算法強(qiáng)以及最為重要的易于實(shí)現(xiàn)的特點(diǎn)。

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

1 混合蛙跳算法的實(shí)現(xiàn)過(guò)程

Step0：對(duì)每一個(gè)個(gè)體初始化，確定試驗(yàn)次數(shù)，混合迭代次數(shù)，個(gè)體總數(shù)，族群數(shù)，個(gè)體維數(shù)，族群內(nèi)更新次數(shù)的值，并調(diào)用測(cè)試函數(shù)對(duì)初始化所產(chǎn)生的解進(jìn)行優(yōu)化。

Step1：以 main函數(shù)進(jìn)入算法，按照適應(yīng)度降序?qū)θ總€(gè)體進(jìn)行排序和族群劃分[3]，同時(shí)對(duì)解進(jìn)行排序、分組為M，每個(gè)組內(nèi)有I個(gè)個(gè)體。

Step2：對(duì)某個(gè)群組中的個(gè)體進(jìn)行重新排序，對(duì)排序分組的族群進(jìn)行局部更新尋找局部最優(yōu)pb，局部最差pw[4]。

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

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

Step5：對(duì)結(jié)果求平均極值及標(biāo)準(zhǔn)差，輸出標(biāo)準(zhǔn)差及平均值極值，得到最終的實(shí)驗(yàn)結(jié)果。

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

2 測(cè)試函數(shù)

表1 測(cè)試函數(shù)Tab.1 Test functions

3 算法各參數(shù)的改變對(duì)函數(shù)的影響

3.1 族群內(nèi)更新次數(shù)對(duì)各函數(shù)平均極值的影響

圖2 族群內(nèi)更新次數(shù)對(duì)平均極值的影響Fig.2 The effects of the number of updates in the population on the mean extremum

圖3 族群內(nèi)更新次數(shù)對(duì)平均極值的影響Fig.3 The effects of the number of updates in the population on the mean extremum

圖4 族群內(nèi)更新次數(shù)對(duì)平均極值的影響Fig.4 The effects of the number of updates in the population on the mean extremum

圖5 族群內(nèi)更新次數(shù)對(duì)平均極值的影響Fig.5 The effects of the number of updates in the population on the mean extremum

3.2 維度對(duì)各函數(shù)平均極值的影響

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

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

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

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

3.3 維度對(duì)各函數(shù)標(biāo)準(zhǔn)差的影響

圖10 維度對(duì)標(biāo)準(zhǔn)差的影響Fig.10 The effect of dimension on standard deviation

圖11 維度對(duì)標(biāo)準(zhǔn)差的影響Fig.11 The effect of dimension on standard deviation

圖12 維度對(duì)標(biāo)準(zhǔn)差的影響Fig.12 The effect of dimension on standard deviation

圖13 維度對(duì)標(biāo)準(zhǔn)差的影響Fig.13 The effect of dimension on standard deviation

3.4 族群內(nèi)更新次數(shù)對(duì)各函數(shù)標(biāo)準(zhǔn)差的影響

圖14 族群內(nèi)更新次數(shù)對(duì)標(biāo)準(zhǔn)差的影響Fig.14 The effect of the number of population updates on the standard deviation

圖15 族群內(nèi)更新次數(shù)對(duì)標(biāo)準(zhǔn)差的影響Fig.15 The effect of the number of population updates on the standard deviation

圖16 族群內(nèi)更新次數(shù)對(duì)標(biāo)準(zhǔn)差的影響Fig.16 The effect of the number of population updates on the standard deviation

4 結(jié)論

在保持試驗(yàn)次數(shù)，混合迭代次數(shù)，個(gè)體總數(shù)，族群數(shù)，族群中的個(gè)體數(shù)不變時(shí)，利用四種測(cè)試函數(shù)對(duì)算法進(jìn)行研究，通過(guò)測(cè)試發(fā)現(xiàn)不同函數(shù)對(duì)于算法優(yōu)化有著不同的效果。圖2至圖9中表明：當(dāng)族群內(nèi)更新次數(shù)增大時(shí)，f1、f3和f4函數(shù)的平均極值逐級(jí)遞減，向理論最優(yōu)值靠攏，算法優(yōu)化效果較好。而當(dāng)維度數(shù)增大時(shí)，f1、f3函數(shù)的平均極值增大，f4函數(shù)遞減。從圖10至圖17中表明：維度增大時(shí)，f1、f3、f4三種函數(shù)的標(biāo)準(zhǔn)差均增加。族群內(nèi)更新次數(shù)增大時(shí)，f1、f3函數(shù)標(biāo)準(zhǔn)呈遞減趨勢(shì)，f4函數(shù)總體遞減但中間產(chǎn)生突變。但是，無(wú)論是維度增大還是族群內(nèi)更新次數(shù)的增加，f2函數(shù)對(duì)算法的平均極值和標(biāo)準(zhǔn)差保持不變。本實(shí)驗(yàn)的不足之處在于僅僅只是研究了混合蛙跳算法兩個(gè)相關(guān)參數(shù)的改變對(duì)混合蛙跳算法的影響，試驗(yàn)次數(shù)相對(duì)較少，后續(xù)會(huì)繼續(xù)改進(jìn)。

5 結(jié)束語(yǔ)

圖17 族群內(nèi)更新次數(shù)對(duì)標(biāo)準(zhǔn)差的影響Fig.17 The effect of the number of population updates on the standard deviation

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