網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150407.1107.001.html

一種改進(jìn)的自適應(yīng)步長的人工螢火蟲算法

唐少虎1,2，劉小明1,2

(1.北方工業(yè)大學(xué) 電氣與控制工程學(xué)院，北京100144；2.北方工業(yè)大學(xué) 城市道路交通智能控制技術(shù)北京市重點(diǎn)實驗室，北京100144)

摘要：在基本的人工螢火蟲算法(GSO)中，螢火蟲的固定移動步長導(dǎo)致算法容易陷入局部最優(yōu)并可能出現(xiàn)函數(shù)適應(yīng)值的震蕩現(xiàn)象。在一些自適應(yīng)步長的人工螢火蟲算法(A-GSO)中，算法迭代過程中會出現(xiàn)一些螢火蟲的鄰域集合為空集的現(xiàn)象，這將導(dǎo)致算法收斂速度降低并陷入局部最優(yōu)值。為此，設(shè)計了改進(jìn)的自適應(yīng)步長的人工螢火蟲算法(FA-GSO)，改進(jìn)的算法針對鄰域無同伴的螢火蟲引入覓食行為尋找優(yōu)化方向并自適應(yīng)調(diào)整移動步長，進(jìn)一步提高求解精度和穩(wěn)定性，并給出了算法的收斂性分析，結(jié)合GSO、A-GSO 2種算法對多個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行尋優(yōu)并提取相關(guān)指標(biāo)。通過指標(biāo)對照，驗證了FA-GSO算法的有效性，表明算法可以改善函數(shù)尋優(yōu)的精度并提高迭代速度。

關(guān)鍵詞：人工螢火蟲算法；自適應(yīng)步長；覓食行為；全局收斂性

DOI:10.3969/j.issn.1673-4785.201403025

中圖分類號：TP183 文獻(xiàn)標(biāo)志碼：A

收稿日期：2014-03-09. 網(wǎng)絡(luò)出版日期：2015-04-07.

基金項目：國家自然科學(xué)基金資助項目(61374191)；國家“863”計劃資助項目(2012AA112401)；“十二五”國家科技支撐計劃課題專項經(jīng)費(fèi)資助項目(2014BAG03B01).

作者簡介：

中文引用格式：唐少虎，劉小明. 一種改進(jìn)的自適應(yīng)步長的人工螢火蟲算法[J]. 智能系統(tǒng)學(xué)報, 2015, 10(3): 470-475.

英文引用格式：TANG Shaohu, LIU Xiaoming. An improved adaptive step glowworm swarm optimization algorithm[J]. CAAI Transactions on Intelligent Systems, 2015, 10(3): 470-475.

An improved adaptive step glowworm swarm optimization algorithm

TANG Shaohu1,2, LIU Xiaoming1,2

(1. College of Electrical and Control Engineering, North China University of Technology, Beijing 100144, China; 2. Beijing Key Lab of Urban Intelligent Traffic Control Technology, North China University of Technology, Beijing 100144, China)

Abstract：In the basic glowworm swarm optimization (GSO), it is easy to fall into local optimum and the oscillation phenomenon of function adaptive values may occur because of the fixed step length. In some adaptive-step glowworm swarm optimization (A-GSO) algorithms, neighborhood sets of some fireflies may be empty in the iterative process of the algorithm, which leads to lower convergence speed and falls into local optimal value. Therefore, an improved foraging-behavior adaptive-step GSO (FA-GSO) algorithm was designed. The foraging behavior of the fireflies without neighborhood peer and adaptive step is introduced in order to find the optimization direction in the improved algorithm. The precision, stability, and global convergence analysis of FA-GSO is presented. After extracting and comparing the relevant optimization indicators of GSO, A-GSO and FA-GSO by several standard test functions, the effectiveness of the FA-GSO algorithm was verified, which indicates that the improved algorithm can improve the accuracy of function optimization and the iteration speed.

Keywords：glowworm swarm optimization; adaptive step; foraging behavior; global convergence

通信作者：唐少虎. E-mail: tshaohu@163.com.

大自然中的螢火蟲種類多種多樣，螢火蟲通過身體發(fā)光來達(dá)到各種生存目的。一般說來，螢火蟲的熒光素亮度越大越能找到其他螢火蟲或越容易找到食物。最后，由于尋找同伴或者食物的原因?qū)е略S多螢火蟲匯聚在一起。以此為啟發(fā)，K. N. Krishnanad和D. Ghose總結(jié)形成了基本的人工螢火蟲算法(glowworm swarm optimization, GSO)，螢火蟲最終會聚集成多個群體從而找到多個局部最優(yōu)值，算法設(shè)計的迭代機(jī)制不僅有利于求解局部最優(yōu)解，而且能夠有助于快速求解全局最優(yōu)值。所以，算法的優(yōu)點(diǎn)是在搜索局部和全局最優(yōu)解上具有速度快、效率高的特點(diǎn)，尤其在多模態(tài)函數(shù)求解問題等優(yōu)化方面有著廣泛的應(yīng)用，如模擬機(jī)器人、多信號源追蹤和定位、傳感器的噪聲測試等方面[1-4]。但另一方面，該算法也存在著一些問題，如算法全局最優(yōu)解的搜索受到約束，存在陷入局部最優(yōu)的風(fēng)險。由于算法設(shè)計的螢火蟲移動步長是固定的，不利于算法后期求解局部最優(yōu)值，而步長自適應(yīng)調(diào)整有利于提高求解的精度和收斂速度。周正新[5]和歐陽喆等[6]通過自適應(yīng)調(diào)整算法不同階段的移動步長，算法初期采取較大的步長有助于快速找到全局最優(yōu)鄰域，而后期較小的步長有利于精確求解局部最優(yōu)和加快收斂速度。

自適應(yīng)步長提高了算法的性能，但是在尋優(yōu)的精度和穩(wěn)定性方面還存在不足。本文針對基本和自適應(yīng)步長的算法在迭代過程中出現(xiàn)的螢火蟲鄰域集合為空集時，導(dǎo)致算法收斂速度降低并很快陷入局部最優(yōu)的問題，提出了一種改進(jìn)的自適應(yīng)步長的人工螢火蟲算法，即基于覓食行為的自適應(yīng)步長人工螢火蟲算法。

1人工螢火蟲算法原理

1.1基本的人工螢火蟲算法

人工螢火蟲算法(GSO)[7]是在2005年由K. N. Krishnanad和D. Ghose提出的一種新的群智能仿生優(yōu)化算法。算法模擬了自然界中螢火蟲求偶行為或者說是覓食行為。

GSO算法主要有4個階段：螢火蟲初始化階段、熒光素更新階段、位置移動階段以及動態(tài)感知范圍更新階段。算法流程如圖1所示。

1)初始化階段。

初始化算法各個參數(shù)、各螢火蟲的位置。螢火蟲隨機(jī)分布在目標(biāo)可行域中，每只螢火蟲攜帶的初始熒光素l0和感知半徑r0是相同的。

2)熒光素更新階段。

螢火蟲的熒光素大小與其所在搜索空間中的位置有直接關(guān)系，螢火蟲所在空間位置的評價值越高，則熒光素更新后的增長就越大，即螢火蟲的發(fā)光強(qiáng)度也越大。另外，螢火蟲的發(fā)光強(qiáng)度的強(qiáng)弱除了受所在空間值的影響，還和螢火蟲上一次迭代的熒光素大小以及揮發(fā)速度的快慢有關(guān)聯(lián)，螢火蟲位置更新完成后，下一次迭代開始前，所有螢火蟲的熒光素都會更新，熒光素根據(jù)式(1)更新：

(1)

式中：ρ(0<ρ<1)是螢火蟲的熒光素?fù)]發(fā)速度參數(shù)，γ是螢火蟲的螢火素更新率參數(shù)，li(t)是在第t次迭代中螢火蟲i的熒光素值，Ji(t+1)是在第t+1次迭代中螢火蟲i的評價值。

3)位置移動階段。

算法每次迭代后螢火蟲會在搜索空間中更新自己的位置，即位置移動。在螢火蟲i位置移動之前必須先找到一個符合條件的同伴，這個同伴必須滿足以下2個條件：a)要在螢火蟲i的感知范圍內(nèi)；b)攜帶的熒光素值要大于螢火蟲i的熒光素值。

在全部滿足以上2個條件的螢火蟲中，根據(jù)式(2)計算選擇每個同伴螢火蟲的概率大?。?/p>

(2)

(3)

式中：s是螢火蟲的移動步長，‖·‖是螢火蟲i和j的歐式空間距離。

4)動態(tài)感知范圍更新階段。

螢火蟲位置更新后，會動態(tài)調(diào)整自身感知范圍，調(diào)整的大小是基于感知范圍內(nèi)同伴的數(shù)量多少。具體根據(jù)式(4)進(jìn)行計算：

(4)

式中：nt是調(diào)整螢火蟲鄰域集合大小的參數(shù)，β是調(diào)整螢火蟲動態(tài)感知范圍大小的參數(shù)。

圖1　基本的GSO算法流程 Fig. 1　Flow chart of basic GSO algorithm

1.2自適應(yīng)步長人工螢火蟲算法

2011年歐陽喆等[6]提出了一種自適應(yīng)步長算法(adaptive-step GSO, A-GSO)，引入熒光因子概念以在算法搜索過程中動態(tài)改變螢火蟲移動步長，使算法避免陷入局部最優(yōu)，提高尋優(yōu)速度和精度。

熒光因子為

(5)

式中：Hi代表熒光因子，Xi是第i只螢火蟲所在空間位置，Xm是此次迭代中螢光素濃度最大的螢火蟲所在的空間位置，dmax是此次迭代中的最優(yōu)螢火蟲到其余全部螢火蟲的空間距離的最大值。

基于熒光因子的自適應(yīng)移動步長按照式(6)進(jìn)行調(diào)整。

(6)

式中：si代表調(diào)整后的螢光蟲移動步長，smax、smin代表螢火蟲移動步長的最大值和最小值，Hi代表熒光因子。

2改進(jìn)的人工螢火蟲算法原理

2.1基于覓食行為的自適應(yīng)步長人工螢火蟲算法

在GSO以及A-GSO算法中，算法運(yùn)行過程中可能出現(xiàn)一些螢火蟲的鄰域螢火蟲集合Ni(t)為空集的現(xiàn)象，對這些螢火蟲的在算法迭代過程中將會出現(xiàn)位置不移動的情況，這將導(dǎo)致算法收斂速度降低并易陷入局部最優(yōu)值。2011年張軍麗等[8]提出了利用人工魚群的覓食行為選擇下一個移動的位置，但是沒有考慮步長的自適應(yīng)調(diào)整。本文借鑒覓食行為，設(shè)計了鄰域集合為空集的螢火蟲自適應(yīng)步長移動策略，提出一種改進(jìn)的基于覓食行為的自適應(yīng)步長的人工螢火蟲算法(foraging-behavior adaptive-step GSO, FA-GSO)，算法改進(jìn)的基本思想是在鄰居集合Ni(t)為空集的螢火蟲位置更新前，先在其動態(tài)決策范圍Ni(t)內(nèi)執(zhí)行覓食行為，將該位置作為螢火蟲在下一時刻移動的方向，計算熒光因子得出動態(tài)調(diào)整的移動步長(自適應(yīng)步長)，然后進(jìn)行位置的移動，接著更新螢火蟲的感知范圍，最后計算螢火蟲的熒光素。這樣在不影響算法整體求解效率的基礎(chǔ)上能夠進(jìn)一步精確、快速求解最優(yōu)值。

為了測試覓食次數(shù)N對算法性能的影響，本文把該值分別設(shè)置為5個不同的值對同一函數(shù)的迭代值進(jìn)行對比。測試函數(shù)如下：

測試結(jié)果如圖2所示，從圖中可知，該值越小越易陷入局部最優(yōu)，但是該值增大后并不能保證提高算法搜索精度，如圖2(a)中覓食次數(shù)N=10時算法對函數(shù)的迭代精度最高，而圖2(b)中覓食次數(shù)N=10、15和30時，算法對函數(shù)的迭代精度相當(dāng)，其中精度最高是覓食次數(shù)為N=10時，因此在下面算法試驗對比分析中，將覓食次數(shù)設(shè)置為10。

(a) 對比實驗1

(b) 對比實驗2 圖2　覓食次數(shù)為不同值時函數(shù)迭代值對比 Fig. 2　Iterative value contrast of different foraging times

2.2FA-GSO算法收斂性分析

GSO算法、PSO算法(粒子群算法)都屬于隨機(jī)優(yōu)化算法，劉洲洲等[9]和張慧斌等[10]分別對2種算法的收斂性給出了分析證明，他們依據(jù)的是Solis[11]給出的隨機(jī)優(yōu)化算法收斂性判定標(biāo)準(zhǔn)。

為了分析FA-GSO算法的收斂性，本文參考Solis提出的判定標(biāo)準(zhǔn)，給出分析證明。

條件1f(D(x,ξ))≤f(x)，并且如果ξ∈S，則有f(D(x,ξ))≤f(ξ)。其中，f和S分別為目標(biāo)函數(shù)和可行解空間，D(x,ξ)為算法第t+1次的迭代結(jié)果。

定理 FA-GSO算法以概率1收斂于全局最優(yōu)解。

證明 根據(jù)1.2和2.1小節(jié)的描述，由于算法的步長是自適應(yīng)調(diào)整的，依據(jù)是式(5)、(6)，并且保證了無同伴螢火蟲的優(yōu)化搜索，通過判斷螢火蟲前后2次的熒光素大小確定位置是否移動，依據(jù)是式(3)和覓食策略，所以可以得出對于ξ∈S，有f(D(x,ξ))≤f(x)，即滿足條件1。

另改進(jìn)的算法使得螢火蟲都可以執(zhí)行覓食行為，當(dāng)覓食次數(shù)N→，則有L=S，進(jìn)一步可得，即，所以滿足條件2。

2.3FA-GSO實現(xiàn)步驟

綜上，基于覓食行為的自適應(yīng)步長人工螢火蟲算法步驟描述如下：

1)初始化螢火蟲群體和參數(shù)。將n只螢火蟲隨機(jī)地分布在搜索空間m維中，同時為每只螢火蟲初始化以相同的熒光素l0和感應(yīng)半徑r0，初始化最大移動步長smax，最小移動步長smin，螢光素?fù)]發(fā)系數(shù)ρ，覓食次數(shù)N，螢光素更新率γ以及設(shè)定迭代次數(shù)Nmax等，形成初始螢火蟲群；

2)執(zhí)行FA-GSO算法搜索。

對初始化的螢火蟲個體，分別執(zhí)行以下操作：

a)對每一個螢火蟲i按式(1)更新熒光素的值，判斷l(xiāng)i(t+1)≤li(t)是否成立，如果是則轉(zhuǎn)向b)，否則在轉(zhuǎn)向b)前，令xi(t+1)=xi(t)。

c)選擇t+1時刻移動的方向：

d)根據(jù)式(5)計算每個螢火蟲的熒光因子，并用式(6)計算動態(tài)移動步長。

e)螢火蟲進(jìn)行位置移動，根據(jù)式(3)更新位置；

f)根據(jù)式(4)更新螢火蟲的動態(tài)感知范圍。

3)判斷是否達(dá)到指定的迭代次數(shù)，如果達(dá)到則轉(zhuǎn)向步驟4)，否則轉(zhuǎn)向2)。

4)輸出結(jié)果，程序結(jié)束。

3實驗結(jié)果與分析

為了驗證所設(shè)計的算法的有效性。選取4個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行驗證，并與GSO算法以及自適應(yīng)步長GSO算法(A-GSO)進(jìn)行比較。這4個常用的測試函數(shù)如下。

實驗的程序運(yùn)行環(huán)境為：處理器Intel i3 CPU M380，主頻為2.53 GHz，內(nèi)存2 GB，操作系統(tǒng)為Windows XP，集成開發(fā)環(huán)境為Visual Studio 2005，算法用VB.NET編寫。

算法參數(shù)初始化為螢火蟲數(shù)量n為50，熒光素更新率r為0.6，熒光素?fù)]發(fā)系數(shù)p為0.4，初始熒光素大小為5，感知范圍為10，初始最小步長為0.01，最大步長為1，b=0.08，nt=5，覓食次數(shù)為10，最大迭代次數(shù)為300。對于上述4個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行試驗，維數(shù)為10。

表1列出4個算法對選定的標(biāo)準(zhǔn)測試函數(shù)求解所得到的最優(yōu)值、最差值、平均值和平均迭代次數(shù)比較，表中的平均迭代次數(shù)為10次獨(dú)立實驗所得到的迭代次數(shù)平均值。從表1中的數(shù)據(jù)對比中可以看到，F(xiàn)A-GSO算法平均通過42次迭代就找到了函數(shù)F1(x)最小值，而其他2種算法都沒有找到最小值，而A-GSO的最優(yōu)解要好于GSO迭代的最優(yōu)解。對比3種算法搜索其他3個函數(shù)的最優(yōu)解看，F(xiàn)A-GSO的最優(yōu)解也是最接近最小值，A-GSO的最優(yōu)解好于GSO搜索的最優(yōu)解，觀察另外2個指標(biāo)，即最差解和平均解的數(shù)據(jù)對照，也可以得出類似的結(jié)論。所以可以看出FA-GSO算法在搜索函數(shù)極值的最優(yōu)解、最差解以及平均解都要比另外3種算法有了一定程度上的提高，表明FA-GSO算法在收斂精度上要優(yōu)于其他2種算法。觀察表中的平均迭代次數(shù)，對比3個算法分別迭代給定的每個函數(shù)，可以看到FA-GSO算法平均迭代次數(shù)要少于其他2個算法，表明FA-GSO算法在收斂速度上要優(yōu)于另外2種算法。

表1　GSO、A-GSO和FA-GSO算法函數(shù)測試指標(biāo)

從圖3~6中看到，4個函數(shù)的FA-GSO算法迭代曲線很接近橫軸，即函數(shù)適應(yīng)值很接近最小值，迭代精度要好于另外2種算法，而且算法能夠找到最優(yōu)解前的迭代次數(shù)也是最少的。此外，觀察GSO算法在迭代函數(shù)F1(x)和F2(x)時都發(fā)生了適應(yīng)值曲線的震蕩現(xiàn)象，驗證了固定步長帶來的尋優(yōu)缺陷，而A-GSO和FA-GSO算法曲線都相對穩(wěn)定。從圖6中還可以看到A-GSO算法在迭代函數(shù)F4(x)時所搜索的最優(yōu)解并沒有好于GSO，但是FA-GSO的最優(yōu)解還是三者中精度最高的，說明搜尋機(jī)制改進(jìn)后的算法在尋優(yōu)精度方面有著較高的穩(wěn)定性。從圖中可以看出FA-GSO算法尋優(yōu)比較穩(wěn)定和快速。綜上所述，F(xiàn)A-GSO算法在函數(shù)搜索精度以及速度2個關(guān)鍵方面的性能有著明顯的改進(jìn)，從而有助于提高尋優(yōu)問題的求解效率。

圖3　F 1(x)函數(shù)值隨3個算法迭代曲線 Fig. 3　 Iterative values graph of F 1(x) tested by the three algorithms

圖4　F 2(x)函數(shù)值隨3個算法迭代曲線 Fig. 4　 Iterative values graph of F 2(x) tested by the three algorithms

圖5　F 3(x)函數(shù)值隨3個算法迭代曲線 Fig. 5　 Iterative values graph of F 3(x) tested by the three algorithms

圖6　F 4(x)函數(shù)值隨3個算法迭代曲線 Fig. 6　 Iterative values graph of F 4(x) tested by the three algorithms

4結(jié)束語

針對GSO和A-GSO算法存在的不足，為了有效避免算法過快陷入局部最優(yōu)和尋優(yōu)值的震蕩現(xiàn)象，通過改進(jìn)算法的迭代機(jī)制，在提出的FA-GSO算法中引入覓食行為并自適應(yīng)調(diào)整移動步長進(jìn)一步改善了局部搜索能力。本文采用3種算法對標(biāo)準(zhǔn)測試函數(shù)的試驗，對照相關(guān)迭代指標(biāo)并分析后得出FA-GSO算法尋優(yōu)結(jié)果優(yōu)于GSO和A-GSO算法，改進(jìn)的算法是有效的，提高了尋優(yōu)穩(wěn)定性、收斂速度和求解精度，從而改善了算法的迭代效率。未來將要做的工作內(nèi)容，可以在算法參數(shù)的優(yōu)化分析及算法的應(yīng)用(如交通信號和交通模型的優(yōu)化等)做進(jìn)一步研究和探索。

參考文獻(xiàn):

[1]LIAO Wenhua, KAO Yucheng, LI Yingshan. A sensor deployment approach using glowworm swarm optimization algorithm in wireless sensor networks[J]. Expert Systems with Applications, 38(10): 12180-12188.

[2]KRISHNANAND K N D, GHOSE D. Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications[J]. Multiagent and Grid Systems, 2006, 2(3) 209-222.

[3]KRISHNANAND K N, GHOSE D. Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions[J]. Swarm Intelligence, 2009, 3(2): 87-124.

[4]YANG Yan, ZHOU Yongquan, GONG Qiaoqiao. Hybrid artificial glowworm swarm optimization algorithm for solving system of nonlinear equations[J]. Journal of Computational Information Systems, 2010, 6(10) 3431-3438.

[5]黃正新, 周永權(quán). 自適應(yīng)步長螢火蟲群多模態(tài)函數(shù)優(yōu)化算法[J]. 計算機(jī)科學(xué), 2011, 38(7): 220-224.

HUANG Zhengxin, ZHOU Yongquan. Self-adaptive step glowworm swarm optimization algorithm for optimizing multimodal functions[J]. Computer Science, 2011, 38(7): 220-224.

[6]歐陽喆, 周永權(quán). 自適應(yīng)步長螢火蟲優(yōu)化算法[J]. 計算機(jī)應(yīng)用, 2011, 31(7): 1804-1807.

OUYANG Zhe, ZHOU Yongquan. Self-adaptive step glowworm swarm optimization algorithm[J]. Journal of Computer Applications, 2011, 31(7): 1804-1807.

[7]KRISHNANAND K N D, GHOSE D. Glowworm swarm optimization: a new method for optimizing multi-modal functions[J]. Computational Intelligence Studies, 2009, 1(1): 93-119

[8]張軍麗, 周永權(quán). 人工螢火蟲與差分進(jìn)化混合優(yōu)化算法[J]. 信息與控制, 2011, 40(5): 608-613.

ZHANG Junli, ZHOU Yongquan. A hybrid optimization algorithm based on artificial glowworm swarm and differential evolution[J]. Information and Control, 2011, 40(5): 608-613.

[9]劉洲洲, 王福豹, 張克旺. 基于改進(jìn)螢火蟲優(yōu)化算法的WSN 覆蓋優(yōu)化分析[J]. 傳感技術(shù)學(xué)報, 2013, 26(5): 675-682.

LIU Zhouzhou, WANG Fubao, ZHANG Kewang. Performance analysis of improved glowworm swarm optimization algorithm and the application in coverage optimization of WSNs[J]. Chinese Journal of Sensors and Actuators, 2013, 26(5): 675-682.

[10]張慧斌, 王鴻斌, 胡志軍. PSO算法全局收斂性分析[J]. 計算機(jī)工程與應(yīng)用, 2011, 47(34): 61-63.

ZHANG Huibin, WANG Hongbin, HU Zhijun. Analysis of particle swarm optimization algorithm global convergence method[J]. Computer Engineering and Applications, 2011, 47(34): 61-63.

[11]SOLIS F J, WETS R J B. Minimization by random search techniques[J]. Mathematics of Operations Research, 1981, 6(1): 19-30.

唐少虎，男，1986年生，博士研究生，主要研究方向為交通控制、群智能算法。

劉小明，男，1974年生，教授，博士，主要研究方向為交通控制、交通流理論。近年來主持國家級、省部級科研項目8項，獲大連市科學(xué)技術(shù)一等獎1項，北京市科學(xué)技術(shù)成果二、三等獎各1項，中國智能交通協(xié)會科學(xué)技術(shù)獎二等獎1項。申請發(fā)明專利3項，授權(quán)發(fā)明專利1項，授權(quán)實用新型專利1項，獲軟件著作權(quán)4項。發(fā)表學(xué)術(shù)論文40余篇，出版專著1部、譯著1部。