基于混合變異的螢火蟲群優化算法

張小瓊　秦亮曦

(廣西大學計算機與電子信息學院　廣西 南寧 530004)

?

基于混合變異的螢火蟲群優化算法

張小瓊秦亮曦

(廣西大學計算機與電子信息學院廣西 南寧 530004)

摘要基本螢火蟲群優化GSO(Glowworm Swarm Optimization)算法在求解函數全局尋優問題時，存在后期收斂速度慢、容易陷入局部極值等問題。為此，提出一種基于混合變異的螢火蟲群優化算法。該算法用混沌變異和邊界變異來增加種群的多樣性，避免算法陷入局部最優，且能使算法獲得精度更高的解。運用六個標準測試函數進行測試，結果表明，改進后的螢火蟲群優化算法比基本GSO算法具有更高的尋優速度、尋優精度和收斂率。

關鍵詞螢火蟲群優化算法混沌變異邊界變異混合變異函數優化

GLOWWORM SWARM OPTIMISATION BASED ON HYBRID MUTATION

Zhang XiaoqiongQin Liangxi

(School of Computer and Electronic Information,Guangxi University,Nanning 530004,Guangxi,China)

AbstractWhile basic glowworm swarm optimisation (GSO) is applied to solving the problem of global optimisation of functions, it has the problems of slow convergence in later period and being prone to falling into local optimum. Therefore we put forward a hybrid mutation-based algorithm of glowworm swarm optimisation. The algorithm uses chaotic mutation and boundary mutation to improve the diversity of the population, and prevents the algorithm from falling into local optimum; moreover this enables the algorithm to achieve a more accurate solution. Six standard test functions are applied to the test, results show that the improved glowworm swarm optimisation is better than the basic GSO in terms of the optimisation speed and precision and the convergence rate.

KeywordsGlowworm swarm optimisation (GSO)Chaotic mutationBoundary mutationHybrid mutationFunction optimisation

0引言

螢火蟲群優化GSO算法是印度學者K N Krishnanand和Debasish Ghose于2005年模擬自然界螢火蟲求偶或覓食行為而提出的一種新型仿生群體智能優化算法[1]。該算法通過螢火蟲個體之間的相互吸引達到尋優的目的，其計算速度快，需要調節的參數少，簡單易于實現，具有很強的通用性，已逐漸成為計算智能研究領域一個新的研究方向，并成功應用于傳感器的噪聲測試[2]、聚類分析[3]、模擬機器人[4]、函數優化[5]等。但與其他群智能算法一樣，也存在著后期收斂速度慢、容易陷入局部極值、求解精度不高等問題。

針對這些問題，文獻[5]提出一種基于熒光因子的自適應調整步長的方法，使得螢火蟲算法尋優的解獲得了更高的精度。文獻[6]提出了一種帶交尾行為的混沌螢火蟲優化算法，通過混沌進行初始化，提高了初始解的質量，又在GSO算法中引入交配行為，進一步提高了螢火蟲群優化算法的收斂速度和求解精度。文獻[7,8]分別運用高斯變異和自適應t分布變異的方法增加螢火蟲種群的多樣性，提高了解的精度和尋優的速度。本文采用混沌變異和邊界變異的混合變異策略，對陷入局部極值的螢火蟲利用混沌變異的方法搜索周圍的最優解來代替本身；對飛出邊界的螢火蟲進行邊界變異，避免邊界螢火蟲聚集的行為，提高種群的效率。

1基本螢火蟲群優化算法

基本螢火蟲群優化算法思想來源于自然界的螢火蟲用閃光來吸引其他螢火蟲，借此進行溝通、求偶等。閃光越亮代表螢火蟲吸引力越大，最后形成螢火蟲聚集在亮度較大的螢火蟲周圍。螢火蟲閃光的亮度取決于螢火蟲攜帶的的熒光素值，熒光素值越大，螢火蟲的閃光越亮。

算法初始時在D維解空間內隨機生成N只螢火蟲，螢火蟲i的當前位置表示為Xi(t)，初始時每只螢火蟲都攜帶相同的螢火素值l0，并且具有相同的決策半徑r0。在螢火蟲移動的過程中，如果螢火蟲j在螢火蟲i的決策范圍內，并且螢火蟲j熒光素值比螢火蟲i的高，螢火蟲i就以一定的概率向其鄰居螢火蟲j移動。螢火蟲所在位置對應一個適應度值，熒光素的大小與螢火蟲所在位置的適應度值有關，熒光素值越大，所在位置越好，即有較好的適應度值。最后，螢火蟲會聚集在適應度值較高的螢火蟲周圍。在完成初始化后，GSO每次迭代包括三個過程：熒光素更新、位置更新、感知范圍更新。

1) 熒光素更新階段

熒光素與螢火蟲所在位置密切相關，所在位置越好，熒光素值就越大，閃光越亮；熒光素除了受所在位置影響，還與螢火蟲上一時刻所攜帶的熒光素值和揮發速度有關。熒光素值根據下式進行更新：

li(t)=(1-ρ)li(t-1)+γf(Xi(t))

(1)

式中，li(t)表示在t時刻螢火蟲i的熒光素值，ρ(0<ρ<1)為常數，表示熒光素的揮發速度，γ也為常數，表示熒光素更新率，f(Xi(t))表示在t時刻螢火蟲i所在位置的適應度值。

2) 位置更新階段

螢火蟲i的移動方向由其所有鄰居螢火蟲的熒光素決定，鄰居螢火蟲是在螢火蟲i的決策范圍內熒光素值比螢火蟲i的熒光素值大的螢火蟲集合，即：

Ni(t)={j:‖Xj(t)-Xi(t)‖

(2)

式中，‖·‖表示歐氏距離，ri(t)表示t時刻螢火蟲i的決策半徑。對所有鄰居螢火蟲j，根據下式計算t時刻螢火i向螢火蟲j移動的概率：

(3)

螢火蟲i根據Pij(t)選擇移動方向為j，然后根據下式更新螢火蟲i的位置：

(4)

其中，s為移動步長。

3) 感知范圍更新

移動后，每只螢火蟲根據鄰居螢火蟲的數量動態地更新各自的感知范圍，如果鄰居螢火蟲數量多，則減小感知范圍，反之增大感知范圍，如下式更新：

ri(t+1)=min{rs,max[0,ri(t)+β(nt-|Ni(t)|)]}

(5)

其中，rs是控制螢火蟲感知范圍閥值，β是領域變化率，ri(t)(0

2混合變異優化GSO算法

2.1種群混沌變異機制

文獻[8]提出的ATM-AGSO算法進行變異時，非最優螢火蟲采用自適應t分布變異，最優螢火蟲采用高斯變異，即：

Xi(t)=Xi(t)×[1+k×H(t)]k=1-(t-1)/(Tmax-1)t=1,2,…,Tmax

(6)

其中，k為變異控制因子，當i為非最優螢火蟲時，H(t)為以迭代次數t為參數自由度的t分布，當i是最優螢火蟲時，H(t)為服從均值為0方差為1的高斯分布。但這種變異方法變異的幅度相對較大，容易錯過附近更優解。為提高算法局部搜索的遍歷性和效率，本文采用混沌立方映射[9]產生混沌變量來代替ATM-AGSO算法中的隨機變量H(t)，進行混沌變異。該策略表示為：

Xi n(t) = Xi(t)×[1 + k×Z(n)]n = 1,2,…,Mk = 1-(t-1)/Tmaxt = 1,2,…,Tmax

(7)

式中，t表示當前迭代次數，Tmax表示算法最大迭代次數，Z(n)為混沌序列。

混沌是自然界廣泛存在的非線性現象，是一種狀似隨機混亂，卻具有遍歷性和規律性的非隨機運動，能按自身規律在一定范圍內不重復地遍歷所有狀態[10]。運用混沌運動的這些特性對GSO算法進行優化搜索，有助于算法跳出局部最優，增加種群的多樣性，增強算法的全局搜索能力。混沌立方映射產生的是(-1，1)之間的序列，只要立方映射的迭代初值不為0，混沌就會發生。首先在D維解空間內根據式(8)隨機產生一個(-1，1)之間的D維向量，作為第一個混沌變量：

Z(1)=1-2rand(1,D)

(8)

然后根據下式對每一維迭代M-1次，最后得到M個混沌序列。

Z(n+1)=4Z(n)3-3Z(n)-1≤Z(n)≤1n=1,2,…,M-1

(9)

利用產生的混沌序列根據式(7)進行變異，比較變異擾動前、后的的適應度值。若變異產生的最優適應度值優于原有個體的適應度值，就用該最優適應度值所處的狀態取代原有個體狀態。這樣根據已有個體狀態增加混沌擾動項Xi×k×Z(n)，獲得有更好適應度值的個體，種群的多樣性得到了保證，也賦予了算法跳出局部極值的能力，同時提高了搜索能力。

2.2邊界變異

在其他一些GSO算法中，當螢火蟲飛出搜索區域后，通常將搜索空間的邊界值賦值給該螢火蟲：

ifXi(t)>XmaxXi(t)=Xmax

或者

ifXi(t)

其中，Xmax、Xmin分別是搜索區域的最大和最小邊界值。經過這樣的處理后，所有越界的螢火蟲會在邊界聚集，其狀態將趨于相同，不僅降低了種群的多樣性，也會影響算法的全局搜索能力；如果邊界附近存在局部最優，還使得算法容易陷入局部極值。

文獻[11]把邊界變異引入到量子粒子群算法中，有效控制了粒子越界的行為，提高了算法的全局搜索能力。同理，我們也可以把邊界變異引入到螢火蟲群算法中，在每代螢火蟲越界時進行邊界變異，該變異策略可表示為：

ifXi(t)>XmaxXi(t)=Xmax×(1-c×rand())

或者

ifXi(t)

其中，c=0.01。從上述變異過程可以看出，對越界螢火蟲進行變異操作后，螢火蟲不再聚集在邊界處，而是分布在搜索區域內，克服了螢火蟲聚集邊界的缺點，同時增加了種群的多樣性，避免了螢火蟲陷入局部極值，提高了算法的整體搜索速度。

2.3HM-GSO混合變異描述

HM-GSO算法是將混沌變異和邊界變異相結合，在算法迭代過程中，隨著種群的不斷進化，個體之間的差異逐漸變小，并出現螢火蟲嚴重聚集的現象，導致算法極容易陷入局部極值。此時對種群中的每只螢火蟲進行混沌變異搜索，對搜索過程中越界的螢火蟲進行邊界變異，最后用混沌擾動后的最優狀態更新為當前螢火蟲的狀態。每次螢火蟲群變異后用最優螢火蟲的狀態和適應度值和公告板上的最優螢火蟲比較，公告板將記錄更優的螢火蟲的狀態和適應度值。當公告板上的適應度值在連續三次迭代中沒有改變或者改變很小(|變化量|

2.4HM-GSO算法步驟

HM-GSO算法的具體步驟設計如下：

1) 初始化ρ、γ、β、s、l0、r0、rs、nt、N、D、Tmax、u等參數，并隨機初始化螢火蟲種群；

2) 計算所有螢火蟲的適應度值，初始化公告板；

3) 根據式(1)對所有螢火蟲進行熒光素更新；

4) 用式(2)計算所有螢火蟲的鄰居集合，式(3)計算螢火蟲的選擇概率，然后用輪盤賭方法選擇移動目標，根據式(4)進行位置更新；

5) 用式(5)更新螢火蟲的感知半徑；

6) 計算當前種群每個個體的適應度值，若最優適應度值優于公告板，則更新公告板的狀態和適應度值；

7) 判斷是否陷入局部最優值，如果公告板上的最優適應度值在連續三次迭代中沒有發生改變或者改變很小(|變化量|

圖1　HM-GSO算法流程圖

8) 在每個螢火蟲周圍進行混沌變異，對飛出邊界的螢火蟲用邊界變異策略控制在搜索范圍內，計算混沌擾動后的適應度值，取最優適應度值與原適應度值比較，若優于原有適應度值，則用擾動后最優適應度值所在的位置取代原有位置。比較變異后螢火蟲群的最優螢火蟲和公告板的最優螢火蟲，如果由優于公告板，則更新公告板的狀態和適應度值；

9) 完成一次迭代，判斷終止條件是否滿足(迭代次數達到Tmax)，如果滿足，記錄結果，退出迭代，否則轉步驟3)，進入下一次迭代。

HM-GSO算法的流程如圖1所示。

3HM-GSO算法性能測試與分析

3.1實驗測試函數

為了驗證HM-GSO算法的收斂速度、收斂率和求解精度等，將本文提出的基于混合變異的螢火蟲群(HM-GSO)算法與基本GSO算法及文獻[8]提出的基于自適應t分布混合變異的人工螢火蟲(ATM-AGSO)算法進行性能比較，采用了6個標準測試函數進行對比測試實驗。6個測試函數如下：

標準測試函數如表1所列。

表1　標準測試函數

3.2實驗參數設置

在GSO算法中，步長s根據經驗選取，F1、F3中取為5，F2、F4、F5和F6中取為1，對于ATM-AGSO算法和HM-GSO算法，s取值為0.3，其他實驗參數設置如表2所示。

表2　實驗參數設置

3.3實驗平臺

本實驗的運行測試環境為：處理器為Intel(R) Core(TM) i3-3110M CPU，主頻2.4 GHz，內存4 GB，操作系統：Windows 7，集成開發環境為Matlab R2012a。

3.4實驗仿真結果與分析

仿真實驗中對這三種算法用這6個標準測試函數分別進行20次獨立實驗，對每一個函數求得這三種算法的最優值、最差值、均值、收斂迭代次數、平均收斂時間和收斂率等，并通過收斂曲線來比較三種算法的收斂速度和求解精度，從而測試本文算法的有效性。在給出收斂精度ε=10-5的情況下，如果滿足|Fitnessbest-Fitness|<ε，則認為算法收斂；否則為不收斂。其中，Fitnessbest為實際求得的最優解，Fitness為理論上的最優解。

從表3、表4可以看出，GSO對6個函數都沒有收斂，HM-GSO和ATM-AGSO測試6個函數時的收斂率達到100%，收斂精度以HM-GSO最大，ATM-AGSO次之，GSO最小。對于函數F1，HM-GSO的平均最優解精度比GSO提高了42個數量級，平均收斂迭代次數比ATM-AGSO減少了65次。對于函數F2，HM-GSO的平均最優解精度比GSO提高了30個數量級，比ATM-AGSO提高了20個數量級，平均收斂迭代次數比ATM-AGSO減少了85次。對于函數多個F3，HM-GSO的最優解精度達到了e-75，平均最優解精度遠優于GSO，比ATM-AGSO提高了40個數量級，平均收斂迭代次數比ATM-AGSO減少了47次。對于函數F4，HM-GSO的平均最優解精度比GSO提高了63個數量級，比ATM-AGSO提高了45個數量級，平均收斂迭代次數比ATM-AGSO減少了61次。對于函數F5，HM-GSO的平均最優解精度比GSO提高了52個數量級，比ATM-AGSO提高了33個數量級，平均收斂迭代次數比ATM-AGSO減少了44次。對于函數F6，HM-GSO的最優解精度達到了e-102，平均最優解精度比ATM-AGSO提高了26個數量級，平均收斂迭代次數比ATM-AGSO減少了12次。

表3　三種算法收斂情況對比

表4　三種算法最優解對比

結合圖2-圖7分析，HM-GSO的尋優曲線更加穩定。隨著迭代次數的增加，在增加不到50時，HM-GSO的最優函數值就到達了收斂精度。HM-GSO的平均收斂時間也比ATM-AGSO更少，且在同一次迭代里面。HM-GSO獲得的最優函數值比GSO和ATM-AGSO更優，說明HM-GSO比GSO和ATM-AGSO具有更快的收斂速度，更高的求解精度。可見，HM-GSO算法在搜索過程中通過混沌變異和邊界變異混合變異的方法增加了種群的多樣性，避免了算法陷入局部最優、容易聚集邊界的缺點，克服了過早收斂的問題。因而全局尋優能力、求解精度、收斂速度和穩定性等方面比其他兩種算法都得到了提高，具有更好的尋優能力。

圖2　F1函數尋優收斂曲線　　圖3　F2函數尋優收斂曲線

圖4　F3函數尋優收斂曲線　　圖5　F4函數尋優收斂曲線

圖6　F5函數尋優收斂曲線　　圖7　F6函數尋優收斂曲線

4結語

本文提出了一種基于混合變異的螢火蟲群優化算法。算法中運用混沌的方法進行變異，并對越界的螢火蟲進行邊界變異，使算法避免陷入局部極值，提高了尋優速度和求解精度。通過函數優化實驗可以看出，改進后的算法優于基本螢火蟲群優化算法，較ATM-AGSO算法有更快的收斂速度和更精確的函數值。下一步我們將融合其他算法，并應用于求解實際問題中。

參考文獻

[1] Krishnanand K N,Ghose D.Glowworm swarm optimization:a new method for optimizing multi-modal functions[J].International Journal of Computational Intelligence Studies,2009,1(1):93-119.

[2] Krishnanand K N,Ghose D.A glowworm swarm optimization based multi-robot system for signal source localization[M]//Liu D K,Wang L F,Tan K C.Design and Control of Intelligent Robotic Systems.Berlin:Springer,2009:53-74.

[3] Huang Z X,Zhou Y Q.Using glowworm swarm optimization algorithm for clustering analysis[J].Journal of Convergence Information Technology,2011,6(2):78-85.

[4] Krishnanand K N,Ghose D.Chasing multiple mobile signal sources:a glowworm swarm optimization approach[C]//Third Indian International Conference on Artificial Intelligence (IICAI 07).Indian,2007.

[5] 歐陽喆,周永權.自適應步長螢火蟲優化算法[J].計算機應用,2011,31(7):1804-1807.

[6] 黃凱,周永權.帶交尾行為的混沌人工螢火蟲優化算法[J].計算機科學,2012,39(3):231-234.

[7] 莫愿斌,劉付永,張宇楠.帶高斯變異的人工螢火蟲優化算法[J].計算機應用研究,2013,30(1):121-123.

[8] 杜曉昕,張劍飛,孫明.基于自適應t分布混合變異的人工螢火蟲算法[J].計算機應用,2013,33(7):1922-1925.

[9] 馮艷紅,劉建芹,賀毅朝.基于混沌理論的動態種群螢火蟲算法[J].計算機應用,2013,33(3):796-799.

[10] 郁書好,蘇守寶.混沌螢火蟲優化算法的研究及應用[J].計算機科學與探索,2014(3):1-6.

[11] 宋建立,譚陽紅,熊智挺.非對稱邊界變異的分層并行量子粒子群算法[J].計算機應用研究,2013,30(6):1630-1632.

中圖分類號TP183

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.063

收稿日期：2014-07-28。張小瓊，碩士生，主研領域：智能算法與智能CAD技術。秦亮曦，教授。