基于金字塔模型和多策略協(xié)同的螢火蟲(chóng)算法

劉彥伶，樊棠懷，王 暉，康 平，趙 嘉

(南昌工程學(xué)院 信息工程學(xué)院，江西 南昌 330099)

0 引 言

螢火蟲(chóng)算法(firefly algorithm，F(xiàn)A)[1]是Yang等提出的一種群智能優(yōu)化算法(swarm intelligent algorithm，SIA)[2]，由于其思想簡(jiǎn)單、易于實(shí)現(xiàn)并擁有較好的優(yōu)化性能，受到了廣泛關(guān)注。但FA采用全吸引模型，即每只螢火蟲(chóng)都會(huì)被任意一只更亮的螢火蟲(chóng)吸引，導(dǎo)致螢火蟲(chóng)在移動(dòng)過(guò)程中發(fā)生振蕩而使算法收斂速度減慢。為提高螢火蟲(chóng)算法的優(yōu)化性能，許多學(xué)者從吸引模型角度對(duì)FA提出改進(jìn)。Wang等[3]提出了一種隨機(jī)吸引模型來(lái)有效減少個(gè)體的移動(dòng)次數(shù)，避免運(yùn)動(dòng)過(guò)程中的粒子振蕩，加快算法收斂速度。文獻(xiàn)[4]讓每只螢火蟲(chóng)與鄰域內(nèi)的螢火蟲(chóng)進(jìn)行比較，通過(guò)調(diào)整鄰域范圍來(lái)有效平衡算法的探索與開(kāi)發(fā)能力。Zhou等[5]提出了一種部分吸引模型，即螢火蟲(chóng)隨機(jī)地從種群中選擇3只優(yōu)于自身的螢火蟲(chóng)進(jìn)行學(xué)習(xí)。與全吸引模型相比，上述提到的吸引模型減少了粒子運(yùn)動(dòng)次數(shù)，避免了算法運(yùn)行過(guò)程中的粒子振蕩，但均采用了統(tǒng)一的進(jìn)化方式且都向最好的粒子靠近，當(dāng)最優(yōu)粒子陷入局部最優(yōu)，算法將快速收斂到局部極值，導(dǎo)致算法精度不高。

策略協(xié)同是螢火蟲(chóng)算法的研究熱點(diǎn)，通過(guò)結(jié)合其它方法的優(yōu)勢(shì)來(lái)挖掘FA更好的優(yōu)化性能。Lv等[6]將高斯擾動(dòng)與螢火蟲(chóng)算法相融合，提出了具有高斯擾動(dòng)和局部搜索的螢火蟲(chóng)算法。文獻(xiàn)[7]中使用韋伯分布和步長(zhǎng)單調(diào)遞減方式，來(lái)對(duì)螢火蟲(chóng)的移動(dòng)公式進(jìn)行改進(jìn)，以提高算法前期全局探索能力和后期的局部開(kāi)發(fā)能力。文獻(xiàn)[8]構(gòu)建廣義中心粒子進(jìn)行單維深度學(xué)習(xí)，再讓其它粒子使用隨機(jī)吸引模型向其進(jìn)行學(xué)習(xí)。上述提出的各改進(jìn)算法對(duì)算法性能有了較大提升，但由于使用的學(xué)習(xí)策略單一，算法的普適性不強(qiáng)。

基于上述分析，為提高FA優(yōu)化性能，本文提出了一種基于金字塔模型和多策略協(xié)同的螢火蟲(chóng)算法(firefly algorithm based on pyramid model and multiply cooperative strategies，PMFA-MCS)。借鑒金字塔分層結(jié)構(gòu)和三角穩(wěn)定性，PMFA-MCS將螢火蟲(chóng)種群按適應(yīng)度排序后分為4層，每層螢火蟲(chóng)分別使用相對(duì)應(yīng)的策略向自身或更高層粒子學(xué)習(xí)一次，形成金字塔模型，提高了群體的多樣性且避免發(fā)生振蕩。每層粒子使用不同的學(xué)習(xí)策略，構(gòu)成了多策略協(xié)同，平衡了探索與開(kāi)發(fā)能力。算法在每一次迭代后將種群重新排序，保證了信息共享與傳遞。實(shí)驗(yàn)部分，測(cè)試了兩組函數(shù)集，將PMFA-MCS的結(jié)果與其它改進(jìn)螢火蟲(chóng)算法及其它群智能算法進(jìn)行了比較。

1 螢火蟲(chóng)算法

螢火蟲(chóng)算法是一種群智能隨機(jī)搜索技術(shù)，它基于螢火蟲(chóng)的閃光和吸引特性來(lái)模擬螢火蟲(chóng)的社會(huì)行為。其算法的數(shù)學(xué)描述如下：

設(shè)螢火蟲(chóng)種群大小為N，維度為D，則第i(i=1，2，…，N) 個(gè)螢火蟲(chóng)可行域空間中的位置可以表示為Xi=(xi1，xi2，…，xiD)。 螢火蟲(chóng)的光亮強(qiáng)度I定義如下

I=I0e-γrij2

(1)

式中：I0為螢火蟲(chóng)在r=0時(shí)的光亮強(qiáng)度，γ為光吸收系數(shù)，通常設(shè)置為1，rij為螢火蟲(chóng)i與j之間的歐式距離，它的計(jì)算公式如下

(2)

式中：xid和xjd為螢火蟲(chóng)i和螢火蟲(chóng)j的第d維位置。

螢火蟲(chóng)的吸引力公式通過(guò)以下公式計(jì)算

β=β0e-γrij2

(3)

式中：β0為最大吸引度，即r=0時(shí)的吸引度。螢火蟲(chóng)i向螢火蟲(chóng)j移動(dòng)的位置更新公式為

xid(t+1)=xid(t)+β(xjd(t)-xid(t))+αid(t)*ε

(4)

式中：xid(t)、xjd(t) 為第t代螢火蟲(chóng)i和j在第d維的位置；αi(t) 表示第t代螢火蟲(chóng)i的步長(zhǎng)因子；ε是區(qū)間[-0.5，0.5]上的隨機(jī)數(shù)。

2 基于金字塔模型和多策略協(xié)同的螢火蟲(chóng)算法

FA采用全吸引模型，每只螢火蟲(chóng)均會(huì)被其它優(yōu)于自身的螢火蟲(chóng)吸引，但過(guò)多的移動(dòng)容易發(fā)生振蕩。使用單一策略，種群多樣性缺失，且隨著算法不斷迭代進(jìn)行，粒子之間逐漸靠近成為相似個(gè)體，算法陷入局部最優(yōu)而出現(xiàn)停滯，提前收斂。為了保持種群的多樣性以及算法整體尋優(yōu)，本文提出了一種基于金字塔模型和多策略協(xié)同的螢火蟲(chóng)算法，從吸引模型和學(xué)習(xí)策略兩個(gè)方面來(lái)提高算法性能。

2.1 金字塔模型

金字塔是世界七大奇跡之一，距今已有五千多年的歷史，其數(shù)量眾多、分布廣泛。金字塔屹立千年而不倒的原因在于其斜面與地面的夾角為52度，這與物體自然塌落時(shí)的極限角和穩(wěn)定角相近。生態(tài)系統(tǒng)中也存在類(lèi)似金字塔結(jié)構(gòu)的錐體，層與層之間的有機(jī)體相互制約，維持了自然界物種間的平衡，保證了生態(tài)系統(tǒng)的穩(wěn)定。因此，金字塔結(jié)構(gòu)被后人廣泛應(yīng)用于生活中。

螢火蟲(chóng)種群中，同樣存在著類(lèi)似金字塔的吸引模式。螢火蟲(chóng)的發(fā)光強(qiáng)度存在差別，最亮的一部分螢火蟲(chóng)數(shù)量較少，只在空中小范圍內(nèi)飛翔，并釋放信號(hào)等待其它螢火蟲(chóng)靠近。亮度較差的螢火蟲(chóng)數(shù)量相對(duì)較多，在區(qū)域內(nèi)隨機(jī)地選擇更亮的螢火蟲(chóng)靠近。亮度一般的螢火蟲(chóng)數(shù)量中等，既吸引亮度較差的螢火蟲(chóng)同時(shí)自身又向最亮的螢火蟲(chóng)移動(dòng)。

在該模型中，第一層為適應(yīng)度最好的粒子，數(shù)量占種群的1/10，我們稱其為領(lǐng)導(dǎo)層。在算法運(yùn)行前期，螢火蟲(chóng)種群由最高領(lǐng)導(dǎo)層的粒子同時(shí)引領(lǐng)，有效延緩種群中其它粒子向最優(yōu)粒子聚集的速度。為了保持這些“領(lǐng)導(dǎo)者”的信息不被丟失且獲取更為有用的信息，需要賦予最高層螢火蟲(chóng)一種方法，讓其在自身周?chē)\(yùn)動(dòng)。第二和第三層統(tǒng)稱為過(guò)渡層，數(shù)量分別為種群數(shù)的2/10和3/10。第二層粒子的適應(yīng)度僅次于最高領(lǐng)導(dǎo)層，螢火蟲(chóng)個(gè)體仍然攜帶一部分優(yōu)勢(shì)信息，需要賦予第二層粒子一種策略使其在保持優(yōu)勢(shì)信息的同時(shí)又能向更優(yōu)粒子學(xué)習(xí)。第三層粒子的適應(yīng)度中等，需要賦予一種方法來(lái)兼顧種群的探索與開(kāi)發(fā)能力的平衡。最后一層稱之為探索層，數(shù)量占種群數(shù)的4/10。由于該層中粒子的適應(yīng)度較差，導(dǎo)致其開(kāi)發(fā)能力弱而探索能力強(qiáng)，因此探索層主要負(fù)責(zé)跟隨優(yōu)秀粒子探索更多的未知空間，即種群的探索工作。

金字塔學(xué)習(xí)模型有如下優(yōu)點(diǎn)：

(1)每只螢火蟲(chóng)都只需要運(yùn)動(dòng)一次，有效解決了多次運(yùn)動(dòng)產(chǎn)生振蕩的問(wèn)題。且越高層的螢火蟲(chóng)被學(xué)習(xí)的機(jī)會(huì)越多，符合螢火蟲(chóng)向更亮個(gè)體移動(dòng)的特性。

(2)不同層螢火蟲(chóng)的開(kāi)發(fā)與探索能力存在差別。L1層粒子適應(yīng)度最好，開(kāi)發(fā)能力最強(qiáng)，L4層粒子適應(yīng)度最差，探索能力最強(qiáng)。每一層粒子根據(jù)自身特點(diǎn)選擇相應(yīng)的策略進(jìn)行學(xué)習(xí)，在尋優(yōu)的同時(shí)有效維持了算法探索與開(kāi)發(fā)間的平衡。

2.2 多策略協(xié)同

PMFA-MCS中，按金字塔結(jié)構(gòu)將種群分為了4層，每一層螢火蟲(chóng)使用不同的策略進(jìn)行更新。4種策略有機(jī)結(jié)合，在不同特征的層上實(shí)施，以協(xié)同提高螢火蟲(chóng)算法的整體性能。迭代一次完成后，種群依據(jù)適應(yīng)度進(jìn)行重新排序，保證種群內(nèi)的信息共享。下面詳細(xì)介紹每一層螢火蟲(chóng)的特點(diǎn)及更新策略。

2.2.1 領(lǐng)導(dǎo)層

螢火蟲(chóng)種群按金字塔結(jié)構(gòu)分層后，最高層由適應(yīng)度最好的N/10個(gè)粒子組成(設(shè)種群數(shù)量為N)，儲(chǔ)存了種群的優(yōu)勢(shì)信息。為保持這些優(yōu)勢(shì)信息不被丟失且還能尋得更有用的信息，讓最高領(lǐng)導(dǎo)層的粒子只在自身周?chē)\(yùn)動(dòng)進(jìn)行局部開(kāi)發(fā)。因此，在第一層螢火蟲(chóng)的移動(dòng)公式上引入貪婪柯西突變策略。柯西變異算子可以幫助粒子迅速逃離局部最優(yōu)，而貪婪策略可以保存種群的優(yōu)勢(shì)信息。加入柯西變異進(jìn)行隨機(jī)擾動(dòng)后螢火蟲(chóng)的移動(dòng)公式為

(5)

cauchy() 是柯西變異生成的隨機(jī)數(shù)。如果粒子使用該策略后的適應(yīng)值比原來(lái)更優(yōu)，則用當(dāng)前位置取代之前的位置，引導(dǎo)其余個(gè)體進(jìn)化。反之則繼續(xù)保留原來(lái)的位置，儲(chǔ)存種群原有的信息。

2.2.2 過(guò)渡層

根據(jù)分組規(guī)則，中間過(guò)渡層由L2和L3層組成。L2中螢火蟲(chóng)的適應(yīng)度僅次于L1，其開(kāi)發(fā)能力強(qiáng)于探索能力，并且儲(chǔ)存有一部分的優(yōu)勢(shì)信息。為保持優(yōu)勢(shì)信息不被丟失的同時(shí)還能向更優(yōu)粒子學(xué)習(xí)，提出一種雙領(lǐng)導(dǎo)機(jī)制，即L2中的螢火蟲(chóng)在自身周?chē)\(yùn)動(dòng)的同時(shí)，由L1中的兩個(gè)粒子引導(dǎo)，向更優(yōu)空間進(jìn)行探索。具體的移動(dòng)公式如下

xid(t+1)=r1*xid(t)+r2*β1*(xjd-xid(t))+r3*β2*(xkd-xid(t))+α*ε

(6)

式中：j和k是L1中的兩個(gè)粒子，r1、r2和r3是(0，1)之間服從均勻分布的隨機(jī)數(shù)，且r1+r2+r3=1。

第三層由適應(yīng)度中等的粒子組成，只儲(chǔ)存了少部分的優(yōu)勢(shì)信息，需兼顧開(kāi)發(fā)與探索能力的平衡。為加快收斂速度和開(kāi)發(fā)精度，將精英鄰域搜索策略分配給L3層粒子。鄰域搜索策略是指給種群中的粒子指定一個(gè)優(yōu)化區(qū)間，令該粒子只在這一特定區(qū)間內(nèi)進(jìn)行進(jìn)化。許多學(xué)者對(duì)此進(jìn)行了深入研究，Wang等[10]將一種全局鄰域搜索機(jī)制引入PSO，獲得了不錯(cuò)的優(yōu)化效果。全局鄰域搜索機(jī)制的定義如下

Xi=r1*Xi+r2*gbest+r3*(Xa-Xb)

(7)

式中：gbest為全局最優(yōu)粒子，Xa和Xb為種群中隨機(jī)選取的兩個(gè)粒子，r1、r2和r3是(0，1)內(nèi)的隨機(jī)數(shù)，且r1+r2+r3=1。 隨后，Wang等[11]在全局鄰域搜索機(jī)制的基礎(chǔ)上，將兩個(gè)粒子的選取方式由全部種群中隨機(jī)選擇改為在當(dāng)前粒子的k鄰域中隨機(jī)選擇，這一改進(jìn)有效提高了FA的性能。

本算法中，根據(jù)金字塔模型的吸引方式，L3層中的個(gè)體要向前兩層隨機(jī)選擇樣本學(xué)習(xí)，而L2中粒子數(shù)多于L1，故大概率學(xué)習(xí)對(duì)象在L2層中。本文在該搜索機(jī)制的基礎(chǔ)上，將最高層和第二層的領(lǐng)域稱為精英領(lǐng)域，提出一種精英鄰域搜索策略。搜索公式如下所示

xid(t+1)=r1*xid(t)+r2*gbest+r3*(xjd-xkd)+α*S*ε

(8)

式中：gbest是全局最優(yōu)粒子，可以增大L3中的粒子向L1區(qū)域?qū)W習(xí)的概率；j和k是從L1和L2中隨機(jī)選取的兩個(gè)粒子 (j≠k)；r1、r2、r3為3個(gè)取值在(0，1)之間的隨機(jī)數(shù)，且r1+r2+r3=1。

2.2.3 探索層

PMFA-MCS中，底部探索層中的粒子適應(yīng)度最差，儲(chǔ)存的優(yōu)勢(shì)信息最少，側(cè)重于算法的全局探索。FA中每只螢火蟲(chóng)更新時(shí)只選擇一個(gè)對(duì)象進(jìn)行學(xué)習(xí)，種群因此較難逃脫局部極值。因此，為讓L4中螢火蟲(chóng)能夠較快速地跳出局部最優(yōu)，令其從更高層中隨機(jī)選擇3個(gè)粒子進(jìn)行學(xué)習(xí)，提高螢火蟲(chóng)個(gè)體運(yùn)動(dòng)的多樣性并探索到更多的搜索區(qū)域。L4層螢火蟲(chóng)選擇3個(gè)樣本學(xué)習(xí)的公式如下所示

xid(t+1)=xid(t)+r1*β1*(xjd-xid(t))+r2*β2*(xkd-xid(t))+r3*β3*(xzd-xid(t))+α*ε

(9)

式中：j、k和z是從前面3層中隨機(jī)選擇的3個(gè)粒子，r1、r2和r3是(0，1)內(nèi)服從均勻分布的隨機(jī)數(shù)，且r1+r2+r3=1。

2.3 算法流程

由上述算法思想，給出PMFA-MCS的流程如下：

步驟1 初始化PMFA-MCS參數(shù)，設(shè)置維度為D，螢火蟲(chóng)種群為N，最大評(píng)估次數(shù)MAX_FEs；

步驟2 隨機(jī)初始化螢火蟲(chóng)的位置，并計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值。

步驟3 將螢火蟲(chóng)按照亮度進(jìn)行排序，并按照金字塔模型分成4層；

步驟4L1螢火蟲(chóng)按式(5)更新位置，從L2開(kāi)始至L4，分別按照式(6)、式(8)和式(9)更新位置；

步驟5 檢驗(yàn)是否滿足終止條件。滿足則運(yùn)行結(jié)束并輸出結(jié)果，不滿足跳轉(zhuǎn)到步驟3。

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

3.1 基準(zhǔn)測(cè)試函數(shù)

本文將使用兩組測(cè)試函數(shù)來(lái)檢測(cè)PMFA-MCS的性能，各測(cè)試函數(shù)的最優(yōu)解都是其在定義域內(nèi)的最小值。所有實(shí)驗(yàn)均使用VC++6.0軟件，基于win10系統(tǒng)進(jìn)行，處理器為Intel(R)Core(TM)i7-6700。

第一組經(jīng)典測(cè)試集由12個(gè)函數(shù)組成，該組函數(shù)在文獻(xiàn)[8]中被使用，其中f1～f7為單峰函數(shù)，一般用于測(cè)試算法的開(kāi)發(fā)能力；f8～f12為多峰函數(shù)，適用于測(cè)試算法的全局探索能力。第二組包含20個(gè)測(cè)試函數(shù)，每個(gè)函數(shù)的定義分類(lèi)參見(jiàn)文獻(xiàn)[12]。

3.2 與改進(jìn)螢火蟲(chóng)算法比較

在本節(jié)中，為了驗(yàn)證提出的算法的性能，使用12個(gè)經(jīng)典的基準(zhǔn)測(cè)試集函數(shù)，將PMFA-MCS與FA[1]、MFA[13]、WSSFA[14]、VSSFA[15]、RaFA[3]、ApFA[16]和LVFA[17]進(jìn)行比較。比較的算法使用相同的參數(shù)，維度D設(shè)置為30，最大評(píng)估次數(shù)MAX_FEs設(shè)置為5×105，螢火蟲(chóng)種群個(gè)數(shù)N=20。 PMFA-MCS算法中參數(shù)，γ=1/Γ2，Γ為優(yōu)化函數(shù)的域長(zhǎng)度，衰減因子C設(shè)置為10。所有算法運(yùn)行30次，尋優(yōu)結(jié)果的平均值和標(biāo)準(zhǔn)差見(jiàn)表1。

表1 8種算法在12個(gè)測(cè)試函數(shù)上的實(shí)驗(yàn)對(duì)比結(jié)果

表1列出了所有算法的平均最優(yōu)值、標(biāo)準(zhǔn)方差和w/t/l的結(jié)果。其中，符號(hào)w表示PMFA-MCS在函數(shù)上優(yōu)于比較算法；符號(hào)t表示PMFA-MCS在函數(shù)上與比較算法相當(dāng)；符號(hào)l表示PMFA-MCS結(jié)果不如其它比較算法。從表中可知，PMFA-MCS尋優(yōu)性能總體上優(yōu)于其它7種算法。在所測(cè)試的12個(gè)基本測(cè)試函數(shù)上，PMFA-MCS的性能比FA、WSSFA和VSSFA都要好。與MFA相比，僅在f5和f12上結(jié)果更差，在f6上結(jié)果與MFA一致，而在其余9個(gè)測(cè)試函數(shù)上都要比MFA的結(jié)果更好；與RaFA相比，PMFA-MCS在除f6外所有單峰函數(shù)上尋優(yōu)精度都要更高，表明算法局部開(kāi)發(fā)能力較強(qiáng)，多峰函數(shù)中，在f9和f10上結(jié)果更優(yōu)，在f11上結(jié)果相當(dāng)；與ApFA相比，PMFA-MCS僅在f12上結(jié)果更差，在f6上結(jié)果相當(dāng)，在剩余測(cè)試函數(shù)上結(jié)果更好；與LVFA相比，單峰函數(shù)方面情況與RaFA類(lèi)似；多峰函數(shù)上，PMFA-MCS僅在f12效果更差。整體而言，PMFA-MCS與各比較算法相比具有較高的尋優(yōu)精度和穩(wěn)定性。

為了進(jìn)一步比較算法的性能差距，對(duì)算法結(jié)果進(jìn)行Friedman檢驗(yàn)。表2列出了以上8種算法的Friedman檢測(cè)結(jié)果。從表中可以看出，PMFA-MCS秩均值均小于其它比較算法，即PMFA-MCS和其它7種螢火蟲(chóng)算法相比，性能最優(yōu)。

表2 8種算法在測(cè)試函數(shù)上的Friedman檢驗(yàn)結(jié)果

圖1展示了8種算法在給定的12個(gè)基準(zhǔn)測(cè)試函數(shù)上的收斂過(guò)程。從圖中可以看出，PMFA-MCS該組測(cè)試函數(shù)上的收斂速度比FA、WSSFA、VSSFA、MFA快。在函數(shù)f1、f2、f3、f4、f7、f9、f10和f11上，PMFA-MCS的尋優(yōu)過(guò)程均要快于其它7種算法，且在f1、f3、f9、f11上，PMFA-MCS提前收斂。對(duì)于函數(shù)f6，MFA、RaFA、ApFA和PMFA-MCS均提前收斂。而在函數(shù)f5、f10上，PMFA-MCS后來(lái)居上，最終在尋優(yōu)結(jié)果上實(shí)現(xiàn)了對(duì)其它比較算法的超越，驗(yàn)證了該分層結(jié)構(gòu)學(xué)習(xí)模型具有提高粒子逃逸局部最優(yōu)的能力。

圖1 8種螢火蟲(chóng)算法收斂曲線

3.3 時(shí)間復(fù)雜度分析

對(duì)于給定問(wèn)題f，計(jì)算其函數(shù)值的時(shí)間復(fù)雜度為O(f)，Gmax為算法的最大迭代次數(shù)。對(duì)于FA、VSSFA、WSSFA、MFA和ApFA，螢火蟲(chóng)需要向剩余所有個(gè)體學(xué)習(xí)，故需兩個(gè)循環(huán)來(lái)遍歷種群，時(shí)間復(fù)雜度為O(Gmax*N2*(D+f))。 而算法RaFA中，每個(gè)粒子只需要在迭代過(guò)程中移動(dòng)一次，所以其復(fù)雜度為O(Gmax*N*(D+f))。 LVFA使用分層學(xué)習(xí)模型，每一層粒子只需運(yùn)動(dòng)一次且最高層粒子不運(yùn)動(dòng)，故其時(shí)間復(fù)雜度為O(Gmax*N*(k-1)/k*(D+f))，k為層數(shù)。本文提出的PMFA-MCS算法中，每只螢火蟲(chóng)只需要運(yùn)動(dòng)一次，其時(shí)間復(fù)雜度與ApFA算法一致，為O(Gmax*N*(D+f))。 表3列出了比較算法的時(shí)間復(fù)雜度，從中可以看出，本文提出的算法的時(shí)間復(fù)雜度要優(yōu)于FA、VSSFA、WSSFA、MFA和ApFA，與RaFA相當(dāng)，比LVFA差。由于LVFA中最高層的優(yōu)勢(shì)粒子不運(yùn)動(dòng)，而PMFA-MCS中領(lǐng)導(dǎo)層使用柯西突變策略來(lái)發(fā)掘更有用的信息，所以PMFA-MCS在性能上優(yōu)于LVFA。

表3 8種算法時(shí)間復(fù)雜度

3.4 與相關(guān)算法比較

為進(jìn)一步測(cè)試PMFA-MCS的性能，本節(jié)使用第二組測(cè)試函數(shù)，將PMFA-MCS與改進(jìn)DE算法CoDE[18]、JADE[19]和jDEscop[20]，改進(jìn)PSO算法CLPSO[21]和HCOPSO[12]，改進(jìn)ABC算法AABCLS[22]、ABCVSS[23]和BABC[24]進(jìn)行比較。測(cè)試函數(shù)的維度設(shè)置為D=50， 算法最大評(píng)估次數(shù)設(shè)置MAX_FEs=5000*D， 其它參數(shù)設(shè)置依據(jù)相應(yīng)參考文獻(xiàn)。算法在每個(gè)函數(shù)上獨(dú)立運(yùn)行25次，實(shí)驗(yàn)結(jié)果見(jiàn)表4。從表4中可知，PMFA-MCS和HCOPSO二者優(yōu)化性能大致相當(dāng)。具體來(lái)看，相比于3種改進(jìn)的差分算法，PMFA-MCS均分別在13個(gè)函數(shù)上勝出，在6個(gè)、6個(gè)、5個(gè)函數(shù)上處于劣勢(shì)。與CLPSO相比，PMFA-MCS僅在f8、f14、f17、f19以及f20上性能較差，在f7上性能相當(dāng)，在其余14個(gè)函數(shù)上均能勝出。與HCOPSO相比，PMFA-MCS在10個(gè)函數(shù)上性能相當(dāng)，在5個(gè)函數(shù)上處于劣勢(shì)，但差距都很小。而相對(duì)于3種改進(jìn)人工蜂群算法，PMFA-MCS的優(yōu)化性能分別在12個(gè)、10個(gè)、9個(gè)函數(shù)上性能更優(yōu)，且僅在f8、f10、f14、f17及f19、f20處于劣勢(shì)，說(shuō)明對(duì)于這些問(wèn)題，ABC處理效果更優(yōu)。總的來(lái)看，在f1～f7、f9～f13、f18及f20上，PMFA-MCS現(xiàn)出較高的性能，其余函數(shù)性能處于劣勢(shì)甚至效果最差。

表4 9種算法在20個(gè)測(cè)試函數(shù)上的優(yōu)化結(jié)果

表5給出了9種算法在20個(gè)測(cè)試函數(shù)上的Friedman檢驗(yàn)結(jié)果。其中，PMFA-MCS的秩均值最小，故PMFA-MCS的綜合性能最優(yōu)。

表5 9種算法在20個(gè)測(cè)試函數(shù)上的Friedman檢驗(yàn)結(jié)果

3.5 算法策略分析

PMFA-MCS使用金字塔模型和多種策略協(xié)同來(lái)提高FA的性能。為了測(cè)試每一種策略對(duì)算法的影響，利用11個(gè)測(cè)試函數(shù)對(duì)每種策略進(jìn)行了實(shí)驗(yàn)。所涉及的算法描述見(jiàn)表6。

表6 不同策略的算法描述

表7給出了不同策略組合的算法運(yùn)行結(jié)果。從表中可以看出，PMFA在11個(gè)函數(shù)上的結(jié)果都要優(yōu)于FA，驗(yàn)證了金字塔分層模型性能要優(yōu)于全吸引模型。除了f4、f12外，PMFA+S1、PMFA+S2、PMFA+S3、PMFA+S4和PMFA-MCS在所有函數(shù)上的測(cè)試結(jié)果都要優(yōu)于PMFA，說(shuō)明各種策略可以幫助PMFA獲得更好的解。其中，第二種策略對(duì)于PMFA性能的改善在總體上要優(yōu)于其它3種策略。對(duì)于f4，雖然PMFA+S1、PMFA+S3和PMFA+4的結(jié)果都要比PMFA差，但PMFA-MCS的結(jié)果卻優(yōu)于PMFA，說(shuō)明通過(guò)融合4種策略后的算法將比使用單一策略時(shí)優(yōu)化性能更高。

表7 不同策略組合時(shí)的算法運(yùn)行結(jié)果

表8給出了不同策略算法組合的Friedman檢驗(yàn)結(jié)果。從表中可以看出，PMFA+S2的秩均值排第二，小于PMFA+S1、PMFA+S3和PMFA+S4，這與前文分析一致。

表8 不同策略算法秩均值檢驗(yàn)結(jié)果

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

針對(duì)螢火蟲(chóng)算法使用全吸引模型和單一策略而容易陷入局部最優(yōu)的問(wèn)題，本文提出了基于金字塔模型和多策略協(xié)同的螢火蟲(chóng)算法。PMFA-MCS將種群分成4層，每層粒子向更高層優(yōu)勢(shì)粒子和自身學(xué)習(xí)，形成金字塔模型，避免粒子多次運(yùn)動(dòng)產(chǎn)生的振蕩。每層粒子使用不同的策略進(jìn)行學(xué)習(xí)，平衡了算法的探索與開(kāi)發(fā)能力，提高了算法的尋優(yōu)精度。實(shí)驗(yàn)部分，將本文算法與其它7種改進(jìn)螢火蟲(chóng)算法以及其它8種群智能算法進(jìn)行比較，結(jié)果表明本文算法具有更好的優(yōu)化性能。