改進(jìn)螢火蟲算法及其收斂性分析

張大力, 夏紅偉, 張朝興, 馬廣程, 王常虹,*

(1. 哈爾濱工業(yè)大學(xué)航天學(xué)院, 黑龍江 哈爾濱 150001; 2. 上海航天控制技術(shù)研究所, 上海 201109)

0 引 言

社會性生物的某些集體行為往往呈現(xiàn)出尋優(yōu)的本質(zhì),通過對這類行為的公式化,得到了一類被稱為群智能算法的優(yōu)化算法,蟻群優(yōu)化(ant colony optimization, ACO)算法、粒子群優(yōu)化(particle swarm optimization, PSO)算法、人工蜂群(artificial bee colony, ABC)算法等均屬此列。由于算法簡單靈活、魯棒性好,可用于求解許多傳統(tǒng)方法無法解決的NP-hard問題,如旅行商問題、裝箱問題等,已經(jīng)廣泛應(yīng)用于人工智能、通信網(wǎng)絡(luò)和工業(yè)生產(chǎn)等領(lǐng)域。

螢火蟲算法(firefly algorithm, FA)是英國學(xué)者Yang于2008年提出的一種元啟發(fā)式算法。該算法通過模擬自然界中螢火蟲個體之間相互吸引的理想化行為達(dá)到尋優(yōu)目的,一經(jīng)提出便受到國內(nèi)外研究人員的關(guān)注,廣泛應(yīng)用于計算機(jī)科學(xué)、復(fù)雜方程求解、結(jié)構(gòu)和工程優(yōu)化領(lǐng)域。但許多構(gòu)造的和現(xiàn)實(shí)的優(yōu)化問題具有大量的局部最優(yōu)解,容易使算法因種群多樣性的快速衰減而陷入早熟停滯,大幅降低優(yōu)化效果。同時,大量局部最優(yōu)對種群的吸引可能導(dǎo)致算法不斷震蕩而無法收斂。有學(xué)者通過引入自適應(yīng)或隨機(jī)機(jī)制針對上述問題進(jìn)行改進(jìn)。Gandomi等采用12種不同的混沌映射對參數(shù)進(jìn)行自適應(yīng)調(diào)節(jié),其中高斯映射調(diào)節(jié)吸引度參數(shù)的改進(jìn)算法取得了一定效果,但性能提升有限,尋優(yōu)成功率不高。Yu等設(shè)計了一種自適應(yīng)步長策略來提高算法的全局探索能力,每個個體的隨機(jī)步長根據(jù)當(dāng)前和歷史信息分別計算,然而實(shí)際尋優(yōu)效果與標(biāo)準(zhǔn)算法區(qū)別很小。Altay等將該改進(jìn)算法用于調(diào)節(jié)數(shù)字水印技術(shù)中的比例因子,由于缺乏與標(biāo)準(zhǔn)算法的橫向?qū)Ρ?不足以說明改進(jìn)算法的優(yōu)越性。Verma等在算法初始化階段引入反向?qū)W習(xí)策略提高算法收斂速度,在迭代過程中采用基于維度的位置更新方法跳出局部最優(yōu),但與其他優(yōu)化算法相比沒有體現(xiàn)出明顯的競爭力。Manju等參考量子PSO提出了量子FA,并利用基于二次插值的重組算子改進(jìn)搜索過程,提高了算法的收斂速度和尋優(yōu)能力,但無法處理復(fù)雜病態(tài)優(yōu)化問題。柳長源等引入了一種驅(qū)散機(jī)制,若種群最優(yōu)值在連續(xù)多次迭代后未發(fā)生變化,則對最優(yōu)個體采用柯西分布進(jìn)行變異,聚集在最優(yōu)個體附近的個體采用均勻分布進(jìn)行驅(qū)散,從函數(shù)優(yōu)化結(jié)果來看改進(jìn)效果并不顯著。劉景森等提出了一種具有振蕩、約束和自然選擇機(jī)制的改進(jìn)策略,提高了算法對高維問題的求解能力,但是增加了額外的調(diào)節(jié)參數(shù),不利于推廣應(yīng)用,其收斂性證明仿照PSO算法證明的思路,簡化到二維空間進(jìn)行分析,無法向高維情況推廣。部分學(xué)者選擇從個體信息交互的角度對算法進(jìn)行改進(jìn)。Wang等提出了一種隨機(jī)吸引模型,通過將個體與其鄰域內(nèi)有限個其他個體進(jìn)行通信,降低了算法計算復(fù)雜度,但尋優(yōu)性能沒有明顯提升。在此基礎(chǔ)上,Dhal等進(jìn)一步考慮粗糙集和局部搜索機(jī)制,提出了一種隨機(jī)吸引粗糙FA,并成功應(yīng)用于圖像分割過程,但與標(biāo)準(zhǔn)算法及其他傳統(tǒng)優(yōu)化算法相比沒有明顯的競爭力。Shan等通過分布式并行技術(shù)將種群劃分為多個子群,子群之間基于4種不同的通信策略進(jìn)行信息交換,但每個子群的尋優(yōu)能力偏弱,不能保證整體的尋優(yōu)效果,且增加了額外的配置參數(shù),適用性不強(qiáng)。Elakkiya等提出了一種基于社區(qū)啟發(fā)的改進(jìn)策略,個體只被由個較優(yōu)個體組成的所謂社區(qū)中的個體吸引,并給出了社區(qū)規(guī)模的自適應(yīng)更新機(jī)制,降低了計算復(fù)雜度,但無法保證尋優(yōu)精度。還有一種改進(jìn)策略是在FA中引入其他算法的思想。Zhao等借鑒ABC算法的思想將螢火蟲種群分為領(lǐng)導(dǎo)者、開發(fā)者和跟隨者3種角色,并為每個角色分配了一種學(xué)習(xí)策略,用來平衡算法的探索和挖掘能力,但沒有取得顯著的性能改進(jìn)。Xing等為了使算法跳出局部最優(yōu),引入了遺傳算法中的變異算子,同時仿照PSO算法將全局最優(yōu)納入到位置更新公式中,改進(jìn)算法用于解決協(xié)同干擾資源分配問題,尋優(yōu)結(jié)果與標(biāo)準(zhǔn)算法相比有少許提升。薛晗等結(jié)合文化算法和FA的優(yōu)點(diǎn),將迭代過程中獲取的經(jīng)驗(yàn)和知識組成信仰空間,并設(shè)計了一套規(guī)則來影響種群更新,但算法沒有足夠的跳出局部最優(yōu)的能力。Gupta等將引力搜索和FA通過串行運(yùn)行的方式結(jié)合起來,提出了一種混合引力搜索FA,計算復(fù)雜度較高,尋優(yōu)能力沒有明顯提升。此外,Cheng等和Xue等采用混合編碼的形式對個體進(jìn)行編碼,利用組合變異、協(xié)同進(jìn)化等方式加快算法收斂速度,但該方法只適用于解決離散工程優(yōu)化問題,缺乏適用性。

基于以上分析可以看出,目前FA仍然具有較大的改進(jìn)潛力,并且理論分析比較薄弱,也在一定程度上制約了FA的進(jìn)一步改進(jìn)和發(fā)展。因此,本文提出一種改進(jìn)FA(improved FA, IFA),以提升算法性能。首先,介紹FA的基本原理。其次,給出新的個體位置更新機(jī)制。圍繞種群更新過程,引入位置置換變異策略和差分進(jìn)化(differential evolution,DE)算法中的最優(yōu)變異策略(DE/best/1),并給出算法流程。然后,給出改進(jìn)算法收斂性的理論證明。最后,采用一組典型基準(zhǔn)函數(shù)和裝箱問題對改進(jìn)算法有效性進(jìn)行驗(yàn)證。

1 FA基本原理

FA受螢火蟲群體的集聚性啟發(fā),其仿生原理如下:搜索空間中的單個元素代表螢火蟲個體;擬優(yōu)化的目標(biāo)抽象為個體所在位置的亮度,衡量個體位置的優(yōu)劣并決定其移動方向;元素搜索和更新的尋優(yōu)過程模擬個體間的吸引和移動行為。

算法數(shù)學(xué)描述如下:

(1) 個體的位置記為=(1,2,…,),其亮度即為該位置對應(yīng)的目標(biāo)函數(shù)值()。

(2) 個體與間的吸引度更新公式定義為

(1)

式中:為初始吸引度,一般取值為1;為光強(qiáng)吸收系數(shù),一般取值為1;為個體間的笛卡爾距離,有

(2)

(3) 個體被吸引并向其移動的位置更新公式為

(3)

式中:為算法迭代次數(shù);為步長因子;為隨機(jī)數(shù),服從均勻分布或高斯分布。

2 IFA

威廉·奧卡姆曾言,“如無必要,勿增實(shí)體”,這就是著名的“奧卡姆剃刀定律”。從優(yōu)化算法設(shè)計的角度來詮釋,可理解為在效果相同或相近的前提下,盡量選擇簡單框架和規(guī)則。在這種思想的指導(dǎo)下,本文提出以下改進(jìn)策略。

2.1 隨機(jī)擾動策略

圖1 吸引力項(xiàng)運(yùn)動特征Fig.1 Motion characteristic of attraction term

由于式(3)第3項(xiàng)隨機(jī)項(xiàng)的變化是獨(dú)立的,沒有利用個體和種群信息,因此其變化很難與個體的進(jìn)化相匹配。一方面,如果取值過小,那么較小的搜索半徑無法提供跳出局部最優(yōu)的能力,如果取值較大,則會因?yàn)檩^大的搜索半徑導(dǎo)致較慢的收斂速度和較低的收斂精度。另一方面,一旦在隨機(jī)項(xiàng)中引入個體信息,那么可與改進(jìn)后的第2項(xiàng)合并同類項(xiàng),在功能上被其覆蓋。

基于以上考慮,向原位置更新式(3)中引入一個隨機(jī)擾動因子,使得吸引力項(xiàng)擁有一個隨機(jī)權(quán)重,并去掉式(3)第3項(xiàng),有

(4)

為保證式(4)在初始階段的搜索能力,將吸引度更新為

(5)

式中:為吸引度調(diào)節(jié)尺度,根據(jù)調(diào)試經(jīng)驗(yàn)建議取值范圍為07～09。

隨機(jī)擾動因子的引入提高了個體的搜索范圍。一方面,在算法初始階段,個體間距離較大,式(5)表示的隨機(jī)權(quán)重簡化為·,此時搜索步長較長,算法能夠在全局范圍內(nèi)進(jìn)行尋優(yōu),一定程度上提高了算法的全局探索能力;另一方面,在算法迭代后期,個體間距離大幅減小,隨機(jī)權(quán)重簡化為(+)·,而此時搜索步長較小,算法能夠在當(dāng)前位置的鄰域深度挖掘。個體搜索范圍的提升使得種群在運(yùn)動過程中能夠覆蓋到更多搜索空間中的區(qū)域,如圖2所示。

圖2 種群運(yùn)動趨勢和個體分布情況Fig.2 Population movement trend and individual distribution

下面對隨機(jī)擾動因子的選擇進(jìn)行分析。典型的隨機(jī)分布有均勻分布、正態(tài)分布、柯西分布、列維分布等。為了更直觀地區(qū)分不同分布的特征,給出上述分布100 000個樣本的分布直方圖,如圖3所示。

圖3 4種不同概率分布的100 000樣本分布Fig.3 Four different probability distributions of 100 000 random samples

由圖3可以看出,均勻分布產(chǎn)生的樣本分布均勻且取值區(qū)間較小,選擇均勻分布作為隨機(jī)擾動因子可獲得在各個方向上更加穩(wěn)定的搜索能力。正態(tài)分布產(chǎn)生的樣本呈現(xiàn)出左右對稱、中間高兩側(cè)低的鐘型分布特征,在原點(diǎn)附近取值的概率較高,離原點(diǎn)越遠(yuǎn)取值概率越低,選擇正態(tài)分布作為隨機(jī)擾動因子,存在初始階段收斂慢的情況,不能保證算法收斂速度。柯西分布和列維分布產(chǎn)生的樣本呈現(xiàn)出明顯的厚尾特征,在原點(diǎn)附近取值的概率較高,偶爾會出現(xiàn)非常大的樣本,選擇柯西或列維分布作為隨機(jī)擾動因子,算法搜索能力不穩(wěn)定,且產(chǎn)生的大樣本很有可能使個體更新超出搜索空間,精度和收斂速度均無法保證。基于以上分析,隨機(jī)擾動因子首選均勻分布,在第4.1節(jié)中給出仿真，對以上分析做進(jìn)一步說明。

2.2 雙重變異策略

為進(jìn)一步提升算法尋優(yōu)性能,本文圍繞個體和種群的更新過程增加兩個變異機(jī)制。

221 位置置換變異策略

圖4 位置置換變異原理和種群更新流程Fig.4 Principle of position substitution mutation and population renewal process

參數(shù)的取值是位置置換變異策略的關(guān)鍵。一方面,由于該操作在個體位置更新后進(jìn)行,且嵌套于種群更新過程中,因此不能過大,否則會提高算法計算復(fù)雜度,降低收斂速度。另一方面,若次數(shù)太少,個體位置變化較小,無法達(dá)到跳出局部最優(yōu)的目的,降低尋優(yōu)精度。因此,置換變異至少2次,至多建議不超過5次,本文取=3。

222 DE/best/1變異策略

(6)

圖5 DE/best/1/變異種群更新流程
Fig.5 DE/best/1 cross mutation population renewal process

DE/best/1變異操作的執(zhí)行次數(shù)為。由于該部分沒有循環(huán)嵌套,可以取大一些的數(shù),從而充分利用歷史最優(yōu)信息指導(dǎo)搜索過程,提高算法收斂精度。參考差分進(jìn)化算法的取值,可取種群規(guī)模。

兩種變異策略得到的子代種群采取與父代種群競爭的模式選取進(jìn)入下一輪循環(huán)的種群,在每輪迭代中保留較優(yōu)個體,提升整體種群質(zhì)量。

2.3 算法平衡性分析

全局探索與局部挖掘能力是群智能優(yōu)化算法解決問題的核心,二者之間的平衡對算法性能至關(guān)重要。研究普遍認(rèn)為,在算法開始階段應(yīng)以全局探索為主,在后期應(yīng)以局部挖掘?yàn)橹?。改進(jìn)算法能夠很好地滿足此規(guī)律。在算法迭代初始階段,個體間相距較遠(yuǎn),從位置更新式(4)和DE/best/1變異策略式(6)可直觀地看出,此時算法有較大的搜索步長,能夠在解空間內(nèi)進(jìn)行全局探索。算法迭代后期,種群不斷聚集,搜索步長隨之減小,此時算法的局部挖掘能力得到不斷強(qiáng)化。第221節(jié)所述的位置置換變異策略是對個體自身信息的突變,該操作不受迭代過程的影響,無論在迭代前期還是迭代后期均能使個體有效地跳出當(dāng)前位置,從而避免算法陷入局部最優(yōu)。需要注意的是,在實(shí)際運(yùn)行中,全局探索和局部挖掘能力是算法各個策略共同觸發(fā)的,沒有明確的界限。

2.4 算法流程

下面給出改進(jìn)算法的流程。

初始化控制參數(shù)，，，位置變異次數(shù)為，DE/best/1變異執(zhí)行次，種群規(guī)模為，搜索空間下界為，上界為，最大迭代次數(shù)為MaxGeneration。

構(gòu)建服從均勻分布的初始種群，計算適應(yīng)度和當(dāng)前全局最優(yōu)解g。

取種群中的一個個體，判斷其與其他個體的吸引關(guān)系，根據(jù)式(2)、式(4)、式(5)更新該個體的位置并進(jìn)行限位，同時更新全局最優(yōu)值g，該步驟執(zhí)行次。

根據(jù)第221節(jié)給出的策略對步驟3中選定的個體進(jìn)行位置置換變異，該步驟執(zhí)行次。

步驟3～步驟4連續(xù)執(zhí)行，重復(fù)次數(shù)為次，得到子種群1。

根據(jù)第222節(jié)給出的策略對種群1進(jìn)行變異操作，同時更新全局最優(yōu)值g。該步驟執(zhí)行次，得到子種群2。

父代種群和子代種群拼接并排序后截斷保留 維數(shù)據(jù)，得到下一輪迭代的父代種群。

本文設(shè)置停止準(zhǔn)則為迭代次數(shù)達(dá)到MaxGeneration，若滿足條件，則終止判斷，輸出優(yōu)化結(jié)果并可視化；若不滿足條件，則重復(fù)步驟3～步驟7。

2.5 算法計算復(fù)雜度分析

結(jié)合算法流程進(jìn)行分析,為了簡便這里記為迭代次數(shù),為適應(yīng)度函數(shù)的計算量,那么算法語句總的執(zhí)行次數(shù)可以表示為·[(5+)·+·(+4)·+(+7)·],此時改進(jìn)算法的時間復(fù)雜度為(··)。顯然,算法的計算復(fù)雜度與問題本身的復(fù)雜度直接相關(guān),主要由適應(yīng)度函數(shù)計算量和算法計算量決定。

3 收斂性證明

3.1 隨機(jī)算法的收斂準(zhǔn)則

Wets給出了一般隨機(jī)優(yōu)化算法收斂性判別準(zhǔn)則,下面重述其主要結(jié)論。

假設(shè)有隨機(jī)優(yōu)化問題[,],其迭代方式為,第次迭代結(jié)果,則+1=(,)。其中,為適應(yīng)度函數(shù),為解空間,是次迭代產(chǎn)生的所有解。

在Lebesgue測度空間定義搜索的下確界:

=inf(∶[∈|()<]>0)

(7)

式中:[]表示集合上的Lebesgue測度。根據(jù)式(7)定義最優(yōu)解區(qū)域?yàn)?/p>

(8)

式中:>0且足夠小,>0且足夠大。若算法找到了,中的一個點(diǎn),則算法收斂。

下面給出算法收斂的充分條件:

全局搜索收斂

(9)

(10)

(11)

證畢

3.2 改進(jìn)算法基本概念的數(shù)學(xué)描述

螢火蟲位置狀態(tài)和位置狀態(tài)空間

螢火蟲位置的狀態(tài)=(,),由螢火蟲的位置和全局最優(yōu)值構(gòu)成,所有可能的個體位置狀態(tài)的集合稱為螢火蟲的位置狀態(tài)空間,記為={=(,)|,∈,()<()}。其中,螢火蟲個體在一次迭代過程中產(chǎn)生的兩組子種群的個體位置記為1和2,其位置狀態(tài)分別記為1=(1,)和2=(2,),為包含兩子種群個體的位置狀態(tài)空間。

群體狀態(tài)和群體狀態(tài)空間

種群位置狀態(tài)集合稱為群體狀態(tài),記為={,,…,},所有群體狀態(tài)構(gòu)成的群體狀態(tài)空間記為={=(,,…,),∈,1≤≤},其中子群位置狀態(tài)記為1=(11,12,…,1)和2=(21,22,…,2),且包含兩子群狀態(tài)空間。

3.3 IFA的馬爾可夫模型建立

對?=(,gb)∈,?1=(1,gb)∈位置狀態(tài)由轉(zhuǎn)移到1記為1()=1。

螢火蟲的位置狀態(tài)由轉(zhuǎn)移到1的轉(zhuǎn)移概率為

(1 ()=1)=(→1′)·(gb→gb′)·(1′→1)·(gb′→gb″)

(12)

式中:(→1′)為式(4)對應(yīng)的轉(zhuǎn)移概率;(gb→gb′)為該步驟全局最優(yōu)位置的轉(zhuǎn)移概率;(1′→1)為步驟4對應(yīng)的轉(zhuǎn)移概率;(gb′→gb″)為該步驟更新全局最優(yōu)的轉(zhuǎn)移概率。

螢火蟲位置狀態(tài)由轉(zhuǎn)移到1,意味著→1′,gb→gb′,1′→1,gb′→gb同時成立。作為子種群,有

(→1′)=1

(13)

全局最優(yōu)位置gb的轉(zhuǎn)移概率為

(14)

位置狀態(tài)由1′→1的概率為

(15)

全局最優(yōu)位置的再次轉(zhuǎn)移概率為

(16)

證畢

對?=(1,2,…,)∈,?1=(11,12,…,1)∈,群體狀態(tài)由轉(zhuǎn)移到1,記作1()=1。

螢火蟲位置群體狀態(tài)由轉(zhuǎn)移到1的轉(zhuǎn)移概率為

(17)

若螢火蟲位置群體狀態(tài)由轉(zhuǎn)移到1,那么表示中所有個體的位置狀態(tài)同時轉(zhuǎn)移到1中所有個體的位置狀態(tài),即1(1)=11,1(2)=12,…,1()=1同時成立。

證畢

在IFA算法迭代中,對?1=(11,12,…,1)∈,?2=(21,22,…,2)∈,記作2(1)=2。

螢火蟲位置群體狀態(tài)由1轉(zhuǎn)移到2的轉(zhuǎn)移概率為

(18)

若螢火蟲位置群體狀態(tài)由1轉(zhuǎn)移到2,那么有1中所有個體位置狀態(tài)同時轉(zhuǎn)移到2中所有個體位置狀態(tài),即2(1)=21,2(1)=22,…,2(1)=2同時成立。在迭代過程中,第二次變異操作個體的狀態(tài)轉(zhuǎn)移與種群狀態(tài)轉(zhuǎn)移有關(guān),根據(jù)式(7)有

(19)

證畢

對?=(1,2,…,)∈,=(1,2,…,)∈,將螢火蟲位置的群體狀態(tài)轉(zhuǎn)移到記作()=。

螢火蟲位置群體狀態(tài)由轉(zhuǎn)移到的轉(zhuǎn)移概率為

(20)

式中:為對父代種群和兩子種群進(jìn)行排序和截斷操作,(gb?→gb)為尋找種群中的最優(yōu)個體的轉(zhuǎn)移概率。

若螢火蟲位置的群體狀態(tài)由一步轉(zhuǎn)移到,就意味著位置的群體狀態(tài)發(fā)生了集體轉(zhuǎn)移,由定理1～定理3可推出最終的轉(zhuǎn)移概率公式。

證畢

螢火蟲的位置群體狀態(tài)序列{();≥0}是離散時空上的有限齊次馬爾可夫鏈。

首先,對于任何一個優(yōu)化算法來講,其搜索空間都是有限的,任意個體狀態(tài)=(,g)中的,g也是有限的,所以位置的狀態(tài)空間是有限空間。又由于=(,,…,)由個個體組成,為大小有限的正整數(shù),故螢火蟲位置的群體狀態(tài)也是有限的。

其次,?(-1)∈,?()∈,其狀態(tài)轉(zhuǎn)移概率(((-1))=())是由群體中所有個體的轉(zhuǎn)移概率和兩子群的轉(zhuǎn)移概率決定。由定理1～定理3,可得

(1((-1))=1(-1))=((-1)→1′(-1))·(g(-1)→g′(-1))·(1′(-1)→1(-1))·(g′(-1)→g(-1))

(21)

(22)

(23)

則

(24)

通過以上分析,(((-1))=())僅與-1時刻的位置狀態(tài)有關(guān),故螢火蟲位置的群體狀態(tài){();≥0}具有馬爾可夫性,且算法迭代與時間無關(guān),所以該過程是齊次的。

證畢

3.4 IFA的收斂性分析

定義最小化問題∶→,?

min() s.t.∈

式中:={,,…,}為維決策變量,所有滿足約束的值構(gòu)成的集合稱為可行域。位置最優(yōu)位置狀態(tài)集為,其群體狀態(tài)集為={=(,,…,)|?∈,1≤≤}。

對閉集,?∈,有∑∈=1,意味著從狀態(tài)空間內(nèi)的任何一點(diǎn)出發(fā),始終無法達(dá)到以外的任意狀態(tài)。

對于個體位置狀態(tài)集{();>0},集合是空間上的一個閉集;對位置群體狀態(tài)集{();≥0},集合是空間上的一個閉集。

同理,假如?∈,??,→成立,那么至少存在一個個體的位置由的內(nèi)部轉(zhuǎn)移至外部,又已證明是上的一個閉集,根據(jù)式(20),有(()=)=0,由閉集定義知,集合是空間上的一個閉集。

證畢

在螢火蟲位置群體狀態(tài)空間中,無法找到外的非空閉集,使其滿足∩=。

假設(shè)在位置群體空間中能夠找到一個閉集,滿足∩=,那么?∈,?∈,有(gb)>(gb)。根據(jù)式(20),其滿足各個組件不為0的條件,那么存在轉(zhuǎn)移概率(()=)≠0,即不是閉集。定理得證。

證畢

假設(shè)〈〉是一組服從rand(0,1)的隨機(jī)變量,且滿足獨(dú)立同分布,那么

隨著螢火蟲位置群體狀態(tài)不斷迭代更新,當(dāng)次數(shù)趨于無窮時,螢火蟲位置群體狀態(tài)序列必然進(jìn)入最優(yōu)集。

由定理6和定理7以及引理1和引理2得證。

在迭代次數(shù)趨于無窮時,IFA能夠以概率1收斂于全局最優(yōu)。

一方面,在每次迭代過程中,IFA都保留了全局最優(yōu),從而保證了適應(yīng)度的非增性,滿足收斂條件一;另一方面,根據(jù)定理9,當(dāng)?shù)螖?shù)趨于無窮時,螢火蟲位置的群體序列必然進(jìn)入最優(yōu)集,即找不到全局最優(yōu)的概率為0,滿足收斂條件二。故IFA以概率1收斂于全局最優(yōu)。

證畢

4 仿真實(shí)驗(yàn)

由于實(shí)際應(yīng)用中算法運(yùn)行時間有限,故需通過固定時間的仿真實(shí)驗(yàn)對算法有效性進(jìn)行驗(yàn)證。算法運(yùn)行環(huán)境為Intel Core i5-3470處理器,CPU3.20 GHz,3.48 GB內(nèi)存,Windows10,64位操作系統(tǒng)。

4.1 隨機(jī)擾動因子性能對比

為驗(yàn)證第2.1節(jié)中的結(jié)論,對4種隨機(jī)擾動因子下的改進(jìn)算法RIFA, GIFA, CIFA, LIFA進(jìn)行仿真試驗(yàn)和性能對比,R(平均)、G(正態(tài))、C(Cauchy)、L(Levy)分別對應(yīng)改進(jìn)算法采用的隨機(jī)分布。選用4個典型基準(zhǔn)函數(shù),如表1所示。

算法參數(shù)設(shè)置情況為=1,=08,=1,=3,=40,取種群規(guī)模,=30,～U(04,09,1,),最大迭代次數(shù)為2 000。初始種群由問題域內(nèi)進(jìn)行隨機(jī)初始化產(chǎn)生。為提高結(jié)果的可信度,保證對比實(shí)驗(yàn)客觀公正,對每一個測試,所有算法均獨(dú)立執(zhí)行50次,取平均最優(yōu)值、時間和成功率(success rate, SR)的統(tǒng)計結(jié)果進(jìn)行比較,最優(yōu)結(jié)果由粗體標(biāo)出,仿真結(jié)果如表2所示。

表1 基準(zhǔn)函數(shù)Table1 Benchmarks functions

表2 4種隨機(jī)擾動因子仿真結(jié)果Table 2 Four random disturbance factors simulation results

表2的統(tǒng)計結(jié)果顯示,隨機(jī)擾動因子選擇均勻分布時,在尋優(yōu)精度、收斂時間和SR上的表現(xiàn)最好,對所有基準(zhǔn)函數(shù)均能找到最優(yōu)解;選擇正態(tài)分布時,算法收斂時間大幅提高,尋優(yōu)精度和SR也出現(xiàn)了下降,特別是函數(shù)～的表現(xiàn)很差;柯西擾動因子的表現(xiàn)與正態(tài)分布類似,收斂時間比前者稍短,但尋優(yōu)精度更加無法保證;列維擾動因子表現(xiàn)最差,運(yùn)行效率最低,優(yōu)化結(jié)果幾乎不可用。因此,改進(jìn)算法的隨機(jī)擾動因子優(yōu)先選擇均勻分布。

4.2 與其他算法的性能對比

選取已在實(shí)踐中檢驗(yàn)過的優(yōu)秀算法PSO、DE以及FA進(jìn)行對比試驗(yàn)。各個算法的參數(shù)設(shè)置情況如下:

(1) PSO:慣性權(quán)重=1,阻尼比=0.99,加速因子=15,=2.0。

(2) DE(DE/rand/1):縮放因子F為范圍在0.2～0.8的均勻隨機(jī)數(shù),變異概率=0.2。

(3) FA:=02,=0.98,=2,=1。

(4) IFA參數(shù)同第4.1節(jié)。

其他仿真條件同第4.1節(jié),仿真結(jié)果見表3。

表3 固定迭代次數(shù)仿真結(jié)果Table 3 Simulation results of fixed iterations

表3的統(tǒng)計結(jié)果顯示,對于函數(shù)～,改進(jìn)算法均能夠找到最優(yōu)解、精度和SR均好于對比方法,在和尤為明顯。但在平均仿真時間上,改進(jìn)算法比其他算法長。這是由于PSO、DE和FA過早陷入局部最優(yōu),根據(jù)優(yōu)化算法本身運(yùn)行機(jī)制,如果沒有足夠的跳出局部最優(yōu)的能力,那么會不斷加速收斂,因此其運(yùn)行時間短于改進(jìn)算法。

函數(shù)是典型的復(fù)雜病態(tài)二次函數(shù),其全局最優(yōu)位于狹窄的、拋物形的山谷中,缺乏有價值的信息,優(yōu)化難度較大,比較考驗(yàn)算法全局探索和局部挖掘能力。各方法對該函數(shù)進(jìn)行優(yōu)化的尋優(yōu)曲線如圖6所示。

圖6 不同算法性能比較Fig.6 Performance comparison of different algorithms

由圖6可以看出,PSO、DE和FA均出現(xiàn)了早熟收斂現(xiàn)象,而IFA在短暫收斂后,在迭代到151步時成功跳出局部最優(yōu)并最終達(dá)到極高的優(yōu)化精度?，F(xiàn)給出算法迭代150步到151步時的個體分布情況。由于個體維數(shù)較高,因此通過評估每個個體與平均個體在搜索空間中的相對距離得到個體分布散點(diǎn)圖,如圖7所示。

圖7 典型迭代時刻個體分布Fig.7 Individual distribution of typical iteration time

可以看出,種群在151步時部分個體突變至距離平均個體較遠(yuǎn)的位置,獲得了更優(yōu)解的同時,帶動種群整體移動,整體的多樣性比150步時有了明顯的提升。通過以上仿真和分析,證明了所提改進(jìn)策略在基準(zhǔn)函數(shù)優(yōu)化方面的有效性。

4.3 裝箱問題實(shí)例

本文將IFA用于求解裝箱問題。裝箱問題是一個經(jīng)典NP-hard組合優(yōu)化問題,在運(yùn)籌學(xué)、離散數(shù)學(xué)、計算機(jī)科學(xué)以及工業(yè)生產(chǎn)等方面有著廣泛的應(yīng)用。

設(shè)有足夠數(shù)量的結(jié)構(gòu)相同容量一致的箱子,,…,每個箱子的最大容量為?，F(xiàn)有一組個物品,,…,，體積分別為(0<<,=1,2,…,)，需裝入箱內(nèi),要求在滿足約束的情況下打包所有物品,要求所需箱子數(shù)量盡可能的少。兩個約束分別為:① 所有物體均不可分割,需保持完整并恰好放入一個箱子中;② 每個箱子所放物品體積總和均不能超過容量上限。假設(shè)物品形狀對裝箱沒有影響,則該問題可描述為

(25)

其中,

假設(shè)30個物品體積分別為[6,3,4,6,8,7,4,7,7,5,5,6,7,7,6,4,8,7,8,8,2,3,4,5,6,5,5,7,7,12],箱子容量=30。固定迭代1 000步,種群規(guī)模為20,其余參數(shù)不變。優(yōu)化結(jié)果與PSO、DE和FA比較,算法收斂情況如圖8所示。

圖8 裝箱問題的性能比較Fig.8 Comparison on bin packing problem

由圖8可以看出,IFA僅需12步即可達(dá)到其他3種算法的優(yōu)化效果,并且經(jīng)進(jìn)一步迭代后能夠跳出局部最優(yōu),從而得到更優(yōu)的結(jié)果。表4給出了幾種優(yōu)化算法的總體運(yùn)行時間(total time,TT)、收斂時間(convergence time,CT)和最優(yōu)結(jié)果(Best)。比較可知,IFA在優(yōu)化結(jié)果和收斂速度方面都有著明顯的優(yōu)勢。

表4 裝箱問題優(yōu)化結(jié)果Table 4 Optimization results of bin packing problem

5 結(jié) 論

本文為克服FA易陷入局部最優(yōu)的缺陷,提出了IFA。首先分析了個體位置更新機(jī)制的特點(diǎn),提出了一種隨機(jī)擾動策略,闡述了改進(jìn)策略的有效性,并分析了不同擾動因子選取的可行性。通過引入元素置換變異策略和最優(yōu)差分變異策略,提高了算法跳出局部最優(yōu)的能力?；陔S機(jī)算法收斂準(zhǔn)則和馬爾可夫過程的理論分析指出,改進(jìn)算法在足夠大的迭代次數(shù)下能夠以概率1收斂到全局最優(yōu)。對4種基準(zhǔn)函數(shù)的仿真結(jié)果表明,隨機(jī)擾動因子選擇均勻分布時有最佳表現(xiàn)。在相同條件下與幾種經(jīng)典算法相比,改進(jìn)算法的收斂精度和SR更高,驗(yàn)證了改進(jìn)算法的優(yōu)越性。將該方法對經(jīng)典裝箱問題進(jìn)行求解,得到了較好的優(yōu)化結(jié)果,驗(yàn)證了改進(jìn)方法的有效性和實(shí)用價值。