張小瓊 秦亮曦
(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院 廣西 南寧 530004)
?
基于混合變異的螢火蟲群優(yōu)化算法
張小瓊秦亮曦
(廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院廣西 南寧 530004)
摘要基本螢火蟲群優(yōu)化GSO(Glowworm Swarm Optimization)算法在求解函數(shù)全局尋優(yōu)問題時(shí),存在后期收斂速度慢、容易陷入局部極值等問題。為此,提出一種基于混合變異的螢火蟲群優(yōu)化算法。該算法用混沌變異和邊界變異來增加種群的多樣性,避免算法陷入局部最優(yōu),且能使算法獲得精度更高的解。運(yùn)用六個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試,結(jié)果表明,改進(jìn)后的螢火蟲群優(yōu)化算法比基本GSO算法具有更高的尋優(yōu)速度、尋優(yōu)精度和收斂率。
關(guān)鍵詞螢火蟲群優(yōu)化算法混沌變異邊界變異混合變異函數(shù)優(yōu)化
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引言
螢火蟲群優(yōu)化GSO算法是印度學(xué)者K N Krishnanand和Debasish Ghose于2005年模擬自然界螢火蟲求偶或覓食行為而提出的一種新型仿生群體智能優(yōu)化算法[1]。該算法通過螢火蟲個(gè)體之間的相互吸引達(dá)到尋優(yōu)的目的,其計(jì)算速度快,需要調(diào)節(jié)的參數(shù)少,簡(jiǎn)單易于實(shí)現(xiàn),具有很強(qiáng)的通用性,已逐漸成為計(jì)算智能研究領(lǐng)域一個(gè)新的研究方向,并成功應(yīng)用于傳感器的噪聲測(cè)試[2]、聚類分析[3]、模擬機(jī)器人[4]、函數(shù)優(yōu)化[5]等。但與其他群智能算法一樣,也存在著后期收斂速度慢、容易陷入局部極值、求解精度不高等問題。
針對(duì)這些問題,文獻(xiàn)[5]提出一種基于熒光因子的自適應(yīng)調(diào)整步長(zhǎng)的方法,使得螢火蟲算法尋優(yōu)的解獲得了更高的精度。文獻(xiàn)[6]提出了一種帶交尾行為的混沌螢火蟲優(yōu)化算法,通過混沌進(jìn)行初始化,提高了初始解的質(zhì)量,又在GSO算法中引入交配行為,進(jìn)一步提高了螢火蟲群優(yōu)化算法的收斂速度和求解精度。文獻(xiàn)[7,8]分別運(yùn)用高斯變異和自適應(yīng)t分布變異的方法增加螢火蟲種群的多樣性,提高了解的精度和尋優(yōu)的速度。本文采用混沌變異和邊界變異的混合變異策略,對(duì)陷入局部極值的螢火蟲利用混沌變異的方法搜索周圍的最優(yōu)解來代替本身;對(duì)飛出邊界的螢火蟲進(jìn)行邊界變異,避免邊界螢火蟲聚集的行為,提高種群的效率。
1基本螢火蟲群優(yōu)化算法
基本螢火蟲群優(yōu)化算法思想來源于自然界的螢火蟲用閃光來吸引其他螢火蟲,借此進(jìn)行溝通、求偶等。閃光越亮代表螢火蟲吸引力越大,最后形成螢火蟲聚集在亮度較大的螢火蟲周圍。螢火蟲閃光的亮度取決于螢火蟲攜帶的的熒光素值,熒光素值越大,螢火蟲的閃光越亮。
算法初始時(shí)在D維解空間內(nèi)隨機(jī)生成N只螢火蟲,螢火蟲i的當(dāng)前位置表示為Xi(t),初始時(shí)每只螢火蟲都攜帶相同的螢火素值l0,并且具有相同的決策半徑r0。在螢火蟲移動(dòng)的過程中,如果螢火蟲j在螢火蟲i的決策范圍內(nèi),并且螢火蟲j熒光素值比螢火蟲i的高,螢火蟲i就以一定的概率向其鄰居螢火蟲j移動(dòng)。螢火蟲所在位置對(duì)應(yīng)一個(gè)適應(yīng)度值,熒光素的大小與螢火蟲所在位置的適應(yīng)度值有關(guān),熒光素值越大,所在位置越好,即有較好的適應(yīng)度值。最后,螢火蟲會(huì)聚集在適應(yīng)度值較高的螢火蟲周圍。在完成初始化后,GSO每次迭代包括三個(gè)過程:熒光素更新、位置更新、感知范圍更新。
1) 熒光素更新階段
熒光素與螢火蟲所在位置密切相關(guān),所在位置越好,熒光素值就越大,閃光越亮;熒光素除了受所在位置影響,還與螢火蟲上一時(shí)刻所攜帶的熒光素值和揮發(fā)速度有關(guān)。熒光素值根據(jù)下式進(jìn)行更新:
li(t)=(1-ρ)li(t-1)+γf(Xi(t))
(1)
式中,li(t)表示在t時(shí)刻螢火蟲i的熒光素值,ρ(0<ρ<1)為常數(shù),表示熒光素的揮發(fā)速度,γ也為常數(shù),表示熒光素更新率,f(Xi(t))表示在t時(shí)刻螢火蟲i所在位置的適應(yīng)度值。
2) 位置更新階段
螢火蟲i的移動(dòng)方向由其所有鄰居螢火蟲的熒光素決定,鄰居螢火蟲是在螢火蟲i的決策范圍內(nèi)熒光素值比螢火蟲i的熒光素值大的螢火蟲集合,即:
Ni(t)={j:‖Xj(t)-Xi(t)‖ (2) 式中,‖·‖表示歐氏距離,ri(t)表示t時(shí)刻螢火蟲i的決策半徑。對(duì)所有鄰居螢火蟲j,根據(jù)下式計(jì)算t時(shí)刻螢火i向螢火蟲j移動(dòng)的概率: (3) 螢火蟲i根據(jù)Pij(t)選擇移動(dòng)方向?yàn)閖,然后根據(jù)下式更新螢火蟲i的位置: (4) 其中,s為移動(dòng)步長(zhǎng)。 3) 感知范圍更新 移動(dòng)后,每只螢火蟲根據(jù)鄰居螢火蟲的數(shù)量動(dòng)態(tài)地更新各自的感知范圍,如果鄰居螢火蟲數(shù)量多,則減小感知范圍,反之增大感知范圍,如下式更新: ri(t+1)=min{rs,max[0,ri(t)+β(nt-|Ni(t)|)]} (5) 其中,rs是控制螢火蟲感知范圍閥值,β是領(lǐng)域變化率,ri(t)(0 2混合變異優(yōu)化GSO算法 2.1種群混沌變異機(jī)制 文獻(xiàn)[8]提出的ATM-AGSO算法進(jìn)行變異時(shí),非最優(yōu)螢火蟲采用自適應(yīng)t分布變異,最優(yōu)螢火蟲采用高斯變異,即: Xi(t)=Xi(t)×[1+k×H(t)]k=1-(t-1)/(Tmax-1)t=1,2,…,Tmax (6) 其中,k為變異控制因子,當(dāng)i為非最優(yōu)螢火蟲時(shí),H(t)為以迭代次數(shù)t為參數(shù)自由度的t分布,當(dāng)i是最優(yōu)螢火蟲時(shí),H(t)為服從均值為0方差為1的高斯分布。但這種變異方法變異的幅度相對(duì)較大,容易錯(cuò)過附近更優(yōu)解。為提高算法局部搜索的遍歷性和效率,本文采用混沌立方映射[9]產(chǎn)生混沌變量來代替ATM-AGSO算法中的隨機(jī)變量H(t),進(jìn)行混沌變異。該策略表示為: Xi n(t) = Xi(t)×[1 + k×Z(n)]n = 1,2,…,Mk = 1-(t-1)/Tmaxt = 1,2,…,Tmax (7) 式中,t表示當(dāng)前迭代次數(shù),Tmax表示算法最大迭代次數(shù),Z(n)為混沌序列。 混沌是自然界廣泛存在的非線性現(xiàn)象,是一種狀似隨機(jī)混亂,卻具有遍歷性和規(guī)律性的非隨機(jī)運(yùn)動(dòng),能按自身規(guī)律在一定范圍內(nèi)不重復(fù)地遍歷所有狀態(tài)[10]。運(yùn)用混沌運(yùn)動(dòng)的這些特性對(duì)GSO算法進(jìn)行優(yōu)化搜索,有助于算法跳出局部最優(yōu),增加種群的多樣性,增強(qiáng)算法的全局搜索能力?;煦缌⒎接成洚a(chǎn)生的是(-1,1)之間的序列,只要立方映射的迭代初值不為0,混沌就會(huì)發(fā)生。首先在D維解空間內(nèi)根據(jù)式(8)隨機(jī)產(chǎn)生一個(gè)(-1,1)之間的D維向量,作為第一個(gè)混沌變量: Z(1)=1-2rand(1,D) (8) 然后根據(jù)下式對(duì)每一維迭代M-1次,最后得到M個(gè)混沌序列。 Z(n+1)=4Z(n)3-3Z(n)-1≤Z(n)≤1n=1,2,…,M-1 (9) 利用產(chǎn)生的混沌序列根據(jù)式(7)進(jìn)行變異,比較變異擾動(dòng)前、后的的適應(yīng)度值。若變異產(chǎn)生的最優(yōu)適應(yīng)度值優(yōu)于原有個(gè)體的適應(yīng)度值,就用該最優(yōu)適應(yīng)度值所處的狀態(tài)取代原有個(gè)體狀態(tài)。這樣根據(jù)已有個(gè)體狀態(tài)增加混沌擾動(dòng)項(xiàng)Xi×k×Z(n),獲得有更好適應(yīng)度值的個(gè)體,種群的多樣性得到了保證,也賦予了算法跳出局部極值的能力,同時(shí)提高了搜索能力。 2.2邊界變異 在其他一些GSO算法中,當(dāng)螢火蟲飛出搜索區(qū)域后,通常將搜索空間的邊界值賦值給該螢火蟲: ifXi(t)>XmaxXi(t)=Xmax 或者 ifXi(t) 其中,Xmax、Xmin分別是搜索區(qū)域的最大和最小邊界值。經(jīng)過這樣的處理后,所有越界的螢火蟲會(huì)在邊界聚集,其狀態(tài)將趨于相同,不僅降低了種群的多樣性,也會(huì)影響算法的全局搜索能力;如果邊界附近存在局部最優(yōu),還使得算法容易陷入局部極值。 文獻(xiàn)[11]把邊界變異引入到量子粒子群算法中,有效控制了粒子越界的行為,提高了算法的全局搜索能力。同理,我們也可以把邊界變異引入到螢火蟲群算法中,在每代螢火蟲越界時(shí)進(jìn)行邊界變異,該變異策略可表示為: ifXi(t)>XmaxXi(t)=Xmax×(1-c×rand()) 或者 ifXi(t) 其中,c=0.01。從上述變異過程可以看出,對(duì)越界螢火蟲進(jìn)行變異操作后,螢火蟲不再聚集在邊界處,而是分布在搜索區(qū)域內(nèi),克服了螢火蟲聚集邊界的缺點(diǎn),同時(shí)增加了種群的多樣性,避免了螢火蟲陷入局部極值,提高了算法的整體搜索速度。 2.3HM-GSO混合變異描述 HM-GSO算法是將混沌變異和邊界變異相結(jié)合,在算法迭代過程中,隨著種群的不斷進(jìn)化,個(gè)體之間的差異逐漸變小,并出現(xiàn)螢火蟲嚴(yán)重聚集的現(xiàn)象,導(dǎo)致算法極容易陷入局部極值。此時(shí)對(duì)種群中的每只螢火蟲進(jìn)行混沌變異搜索,對(duì)搜索過程中越界的螢火蟲進(jìn)行邊界變異,最后用混沌擾動(dòng)后的最優(yōu)狀態(tài)更新為當(dāng)前螢火蟲的狀態(tài)。每次螢火蟲群變異后用最優(yōu)螢火蟲的狀態(tài)和適應(yīng)度值和公告板上的最優(yōu)螢火蟲比較,公告板將記錄更優(yōu)的螢火蟲的狀態(tài)和適應(yīng)度值。當(dāng)公告板上的適應(yīng)度值在連續(xù)三次迭代中沒有改變或者改變很小(|變化量| 2.4HM-GSO算法步驟 HM-GSO算法的具體步驟設(shè)計(jì)如下: 1) 初始化ρ、γ、β、s、l0、r0、rs、nt、N、D、Tmax、u等參數(shù),并隨機(jī)初始化螢火蟲種群; 2) 計(jì)算所有螢火蟲的適應(yīng)度值,初始化公告板; 3) 根據(jù)式(1)對(duì)所有螢火蟲進(jìn)行熒光素更新; 4) 用式(2)計(jì)算所有螢火蟲的鄰居集合,式(3)計(jì)算螢火蟲的選擇概率,然后用輪盤賭方法選擇移動(dòng)目標(biāo),根據(jù)式(4)進(jìn)行位置更新; 5) 用式(5)更新螢火蟲的感知半徑; 6) 計(jì)算當(dāng)前種群每個(gè)個(gè)體的適應(yīng)度值,若最優(yōu)適應(yīng)度值優(yōu)于公告板,則更新公告板的狀態(tài)和適應(yīng)度值; 7) 判斷是否陷入局部最優(yōu)值,如果公告板上的最優(yōu)適應(yīng)度值在連續(xù)三次迭代中沒有發(fā)生改變或者改變很小(|變化量| 圖1 HM-GSO算法流程圖 8) 在每個(gè)螢火蟲周圍進(jìn)行混沌變異,對(duì)飛出邊界的螢火蟲用邊界變異策略控制在搜索范圍內(nèi),計(jì)算混沌擾動(dòng)后的適應(yīng)度值,取最優(yōu)適應(yīng)度值與原適應(yīng)度值比較,若優(yōu)于原有適應(yīng)度值,則用擾動(dòng)后最優(yōu)適應(yīng)度值所在的位置取代原有位置。比較變異后螢火蟲群的最優(yōu)螢火蟲和公告板的最優(yōu)螢火蟲,如果由優(yōu)于公告板,則更新公告板的狀態(tài)和適應(yīng)度值; 9) 完成一次迭代,判斷終止條件是否滿足(迭代次數(shù)達(dá)到Tmax),如果滿足,記錄結(jié)果,退出迭代,否則轉(zhuǎn)步驟3),進(jìn)入下一次迭代。 HM-GSO算法的流程如圖1所示。 3HM-GSO算法性能測(cè)試與分析 3.1實(shí)驗(yàn)測(cè)試函數(shù) 為了驗(yàn)證HM-GSO算法的收斂速度、收斂率和求解精度等,將本文提出的基于混合變異的螢火蟲群(HM-GSO)算法與基本GSO算法及文獻(xiàn)[8]提出的基于自適應(yīng)t分布混合變異的人工螢火蟲(ATM-AGSO)算法進(jìn)行性能比較,采用了6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行對(duì)比測(cè)試實(shí)驗(yàn)。6個(gè)測(cè)試函數(shù)如下: 標(biāo)準(zhǔn)測(cè)試函數(shù)如表1所列。 表1 標(biāo)準(zhǔn)測(cè)試函數(shù) 3.2實(shí)驗(yàn)參數(shù)設(shè)置 在GSO算法中,步長(zhǎng)s根據(jù)經(jīng)驗(yàn)選取,F(xiàn)1、F3中取為5,F(xiàn)2、F4、F5和F6中取為1,對(duì)于ATM-AGSO算法和HM-GSO算法,s取值為0.3,其他實(shí)驗(yàn)參數(shù)設(shè)置如表2所示。 表2 實(shí)驗(yàn)參數(shù)設(shè)置 3.3實(shí)驗(yàn)平臺(tái) 本實(shí)驗(yàn)的運(yùn)行測(cè)試環(huán)境為:處理器為Intel(R) Core(TM) i3-3110M CPU,主頻2.4 GHz,內(nèi)存4 GB,操作系統(tǒng):Windows 7,集成開發(fā)環(huán)境為Matlab R2012a。 3.4實(shí)驗(yàn)仿真結(jié)果與分析 仿真實(shí)驗(yàn)中對(duì)這三種算法用這6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)分別進(jìn)行20次獨(dú)立實(shí)驗(yàn),對(duì)每一個(gè)函數(shù)求得這三種算法的最優(yōu)值、最差值、均值、收斂迭代次數(shù)、平均收斂時(shí)間和收斂率等,并通過收斂曲線來比較三種算法的收斂速度和求解精度,從而測(cè)試本文算法的有效性。在給出收斂精度ε=10-5的情況下,如果滿足|Fitnessbest-Fitness|<ε,則認(rèn)為算法收斂;否則為不收斂。其中,F(xiàn)itnessbest為實(shí)際求得的最優(yōu)解,F(xiàn)itness為理論上的最優(yōu)解。 從表3、表4可以看出,GSO對(duì)6個(gè)函數(shù)都沒有收斂,HM-GSO和ATM-AGSO測(cè)試6個(gè)函數(shù)時(shí)的收斂率達(dá)到100%,收斂精度以HM-GSO最大,ATM-AGSO次之,GSO最小。對(duì)于函數(shù)F1,HM-GSO的平均最優(yōu)解精度比GSO提高了42個(gè)數(shù)量級(jí),平均收斂迭代次數(shù)比ATM-AGSO減少了65次。對(duì)于函數(shù)F2,HM-GSO的平均最優(yōu)解精度比GSO提高了30個(gè)數(shù)量級(jí),比ATM-AGSO提高了20個(gè)數(shù)量級(jí),平均收斂迭代次數(shù)比ATM-AGSO減少了85次。對(duì)于函數(shù)多個(gè)F3,HM-GSO的最優(yōu)解精度達(dá)到了e-75,平均最優(yōu)解精度遠(yuǎn)優(yōu)于GSO,比ATM-AGSO提高了40個(gè)數(shù)量級(jí),平均收斂迭代次數(shù)比ATM-AGSO減少了47次。對(duì)于函數(shù)F4,HM-GSO的平均最優(yōu)解精度比GSO提高了63個(gè)數(shù)量級(jí),比ATM-AGSO提高了45個(gè)數(shù)量級(jí),平均收斂迭代次數(shù)比ATM-AGSO減少了61次。對(duì)于函數(shù)F5,HM-GSO的平均最優(yōu)解精度比GSO提高了52個(gè)數(shù)量級(jí),比ATM-AGSO提高了33個(gè)數(shù)量級(jí),平均收斂迭代次數(shù)比ATM-AGSO減少了44次。對(duì)于函數(shù)F6,HM-GSO的最優(yōu)解精度達(dá)到了e-102,平均最優(yōu)解精度比ATM-AGSO提高了26個(gè)數(shù)量級(jí),平均收斂迭代次數(shù)比ATM-AGSO減少了12次。 表3 三種算法收斂情況對(duì)比 表4 三種算法最優(yōu)解對(duì)比 結(jié)合圖2-圖7分析,HM-GSO的尋優(yōu)曲線更加穩(wěn)定。隨著迭代次數(shù)的增加,在增加不到50時(shí),HM-GSO的最優(yōu)函數(shù)值就到達(dá)了收斂精度。HM-GSO的平均收斂時(shí)間也比ATM-AGSO更少,且在同一次迭代里面。HM-GSO獲得的最優(yōu)函數(shù)值比GSO和ATM-AGSO更優(yōu),說明HM-GSO比GSO和ATM-AGSO具有更快的收斂速度,更高的求解精度。可見,HM-GSO算法在搜索過程中通過混沌變異和邊界變異混合變異的方法增加了種群的多樣性,避免了算法陷入局部最優(yōu)、容易聚集邊界的缺點(diǎn),克服了過早收斂的問題。因而全局尋優(yōu)能力、求解精度、收斂速度和穩(wěn)定性等方面比其他兩種算法都得到了提高,具有更好的尋優(yōu)能力。 圖2 F1函數(shù)尋優(yōu)收斂曲線 圖3 F2函數(shù)尋優(yōu)收斂曲線 圖4 F3函數(shù)尋優(yōu)收斂曲線 圖5 F4函數(shù)尋優(yōu)收斂曲線 圖6 F5函數(shù)尋優(yōu)收斂曲線 圖7 F6函數(shù)尋優(yōu)收斂曲線 4結(jié)語 本文提出了一種基于混合變異的螢火蟲群優(yōu)化算法。算法中運(yùn)用混沌的方法進(jìn)行變異,并對(duì)越界的螢火蟲進(jìn)行邊界變異,使算法避免陷入局部極值,提高了尋優(yōu)速度和求解精度。通過函數(shù)優(yōu)化實(shí)驗(yàn)可以看出,改進(jìn)后的算法優(yōu)于基本螢火蟲群優(yōu)化算法,較ATM-AGSO算法有更快的收斂速度和更精確的函數(shù)值。下一步我們將融合其他算法,并應(yīng)用于求解實(shí)際問題中。 參考文獻(xiàn) [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] 歐陽喆,周永權(quán).自適應(yīng)步長(zhǎng)螢火蟲優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,2011,31(7):1804-1807. [6] 黃凱,周永權(quán).帶交尾行為的混沌人工螢火蟲優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2012,39(3):231-234. [7] 莫愿斌,劉付永,張宇楠.帶高斯變異的人工螢火蟲優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(1):121-123. [8] 杜曉昕,張劍飛,孫明.基于自適應(yīng)t分布混合變異的人工螢火蟲算法[J].計(jì)算機(jī)應(yīng)用,2013,33(7):1922-1925. [9] 馮艷紅,劉建芹,賀毅朝.基于混沌理論的動(dòng)態(tài)種群螢火蟲算法[J].計(jì)算機(jī)應(yīng)用,2013,33(3):796-799. [10] 郁書好,蘇守寶.混沌螢火蟲優(yōu)化算法的研究及應(yīng)用[J].計(jì)算機(jī)科學(xué)與探索,2014(3):1-6. [11] 宋建立,譚陽紅,熊智挺.非對(duì)稱邊界變異的分層并行量子粒子群算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(6):1630-1632. 中圖分類號(hào)TP183 文獻(xiàn)標(biāo)識(shí)碼A DOI:10.3969/j.issn.1000-386x.2016.02.063 收稿日期:2014-07-28。張小瓊,碩士生,主研領(lǐng)域:智能算法與智能CAD技術(shù)。秦亮曦,教授。