張 強(qiáng), 朱劉濤, 王 穎

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院, 黑龍江 大慶 163318)

混洗蛙跳算法(shuffled frog leaping algorithm, SFLA)[1]是一種具有粒子群優(yōu)化算法全局搜索和模因算法局部搜索的元啟發(fā)式智能優(yōu)化算法, 具有收斂較快、 參數(shù)調(diào)整少、 搜索能力強(qiáng)等優(yōu)勢, 已廣泛應(yīng)用在函數(shù)優(yōu)化[2-3]、 車間調(diào)度[4-6]、 故障診斷[7-8]、 聚類問題[9-10]和圖像處理[11-12]等領(lǐng)域. 但該算法也存在一些不足： 1) 混洗蛙跳算法按適應(yīng)值降序的方式分配到子群內(nèi), 導(dǎo)致最后一個(gè)子群內(nèi)個(gè)體的適應(yīng)值整體偏低, 從而影響整個(gè)蛙群的尋優(yōu)性能； 2) 每個(gè)子群內(nèi)更新最差青蛙, 并根據(jù)子群內(nèi)的最優(yōu)青蛙調(diào)整位置, 易導(dǎo)致最差青蛙具有趨同性, 使青蛙種群多樣性降低, 對(duì)于多模優(yōu)化問題混洗蛙跳算法易陷入局部最優(yōu)； 3) 混洗蛙跳算法未充分利用整個(gè)蛙群中其他個(gè)體的迭代尋優(yōu)信息, 導(dǎo)致子群易被限制在較小的尋優(yōu)空間. 文獻(xiàn)[13-15]提出了一種文化算法理論, 該算法是由信念空間和群體空間構(gòu)成的雙層進(jìn)化結(jié)構(gòu). 群體空間通過接受函數(shù)將優(yōu)秀青蛙的經(jīng)驗(yàn)選擇性地傳遞到信念空間, 而信念空間再通過影響函數(shù)將進(jìn)化過程中的優(yōu)秀經(jīng)驗(yàn)反饋到群體空間, 以指導(dǎo)個(gè)體的進(jìn)化, 通過兩個(gè)空間的相互影響準(zhǔn)確反映進(jìn)化過程, 進(jìn)而提高尋優(yōu)效率和速率. 本文通過在基本混洗蛙跳算法原理的基礎(chǔ)上引入文化算法的理念, 提出一種文化混洗蛙跳算法(cultural shuffled frog leaping algorithm, CSFLA), 改進(jìn)了群體空間和信念空間內(nèi)個(gè)體的進(jìn)化方式, 設(shè)計(jì)了相應(yīng)的接受函數(shù)實(shí)現(xiàn)個(gè)體優(yōu)秀經(jīng)驗(yàn)及進(jìn)化信息的有效傳遞, 并通過影響函數(shù)將信念空間的進(jìn)化信息反饋到群體空間, 以進(jìn)一步指導(dǎo)青蛙個(gè)體在優(yōu)化問題空間進(jìn)行有效尋優(yōu).

1 基本混洗蛙跳算法

基本混洗蛙跳算法的思想是將整個(gè)青蛙群體分為不同的子群體, 每個(gè)子群體的最差個(gè)體先向子群內(nèi)最優(yōu)個(gè)體學(xué)習(xí)產(chǎn)生新個(gè)體, 如果新個(gè)體優(yōu)于最差個(gè)體則替換; 否則再向種群最優(yōu)個(gè)體學(xué)習(xí)產(chǎn)生新個(gè)體, 如果新個(gè)體優(yōu)于最差個(gè)體則替換; 否則隨機(jī)產(chǎn)生一個(gè)個(gè)體. 當(dāng)子群進(jìn)化到指定次數(shù)后就重新劃分子群進(jìn)行尋優(yōu), 直至滿足所設(shè)置的結(jié)束條件.

1.1 種群初始化

混洗蛙跳算法將每只青蛙都視為優(yōu)化問題的解, 設(shè)青蛙種群規(guī)模為P(P=mn, 其中m為子群個(gè)數(shù),n為子群內(nèi)青蛙個(gè)數(shù)), 最大進(jìn)化代數(shù)為T, 子群迭代次數(shù)為t.

1.2 子群劃分原理

先計(jì)算每個(gè)青蛙的適應(yīng)度f(X), 再按降序排序. 設(shè)蛙群中適應(yīng)值最好的青蛙為Pg, 用X(j)k表示第k個(gè)分組內(nèi)的第j個(gè)青蛙,j=1,2,…,n,k=1,2,…,m. 按

Gk={X(j)k,f(j)k|X(j)k=X(k+m(j-1)),f(j)k=f(k+m(j-1))}

(1)

將青蛙種群分為m個(gè)子群, 每個(gè)子群均包含n個(gè)青蛙. 圖1為蛙跳算法分組示意圖.

1.3 子群內(nèi)青蛙進(jìn)化

設(shè)每個(gè)子群內(nèi)最優(yōu)解為Xb, 最差解為Xw, 整個(gè)種群當(dāng)前最優(yōu)解為Xg, 利用下式對(duì)每個(gè)子群的Xw進(jìn)行更新：

(2)

(3)

圖1 蛙跳算法分組示意圖Fig.1 Schematic diagram of frog leaping algorithm grouping

當(dāng)每個(gè)子群分別迭代指定次數(shù)時(shí), 如果達(dá)到群體進(jìn)化最大進(jìn)化代數(shù)T或滿足尋優(yōu)精度則輸出結(jié)果, 否則將所有青蛙個(gè)體整合完成青蛙種群的信息共享, 繼續(xù)進(jìn)行子群劃分、 子群個(gè)體進(jìn)化, 直至滿足算法終止條件.

2 文化混洗蛙跳算法原理

文化混洗蛙跳算法的基本框架由種群空間和信念空間構(gòu)成. 種群空間包含優(yōu)化問題的候選解, 主要由采用蛙跳算法的進(jìn)化方式進(jìn)行尋優(yōu); 信念空間主要用于保存進(jìn)化過程中的優(yōu)秀經(jīng)驗(yàn), 采用螺旋更新的方式在最優(yōu)解附近尋找更優(yōu)解, 進(jìn)而加速尋優(yōu)性能. 信念空間通過接受函數(shù)從群體空間獲得優(yōu)秀個(gè)體； 通過信念空間的不斷進(jìn)化后, 再通過影響函數(shù)將優(yōu)秀個(gè)體的經(jīng)驗(yàn)反饋給群體空間, 進(jìn)而指導(dǎo)群體空間的個(gè)體進(jìn)化.

2.1 群體空間進(jìn)化方式

文化混洗蛙跳算法群體空間進(jìn)化方式仍采用經(jīng)典混洗蛙跳算法的更新方式, 即只更新每個(gè)分組內(nèi)的最差個(gè)體. 但原算法最差個(gè)體是先向組內(nèi)最優(yōu)個(gè)體學(xué)習(xí), 未改善則再向當(dāng)代整個(gè)蛙群最優(yōu)個(gè)體學(xué)習(xí), 這種學(xué)習(xí)方式較單一, 未充分考慮個(gè)體經(jīng)驗(yàn)和全局經(jīng)驗(yàn)的相互作用關(guān)系, 易導(dǎo)致算法陷入局部最優(yōu). 基于此, 本文提出一種改進(jìn)方法, 將向種群最優(yōu)個(gè)體學(xué)習(xí)的方式改進(jìn)成向組內(nèi)最優(yōu)個(gè)體、 種群最優(yōu)個(gè)體和信念空間個(gè)體(信念空間通過影響函數(shù)提供)同時(shí)學(xué)習(xí), 實(shí)現(xiàn)公式為

(4)

其中:Xg(t)為種群最優(yōu)個(gè)體；Xb(t)為組內(nèi)最優(yōu)個(gè)體；Xs(t)為信念空間的個(gè)體；t表示當(dāng)前迭代次數(shù)；X(t+1)為第(t+1)代青蛙的位置；r1在[0,1]內(nèi)隨機(jī)取值.

2.2 信念空間進(jìn)化方式

信念空間內(nèi)的個(gè)體來自于群體空間的較優(yōu)個(gè)體. 研究表明, 優(yōu)秀個(gè)體附近更易找到更優(yōu)個(gè)體, 所以可對(duì)信念空間內(nèi)的個(gè)體進(jìn)行尋優(yōu). 為模擬個(gè)體進(jìn)行周圍尋優(yōu)的進(jìn)化方式, 本文個(gè)體位置更新采用螺旋方式, 同時(shí)為降低信念空間個(gè)體聚集到局部最優(yōu)解的幾率, 需個(gè)體以一定概率進(jìn)行隨機(jī)游走. 如果通過螺旋更新或隨機(jī)游走方式獲得的個(gè)體優(yōu)于原個(gè)體則替換, 否則不進(jìn)行任何操作. 個(gè)體跳躍步長計(jì)算公式為

(5)

其中:Xb為信念空間內(nèi)最優(yōu)個(gè)體;Xw為組內(nèi)最優(yōu)個(gè)體;t表示當(dāng)前迭代次數(shù);Tmax為最大迭代次數(shù)；r,r1在[0,1]內(nèi)隨機(jī)取值.

本文將擾動(dòng)系數(shù)A作為概率閾值, 在優(yōu)化過程中,A的變化范圍隨著α的減小而減小; 當(dāng)|A|≤1時(shí), 使用螺旋進(jìn)化方式更新位置, 能加快族群內(nèi)的青蛙向最優(yōu)位置靠攏; 當(dāng)|A|>1時(shí), 采用個(gè)體隨機(jī)游走方式完成對(duì)獵物的捕食.

1) 個(gè)體螺旋進(jìn)化尋優(yōu). 首先計(jì)算信念空間內(nèi)最優(yōu)個(gè)體與最差個(gè)體之間的距離, 然后在最優(yōu)個(gè)體與最差個(gè)體間創(chuàng)建螺旋運(yùn)動(dòng)軌跡, 促使青蛙種群在迭代中快速聚集在某一區(qū)域, 以加快算法后期的收斂速度, 其更新公式為

(6)

其中:l為[-1,1]內(nèi)的隨機(jī)概率；Xb表示信念空間內(nèi)最優(yōu)個(gè)體.

2) 個(gè)體隨機(jī)游走. 以信念空間內(nèi)最優(yōu)個(gè)體為參照, 適當(dāng)擴(kuò)大蛙群的搜索范圍, 并使空間內(nèi)的青蛙由原位置不斷向最優(yōu)解位置移動(dòng), 其更新公式為

(7)

2.3 接受函數(shù)

接受函數(shù)的作用是從群體空間將優(yōu)秀個(gè)體輸送到信念空間. 本文算法設(shè)信念空間的個(gè)體數(shù)量為子群個(gè)數(shù)的2倍(2m個(gè)), 在算法迭代初期子群內(nèi)的個(gè)體分布相對(duì)分散, 所以每個(gè)子群將最好的兩個(gè)個(gè)體輸送到信念空間. 但算法到迭代后期, 每個(gè)子群的個(gè)體位置相對(duì)集中, 故算法通過下式計(jì)算每個(gè)子群的方差：

(8)

2.4 影響函數(shù)

影響函數(shù)的作用是將信念空間的優(yōu)秀經(jīng)驗(yàn)傳遞給群體空間, 用于指導(dǎo)個(gè)體進(jìn)行尋優(yōu), 其主要思想是通過引入較優(yōu)個(gè)體引領(lǐng)整個(gè)子群內(nèi)個(gè)體的進(jìn)化. 首先, 在信念空間選擇適應(yīng)度最好的m個(gè)個(gè)體(m為子群個(gè)數(shù))； 其次, 為改進(jìn)后續(xù)子群整體適應(yīng)度值偏低的情形, 將算法按適應(yīng)度升序把m個(gè)個(gè)體分配給文化蛙跳算法的m個(gè)子群, 即將適應(yīng)度最好的個(gè)體分配給最后一個(gè)子群, 適應(yīng)度第二好的個(gè)體分配給倒數(shù)第二個(gè)子群, 以此類推.

3 仿真實(shí)驗(yàn)

本文選用如表1所示的12個(gè)常用基準(zhǔn)測試函數(shù)(包括單峰問題和多峰問題)進(jìn)行仿真實(shí)驗(yàn).

表1 12個(gè)典型優(yōu)化函數(shù)

Table 1 Twelve typical optimization functions

將文化混洗蛙跳算法(CSFLA), 與混洗蛙跳算法的4種改進(jìn)算法(MSFLA[16],MSFLA1[17],ISFLA[18],MSFLA2[19])以及近幾年提出的8種智能算法(鯨魚優(yōu)化算法(WOA)[20]、 灰狼算法(GWO)[21]、 飛蛾撲火算法(MFO)[22]、 布谷鳥算法(CSA)[23]、 蝙蝠算法(BAT)[24]、 多元宇宙算法(MVO)[25]、 果蠅算法(FFOA)[26]、 烏賊算法(CFA)[27])進(jìn)行對(duì)比實(shí)驗(yàn). 實(shí)驗(yàn)環(huán)境為: Intel(R)Core(TM)i7 8750H CPU雙核處理器(2.20 GHz, 2.21 GHz), 16 GB內(nèi)存, Microsoft Windows 10 Professional操作系統(tǒng), 采用MATLAB R2014a進(jìn)行編碼并實(shí)現(xiàn). 對(duì)每個(gè)測試函數(shù), 本文算法及4種蛙跳改進(jìn)算法均采用相同的參數(shù)設(shè)置, 其他8種算法參數(shù)均按原文獻(xiàn)的設(shè)置方式. 設(shè)最大迭代次數(shù)為100, 種群數(shù)為40, 子群數(shù)為5, 每種算法分別計(jì)算20次取平均值. 每種算法分別對(duì)12個(gè)函數(shù)的100維進(jìn)行優(yōu)化對(duì)比, 性能對(duì)比結(jié)果如圖2所示.

圖2 不同算法對(duì)不同測試函數(shù)的迭代曲線對(duì)比Fig.2 Comparison of iterative curves of different algorithms for different test functions

由圖2可見： CSFLA的尋優(yōu)速度和尋優(yōu)精度均優(yōu)于其他對(duì)比算法； WOA的尋優(yōu)性能相對(duì)較好, 但并非對(duì)12個(gè)優(yōu)化函數(shù)都優(yōu)于其他算法, 其他算法在一些函數(shù)也有一定的優(yōu)勢; 從單峰函數(shù)f1～f4的迭代曲線可見, CSFLA相對(duì)于其他算法, 能快速收斂到最優(yōu)解. 多峰多極值函數(shù)局部極值的個(gè)數(shù)隨維數(shù)的增加而呈指數(shù)級(jí)增長, 但由多峰多極值函數(shù)f8～f10的優(yōu)化結(jié)果可見, CSFLA均求解到了最優(yōu)值0, 即使在500維函數(shù)測試也能求解到最優(yōu)值, 函數(shù)f6,f7,f9,f11,f12的優(yōu)化結(jié)果優(yōu)于其他對(duì)比算法, 且從迭代曲線可見, 算法可在40次迭代內(nèi)即能獲得較好的結(jié)果, 這也表明由于信念空間個(gè)體優(yōu)秀經(jīng)驗(yàn)的反饋, 加速了算法尋優(yōu)效率, 提高了尋優(yōu)性能.

為驗(yàn)證本文算法對(duì)高維優(yōu)化問題的求解能力, 選取函數(shù)f3～f12作為測試函數(shù), 優(yōu)化問題維數(shù)設(shè)為500, 其他算法運(yùn)行參數(shù)不變. 選取最優(yōu)值(min)、 平均值(avg)和標(biāo)準(zhǔn)方差(std)進(jìn)行對(duì)比, 對(duì)比結(jié)果列于表2.

表2 不同算法對(duì)函數(shù)f3～f12的500維問題尋優(yōu)結(jié)果對(duì)比

續(xù)表2

由表2可見, CSFLA性能優(yōu)于其他算法. 對(duì)于f3,f4函數(shù), CSFLA的尋優(yōu)精度明顯優(yōu)于其他算法； 對(duì)于f8,f10函數(shù), CSFLA均找到了全局最優(yōu)解； CSFLA,WOA和FFOA對(duì)f5,f12函數(shù)的尋優(yōu)結(jié)果數(shù)量相同; CSFLA和WOA對(duì)f6,f10,f11函數(shù)的尋優(yōu)結(jié)果相似; CSFLA和MSFLA2對(duì)f7,f9函數(shù)的尋優(yōu)結(jié)果相似, 但CSFLA平均值和標(biāo)準(zhǔn)差相對(duì)更好, 且進(jìn)化次數(shù)明顯優(yōu)于其他算法. 其原因如下：

1) 引入信息空間指導(dǎo)群體空間進(jìn)化, 有效記錄了算法進(jìn)化過程中形成的優(yōu)秀經(jīng)驗(yàn), 同時(shí)對(duì)信念空間的個(gè)體利用螺旋方式在最優(yōu)個(gè)體周圍查找更優(yōu)解, 并通過影響函數(shù)將優(yōu)秀進(jìn)化經(jīng)驗(yàn)反饋到群體空間提供個(gè)體尋優(yōu)性能；

2) 相對(duì)于基本蛙跳算法, CSFLA改進(jìn)了最差個(gè)體的進(jìn)化方式, 增加了最差個(gè)體的參考知識(shí), 分別為子群最優(yōu)、 種群最優(yōu)和信念空間的知識(shí), 較好地平衡了個(gè)體進(jìn)行局部尋優(yōu)和全局探索.

綜上所述, 本文將文化算法理論與混洗蛙跳算法進(jìn)行融合, 基于社會(huì)學(xué)理論改進(jìn)最優(yōu)個(gè)體的進(jìn)化方式, 利用螺旋進(jìn)化和隨機(jī)游走的方式在最優(yōu)個(gè)體周圍尋找更優(yōu)解, 同時(shí)利用種群最優(yōu)、 子群最優(yōu)和信念空間的知識(shí)平衡個(gè)體的局部尋優(yōu)和全局探索. 通過對(duì)12個(gè)基準(zhǔn)函數(shù)測試的結(jié)果表明, 該算法可用較少的迭代次數(shù)獲取較優(yōu)的結(jié)果, 尤其針對(duì)單峰函數(shù)尋優(yōu)效果更明顯. 所以本文算法可應(yīng)用到適應(yīng)值計(jì)算復(fù)雜度較大的優(yōu)化問題中.