一種改進的自適應步長的人工螢火蟲算法

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150407.1107.001.html

一種改進的自適應步長的人工螢火蟲算法

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

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

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

關鍵詞：人工螢火蟲算法；自適應步長；覓食行為；全局收斂性

DOI:10.3969/j.issn.1673-4785.201403025

中圖分類號：TP183 文獻標志碼：A

收稿日期：2014-03-09. 網絡出版日期：2015-04-07.

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

作者簡介：

中文引用格式：唐少虎，劉小明. 一種改進的自適應步長的人工螢火蟲算法[J]. 智能系統學報, 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.

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

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

1人工螢火蟲算法原理

1.1基本的人工螢火蟲算法

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

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

1)初始化階段。

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

2)熒光素更新階段。

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

(1)

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

3)位置移動階段。

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

在全部滿足以上2個條件的螢火蟲中，根據式(2)計算選擇每個同伴螢火蟲的概率大小：

(2)

(3)

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

4)動態感知范圍更新階段。

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

(4)

式中：nt是調整螢火蟲鄰域集合大小的參數，β是調整螢火蟲動態感知范圍大小的參數。

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

1.2自適應步長人工螢火蟲算法

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

熒光因子為

(5)

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

基于熒光因子的自適應移動步長按照式(6)進行調整。

(6)

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

2改進的人工螢火蟲算法原理

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

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

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

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

(a) 對比實驗1

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

2.2FA-GSO算法收斂性分析

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

為了分析FA-GSO算法的收斂性，本文參考Solis提出的判定標準，給出分析證明。

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

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

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

另改進的算法使得螢火蟲都可以執行覓食行為，當覓食次數N→，則有L=S，進一步可得，即，所以滿足條件2。

2.3FA-GSO實現步驟

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

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

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

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

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

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

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

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

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

3)判斷是否達到指定的迭代次數，如果達到則轉向步驟4)，否則轉向2)。

4)輸出結果，程序結束。

3實驗結果與分析

為了驗證所設計的算法的有效性。選取4個標準測試函數進行驗證，并與GSO算法以及自適應步長GSO算法(A-GSO)進行比較。這4個常用的測試函數如下。

實驗的程序運行環境為：處理器Intel i3 CPU M380，主頻為2.53 GHz，內存2 GB，操作系統為Windows XP，集成開發環境為Visual Studio 2005，算法用VB.NET編寫。

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

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

表1　GSO、A-GSO和FA-GSO算法函數測試指標

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

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

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

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

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

4結束語

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

參考文獻:

[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]黃正新, 周永權. 自適應步長螢火蟲群多模態函數優化算法[J]. 計算機科學, 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]歐陽喆, 周永權. 自適應步長螢火蟲優化算法[J]. 計算機應用, 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]張軍麗, 周永權. 人工螢火蟲與差分進化混合優化算法[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]劉洲洲, 王福豹, 張克旺. 基于改進螢火蟲優化算法的WSN 覆蓋優化分析[J]. 傳感技術學報, 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]. 計算機工程與應用, 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項，獲大連市科學技術一等獎1項，北京市科學技術成果二、三等獎各1項，中國智能交通協會科學技術獎二等獎1項。申請發明專利3項，授權發明專利1項，授權實用新型專利1項，獲軟件著作權4項。發表學術論文40余篇，出版專著1部、譯著1部。