戈濤，張馨

（1.合肥市現(xiàn)代職業(yè)教育公共實(shí)訓(xùn)中心，合肥230012；2.安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥230601）

0 引言

果蠅優(yōu)化算法是臺(tái)灣學(xué)者潘文超在2011 年提出的新型群體智能優(yōu)化算法[1-2]，主要是模擬果蠅搜尋食物的過(guò)程，果蠅有著優(yōu)于其他物種的敏感嗅覺(jué)器官，能夠嗅到漂浮在幾十公里外空氣中的各種食物味道，當(dāng)靠近食物位置時(shí)又能通過(guò)其敏銳的視覺(jué)找到食物和同伴，并向味道濃度最大的方向飛去。果蠅算法就是通過(guò)模擬此過(guò)程并不斷迭代尋優(yōu)以求得問(wèn)題的最優(yōu)解。果蠅優(yōu)化算法自誕生之日起就以其算法簡(jiǎn)單、調(diào)整參數(shù)少、易實(shí)現(xiàn)等優(yōu)點(diǎn)而受到廣大學(xué)者的青睞，現(xiàn)已被廣泛應(yīng)用與求解函數(shù)優(yōu)化[3]、PID 控制參數(shù)優(yōu)化[4]、最小二乘支持向量機(jī)參數(shù)優(yōu)化[5]、置換流水線調(diào)度[6]、LSSVR 干燥速率建模[7]、多維背包問(wèn)題[8]等。隨著對(duì)果蠅優(yōu)化算法的不斷深入研究，算法本身也暴露出了不可忽視的缺點(diǎn)。果蠅優(yōu)化算法在求解單峰值函數(shù)時(shí)尚能表現(xiàn)出良好的尋優(yōu)效果，但是在求解多峰值或者高維度的復(fù)雜優(yōu)化問(wèn)題時(shí)很難達(dá)到理想的效果。

為了解決原始果蠅優(yōu)化算法自身存在的收斂速度慢、尋優(yōu)精度低、易陷入局部最優(yōu)等問(wèn)題，本文提出了一種新型的果蠅優(yōu)化算法，將本文方法與原始果蠅優(yōu)化算法及改進(jìn)的果蠅算法DS-FOA 和LGMS-FOA 進(jìn)行仿真對(duì)比，實(shí)驗(yàn)結(jié)果表明，本文所提出的算法在收斂效果和尋優(yōu)速度上有了明顯提高且具有更高的穩(wěn)定性。

1 基本果蠅優(yōu)化算法介紹

1.1 FOA算法描述

在基本果蠅優(yōu)化算法中，每只果蠅個(gè)體會(huì)被隨機(jī)的分布在一個(gè)N 維的特定搜索空間，其搜索步長(zhǎng)固定不變，搜尋食物的方向具有隨機(jī)性，每個(gè)果蠅個(gè)體都攜帶有味道濃度，該值與味道濃度判定值有關(guān)，由于在初始階段不知道食物的具體位置，因此把每個(gè)果蠅個(gè)體與原點(diǎn)距離的倒數(shù)作為判斷味道濃度判定值的依據(jù)，將該值代入目標(biāo)函數(shù)以求得果蠅個(gè)體的味道濃度值，味道濃度值越小的果蠅距離食物源的位置越近（適用于最小優(yōu)化問(wèn)題），記錄下果蠅群體中味道濃度值最小的果蠅位置，其他果蠅憑借敏銳的嗅覺(jué)飛往該位置，最后通過(guò)迭代不斷更新果蠅群體中的最佳位置，直到迭代結(jié)束找到問(wèn)題的最優(yōu)解。

1.2 FOA具體步驟

FOA 算法主要分為7 個(gè)步驟：果蠅群體位置初始化，果蠅飛行方向和距離，味道濃度判定值計(jì)算，味道濃度值計(jì)算，計(jì)算最佳味道濃度，保留最佳味道濃度值及其位置，迭代尋優(yōu)。

（1）果蠅群體位置初始化

設(shè)定果蠅群體規(guī)模和最大迭代次數(shù)分別為Sizepop、Maxgen,果蠅群體位置為X_axis,Y_axis。

（2）果蠅飛行方向和距離

其中，RValue 為果蠅的隨機(jī)搜索距離。（3）味道濃度判定值計(jì)算

計(jì)算果蠅個(gè)體與原點(diǎn)的距離（Di）和果蠅個(gè)體的味道濃度判定值（Si）：

（4）味道濃度值計(jì)算

將味道濃度判定值Si代入適應(yīng)度函數(shù)Function中，求出該果蠅個(gè)體位置的味道濃度smell(i)：

smell(i)=Function(Si)

（5）計(jì)算最佳味道濃度

找出此果蠅群體中的最優(yōu)個(gè)體（即味道濃度最小值）以及其位置：

[bestsmellbestindex] =min(smell)

（6）保留最佳味道濃度值及其位置

保留最優(yōu)味道濃度值bestsmell 與其對(duì)應(yīng)的X、Y 坐標(biāo)，此時(shí)果蠅群體往該位置飛去：

（7）迭代尋優(yōu)

重復(fù)執(zhí)行步驟（2）-（5），并判斷味道濃度是否優(yōu)于前一迭代味道濃度，若成立則執(zhí)行步驟（6）。

1.3 基本FOA的缺陷

缺陷一：基本FOA 算法中，果蠅個(gè)體在搜索空間內(nèi)移動(dòng)步長(zhǎng)是固定不變的，選擇一個(gè)固定的移動(dòng)步長(zhǎng)值求解優(yōu)化問(wèn)題是不恰當(dāng)?shù)?，尤其是?duì)于多峰值函數(shù)，若搜索步長(zhǎng)值取得較大，在算法前期尚可獲得較快的尋優(yōu)速度，進(jìn)行全局搜索，但是到了算法尋優(yōu)后期較大的移動(dòng)步長(zhǎng)極有可能跳過(guò)函數(shù)最優(yōu)解，尋優(yōu)精度降低，陷入局部最優(yōu)；若搜索步長(zhǎng)值取得較小值，雖然尋優(yōu)精度提高了，但是步長(zhǎng)值較小會(huì)降低了尋優(yōu)速度，需要不斷重復(fù)的迭代，降低了尋優(yōu)效率，不利于進(jìn)行全局尋優(yōu)。

缺陷二：基本FOA 算法中，在果蠅視覺(jué)搜索過(guò)程中，果蠅群體一旦發(fā)現(xiàn)具有最優(yōu)味道濃度的果蠅，所有果蠅個(gè)體都會(huì)飛往該果蠅的位置，可是該果蠅極有可能并不是整個(gè)搜索空間中的最優(yōu)果蠅個(gè)體，而是局部最優(yōu)果蠅個(gè)體，若此局部最優(yōu)果蠅個(gè)體周圍沒(méi)有比其味道濃度更優(yōu)的果蠅，它就會(huì)保持不動(dòng)，其他果蠅則源源不斷地飛往此果蠅的位置，不但降低了尋優(yōu)效率，也容易使算法陷入局部最優(yōu)。

2 改進(jìn)的FOA算法（CSFOA）

2.1 非線性遞減步長(zhǎng)

針對(duì)基本FOA 算法中的缺陷一，CSFOA 算法中變固定步長(zhǎng)值為非線性遞減步長(zhǎng)，移動(dòng)步長(zhǎng)變化率如圖1所示，在果蠅算法迭代尋優(yōu)初始階段，果蠅個(gè)體保持一個(gè)較大的移動(dòng)步長(zhǎng)，使算法的搜索能力能夠滲透到整個(gè)搜索空間，從而提高算法全局尋優(yōu)的能力，避免算法陷入某個(gè)局部最優(yōu)值；在果蠅算法迭代尋優(yōu)后期，果蠅個(gè)體的移動(dòng)步長(zhǎng)非線性的動(dòng)態(tài)逐漸減小，使其能在當(dāng)前局部最優(yōu)解附近進(jìn)行精細(xì)搜索，不僅避免了因?yàn)橐苿?dòng)步長(zhǎng)值過(guò)大而跳過(guò)最優(yōu)解可能，而且也提高了算法后期的收斂精度。

圖1 移動(dòng)步長(zhǎng)變化率

具體公式如下：

其中Lmax，Lmin分別為最大和最小移動(dòng)步長(zhǎng)，Rate為步長(zhǎng)的變化率，t 為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)，p 為步長(zhǎng)調(diào)節(jié)因子，c 為指數(shù)調(diào)節(jié)因子。

2.2 隨機(jī)策略

針對(duì)基本FOA 算法中的缺陷二，本文引入了隨機(jī)機(jī)制，增加算法探索解空間的能力，若某個(gè)最優(yōu)解經(jīng)過(guò)多次迭代始終不變，則此時(shí)極有可能陷入局部最優(yōu)解，如圖2 所示，因此引入隨機(jī)策略進(jìn)行擾動(dòng)，使算法逃離局部最優(yōu)，增加解得多樣性，從而進(jìn)行全局搜索。具體策略如下：

其中（1-e-λx）滿足指數(shù)分布，besti-1為上一代最優(yōu)味道濃度值。

圖2 局部最優(yōu)實(shí)例

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

3.1 實(shí)驗(yàn)平臺(tái)

本文的實(shí)驗(yàn)平臺(tái)是MATLAB R2014a,在操作系統(tǒng)為Windows 7，內(nèi)存為4GB，CPU 頻率為3.20GHz 的PC上運(yùn)行。

3.2 參數(shù)設(shè)置

具體參數(shù)設(shè)置如下：果蠅群體大小Sizepop=20，迭代次數(shù)tmax=100，步長(zhǎng)調(diào)節(jié)因子p=1，指數(shù)調(diào)節(jié)因子c=1.5，最大移動(dòng)步長(zhǎng)Lmax=5，最小移動(dòng)步長(zhǎng)Lmin=0.01，隨機(jī)策略中的λ=0.5。

3.3 測(cè)試函數(shù)

為了驗(yàn)證算法的可行性，本文選取8 個(gè)基準(zhǔn)測(cè)試函數(shù)對(duì)FOA、DS-FOA、LGMS-FOA 以及本文算法進(jìn)行測(cè)試，求出在指定搜索區(qū)間內(nèi)的函數(shù)最優(yōu)值，測(cè)試函數(shù)如表1 所示。

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

3.4 仿真實(shí)驗(yàn)

使用基本FOA、DS-FOA、LGMS-FOA 以及本文算法CSFOA 對(duì)8 個(gè)基準(zhǔn)函數(shù)獨(dú)立運(yùn)行實(shí)驗(yàn)20 次，分別求出8 個(gè)基準(zhǔn)測(cè)試函數(shù)的平均值以及標(biāo)準(zhǔn)偏差，函數(shù)的平均值反映了算法的尋優(yōu)能力，標(biāo)準(zhǔn)偏差則能夠反映出算法的穩(wěn)定性。在MATLAB 上經(jīng)過(guò)20 次獨(dú)立運(yùn)行的實(shí)驗(yàn)結(jié)果如表2 所示，其中Mean、Std 分別代指函數(shù)的平均值和標(biāo)準(zhǔn)偏差。

表2 四種算法優(yōu)化性能對(duì)比

圖3 f1(x)函數(shù)優(yōu)化對(duì)比

圖4 f2(x)函數(shù)優(yōu)化對(duì)比

圖5 f3(x)函數(shù)優(yōu)化對(duì)比

圖6 f4(x)函數(shù)優(yōu)化對(duì)比

圖7 f5(x)函數(shù)優(yōu)化對(duì)比

圖8 f6(x)函數(shù)優(yōu)化對(duì)比

圖9 f7(x)函數(shù)優(yōu)化對(duì)比

圖10 f8(x)函數(shù)優(yōu)化對(duì)比

從表2 中可以看出，在求解高維函數(shù)的最優(yōu)值時(shí)，原始FOA 算法的弊端尤其明顯，由于原始FOA 采用固定的步長(zhǎng)值，限制了算法的尋優(yōu)性能，導(dǎo)致算法容易陷入局部最優(yōu)；相較于原始FOA，DS-FOA 引入了初始步長(zhǎng)L0，使算法能夠隨著迭代的進(jìn)行移動(dòng)步長(zhǎng)逐漸減小，提高了算法在迭代后期的收斂精度；LGMS-FOA 則是引入了權(quán)重系數(shù)w，并且隨著不斷迭代權(quán)重系數(shù)w 按指數(shù)形式下降，相較于原始FOA 同樣提高了算法的收斂精度，但是在對(duì)函數(shù)f2(x)、f3(x)、f4(x)求解中其收斂精度卻低于原始FOA 的收斂精度，原因在于LGMSFOA 算法并沒(méi)有解決算法陷入局部極值的問(wèn)題。與其他三種算法相比，CSFOA 算法不管是在收斂精度還是算法穩(wěn)定性方面都有著明顯的優(yōu)勢(shì)。

表3 目標(biāo)精度下平均迭代次數(shù)與成功率對(duì)比

圖3～圖6 為四種算法的迭代尋優(yōu)過(guò)程，從中可以看出，原始FOA 算法收斂速度較慢，DS-FOA 和LGMS-FOA 算法收斂速度雖有提高，但是容易陷入局部最優(yōu)，而CSFOA 算法由于采用了隨機(jī)策略，即使遇到局部最優(yōu)解也能及時(shí)跳出局部極值，尋找到函數(shù)最優(yōu)解，提高了算法的尋優(yōu)性能。

表3 為8 個(gè)基準(zhǔn)測(cè)試函數(shù)在目標(biāo)精度下所需要的迭代次數(shù)和成功率的結(jié)果對(duì)比，從中可以看出，在低維情況下，三種改進(jìn)的FOA 算法有著更強(qiáng)的尋有能力，迭次數(shù)更少，且成功率高；在高維情況下，原始FOA 算法、DS-FOA 算法和LGMS-FOA 算法的尋優(yōu)能力下降，易陷入局部最優(yōu)，且在完成目標(biāo)精度情況下需要經(jīng)過(guò)多次迭代，影響了算法的尋優(yōu)效率，而CSFOA 算法在低維和高維情況下都表現(xiàn)出了良好的尋優(yōu)能力，且具有更高的效率和穩(wěn)定性。

4 結(jié)語(yǔ)

本文針對(duì)基本果蠅算法的缺陷，提出了非線性動(dòng)態(tài)機(jī)制，將基本果蠅算法中的固定步長(zhǎng)變?yōu)榉蔷€性遞減步長(zhǎng)，既保持了算法在迭代初期全局尋優(yōu)的能力，又維持了算法在迭代后期進(jìn)行精細(xì)搜索的能力；為了增加算法在整個(gè)尋優(yōu)空間中探索解空間的能力，引入了隨機(jī)策略，對(duì)空間解進(jìn)行擾動(dòng)，避免算法陷入局部最優(yōu)。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法具有更好的探索解空間的能力，有效避免了算法陷入局部極值，增加了算法的穩(wěn)定性，提高了運(yùn)行效率。接下來(lái)的研究任務(wù)是將新改進(jìn)的算法用于解決實(shí)際問(wèn)題，驗(yàn)證其解決問(wèn)題的能力和效率。