李良光，朱 麗，邢麗坤

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

0 引 言

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

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

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

1 基本果蠅優(yōu)化算法

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

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

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

步驟3 計(jì)算食物位置與原點(diǎn)的距離Di，并使用倒數(shù)作為果蠅個(gè)體的氣味濃度判定值Si；

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

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

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

步驟7 進(jìn)入迭代優(yōu)化求出最優(yōu)值。

2 混合策略改進(jìn)的果蠅優(yōu)化算法

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

步驟1 初始化果蠅種群大小Sizepop，最大迭代數(shù)Maxgen，最大權(quán)重因子wmax、最小權(quán)重因子wmin和常量系數(shù)b，隨機(jī)生成群體坐標(biāo)X_axis、Y_axis；

步驟2 執(zhí)行FOA算法中的步驟2～步驟5；

步驟3 計(jì)算自適應(yīng)權(quán)重w；

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

步驟5 對個(gè)體的歷史最優(yōu)位置，使用搜索包圍和螺旋上升公式，進(jìn)行加速搜索；

步驟6 按照更新后的位置公式自適應(yīng)更新果蠅的位置；

步驟7 進(jìn)入迭代尋優(yōu)重復(fù)執(zhí)行算法流程中的步驟2～步驟6，直到達(dá)到最大迭代數(shù)。

2.1 自適應(yīng)權(quán)重系數(shù)

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

(1)

(2)

其中，smelli是當(dāng)前果蠅的適應(yīng)度值，smellavg是果蠅種群的平均適應(yīng)度值，smellav1，smellav2分別是適應(yīng)度值大于果蠅種群平均適應(yīng)度值的所有果蠅的平均適應(yīng)度值，小于果蠅種群平均適應(yīng)度值的所有果蠅的平均適應(yīng)度值,wmax為最大權(quán)重因子，wmin為最小權(quán)重因子，r是[0,1]之間的隨機(jī)數(shù)。

2.2 搜索包圍和螺旋式上升

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

(1)搜索包圍機(jī)制

a=2-2g/Maxgen

(3)

A=2a·rand-a

(4)

C=2·rand

(5)

(6)

(7)

(8)

(9)

(2)螺旋更新位置

(10)

(11)

對兩種搜索策略選擇相同的概率p進(jìn)行位置更新，其數(shù)學(xué)模型表示如下

(12)

(13)

為了避免過早收斂、平衡算法探索和開發(fā)能力，將自適應(yīng)權(quán)重系數(shù)引入歷史最優(yōu)位置更新公式中以提高算法的尋優(yōu)精度，因此，變化后的位置更新公式為

(14)

(15)

2.3 多尺度高斯變異算子

2.3.1 多尺度協(xié)同變異

果蠅算法與其它智能算法一樣，容易陷入局部收斂，為了克服對群體初始位置依賴引起的局部最優(yōu)限制，提出多尺度協(xié)同變異。當(dāng)算法達(dá)到局部極值時(shí)，會(huì)改變?nèi)后w的位置，以避開局部最優(yōu)。然后根據(jù)群體的新位置，迭代地尋找一個(gè)新的極值來尋找全局最優(yōu)。

但是一個(gè)適當(dāng)?shù)耐蛔兂叨炔荒茴A(yù)先確定，必須考慮以下幾個(gè)問題：

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

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

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

2.3.2 高斯變異算子

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

(16)

(1)根據(jù)適應(yīng)度值對群體中的果蠅進(jìn)行分類；

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

(17)

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

(2)每個(gè)子組的適應(yīng)度值在第t次迭代中根據(jù)式(18)～式(20)設(shè)置

(18)

(19)

(20)

隨著算法的迭代，變異算子可能變得非常大。因此，需要變異算子的標(biāo)準(zhǔn)差來規(guī)范變異算子

(21)

(3)根據(jù)各子群的標(biāo)準(zhǔn)差，將種群位置定義為

(22)

(23)

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了研究MSFOA的性能，本文設(shè)計(jì)了兩個(gè)對比實(shí)驗(yàn)：①FOA優(yōu)化實(shí)驗(yàn)；②MSFOA 優(yōu)化實(shí)驗(yàn)。通過對比實(shí)驗(yàn)來驗(yàn)證所提出的MSFOA算法的可靠性。實(shí)驗(yàn)選用6個(gè)著名的函數(shù)作為測試函數(shù)，測試函數(shù)的具體參數(shù)設(shè)置見表1。

表1 6個(gè)測試函數(shù)的參數(shù)設(shè)置

為了比較和突出MSFOA算法的優(yōu)化結(jié)果，本文選擇了具有更高要求的實(shí)驗(yàn)參數(shù)，兩個(gè)參數(shù)可以設(shè)置為：初始種群數(shù)Sizepop=30，最大尋優(yōu)數(shù)Maxgen=200，參照表1中每個(gè)函數(shù)的搜索區(qū)間隨機(jī)初始化果蠅種群位置。

算法性能評估采用的方法：①固定尋優(yōu)次數(shù)，評估算法的尋優(yōu)能力和穩(wěn)定性，并與參考文獻(xiàn)[11]自適應(yīng)粒子群優(yōu)化算法APSO和文獻(xiàn)[12]的鯨魚優(yōu)化算法WOA進(jìn)行比較；②固定收斂精度目標(biāo)值，比較MSFOA和FOA算法在不同高維情況下的運(yùn)行時(shí)間，分析MSFOA的時(shí)間復(fù)雜度。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 固定進(jìn)化迭代次數(shù)的收斂速度和精度

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

表2 4種對比算法參數(shù)設(shè)定

表3 算法優(yōu)化性能比較

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

3.2.2 算法時(shí)間復(fù)雜度的分析

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

圖1 Rastrigin函數(shù)適應(yīng)度進(jìn)化曲線

圖2 Schaffer函數(shù)適應(yīng)度進(jìn)化曲線

圖3 Ackley函數(shù)適應(yīng)度進(jìn)化曲線

圖4 Griewank函數(shù)適應(yīng)度進(jìn)化曲線

圖5 Quartic函數(shù)適應(yīng)度進(jìn)化曲線

圖6 Sphere函數(shù)適應(yīng)度進(jìn)化曲線

表4 f1、f3、f4的平均運(yùn)行時(shí)間對比

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

4 結(jié)束語

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