摘  要： 針對基本果蠅優(yōu)化算法在求解高維函數(shù)時(shí)存在求解精度低、迭代收斂速度較慢等問題，提出一種基于差分演化的果蠅優(yōu)化算法。該算法將差分演化策略融合到果蠅優(yōu)化算法中，對每代產(chǎn)生的群體進(jìn)行變異、交叉、選擇操作，增加種群的多樣性，使其能更快、更有效地求解高維函數(shù)問題。對12個(gè)基準(zhǔn)函數(shù)進(jìn)行了仿真驗(yàn)證，結(jié)果表明，與基本的果蠅優(yōu)化算法和差分演化算法相比，新算法在收斂速度、求解精度上都具有明顯的優(yōu)越性。

　　關(guān)鍵詞： 果蠅優(yōu)化算法；差分演化；多樣性

0 引言

　　果蠅優(yōu)化算法（Fruit Fly Optimization Algorithm，F(xiàn)OA）是一種新的全局優(yōu)化進(jìn)化算法[1]。該算法源于對果蠅覓食行為的模擬[2]，由于該算法參數(shù)較少，結(jié)構(gòu)簡單，實(shí)現(xiàn)容易，因而一經(jīng)提出便得到了一些學(xué)者的研究和應(yīng)用[3-6]。然而，果蠅優(yōu)化算法和其他全局優(yōu)化算法一樣，受參數(shù)的影響很大，也容易陷入局部最優(yōu)。目前關(guān)于改善果蠅優(yōu)化算法性能的研究成果相對較少，迫切需要展開更深入研究。

　　果蠅優(yōu)化算法中所有個(gè)體都向最優(yōu)的位置聚集，這一行為導(dǎo)致種群多樣性的丟失，特別是對于高維多極值復(fù)雜優(yōu)化問題，易出現(xiàn)求解精度低、迭代收斂速度較慢等問題。針對這一問題，本文將差分演化策略融合到果蠅優(yōu)化算法中，對每代產(chǎn)生的群體進(jìn)行若干次的變異、交叉、選擇操作，從而增加種群的多樣性，使其更快、更有效地求解復(fù)雜函數(shù)問題。

1 基本果蠅優(yōu)化算法和差分進(jìn)化算法

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

　　果蠅優(yōu)化算法是一種基于果蠅覓食行為推演出的尋求全局優(yōu)化的新方法。果蠅本身在感官知覺上優(yōu)于其他物種，尤其是在嗅覺與視覺上。首先果蠅利用嗅覺搜集空氣中的氣味，然后飛向食物位置附近，再利用視覺發(fā)現(xiàn)食物與同伴聚集的位置，并且往該方向飛去。

　　依據(jù)果蠅搜索食物特性，將果蠅優(yōu)化算法歸納為以下幾個(gè)必要的步驟[2]：

　　（1）初始化種群。給定種群規(guī)模Sizepop和最大迭代數(shù)Maxgen，在搜索空間中隨機(jī)初始化果蠅群體位置X_axis和Y_axis；

　?。?）設(shè)置果蠅個(gè)體利用嗅覺搜尋食物的隨機(jī)方向與距離：

　　Xi=X_axis+RandValue（1）

　　Yi=Y_axis+RandValue（2）

　　式中，RandValue為搜索距離。

　?。?）計(jì)算個(gè)體與原點(diǎn)之距離Disti和味道濃度判定值Si，其值為距離Disti的倒數(shù)：

　　Si=1/Disti（4）

　　（4）將味道濃度判定值Si代入味道濃度判定函數(shù)（或稱為適應(yīng)度函數(shù)），求出果蠅個(gè)體位置的味道濃度Smell（i）（適應(yīng)值）：

　　Smell（i）=Function（Si）（5）

　　（5）找出該果蠅群體中味道濃度最佳的果蠅個(gè)體（最小化問題）：

　　[bestSmell bestindex]=min（Smell（i））（6）

　　式中，bestSmell為最佳味道濃度值；bestindex為最佳位置序列。

　?。?）記錄并保留最佳味道濃度值bestSmell與其X、Y坐標(biāo)，這時(shí)果蠅群體利用視覺向該位置飛去：

　　Smellbest=bestSmell（7）

　　X_axis=X（bestindex）（8）

　　Y_axis=Y（bestindex）（9）

　?。?）進(jìn)入迭代尋優(yōu)，重復(fù)執(zhí)行步驟（2）～（5），并判斷最佳味道濃度是否優(yōu)于前一迭代最佳味道濃度且當(dāng)前迭代次數(shù)小于最大迭代次數(shù)，若是則執(zhí)行步驟（6）。

　　1.2 差分進(jìn)化算法

　　差分進(jìn)化（Differential Evolution，DE）算法[7]是一種隨機(jī)的并行直接搜索算法。其基本原理：對個(gè)體進(jìn)行方向擾動，以達(dá)到使個(gè)體函數(shù)值下降的目的。通過對種群中兩個(gè)隨機(jī)選擇的不同向量來干擾現(xiàn)有向量，得到臨時(shí)種群；對臨時(shí)種群進(jìn)行評價(jià)，計(jì)算臨時(shí)種群中每個(gè)個(gè)體的目標(biāo)函數(shù)值；對臨時(shí)種群進(jìn)行比較、選擇，選取目標(biāo)函數(shù)值小的新種群。DE算法以差分策略為主要特征，不同的差分策略實(shí)現(xiàn)不同的變異操作。本文選取rand/1/bin策略。如下所示：

　?。?）變異操作。選取rand/1/bin策略。從種群中隨機(jī)選擇3個(gè)不同個(gè)體xp，xq，xr，則：

　　vi（t）=xp+F（xq-xr）（10）

　　式中，F(xiàn)為縮放因子。

　?。?）交叉操作。此操作可以增加種群的多樣性。如下所示：

　　式中，CR為交叉概率，CR∈[0，1]；rand（1，n）為[1，n]之間的隨機(jī)整數(shù)。

　?。?）選擇操作。由適應(yīng)值函數(shù)對向量進(jìn)行比較選擇，如下所示：

2 融合差分算法的混合果蠅算法

　　在果蠅優(yōu)化算法迭代過程中，一旦發(fā)現(xiàn)最優(yōu)個(gè)體，種群中的所有個(gè)體都向這個(gè)最優(yōu)位置聚攏，這一特性減少了種群的多樣性。如果該個(gè)體不是全局最優(yōu)，極易使種群陷入局部最優(yōu)。本文提出的融合差分演化的混合果蠅算法（簡稱DFOA），結(jié)合差分演化策略，對每代產(chǎn)生的群體進(jìn)行若干次差分演化操作（變異、交叉、選擇），增加種群的多樣性，更快、更有效地求解極值。

　　具體步驟如下：

　?。?）初始化算法所需的參數(shù)；

　?。?）按式（1）、（2）初始化果蠅群體；

　?。?）按式（3）~（5）對果蠅個(gè)體進(jìn)行操作；

　　（4）按照式（6）得到最佳的果蠅位置和最佳味道濃度值；

　?。?）對果蠅種群按照式（12）~（14）進(jìn)行m代的差分演化操作，將得到的個(gè)體作為最佳果蠅個(gè)體；

　?。?）記錄并保留新的最佳味道濃度值Smellbest與X、Y的坐標(biāo)X_axis、Y_axis。

　　（7）重復(fù)執(zhí)行步驟（2）~（6）的操作，直到達(dá)到最大迭代次數(shù)，或者達(dá)到目標(biāo)精度要求。

　　從步驟（5）中可以知道，差分演化代數(shù)m可以不同。種群中差分進(jìn)化代數(shù)m表明執(zhí)行變異、交叉、選擇操作的次數(shù)，這些操作決定了種群的變異次數(shù)，與種群的多樣性有關(guān)。

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

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

　　為了驗(yàn)證本文DFOA算法的性能，設(shè)計(jì)了3類測試函數(shù)：（1）DE優(yōu)化實(shí)驗(yàn)；（2）DFOA優(yōu)化實(shí)驗(yàn)；（3）FOA優(yōu)化實(shí)驗(yàn)。實(shí)驗(yàn)選用12個(gè)常用的優(yōu)化算法比較基準(zhǔn)函數(shù)（求解最小值）。函數(shù)表達(dá)式、搜索區(qū)間、理論極值如表1所示。其中F7、F10表達(dá)式如下所示：

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

　　3.2.1固定迭代次數(shù)，評估算法性能

　　本文將迭代次數(shù)固定為1 000，函數(shù)維數(shù)為30，種群個(gè)數(shù)設(shè)置為50，差分迭代次數(shù)為10。參數(shù)F取為0.5，CR取為0.1~0.9之間的自適應(yīng)交叉概率。記錄DE、FOA和DFOA三種算法經(jīng)過20次獨(dú)立運(yùn)行后，12個(gè)基準(zhǔn)測試函數(shù)的運(yùn)行結(jié)果，如表2所示。

　　從表2中可以看出，DFOA不論是在最優(yōu)值、優(yōu)化均值和穩(wěn)定性上都比FOA和DE算法好很多。對于復(fù)雜問題，改進(jìn)的算法在精度、收斂速度上都有顯著的提高。

　　3.2.2 差分迭代次數(shù)對算法的影響

　　種群中差分進(jìn)化代數(shù)m表明執(zhí)行變異、交叉、選擇操作的次數(shù)，這些差分操作決定了種群的變異次數(shù)，與種群的多樣性有關(guān)，因此關(guān)系到DFOA的性能。不同的差分迭代次數(shù)使算法的結(jié)果也不相同。參數(shù)的設(shè)置如上述所示。獨(dú)立運(yùn)行20次結(jié)果如表3所示。

　　由表3可知，m值越大，算法的收斂精度就越高，但缺點(diǎn)是程序執(zhí)行的速度會變慢。因此，必須考慮到優(yōu)化問題的復(fù)雜程度，適當(dāng)選擇m值。

4 結(jié)束語

　　基本的果蠅優(yōu)化算法在尋優(yōu)過程中，所有個(gè)體都向最優(yōu)值聚攏，這一行為導(dǎo)致種群多樣性的丟失，特別是對于高維復(fù)雜優(yōu)化問題，易出現(xiàn)求解精度低、迭代收斂速度較慢等問題。針對這一問題，本文將差分演化策略融合到果蠅優(yōu)化算法中，對每代產(chǎn)生的群體進(jìn)行若干次差分演化操作，增加種群的多樣性。并通過12個(gè)基準(zhǔn)函數(shù)進(jìn)行仿真驗(yàn)證，結(jié)果表明：相較于FOA、DE，新算法能更快、更有效地求解復(fù)雜函數(shù)問題。

參考文獻(xiàn)

　　[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].計(jì)算機(jī)應(yīng)用，2014（4）：1060-1064.

　　[6] 韓俊英，劉成忠.自適應(yīng)調(diào)整參數(shù)的果蠅優(yōu)化算法[J].計(jì)算機(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.