姜建國， 張麗媛， 蘇 仟， 鄧凌娟， 劉夢(mèng)楠

(西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710071)

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)是一種較新的基于群體智能的元啟發(fā)式全局優(yōu)化算法，由Eusuff和Lansey于2003年受青蛙覓食過程的啟發(fā)而提出[1]．該算法結(jié)合了模因算法(Memetic Algorithm，MA)和粒子群算法(Particle Swarm Optimization，PSO)兩者的優(yōu)點(diǎn)，具有結(jié)構(gòu)簡單、收斂速度快和全局尋優(yōu)能力強(qiáng)等特點(diǎn)[2]．但在標(biāo)準(zhǔn)SFLA中，初始種群通過隨機(jī)方式產(chǎn)生，種群分布不是很均勻;局部更新策略中，子群當(dāng)前最差值對(duì)其進(jìn)化行為的影響在進(jìn)化過程中恒定不變，使得種群在迭代后期需要多次迭代才能收斂到全局最優(yōu);隨著進(jìn)化代數(shù)的增加，算法進(jìn)化速度會(huì)降低甚至停滯，陷入早熟．

文獻(xiàn)[3-5]均對(duì)算法進(jìn)行了一些改進(jìn)．其中，文獻(xiàn)[3]用基于對(duì)立學(xué)習(xí)的策略產(chǎn)生初始種群，提高了候選解的質(zhì)量，但是SFLA與差分進(jìn)化算法的交替搜索在一定程度上增加了算法的執(zhí)行時(shí)間，降低了算法的執(zhí)行效率；文獻(xiàn)[4]在子群局部搜索中引入搜索加速因子，提高了算法的尋優(yōu)能力，但改進(jìn)后的局部搜索算法本質(zhì)上仍為線性搜索算法，不利于算法快速收斂于最優(yōu)解；文獻(xiàn)[5]在基本蛙跳算法的全局搜索過程中加入自適應(yīng)混沌變異操作，提高了算法的尋優(yōu)能力．但是當(dāng)求解問題的維數(shù)增加時(shí)，計(jì)算量與之成正比，降低了算法的執(zhí)行效率．

為此，筆者綜合考慮初始化、局部搜索和全局搜索，提出了一種利用動(dòng)態(tài)搜索策略的混合蛙跳算法(Shuffled Frog Leaping Algorithm using Dynamic Searching Strategy，DSFLA)，即通過隨機(jī)化均勻設(shè)計(jì)方法[6]構(gòu)造初始種群，使算法的初始種群能更均勻地分布于可行域中；引入影響因子，動(dòng)態(tài)地改變子群當(dāng)前最差值對(duì)其進(jìn)化行為的影響，使算法快速收斂到全局最優(yōu)解；根據(jù)相鄰兩次混合迭代后種群的適應(yīng)度方差差值，判斷種群是否陷入早熟，并通過對(duì)全局最優(yōu)值微擾，使算法跳出局部最優(yōu)．實(shí)驗(yàn)結(jié)果表明，DSFLA既能提高收斂精度，又能加快收斂速度，對(duì)于經(jīng)典的評(píng)價(jià)優(yōu)化算法執(zhí)行效率的測(cè)試函數(shù)，均取得了比較好的結(jié)果．

1 標(biāo)準(zhǔn)SFLA

1.1 算法描述

混合蛙跳算法是一種受自然生物模仿啟示而產(chǎn)生的群體進(jìn)化算法，它模擬青蛙群體尋找食物時(shí)，按子群分類進(jìn)行信息交換的過程，將全局搜索與子群局部搜索相結(jié)合，使算法朝著全局最優(yōu)解的方向進(jìn)化[1]．

在SFLA中，種群由虛擬的青蛙組成，每只青蛙代表1個(gè)候選解．種群被分成多個(gè)子群，每個(gè)子群包含一定數(shù)量的青蛙，稱為1個(gè)memeplex．不同的memeplex可以看做是具有不同文化的青蛙子群，其中每只青蛙都有自己的文化，同時(shí)其行為又會(huì)受到其他青蛙行為的影響．每個(gè)memeplex內(nèi)部執(zhí)行局部搜索，在已定義的局部搜索次數(shù)結(jié)束后，所有的memeplex被混合，形成新的種群，使得各個(gè)memeplex間的信息得到全局交換．局部搜索和全局信息交換交替進(jìn)行，直到滿足收斂條件(一定的收斂精度或最大迭代次數(shù))為止．

1.2 求解無約束函數(shù)優(yōu)化問題的步驟

(1) 初始化．對(duì)于一個(gè)D維優(yōu)化問題，在其可行域Ω?RD中隨機(jī)生成P個(gè)候選解，記為初始種群S= (X1，X2， …，XP)，用Xi= (xi1，xi2， …，xiD)表示第i(1≤i≤P)個(gè)候選解．

(2) 子群劃分．計(jì)算每個(gè)候選解的適應(yīng)度值f(Xi)(即目標(biāo)函數(shù)值)，并按降序排序，然后將其分到M個(gè)子群中．具體方法為：第1個(gè)候選解分到第1個(gè)子群中，第2個(gè)候選解分到第2個(gè)子群中，第M個(gè)候選解分到第M個(gè)子群中，第M+1 個(gè)候選解分到第1個(gè)子群中，第M+2 個(gè)候選解分到第2個(gè)子群中，依此完成P個(gè)候選解的分組．

(3) 子群局部搜索．設(shè)一個(gè)子群中的最好青蛙為Xb，最差青蛙為Xw，整個(gè)種群中的最好青蛙為Xg．對(duì)每個(gè)子群進(jìn)行局部搜索，即對(duì)子群中的Xw進(jìn)行更新，更新策略如下:

其中，Di是步長更新值，int[x]是對(duì)x取整；r為(0， 1)之間的隨機(jī)數(shù)，其有效位依所計(jì)算的問題和仿真環(huán)境而定；Dmax是允許青蛙移動(dòng)的最大距離．

(4) 全局信息交換．當(dāng)各個(gè)子群完成局部搜索后，混合所有的子群，重復(fù)執(zhí)行步驟(2)、(3)和(4)，直到滿足終止條件為止．

2 改進(jìn)的SFLA

針對(duì)標(biāo)準(zhǔn)SFLA中存在的問題，對(duì)初始種群的構(gòu)造、局部搜索更新策略和早熟收斂均進(jìn)行了改進(jìn)，提出了一種改進(jìn)的混合蛙跳算法．

2.1 基于隨機(jī)化均勻設(shè)計(jì)方法的初始種群的構(gòu)造

SFLA是一種基于種群的元啟發(fā)式全局優(yōu)化算法，初始種群的好壞對(duì)該算法的搜索性能具有非常重要的影響．當(dāng)種群中的青蛙在其搜索空間分布不均勻時(shí)，會(huì)降低SFLA的全局搜索能力．經(jīng)典SFLA中，初始種群是隨機(jī)生成的，分布并不均勻．針對(duì)此問題，文中使用隨機(jī)化均勻設(shè)計(jì)方法[6]構(gòu)造初始種群．隨機(jī)化均勻設(shè)計(jì)(Random Uniform Design，RUD)是用一般生成向量代替均勻設(shè)計(jì)中的本原根產(chǎn)生隨機(jī)化均勻設(shè)計(jì)點(diǎn)集，許多隨機(jī)化均勻設(shè)計(jì)點(diǎn)集的偏差明顯小于原有均勻設(shè)計(jì)，因而具有更好的代表性．因此，文中采用隨機(jī)化均勻設(shè)計(jì)方法構(gòu)造更均勻的初始種群．

文獻(xiàn)[6]將隨機(jī)化均勻設(shè)計(jì)方法應(yīng)用于改進(jìn)遺傳算法，取得了比較理想的結(jié)果．文中引用此方法，并根據(jù)混合蛙跳算法的具體情況進(jìn)行如下調(diào)整：將文獻(xiàn)[6]3.3節(jié)中利用隨機(jī)化均勻設(shè)計(jì)所得的元素xij映射到SFLA問題的可行域中，則第i個(gè)候選解(記為aij)的第j維的值為

aij=amin+xij(amax-amin) ，i=1，2，…，P，j=1，2，…，D,

其中，amax為可行域的上界，amin為可行域的下界．

圖1(a)是在[0，1]2中用隨機(jī)化均勻設(shè)計(jì)方法產(chǎn)生的 1 000 個(gè)點(diǎn)組成的點(diǎn)集，圖1(b)是用隨機(jī)方法產(chǎn)生的 1 000 個(gè)點(diǎn)組成的點(diǎn)集．由圖1可以看出，隨機(jī)化均勻設(shè)計(jì)方法相比于隨機(jī)方法產(chǎn)生的點(diǎn)集更能均勻地分布在可行域中，有利于提高算法搜索到最優(yōu)解的概率，為算法更快、更準(zhǔn)確地搜索到全局最優(yōu)解提供了條件．

圖1 隨機(jī)化均勻設(shè)計(jì)法與隨機(jī)法效果對(duì)比

2.2 動(dòng)態(tài)影響因子的引入

在標(biāo)準(zhǔn)SFLA的局部搜索策略中，子群當(dāng)前最差值根據(jù)全局最優(yōu)值或子群當(dāng)前最優(yōu)值生成步長更新值，并將此步長更新值與當(dāng)前最差值進(jìn)行求和，生成子群中最差值的更新值(見式(1)和式(2))，從而實(shí)現(xiàn)對(duì)子群中最差值的更新．在算法的整個(gè)迭代過程中，子群當(dāng)前最差值對(duì)其更新值的影響恒定不變，即系數(shù)恒為1．此系數(shù)設(shè)置為1對(duì)應(yīng)較大的更新值，能保證算法在迭代初期具有較強(qiáng)的全局搜索能力，進(jìn)而不斷搜索到新區(qū)域．但是隨著迭代次數(shù)的增加，算法需要在最優(yōu)解周圍進(jìn)行局部搜索，如果此時(shí)子群當(dāng)前最差值對(duì)其更新值的影響仍然和算法迭代初期相同，算法可能會(huì)因?yàn)楦轮颠^大而跳過最優(yōu)值，因而需要執(zhí)行很多次才能收斂到全局最優(yōu)，從而導(dǎo)致算法在后期收斂速度不夠理想．因此，可以考慮引入影響因子，動(dòng)態(tài)地減小子群當(dāng)前最差值對(duì)其更新值的影響．

文獻(xiàn)[7]給出了一種更新公式，即Xneww=KXw+Di，-Dmax≤Di≤Dmax，并將其中的影響因子K設(shè)為從0.9到0.4線性地減小，即K= 0.9- (0.9- 0.4)t/tmax，其中，t是當(dāng)前迭代次數(shù)，tmax是最大混合迭代次數(shù)．可以看出，當(dāng)?shù)螖?shù)不斷增加時(shí)，K線性地減少．該方法使得SFLA在搜索初期具有較強(qiáng)的全局搜索能力，在后期具有較強(qiáng)的局部搜索能力．線性遞減意味著遞減速率在迭代過程中是恒定的，但是考慮到算法的尋優(yōu)原理，迭代初期需要較慢的迭代速率，以保證算法能展開充分的全局搜索．為此，在綜合考慮提高搜索效率并改善早熟收斂的情況下，這里采用余弦函數(shù)動(dòng)態(tài)地改變子群當(dāng)前最差值對(duì)其更新值的影響，即

Xneww=c1KXw+c2Xw+Di， -Dmax≤Di≤Dmax,

(3)

其中，影響因子K=cos((t/tmax)(π/2))；c1和c2為調(diào)節(jié)參數(shù)，且有c1+c2=1，當(dāng)取c1>c2時(shí)，動(dòng)態(tài)調(diào)節(jié)因子K對(duì)Xw的影響較大；當(dāng)取c1

余弦函數(shù)在[0，π/2]區(qū)間內(nèi)非線性地單調(diào)遞減，從而滿足更新值在迭代初期較大、而在迭代后期以較小的速率單調(diào)遞減的要求；而且在此區(qū)間內(nèi)開始時(shí)，遞減速度較慢，有利于種群在迭代初期充分地展開全局搜索，而不會(huì)迅速減小到很小以至于算法快速進(jìn)入局部搜索而產(chǎn)生早熟收斂現(xiàn)象．因此，采取動(dòng)態(tài)的余弦函數(shù)來調(diào)整當(dāng)前子群最差值對(duì)更新值的影響，對(duì)混合蛙跳算法收斂速度的提高有顯著的推進(jìn)作用．

2.3 基于群體適應(yīng)度方差的局部最優(yōu)的判斷

文獻(xiàn)[8]在粒子群算法中利用群體適應(yīng)度方差δ2小于某個(gè)閾值c來判斷粒子群是否發(fā)生早熟收斂現(xiàn)象．文中通過進(jìn)一步實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)混合蛙跳算法陷入局部最優(yōu)時(shí)，群體適應(yīng)度方差也會(huì)在數(shù)次迭代過程中保持相對(duì)穩(wěn)定．據(jù)此，這里通過計(jì)算相鄰兩次混合迭代后群體適應(yīng)度方差δ2的差值，來判斷種群是否出現(xiàn)早熟收斂現(xiàn)象．

2.4 局部最優(yōu)的處理

在標(biāo)準(zhǔn)混合蛙跳算法中，局部更新策略根據(jù)當(dāng)前子群最優(yōu)值或全局最優(yōu)值來更新子群中的最差值，這使得算法能夠朝著最優(yōu)值進(jìn)化，因而能在短時(shí)間內(nèi)收斂到全局最優(yōu)值[9]．但如果當(dāng)前最優(yōu)值是局部最優(yōu)，則算法就會(huì)在數(shù)次更新后陷入早熟收斂，而很難收斂到全局最優(yōu)值，特別是對(duì)一些具有許多局部最優(yōu)解的復(fù)雜多峰函數(shù)，為全局最優(yōu)解的計(jì)算帶來了很大的困難．

早熟收斂的處理方法一般分為兩種：早熟收斂預(yù)防與早熟收斂后的再處理，即重構(gòu)種群多樣性[10]．早熟處理相對(duì)于設(shè)計(jì)方法復(fù)雜的早熟收斂預(yù)防顯得簡單．文獻(xiàn)[10]將全局最優(yōu)值的微擾應(yīng)用于解決粒子群優(yōu)化算法的早熟收斂，取得了很好的效果．因此，可采用對(duì)陷入早熟的青蛙種群的全局最優(yōu)值微擾，幫其跳出局部最優(yōu)．其基本思路是：根據(jù)2.3節(jié)給出的方法判斷種群是否出現(xiàn)早熟收斂現(xiàn)象，如果是，則對(duì)當(dāng)前全局最優(yōu)值進(jìn)行微擾．這種改進(jìn)在后面的測(cè)試中顯示出了良好的性能．

微擾公式為

(4)

3 仿真與結(jié)果分析

3.1 仿真設(shè)置

為了檢驗(yàn)文中算法的性能，將DSFLA與文獻(xiàn)[2]的改進(jìn)算法(Shuffled Frog Leaping Algorithm Using Niche Technology，NSFLA)和經(jīng)典混合蛙跳算法SFLA進(jìn)行對(duì)比．

實(shí)驗(yàn)選取5個(gè)典型的函數(shù)優(yōu)化問題：Sphere[11]，Rosenbrock[11]，Rastrigin[11]，Griewank[11]和Schaffer’s f7[5]進(jìn)行測(cè)試．其中，Sphere是簡單的單峰函數(shù)；Rosenbrock是非凸的病態(tài)函數(shù)；Rastrigin，Griewank和Schaffer’s f7是復(fù)雜的多峰函數(shù)．參數(shù)設(shè)置如表1所示．適應(yīng)度值即為測(cè)試函數(shù)的函數(shù)值f(x)．對(duì)于每個(gè)測(cè)試函數(shù)，算法獨(dú)立運(yùn)行20次取平均值，仿真從平均求解精度和求解成功率兩方面對(duì)3個(gè)算法進(jìn)行對(duì)比，涉及的公共參數(shù)設(shè)置如下:

(1) 青蛙移動(dòng)的最大步長Dmax: 根據(jù)文獻(xiàn)[1]將其設(shè)置為可行域的界×45%．

(2) 對(duì)于式(3)中的c1和c2，實(shí)驗(yàn)中取值c1=0.6，c2=0.4．

(3) 通過實(shí)驗(yàn)分析，2.4節(jié)中的擾動(dòng)系數(shù)q取值為[0.5， 3]時(shí)，具有良好的擾動(dòng)效果，這里取q=1.3．

表1 文獻(xiàn)[2]中初始條件的設(shè)置

注：種群規(guī)模P=20；子群個(gè)數(shù)M=5；局部搜索次數(shù)N=10；混合迭代次數(shù)G=100．

3.2 仿真結(jié)果與分析

3.2.1 算法求解精度對(duì)比

對(duì)于每個(gè)測(cè)試函數(shù)，算法獨(dú)立運(yùn)行20次，表2是算法求解精度的對(duì)比結(jié)果．由表2可以看出，對(duì)于Sphere函數(shù)，DSFLA的平均值在數(shù)量級(jí)上比SFLA和NSLFA均有較明顯的提高;對(duì)于非凸的病態(tài)函數(shù)Rosenbrock，DSFLA得到了更好的結(jié)果；對(duì)于Rastrigin和Griewank函數(shù)，DSFLA收斂到了真正的全局最優(yōu)解0；對(duì)于Schaffer’s f7函數(shù)，DSFLA也較另外兩種算法有更理想的結(jié)果．由此可得，DSFLA具有更高的收斂精度．

表2 算法求解精度對(duì)比

3.2.2 算法求解成功率對(duì)比

指定各測(cè)試函數(shù)的收斂精度如表3所示．為了避免算法因局部收斂而使程序無法結(jié)束，設(shè)最大迭代次數(shù)G=200，如果在200次迭代內(nèi)算法無法結(jié)束，則認(rèn)為算法無法收斂到指定的精度．算法獨(dú)立運(yùn)行20次后，結(jié)果如表4所示．表4中成功率定義為: 成功率=(達(dá)到精度的次數(shù)/總次數(shù))×100%．

表3 函數(shù)收斂精度設(shè)置

由表4可以看出，除了Rosenbrock函數(shù)之外，DSFLA全部以100%的成功率收斂到了相應(yīng)的精度，且平均進(jìn)化代數(shù)較少．雖然DSFLA的平均運(yùn)行時(shí)間大于文獻(xiàn)[2]中的NSFLA的平行運(yùn)行時(shí)間，但是較標(biāo)準(zhǔn)的SFLA還是有所改善．

綜上分析，文中提出的DSFLA在求解精度和收斂效果兩方面均獲得了比較滿意的結(jié)果．尤其對(duì)于具有較多局部最優(yōu)值的問題，更體現(xiàn)出了DSFLA的優(yōu)越性．

表4 固定目標(biāo)精度下20次實(shí)驗(yàn)結(jié)果對(duì)比

4 結(jié) 束 語

分析了混合蛙跳算法的優(yōu)化原理，針對(duì)原算法中存在的初始種群不均勻、局部更新策略中存在的收斂速度慢以及算法執(zhí)行后期易陷入局部最優(yōu)等問題，提出了一種改進(jìn)的混合蛙跳算法．通過隨機(jī)化均勻設(shè)計(jì)方法構(gòu)造更加均勻的初始種群，提高了算法搜索到全局最優(yōu)解的概率;在局部更新策略中引入影響因子，動(dòng)態(tài)地改變子群當(dāng)前最差值對(duì)其進(jìn)化行為的影響，提高了算法的收斂速度;根據(jù)群體適應(yīng)度方差判斷種群是否陷入局部最優(yōu)，并通過對(duì)全局最優(yōu)值微擾，幫其跳出局部最優(yōu)，處理了早熟收斂，提高了算法的收斂精度．仿真結(jié)果表明，DSFLA在求解精度和收斂效果兩方面都有所提高，取得了較好的結(jié)果．

[1] Eusuff M, Lansey K, Pasha F. Shuffled Ffrog-leaping Algorithm: a Memetic Meta-heuristic for Discrete Optimization[J]. Engineering Optimization, 2006, 38(2): 129-154.

[2] 姜建國, 李錦, 龍秀萍, 等. 采用小生境技術(shù)的混合蛙跳算法[J]. 計(jì)算力學(xué)學(xué)報(bào), 2012, 29(6): 960-965.

Jiang Jianguo, Li Jin, Long Xiuping, et al. Shuffled Frog Leaping Algorithm Using Niche Technology [J]. Chinese Journal of Computational Mechanics, 2012, 29(6): 960-965.

[3] 趙鵬軍, 邵澤軍. 一種新的改進(jìn)的混合蛙跳算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(8): 48-50.

Zhao Pengjun, Shao Zejun. Novel Improved Shuffled Frog Leaping Algorithm [J]. Computer Engineering and Applications, 2012, 48(8): 48-50.

[4] Elbeltagi E, Hegazy T, Grierson D. A Modified Shuffled Frog-leaping Optimization Algorithm: Applications to Project Management[J]. Structure and Infrastructure Engineering, 2007, 3(1): 53-60.

[5] 葛宇, 王學(xué)平, 梁靜. 自適應(yīng)混沌變異蛙跳算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(3): 945-947.

Ge Yu, Wang Xueping, Liang Jing. Adaptive Chaotic Mutation Shuffled Frog Leaping Algorithms[J]. Application Research of Computers, 2011, 28(3): 945-947.

[6] 任哲, 周本達(dá), 陳明華. 一種基于隨機(jī)化均勻設(shè)計(jì)點(diǎn)集的遺傳算法用于求解 MVCP[J]. 模式識(shí)別與人工智能, 2010, 23(2): 284-288.

Ren Zhe, Zhou Benda, Chen Minghua. A Genetic Algorithm Based on Random Uniform Design Point Set for Solving MVCP[J]. Pattern Recognition and Artificial Intelligence, 2010, 23(2): 284-288.

[7] Luo P, Lu Q, Wu C. Modified Shuffled Frog Leaping Algorithm Based on New Searching Strategy[C]//7th International Conference on Natural Computation. Piscataway: IEEE, 2011: 1346-1350.

[8] 呂振肅, 侯志榮. 自適應(yīng)變異的粒子群優(yōu)化算法[J]. 電子學(xué)報(bào), 2004, 32(3): 416-420.

Lü Zhenxiao, Hou Zhirong. Particle Swarm Optimization with Adaptive Mutation[J]. Acta Electronica Sinica, 2004, 32(3): 416-420.

[9] 鞏敦衛(wèi), 朱美強(qiáng), 郭西進(jìn), 等. 一種新的基于混沌變異解決早熟收斂的遺傳算法[J]. 控制與決策, 2003, 18(6): 686-689.

Gong Dunwei, Zhu Meiqiang, Guo Xijin, et al. Genetic Algorithm Based on Chaotic Mutation to Deal with Premature Convergence[J]. Control and Decision, 2003, 18(6): 686-689.

[10] 金榮洪, 袁智皓, 耿軍平, 等. 基于改進(jìn)粒子群算法的天線方向圖綜合技術(shù)[J]. 電波科學(xué)學(xué)報(bào), 2006, 21(6): 873-878.

Jin Ronghong, Yuan Zhihao, Geng Junping, et al. The Pattern Synthesis of Antennas Based on a Modified PSO Algorithm[J]. Chinese Journal of Radio Science, 2006, 21(6): 873-878.

[11] 姜建國, 田旻, 王向前, 等. 采用擾動(dòng)加速因子的自適應(yīng)粒子群優(yōu)化算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 2012, 39(4): 93-101.

Jiang Jianguo, Tian Min, Wang Xiangqian, et al. Adaptive Particle Swarm Optimization via Disturbing Acceleration Coefficents [J]. Journal of Xidian University, 2012, 39(4): 93-101.