一種基于步長指數遞減策略的果蠅優化算法

秋興國，黃潤青

（西安科技大學計算機科學與技術學院，陜西西安 710054）

果蠅優化算法是潘文超[1]于2011 年提出的一種新型演化式群體優化算法[2]，該算法模型的構建是基于果蠅覓食行為的仿生學原理[3]，目的是尋找全局最優值，與其他算法相比具有參數少、易于實現和局部搜索能力強[4]等優點，但它同時具有收斂速度慢、不夠穩定、易陷入局部最優等局限性[5]。為提高傳統果蠅算法的性能，文獻[6]提出了一種融合變異機制的果蠅優化算法，通過使位于種群中心的個體進行變異操作來避免算法易陷入局部極優值的情況；文獻[7]提出的果蠅優化算法融合了模擬退火的思想，使用非均勻變異的思想優化果蠅迭代步長，使算法收斂速度和精度得到了提高；文獻[8]將萊維飛行和反向學習引入果蠅算法中，通過對果蠅個體進行位置更新來控制算法的收斂速度和精度。

文中提出一種基于t分布及自適應步長策略的果蠅優化算法(TEFOA)，該算法從種群位置初始化、果蠅位置更新兩個方面來進行優化。通過t分布對果蠅位置更新時進行位置擾動，使種群具有更加隨機的特點，引入指數遞減步長調整因子，優化了原有算法的位置更新方式。對5 個經典性能函數進行仿真測試，結果表明，提出的果蠅優化算法有較好的收斂速度收斂精度，降低了算法陷入局部極值的可能性。

1 果蠅算法基本介紹

果蠅優化算法是一種演化式群智能優化算法，是基于果蠅覓食行為提出的。果蠅在嗅覺和視覺[9]上的敏感性優于其他物種。在覓食過程中，每個果蠅個體攜帶有食物味道濃度，在算法中將果蠅個體與原點位置距離的倒數作為味道濃度判定的方法[10]，果蠅群體中所有個體朝味道濃度最優的果蠅個體位置飛去[11]，該味道濃度最優的果蠅個體位置作為下一次迭代尋優過程中果蠅種群的初始位置，通過數次迭代，不斷更新果蠅群體的最優位置，直到得出最優解或達到最大迭代次數[12]。圖1 顯示了果蠅搜尋食物的邏輯迭代過程。

圖1 果蠅群體進化圖

根據果蠅覓食過程中的行為特點，將標準的果蠅優化算法歸納為以下步驟[13]：

1）初始化相關參數，主要包括果蠅種群規模(Sizepop)、群體最大迭代次數(Maxgen)、果蠅個體初始位置X-axis、Y-axis，并進行群體位置初始化，其中rand()表示[0,1]間的隨機數。

2）確定初始果蠅群體中果蠅個體位置和方向。RValue為果蠅隨機搜索距離和方向的隨機數。

3）利用每個果蠅個體位置坐標與原點的距離Di來計算其味道濃度判定值Si，Si為距離Di的倒數。

4）將味道濃度判定值Si代入適應度函數判定函數[14](或稱為適應度函數，Fitness function)，該函數是為了計算該種群中果蠅個體的味道濃度Smell(i)。

5）找出種群當前味道濃度最優的果蠅個體位置，記錄其坐標和味道濃度值。

6）記錄最優味道濃度值及對應的橫縱坐標，此時群體果蠅根據視覺向最優個體位置飛去，形成新的果蠅群體。

7）迭代尋優階段，重復執行步驟2)～步驟5)，判斷當前迭代次數是否小于最大迭代次數，當前味道濃度是否優于所記錄的最優味道濃度，若成立，執行步驟6)。

2 改進的FOA算法(TEFOA)

2.1 指數遞減步長

搜索步長是決定FOA 算法搜索能力的關鍵因素。由指數函數確定的自適應步長在初期迭代搜索時，可在較大范圍內展開全局搜索，這有利于跳出局部最優解[15]，加快算法的收斂速度，降低運行時間；隨著迭代次數的增加，在算法運行后期，由于已經步入了有潛力的搜索區域，只需要在區域內進行局部搜索，即設置較小的搜索步長在當前搜索區域進行精細搜索[16]。受文獻[9]的啟發，用指數遞減策略對果蠅算法進行優化。所使用的指數遞減策略表達式為：

其中，wmax、wmin分別表示w的最大值和最小值，取wmax=1，wmin=0.4[13]；t表示當前迭代次數；tmax為最大迭代次數；參數c取值與文獻[9]保持一致，即c=10。該函數圖像如圖2 所示，在果蠅算法迭代尋優初期，w隨迭代次數的增加以較快的速率下降，可使果蠅個體在初期能夠保持一個較大的搜索步長。該算法搜索能力較強，為避免出現算法陷入局部極優值的情況[17]。在算法迭代尋優后期，當迭代次數逐漸增加時，w以非線性的動態逐步減小，搜索步長變小，可以進行精細搜索。這不僅能夠避免因步長較大而跳過最優解的可能性[18]，而且還提高了算法后期的收斂精度和時間效率[19]。

圖2 指數遞減因子的變化曲線

指數遞減結合果蠅算法的具體公式下，其中t(Iteration)為變異策略。

2.2 t變異策略

1908 年，威廉·戈塞[20]首先推導出t分布。t分布圖像形態與n(自由度)有關。自由度越小，t分布的曲線愈平坦，曲線中間越低，曲線雙側尾部越高。自由度n=1 時，t分布的曲線為柯西分布曲線，即t(n=1)=C(0,1)，C(0,1)為柯西分布；自由度越大，t分布的曲線越接近正態分布曲線[21]；自由度n→∞時，t分布的曲線近似為高斯分布曲線[22]，即t(n→∞)→N(0,1)，其中N(0,1)為高斯分布。即t分布的兩個特殊情況[23]是柯西分布和高斯分布。t分布的自由度分布曲線如圖3所示，在算法優化中，t分布自由度的取值為當前迭代次數。

圖3 t分布曲線圖

3 仿真實驗及結果分析

3.1 測試函數驗證

為了檢驗算法的有效性，選取了5 個經典性能測試函數對標準果蠅算法和文中優化算法在相同環境下進行Matlab 仿真實驗對比(求最小值)，所選函數均有不同特性，使用這些函數進行測試所得的實驗結果可以全面地反映算法的性能，更具有說服力。

實驗中所采用的經典測試函數如表1 所示。

3.2 固定迭代次數下實驗仿真分析

在測試函數過程中，借助Matlab 2016a 平臺，設置迭代次數為1 500 次，種群規模為20，算法獨立重復實驗50 次。為了使測試結果更具有說服力，選取FOA、LGMS-FOA[24]、TEFOA 這3 種算法進行同條件測試，記錄實驗過程中的平均值、標準差和測試函數最優值作為評價標準。實驗中所采用的標準測試函數如表1 所示，實驗結果如表2 所示，其中Mean 表示函數的平均值，Std 表示函數的標準差，Best 表示函數可達到的最優值，并繪制迭代次數增加時適應度值的變化曲線。

表1 測試函數

表2 測試結果表

測試函數的變化曲線如圖4～8 所示。

圖4 Sphere函數變化曲線

圖5 Griewank函數變化曲線

圖6 Rastrigin函數變化曲線

4 結束語

圖7 Schaffer函數變化曲線

圖8 Sum Squares函數變化曲線

通過對實驗結果進行分析可知，盡管函數對于不同的算法有著不同的尋優精度，但在5 種標準函數的測試中，文中優化算法比標準FOA 算法的運算精度均有不同程度的提高。所以，提出的TEFOA 算法優于傳統的FOA 算法，尤其是在Rastrigin 和Schaffer 兩個測試函數上表現優異，在迭代過程中訓練得出的最優值均可達到函數本身的最優值；另外，從適應度值的變化曲線可以看出，平均迭代不到500次就可獲得最優值，TEFOA 算法的收斂速度優于傳統的FOA 算法，收斂速度得到了較大的提高。這充分說明了文中的改進算法具有更高的收斂精度、更優的搜索能力和更快的收斂速度，在一定程度上也可以避免局部最優[25-26]。

FOA 算法是近年來提出的種群智能優化算法，但傳統的果蠅算法存在著局限性和不足之處，如難以跳出局部最優值、收斂緩慢、精確度不高等。文中考慮到這些方面的問題，在優化算法中對果蠅算法的移動步長部分作了指數調整策略，即在迭代的初期階段保留了算法較大的搜索步長，也保留了迭代后期算法的精細搜索能力；并在果蠅位置更新時添加擾動策略，避免算法難以跳出局部最優解。經Matlab 平臺對標準函數進行測試實驗，結果表明，文中的算法改進使得算法易陷入局部最優和收斂速度慢的不足得到了優化，并提高了求解效率。接下來的任務是將改進算法應用于實際問題，驗證解決實際問題的能力。