牛勇力，吳 清,2，李平娜，謝章華

(1.河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401；2.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401)

自適應(yīng)修改權(quán)重參數(shù)的果蠅優(yōu)化算法

牛勇力1，吳 清1,2，李平娜1，謝章華1

(1.河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津 300401；2.河北省大數(shù)據(jù)計(jì)算重點(diǎn)實(shí)驗(yàn)室，天津 300401)

針對果蠅優(yōu)化算法容易陷入局部極值、迭代后期收斂速度慢和收斂精度低的缺陷，借鑒粒子群優(yōu)化算法中個(gè)體認(rèn)知因子和群體引導(dǎo)因子的思想，提出了自適應(yīng)修改權(quán)重參數(shù)的果蠅優(yōu)化算法。該算法引入了果蠅個(gè)體認(rèn)知因子和果蠅群體引導(dǎo)因子，讓果蠅個(gè)體對自己的位置有充分的認(rèn)知，也讓果蠅群體對果蠅個(gè)體有很好的引導(dǎo)。在每次迭代時(shí)，算法根據(jù)當(dāng)前果蠅群體的適應(yīng)度值自適應(yīng)修改個(gè)體認(rèn)知因子和群體引導(dǎo)因子的大小，從而調(diào)整迭代步長的大小，使得改進(jìn)后的算法能夠避免早熟收斂，提高收斂精度和收斂速度?；跍y試函數(shù)的實(shí)驗(yàn)結(jié)果表明，自適應(yīng)修改權(quán)重參數(shù)的果蠅優(yōu)化算法能跳出局部極值，具有更好的全局搜索能力，在收斂速度和收斂精度方面比基本果蠅優(yōu)化算法有較大的提高。

果蠅優(yōu)化算法;自適應(yīng);迭代步長;認(rèn)知因子;引導(dǎo)因子

0 引 言

果蠅優(yōu)化算法(Fruit fly Optimization Algorithm,FOA)[1]是近年來提出的一類新的全局優(yōu)化智能算法。該算法源于對果蠅群體覓食行為的仿真模擬。和其他智能優(yōu)化算法相比，F(xiàn)OA結(jié)構(gòu)簡單，容易理解，具有調(diào)整參數(shù)少、計(jì)算量小、收斂速度快等優(yōu)點(diǎn)，因此逐漸受到國內(nèi)外學(xué)者的關(guān)注和研究，并且成功應(yīng)用于工程和科學(xué)等領(lǐng)域，如控制器的調(diào)節(jié)[2]、電力負(fù)荷預(yù)測[3-4]、聯(lián)合補(bǔ)充問題[5-6]等。

但是FOA也有自身的缺點(diǎn)。在迭代優(yōu)化過程中，果蠅個(gè)體搜索食物的范圍大小是固定的，使得算法極易陷入局部最優(yōu)，出現(xiàn)早熟收斂；此外，F(xiàn)OA不能表現(xiàn)出果蠅群體搜索食物的狀態(tài)變化，容易導(dǎo)致算法在后期收斂速度變慢，收斂精度低。

針對上述問題，借鑒粒子群優(yōu)化算法中認(rèn)知因子和引導(dǎo)因子的思想，提出了自適應(yīng)調(diào)整權(quán)重參數(shù)的果蠅優(yōu)化算法(FOA with Adaptive Modifying Weight Parameters,FOAAMWP)。該算法在迭代過程中，引入個(gè)體認(rèn)知因子和群體引導(dǎo)因子，使其得以根據(jù)果蠅群體搜索食物的實(shí)際情況動(dòng)態(tài)修改迭代步長，從而具有更好的全局搜索能力，并通過實(shí)驗(yàn)對其進(jìn)行了驗(yàn)證。

1 果蠅優(yōu)化算法

果蠅優(yōu)化算法是一種模擬果蠅覓食行的尋求全局優(yōu)化的新算法。果蠅在嗅覺和視覺上優(yōu)于其他物種，其發(fā)達(dá)的嗅覺能很好地搜集空氣中的食物氣味，然后飛近食物，再利用敏銳的視覺發(fā)現(xiàn)食物和其他果蠅聚集的位置[7]。

根據(jù)果蠅搜索食物的過程，將果蠅優(yōu)化算法歸納為以下幾個(gè)步驟：

(1)給定果蠅群體規(guī)模Sizepop，最大迭代次數(shù)Maxgen，隨機(jī)初始化果蠅群體位置X_axis和Y_axis。

(2)賦給每個(gè)果蠅個(gè)體利用嗅覺搜尋食物的隨機(jī)方向和距離：

(1)

其中，RandomValue為搜索距離。

(3)由于無法得知食物的準(zhǔn)確位置，因此先估計(jì)與原點(diǎn)的距離Disti，再計(jì)算味道濃度判定值Si，其中味道濃度判定值為距離的倒數(shù)：

(2)

(3)

(4)將Si代入味道濃度判定函數(shù)(也稱適應(yīng)度函數(shù))，求出每個(gè)果蠅個(gè)體位置的味道濃度Smelli：

Smelli=Function(Si)

(4)

(5)找出該果蠅群體中味道濃度最佳的果蠅個(gè)體，即最優(yōu)果蠅個(gè)體：

(5)

(6)記錄并保留最佳味道濃度值bestSmell及其對應(yīng)的X、Y坐標(biāo)，此時(shí)果蠅群體利用視覺向該位置飛去：

(6)

(7)進(jìn)入迭代尋優(yōu)，重復(fù)執(zhí)行步驟(2)～(5)，并判斷最佳味道濃度是否優(yōu)于前一次迭代的最佳味道濃度，同時(shí)當(dāng)前迭代次數(shù)是否小于最大迭代次數(shù)Maxgen，若是則執(zhí)行步驟(6)，否則迭代停止，算法結(jié)束。

2 自適應(yīng)調(diào)整權(quán)重參數(shù)的果蠅優(yōu)化算法

在FOA迭代尋優(yōu)的過程中，從式(1)可以看出，每個(gè)果蠅個(gè)體利用嗅覺搜索食物的迭代步長是一個(gè)固定范圍的隨機(jī)值，再利用視覺向同一只最優(yōu)果蠅靠近，這樣操作雖然使算法的收斂速度加快，但不足之處是果蠅搜索范圍具有局限性，無法實(shí)現(xiàn)全局搜索，若該最優(yōu)果蠅個(gè)體不是全局最優(yōu)，則極易導(dǎo)致算法陷入局部最優(yōu)而無法跳出，收斂精度低，出現(xiàn)早熟收斂。

提出的自適應(yīng)調(diào)整權(quán)重參數(shù)的果蠅優(yōu)化算法，借鑒粒子群優(yōu)化算法中的認(rèn)知因子和引導(dǎo)因子，在迭代優(yōu)化過程中，引入個(gè)體認(rèn)知因子和群體引導(dǎo)因子。其中，個(gè)體認(rèn)知因子控制著果蠅個(gè)體對自己和其他果蠅個(gè)體位置的認(rèn)知，群體引導(dǎo)因子控制著整個(gè)果蠅群體目前的最優(yōu)位置對果蠅個(gè)體的引導(dǎo)。在迭代尋優(yōu)過程中，兩個(gè)因子較好的調(diào)整策略是在優(yōu)化前期，果蠅個(gè)體具有較大的認(rèn)知能力，果蠅群體具有較小的引導(dǎo)能力，這樣有利于果蠅個(gè)體在更大的范圍內(nèi)進(jìn)行搜索，避免果蠅群體陷入局部最優(yōu)，導(dǎo)致早熟收斂；在優(yōu)化后期，果蠅個(gè)體具有較小的認(rèn)知能力，果蠅群體具有較大的引導(dǎo)能力，這樣有利于果蠅群體快速收斂到全局最優(yōu)，避免果蠅個(gè)體再跳出全局最優(yōu)值，提高算法的收斂精度。

從FOA的迭代過程可以看出，最優(yōu)果蠅個(gè)體的味道濃度隨著迭代過程的進(jìn)行逐漸減小，因此所提出的FOAAMWP根據(jù)每次迭代過程中的味道濃度值，自適應(yīng)動(dòng)態(tài)調(diào)整個(gè)體認(rèn)知因子和群體引導(dǎo)因子的權(quán)重。在FOAAMWP中，個(gè)體認(rèn)知因子c1和群體引導(dǎo)因子c2的取值為：

(7)

因此，在迭代過程前期，保證了較大的c1和較小的c2，有利于果蠅個(gè)體向更大的區(qū)域搜索尋優(yōu)。隨著迭代優(yōu)化過程的進(jìn)行，果蠅群體逐漸靠近全局最優(yōu)值，味道濃度值也逐漸減小，從而在迭代優(yōu)化后期，保證了較小的c1和較大的c2，使得果蠅群體能夠快速收斂到全局最優(yōu)值。

為了使果蠅個(gè)體在每次迭代優(yōu)化中，對自己的位置有清楚的認(rèn)知，不但考慮最優(yōu)果蠅個(gè)體的位置對該果蠅個(gè)體的影響，還要充分利用果蠅群體里其他果蠅個(gè)體的位置所包含的信息。在相關(guān)粒子群優(yōu)化算法中[8]，假設(shè)在第i個(gè)粒子搜索到的最優(yōu)位置pi(t)(i=1,2,…,Sizepop)和整個(gè)粒子群搜索到的最優(yōu)位置pg(t)都固定不變的情況下，得出結(jié)論：

(8)

受文獻(xiàn)[9]的啟發(fā)，假設(shè)在果蠅個(gè)體位置xi(t),yi(t)(i=1,2,…,Sizepop)和果蠅群體最優(yōu)位置Xaxis(t),Yaxis(t)都固定不變的情況下，也能得到：

(9)

(10)

(11)

(12)

根據(jù)以上分析，為了避免果蠅優(yōu)化算法的早熟收斂，在迭代優(yōu)化過程中，將式(1)更換為：

(13)

通過上述分析，F(xiàn)OAAMWP的流程圖如圖1所示。

圖1 FOAAMWP流程圖

3 實(shí) 驗(yàn)

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

為了驗(yàn)證FOAAMWP的性能，設(shè)計(jì)了兩類對比測試實(shí)驗(yàn)：(1)FOA和FOAAMWP的對比實(shí)驗(yàn)；(2)FOAAMWP和同類其他算法的對比實(shí)驗(yàn)。對比實(shí)驗(yàn)選用文獻(xiàn)[10-11]中常用于優(yōu)化算法比較的測試函數(shù)，函數(shù)形式、維數(shù)、搜索區(qū)間、函數(shù)最小值等如表1所示。

表1 改進(jìn)算法測試的優(yōu)化函數(shù)

為了便于比較和突出FOAAMWP的性能，令FOA和FOAAMWP的果蠅群體規(guī)模Sizepop=30，最大迭代次數(shù)Maxgen=2 000，隨機(jī)初始化果蠅群體位置區(qū)間為表1中各函數(shù)的搜索區(qū)間，迭代過程中果蠅搜尋食物的隨機(jī)飛行方向和距離區(qū)間為[-1,1]。算法性能評估采用的方法：

(1)固定迭代次數(shù)，評估算法的收斂精度；

(2)固定收斂精度目標(biāo)值，評估算法達(dá)到該精度目標(biāo)所需的平均迭代次數(shù)和收斂速度；

(3)采用參考文獻(xiàn)中同類算法的參數(shù)，評估算法的收斂精度，并與參考文獻(xiàn)進(jìn)行比較。

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

3.2.1 固定迭代次數(shù)的收斂精度

六個(gè)測試函數(shù)f1～f6在固定迭代優(yōu)化次數(shù)的條件下，分別采用FOAAMWP和FOA對測試函數(shù)進(jìn)行20次獨(dú)立實(shí)驗(yàn)，優(yōu)化均值為20次獨(dú)立實(shí)驗(yàn)的最優(yōu)值平均值，標(biāo)準(zhǔn)差為20次獨(dú)立實(shí)驗(yàn)得到最優(yōu)值的標(biāo)準(zhǔn)差。表2為測試函數(shù)在30維條件下運(yùn)行后的實(shí)驗(yàn)結(jié)果。

表2 算法在測試函數(shù)30維的條件下的性能比較

從表2可以看出，不管是單峰函數(shù)還是多峰函數(shù)，F(xiàn)OAAMWP均比FOA更接近最優(yōu)值。對于單峰函數(shù)f1，F(xiàn)OAAMWP比FOA的收斂精度和標(biāo)準(zhǔn)差都提高了7個(gè)數(shù)量級，說明FOAAMWP比FOA的收斂精度更高，收斂的穩(wěn)定性更好。對于單峰函數(shù)f3，F(xiàn)OAAMWP的收斂標(biāo)準(zhǔn)差為0，說明FOAAMWP在得到函數(shù)最優(yōu)值以后，保持了良好的穩(wěn)定性。

對于多峰函數(shù)f2，f5和f6，F(xiàn)OAAMWP比FOA的收斂精度分別提高了2，4和7個(gè)數(shù)量級，說明FOAAMWP能跳出函數(shù)的局部最優(yōu)值，避免早熟收斂，收斂精度比FOA要高。對于多峰函數(shù)f4，F(xiàn)OAAMWP能夠得到函數(shù)的最優(yōu)值為0，并且標(biāo)準(zhǔn)差也為0，充分說明FOAAMWP比FOA的收斂精度更高、性能更好。

3.2.2 固定收斂精度下的迭代次數(shù)

六個(gè)測試函數(shù)f1～f6在30維的條件下，分別采用FOA和FOAAMWP經(jīng)過20次獨(dú)立運(yùn)行后得到各函數(shù)目標(biāo)精度的平均迭代優(yōu)化次數(shù)和成功率，如表3所示。其中，成功率=達(dá)到精度的運(yùn)行次數(shù)/實(shí)驗(yàn)總次數(shù)，∞表示達(dá)到最大迭代次數(shù)時(shí)也沒有達(dá)到目標(biāo)精度。

從表3可以看出，對于函數(shù)f1和f4～f6，F(xiàn)OA在經(jīng)過多次的迭代優(yōu)化后，才達(dá)到表中的目標(biāo)精度，而FOAAMWP只要經(jīng)過較少次的迭代優(yōu)化后，就能滿足表中的目標(biāo)精度，說明FOAAMWP在收斂速度上比FOA有大幅提高。在20次的獨(dú)立實(shí)驗(yàn)中，對于函數(shù)f1，f5和f6，只有個(gè)別幾次的實(shí)驗(yàn)?zāi)軌驖M足目標(biāo)值，而FOAAMWP均能以100%的成功率達(dá)到目標(biāo)精度，說明FOAAMWP在收斂穩(wěn)定性上比FOA更好。對于函數(shù)f2和f3，F(xiàn)OA在優(yōu)化過程結(jié)束，達(dá)到最大迭代次數(shù)時(shí)，仍然沒有達(dá)到目標(biāo)精度，成功率為0，而FOAAMWP在經(jīng)過次數(shù)少的迭代優(yōu)化后，能以100%的成功率達(dá)到目標(biāo)精度，充分說明FOAAMWP比FOA的收斂更穩(wěn)定、性能更好。

表3 在目標(biāo)值下的平均迭代次數(shù)和成功率比較

3.2.3 與同類算法的性能比較

表4是FOAAMWP與MFOA和IFOA的實(shí)驗(yàn)結(jié)果比較，表5是FOAAMWP與DFOA的實(shí)驗(yàn)結(jié)果比較。其中，最優(yōu)值為迭代優(yōu)化后得到的最小值，平均值和標(biāo)準(zhǔn)差分別為迭代優(yōu)化中得到的所有值的平均值和標(biāo)準(zhǔn)差。為了比較更準(zhǔn)確客觀，實(shí)驗(yàn)選取和參考文獻(xiàn)中相同的參數(shù)。文獻(xiàn)[12]的果蠅群體規(guī)模為50，迭代次數(shù)為1 000，每個(gè)測試函數(shù)獨(dú)立進(jìn)行30次；文獻(xiàn)[13]的果蠅群體規(guī)模為10，迭代次數(shù)為5 000，每個(gè)測試函數(shù)獨(dú)立運(yùn)行30次；文獻(xiàn)[14]的果蠅群體規(guī)模為40，迭代次數(shù)為500，突變因子為0.9，每個(gè)測試函數(shù)獨(dú)立運(yùn)行20次，并且f3的搜索區(qū)間為[-10,10]。測試函數(shù)的維數(shù)均為30維，-表示文獻(xiàn)中沒有對該測試函數(shù)進(jìn)行實(shí)驗(yàn)。

表4 算法的性能比較(1)

從表4可以看出，F(xiàn)OAAMWP和MFOA在參數(shù)相同的條件下，在優(yōu)化均值上比MFOA高出2～5個(gè)數(shù)量級，說明FOAAMWP的收斂精度比MFOA高，在標(biāo)準(zhǔn)差，即穩(wěn)定性上FOAAMWP和MFOA基本持平。對于函數(shù)f1和f5，雖然FOAAMWP比IFOA在優(yōu)化均值和標(biāo)準(zhǔn)差上有差距，但在函數(shù)f2～f4中可以看出，F(xiàn)OAAMWP比IFOA收斂精度更高，收斂穩(wěn)定性更好。

表5 算法的性能比較(2)

從表5可以看出，對于函數(shù)f1，f2和f4，F(xiàn)OAAMWP比DFOA能得到更好的最優(yōu)值、平均值和標(biāo)準(zhǔn)差。

通過與同類算法的比較，得出FOAAMWP在收斂精度和收斂穩(wěn)定性上與同類算法基本持平，性能相當(dāng)，說明FOAAMWP能夠跳出局部最優(yōu)，在更大的范圍內(nèi)搜索全局最優(yōu)值。

4 結(jié)束語

針對果蠅優(yōu)化算法的早熟收斂導(dǎo)致收斂精度低的問題，引入了果蠅個(gè)體認(rèn)知因子和果蠅群體引導(dǎo)因子，提出了自適應(yīng)調(diào)整權(quán)重參數(shù)的果蠅優(yōu)化算法。該算法在每次迭代過程中計(jì)算認(rèn)知因子和引導(dǎo)因子的大小，不僅充分利用了果蠅群體中所有果蠅位置的信息，也根據(jù)果蠅群體對果蠅個(gè)體的引導(dǎo)作用，自適應(yīng)調(diào)整權(quán)重參數(shù)的大小，從而跳出局部極值，提高了果蠅優(yōu)化算法的收斂精度和全局搜索能力。通過實(shí)驗(yàn)對比分析，結(jié)果表明，F(xiàn)OAAMWP比FOA具有更好的全局搜索能力，更高的收斂精度和收斂速度。

[1] Pan W T.A new fruit fly optimization algorithm:taking the financial distress model as an example[J].Knowledge-Based Systems,2012,26(2):69-74.

[2] Li C,Xu S,Li W,et al.A novel modified fly optimization algorithm for designing the self-tuning proportional integral derivative controller[J].Journal of Convergence Information Technology,2012,7(16):69-77.

[3] 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(2):378-387.

[4] Li H Z,Guo S,Zhao H R,et al.Annual electric load forecasting by a least squares support vector machine with a fruit fly optimization algorithm[J].Energies,2012,5(12):4430-4445.

[5] Wang L,Shi Y,Liu S.An improved fruit fly optimization algorithm and its application to joint replenishment problems[J].Expert Systems with Applications,2015,42(9):4310-4323.

[6] Wang L,Liu R,Liu S.An effective and efficient fruit fly optimization algorithm with level probability policy and its applications[J].Knowledge-Based Systems,2016,97:158-174.

[7] 劉成忠，韓俊英.基于細(xì)菌遷徙的自適應(yīng)果蠅優(yōu)化算法[J].計(jì)算機(jī)工程與科學(xué),2014,36(4):690-696.

[8] Fvan D.An analysis of particle swarm optimizers[D].South Africa:University of Pretoria,2002.

[9] 高 鷹.一種自適應(yīng)擴(kuò)展粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2006,42(15):12-15.

[10] 韓俊英，劉成忠.自適應(yīng)調(diào)整參數(shù)的果蠅優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(7):50-55.

[11] 張彩宏，潘廣貞.融合禁忌搜索的混合果蠅優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2016,37(4):907-913.

[12] Pan W T.Using modified fruit fly optimisation algorithm to perform the function test and case studies[J].Connection Science,2013,25(2):151-160.

[13] Pan Q K,Sang H Y,Duan J H,et al.An improved fruit fly optimization algorithm for continuous function optimization problems[J].Knowledge-Based Systems,2014,62(5):69-83.

[14] Niu J,Zhong W,Liang Y,et al.Fruit fly optimization algorithm based on differential evolution and its application on gasification process operation optimization[J].Knowledge-Based Systems,2015,88:253-263.

AFruitFlyOptimizationAlgorithmwithAdaptiveModifyingWeightParameters

NIU Yong-li1，WU Qing1,2，LI Ping-na1，XIE Zhang-hua1

(1.School of Computer Science and Software，Hebei University of Technology,Tianjin 300401,China；2.Key Laboratory of Big Data Calculation of Hebei Province,Tianjin 300401,China)

In view of the defects of easily falling into local extreme,slow convergence speed in later iteration and low convergence precision for fruit fly optimization algorithm,a fruit fly optimization algorithm based on adaptive modifying weight parameters is proposed considering individual cognitive factor and group guiding factor of particle swarm optimization.It introduces individual cognitive factor and group guiding factor so that the individual has sufficient awareness on its own position and the group has a good guide on the individuals.In each loop of iteration it dynamically has modified size of cognitive factor and guiding factor based on the current value of fitness of the fruit fly group and regulated iterative step size by adaptive method,which makes it avoid the premature convergence and improve its convergence accuracy and convergence rate.Experimental results of standard test functions show that it can jump out of local extreme with advantages of more precise and faster convergence.

fruit fly optimization algorithm;adaptive;iterative step;cognitive factor;guiding factor

2016-10-17

2017-01-21 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-07-19

國家自然科學(xué)基金資助項(xiàng)目(21276063，21476059)；河北省科技支撐項(xiàng)目(16273101D)

牛勇力(1992-)，男，碩士研究生，研究方向?yàn)橹悄苡?jì)算、機(jī)器學(xué)習(xí)；吳 清，通訊作者，教授，碩士生導(dǎo)師，研究方向?yàn)橹悄苡?jì)算等。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170719.1110.042.html

TP18;TP301

A

1673-629X(2017)11-0041-05

10.3969/j.issn.1673-629X.2017.11.009