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

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

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

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

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

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

果蠅優(yōu)化算法;自適應;迭代步長;認知因子;引導因子

0 引 言

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

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

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

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

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

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

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

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

(1)

其中，RandomValue為搜索距離。

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

(2)

(3)

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

Smelli=Function(Si)

(4)

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

(5)

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

(6)

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

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

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

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

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

(7)

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

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

(8)

受文獻[9]的啟發(fā)，假設在果蠅個體位置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 實 驗

3.1實驗設計

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

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

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

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

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

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

3.2實驗結(jié)果與分析

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

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

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

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

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

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

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

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

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

3.2.3 與同類算法的性能比較

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

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

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

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

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

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

4 結(jié)束語

針對果蠅優(yōu)化算法的早熟收斂導致收斂精度低的問題，引入了果蠅個體認知因子和果蠅群體引導因子，提出了自適應調(diào)整權重參數(shù)的果蠅優(yōu)化算法。該算法在每次迭代過程中計算認知因子和引導因子的大小，不僅充分利用了果蠅群體中所有果蠅位置的信息，也根據(jù)果蠅群體對果蠅個體的引導作用，自適應調(diào)整權重參數(shù)的大小，從而跳出局部極值，提高了果蠅優(yōu)化算法的收斂精度和全局搜索能力。通過實驗對比分析，結(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] 劉成忠，韓俊英.基于細菌遷徙的自適應果蠅優(yōu)化算法[J].計算機工程與科學,2014,36(4):690-696.

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

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

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

[11] 張彩宏，潘廣貞.融合禁忌搜索的混合果蠅優(yōu)化算法[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)絡出版時間

時間：2017-07-19

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

牛勇力(1992-)，男，碩士研究生，研究方向為智能計算、機器學習；吳 清，通訊作者，教授，碩士生導師，研究方向為智能計算等。

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