江澤昌， 劉天羽， 吳 星， 王義東

(上海電機(jī)學(xué)院 電氣學(xué)院，上海 201306)

混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)最早是由Eusuff等[1]于2003年提出的，是一種模仿自然界生物行為而產(chǎn)生的基于種群智能后啟發(fā)式的全局優(yōu)化方法。但是，SFLA和其他智能算法一樣容易收斂到局部最優(yōu)，且存在著初始種群不均勻、求解精度不高、收斂速度不夠快的缺點(diǎn)[2-3]。

鑒于此，研究者們對(duì)SFLA進(jìn)行了大量研究。文獻(xiàn)[4]中通過對(duì)SFLA的改進(jìn)，重新定義了青蛙的覓食機(jī)制和進(jìn)化迭代公式，改善了算法的局部搜索和全局搜索能力。文獻(xiàn)[5]中通過對(duì)學(xué)習(xí)的策略產(chǎn)生初始種群，在進(jìn)化過程中嵌入了差分進(jìn)化，對(duì)復(fù)雜函數(shù)優(yōu)化使其具有較強(qiáng)地求解能力。文獻(xiàn)[6]中通過理想的搜索策略，使最差個(gè)體青蛙向最好個(gè)體青蛙學(xué)習(xí)，且在搜索過程中引入2個(gè)加速因子，提高了搜索速度。文獻(xiàn)[7-8]中采用隨機(jī)分組的策略，在最差學(xué)習(xí)的過程中引入Minkowski距離，避免了算法陷入局部極小，加快了收斂速度。文獻(xiàn)[9]中引入柯西變異算子，使算法跳出局部最優(yōu)。文獻(xiàn)[10]中將模糊算法和混合SFLA相結(jié)合。文獻(xiàn)[11-12]中引入差分算法，使SFLA跳出局部最優(yōu)和避免早熟。文獻(xiàn)[13]中對(duì)原始算法添加了變異算子，通過模糊控制器調(diào)節(jié)變異算子的規(guī)模，動(dòng)態(tài)地調(diào)整變異算子在解空間的搜索范圍、不同階段和候選解分布的演化過程。上述文獻(xiàn)只是對(duì)子群中最差青蛙進(jìn)行了更新改進(jìn)，并沒有對(duì)全局最優(yōu)青蛙進(jìn)行改進(jìn)。

針對(duì)SFLA在后期收斂速度慢、易于陷入局部最優(yōu)、且精度低等問題，本文研究了一種改進(jìn)的混合SFLA。由于在局部搜索中，最差青蛙只是向最優(yōu)的青蛙學(xué)習(xí)，故引用精英策略對(duì)最差青蛙的位置進(jìn)行更新，使最差青蛙在向最優(yōu)青蛙學(xué)習(xí)的同時(shí)，也向本子群中較好青蛙學(xué)習(xí)；引入了柯西變異算子，增大了全局搜索能力，提高了搜索效率和算法的收斂速度；針對(duì)全局最優(yōu)青蛙很少有機(jī)會(huì)進(jìn)化的問題，引入了Minkowski距離，使全局最優(yōu)青蛙既能向局部其他青蛙方向進(jìn)化，也能向局部最優(yōu)青蛙進(jìn)化，提高了全局最優(yōu)青蛙的質(zhì)量。利用5個(gè)典型函數(shù)對(duì)改進(jìn)后的SFLA和SFLA進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，改進(jìn)后的SFLA具有較快的收斂速度，能避免早熟，且優(yōu)化精度高。最后，對(duì)改進(jìn)的SFLA進(jìn)行了收斂性分析。

1 SFLA的基本原理

SFLA是模擬青蛙在覓食的過程中，通過群體間的相互合作與競爭相互結(jié)合，以實(shí)現(xiàn)群體進(jìn)化的目的。本文以函數(shù)的最小值為例說明SFLA的基本步驟：設(shè)群體青蛙的種群規(guī)模為M，且在d維空間里第i個(gè)個(gè)體的坐標(biāo)xi=(xi1,xi2,…,xid)(i，d∈N)，計(jì)算個(gè)體的適應(yīng)值，然后按照從大到小順序排列。將整個(gè)種群劃分為S個(gè)局部子群，每個(gè)局部子群中有N只青蛙，即

M=SN

在降序排列的過程中，把排列好的個(gè)體平均分配到S個(gè)局部子群中去，在指定的局部迭代次數(shù)Ne內(nèi)進(jìn)行搜索，若滿足全局迭代次數(shù)maxGE，則停止此次搜索，輸出全局最優(yōu)值；否則，將全部青蛙混合重新計(jì)算。

在SFLA中，若局部青蛙產(chǎn)生的新個(gè)體優(yōu)于局部子群中的最差青蛙時(shí)，則用新個(gè)體來代替局部最差青蛙，因此，在多次替換后產(chǎn)生的新個(gè)體必然優(yōu)于之前的最差青蛙，即在多次迭代中，會(huì)使整體中局部子群的青蛙得到進(jìn)化。若局部子群中產(chǎn)生的新個(gè)體不優(yōu)于局部子群里的最差青蛙時(shí)，就用全局最優(yōu)解Xg來代替局部子群中最好青蛙Xb。其具體的最差青蛙更新策略為

2 一種改進(jìn)的SFLA算法

2.1 引入精英策略改進(jìn)最差青蛙

精英策略的基本思想是為了保留住最適應(yīng)的個(gè)體而產(chǎn)生的，目標(biāo)就是為了將最優(yōu)解的信息傳入到下一代[14]。

在基本SFLA中，局部子群中的最差青蛙只向該子群中的最優(yōu)青蛙學(xué)習(xí)，最差青蛙被限制在當(dāng)前位置與子群中最優(yōu)青蛙的線性區(qū)域中。本文借鑒精英策略，保留子群中的最優(yōu)青蛙，以防止最優(yōu)青蛙向較壞方向變異而造成群龍無首，繼而出現(xiàn)退化的現(xiàn)象。選擇每組中的最差青蛙讓其以自身為原點(diǎn)，以到該組中最優(yōu)青蛙的距離為半徑進(jìn)行360°搜索，并提高搜索速度，使最差青蛙向該子群中較好青蛙學(xué)習(xí)，且在學(xué)習(xí)過程中保證自身不退化。

2.2 引用柯西分布變異算子

SFLA在后期的搜索中，很容易陷入局部收斂的情況，為避免該情況的發(fā)生，本文引入柯西分布變異算子，使算法在后期跳出局部最優(yōu)。

柯西分布是概率論與數(shù)理統(tǒng)計(jì)中的一類常見的分布，其中一維柯西分布的函數(shù)為[15]

(3)

式中：x為隨機(jī)變量；t為常數(shù)。

當(dāng)t=1時(shí)，式(3)為標(biāo)準(zhǔn)的柯西分布函數(shù)。圖1所示為標(biāo)準(zhǔn)柯西分布概率密度函數(shù)曲線。

圖1 標(biāo)準(zhǔn)柯西分布概率密度函數(shù)曲線

由圖可見，曲線的兩端長扁形狀且趨于零，因此，利用柯西分布可以避免改進(jìn)的SFLA在后期易陷入局部最優(yōu)的情況。利用柯西分布隨機(jī)變量生成函數(shù)

η=tan[(ξ-0.5)π]

(4)

式中，ξ為[0，1]上的隨機(jī)變量。

考慮上述因素，提出了一種改進(jìn)的算法，其更新策略為

2.3 全局最優(yōu)蛙改進(jìn)策略

在基本SFLA中，在最差青蛙的進(jìn)化過程中，全局最優(yōu)的青蛙幾乎不進(jìn)化。實(shí)驗(yàn)證明[7]在進(jìn)化過程中，全局最優(yōu)地位會(huì)保持很多代，造成算法的尋優(yōu)速度變慢，且容易出現(xiàn)早熟現(xiàn)象。Minkowski距離是歐氏幾何空間中的廣義距離度量，提供了豐富、靈活的度量選擇[16]。由于全局最優(yōu)青蛙在位置上很少進(jìn)化，為增加其進(jìn)化的機(jī)會(huì)，本文利用Minkowski距離，使全局最優(yōu)青蛙向局部子群中其他最優(yōu)青蛙和除了最差青蛙以外的其他青蛙進(jìn)行學(xué)習(xí)，以提高青蛙質(zhì)量，其更新策略為

Xg=rand()c1M(Xg,Xj)+c2(Xg-Xbj)

(8)

j∈N

式中：Xj為局部除了最差青蛙以外的其他青蛙；Xbi為子群中最優(yōu)青蛙；M(Xg,Xj)為Xg向其他子群除最差青娃以外學(xué)習(xí)的Minkowski距離；c1與c2為更新的權(quán)值。

改進(jìn)后的SFLA算法流程圖如圖2所示。

圖2 改進(jìn)后的ACSFLA的算法流程圖

3 改進(jìn)算法的驗(yàn)證

為驗(yàn)證改進(jìn)策略和新算法的有效性，利用5個(gè)典型函數(shù)，即Sphere，Rosenbrook，Rastrigin，Griewank，Schaffer f7作為實(shí)驗(yàn)對(duì)象，采用Matlab7.1編程，在Intel處理器5-3210M(4GB內(nèi)存)中、Win7操作系統(tǒng)下進(jìn)行了大量的實(shí)驗(yàn)仿真。為增加對(duì)比性，本文所有的公共參數(shù)均設(shè)置相同，其中，M=1 800，S=30，迭代次數(shù)Ne=100。各函數(shù)的表達(dá)式和搜索范圍如表1所示。

用上述5種函數(shù)對(duì)改進(jìn)后的SFLA和基本SFLA進(jìn)行仿真比較，所有實(shí)驗(yàn)獨(dú)立運(yùn)行40次，Ne=100，表2所示為2種算法的仿真實(shí)驗(yàn)結(jié)果的平均值和方差。由表2可見，改進(jìn)后的SFLA對(duì)測試函數(shù)的仿真優(yōu)化結(jié)果，無論是其最優(yōu)解還是平均值，都較基本SFLA的要小，可見，由于引入了精英策略和Minkowski距離后，使最差青蛙的進(jìn)化得到了保證，也提高了全局最優(yōu)青蛙進(jìn)化的機(jī)會(huì)，因此，改進(jìn)后的SFLA較基本SFLA具有更好的優(yōu)化效果；同時(shí)，改進(jìn)后的SFLA獲得的平均值與標(biāo)準(zhǔn)差都比基本SFLA的小，說明改進(jìn)后的SFLA較基本SFLA在精度上有了明顯提高。

表1 測試函數(shù)

表2 2種算法對(duì)測試函數(shù)的仿真優(yōu)化結(jié)果比較

由于改進(jìn)后的SFLA算法較基本SFLA算法在仿真過程中存在著許多偶然因素，本文利用這2種算法對(duì)5種測試函數(shù)分別迭代100次和1 000次，運(yùn)行40次后得到函數(shù)最優(yōu)解的運(yùn)行曲線如圖3所示。由圖可見，無論是哪種函數(shù)，改進(jìn)后的SFLA較基本SFLA的收斂速度都要快，而且隨著迭代次數(shù)的增加，改進(jìn)后的SFLA的收斂性得到了明顯提高，并跳出了基本SFLA局部收斂，使后期收斂速度慢的問題得到了解決。

4 改進(jìn)后SFLA的收斂性分析

本文借鑒文獻(xiàn)[17]對(duì)SFLA收斂性的分析，對(duì)改進(jìn)的SFLA進(jìn)行分析，其證明過程如下。

由式(5)～(7)可得第k次迭代后，

(9)

(a)Sphere函數(shù)迭代100次

(b)Sphere函數(shù)迭代1 000次

(c)Rosenbroock函數(shù)迭代100次

(d)Rosenbroock函數(shù)迭代1 000次

(e)Rastrin函數(shù)迭代100次

(f)Rastrin函數(shù)迭代1 000次

(h)Griewank函數(shù)迭代1 000次

(i)Schaffer f7函數(shù)100次

(j)Schaffer f7函數(shù)1 000次

而第k+1次迭代后，

(10)

將式(9)與(10)相減

ΔXk+1=Xk-Xk-1， Δe=(ejθ′-ejθ)

可得

(15)

分別以進(jìn)化k次和k+1次的青蛙為圓心，在(0°,360°)的搜索范圍內(nèi)搜索，得到它們的差值Δe，再與式(7)聯(lián)合，可得

(16)

5 結(jié) 語

針對(duì)基本SFLA在后期收斂速度慢和易于陷入局部收斂的問題，研究了基于精英策略的改進(jìn)SFLA，通過引入精英策略對(duì)最差青蛙進(jìn)行改進(jìn)，引入柯西分布變異算子改進(jìn)了搜索策略，并利用Minkowsk距離提升了全局最優(yōu)青蛙優(yōu)化的機(jī)會(huì)；通過對(duì)常用的5個(gè)測試函數(shù)進(jìn)行仿真測試，結(jié)果表明，改進(jìn)的SFLA具有較快的收斂速度，能夠避免早熟，且優(yōu)化精度高。最后，通過對(duì)改進(jìn)的SFLA進(jìn)行收斂性分析，其收斂性可以以等比數(shù)列進(jìn)行分析。

[1] EUSUFF M, LANSEY K, PASHA F.Shuffled frog-leaping algorithm: A memetic meta-heuristic for discrete optimization [J].Engineering Optimization, 2006, 38(2):129-154.

[2] 賀毅朝,曲文龍,許冀偉.一種改進(jìn)的混合蛙跳算法及其收斂性分析 [J].計(jì)算機(jī)工程與應(yīng)用,2011,47(22):37-40.

[3] 蘇仟.混合蛙跳算法研究與改進(jìn) [D].西安：西安電子科技大學(xué),2014：19-20.

[4] 趙紅星,常小剛.一種改進(jìn)的混合蛙跳算法 [J].蘭州交通大學(xué)學(xué)報(bào),2017,36(1):51-56.

[5] 趙鵬軍,劉三陽.求解復(fù)雜函數(shù)優(yōu)化問題的混合蛙跳算法 [J].計(jì)算機(jī)應(yīng)用研究,2009,26(7):2435-2437.

[6] JABALLAH S, ROUIS K, ABDALLAH F B, et al. An improved shuffled frog leaping algorithm with a fast search strategy for optimization problems [C]//IEEE International Conference on Intelligent Computer Communication and Processing. Cluj Napoca, Romania：IEEE,2014:23-27.

[7] 魏立新,鄭翠紅,王洪慶,等.混洗蛙跳算法的改進(jìn)研究 [J].控制工程,2016, 23(2):167-172.

[8] BALA S M, MEENAKUMARI R. Optimum generation scheduling using an improved adaptive shuffled frog leaping algorithm [C]//International Conference on Cognitive Computing and Information Processing.[S.l.]：IEEE,2015:1-6.

[9] 王晨.基于混合蛙跳算法的微電網(wǎng)運(yùn)行優(yōu)化 [D].蘭州：蘭州理工大學(xué),2014:19-20.

[10] 王洋,劉志珍.基于蛙跳模糊算法的Jiles Atherton鐵心磁滯模型參數(shù)確定 [J].電工技術(shù)學(xué)報(bào),2017,32(4):154-161.

[11] 王娜,高學(xué)軍.一種新穎的差分混合蛙跳算法 [J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(1):196-200.

[12] 何兵,車林仙,劉初升.一種蛙跳和差分進(jìn)化混合算法 [J].計(jì)算機(jī)工程與應(yīng)用,2011,47(18):4-8.

[13] 葛宇，王學(xué)平，梁靜. 改進(jìn)的混合蛙跳算法 [J].計(jì)算機(jī)應(yīng)用，2012，32(1): 234-237.

[14] 張家善,王志宏,陳應(yīng)顯.一種基于精英策略的改進(jìn)蟻群算法及應(yīng)用 [J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2012,21(10):105-108，134.

[15] 黎紅玲,羅林,蒲冬梅,等.基于柯西分布的粒子群優(yōu)化算法改進(jìn) [J].電子科技,2016,29(01):33-35，39.

[16] 盧賓賓,楊歡,孫華波,等.利用Minkowski距離逼近道路網(wǎng)絡(luò)距離算法研究 [J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),2017,42(10):1373-1380.

[17] 肖瑩瑩,林廷宇,李伯虎,等. 混合蛙跳算法自適應(yīng)參數(shù)調(diào)整改進(jìn)策略 [J].系統(tǒng)工程與電子技術(shù),2016,38(8):1939-1950.