秋興國(guó)，黃潤(rùn)青

（西安科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西西安 710054）

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

文中提出一種基于t分布及自適應(yīng)步長(zhǎng)策略的果蠅優(yōu)化算法(TEFOA)，該算法從種群位置初始化、果蠅位置更新兩個(gè)方面來(lái)進(jìn)行優(yōu)化。通過(guò)t分布對(duì)果蠅位置更新時(shí)進(jìn)行位置擾動(dòng)，使種群具有更加隨機(jī)的特點(diǎn)，引入指數(shù)遞減步長(zhǎng)調(diào)整因子，優(yōu)化了原有算法的位置更新方式。對(duì)5 個(gè)經(jīng)典性能函數(shù)進(jìn)行仿真測(cè)試，結(jié)果表明，提出的果蠅優(yōu)化算法有較好的收斂速度收斂精度，降低了算法陷入局部極值的可能性。

1 果蠅算法基本介紹

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

圖1 果蠅群體進(jìn)化圖

根據(jù)果蠅覓食過(guò)程中的行為特點(diǎn)，將標(biāo)準(zhǔn)的果蠅優(yōu)化算法歸納為以下步驟[13]：

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

2）確定初始果蠅群體中果蠅個(gè)體位置和方向。RValue為果蠅隨機(jī)搜索距離和方向的隨機(jī)數(shù)。

3）利用每個(gè)果蠅個(gè)體位置坐標(biāo)與原點(diǎn)的距離Di來(lái)計(jì)算其味道濃度判定值Si，Si為距離Di的倒數(shù)。

4）將味道濃度判定值Si代入適應(yīng)度函數(shù)判定函數(shù)[14](或稱為適應(yīng)度函數(shù)，F(xiàn)itness function)，該函數(shù)是為了計(jì)算該種群中果蠅個(gè)體的味道濃度Smell(i)。

5）找出種群當(dāng)前味道濃度最優(yōu)的果蠅個(gè)體位置，記錄其坐標(biāo)和味道濃度值。

6）記錄最優(yōu)味道濃度值及對(duì)應(yīng)的橫縱坐標(biāo)，此時(shí)群體果蠅根據(jù)視覺(jué)向最優(yōu)個(gè)體位置飛去，形成新的果蠅群體。

7）迭代尋優(yōu)階段，重復(fù)執(zhí)行步驟2)～步驟5)，判斷當(dāng)前迭代次數(shù)是否小于最大迭代次數(shù)，當(dāng)前味道濃度是否優(yōu)于所記錄的最優(yōu)味道濃度，若成立，執(zhí)行步驟6)。

2 改進(jìn)的FOA算法(TEFOA)

2.1 指數(shù)遞減步長(zhǎng)

搜索步長(zhǎng)是決定FOA 算法搜索能力的關(guān)鍵因素。由指數(shù)函數(shù)確定的自適應(yīng)步長(zhǎng)在初期迭代搜索時(shí)，可在較大范圍內(nèi)展開(kāi)全局搜索，這有利于跳出局部最優(yōu)解[15]，加快算法的收斂速度，降低運(yùn)行時(shí)間；隨著迭代次數(shù)的增加，在算法運(yùn)行后期，由于已經(jīng)步入了有潛力的搜索區(qū)域，只需要在區(qū)域內(nèi)進(jìn)行局部搜索，即設(shè)置較小的搜索步長(zhǎng)在當(dāng)前搜索區(qū)域進(jìn)行精細(xì)搜索[16]。受文獻(xiàn)[9]的啟發(fā)，用指數(shù)遞減策略對(duì)果蠅算法進(jìn)行優(yōu)化。所使用的指數(shù)遞減策略表達(dá)式為：

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

圖2 指數(shù)遞減因子的變化曲線

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

2.2 t變異策略

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

圖3 t分布曲線圖

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

3.1 測(cè)試函數(shù)驗(yàn)證

為了檢驗(yàn)算法的有效性，選取了5 個(gè)經(jīng)典性能測(cè)試函數(shù)對(duì)標(biāo)準(zhǔn)果蠅算法和文中優(yōu)化算法在相同環(huán)境下進(jìn)行Matlab 仿真實(shí)驗(yàn)對(duì)比(求最小值)，所選函數(shù)均有不同特性，使用這些函數(shù)進(jìn)行測(cè)試所得的實(shí)驗(yàn)結(jié)果可以全面地反映算法的性能，更具有說(shuō)服力。

實(shí)驗(yàn)中所采用的經(jīng)典測(cè)試函數(shù)如表1 所示。

3.2 固定迭代次數(shù)下實(shí)驗(yàn)仿真分析

在測(cè)試函數(shù)過(guò)程中，借助Matlab 2016a 平臺(tái)，設(shè)置迭代次數(shù)為1 500 次，種群規(guī)模為20，算法獨(dú)立重復(fù)實(shí)驗(yàn)50 次。為了使測(cè)試結(jié)果更具有說(shuō)服力，選取FOA、LGMS-FOA[24]、TEFOA 這3 種算法進(jìn)行同條件測(cè)試，記錄實(shí)驗(yàn)過(guò)程中的平均值、標(biāo)準(zhǔn)差和測(cè)試函數(shù)最優(yōu)值作為評(píng)價(jià)標(biāo)準(zhǔn)。實(shí)驗(yàn)中所采用的標(biāo)準(zhǔn)測(cè)試函數(shù)如表1 所示，實(shí)驗(yàn)結(jié)果如表2 所示，其中Mean 表示函數(shù)的平均值，Std 表示函數(shù)的標(biāo)準(zhǔn)差，Best 表示函數(shù)可達(dá)到的最優(yōu)值，并繪制迭代次數(shù)增加時(shí)適應(yīng)度值的變化曲線。

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

表2 測(cè)試結(jié)果表

測(cè)試函數(shù)的變化曲線如圖4～8 所示。

圖4 Sphere函數(shù)變化曲線

圖5 Griewank函數(shù)變化曲線

圖6 Rastrigin函數(shù)變化曲線

4 結(jié)束語(yǔ)

圖7 Schaffer函數(shù)變化曲線

圖8 Sum Squares函數(shù)變化曲線

通過(guò)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析可知，盡管函數(shù)對(duì)于不同的算法有著不同的尋優(yōu)精度，但在5 種標(biāo)準(zhǔn)函數(shù)的測(cè)試中，文中優(yōu)化算法比標(biāo)準(zhǔn)FOA 算法的運(yùn)算精度均有不同程度的提高。所以，提出的TEFOA 算法優(yōu)于傳統(tǒng)的FOA 算法，尤其是在Rastrigin 和Schaffer 兩個(gè)測(cè)試函數(shù)上表現(xiàn)優(yōu)異，在迭代過(guò)程中訓(xùn)練得出的最優(yōu)值均可達(dá)到函數(shù)本身的最優(yōu)值；另外，從適應(yīng)度值的變化曲線可以看出，平均迭代不到500次就可獲得最優(yōu)值，TEFOA 算法的收斂速度優(yōu)于傳統(tǒng)的FOA 算法，收斂速度得到了較大的提高。這充分說(shuō)明了文中的改進(jìn)算法具有更高的收斂精度、更優(yōu)的搜索能力和更快的收斂速度，在一定程度上也可以避免局部最優(yōu)[25-26]。

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