基于函數(shù)變化率的自適應(yīng)變異蛙跳算法

許健　許峰

摘要：針對蛙跳算法進(jìn)化后期種群多樣性下降、易陷于局部最優(yōu)解的缺陷，提出一種自適應(yīng)變異蛙跳算法。其基本思想是：根據(jù)函數(shù)變化率建立一種自適應(yīng)變異選擇機(jī)制，當(dāng)函數(shù)變化率較大時，采用高斯變異提高算法的局部收斂能力；當(dāng)函數(shù)變化率較小，即算法可能陷入局部收斂時，采用柯西變異促使算法跳出局部最優(yōu)。數(shù)值實驗結(jié)果表明，該自適應(yīng)變異選擇機(jī)制不僅提高了蛙跳算法的局部收斂性，而且能在很大程度上避免早熟現(xiàn)象。

關(guān)鍵詞：蛙跳算法；變異；自適應(yīng)；函數(shù)變化度；局部收斂性

DOIDOI：10.11907/rjdk.181434

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2018）009007704

英文標(biāo)題Adaptive Mutation SFLA Based on the Function Change Rate

--副標(biāo)題

英文作者XU Jian， XU Feng

英文作者單位（College of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001，China）

英文摘要Abstract：In light of population diversity decline in the late evolution of shuffled frog leaping algorithm，an adaptive mutation shuffled frog leaping algorithm is put forward.The basic idea is to establish an adaptive selection mechanism according to the function change rate；when the function change rate is large，the Gauss mutation is used to improve the local convergence of the algorithm；when the function change rate is less likely to fall into local convergence，Cauchy mutation is used to urge algorithm jump out local optimum.Numerical experiments show that this adaptive mutation selection mechanism not only improves the local convergence of shuffled frog leaping algorithm，but can also avoid the premature phenomenon to a great extent.

英文關(guān)鍵詞Key Words：SFLA；mutation；adaptive；function change rate；local convergence

0引言

蛙跳算法（Shuffled Frog Leaping Algorithm，SFLA）[1]是一種新型群智能優(yōu)化算法。與其它群智能優(yōu)化算法類似，蛙跳算法不可避免地存在一些缺陷，如局部搜索能力欠佳、搜索效率不高等。因此，學(xué)者們進(jìn)行了大量研究工作。崔玉娟等[2]將混沌映射引入蛙跳算法，改善了蛙跳算法的局部收斂性；吳國偉[3]、銀莉等[4]將蛙跳算法與粒子群算法相結(jié)合，在一定程度上避免了蛙跳算法過早收斂的現(xiàn)象；李盼池等[5]根據(jù)平均目標(biāo)函數(shù)值進(jìn)行自適應(yīng)分組，提高了蛙跳算法的優(yōu)化能力；葉晶晶[6]在蛙跳算法中引入模擬退火思想，有效避免了算法陷入局部最優(yōu)；許波等[7]將蛙跳算法引入遺傳算法，以改善遺傳算法性能；任聰?shù)萚8]將混合蛙跳搜索策略引入人工蜂群粒子群算法，改善了粒子群算法性能。蛙跳算法的應(yīng)用研究也取得了豐碩成果，已被應(yīng)用于流水線調(diào)度、車輛路徑問題、神經(jīng)網(wǎng)絡(luò)優(yōu)化、支持向量機(jī)預(yù)測等多個領(lǐng)域[9-14]。

變異操作作為提高群智能優(yōu)化算法尋優(yōu)能力的一種有效手段，已被成功用于遺傳算法、粒子群算法和蟻群算法等經(jīng)典算法中。在蛙跳算法中，如何利用、改進(jìn)變異操作以提高算法尋優(yōu)性能已被越來越多學(xué)者所重視，特別是對自適應(yīng)變異機(jī)制的研究已成為蛙跳算法的一個研究熱點。葛宇等[15]應(yīng)用混沌序列構(gòu)造一種自適應(yīng)變異算子；李晶晶[16]根據(jù)種群中最優(yōu)個體是否相同給出一種高斯變異與柯西變異的自適應(yīng)選擇方法；劉珂等[17]在蛙跳算法中根據(jù)種群交換次數(shù)設(shè)計一種高斯變異與柯西變異的自適應(yīng)選擇方法；彭平等[18]利用層次分析法自適應(yīng)調(diào)整各影響參數(shù)權(quán)重。

本文在傳統(tǒng)研究工作的基礎(chǔ)上，提出一種基于目標(biāo)函數(shù)變化率的自適應(yīng)變異蛙跳算法，并根據(jù)數(shù)值實驗對該算法進(jìn)行了性能測試。

1蛙跳算法

1.1蛙跳算法數(shù)學(xué)模型

蛙跳算法可以用數(shù)學(xué)語言描述如下：設(shè)有N只青蛙，構(gòu)成一個種群X=（X1，X2，…，Xn），其中每個個體在空間中的坐標(biāo)為Xi=（xi1，xi2， …，xid），坐標(biāo)值可以理解為該個體信息。計算每個個體的適應(yīng)度f（xi1，xi2，…，xid），根據(jù)適應(yīng)度大小按逆序排列，存儲于集合F={（Xi，f（xi1，xi2，…，xid）），i=1，2，…，n}。將種群分割為S個子種群（S1，S2，…， Ss），每個子種群含有P個個體，即N=S*P。在進(jìn)化時，將集合F={（Xi，f（xi1，xi2，…，xid）），i=1，2，…，n}中的所有個體依次放入子種群（S1，S2，…，Ss）中。重復(fù)上述過程，直到將所有個體放入集合S。

將每個子種群中適應(yīng)度最大和最小的個體分別記為Pb和Pw，種群中適應(yīng)度最大的個體記為Xb。每次更新時，僅對Pw進(jìn)行操作以提高其適應(yīng)度。更新方法是：

Ds=r（Pb-Pw）（1）

Pn=Pw+Ds （-Dmax≤Ds≤Dmax）（2）

其中，Dmax是最大步長，Ds是調(diào)整向量，r是（0，1）內(nèi)的隨機(jī)數(shù)。

若新個體Pn的適應(yīng)度大于Pw的適應(yīng)度，則以Pn替代Pw；否則，以Xb替代Pb，重復(fù)以上更新方法。若適應(yīng)度有所改進(jìn)，則替代Pw；否則，隨機(jī)生成新個體替代Pw。重復(fù)上述步驟，直至達(dá)到設(shè)定的最大迭代次數(shù)Ne。

對所有子種群進(jìn)行局部搜索，混合這些子種群后組成一個新種群，并對新種群按適應(yīng)度排序，再將其分割成子種群，然后進(jìn)行更新和局部搜索，直至達(dá)到設(shè)定的最大進(jìn)化代數(shù)Nmax。

1.2蛙跳算法流程

蛙跳算法流程如圖1所示。

2基于函數(shù)變化率的自適應(yīng)變異蛙跳算法

2.1變異算子

“變異”的概念來源于生物學(xué)，指父代與子代間的遺傳學(xué)差異。1975年，美國Michigan大學(xué)的Holland教授提出遺傳算法時，首次將變異操作引入進(jìn)化算法。在進(jìn)化算法中，變異算子主要有以下兩個作用：①當(dāng)進(jìn)化計算進(jìn)行局部搜索時，變異算子可加速算法向最優(yōu)解收斂，提高算法局部搜索能力和收斂速度；②當(dāng)種群的多樣性下降，有陷于局部收斂的趨勢時，變異算子可以提高種群多樣性，引導(dǎo)個體跳出局部最優(yōu)區(qū)域。

蛙跳算法主要采用下列兩種變異算子：

（1）高斯變異算子。在概率統(tǒng)計中，正態(tài)分布也稱為高斯分布，標(biāo)準(zhǔn)正態(tài)分布的概率密度函數(shù)φ（x）及圖形如下：

φ（x）=12πe-x22，-

高斯變異是將一個服從高斯分布的隨機(jī)擾動項加到每個個體上。若用Ni（ni1，ni2，…，nid）表示第i個個體服從高斯分布的隨機(jī)擾動項，則第i個個體的高斯變異可描述為：

Xi=Xi+XiNi，（4）

其中nij是服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)。

（2）柯西變異算子?？挛鞣植际菙?shù)學(xué)期望不存在最著名的例子，在概率統(tǒng)計中占有重要地位，其概率密度函數(shù)f（x）如下：

將一個服從柯西分布的隨機(jī)擾動項加到個體上的操作稱為柯西變異。

從圖3中可以清楚看出，柯西分布在中間區(qū)域部分小于高斯分布，而在兩側(cè)區(qū)域部分大于高斯分布，且兩翼較窄，具有典型的兩翼概率特征，說明柯西分布能以很大概率產(chǎn)生一個較大的隨機(jī)數(shù)，也即是說，柯西分布能以很大概率產(chǎn)生較大的變異步長。

圖3柯西分布密度函數(shù)

根據(jù)上述分析可知，高斯變異具有較強(qiáng)的局部搜索能力，可提高算法收斂速度；柯西變異則具有較強(qiáng)的全局搜索能力，當(dāng)算法可能陷于局部最優(yōu)時，能以很大概率引導(dǎo)個體跳出局部最優(yōu)區(qū)域。

2.2自適應(yīng)變異選擇機(jī)制

如何適當(dāng)?shù)剡x擇高斯變異和柯西變異是蛙跳算法中極具實用價值的問題。傳統(tǒng)自適應(yīng)方法基本上是針對具體問題設(shè)計的，在特定問題中效果較好，但缺乏普適性。因此，本文根據(jù)目標(biāo)函數(shù)變化率，提出下列變異機(jī)制的自適應(yīng)選擇方法[19]：

當(dāng)γij的模小于設(shè)定閾值ε（通常取10-2），即目標(biāo)函數(shù)變化率很小時，表明算法可能陷入局部收斂，此時選用柯西變異引導(dǎo)個體跳出局部收斂，否則選擇高斯變異進(jìn)行局部搜索，以提高算法收斂速度。

2.3基于函數(shù)變化率的自適應(yīng)變異蛙跳算法流程

本文提出一種基于函數(shù)變化率的自適應(yīng)變異蛙跳算法 （Adaptive Mutation SFLA Based on the Function Change Rate，AMSFLA），其流程如下：①給定蛙跳算法參數(shù)，包括：種群規(guī)模N、子種群數(shù)S、子種群內(nèi)部更新次數(shù)Ne、進(jìn)化次數(shù)Nmax，并生成初始種群；②計算每個個體的適應(yīng)度，并根據(jù)適應(yīng)度將這些個體按降序排列，確定Xb；③若滿足停止條件，則輸出結(jié)果，否則進(jìn)行下一步；④計算目標(biāo)函數(shù)的相對變化率，并據(jù)此選擇高斯變異或柯西變異；⑤將種群分成S個子種群；⑥對子種群進(jìn)行局部搜索；⑦將各子種群重新混合組成新種群，轉(zhuǎn)到②。

3數(shù)值實驗與算法性能測試

為了檢測AMSFLA的性能，下面選取4個標(biāo)準(zhǔn)測試函數(shù)，分別用基本蛙跳算法（SFLA）、一種改進(jìn)蛙跳算法（ISFLA）[20]和AMSFLA 3種算法進(jìn)行對比實驗。

（1）De Jong F1。

f1（x1，x2，x3）=∑3i=1x2i-5.12≤xi≤5.12 （i=1，2，3）

（2） De Jong F2。

f2（x1，x2）=100（x21-x2）2+（1-x1）2-2.048≤xi≤2.048 （i=1，2）

（3）Schaffer F6。

f3（x1，x2）=0.5+sin2x21+x22-0.51.0+0.001（x21+x22）2-100≤xi≤100 （i=1，2）

（4） Schaffer F7。

f4（x1，x2）=（x12+x22）0.25[sin2（50（x21+x22）0.1）+1.0]-100≤xi≤100 （i=1，2）

這4個函數(shù)理論上的最優(yōu)值均為0。第1個為簡單函數(shù)，常用于測試算法效率。其余3個均為復(fù)雜多峰函數(shù)，常導(dǎo)致算法陷入局部最優(yōu)，所以可用來測試算法是否發(fā)生早熟。

驗證方法為：首先給出3種算法對4個測試函數(shù)某次運算得到的典型進(jìn)化曲線，以直觀比較3種算法的性能，然后進(jìn)一步從收斂速度、優(yōu)化精度、優(yōu)化結(jié)果穩(wěn)定性及100次優(yōu)化成功率4個方面進(jìn)行定量比較。

圖4顯示，對于f1這種簡單函數(shù)，ISFLA與AMSFLA的優(yōu)化效果幾乎沒有區(qū)別，SFLA的優(yōu)化效果稍差；圖5-圖7則顯示，雖然ISFLA的優(yōu)化效果明顯優(yōu)于SFLA，但在進(jìn)化過程中，還是與SFLA一樣出現(xiàn)了早熟現(xiàn)象，而AMSFLA的優(yōu)化效果不僅遠(yuǎn)優(yōu)于SFLA，而且也明顯優(yōu)于ISFLA，幾乎未出現(xiàn)早熟現(xiàn)象，只是對于f4的優(yōu)化效果與理論值相比略差。

為更進(jìn)一步定量比較SFLA、ISFLA和AMSFLA的性能，表1給出了3種算法優(yōu)化指標(biāo)。其采用相同參數(shù)運行100次，若最優(yōu)值與理論值的誤差在允許誤差內(nèi)，則視為成功。

表1中的各項指標(biāo)顯示，AMSFLA在最優(yōu)解質(zhì)量、算法穩(wěn)定性與收斂速度方面均遠(yuǎn)優(yōu)于SFLA，對于復(fù)雜問題的優(yōu)化能力也明顯優(yōu)于ISFLA。需要特別指出的是，AMSFLA的抗早熟能力得到了很大提高。

4結(jié)語

通過對高斯變異和柯西變異不同特點的分析，本文設(shè)計了一種根據(jù)函數(shù)變化率自適應(yīng)選擇高斯變異和柯西變異的方法，具有較強(qiáng)的普適性，并將其引入蛙跳算法。新算法可實現(xiàn)高斯變異局部搜索能力強(qiáng)和柯西變異可避免早熟兩個優(yōu)勢的互補。數(shù)值實驗結(jié)果顯示，該算法不僅局部搜索能力強(qiáng)、解的精度高，而且可在很大程度上克服蛙跳算法易陷于局部收斂的缺陷。

雖然基本蛙跳算法已被證明是全局收斂[16]，但本文在基本蛙跳算法中引入了高斯變異和柯西變異，因此其理論上的收斂性尚有待研究。另外，由于本文算法中添加了目標(biāo)函數(shù)變化率過程，所以運行效率有所下降。然而，這恰好符合優(yōu)化中“沒有免費午餐”的原理。

參考文獻(xiàn)參考文獻(xiàn)：

[1]EUSUFF M M，LANSEYLE K F.Optimization of water distribution network design using shuffled frog leaping algorithm [J].Journal of Water Resource Planning and Management，2003，129（3）：210225.

[2]崔玉娟，察豪，田斌.改進(jìn)的混合蛙跳算法在雷達(dá)網(wǎng)部署中的應(yīng)用[J].海軍工程大學(xué)學(xué)報，2015，27（1）：108112.

[3]吳國偉，趙艷玲，王龍.基于蛙跳算法的離散粒子群算法端元提取[J].中國圖像圖形學(xué)報，2015，20（5）：724732.

[4]銀莉，靳雁霞，張曉聞.粒子群蛙跳算法在圖像相關(guān)反饋中的研究[J].微電子學(xué)與計算機(jī)，2017，34（2）：97101.

[5]李盼池，盧愛平.自適應(yīng)分組量子衍生蛙跳算法[J].系統(tǒng)工程理論與實踐，2016，36（5）：13061317.

[6]葉晶晶.蛙跳算法的改進(jìn)及在車輛路徑問題中的研究[D].廣州：廣東工業(yè)大學(xué)，2016.

[7]許波，彭志平，余建平.基于蛙跳思想的量子編碼遺傳算法[J].中國工程科學(xué)，2014，16（3）：108112.

[8]任聰，葛洪偉，楊金龍.引入混合蛙跳搜索策略的人工蜂群粒子群算法[J].計算機(jī)工程與應(yīng)用，2015，51（22）：3841.

[9]潘玉霞，潘全科，李俊青.蛙跳優(yōu)化算法求解多目標(biāo)無等待流水線調(diào)度[J].控制理論與應(yīng)用，2011，28（10）：13631370.

[10]張思亮，葛洪偉.粒子群和蛙跳的混合算法求解車輛路徑問題[J].計算機(jī)工程與應(yīng)用，2011，47（21）：246248.