張 靜 高 尚

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

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

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

2 果蠅算法

2.1 基本原理

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

2.2 算法過程

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

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

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

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

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

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

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

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

2.3 果蠅算法的不足

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

3 改進(jìn)后的果蠅算法

3.1 輪盤賭策略

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

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

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

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

3.2 改進(jìn)后的算法過程

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

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

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

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

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

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

Step6計(jì)算果蠅個(gè)體的味道濃度Smelli*：

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

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

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

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

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

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

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

種群規(guī)模為20時(shí)，迭代到71次達(dá)到1e-4精度，種群規(guī)模為30 時(shí)，迭代到64 次達(dá)到1e-4精度?？梢娫黾臃N群規(guī)模對(duì)其收斂速度改進(jìn)不大。

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

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

由圖2 可知，相比于FOA 算法和SA-FOA［14］算法，改進(jìn)后的FOA 算法經(jīng)過兩次迭代即可達(dá)到1e-4精度，收斂速度非?？欤介L(zhǎng)改進(jìn)效果明顯，且精度較高。

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

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

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

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

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

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

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

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

4.2.2 算法性能分析

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

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

表3 算法平均運(yùn)行時(shí)間對(duì)比

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

4.3 與其他算法性能對(duì)比

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

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

5 結(jié)語

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

表4 MFOA算法與其他算法的性能對(duì)比表