基于混合策略改進的果蠅優化算法

李良光，朱 麗，邢麗坤

(安徽理工大學 電氣與信息工程學院，安徽 淮南 232001)

0 引 言

果蠅優化算法(fruit fly optimization algorithm，FOA)和其它智能優化算法相比有許多明顯的優點，例如結構簡單、易于實際應用、求解速度快、計算成本低等[1,2]，因此,在許多領域都得到了成功的應用。其中，Li等[3]將FOA應用于解決煉鋼系統中混合流車間重調度問題，得到了不錯的實驗結果。Zhang等[4,5]將FOA引入服務計算，并對其性能進行了實驗分析。Zheng等[6]設計了一種新的編碼方案和多組技術，提高了解決半導體最終測試調度問題的效率。

然而，與其它優化算法一樣，FOA也有其局限性。因此，近年來許多研究人員都在嘗試改進FOA。其中文獻[7]提出融合禁忌搜索的混合果蠅優化算法，即將“禁忌”與“特赦”思想引入果蠅算法，從而避免算法陷入局部收斂；文獻[8]提出了一種基于極值優化的果蠅算法，將極值動態算法的基本思想引入FOA，通過改變初始分布策略，隨機替換個體來提高果蠅種群的多樣性，從而防止局部最優和提高收斂精度；文獻[9]提出基于自適應改變迭代步長值的果蠅優化算法，根據群體每次迭代的歷史記憶動態自適應地調整群體范圍參數，采用更準確的精英策略，因此非常有效地加速群體向全局最優前端的收斂。

為了克服FOA的缺點同時保留其優點，本文提出混合策略改進的果蠅優化算法(mixed strategy based improved fruit fly optimization algorithm，MS-FOA)。采用搜索包圍和螺旋上升組合搜索的方法，對果蠅個體歷史最優位置進行更新，加快算法收斂速度；引入自適應加權系數提高算法的優化精度；結合多尺度高斯變異算子克服局部最優的限制。

1 基本果蠅優化算法

果蠅算法是根據果蠅在自然界中的覓食行為，果蠅以獨特的嗅覺和視覺以及氣味濃度來決定食物的位置。FOA的優化過程包括以下7個步驟：

步驟1 初始化種群大小Sizepop，最大迭代數Maxgen，隨機生成群體位置X_axis、Y_axis；

步驟2 給出果蠅隨機搜尋食物的方向和距離；

步驟3 計算食物位置與原點的距離Di，并使用倒數作為果蠅個體的氣味濃度判定值Si；

步驟4 將果蠅個體的氣味濃度判定值Si帶入氣味函數(或稱適應度函數)，求出個體氣味濃度值smelli；

步驟5 找出該果蠅群體中氣味濃度最低的果蠅(求最小值)；

步驟6 保留已識別的最佳氣味濃度值并更換群體位置；

步驟7 進入迭代優化求出最優值。

2 混合策略改進的果蠅優化算法

本文針對果蠅算法收斂速度慢，易陷入局部最優，尋優精度不高等問題，引入3種改進策略，提出一種基于混合策略改進的果蠅優化算法(mixed strategy based improved fruit fly optimization algorithm，MS-FOA)，算法的流程如下所示：

步驟1 初始化果蠅種群大小Sizepop，最大迭代數Maxgen，最大權重因子wmax、最小權重因子wmin和常量系數b，隨機生成群體坐標X_axis、Y_axis；

步驟2 執行FOA算法中的步驟2～步驟5；

步驟3 計算自適應權重w；

步驟4 將種群劃分為N個子種群，計算各子種群的變異因子,對每個果蠅進行高斯變異；

步驟5 對個體的歷史最優位置，使用搜索包圍和螺旋上升公式，進行加速搜索；

步驟6 按照更新后的位置公式自適應更新果蠅的位置；

步驟7 進入迭代尋優重復執行算法流程中的步驟2～步驟6，直到達到最大迭代數。

2.1 自適應權重系數

為了解決算法過早收斂的問題，將粒子群算法(PSO)慣性權重因子w[10]引入果蠅位置更新公式中。然而，隨著迭代次數的增加傳統慣性權重因子呈線性遞減，這種變化易使得算法收斂速度過慢。因此，受文獻[11]中改進策略的啟發，本文在不改變原始權重因子變化趨勢的情況下，引入非線性調整策略，綜合利用了種群的慣性因子以及果蠅的適應度, 更加靈活有效地調節算法的局部和全局搜索能力,其公式可以表示為

(1)

(2)

其中，smelli是當前果蠅的適應度值，smellavg是果蠅種群的平均適應度值，smellav1，smellav2分別是適應度值大于果蠅種群平均適應度值的所有果蠅的平均適應度值，小于果蠅種群平均適應度值的所有果蠅的平均適應度值,wmax為最大權重因子，wmin為最小權重因子，r是[0,1]之間的隨機數。

2.2 搜索包圍和螺旋式上升

目前針對FOA的改進方法大多都是對步長值或果蠅全局搜索能力的調整，來提高算法的收斂精度和穩定性，然而，它忽略了果蠅算法的缺陷，那就是收斂速度慢的問題。受鯨魚捕食獵物的啟發[12]，本文在對個體歷史最優位置的更新中，采用搜索包圍和螺旋式上升組合搜索加快果蠅迭代速度。具體方法如下：

(1)搜索包圍機制

a=2-2g/Maxgen

(3)

A=2a·rand-a

(4)

C=2·rand

(5)

(6)

(7)

(8)

(9)

(2)螺旋更新位置

(10)

(11)

對兩種搜索策略選擇相同的概率p進行位置更新，其數學模型表示如下

(12)

(13)

為了避免過早收斂、平衡算法探索和開發能力，將自適應權重系數引入歷史最優位置更新公式中以提高算法的尋優精度，因此，變化后的位置更新公式為

(14)

(15)

2.3 多尺度高斯變異算子

2.3.1 多尺度協同變異

果蠅算法與其它智能算法一樣，容易陷入局部收斂，為了克服對群體初始位置依賴引起的局部最優限制，提出多尺度協同變異。當算法達到局部極值時，會改變群體的位置，以避開局部最優。然后根據群體的新位置，迭代地尋找一個新的極值來尋找全局最優。

但是一個適當的突變尺度不能預先確定，必須考慮以下幾個問題：

(1)如果突變尺度過大，可能會跳過一些極值點，包括全局極值；

(2)如果變異尺度太小，則可能需要大量迭代才能遍歷整個搜索空間。這會大大降低算法的收斂速度。

為了解決上述問題，本文使用了一個具有不同尺度方差的高斯突變算子來逃離局部最優。

2.3.2 高斯變異算子

假設總共有M個突變尺度。初始化高斯變異算子的方差

(16)

(1)根據適應度值對群體中的果蠅進行分類；

(2)將排序后的果蠅分組生成M個子群，每個子群中有P=N/M個果蠅，計算每個子群的適應度值如下

(17)

(1)得到了所有子群的最大值和最小值，分別表示為Fitmax、Fitmin；

(2)每個子組的適應度值在第t次迭代中根據式(18)～式(20)設置

(18)

(19)

(20)

隨著算法的迭代，變異算子可能變得非常大。因此，需要變異算子的標準差來規范變異算子

(21)

(3)根據各子群的標準差，將種群位置定義為

(22)

(23)

3 實驗及結果分析

3.1 實驗設計

為了研究MSFOA的性能，本文設計了兩個對比實驗：①FOA優化實驗；②MSFOA 優化實驗。通過對比實驗來驗證所提出的MSFOA算法的可靠性。實驗選用6個著名的函數作為測試函數，測試函數的具體參數設置見表1。

表1 6個測試函數的參數設置

為了比較和突出MSFOA算法的優化結果，本文選擇了具有更高要求的實驗參數，兩個參數可以設置為：初始種群數Sizepop=30，最大尋優數Maxgen=200，參照表1中每個函數的搜索區間隨機初始化果蠅種群位置。

算法性能評估采用的方法：①固定尋優次數，評估算法的尋優能力和穩定性，并與參考文獻[11]自適應粒子群優化算法APSO和文獻[12]的鯨魚優化算法WOA進行比較；②固定收斂精度目標值，比較MSFOA和FOA算法在不同高維情況下的運行時間，分析MSFOA的時間復雜度。

3.2 實驗結果與分析

3.2.1 固定進化迭代次數的收斂速度和精度

6個測試函數的迭代次數設置為200，通過6個基準函數進一步比較FOA、WOA、MSFOA、和APSO 算法的性能。4種算法的個性化參數值的設置見表2。為了保證結果的可靠性，對每個測試函數獨立運行20次，得到 20次的最優結果見表3。從表3中可以看出，使用改進后的MSFOA算法對單峰函數和多峰函數的均值和標準差都有明顯改善。對于單峰函數f5，MSFOA比FOA的收斂精度和標準差提高了55個數量級，對于單峰函數f6，MSFOA的尋優精度更高，達到了e-207，比FOA和WOA高了207個數量級，比APSO算法高了95個數量級，并且MSFOA的收斂標準差為0，說明MSFOA達到目標精度后保持了良好的收斂狀態；對于多峰函數f1,MSFOA的均值和標準差均達到了理論最優值0，對于多峰函數f3，MSFOA 和APSO的均值和標準差相同，其均值都優于FOA和WOA 16個數量級，充分說明MSFOA比FOA、WOA、和APSO收斂精度更高，收斂平穩性更好。

表2 4種對比算法參數設定

表3 算法優化性能比較

為了清晰地反映出改進算法的優化效果，圖1～圖6顯示了6個測試函數的適應度進化曲線圖(為了方便顯示和觀察收斂曲線，本文將函數的適應度作為基數10的對數)，形象對比了FOA、WOA、MSFOA和APSO算法在不同函數中迭代200次的收斂曲線。從6個函數收斂曲線中可以明顯看出：對于多峰函數f1、f2、f3和f4，MSFOA比FOA、WOA和APSO穩定且逐漸接近全局最優；對于單峰函數f5和f6，MSFOA也能快速收斂，并且對于其它3種算法都會出現收斂停滯，陷入局部最優的情況，這明確地說明了MSFOA逃離局部最優并逐步接近全局最優的能力。總體來說，MSFOA算法具有更好的優化性能。

3.2.2 算法時間復雜度的分析

大多數的改進算法往往只注重提高算法的性能，卻沒有考慮算法運行的時間。然而一個可靠的改進算法還應該具有較低的時間復雜度。本小節選用3個比較典型的多模函數f1，f3和f4 來測試和分析時間復雜度。設置種群大小Sizepop=30，最大迭代數Maxgen=200，獨立運行20次，為了驗證本文改進的算法對于提升算法收斂速度的有效性，將函數設置在不同維度(30維、100維和300維)來計算兩種算法的平均運行時間，D為維度，測試結果見表4。

圖1 Rastrigin函數適應度進化曲線

圖2 Schaffer函數適應度進化曲線

圖3 Ackley函數適應度進化曲線

圖4 Griewank函數適應度進化曲線

圖5 Quartic函數適應度進化曲線

圖6 Sphere函數適應度進化曲線

表4 f1、f3、f4的平均運行時間對比

從表4中可以看出，MSFOA在達到目標精度下所需的平均時間均比FOA少，對于30維函數，MSFOA和FOA所需的平均時間差不多,但是在計算高維函數時，MSFOA運行時間明顯比FOA少，說明MSFOA在處理高維函數時復雜度更低，進而驗證了本文在對個體歷史最優位置的更新中，采用搜索包圍和螺旋式上升組合搜索的方法，加快果蠅搜索迭代速度是可行有效的。

4 結束語

在保持傳統果蠅算法良好性能的基礎上提出了混合策略改進的果蠅優化算法，采用搜索包圍和螺旋上升組合搜索的方法，能夠快速找到全局最優解，將自適應權重系數引入位置更新公式中，融合多尺度高斯變異算子，使得改進后的算法克服了局部最優的限制，避免了過早收斂。通過對6個測試函數的仿真實驗，仿真結果表明，本文所提出的MSFOA算法有效地提高了收斂精度，同時也保持了較低的復雜度。