郭曉東， 王麗芳， 張學良

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

?

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

郭曉東1,2， 王麗芳3， 張學良2

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

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

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

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

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

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

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

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

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

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

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

2) 生成初始種群

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

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

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

Smelli=f(Si).

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

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

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

Y_axis=Y(bestindex).

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

2 基于自適應搜索步長的改進FOA算法

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

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

2.1 動態(tài)步長

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

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

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

由第i個果蠅確定的參數為

由果蠅群體位置確定的參數為

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

step2=rand(1,n)*Y_axis.

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

2.2 步長調節(jié)系數

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

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

式中：g為當前進化代數；maxgen為最大迭代代數；α=3.

3 仿真實驗及結果分析

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

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

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

表 1 測試函數

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

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

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

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

圖 2 ackley函數適應度進化曲線Fig.2 The fitness curve of ackley

圖 3 rastrigin函數適應度進化曲線Fig.3 The fitness curve of rastrigin

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

圖 4 branins函數適應度進化曲線Fig.4 The fitness curve of branins

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

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

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

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

4 結 論

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

[1]潘文超. 應用果蠅優(yōu)化算法優(yōu)化廣義回歸神經網絡進行企業(yè)經營績效評估[J]. 太原理工大學學報(社會科學版), 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ōu)化算法[J]. 計算機應用, 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]. 計算機科學與技術, 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ōu)化算法[J]. 計算機工程與應用, 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技術和FOA-GRNN理論的高速公路道路關閉交通事件對車輛影響的判斷模型[J]. 武漢理工大學學報, 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)化最小二乘支持向量機混合預測模型[J]. 經濟數學, 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

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

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

TP18

A

10.3969/j.issn.1673-3193.2016.06.004