摘  要： 針對基本果蠅優化算法（FOA）收斂速度慢和尋優精度不高的缺點，在位置更新公式中引入加權因子，提出了基于線性遞減策略和先增后減策略的兩種加權果蠅優化算法（WFOA），從而增強了種群的多樣性。通過對6個測試函數的仿真實驗，驗證了這些策略的可行性，表明這些策略能夠有效地提高算法的收斂速度和搜優精度。經過兩種策略的對比，發現線性遞減策略具有更快的收斂速度，而先增后減策略具有更強的魯棒性和稍好的尋優精度。

　　關鍵詞： 加權因子；果蠅優化算法；線性遞減策略；先增后減策略

　　果蠅優化算法FOA（Fruit Fly Optimization Algorithm）是由臺灣博士潘文超于2011年提出的，與蟻群算法和粒子群算法類似，是基于動物群體覓食行為演化出的一種尋求全局優化的新方法[1-3]。它不同于順序執行的傳統智能算法，而是以果蠅群體自組織性和并行性為基礎，構造出的一種動物自治體模型。FOA有著算法簡單、控制參數少、容易實現、且具有一定并行性等特點，因此在各領域得到廣泛應用[4]。FOA可以優化神經網絡參數，已成功應用于企業經營績效評估、外貿出口預測、原油含水率預測等[3，5-6]；FOA也可優化支持向量機模型，已成功應用于故障診斷、物流需求量預測等[7-8]。但由于FOA是較晚提出的一種隨機搜索算法，其在理論分析和應用研究等方面還處于初級階段，同時也存在易發散、收斂精度不高等缺點。

　　本文針對FOA收斂速度慢、收斂精度低等缺點，提出了加權果蠅優化算法WFOA（Weighted Fruit Fly Optimization Algorithm），進而對幾種不同加權策略下的果蠅優化算法進行了對比研究。

1 果蠅優化算法及其改進

　　1.1 果蠅優化算法

　　FOA在計算方法上類似于遺傳算法，但不同的是FOA不使用雜交和變異等算子，而是通過模仿果蠅特殊的嗅覺和視覺特點來進行搜索。果蠅的嗅覺器官能很好地搜集飄浮在空氣中的各種氣味，甚至能嗅到幾十公里以外的食物源。然后飛近食物位置，使用敏銳的視覺發現食物與同伴聚集的位置，并且往該方向飛去[2]。

　　根據果蠅搜索食物的特性，將果蠅優化算法歸納為以下幾個必要的步驟[1-3]：

　　（1）給定群體規模Sizepop，最大迭代次數Maxgen，隨機初始化果蠅群體位置X_axis，Y_axis；

　　（2）賦予果蠅個體利用嗅覺搜尋食物的方向與距離：

　　Xi=X_axis+Random ValueYi=Y_axis+Random Value（1）

　　（3）由于無法得知食物位置，因此先估計與原點的距離Disti，再計算味道濃度判定值Si，此值為距離的倒數：

　　Si=1/Disti（3）

　　（4）將味道濃度判定值代入味道濃度判定函數（或稱為適應度函數Fitness Function），以求出果蠅個體的味道濃度Smelli：

　　Smelli=Function（Si）（4）

　　（5）找出該果蠅群體中味道濃度最佳的果蠅（求極小值）：

　　[bestSmell bestindex]=min（Smelli）（5）

　　（6）記錄并保留最佳味道濃度值bestSmell與其X、Y坐標，此時果蠅群體利用視覺向該位置（Fly2）飛去，形成新的群聚位置：

　　Smellbest=bestSmellX_axis=X（bestindex）Y_axis=Y（bestindex）（6）

　　（7）進入迭代尋優，重復執行步驟（2）~步驟（5），并判斷最佳味道濃度是否優于前一迭代最佳味道濃度，前提是當前迭代次數小于等于Maxgen，若是則執行步驟（6）。

　　1.2 加權果蠅優化算法（WFOA）

　　在FOA中，每個果蠅個體在n維搜索空間中通過適應度函數來衡量個體的優劣，當種群完成一次迭代后，與群體的歷史最佳位置比較得出新的最佳位置，進而在新最佳位置附近繼續隨機尋優。由式（1）可以看出，迭代搜索始終在以當前最優位置為中心，以隨機飛行方向與距離Random Value為半徑的領域內展開，果蠅群體被限定在過分狹小的搜索范圍內，降低了種群的多樣性[9]。受PSO（粒子群算法）的慣性權重啟發[10-11]，在迭代位置更新公式中引入加權因子w，將式（1）變更如下，其他步驟不變。

　　Xi=w×X_axis+Random ValueYi=w×Y_axis+Random Value（7）

　　在迭代尋優過程中，希望前期具有較強的“探索”能力，即較強的全局搜索能力，以得到合適的種子，而在迭代后期，應具有較強的“開發”能力，即較強的局部搜索能力，從而展開精細的局部搜索。前期具有較大的值，一方面是對自己“歷史經驗”的認可，能夠充分利用果蠅個體本身的歷史記憶；另一方面使得個體搜索的區域范圍變大，讓果蠅個體在更廣的可行域里進行搜索，整個群體找到最優解的概率就大，相應的全局搜索能力就強。隨著迭代進行到后期，需要較小的w值，使其可搜索的范圍相對縮小，這時主要根據隨機飛行方向與距離Random Value，在“以往經驗”尋到的最優解附近進行小范圍精細搜索。

　　1.3 加權因子的幾種調整策略

　　策略1 線性遞減

　　w1=Wmax-（Wmax-Wmin）/Maxgen×g（8）

　　策略2 先增后減

　　令d=g/Maxgen，則有：

　　w2=d+1，        0≤d≤0.4w2=-7/6×d+28/15，0.4≤d≤1（9）

　　其中，g為當前迭代數，Maxgen為最大迭代數，Wmax為最大加權因子，Wmin為最小加權因子。對于策略1，經過實驗仿真，分別確定Wmax、Wmin為1.4、0.7的最佳權值范圍，隨著迭代數的變化，權值從1.4線性遞減到0.7，具體參數設置見式（8）。對于策略2，從第一次迭代開始到第Maxgen的40%代，權值從1線性遞增到1.4，而從Maxgen的40%代直至迭代結束，權值從1.4線性遞減到0.7，具體參數設置見式（9），兩種策略隨迭代的權值變化如圖1所示。

　　由式（8）和圖1可看出，策略1在進化初期具有很強的全局搜索能力。如果在初期能搜索到最好點，可在迭代前期達到快速收斂。由式（9）和圖1可看出，策略2在迭代開始至Maxgen的40%期間，全局搜索能力逐漸增強，而從Maxgen的40%到結束期間，其全局搜索能力逐漸減弱。由此可知，在沒有陷入局部極值的情況下，策略1比策略2應該具有更快的收斂速度。

2 實驗仿真及結果分析

　　2.1 實驗設計

　　為了測試w0-FOA、w1-FOA、w2-FOA算法的尋優性能，本文選用6個常用于優化算法比較的基準函數，函數形式、搜索區間、理論極值和目標精度如表1所示[4]。其中w0-FOA是w取固定值1，即基本FOA算法。具體參數設置為：群體規模Sizepop=30，最大迭代數Maxgen=1 000；隨機初始化果蠅群體位置為表1中各函數的搜索區間；迭代的果蠅搜尋食物的隨機飛行方向與距離區間為[-1，1]。測試軟件平臺為Windows7、MATLAB 2012b，機器主頻為2.5 GHz，內存為2 GB。

　　2.2 實驗結果與分析

　　6個測試函數在固定迭代數為1 000次，分別采用w0-FOA、w1-FOA和w2-FOA經過20次獨立運行后的標準差、優化均值和最好解如表2~表7所示；6個測試函數在表1中指定的目標精度下經過20次獨立運行后的平均迭代次數和達優率亦見表2~表7。其中，平均迭代數是達到目標精度的迭代數平均值，達優率為達到目標精度的運行次數與總實驗次數之比。圖2是6個測試函數適應度對數值進化曲線（注：為了方便進化曲線的顯示和觀察，本文對函數的適應度取以10為底的對數）。

　　從表2、3、7可以看出，w0-FOA對f1、f2、f6未能達到目標精度，而w1-FOA和w2-FOA都能100%達到目標精度，并且改進算法的收斂精度與w0-FOA的收斂精度相差11個數量級以上。從表6可以看出，雖然3種策略對f5均未達到指定的目標精度，但是w1-FOA和w2-FOA找到的最好解要比w0-FOA找到的優。而從表5可以看出，w1-FOA的均值和魯棒性是其中最好的，w2-FOA和w0-FOA的優化均值相差不大，但是w2-FOA找到的最好解要比w0-FOA找到的最好解優11個數量級。其中效果不太好的是f3函數，因為此函數的全局最優點隱藏在一條狹長的通道中，對外提供很少的信息，使算法很難辨別搜索方向，WFOA的優勢體現不出。

　　由圖2和表2~表7可看出，w1-FOA最多只需28.70次迭代就能達到目標精度（除f5），w2-FOA也最多只需136.60次迭代就可達到目標精度（除f5），由此可見，WFOA對收斂速度的影響非常顯著。

　　本文提出的WFOA算法在引入加權因子的基礎上，對粒子群算法中的線性遞減策略和先增后減策略公式進行了適當的參數調整，經測試函數驗證發現，總體上改進算法比原算法具有更快的收斂速度和更好的收斂精度，但w1-FOA比w2-FOA具有更快的收斂速度，而w2-FOA具有更強的魯棒性和稍好的尋優精度。值得注意的是，不同加權策略對收斂速度的影響非常明顯，如何正確選擇權值策略和適當參數，使收斂速度和收斂精度達到最佳平衡，是接下來需要研究的問題。

　　參考文獻

　　[1] PAN W T. A new fruit fly optimization algorithm： taking the financial distress model as an example[J]. Knowledge-based Systems， 2012，26：69-74.

　　[2] 潘文超.果蠅最佳化演算法[M].臺北：滄海書局，2011.

　　[3] 潘文超.應用果蠅優化算法優化廣義回歸神經網絡進行企業經營績效評估[J].太原理工大學學報（社會科學版），2011，29（4）：1-5.

　　[4] 韓俊英，劉成忠.基于細菌趨化的果蠅優化算法[J].計算機應用，2013，33（4）：964-966.

　　[5] 許智慧，王福林，孫丹丹，等.基于FOA_RBF神經網絡的外貿出口預測[J].數學的實踐與認識，2012，42（13）：14-19.

　　[6] 劉翠玲，張路路，王進旗，等.基于FOA—GRNN油井計量原油含水率的預測[J].計算機仿真，2012，29（11）：243-246.

　　[7] 張翔，陳林.基于果蠅優化算法的支持向量機故障診斷[J].電子設計工程，2013，21（16）：90-93.

　　[8] 李泓澤，郭森，李春杰.果蠅優化最小二乘支持向量機混合預測模型[J].經濟數學，2012，29（3）：103-106.

　　[9] 潘峰，李位星，高琪，等.粒子群優化算法與多目標優化[M].北京：北京理工大學出版社，2013.

　　[10] SHI Y， EBERHART R. Empirical study of particle swarm optimization[C]. International Conference on Evolutionary，Washington： USA，1999：1945-1950.

　　[11] 崔紅梅，朱慶保.微粒群算法的參數選擇及收斂性分析[J].計算機工程與應用，2007，43（23）：89-91.