基于輪盤賭反向選擇機制的果蠅優(yōu)化算法?

張 靜 高 尚

（江蘇科技大學計算機學院 鎮(zhèn)江 212003）

1 引言

果蠅優(yōu)化算法（Fruit fly optimization algorithm，F(xiàn)OA）是潘文超博士于2011年6月在果蠅覓食行為中得到啟發(fā)從而提出的。果蠅優(yōu)化算法是一種全局優(yōu)化群智能算法［1～2］，該算法用以求解數(shù)學函數(shù)極值、微調(diào)Z-SCORE模型系數(shù)、廣義回歸神經(jīng)網(wǎng)絡參數(shù)優(yōu)化［3～4］、船舶操縱響應模型的辨識與語音信號盲分離［5］等各種領域。由于果蠅優(yōu)化算法是新興的智能算法，對其理論研究不夠成熟，同時研究成果也不是很多，因此，對果蠅優(yōu)化算法的相關研究需要積極展開。

果蠅優(yōu)化算法簡單易于理解，程序容易實現(xiàn)，運行所需時間較短，受影響的參數(shù)較少，僅有三個：初始位置、種群大小和迭代步長。所以該算法與其他群智能算法相比，具有一定的優(yōu)勢（如遺傳算法需要調(diào)整5個參數(shù)［6］，易早熟收斂且計算量大；粒子群算法需要調(diào)整5個參數(shù)［7］，易陷入局部最優(yōu)；蟻群算法需要調(diào)整7個參數(shù)［8］，過于復雜限制了其應用；免疫算法需要調(diào)整5個參數(shù)［9］，復雜而且計算量大；人工魚群算法需要調(diào)整5 個參數(shù)［10］，計算量大）［11］。果蠅優(yōu)化算法與其他全局優(yōu)化算法近似，都是希望通過迭代從而找到全局最優(yōu)值，但若此最優(yōu)個體不是全局最優(yōu)，則極易使得算法陷入局部最優(yōu)，會導致后期收斂速度緩慢，尋優(yōu)精度偏低。本文針對基本FOA 算法尋優(yōu)精度不高，易陷入局部最優(yōu)的缺點，并從保持種群多樣性以提高果蠅優(yōu)化算法的全局尋優(yōu)能力的角度出發(fā)，在該算法在迭代過程中，采用基于輪盤賭法反向選擇機制來選擇搜索步長，即果蠅群體中適應度越低的個體食物源被選擇的概率越大，這選擇策略與輪盤賭選擇機制相反，從而避免果蠅整體種群迅速向某些適應度值過高的個體進化，達到保持果蠅種群多樣性的目的，最終達到避免果蠅優(yōu)化算法的過早收斂。

2 果蠅算法

2.1 基本原理

果蠅算法是一種根據(jù)果蠅覓食行為推演出尋求全局優(yōu)化方法。果蠅相比于其他物種具有更好的感官知覺，特別是在氣味和視覺方面。果蠅的嗅覺器官能收集到漂浮在周圍空氣中的各類氣味，甚至可以聞到40km 之外的食物。然后，當它飛到食物位置附近后，就可使用敏銳的視覺發(fā)現(xiàn)食物和同伴聚集的位置，從而向食物方向飛去［1］。

2.2 算法過程

根據(jù)果蠅搜尋食物的過程，我們可以將其總結(jié)為以下必要步驟［1］。

Step1 初始化參數(shù)：群體規(guī)模popsize，最大迭代詞數(shù)max gen，隨機初始化果蠅群體位置X_axis，Y_axis；

Step2 賦予果蠅個體利用嗅覺搜尋食物的隨機方向和距離，式（1）中，Random 為搜索距離，其表示一般的隨機數(shù)：

Step3 由于無法得知食物的具體位置，應先計算與原點之間的距離Disti，再計算味道濃度判斷值Si，此值為距離之倒數(shù)：

Step4 將味道濃度判斷值Si代入味道濃度判斷函數(shù)（適應度函數(shù)），從而求得果蠅個體的味道濃度Smelli：

Step5 找出果蠅種群中味道濃度最佳的果蠅（以最小化問題為例）：

Step6 保留最優(yōu)味道濃度值以及其對應的X、Y坐標，果蠅群體利用視覺向該位置飛去：

Step7 此時果蠅種群進入迭代尋優(yōu)。重復執(zhí)行Step2～Step5，并判斷當前味道濃度是否由于歷史味道濃度，且當前迭代次數(shù)小于最大迭代次數(shù)max gen，若是則執(zhí)行Step6；否則，結(jié)束算法。

2.3 果蠅算法的不足

果蠅算法雖然擁有結(jié)構(gòu)簡單、參數(shù)少、易調(diào)節(jié)、易于理解和實現(xiàn)，成功地應用于多個方面，但是隨著研究的深入，算法還存在收斂速度慢、尋優(yōu)精度低等缺點，當位置更新時，當前最優(yōu)個體易于陷入局部極值，并且沒有有效的機制來跳出該局部極值，導致種群停止進化，最終出現(xiàn)全局尋優(yōu)失敗，特別是在解決多峰、高維等復雜問題時會陷入局部最優(yōu)值，導致全局搜索能力較差。

3 改進后的果蠅算法

3.1 輪盤賭策略

傳統(tǒng)的輪盤賭策略是使用適應度值與總適應度值的比率作為選擇概率［12］，這是一種貪婪的選擇方式，這種選擇策略使果蠅種群在具有高適應度值得食物中聚集，從而減少了種群的多樣性。因此反向輪盤賭的選擇策略［13］被引入到果蠅算法中，所謂反向輪盤賭選擇策略，就是將傳統(tǒng)輪盤賭策略中的概率式（7）：

其中fiti是第i 個解的適應度值，N是解的個數(shù)。

換成如下的概率式（8）：

也就是說，適應度值得倒數(shù)與總適應度值的倒數(shù)之間的比率被用于優(yōu)化果蠅種群。從公式可以看出，適應度值越大，適應度值的倒數(shù)的概率就越小，這就可以保持果蠅種群的多樣性，并且不容易陷入局部最優(yōu)。

3.2 改進后的算法過程

改進后的果蠅優(yōu)化算法的可歸納為以下幾個步驟。

Step1 初始化參數(shù)：群體規(guī)模popsize，最大迭代詞數(shù)max gen，隨機初始化果蠅群體位置X_axis，Y_axis；

Step2 執(zhí)行FOA算法的step2～step6；

Step3 根據(jù)式（8）確定個果蠅的味道濃度判定值Si的適應值；

Step4 采用反向輪盤賭發(fā)策略從Si中確定全局最優(yōu)的某個替代值(bestX,bestY)作為果蠅的搜索距離，然后根據(jù)式（9）更新果蠅的位置：

Step5 根據(jù)式（10）計算果蠅原點之間的距離Disti*和式（11）味道濃度判斷值Si*：

Step6計算果蠅個體的味道濃度Smelli*：

Step7 若Smelli*＜Smellbest，則保留最優(yōu)味道濃度值以及其對應的X、Y坐標，果蠅群體利用視覺向該位置飛去：

Step8 進入迭代尋優(yōu)，重復執(zhí)行Step3～Step7，直至當前迭代次數(shù)達到最大迭代次數(shù)max gen 或者已經(jīng)達到理論最優(yōu)值。

4 數(shù)值仿真與分析

4.1 一元函數(shù)優(yōu)化問題

圖1 不同種群規(guī)模下FOA迭代過程圖

一元函數(shù)舉例函數(shù)如下：min f(x)= -5+x2,x∈(-10,10)。

應用傳統(tǒng)的FOA 算法得到迭代結(jié)果如圖1 所示，迭代次數(shù)為100，種群規(guī)模分別為20和30。

種群規(guī)模為20時，迭代到71次達到1e-4精度，種群規(guī)模為30 時，迭代到64 次達到1e-4精度。可見增加種群規(guī)模對其收斂速度改進不大。

在種群規(guī)模、迭代次數(shù)相同的條件下，為了更加值觀地得到改進后的FOA 算法的尋優(yōu)效果，圖2展示了傳統(tǒng)的FOA 算法、改進后的FOA 算法和SA-FOA［14］算法的優(yōu)化過程。

圖2 傳統(tǒng)FOA和改進后的FOA比較

由圖2 可知，相比于FOA 算法和SA-FOA［14］算法，改進后的FOA 算法經(jīng)過兩次迭代即可達到1e-4精度，收斂速度非常快，步長改進效果明顯，且精度較高。

4.2 多元函數(shù)優(yōu)化問題

潘文超教授的相關著作中只提到關于一元二次函數(shù)的極值優(yōu)化應用，這里將本文提出改進后的FOA 算法運用到多元函數(shù)求解最優(yōu)值，與基本的FOA 和SA-FOA［14］算法進行比較。本文從常用于優(yōu)化算法比較的測試函數(shù)中選擇四個來進行驗證，函數(shù)名稱、函數(shù)表達式和理論最優(yōu)解如表1 所示，Sphere 函數(shù)是單峰函數(shù)，其他函數(shù)皆為多峰函數(shù)。另外，Ackley 的函數(shù)搜索非常復雜，這是通過疊加中等放大指數(shù)函數(shù)的余弦而獲得的連續(xù)實驗函數(shù)，其特征在于，通過余弦波調(diào)制幾乎平坦的區(qū)域以形成孔或者峰，從而使表面起伏，并且很難找到最優(yōu)值，容易陷入局部最優(yōu)，因此，與其他三個函數(shù)相比，該函數(shù)尋優(yōu)難度較大。在進行測試時本文打算從兩方面進行：第一，算法的可行性分析，即尋優(yōu)性能分析，在種群規(guī)模和迭代次數(shù)相同時，將收斂速度和尋優(yōu)精度與其他算法進行比較；第二，算法的性能分析，即比較兩種算法的迭代次數(shù)與運行時間。

4.2.1 尋優(yōu)性能分析

設定該果蠅種群規(guī)模的大小為30，固定迭代次數(shù)為100。在本文中，用FOA 算法、SA-FOA［14］算法和改進后的FOA 算法用于對四個測試函數(shù)執(zhí)行20 次獨立測試。測試結(jié)果如表2 和圖3 所示，對于每個測試函數(shù)，其平均值反映了在相同種群規(guī)模和迭代次數(shù)下每種算法所達到的解的精度，標準方差反映了每種算法的魯棒性和穩(wěn)定性。

表1 算法測試函數(shù)

表2 FOA算法與MFOA算法的性能比較

從表2 可得出，對四個測試函數(shù)，相比FOA 算法和SA-FOA［14］算法，本文提出的改進后的FOA 算法都能找到或者更接近于理論最優(yōu)值，其求解得到的最差值、最優(yōu)值、平均值和標準方差均優(yōu)于FOA算法和SA-FOA［14］算法，改進后的FOA對函數(shù)f1(x)的尋優(yōu)精度相比FOA 高出了100多個數(shù)量級；改進后的FOA 對函數(shù)f2(x)和f3(x)尋優(yōu)成功率（尋優(yōu)成功率=找到最優(yōu)值的運行次數(shù)/總的運行次數(shù)）能達到100%；對于復雜結(jié)構(gòu)的f4(x)，改進后的FOA的尋優(yōu)精度也是較高。對比三種算法20 次運行后的平均值和標準方差，可以得出，改進后的FOA 的平均值要遠遠低于FOA 和SA-FOA［14］算法，更接近或者等于理論最優(yōu)解；除此之外，改進后的FOA 的方差較低。因此，本文算法搜索最優(yōu)值的能力更強，解的精度更高，更具有較好的魯棒性。

圖3 顯示了的三種算法的優(yōu)化測試曲線。從圖3 中可以看出，在迭代次數(shù)為200 時，改進后的FOA 比傳統(tǒng)FOA 以及SA-FOA［14］算法的收斂速度都更快（接近最優(yōu)解時FOA 迭代次數(shù)大約100、97、80、110；改進后的FOA 迭代次數(shù)大約為7、8、6、12；SA-FOA［14］迭代次數(shù)大約為48、48、24、60），并且尋優(yōu)精度比其他兩種算法要高出很多。由圖3 中的（a）、（b）和（c）可以得出，三種算法對單峰函數(shù)和多峰函數(shù)具有較好的尋優(yōu)效果，但是改進后的FOA算法效果更優(yōu)；雖然對于結(jié)構(gòu)相對復雜的多峰函數(shù)，三種算法都沒有達到與另外幾個函數(shù)一樣的尋優(yōu)結(jié)果。然而，改進的FOA 算法尋優(yōu)精度和收斂速度仍然優(yōu)于其他兩種算法。因此，本文算法能夠更好地跳出局部極值，具有更高的收斂精度和更強的尋優(yōu)性能。

4.2.2 算法性能分析

算法的效率指的是算法的執(zhí)行時間隨問題規(guī)模的大小增加而增長的趨勢。改進算法是否有效、可行，除了提高尋優(yōu)性能，其自身的時間復雜度也應該更低。由于任何一個算法都包括控制結(jié)構(gòu)和許多原操作，因此從算法中選擇作為所研究問題的基本操作的原始操作在算法中的執(zhí)行次數(shù)為依據(jù)。FOA算法中，主要是測試函數(shù)的維數(shù)影響著算法的時間復雜度。選用以上三個測試函數(shù)（f1(x)是單峰函數(shù)）對本文算法的時間復雜度進行測試并分析，設置種群規(guī)模為30，迭代次數(shù)為200，獨立運行20 次，計算兩種算法在不同維數(shù)（200 維數(shù)，400維數(shù)，600 維數(shù)）所需要的平均運行時間，仿真結(jié)果如表3所示。

圖3 兩種算法的優(yōu)化曲線

表3 算法平均運行時間對比

從表3 的平均運行時間可以得出結(jié)論，改進算法的平均運行時間只比傳統(tǒng)的FOA 算法稍長一點，因此本文改進的FOA 算法復雜都較低，是可行有效的。

4.3 與其他算法性能對比

為測試本文算法與其他算法的性能優(yōu)劣，本文將改進后的FOA 與其他幾種算法的優(yōu)化均值進行了對比，文獻中的基于模擬退火的果蠅優(yōu)化算法［14］（SA-FOA）、文獻中的自適應調(diào)整參數(shù)的果蠅優(yōu)化算法［15］（FOAAP）、文獻自適應混沌果蠅優(yōu)化算法［16］（ACFOA）和文獻中的自適應變異的果蠅優(yōu)化算法［17］（DDSCFOA），對以上四個測試函數(shù)的性能進行比較，迭代次數(shù)為2000，種群規(guī)模為30，獨立運行次數(shù)20后取平均值，其運行結(jié)果如表4所示。

首先將本文算法比參考文獻中的其他算法提高很大，對于函數(shù)f1(x)、f2(x)和f3(x)，本文算法能收斂到理論全局最小值；對于函數(shù)f4(x)，本文算法平均最優(yōu)值優(yōu)于其他算法，最多相差13 個數(shù)量級。綜上所述，本文算法在實驗條件（種群數(shù)、迭代次數(shù)等）一致的情況下，本文算法的平均優(yōu)化值要好于參考文獻中的算法。因此，與參考文獻算法相比，本文算法具有更強的搜索復雜函數(shù)的能力，且具有較好的全局搜索能力。

5 結(jié)語

果蠅優(yōu)化算法屬于演化式計算的范疇，相比其他群智能算法，F(xiàn)OA算法原理簡單，計算速度快，易于實現(xiàn)。本文針對傳統(tǒng)果蠅算法尋優(yōu)精度不高、收斂速度較慢且易于陷入局部最優(yōu)的特點，提出了基于輪盤賭反向選擇機制的果蠅優(yōu)化算法，通過提高其種群多樣性來提高其求解問題時的全局尋優(yōu)能力。仿真實驗表明，與參考文獻中的其他果蠅優(yōu)化算法相比，改進后的FOA 算法在一元函數(shù)和多元函數(shù)的最優(yōu)化實例中收斂速度和精度都大大提高，且不易陷入局部最優(yōu)，可作為求解各類優(yōu)化問題的實用高效的智能方法，本文算法有效、可行。

表4 MFOA算法與其他算法的性能對比表