基于均勻局部搜索和可變步長的螢火蟲算法

王曉靜，彭 虎，鄧長壽，黃海燕，張 艷，譚旭杰

(九江學(xué)院 信息科學(xué)與技術(shù)學(xué)院，江西 九江 332005)

0 引言

Yang[1]研究了螢火蟲個(gè)體間相互吸引與發(fā)光亮度的關(guān)聯(lián)關(guān)系，以及螢火蟲的移動(dòng)特性，于2008年提出了一種新型群智能優(yōu)化算法，即螢火蟲算法(Firefly Algorithm, FA)。FA的基本思想是模擬螢火蟲的發(fā)光特性在一定區(qū)域內(nèi)尋找伙伴，向位置較優(yōu)的螢火蟲移動(dòng)，以達(dá)到尋優(yōu)的目的。螢火蟲算法操作簡單、參數(shù)少、收斂速度較快，已被成功地用于路徑優(yōu)化[2]、電頻譜分配[3]、水資源優(yōu)化配置[4]、板料成形優(yōu)化[5]、工程管柱設(shè)計(jì)[6]等優(yōu)化問題中，從而引起了國內(nèi)外學(xué)者的廣泛關(guān)注，成為智能計(jì)算領(lǐng)域的一個(gè)研究熱點(diǎn)。

螢火蟲算法也存在一些不足，比如后期收斂速度慢、易陷入局部最優(yōu)、尋優(yōu)結(jié)果依賴于初始種群和參數(shù)設(shè)置等。許多學(xué)者對其進(jìn)行了各種改進(jìn)。如臧睿等[6]將自適應(yīng)慣性權(quán)重引入標(biāo)準(zhǔn)螢火蟲算法，提高了算法的收斂速度。王翔等[7]設(shè)計(jì)了一種混沌局部搜索算子和替換算子，克服了螢火蟲算法收斂速度慢和易于早熟的缺陷。Wang等[8]設(shè)計(jì)了隨機(jī)吸引模型和三個(gè)鄰域搜索策略，以及動(dòng)態(tài)參數(shù)調(diào)整策略，提高了螢火蟲算法的搜索精度，增強(qiáng)了算法的魯棒性。Yu等[9-10]先后提出了基于個(gè)體最好位置與全局最好位置的步長設(shè)置策略[9]，以及非線性動(dòng)態(tài)調(diào)整步長策略[10]，提高了搜索質(zhì)量。劉金等[11]提出了圖形處理器(Graphics Processing Unit, GPU)上的維度并行隨機(jī)吸引策略螢火蟲算法，降低了標(biāo)準(zhǔn)螢火蟲算法的時(shí)間復(fù)雜度，提高了其優(yōu)化能力。陸克中等[12]提出了一種基于全局信息共享的自適應(yīng)FA，提高了收斂速度和收斂精度。

本文借鑒Peng等[13]提出的均勻局部搜索策略對差分進(jìn)化(Differential Evolution, DE)算法的改進(jìn)，在螢火蟲種群中隨機(jī)選擇兩個(gè)個(gè)體構(gòu)成一個(gè)局部空間，利用均勻設(shè)計(jì)實(shí)驗(yàn)設(shè)計(jì)方法，在此空間中尋找一個(gè)最優(yōu)個(gè)體并進(jìn)行迭代，以達(dá)到增強(qiáng)局部開采能力的目的，從而提高算法的收斂性能。為了彌補(bǔ)局部搜索可能出現(xiàn)的局部最優(yōu)和早熟的缺陷，考慮到螢火蟲位置更新時(shí)在局部和全局之間的平衡性，引入Yu等[10]提出的非線性動(dòng)態(tài)調(diào)整步長策略，利用當(dāng)前迭代次數(shù)和最大迭代次數(shù)建立起非線性變化的步長值對算法進(jìn)行改進(jìn)。通過12個(gè)測試函數(shù)的驗(yàn)證，證明了改進(jìn)算法的有效性，并針對不同維度問題中算法結(jié)果的差異，分析了原因并給出了解決辦法。

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

螢火蟲算法用搜索空間中的所有可行解模擬夜空中的螢火蟲個(gè)體，將問題的目標(biāo)函數(shù)適應(yīng)度值定義為螢火蟲所處位置的相應(yīng)解，將優(yōu)化過程模擬成螢火蟲個(gè)體的相互吸引和位置更新過程，將個(gè)體的優(yōu)勝劣汰過程類比為搜索和優(yōu)化過程中用好的可行解取代較差可行解的迭代過程。算法涉及兩個(gè)關(guān)鍵因素，即螢火蟲個(gè)體的發(fā)光亮度和相對吸引度。螢火蟲的發(fā)光亮度取決于自身所在位置的目標(biāo)值，亮度越高表示所處的位置越好，即目標(biāo)值越佳。吸引度與亮度相關(guān)，越亮的螢火蟲擁有越高的吸引力，可以吸引視線范圍內(nèi)亮度比其弱的螢火蟲往這個(gè)方向移動(dòng)。如果發(fā)光亮度相同，則螢火蟲各自隨機(jī)移動(dòng)。亮度和吸引度與螢火蟲之間的距離成反比，都隨著距離的增加而減小。

1.1 標(biāo)準(zhǔn)FA的基本思想

標(biāo)準(zhǔn)FA涉及的主要公式包括相對熒光亮度公式、相對吸引度公式和位置更新公式[14]如下所示：

熒光亮度為：

I(r)=I0e-γr

(1)

其中：I0為螢火蟲的最大熒光亮度，即r=0處的熒光亮度，與目標(biāo)函數(shù)值相關(guān)，目標(biāo)函數(shù)值越優(yōu)自身亮度越高；γ為光強(qiáng)吸收系數(shù)，以體現(xiàn)光強(qiáng)的減弱特性，在多數(shù)問題中γ∈[0.01，100]；r通常為螢火蟲i與j間的歐氏距離。

吸引度為：

β(r) =β0e-γr2

(2)

其中：β0為最大吸引度，即r=0處的吸引度；γ為光強(qiáng)吸收系數(shù)。

尋優(yōu)過程中螢火蟲j受螢火蟲i的吸引，從而向螢火蟲i靠近的位置更新公式為：

xj(t+ 1) =xj(t) +β(xi(t)-xj(t)) +αεj

(3)

其中：xj(t+ 1)為螢火蟲xj第t+1次移動(dòng)后的位置；α為步長因子，是[0,1]上的常數(shù)；ε為[0,1]上服從高斯分布的隨機(jī)因子。

1.2 標(biāo)準(zhǔn)FA步驟

在以上3個(gè)公式的基礎(chǔ)上，標(biāo)準(zhǔn)螢火蟲算法通過算法1的步驟完成尋優(yōu)過程。

算法1 標(biāo)準(zhǔn)FA。

1)

選取適應(yīng)度函數(shù)f(X),X= (x1,x2,…,xd)T

2)

初始化螢火蟲種群Xi(i=l, 2,…,n)

3)

初始化算法基本參數(shù)γ、β0、MaxFEs(最大評估次數(shù))

4)

5)

While (FEs

6)

Fori=1∶n

7)

Forj=1∶n

8)

If (Ij>Ii)

1）模型坐標(biāo)系：有限元模型坐標(biāo)系：模型建立在直角坐標(biāo)系（X，Y，Z）下，X 軸，沿河流方向并指向下游；Y 軸，垂直河流方向，指向山外；Z軸，豎直向上。

9)

根據(jù)式(2)計(jì)算相對吸引度

10)

根據(jù)式(3)螢火蟲Xi在d維空間向xj移動(dòng)

11)

計(jì)算適應(yīng)度值f(X)，更新熒光亮度

12)

FEs=FEs+1

13)

End if

14)

End for

15)

End for

16)

對所有螢火蟲排序,確定當(dāng)前最優(yōu)位置

17)

End while

18)

輸出結(jié)果

2 改進(jìn)的螢火蟲算法

2.1 均勻局部搜索

均勻設(shè)計(jì)是Wang等[15]于1981年提出的科學(xué)實(shí)驗(yàn)方法，其實(shí)驗(yàn)思想是找到一些散布得更均勻的點(diǎn)集，利用這些點(diǎn)集來安排實(shí)驗(yàn)，使得實(shí)驗(yàn)結(jié)果既有代表性，又有相對較少的實(shí)驗(yàn)次數(shù)，從而減少實(shí)驗(yàn)時(shí)間，節(jié)約實(shí)驗(yàn)成本。在相同的均勻性前提下，正交設(shè)計(jì)實(shí)驗(yàn)次數(shù)的量級是O(q2)，而均勻設(shè)計(jì)實(shí)驗(yàn)次數(shù)的量級是O(qlogq)。顯然后者在實(shí)驗(yàn)次數(shù)上占很大優(yōu)勢。

Peng等[13]基于均勻設(shè)計(jì)提出了均勻局部搜索(Uniform Local Search, ULS)算子，并將之用于增強(qiáng)DE算法的局部開采能力，實(shí)驗(yàn)結(jié)果證明了ULS優(yōu)異的局部搜索性能。均勻設(shè)計(jì)實(shí)驗(yàn)用均勻設(shè)計(jì)表來安排實(shí)驗(yàn)。均勻設(shè)計(jì)表是一個(gè)n行k列的表格，實(shí)驗(yàn)次數(shù)和水平個(gè)數(shù)相等，即n=q。用Un(qk)表示均勻設(shè)計(jì)表，其中U表示均勻設(shè)計(jì)，n表示實(shí)驗(yàn)次數(shù)，q表示每個(gè)因素的水平個(gè)數(shù)，k表示獨(dú)立因素的最大個(gè)數(shù)[16]。

如文獻(xiàn)[13]所述，ULS采用均勻設(shè)計(jì)表U7(76)進(jìn)行實(shí)驗(yàn)，如表1所示。構(gòu)建均勻設(shè)計(jì)表格的過程可參照文獻(xiàn)[17]。從表1中可以看出，均勻設(shè)計(jì)允許每個(gè)因素?fù)碛凶畲罂赡艿乃綌?shù)，因此，水平的數(shù)量等于實(shí)驗(yàn)數(shù)。研究中考慮到如下兩點(diǎn)，首先，此處的均勻局部搜索方法中，表1的最后一行全是“7”，這代表了一個(gè)多余的原生個(gè)體；其二，經(jīng)過多次實(shí)驗(yàn)驗(yàn)證，U6(66)是最合適的。因此，去掉均勻設(shè)計(jì)表U7(76)的最后一行從而構(gòu)成U6(66)均勻設(shè)計(jì)表。每個(gè)因素有6個(gè)水平能從實(shí)驗(yàn)得到有效的信息，水平數(shù)大于6就沒有必要，并且ULS還需要消耗更多的函數(shù)評估次數(shù)。

表1 均勻設(shè)計(jì)表U7(76)Tab. 1 Uniform design table U7(76)

以二維空間為例，如圖1所示[13]，均勻局部搜索就是在種群G中隨機(jī)選擇兩個(gè)個(gè)體A和B執(zhí)行一組實(shí)驗(yàn)，其搜索空間為A和B所構(gòu)成的2維空間，將每一維均勻的分解成6個(gè)部分代表6個(gè)水平。依據(jù)均勻設(shè)計(jì)表的U6(66)的第一列和第二列，在A和B形成的搜索空間中生成了6個(gè)實(shí)驗(yàn)個(gè)體。假設(shè)C是這6個(gè)實(shí)驗(yàn)個(gè)體中的最優(yōu)個(gè)體，那么C個(gè)體第一維的水平是1，第二維的水平是2。

在ULS算子中，如果問題的維數(shù)D大于6，則將D隨機(jī)的分成6組，ULS將構(gòu)建6個(gè)實(shí)驗(yàn)個(gè)體，花費(fèi)6次評估次數(shù)。作為一種通用的局部搜索框架，ULS能應(yīng)用到其他進(jìn)化算法中以提高改善搜索能力。ULS算子的步驟如算法2所示[13]。

算法2 ULS算子步驟。

1)

輸入：種群P、適應(yīng)度函數(shù)評估次數(shù)FEs。

2)

從種群P中隨機(jī)選擇兩個(gè)個(gè)體xi,G和xj,G。

3)

基于U6(66)在個(gè)體xi,G和xj,G之間構(gòu)建6個(gè)實(shí)驗(yàn)個(gè)體Y1,Y2,…,Y6。

4)

評估目標(biāo)函數(shù)值f(Y1),f(Y2),…,f(Y6)。

5)

從Y1,Y2,…,Y6中選取最優(yōu)個(gè)體O。

6)

If(f(xi,G)>f(O))

7)

xi,G=O

8)

End if

9)

FEs=FEs+6

10)

更新種群P，返回FEs。

圖1 二維搜索空間中兩個(gè)隨機(jī)個(gè)體的均勻局部尋優(yōu)示意圖 Fig. 1 Illustration of uniform local search with two randomly chosen individuals in two-dimensional search space

2.2 基于均勻局部搜索和可變步長策略的螢火蟲優(yōu)化算法

螢火蟲因亮度而相互吸引，如果某個(gè)個(gè)體周圍有太多螢火蟲亮度比其高，就會(huì)造成搜索過程中的震蕩，這種無意義的震蕩會(huì)增加時(shí)間復(fù)雜度。相反，如果這種吸引力很少，就會(huì)導(dǎo)致錯(cuò)過極優(yōu)值而過早收斂。因此，吸引的數(shù)量和范圍很重要。假如先把搜索過程限定在一定的范圍內(nèi)，搜索到該范圍內(nèi)的最優(yōu)值，再進(jìn)行擴(kuò)展，以局部最優(yōu)促成全局最優(yōu)，就是一個(gè)合理的優(yōu)化思路。ULS算子正好實(shí)現(xiàn)了這個(gè)思路。

在標(biāo)準(zhǔn)FA中，螢火蟲因相互吸引而進(jìn)行位置移動(dòng)更新，之后再執(zhí)行均勻局部搜索ULS算子進(jìn)行一次搜索，利用該算子優(yōu)異的局部搜索性能來提高FA的解質(zhì)量。雖然ULS是一個(gè)有效的提高收斂速度的方法，但是它是一個(gè)相對貪婪的機(jī)制，執(zhí)行次數(shù)越多，陷入局部極值的概率越大，因此，權(quán)衡收斂速度和種群多樣性，每一代種群執(zhí)行一次ULS。

在標(biāo)準(zhǔn)FA中，步長因子α的取值是固定的，這不能真正地反映搜索過程。通常較大的α取值適用于探索新的搜索空間，而較小的α取值適用于局部開采。因此，步長對于全局勘探和算法收斂有很大的影響。文獻(xiàn)[10]中VSSFA(Variable Step Size Firefly Algorithm)中可變步長策略平衡了螢火蟲的全局勘探和局部開采能力。在VSSFA中，步長α的調(diào)整公式如下：

α(t)=0.4/(1+exp(0.015*(t-maxG)/3))

(4)

其中：t是當(dāng)前迭代次數(shù)，maxG是最大迭代次數(shù)。在標(biāo)準(zhǔn)FA中，加入U(xiǎn)LS算子，提出基于均勻局部搜索的螢火蟲優(yōu)化算法(Uniform local search Firefly Algorithm, UFA)，該算法純粹從搜索過程進(jìn)行改進(jìn)。其算法步驟在算法3的基礎(chǔ)上略去第10)行即可。

在標(biāo)準(zhǔn)FA的基礎(chǔ)上，使用以上步長調(diào)整策略，再利用均勻局部搜索算子ULS，提出了基于均勻局部搜索和可變步長的螢火蟲優(yōu)化算法(Firefly Algorithm based on Uniform local search and Variable step size, UVFA)，從搜索過程和參數(shù)調(diào)整兩個(gè)方面對標(biāo)準(zhǔn)FA進(jìn)行優(yōu)化，其算法的步驟如算法3所示。UVFA與標(biāo)準(zhǔn)螢火蟲算法FA的區(qū)別主要體現(xiàn)在步驟的第10)行和第15)行，分別利用式(4)進(jìn)行步長調(diào)整和利用均勻局部搜索算子增強(qiáng)局部尋優(yōu)能力。

算法3 UVFA步驟。

1)

選取適應(yīng)度函數(shù)f(X),X= (x1,x2,…,xd)T

2)

初始化螢火蟲種群Xi(i=l, 2,…,n)

3)

初始化算法基本參數(shù)γ、β0、MaxFEs(最大評估次數(shù))

4)

FEs=n

5)

While (FEs

6)

Fori=1∶n

7)

Forj=1∶n

8)

If (Ij>Ii)

9)

根據(jù)式(2)計(jì)算相對吸引度

10)

根據(jù)式(4)計(jì)算步長α的值

11)

根據(jù)式(3)螢火蟲Xi在d維空間向xj移動(dòng)

12)

計(jì)算適應(yīng)度值f(X)，更新熒光亮度

13)

FEs=FEs+1

14)

End if

15)

利用ULS算子進(jìn)行局部搜索

16)

End for

17)

End for

18)

對所有螢火蟲排序,確定當(dāng)前最優(yōu)位置

19)

End while

20)

輸出結(jié)果

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

3.1 測試函數(shù)及算法參數(shù)設(shè)置

本文采用國際上廣泛使用的12個(gè)標(biāo)準(zhǔn)測試函數(shù)來分析和驗(yàn)證UVFA的收斂速度和解的質(zhì)量，這12個(gè)函數(shù)的名稱、形式、搜索范圍以及最優(yōu)值如表2所示，其中：函數(shù)f1～f7是單峰值函數(shù)，f8～f12是具有多個(gè)極小值的多峰值函數(shù)[18]。Sphere函數(shù)為非線性函數(shù)，不同維之間可分離，主要用于測試算法的尋優(yōu)精度；Schwefel2.22函數(shù)是具有明顯轉(zhuǎn)折點(diǎn)的非線性函數(shù)；Schwefel1.2函數(shù)的最優(yōu)解周圍具有很小的下降梯度；Schwefel2.21函數(shù)為倒錐形非線性函數(shù)；Rosenbrock函數(shù)為多維病態(tài)二次函數(shù)，極難進(jìn)行極小化；Step函數(shù)計(jì)算一個(gè)動(dòng)態(tài)系統(tǒng)的階躍響應(yīng)；Quartic with noise函數(shù)是凹形非線性函數(shù)； Schwefel 2.26函數(shù)是具有正弦特點(diǎn)的多個(gè)局部極小值的函數(shù)；Rastrigin函數(shù)使用余弦函數(shù)產(chǎn)生局部極小值，是典型多峰函數(shù)，域內(nèi)有大量局部極小點(diǎn)，容易陷入局部最優(yōu)，而不能得到全局最優(yōu)解；Ackley函數(shù)為連續(xù)、旋轉(zhuǎn)、不可分離的多峰函數(shù)，具有大量局部最優(yōu)點(diǎn)；Griewank函數(shù)是典型的非線性多模態(tài)函數(shù)，通常被認(rèn)為是優(yōu)化算法很難處理的復(fù)雜多模態(tài)函數(shù)；Penalized1函數(shù)使用正弦函數(shù)產(chǎn)生大量局部極小值。

實(shí)驗(yàn)硬件環(huán)境為Intel Core i7-4770 CPU 3.40 GHz處理器，8 GB內(nèi)存，64位操作系統(tǒng)；軟件環(huán)境為Windows 7操作系統(tǒng)，Matlab 7.11.0版本。

表2 基準(zhǔn)測試函數(shù)[18]Tab. 2 Benchmark functions

為了說明UVFA的性能，將其算法參數(shù)和對比算法的參數(shù)設(shè)置成相同的，具體如表3所示。實(shí)驗(yàn)中，12個(gè)測試函數(shù)的維度均設(shè)置為30維，每個(gè)函數(shù)運(yùn)行30次。

表3 算法參數(shù)設(shè)置Tab. 3 Algorithm parameters settings

為了客觀公正地評價(jià)實(shí)驗(yàn)結(jié)果，采用統(tǒng)計(jì)學(xué)中的Wilcoxon秩和檢驗(yàn)與Friedman檢驗(yàn)對實(shí)驗(yàn)結(jié)果進(jìn)行分析。Wilcoxon秩和檢驗(yàn)基于樣本的秩和來判斷兩個(gè)樣本是否來自相同的總體，用以分析對比算法的實(shí)驗(yàn)結(jié)果是否存在顯著差異[19]。Friedman檢驗(yàn)利用秩分析多個(gè)獨(dú)立樣本的總體分布是否存在顯著差異，通過對各樣本的秩均值進(jìn)行排名反映算法性能的優(yōu)劣，秩均值越小表示算法性能越好[20]。

3.2 實(shí)驗(yàn)結(jié)果及算法收斂性對比分析

將標(biāo)準(zhǔn)FA、明智步長策略的螢火蟲算法(Wise Step Strategy for Firefly Algorithm, WSSFA)[9]、VSSFA、UFA和UVFA運(yùn)行結(jié)果的平均誤差值和標(biāo)準(zhǔn)方差進(jìn)行對比，并給出秩和檢驗(yàn)結(jié)果，具體數(shù)據(jù)如表4所示。表中用“-”、“+”和“≈”3個(gè)符號分別代表該算法解的質(zhì)量較UVFA解的質(zhì)量差、優(yōu)和相似。帶下劃線數(shù)字表示對比算法中的平均誤差最優(yōu)值。此外，通過對FA、WSSFA、VSSFA與UFA實(shí)驗(yàn)數(shù)據(jù)的秩和檢驗(yàn)結(jié)果統(tǒng)計(jì)顯示，在12個(gè)測試函數(shù)中，UFA全部優(yōu)于其他3種算法。FA、WSSFA、VSSFA、UFA和UVFA實(shí)驗(yàn)結(jié)果的Friedman檢驗(yàn)秩均值分別為4.54、4.31、3.15、1.85、1.15，進(jìn)一步說明了UVFA的性能是對比算法中最優(yōu)的。

針對12個(gè)測試函數(shù)，UFA的尋優(yōu)結(jié)果都顯著地優(yōu)于標(biāo)準(zhǔn)FA、WSSFA和VSSFA，UVFA較UFA的結(jié)果也有了改善。特別是，UFA針對每個(gè)函數(shù)的平均誤差值均比FA、WSSFA和VSSFA有了大幅改進(jìn)?？梢?，ULS算子對UVFA的貢獻(xiàn)是顯著的，可變步長因子在函數(shù)f1、f2、f3、f5、f7、f10上的效果較好。

為了更好地反映改進(jìn)算法的收斂過程，用圖2展示了FA、WSSFA、VSSFA、UFA和UVFA對前12個(gè)代表函數(shù)的收斂曲線并進(jìn)行對比。圖2中橫坐標(biāo)表示函數(shù)評價(jià)次數(shù)，其上界是150 000；縱坐標(biāo)表示30次實(shí)驗(yàn)?zāi)繕?biāo)函數(shù)均值以10為底的對數(shù)形式lg(f)。

由圖2可以得出以下結(jié)論：第一，改進(jìn)的局部搜索螢火蟲算法的收斂速度明顯快于標(biāo)準(zhǔn)螢火蟲算法。這種現(xiàn)象是由于ULS算子較強(qiáng)的局部開采能力而產(chǎn)生的，同時(shí)可變步長策略又平衡了全局探索能力，故可以提升算法的收斂速度。第二，在進(jìn)化的初期階段，UFA與UVFA的收斂速度相當(dāng)；在進(jìn)化的后期，UVFA的收斂速度快于UFA。這是合理的。在進(jìn)化后期，種群中最優(yōu)解已經(jīng)陷入局部極值，沒有改進(jìn)空間；與此同時(shí)，種群中其他的較優(yōu)解還存在一定改進(jìn)的空間，故UVFA的收斂速度會(huì)快于UFA，在函數(shù)f1、f2、f3、f5、f7、f10上，UVFA算法的求解質(zhì)量也明顯地優(yōu)于UFA。

表4 算法FA、WSSFA、VSSFA、UFA、UVFA的實(shí)驗(yàn)平均誤差值(標(biāo)準(zhǔn)方差)對比(30維)Tab. 4 Mean error values (standard deviation) comparison of standard FA, WSSFA,VSSFA, UFA, and UVFA (D=30)

圖2 算法FA、WSSFA、VSSFA、UFA、UVFA針對12個(gè)測試函數(shù)的收斂曲線 Fig. 2 Convergence curves of standard FA, WSSFA,VSSFA, UFA, and UVFA on all test functions

3.3 時(shí)間開銷分析

表5是標(biāo)準(zhǔn)FA、WSSFA、VSSFA、UFA和UVFA在12個(gè)函數(shù)上運(yùn)行30次所用的平均機(jī)器時(shí)間數(shù)據(jù)。可以明顯地看出UFA和UVFA在時(shí)間上的優(yōu)勢，其理由是ULS算子在搜索過程中對空間的分解和重組需要一定的時(shí)間開銷，但這個(gè)時(shí)間與FA搜索過程的時(shí)間開銷相抵消，并且要小于FA的時(shí)間開銷。

表5中的平均時(shí)間行是每種算法在運(yùn)行12個(gè)測試函數(shù)時(shí)所耗用的平均時(shí)間，速度比是UVFA的平均時(shí)間/相應(yīng)算法的平均時(shí)間得到的值，體現(xiàn)了UVFA的速度優(yōu)勢?？梢钥闯觯琔VFA相對于標(biāo)準(zhǔn)FA、WSSFA和VSSFA的速度比分別是0.31、0.20和0.30，相對于UFA的速度比是0.99，說明了ULS算子在優(yōu)化過程中對收斂速度的貢獻(xiàn)是相當(dāng)明顯的。

3.4 維數(shù)變化分析

通常算法的性能會(huì)隨著問題規(guī)模的增大而降低，為了觀察這種影響，表6列出了FA、VSSFA、UFA和UVFA在5維、20維100維等不同維度上的平均誤差值和平均標(biāo)準(zhǔn)方差值。帶下劃線數(shù)據(jù)表示對比算法中的平均誤差最優(yōu)值，并進(jìn)行了秩和檢驗(yàn)，檢驗(yàn)結(jié)果的表示同上。每個(gè)函數(shù)分別獨(dú)立運(yùn)行30次。由于10維、50維、200維數(shù)據(jù)與100維數(shù)據(jù)結(jié)果相似，因此，沒有一一列出。

通過對以上5、20和100幾種維度的數(shù)據(jù)進(jìn)行秩和檢驗(yàn)分析，我們發(fā)現(xiàn)，UFA在每一種維度上和FA、VSSFA結(jié)果相比，均顯示出了絕對的優(yōu)勢；UVFA除了具有UFA的優(yōu)勢之外，在低維度問題中，較UFA的優(yōu)化效果不明顯，隨著維度的增大，搜索結(jié)果顯示出普遍的小幅度優(yōu)化。表7是各算法實(shí)驗(yàn)結(jié)果的Friedman檢驗(yàn)排名，在5維和20維問題中，UFA排名是第一，在100維等其他高維度中UVFA排名第一。從統(tǒng)計(jì)學(xué)的角度，說明了UVFA在所有參與比較的算法中是最優(yōu)的。另外，UFA和UVFA的實(shí)驗(yàn)時(shí)間大幅度降低，在搜索速度上有很大的改進(jìn)。綜合以上結(jié)果可見UVFA具有較好的穩(wěn)定性和魯棒性，不僅適用于各種低維問題，也適用于復(fù)雜的高維問題。

表5五個(gè)算法的實(shí)驗(yàn)平均機(jī)器時(shí)間對比s

Tab. 5 Experiment average machine time comparison among five algorithms s

表6 各種維度下算法FA、VSSFA、UFA、UVFA的實(shí)驗(yàn)平均誤差值(標(biāo)準(zhǔn)方差)對比Tab. 6 Mean error values (standard deviation) comparison of standard FA, VSSFA, UFA, and UVFA under various dimensions

表7 各算法實(shí)驗(yàn)結(jié)果的Friedman檢驗(yàn)值Tab. 7 Experimental results of algorithms by Friedman test under different dimensions

3.5 ULS算子參數(shù)變化對UVFA的影響分析

以上實(shí)驗(yàn)是在U6(66)均勻設(shè)計(jì)表上進(jìn)行的，考慮到針對不同規(guī)模問題，不同大小的均勻設(shè)計(jì)表會(huì)對實(shí)驗(yàn)結(jié)果有所影響，因此，設(shè)定水平數(shù)q=12，獨(dú)立因素的最大個(gè)數(shù)k=12，即U12(1212)均勻設(shè)計(jì)表，以及q=k=18，即U18(1818)均勻設(shè)計(jì)表，分別在5、20、100三種維度上分別進(jìn)行UVFA仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表10所示。需要說明的是，如果維數(shù)D<因素?cái)?shù)k，則只取前D個(gè)因素，即均勻設(shè)計(jì)表中前D列的值進(jìn)行實(shí)驗(yàn)。

從秩和檢驗(yàn)的結(jié)果可以發(fā)現(xiàn)，U12和U18的結(jié)果并沒有顯示出優(yōu)勢，甚至反而使尋優(yōu)結(jié)果變差，驗(yàn)證了文獻(xiàn)[13]中關(guān)于使用U6(66)進(jìn)行均勻局部搜索是最合適的選擇。

表8 各種維度下不同ULS算子參數(shù)對算法UVFA的實(shí)驗(yàn)平均誤差值對比Tab. 8 Comparison of experimental mean error values with different ULS parameters to UVFA under various dimensions

4 結(jié)語

本文利用ULS算子改進(jìn)標(biāo)準(zhǔn)FA，提高了螢火蟲算法的搜索質(zhì)量和收斂速度，為了平衡螢火蟲全局和局部的搜索能力，特增加可變步長策略，對均勻局部搜索螢火蟲算法進(jìn)一步優(yōu)化。從實(shí)驗(yàn)的結(jié)果來看，在不同維度的優(yōu)化問題中，改進(jìn)的UVFA的質(zhì)量均明顯地優(yōu)于標(biāo)準(zhǔn)FA和動(dòng)態(tài)步長螢火蟲算法VSSFA，并且實(shí)驗(yàn)時(shí)間明顯縮短，同時(shí)，UVFA也顯示出較簡化版UFA的優(yōu)越性，證明了改進(jìn)算法是有效的。

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

[1] YANG X S. Nature-Inspired Metaheuristic Algorithms [M]. Beckington, UK: Luniver Press, 2008: 81-96.

[2] 徐曉光,胡楠,徐禹翔,等.改進(jìn)螢火蟲算法在路徑規(guī)劃中的應(yīng)用[J]. 電子測量與儀器學(xué)報(bào),2016,30(11):1735-1742.(XU X G, HU N, XU Y X, et al. Application of improved firefly algorithm in path planning [J]. Journal of Electronic Measurement and Instrumentation, 2016, 30(11): 1735-1742.)

[3] 李衛(wèi)軍.蛙跳螢火蟲算法及其在無線電頻譜分配中的應(yīng)用[J].微型機(jī)與應(yīng)用,2015,34(5):16-18.(LI W J. Study on leapfrog firefly algorithm and its application in the radio spectrum allocation [J]. Microcomputer & Its Applications, 2015, 34(5): 16-18.)

[4] 張凱,沈潔.基于螢火蟲算法和熵權(quán)法的水資源優(yōu)化配置[J].水資源保護(hù),2016,32(3):50-53.(ZHANG K, SHEN J. Optimal allocation of water resources based on firefly algorithm and entropy method [J]. Water Resources Protection, 2016, 32(3): 50-53.)

[5] 王曉新,陳磊.基于高斯過程的螢火蟲算法及其在板料成形優(yōu)化設(shè)計(jì)中的應(yīng)用[J].鍛壓技術(shù),2015,40(12):26-34.(WANG X X, CHEN L. Firefly algorithm and application in sheet metal forming optimization based on Gaussian process [J]. Forging and Stamping Technology, 2015, 40(12): 26-34.)

[6] 臧睿,李輝輝.基于標(biāo)準(zhǔn)螢火蟲算法的改進(jìn)與仿真應(yīng)用[J].計(jì)算機(jī)科學(xué),2016,43(S2):113-116.(ZANG R, LI H H. Improvement and simulation application based on standard firefly algorithm [J]. Computer Science, 2016, 43(S2): 113-116.)

[7] 王翔,于浩杰,顏敏,等.一種新穎的改進(jìn)螢火蟲算法[J].計(jì)算機(jī)與應(yīng)用化學(xué),2014(8):987-992.(WANG X, YU H J, YAN M, et al. A novel improved firefly algorithm [J]. Computers and Applied Chemistry, 2014(8): 987-992.)

[8] WANG H, CUI Z, SUN H, et al. Randomly attracted firefly algorithm with neighborhood search and dynamic parameter adjustment mechanism [J]. Soft Computing, 2017, 21(18): 5325-5339.

[9] YU S, SU S, LU Q, et al. A novel wise step strategy for firefly algorithm [J]. International Journal of Computer Mathematics, 2014, 91(12): 2507-2513.

[10] YU S, ZHU S, MA Y, et al. A variable step size firefly algorithm for numerical optimization [J]. Applied Mathematics and Computation, 2015, 263(C): 214-220.

[11] 劉金,吳志健,吳雙可,等.GPU上的維度并行隨機(jī)吸引策略螢火蟲算法[J].計(jì)算機(jī)工程與科學(xué),2016,38(10):1961-1966.(LIU J, WU Z J, WU S K, et al. A dimensionally parallel firefly algorithm with random attraction on GPU[J]. Computer Engineering and Science,2016,38(10):1961-1966.)

[12] 陸克中,孫俊.全局信息共享的自適應(yīng)FA算法[J].計(jì)算機(jī)工程與科學(xué),2016,38(6):1164-1170.(LU K Z, SUN J. An adaptive FA algorithm based on global information sharing [J]. Computer Engineering and Science, 2016, 38(6): 1164-1170.)

[13] PENG H, WU Z J, DENG C S. Enhancing differential evolution with commensal learning and uniform local search [J]. Chinese Journal of Electronics, 2017, 26(4): 725-733.

[14] YANG X S. Firefly algorithm, stochastic test functions and design optimisation [J]. International Journal of Bio-Inspired Computation, 2010, 2(2): 78-84.

[15] WANG Y, FANG K T. A note on uniform distribution and experimental design [J]. Science Bulletin, 1981, 26(6): 485-489.

[16] 王元.均勻設(shè)計(jì)──一種試驗(yàn)設(shè)計(jì)方法[J].科技導(dǎo)報(bào),1994,12(5):20-21.(WANG Y. Uniform design ─ a method for experimental design [J]. Science and Technology Review, 1994, 12(5): 20-21.)

[17] FANG K T, MA C, WINKER P, et al. Uniform design: theory and application [J]. Technometrics, 2000, 42(3): 237-248.

[18] YAO X, LIU Y, LIN G. Evolutionary programming made faster [J]. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 82-102.

[19] ROSNER B, GLYNN R J, LEE M L T. Incorporation of clustering effects for the Wilcoxon rank sum test: a large-sample approach [J]. Biometrics, 2003, 59(4): 1089-1098.

[20] FRIEDMAN M. The use of ranks to avoid the assumption of normality implicit in the analysis of variance [J]. Journal of the American Statistical Association, 1937, 32(200): 675-701.

This work is partially supported by the National Natural Science Foundation of China (61364025, 61763019), the Science and Technology Project of Jiangxi Provincial Education Department (GJJ161072, GJJ161076).

WANGXiaojing, born in 1980, M. S., lecturer. Her research interests include evolutionary computation.

PENGHu, born in 1981, Ph. D., lecturer. His research interests include evolutionary computation.

DENGChangshou, born in 1972, Ph. D., professor. His research interests include intelligent computing, data mining.

HUANGHaiyan, born in 1982, M. S., lecturer. Her research interests include evolutionary computation.

ZHANGYan, born in 1979, M. S., lecturer. Her research interests include evolutionary computation.

TANXujie, born in 1978, M. S., lecturer. His research interests include intelligent computing.