摘 要： 針對基本果蠅優(yōu)化算法在求解高維函數(shù)時存在求解精度低、迭代收斂速度較慢等問題,，提出一種基于差分演化的果蠅優(yōu)化算法,。該算法將差分演化策略融合到果蠅優(yōu)化算法中，對每代產(chǎn)生的群體進行變異,、交叉,、選擇操作，增加種群的多樣性,，使其能更快,、更有效地求解高維函數(shù)問題。對12個基準函數(shù)進行了仿真驗證,，結(jié)果表明,，與基本的果蠅優(yōu)化算法和差分演化算法相比，新算法在收斂速度,、求解精度上都具有明顯的優(yōu)越性,。
關(guān)鍵詞： 果蠅優(yōu)化算法；差分演化,；多樣性
0 引言
果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm,，F(xiàn)OA）是一種新的全局優(yōu)化進化算法[1]。該算法源于對果蠅覓食行為的模擬[2],，由于該算法參數(shù)較少,，結(jié)構(gòu)簡單，實現(xiàn)容易,，因而一經(jīng)提出便得到了一些學(xué)者的研究和應(yīng)用[3-6],。然而，果蠅優(yōu)化算法和其他全局優(yōu)化算法一樣,，受參數(shù)的影響很大,，也容易陷入局部最優(yōu)。目前關(guān)于改善果蠅優(yōu)化算法性能的研究成果相對較少,，迫切需要展開更深入研究,。
果蠅優(yōu)化算法中所有個體都向最優(yōu)的位置聚集,，這一行為導(dǎo)致種群多樣性的丟失，特別是對于高維多極值復(fù)雜優(yōu)化問題,，易出現(xiàn)求解精度低,、迭代收斂速度較慢等問題。針對這一問題,，本文將差分演化策略融合到果蠅優(yōu)化算法中,，對每代產(chǎn)生的群體進行若干次的變異、交叉,、選擇操作,，從而增加種群的多樣性，使其更快,、更有效地求解復(fù)雜函數(shù)問題,。
1 基本果蠅優(yōu)化算法和差分進化算法
1.1 基本的果蠅優(yōu)化算法
果蠅優(yōu)化算法是一種基于果蠅覓食行為推演出的尋求全局優(yōu)化的新方法。果蠅本身在感官知覺上優(yōu)于其他物種,，尤其是在嗅覺與視覺上,。首先果蠅利用嗅覺搜集空氣中的氣味，然后飛向食物位置附近,，再利用視覺發(fā)現(xiàn)食物與同伴聚集的位置,，并且往該方向飛去。
依據(jù)果蠅搜索食物特性,，將果蠅優(yōu)化算法歸納為以下幾個必要的步驟[2]：
?。?）初始化種群。給定種群規(guī)模Sizepop和最大迭代數(shù)Maxgen,，在搜索空間中隨機初始化果蠅群體位置X_axis和Y_axis,；
（2）設(shè)置果蠅個體利用嗅覺搜尋食物的隨機方向與距離：
Xi=X_axis+RandValue（1）
Yi=Y_axis+RandValue（2）
式中,，RandValue為搜索距離,。
（3）計算個體與原點之距離Disti和味道濃度判定值Si,，其值為距離Disti的倒數(shù)：
Si=1/Disti（4）
?。?）將味道濃度判定值Si代入味道濃度判定函數(shù)（或稱為適應(yīng)度函數(shù)），求出果蠅個體位置的味道濃度Smell（i）（適應(yīng)值）：
Smell（i）=Function（Si）（5）
?。?）找出該果蠅群體中味道濃度最佳的果蠅個體（最小化問題）：
[bestSmell bestindex]=min（Smell（i））（6）
式中,，bestSmell為最佳味道濃度值,；bestindex為最佳位置序列,。
（6）記錄并保留最佳味道濃度值bestSmell與其X,、Y坐標,，這時果蠅群體利用視覺向該位置飛去：
Smellbest=bestSmell（7）
X_axis=X（bestindex）（8）
Y_axis=Y（bestindex）（9）
?。?）進入迭代尋優(yōu)，重復(fù)執(zhí)行步驟（2）～（5）,，并判斷最佳味道濃度是否優(yōu)于前一迭代最佳味道濃度且當前迭代次數(shù)小于最大迭代次數(shù),，若是則執(zhí)行步驟（6）。
1.2 差分進化算法
差分進化（Differential Evolution,，DE）算法[7]是一種隨機的并行直接搜索算法,。其基本原理：對個體進行方向擾動，以達到使個體函數(shù)值下降的目的,。通過對種群中兩個隨機選擇的不同向量來干擾現(xiàn)有向量,，得到臨時種群；對臨時種群進行評價,，計算臨時種群中每個個體的目標函數(shù)值,；對臨時種群進行比較、選擇,，選取目標函數(shù)值小的新種群,。DE算法以差分策略為主要特征，不同的差分策略實現(xiàn)不同的變異操作,。本文選取rand/1/bin策略,。如下所示：
（1）變異操作,。選取rand/1/bin策略,。從種群中隨機選擇3個不同個體xp，xq,，xr,，則：
vi（t）=xp+F（xq-xr）（10）
式中，F(xiàn)為縮放因子,。
?。?）交叉操作。此操作可以增加種群的多樣性,。如下所示：
式中,，CR為交叉概率，CR∈[0,，1],；rand（1，n）為[1,，n]之間的隨機整數(shù),。
（3）選擇操作,。由適應(yīng)值函數(shù)對向量進行比較選擇,，如下所示：
2 融合差分算法的混合果蠅算法
在果蠅優(yōu)化算法迭代過程中,，一旦發(fā)現(xiàn)最優(yōu)個體，種群中的所有個體都向這個最優(yōu)位置聚攏,，這一特性減少了種群的多樣性,。如果該個體不是全局最優(yōu)，極易使種群陷入局部最優(yōu),。本文提出的融合差分演化的混合果蠅算法（簡稱DFOA）,，結(jié)合差分演化策略，對每代產(chǎn)生的群體進行若干次差分演化操作（變異,、交叉,、選擇），增加種群的多樣性,，更快,、更有效地求解極值。
具體步驟如下：
?。?）初始化算法所需的參數(shù),；
（2）按式（1）,、（2）初始化果蠅群體,；
（3）按式（3）~（5）對果蠅個體進行操作,；
?。?）按照式（6）得到最佳的果蠅位置和最佳味道濃度值；
?。?）對果蠅種群按照式（12）~（14）進行m代的差分演化操作,，將得到的個體作為最佳果蠅個體；
?。?）記錄并保留新的最佳味道濃度值Smellbest與X,、Y的坐標X_axis、Y_axis,。
?。?）重復(fù)執(zhí)行步驟（2）~（6）的操作，直到達到最大迭代次數(shù),，或者達到目標精度要求,。
從步驟（5）中可以知道，差分演化代數(shù)m可以不同,。種群中差分進化代數(shù)m表明執(zhí)行變異,、交叉、選擇操作的次數(shù),，這些操作決定了種群的變異次數(shù),，與種群的多樣性有關(guān)。
3 實驗及結(jié)果分析
3.1 實驗設(shè)計
為了驗證本文DFOA算法的性能,，設(shè)計了3類測試函數(shù)：（1）DE優(yōu)化實驗,；（2）DFOA優(yōu)化實驗；（3）FOA優(yōu)化實驗,。實驗選用12個常用的優(yōu)化算法比較基準函數(shù)（求解最小值）,。函數(shù)表達式、搜索區(qū)間,、理論極值如表1所示,。其中F7、F10表達式如下所示：
3.2 對比實驗與結(jié)果分析
3.2.1固定迭代次數(shù),，評估算法性能
本文將迭代次數(shù)固定為1 000,，函數(shù)維數(shù)為30，種群個數(shù)設(shè)置為50,，差分迭代次數(shù)為10,。參數(shù)F取為0.5，CR取為0.1~0.9之間的自適應(yīng)交叉概率,。記錄DE,、FOA和DFOA三種算法經(jīng)過20次獨立運行后，12個基準測試函數(shù)的運行結(jié)果,，如表2所示,。
從表2中可以看出，DFOA不論是在最優(yōu)值,、優(yōu)化均值和穩(wěn)定性上都比FOA和DE算法好很多,。對于復(fù)雜問題，改進的算法在精度,、收斂速度上都有顯著的提高,。
3.2.2 差分迭代次數(shù)對算法的影響
種群中差分進化代數(shù)m表明執(zhí)行變異、交叉,、選擇操作的次數(shù),，這些差分操作決定了種群的變異次數(shù)，與種群的多樣性有關(guān),，因此關(guān)系到DFOA的性能,。不同的差分迭代次數(shù)使算法的結(jié)果也不相同。參數(shù)的設(shè)置如上述所示,。獨立運行20次結(jié)果如表3所示,。
由表3可知，m值越大,，算法的收斂精度就越高,，但缺點是程序執(zhí)行的速度會變慢,。因此，必須考慮到優(yōu)化問題的復(fù)雜程度,，適當選擇m值,。
4 結(jié)束語
基本的果蠅優(yōu)化算法在尋優(yōu)過程中，所有個體都向最優(yōu)值聚攏,，這一行為導(dǎo)致種群多樣性的丟失,，特別是對于高維復(fù)雜優(yōu)化問題，易出現(xiàn)求解精度低,、迭代收斂速度較慢等問題,。針對這一問題，本文將差分演化策略融合到果蠅優(yōu)化算法中,，對每代產(chǎn)生的群體進行若干次差分演化操作,，增加種群的多樣性。并通過12個基準函數(shù)進行仿真驗證,，結(jié)果表明：相較于FOA,、DE，新算法能更快,、更有效地求解復(fù)雜函數(shù)問題,。
參考文獻
[1] PAN W T. A new fruit optimization algorithm： taking the financial distress model as an example[J]. Knowledge-Based Systems， 2012,，26（1）：69-74.
[2] 潘文超.果蠅最佳化演算法[M].臺北：滄海書局,，2011：10-12.
[3] XING Y F. Design and optimization of key control characteristics based on improved fruit fly optimization algorithm [J]. Kybernetes， 2013,， 42（3）： 466-481.
[4] LI H Z,， GUO S， Li C J,， et al. A hybrid annual power load forecasting model based on generalized regression neural network with fruit fly optimization algorithm[J]. Knowledge-based systems,，2013，37（1）：378-387.
[5] 劉成忠,，黃高寶,，張仁陟，等.局部深度搜索的混合果蠅優(yōu)化算法[J].計算機應(yīng)用,，2014（4）：1060-1064.
[6] 韓俊英,，劉成忠.自適應(yīng)調(diào)整參數(shù)的果蠅優(yōu)化算法[J].計算機工程與應(yīng)用，2014（7）：50-55.
[7] STORN R,， PRICE K. Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces[J]. Technical Report,， International Computer Science Institute， 1995（8）： 22-25.