基于自適應(yīng)步長的果蠅優(yōu)化算法

郭曉東， 王麗芳， 張學(xué)良

(1. 太原科技大學(xué) 電子信息工程學(xué)院， 山西太原 030024；2. 太原科技大學(xué) 機械工程學(xué)院，山西 太原 030024；3. 太原科技大學(xué) 復(fù)雜系統(tǒng)與計算智能實驗室， 山西 太原 030024)

?

基于自適應(yīng)步長的果蠅優(yōu)化算法

郭曉東1,2， 王麗芳3， 張學(xué)良2

(1. 太原科技大學(xué) 電子信息工程學(xué)院， 山西太原 030024；2. 太原科技大學(xué) 機械工程學(xué)院，山西 太原 030024；3. 太原科技大學(xué) 復(fù)雜系統(tǒng)與計算智能實驗室， 山西 太原 030024)

針對固定搜索步長下標(biāo)準(zhǔn)果蠅優(yōu)化算法(SFOA)尋優(yōu)速度慢， 收斂精度不高， 容易陷于局部極值的不足， 通過分析果蠅個體生成機制中搜索步長與算法搜索能力的關(guān)系， 提出了一種基于自適應(yīng)步長的改進果蠅優(yōu)化算法(FOABASS)， 在該算法中搜索步長隨種群當(dāng)前位置、 當(dāng)前優(yōu)化代數(shù)的變化而變化， 由此生成的果蠅群體具備較強的全局勘探能力， 同時兼顧全局勘探能力和局部開發(fā)能力的平衡. 最后給出了FOABASS算法和SFOA算法、 其它幾種改進FOA算法的性能比較， 仿真結(jié)果表明了該算法的有效性.

果蠅優(yōu)化算法； 函數(shù)優(yōu)化； 自適應(yīng)步長； 局部極值

果蠅優(yōu)化算法 (Fruit Fly Optimization Algorithm， FOA)源于對果蠅覓食行為的模擬[1-2]， 由潘文超在2011年6月提出. 作為一類新的全局優(yōu)化進化算法， FOA算法引起了許多學(xué)者的關(guān)注， 發(fā)展出了數(shù)個不同的改進版本， 如多群體果蠅優(yōu)化算法[3]、 混沌果蠅優(yōu)化算法[4]、 反向認知的果蠅優(yōu)化算法[5]、 基于歷史認知的果蠅優(yōu)化算法[6]、 對FOA參數(shù)的研究[7-8]， 等. FOA算法已成功應(yīng)用于廣義回歸神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化[1]， 函數(shù)優(yōu)化[9]， 高速公路道路關(guān)閉交通事件對車輛影響的判斷模型[10]， LSSVR干燥速率建模[11]， PID控制器設(shè)計[12]、 最小二乘支持向量機參數(shù)優(yōu)化[13]等科學(xué)與工程領(lǐng)域.

與其它群智能算法比較， FOA算法具有概念簡單、 參數(shù)少、 易于實現(xiàn)、 運行速度快的特點. 另一方面， FOA算法的工作機理使得該算法容易陷入局部極值， 導(dǎo)致收斂速度變慢、 精度降低， 甚至優(yōu)化失敗.

本文介紹了FOA算法工作機理， 分析了導(dǎo)致FOA算法尋優(yōu)速度慢， 收斂精度不高， 容易陷于局部極值的原因， 并給出了解決辦法， 使用自適應(yīng)步長來生成果蠅個體， 提出了一種基于自適應(yīng)步長的改進FOA算法， 最后給出了該算法和標(biāo)準(zhǔn)FOA算法(SFOA)、 其它改進FOA算法的性能比較.

1 標(biāo)準(zhǔn)果蠅優(yōu)化算法

果蠅優(yōu)化算法是一種基于果蠅覓食行為推演出的尋求全局優(yōu)化的新方法. 果蠅本身在感官知覺上優(yōu)于其它物種， 尤其是在嗅覺與視覺上. 果蠅通過其嗅覺器官搜集飄浮在空氣中的各種氣味， 然后飛近食物位置， 同時使用敏銳的視覺發(fā)現(xiàn)食物與同伴聚集的位置， 并且往該方向飛去. 記待優(yōu)化的函數(shù)為

minf(x1,x2,…,xn), (x1,x2,…,xn)∈S.

依據(jù)果蠅搜索食物的過程， 可將果蠅優(yōu)化算法歸納為以下幾個必要的步驟[1-2]：

1) 初始化： 設(shè)置群體規(guī)模sizepop， 最大迭代次數(shù)maxgen及步長step， 初始化果蠅群體位置X_axis,Y_axis為初始區(qū)間內(nèi)的隨機點.

2) 生成初始種群

其中，i=1,2,…,sizepop.

3) 由于無法得知食物位置， 因此先估計與原點之距離Di， 再計算味道濃度判定值Si.

4) 將味道濃度判定值Si代入味道濃度判定函數(shù)(對應(yīng)于適應(yīng)度函數(shù))， 用來求出果蠅個體的味道濃度Smelli(對應(yīng)于適應(yīng)值).

Smelli=f(Si).

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

其中，bestSmell為Smell中的最佳味道濃度(即最小適應(yīng)值)，bestindex為該最佳味道濃度對應(yīng)果蠅的編號.

6) 記錄并保留最佳味道濃度值bestSmell與其X,Y坐標(biāo)， 這時候果蠅群體利用視覺向該位置飛去.

Y_axis=Y(bestindex).

7) 進入迭代尋優(yōu)， 重復(fù)執(zhí)行步驟2)～5)， 并判斷最佳味道濃度bestSmell是否優(yōu)于前一迭代最佳味道濃度Smellbest， 并且當(dāng)前迭代次數(shù)小于最大迭代數(shù)maxgen； 若是則執(zhí)行步驟6).

2 基于自適應(yīng)搜索步長的改進FOA算法

果蠅優(yōu)化算法模擬果蠅的覓食行為， 利用敏銳的嗅覺感知食物的方向， 迅速靠近食物， 同時利用視覺發(fā)現(xiàn)處在更好位置的同伴， 并聚集到其周圍. 如果該點是局部極值， 此時， 果蠅群體需憑借其嗅覺跳出局部極值. 標(biāo)準(zhǔn)果蠅優(yōu)化算法(SFOA)中， 由于采用固定步長， 限制了果蠅群體的勘探能力， 種群極易陷于局部極值， 使優(yōu)化過程停滯. 研究表明， 采用動態(tài)步長能夠有效提高算法的優(yōu)化速度和精度[9].

本文提出的自適應(yīng)變步長FOA算法(FOABASS)采用隨迭代次數(shù)和全局最優(yōu)個體的二維坐標(biāo)變化的動態(tài)步長生成果蠅個體， 由于其在較大的范圍內(nèi)動態(tài)變化， 使得果蠅群體兼具較強的全局勘探和局部開發(fā)能力.

2.1 動態(tài)步長

果蠅的覓食能力和果蠅群體的密集程度有關(guān)， 群體越松散， 果蠅的勘探能力越強， 就能夠更快速地靠近食物； 群體越密集， 果蠅的開發(fā)能力就越強， 就能更精確地定位食物的位置. 優(yōu)化算法的性能取決于算法全局勘探和局部開發(fā)能力的平衡. 果蠅群體的密集程度由搜索步長決定， 標(biāo)準(zhǔn)果蠅優(yōu)化算法中， 一旦找到更好的位置， 使用固定的步長生成果蠅個體， 在此位置附近展開進一步的搜索， 使得果蠅個體只能在以當(dāng)前最優(yōu)位置為中心， 以步長step為半徑的區(qū)域進行搜索， 該機制給FOA算法提供了足夠的局部開發(fā)能力和有限的全局勘探能力.

在SFOA算法中， 果蠅個體位置由群體的當(dāng)前位置以及一個隨機偏移量決定.

其中，randvalue1=2*step1*rand1-step1，randvalue2=2*step2*rand2-step2,rand1,rand2是兩個不同的隨機數(shù). SFOA中，step1,step2為定值， 且step1=step2.

由第i個果蠅確定的參數(shù)為

由果蠅群體位置確定的參數(shù)為

可見， 可通過改變X_axis,randvalue1以及Y_axis,randvalue2的相對大小來控制Si和S的距離. 考慮兩種極端的情況： 當(dāng)X_axis/randvalue1=-1，Y_axis/randvalue2=-1時， 第i個果蠅個體(Xi,Yi)距離群體位置(X_axis,Y_axis)無窮遠， 由它們所確定的Si和S的距離最遠， 意味著算法具有無限的全局勘探能力； 當(dāng)|X_axis/randvalue1|→∞， |Y_axis/randvalue2|→∞時， 第i個果蠅個體(Xi,Yi)無限靠近群體位置(X_axis,Y_axis)，Si和S的距離最近， 意味著算法具有無限的局部開發(fā)能力. 如果置

step2=rand(1,n)*Y_axis.

這樣， 果蠅種群的搜索半徑就可實現(xiàn)從(0,∞)變化.

2.2 步長調(diào)節(jié)系數(shù)

在優(yōu)化過程的不同階段， 算法應(yīng)具有不同的全局勘探能力和局部開發(fā)能力， 一般說來， 在優(yōu)化過程的初期， 算法應(yīng)具備較強的全局勘探能力， 在優(yōu)化過程的后期， 算法應(yīng)具備較強的局部開發(fā)能力. 為此， 令

其中， 步長調(diào)節(jié)系數(shù)w隨優(yōu)化迭代次數(shù)的增加而逐漸減小， 經(jīng)實驗， 令其初值為2， 終值為0.25. 如圖 1 所示.

式中：g為當(dāng)前進化代數(shù)；maxgen為最大迭代代數(shù)；α=3.

3 仿真實驗及結(jié)果分析

為了驗證基于自適應(yīng)步長的改進FOA算法的優(yōu)化性能， 本文對9個基準(zhǔn)測試函數(shù)進行了求最小值問題的優(yōu)化仿真實驗， 測試函數(shù)名稱、 表達式、 定義域、 維數(shù)、 理論極值、 目標(biāo)極值見表 1.

為驗證FOABASS算法的性能， 設(shè)計了3個實驗與SFOA算法、 反向認知的高效果蠅算法(BWFOA)[5]、 基于歷史認知的果蠅優(yōu)化算法(FOABHC)[6]進行比較.

參數(shù)設(shè)置為： 置種群規(guī)模sizepop=15， 最大迭代代數(shù)maxgen=150， 初始化果蠅群體位置為定義域中的任意位置， 標(biāo)準(zhǔn)FOA算法中搜索步長step=1. 這里把將(5)， (6)所確定的算法記為算法Ⅰ， 把式(5)～式(8)所確定的算法即FOABASS算法記為算法Ⅱ.

表 1 測試函數(shù)

表 2 給出了各算法獨立運行20次后的平均優(yōu)化結(jié)果. 其中， 最好解、 最差解、 平均值、 標(biāo)準(zhǔn)差分別是獨立運行20次得到的最小優(yōu)化結(jié)果、 最大優(yōu)化結(jié)果、 優(yōu)化結(jié)果的平均值、 標(biāo)準(zhǔn)差； 成功率是達到目標(biāo)極值的運行次數(shù)/總的試驗次數(shù)； 平均迭代次數(shù)是達到目標(biāo)極值的迭代次數(shù)平均值.

表 2 FOABASS算法與SFOA的性能比較

從表 2 可以看出， 對9個測試函數(shù)， 算法Ⅰ和算法Ⅱ的優(yōu)化結(jié)果全面優(yōu)于標(biāo)準(zhǔn)果蠅優(yōu)化算法SFOA. 算法Ⅱ?qū)?sphere, rastrigrin, ackley等3個函數(shù)的優(yōu)化結(jié)果平均值略劣于算法Ⅰ， 占全部測試函數(shù)的33.3%； 對Schaffer函數(shù)的優(yōu)化結(jié)果與算法Ⅰ完全相同， 占11.1%； 對其它5個函數(shù)的優(yōu)化結(jié)果平均值優(yōu)于算法Ⅰ， 占全部測試函數(shù)的55.6%. 除函數(shù)easom, michalewicz以外， 算法Ⅱ達到目標(biāo)值所需的平均迭代次數(shù)要少于算法Ⅰ， 占全部測試函數(shù)的77.8%.

圖 2～圖 4 分別給出了函數(shù)ackley, rastrigin, branins的適應(yīng)度隨迭代次數(shù)變化的進化曲線.

圖 2 ackley函數(shù)適應(yīng)度進化曲線Fig.2 The fitness curve of ackley

圖 3 rastrigin函數(shù)適應(yīng)度進化曲線Fig.3 The fitness curve of rastrigin

為了便于比較， 3種算法從相同初始點出發(fā)開始尋優(yōu). 3個函數(shù)ackley, rastrigin, branins的適應(yīng)度的最小值分別為0, 0, 0.397 887， 有兩點很清楚， 一是算法Ⅰ和算法Ⅱ在收斂速度和精度上要優(yōu)于SFOA算法； 二是在優(yōu)化過程初期， 算法Ⅱ的收斂速度更快.

圖 4 branins函數(shù)適應(yīng)度進化曲線Fig.4 The fitness curve of branins

表 3 給出了FOABASS與反向認知的果蠅優(yōu)化算法(BWFOA)優(yōu)化結(jié)果平均值的仿真結(jié)果, BWFOA的優(yōu)化結(jié)果取自文獻[5]. 種群規(guī)模sizepop=15， 最大迭代次數(shù)maxgen=150. FOABASS的優(yōu)化結(jié)果取自表 2. FOABASS對4個函數(shù)的優(yōu)化結(jié)果均優(yōu)于BWFOA.

表 3 FOABASS與BWFOA算法優(yōu)化結(jié)果平均值的比較

表 4 給出了FOABASS算法和基于歷史認知的果蠅優(yōu)化算法(FOABHC)的仿真結(jié)果, FOABHC的優(yōu)化結(jié)果取自文獻[6]. 種群規(guī)模sizepop=15， 最大迭代次數(shù)maxgen=200. 表中FOABASS算法對 sphere函數(shù)的優(yōu)化結(jié)果平均值略劣于FOABHC算法， 對函數(shù)schaffer、 griewank、 rastrigrin的優(yōu)化結(jié)果與FOABHC算法相同； 對其它兩個函數(shù)rosenbrock, ackley的優(yōu)化結(jié)果平均值優(yōu)于FOABHC算法.

表 4 FOABASS算法與FOABHC算法優(yōu)化結(jié)果平均值的比較

4 結(jié) 論

本文在對標(biāo)準(zhǔn)果蠅優(yōu)化算法中果蠅個體生成機制進行深入分析的基礎(chǔ)上， 針對固定搜索步長下SFOA算法尋優(yōu)速度慢， 收斂精度不高， 容易陷于局部極值的不足， 提出了一種基于自適應(yīng)步長的改進FOA算法(FOABASS)， 新算法采用隨種群當(dāng)前位置、 當(dāng)前優(yōu)化代數(shù)變化而變化的可變搜索步長生成果蠅個體， 使得果蠅群體具備較強的全局勘探能力， 同時兼顧了全局勘探能力和局部開發(fā)能力的平衡. 對9個典型測試函數(shù)的優(yōu)化仿真結(jié)果表明， FOABASS算法較SFOA算法和其它幾種改進FOA算法具有更好的優(yōu)化性能. 需要進一步研究的工作有： ① 對自適應(yīng)步長果蠅優(yōu)化算法的穩(wěn)定性進行分析； ② 對果蠅優(yōu)化算法的收斂性進行分析； ③ 對步長調(diào)節(jié)系數(shù)w的遞減模型做進一步的研究.

[1]潘文超. 應(yīng)用果蠅優(yōu)化算法優(yōu)化廣義回歸神經(jīng)網(wǎng)絡(luò)進行企業(yè)經(jīng)營績效評估[J]. 太原理工大學(xué)學(xué)報(社會科學(xué)版), 2011, 29(4)： 1-5. Pan Wenchao. Using fruit fly optimization algorithm optimized general regression neural network to construct the operating performance of enterprises model[J]. Journal of Taiyuan University of Technology(Social Sciences Edition), 2011, 29(4)： 1-5. (in Chinese)

[2]Pan Wenchao. A new fruit fly optimization algorithm： taking the financial distress model as an example[J]. Knowledge-Based Systems, 2012, 26： 69-74.

[3]Yuan Xiaofang, Dai Xiangshang, Zhao Jingyi, et al. On a novel multi-swarm fruit fly optimization algorithm and its application[J]. Applied Mathematics and Computation, 2014, 233： 260-271.

[4]韓俊英, 劉成忠. 自適應(yīng)混沌果蠅優(yōu)化算法[J]. 計算機應(yīng)用, 2013(5)： 1313-1316, 1333. Han Junying, Liu Chengzhong. Adaptive chaos fruit fly optimization algorithm[J]. Journal of Computer Applications, 2013(5)： 1313-1316, 1333. (in Chinese)

[5]韓俊英, 劉成忠. 反向認知的高效果蠅優(yōu)化算法[J]. 計算機工程, 2013, 39(11)： 223-225. Han Junying, Liu Chengzhong. Efficient fruit fly optimization algorithm with reverse cognition[J]. Computer Engineering. 2013, 39(11)： 223-225. (in Chinese)

[6]韓俊英, 劉成忠. 基于歷史認知的果蠅優(yōu)化算法[J]. 計算機科學(xué)與技術(shù), 2014, 8(3)： 368-375. Han Junying, Liu Chengzhong. Fruit fly optimization algorithm based on history cognition[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(3)： 368-375. (in Chinese)

[7]Scan H, Gunduz M. Parameter analysis on fruit fly optimization algorithm[J]. Journal of Computer and Communications, 2014(2)： 137-141.

[8]韓俊英, 劉成忠. 自適應(yīng)調(diào)整參數(shù)的果蠅優(yōu)化算法[J]. 計算機工程與應(yīng)用, 2014(7)： 50-55. Han Junying, Liu Chengzhong. Fruit fly optimization algorithm with adaptive parameter[J]. Computer Engineering and Applications, 2014(7)： 50-55. (in Chinese)

[9]Pan Quanke, Sang Hongyan, Duan Junhua, et al. An improved fruit fly optimization algorithm for continuous function optimization problems [J]. Knowledge-Based Systems, 2014, 62： 69-83.

[10]史東亞, 陸鍵, 陸林軍. 基于RFID技術(shù)和FOA-GRNN理論的高速公路道路關(guān)閉交通事件對車輛影響的判斷模型[J]. 武漢理工大學(xué)學(xué)報, 2012, 34(3)： 63-68. Shi Dongya, Lu Jian, Lu Linjun. A judge model of the impact of lane closure incident on individual vehicles on free ways based on RFID technology and FOA-GRNN method[J]. Journal of Wuhan University of Technology, 2012, 34(3)： 63-68. (in Chinese)

[11]王欣, 杜康, 秦斌, 等. 基于果蠅優(yōu)化算法的LSSVR干燥速率建模[J]. 控制工程, 2012 19(4)： 630-633. Wang Xin, Du Kang, Qin Bin, et al. Drying rate modeling based on FOALSSVR[J]. Control Engineering of China, 2012 19(4)： 630-633. (in Chinese)

[12]Li Chunquan, Xu Shaoping, Li Wen, et al. A novel modified fly optimization algorithm for designing the self-tuning proportional integral derivative controller[J]. Journal of Convergence Information Technology(JCIT), 2012, 7(16)： 69-77.

[13]李泓澤, 郭森, 李春杰. 果蠅優(yōu)化最小二乘支持向量機混合預(yù)測模型[J]. 經(jīng)濟數(shù)學(xué), 2012, 29(3)： 103-106. Li Hongze, Guo Sen, Li Chunjie. A hybrid forecasting model based on fruit fly optimization algorithm and least squares support vector machine： the case of logistics demand forecasting of China[J]. Journal of Quantitative Economics, 2012, 29(3)： 103-106. (in Chinese)

Fruit Fly Optimization Algorithm Based on Adaptive Step Size

GUO Xiao-dong1,2, WANG Li-fang3, ZHANG Xue-liang2

(1. College of Electronic Information and Engineering, Taiyuan University of Science and Technology, Taiyuan 030024, China； 2. College of Mechanical Engineering， Taiyuan University of Science and Technology, Taiyuan 030024, China 3. Complex System and Computational Intelligence Laboratory, Taiyuan University of Science and Technology, Taiyuan 030024, China)

Considering the premature convergence problems of slow optimizing speed, low convergence precision and easy local extremum for standard fruit fly optimization algorithm(SFOA) with the fixed-length step, a new FOA based on adaptive step size, named FOABASS, was presented by analyzing the relation of step size and searching ability of fruit fly. In FOABASS, the step size in search was created on the condition of dynamic step size which varies with current swarm location and evolution generation. Then, the high capacity of new algorithm for finding the global optimum and the balance between global exploration and local exploitation ability was obtained. Finally, simulation results of FOABASS, SFOA algorithm and other modified version show the superiority and the effectiveness of FOABASS.

fruit fly optimization algorithm; function optimization; adaptive step size; local extremum

1673-3193(2016)06-0570-06

2015-05-06

太原科技大學(xué)博士科研啟動基金資助項目(20122009)； 山西省優(yōu)秀研究生創(chuàng)新項目(20113121)； 國家自然科學(xué)基金青年項目(61003053)

郭曉東(1977-)， 男， 講師， 博士生， 主要從事智能計算與智能控制的研究.

TP18

A

10.3969/j.issn.1673-3193.2016.06.004