一種改進的進化模型和混沌優化的螢火蟲算法?

李肇基 程 科 王萬耀 崔慶華

（江蘇科技大學計算機學院 鎮江 212000）

1 引言

螢火蟲算法（Firefly Algorithm，FA）是2008 年由Xin-She Yang［1］提出的一種元啟發式算法，其思想來源于螢火蟲的發光行為。螢火蟲會向亮度更強且更為靠近自己的螢火蟲移動，通過這種方式進行種群進化，進而實現尋優。目前，螢火蟲算法已成功應用到數值優化、工程技術、資源管理等領域［2～6］，并且表現出良好的性能和適應性。與大多數隨機算法相同，傳統螢火蟲算法同樣存在后期收斂速度慢、易陷入局部最優等缺點。

針對傳統算法的缺點，眾多學者對其進行了研究與改進。Gandomi［7］等用不同的混沌映射模型對光強吸收系數與吸引度系數進行混沌映射，實驗證明正弦映射與高斯映射能有效提高螢火蟲算法的全局優化能力。但是，僅對光強吸收系數與吸引度因子采用混沌優化，沒有充分體現混沌思想對螢火蟲算法的種群與進化過程的優化作用；馮艷紅［8］等將立方映射所產生的混沌序列引入到螢火蟲算法，提出一種基于混沌理論的動態種群螢火蟲算法，減少了螢火蟲的無效運動提高了算法精度。但是采用隨機方式替換掉種群中的個體，容易破壞原種群結構，使優化結果變差；符強［9］等分析了螢火蟲算法的進化計算機制，提出一種基于新型進化計算模式的改進型螢火蟲優化算法（IEFA），并利用高斯變異改善個體的多樣性，有效改善螢火蟲算法過早進化停滯的問題，但是對整個種群進行變異擾動，可能會使種群多樣性降低，而且增加了算法的計算時間；郁書好［10］將自適應步長運用到螢火蟲算法的位置更新公式中，提出自適應步長螢火蟲優化算法，有效地提高了算法的綜合性能。但是單純地改變步長機制，并不能有效解決初始種群分布不均和進化過程中的域約束等問題。

基于標準螢火蟲算法存在的缺陷，并受近年來一些改進思想的啟發，提出一種改進的進化模型和混沌優化的螢火蟲算法（Firefly Algorithm Based on Improved Evolutionary Model and Chaos Optimization，FAEC），該算法通過混沌映射對種群進行初始化，在迭代過程中采用慣性權重和動態步長平衡算法的局部尋優與全局搜索性能，并通過種群最優個體引導其他個體進行移動，實現螢火蟲之間的信息共享，對超出搜索區域的螢火蟲，引入對稱邊界變異操作，提高了種群多樣性。最后標準測試函數的結果表明，與標準螢火蟲算法相比所提算法具有更高的尋優精度和更快的收斂速度，同時能夠避免因迭代過早停滯而陷入局部最優的問題。

2 傳統螢火蟲算法

2.1 算法的仿生原理與數學描述

傳統螢火蟲算法是一種仿生智能優化算法，具體的仿生原理如下［11］。

1）螢火蟲總是不分雄雌地向著比較亮的螢火蟲移動，最亮的螢火蟲隨機移動。

2）螢火蟲之間的相對吸引力決定了螢火蟲的移動距離，吸引力與螢火蟲個體的亮度成正比關系，與螢火蟲之間的距離成反比關系。

3）對于函數優化問題，可以將目標函數的值作為螢火蟲亮度的評判標準，將螢火蟲的位置作為目標函數的解。螢火蟲的亮度越高，表明目標函數值越優，通過種群進化，最終亮度最高的螢火蟲的位置，便是待優化的目標函數趨近理論最優值的解。

在FA 算法中，亮度和吸引度是螢火蟲個體的兩個重要特征。其中，亮度的高低代表了螢火蟲所處位置的優劣并決定了螢火蟲個體的移動方向，吸引度則直接影響了螢火蟲個體的移動距離，通過亮度和吸引度的不斷更新和迭代來尋找目標函數的最優解。在FA 算法中螢火蟲i 到螢火蟲j 的距離rij，通常用歐氏距離計算，即:

其中d表示搜索空間的維度。

由定義螢火蟲i對螢火蟲j的吸引力和螢火蟲i對螢火蟲j的相對亮度成正比，可得螢火蟲i對螢火蟲j的吸引力為

式中，β0為最大吸引力，表示光源處（r=0）螢火蟲的吸引力，通常 β0=1。γ 為光強吸收系數，它的取值對FA 算法的收斂速度和優化效果有很大的影響。

螢火蟲i相對螢火蟲j的熒光亮度公式為

式中，Ii是螢火蟲i 的絕對亮度，對應螢火蟲i 所處位置的目標函數值；γ 為光強吸收系數，描述了熒光隨著距離增加和傳播介質的吸收而逐漸減弱的光學特性，可設為常量。

螢火蟲j被螢火蟲i吸引，j向i移動來更新原有的位置，j位置的更新公式為

式中，t為算法的迭代次數，xj(t+1)代表螢火蟲j在第t+1次迭代的位置；βij是螢火蟲i對螢火蟲j的吸引力；α 為常數，取 α ∈［0，1］；rand 是在［0，1］上服從均勻分布的隨機因子。

算法尋優過程為:采用隨機方式在搜索空間生成螢火蟲種群，螢火蟲個體的亮度由其所在的空間位置決定，通過比較式（3）可得，螢火蟲會向比自己亮度更高的個體移動，通過計算式（2）所得的吸引力是影響移動距離的主要因素，移動后的新位置根據式（4）來計算，在位置更新公式中增加了隨機擾動項，避免種群過早陷入局部最優，經過若干次迭代尋優后，種群個體將會運動到亮度最高的螢火蟲的位置，算法得到全局最優解。

2.2 算法的局限性分析

在實際問題中很多待優化函數通常具有多峰、高維、地形復雜等，表現為大量的局部極值分布在全局最優值周圍，傳統螢火蟲算法在優化這類問題時容易早熟收斂，尋優精度難以提高。造成這種現象的原因是由于傳統螢火蟲算法通過螢火蟲個體之間的相互吸引來實現尋優，而個體不具備變異特性，很容易陷入局部極值。尤其在進化前期，種群中的超級個體通常會吸引其他個體快速聚集到其周圍，造成種群多樣性降低，而且，隨著個體逐漸接近全局最優值，種群的收斂速度會明顯下降甚至出現進化停滯現象，喪失了進一步進化的能力，往往這種現象發生時，算法尚未收斂到全局最優值。因此，保證種群在整個進化過程中具有持續優化能力，提高種群多樣性，是提高傳統螢火蟲算法性能的重要途徑。

3 一種改進的進化模型和混沌優化的螢火蟲算法

3.1 基于混沌優化策略的種群初始化

在非線性系統中，存在一種特有的非周期運動現象被稱為混沌現象，其特點是行為復雜，與隨機現象類似，但是存在內在的規律性。利用混沌運動的隨機性、遍歷性和初值敏感性來提高隨機優化算法的效率就是混沌優化［12］。基本思想為利用混沌變量的遍歷性和隨機性，通過混沌映射規則將待優化變量映射到混沌變量的取值區間內，將獲得的混沌序列，通過線性變換轉化到目標函數的搜索空間。

在多種混沌序列的模型中，邏輯自映射函數產生的混沌序列遍歷性要優于常用的Logistics 映射［13］。采用邏輯自映射函數生成混沌序列，如式（5）所示:

其中，為避免混沌序列出現全為1 或0.5 的情況，所以初始值不能取0 和0.5，d 表示D 維搜索空間的第d維。

初始化混沌種群的過程描述如下:

步驟1 對于D 維空間的M 個螢火蟲個體，根據邏輯自映射函數的性質，首先初始化混沌變量，在(-1,1)區間隨機產生初始變量。

步驟2 按照式（5）迭代，將邏輯自映射生成的MaxGeneration *D-1 個混沌變量，與初始混沌變量一起對應全部MaxGeneration*D 個螢火蟲個體。

步驟3 將產生的混沌變量序列按式（6）變換到目標函數的搜索空間，生成螢火蟲初始種群的M個個體，公式如下:

式中，Lb 和Ub 分別表示搜索空間第d維的下限和上限，yn,d是根據式（6）產生的第i個螢火蟲對應的第d 維混沌變量，xi,d為第i 個螢火蟲在搜索空間中第d維的坐標值。

傳統螢火蟲算法的隨機種群初始化效果如圖1 所示，基于混沌優化策略的種群初始化效果如圖2所示。

圖1 隨機種群初始化

圖2 基于混沌優化策略的種群初始化

從圖1 和圖2 的初始化種群分布對比可以看出，采用混沌優化策略的初始種群，種群分布的均勻性要明顯優于采用隨機策略的初始化種群。

3.2 基于慣性權重的進化計算模型

由式（2）可知，隨著種群的持續迭代，個體之間距離不斷減小，個體間的相對吸引力逐漸增大，降低了算法的局部搜索能力。式（4）中加入了帶有特定系數的隨機項，加大了搜索范圍，避免算法過早陷入局部最優，但可能需要迭代多次才能達到精度要求，使得算法在迭代次數受限的情況下，無法滿足精度要求。為了提高算法的局部搜索和全局搜索能力，在式（4）中引入慣性權重，并增加種群中最優個體對其他個體的牽引作用［9］。改進的位置更新公式如式（7）所示:式中，第一項ω(t)×xj(t)表示螢火蟲個體的前一次迭代位置對當前位置的影響，第四項ω(t)×rand()×(xbest(t)-xj(t))表示當前迭代的種群最優個體對種群中個體提供的牽引作用，用來控制當前種群最優個體對其他個體的影響程度，以及當前個體對前代個體的繼承情況。慣性權重分為固定權重和時變權重，在粒子群算法研究中，自適應權重［14］是常用的時變權重之一。為充分利用目標函數信息，加強搜索方向的指導性，進一步提高個體移動速度［15］，提出一種新型的自適應慣性權重，計算公式如式（8）所示:

式中，f(xbest(t)) 為第t 次迭代的全局最優值，fi(t-1)和 fi(t-2)分別為 i 螢火蟲第 t-1 和 t-2 次迭代的值，M(f)=f(xi(t))為第t 次迭代的種群目標函數值的平均值。

螢火蟲的移動距離受到慣性權重的影響，分析式（8）可得，在每一次迭代中，慣性權重根據上一次迭代產生的全體目標函數值與i螢火蟲前兩次迭代的目標函數值計算所得，從而減少慣性權重變化的盲目性。由于在慣性權重的求解過程中充分利用了目標函數的信息，使得螢火蟲算法的搜索方向具有指導性，螢火蟲個體向高質量區域快速移動。在算法迭代后期，螢火蟲個體已經接近最優解，且相鄰兩次迭代差值減小，此時慣性權重變小，螢火蟲的移動距離隨之減小，加快了算法的收斂速度，提高了搜索能力，從而改善算法的尋優性能。

3.3 基于高斯分布的種群變異操作

螢火蟲種群陷入局部最優的特征是進化出現停滯，即連續多次迭代并未使種群最優值發生變化。通過實驗總結初步設定，當經過連續6 次迭代，種群的全局最優值未發生變化，則判定其進化停滯，已經陷入局部最優區域。為了幫助螢火蟲種群脫離局部最優值束縛，本文采用高斯分布對螢火蟲種群進行變異操作。高斯概率分布被廣泛應于工程應用中，對工程優化與設計具有良好的促進作用。高斯分布的概率密度函數如式（9）所示。

其中，σ 為高斯分布的方差，μ 為期望。

將種群中的全部螢火蟲個體按目標函數值的大小進行排序，利用最優的10%×n 個螢火蟲將排名最后的10%×n 個螢火蟲群體進行狀態替換更新，同時對更新螢火蟲群體的狀態進行高斯變異處理，變異公式如式（10）所示。

其中，N(0,1)為隨機向量，并且為服從期望為0、方差為1的高斯分布。

當經過6 次迭代后，全局最優值沒有發生改變時，未執行種群變異操作的種群分布如圖3 所示，執行基于高斯分布的種群變異操作的種群分布如圖4所示。

圖3 未執行種群變異操作的種群分布

圖4 進行種群變異操作的種群分布

從圖3 和圖4 圈出的區域對比可以看出，圖3中被圈出的點分布較密集，已經陷入局部最優區域，種群未執行高斯種群變異操作，陷入局部最優區域的個體無法跳出局部最優值的束縛，圖4 為已經執行高斯種群變異操作，種群個體能夠跳出局部極值區域。

3.4 動態步長與域約束機制

步長在螢火蟲優化算法中扮演著重要的角色，設置合適的步長值會直接影響到算法的全局搜索和局部搜索能力。標準FA 算法采用固定的步長值，在一定程度上無法體現出個體的差異性，遞減步長能夠動態調節個體的移動幅度，使個體在迭代前期以較大的步長進行全局搜索，而后期則以較小步長進行局部尋優。本文采用隨著迭代次數非線性遞減的方式計算步長。如式（11）所示:

式中，Δαt為步長的動態衰減系數，并且Δαt=1-(10-4/0.9)(1/t)，t表示迭代次數。隨著迭代次數t的增大，Δαt逐漸增大，（1- Δαt）減小，使得t+1 代的步長逐漸減小。

采用固定步長和非線性遞減步長的曲線走勢如圖5和圖6所示。

圖5 固定步長曲線

圖6 非線性遞減步長曲線

在螢火蟲算法的迭代過程中，為了保證種群個體能夠在搜索空間中進行有效搜索，當螢火蟲的位置超出目標函數的可行域時，一般是將螢火蟲的位置替換為超出的邊界值，此時域約束公式如式（12）所示:

式中，xmin為搜索空間下限，xmax為搜索空間上限。這種邊界控制策略容易使算法陷入局部最優，而且超出邊界的點全部約束在邊界處，有可能會使算法在邊界處過早收斂，降低算法的尋優率。因此，引入一種對稱邊界變異操作［16］，此時的域約束公式如式（13）所示:

對稱邊界變異操作能夠使種群中螢火蟲的位置始終保持在可行域內，避免了螢火蟲算法在邊界處陷入局部最優，同時在一定程度上提高了種群的多樣性，動態步長與邊界變異操作有效地提高了螢火蟲算法的收斂速度和尋優率。

3.5 算法流程

基于標準螢火蟲算法，將混沌優化策略、慣性權重、種群最優個體引導、動態步長和域約束機制等引入螢火蟲算法，提出一種改進的進化模型和混沌優化的螢火蟲算法，其算法的執行流程描述如下:

步驟1:初始化參數。設置螢火蟲數目m，問題維度d，光強吸收系數γ，步長因子初始值α，最大吸引度因子 β0，最大迭代次數MaxGeneration，搜索精度ε。

步驟2:初始化種群。采用式（5）生成初始混沌序列，然后根據式（6）將混沌序列映射到螢火蟲算法的解空間，生成螢火蟲種群的初始位置xi(i=1,2,…,m)。

步驟3:根據種群中個體的位置計算各螢火蟲的目標函數值，作為螢火蟲個體各自的最大熒光亮度I0，對種群中的螢火蟲個體按照目標函數值排序并記錄最優值 fbest，同時記錄最優個體位置。

步驟4:根據式（3）計算種群中螢火蟲個體之間的距離rij，再由式（1）計算種群中螢火種個體的相對熒光亮度Iij(rij)，并比較鄰域內螢火蟲亮度的大小，確定螢火蟲個體的移動方向。

步驟5:根據式（2）計算螢火蟲個體的吸引度βij(rij)，再由式（8）計算當前第t 次迭代的慣性權重ω(t)，最后根據式（7）更新螢火蟲的空間位置。

步驟6:由式（11）對迭代步長進行更新，并根據式（13）對種群中的螢火蟲個體進行域約束操作。

步驟7:重新計算移動后的螢火蟲種群的目標函數值，并記錄種群的最優目標函數值 fbest和最優個體位置xbest(t)。當連續6次迭代一直未更新，則將種群中最差的10%×m 個螢火蟲的狀態替換為最優的10%×m 個螢火蟲的狀態，并通過式（10）對過渡種群進行高斯變異操作。

步驟8:當滿足搜索精度或者達到最大迭代次數，轉步驟9，否則轉步驟3。

步驟9:算法迭代完成，輸出結果。

4 實驗仿真與分析

在六個標準測試函數上分析和驗證FAEC 算法的收斂速度與尋優能力，對文獻［9］中的基于改進型進化機制的IEFA 算法和傳統FA 算法進行對比測試。仿真實驗環境基于Windows 10 操作系統，2.5GH 主頻的 Intel 處理器，4G 內存，利用 MatlabR2015a進行編程測試。

1）Sphere Model 函數

2）Rastrigin函數

3）Ackley函數

4）Griewank函數

5）Rosenbrock函數

6）Zakharov函數

4.1 尋優精度分析

對FAEC、IEFA 和FA 算法的公共參數設置如下:初始螢火蟲個體數目為20，迭代次數為500，最大吸引度因子β0=1，初始步長因子α=0.2，光強吸收因子γ =1。其中，對于IEFA，慣性權重從1.1 到0.4線性遞減，步長衰減系數△α=0.97。

函數 f1和 f2的維數為2，函數 f3的維數為15，函數 f4、f5和 f6的維數為30。以上六個標準測試函數經過30次試驗，平均測試結果如表1所示。

表 1 所列為 FA 算法、IEFA 算法和 FAEC 算法對6 個標準測試函數獨立運行30 次的統計結果。可以看出，對于低維測試函數 f1和 f2，3 種算法的尋優精度均很高，而且IEFA 算法和FAEC 算法的最優值、最差值、平均值和標準差均明顯優于標準FA 算法。對于函數 f3、f4和 f6，由于均為高維而且含有大量的局部極值，FAEC 算法的最優值與最差值要比標準FA 算法高出3 個數量級以上，而且綜合性能均優于IEFA 算法，f5為單峰高維，雖然三個函數的測試結果均不理想，但FAEC 在最優值、平均值和標準差上要優于標準FA 和IEFA。對于6 個標準測試函數，FAEC 算法的標準差均低于FA 和IEFA，顯示了其較穩定的尋優過程。因此，與標準FA 和IEFA 算法相比，FAEC 算法具有較高的尋優精度和較穩定的迭代過程。

表1 FA和IEFA，FAEC算法對6個測試函數的計算結果比較

4.2 尋優速度分析

針對以上6 個標準測試函數進行尋優速度分析，算法的參數設置與4.1節一致。

圖7～12 為三種算法在測試函數 f1至 f6上的尋優曲線。

圖7 f1 函數尋優過程（D=2）

圖8 f2 函數尋優過程（D=2）

圖9 f3 函數尋優過程（D=15）

圖10 f4 函數尋優過程（D=30）

圖11 f5 函數尋優過程（D=30）

圖12 f6 函數尋優過程（D=30）

圖 7～12 顯示了 FAEC 算法、IEFA 算法和 FA 算法的尋優過程。從圖7～12 可以看出，與傳統FA 算法和IEFA算法相比，FAEC算法能夠在較少的迭代次數下搜索到全局最優解，具有更快的迭代速度和更高的尋優精度。其中，從圖7、圖8、圖11、圖12中可以直觀地看出，FAEC 算法在50 次迭代內就能收斂并趨于穩定，在圖8中，雖然FAEC算法在迭代初期的迭代曲線劣于IEFA，但最終仍以較少的迭代次數趨于穩定，從圖9、圖10、圖11 可以看出，與使用隨機種群初始化的IEFA算法相比，FAEC算法采用混沌種群初始化方法，并利用非線性遞減步長與對稱邊界變異操作，有助于算法跳出局部最優，平衡和局部尋優與全局搜索，并在一定程度上增加了種群的多樣性，表現出較快的收斂速度和尋優精度。

5 結語

針對FA 算法易陷入局部極值、后期收斂速度慢、尋優精度較低等問題，引入混沌優化策略、進化模型和慣性權重等概念，提出一種改進的進化模型和混沌優化的螢火蟲算法。引入改進的邏輯自映射混沌模型提高種群多樣性；加強種群中最優螢火蟲個體對其他個體的引導作用以及個體對前代位置的繼承情況，采用慣性權重對兩者進行平衡調整，克服早熟收斂問題，增強全局搜索與局部搜索能力，提高收斂速度與尋優精度；在迭代過程中，采用非線性遞減步長與對稱邊界變異，提高了收斂速度，增加了種群多樣性。實驗結果驗證了算法的有效性和優越性。今后相關工作主要側重于FAEC算法的理論推導與實際問題應用研究。