基于自适应步长的果蝇优化算法

郭晓东， 王丽芳， 张学良

(1. 太原科技大学 电子信息工程学院， 山西太原 030024；2. 太原科技大学 机械工程学院，山西 太原 030024；3. 太原科技大学 复杂系统与计算智能实验室， 山西 太原 030024)



基于自适应步长的果蝇优化算法

郭晓东1,2， 王丽芳3， 张学良2

(1. 太原科技大学 电子信息工程学院， 山西太原 030024；2. 太原科技大学 机械工程学院，山西 太原 030024；3. 太原科技大学 复杂系统与计算智能实验室， 山西 太原 030024)

针对固定搜索步长下标准果蝇优化算法(SFOA)寻优速度慢， 收敛精度不高， 容易陷于局部极值的不足， 通过分析果蝇个体生成机制中搜索步长与算法搜索能力的关系， 提出了一种基于自适应步长的改进果蝇优化算法(FOABASS)， 在该算法中搜索步长随种群当前位置、 当前优化代数的变化而变化， 由此生成的果蝇群体具备较强的全局勘探能力， 同时兼顾全局勘探能力和局部开发能力的平衡. 最后给出了FOABASS算法和SFOA算法、 其它几种改进FOA算法的性能比较， 仿真结果表明了该算法的有效性.

果蝇优化算法； 函数优化； 自适应步长； 局部极值

果蝇优化算法 (Fruit Fly Optimization Algorithm， FOA)源于对果蝇觅食行为的模拟[1-2]， 由潘文超在2011年6月提出. 作为一类新的全局优化进化算法， FOA算法引起了许多学者的关注， 发展出了数个不同的改进版本， 如多群体果蝇优化算法[3]、 混沌果蝇优化算法[4]、 反向认知的果蝇优化算法[5]、 基于历史认知的果蝇优化算法[6]、 对FOA参数的研究[7-8]， 等. FOA算法已成功应用于广义回归神经网络参数优化[1]， 函数优化[9]， 高速公路道路关闭交通事件对车辆影响的判断模型[10]， LSSVR干燥速率建模[11]， PID控制器设计[12]、 最小二乘支持向量机参数优化[13]等科学与工程领域.

与其它群智能算法比较， FOA算法具有概念简单、 参数少、 易于实现、 运行速度快的特点. 另一方面， FOA算法的工作机理使得该算法容易陷入局部极值， 导致收敛速度变慢、 精度降低， 甚至优化失败.

本文介绍了FOA算法工作机理， 分析了导致FOA算法寻优速度慢， 收敛精度不高， 容易陷于局部极值的原因， 并给出了解决办法， 使用自适应步长来生成果蝇个体， 提出了一种基于自适应步长的改进FOA算法， 最后给出了该算法和标准FOA算法(SFOA)、 其它改进FOA算法的性能比较.

1 标准果蝇优化算法

果蝇优化算法是一种基于果蝇觅食行为推演出的寻求全局优化的新方法. 果蝇本身在感官知觉上优于其它物种， 尤其是在嗅觉与视觉上. 果蝇通过其嗅觉器官搜集飘浮在空气中的各种气味， 然后飞近食物位置， 同时使用敏锐的视觉发现食物与同伴聚集的位置， 并且往该方向飞去. 记待优化的函数为

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

依据果蝇搜索食物的过程， 可将果蝇优化算法归纳为以下几个必要的步骤[1-2]：

1) 初始化： 设置群体规模sizepop， 最大迭代次数maxgen及步长step， 初始化果蝇群体位置X_axis,Y_axis为初始区间内的随机点.

2) 生成初始种群

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

3) 由于无法得知食物位置， 因此先估计与原点之距离Di， 再计算味道浓度判定值Si.

4) 将味道浓度判定值Si代入味道浓度判定函数(对应于适应度函数)， 用来求出果蝇个体的味道浓度Smelli(对应于适应值).

Smelli=f(Si).

5) 找出该果蝇群体中味道浓度最佳的果蝇(最优个体) .

其中，bestSmell为Smell中的最佳味道浓度(即最小适应值)，bestindex为该最佳味道浓度对应果蝇的编号.

6) 记录并保留最佳味道浓度值bestSmell与其X,Y坐标， 这时候果蝇群体利用视觉向该位置飞去.

Y_axis=Y(bestindex).

7) 进入迭代寻优， 重复执行步骤2)～5)， 并判断最佳味道浓度bestSmell是否优于前一迭代最佳味道浓度Smellbest， 并且当前迭代次数小于最大迭代数maxgen； 若是则执行步骤6).

2 基于自适应搜索步长的改进FOA算法

果蝇优化算法模拟果蝇的觅食行为， 利用敏锐的嗅觉感知食物的方向， 迅速靠近食物， 同时利用视觉发现处在更好位置的同伴， 并聚集到其周围. 如果该点是局部极值， 此时， 果蝇群体需凭借其嗅觉跳出局部极值. 标准果蝇优化算法(SFOA)中， 由于采用固定步长， 限制了果蝇群体的勘探能力， 种群极易陷于局部极值， 使优化过程停滞. 研究表明， 采用动态步长能够有效提高算法的优化速度和精度[9].

本文提出的自适应变步长FOA算法(FOABASS)采用随迭代次数和全局最优个体的二维坐标变化的动态步长生成果蝇个体， 由于其在较大的范围内动态变化， 使得果蝇群体兼具较强的全局勘探和局部开发能力.

2.1 动态步长

果蝇的觅食能力和果蝇群体的密集程度有关， 群体越松散， 果蝇的勘探能力越强， 就能够更快速地靠近食物； 群体越密集， 果蝇的开发能力就越强， 就能更精确地定位食物的位置. 优化算法的性能取决于算法全局勘探和局部开发能力的平衡. 果蝇群体的密集程度由搜索步长决定， 标准果蝇优化算法中， 一旦找到更好的位置， 使用固定的步长生成果蝇个体， 在此位置附近展开进一步的搜索， 使得果蝇个体只能在以当前最优位置为中心， 以步长step为半径的区域进行搜索， 该机制给FOA算法提供了足够的局部开发能力和有限的全局勘探能力.

在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的距离最近， 意味着算法具有无限的局部开发能力. 如果置

step2=rand(1,n)*Y_axis.

这样， 果蝇种群的搜索半径就可实现从(0,∞)变化.

2.2 步长调节系数

在优化过程的不同阶段， 算法应具有不同的全局勘探能力和局部开发能力， 一般说来， 在优化过程的初期， 算法应具备较强的全局勘探能力， 在优化过程的后期， 算法应具备较强的局部开发能力. 为此， 令

其中， 步长调节系数w随优化迭代次数的增加而逐渐减小， 经实验， 令其初值为2， 终值为0.25. 如图 1 所示.

式中：g为当前进化代数；maxgen为最大迭代代数；α=3.

3 仿真实验及结果分析

为了验证基于自适应步长的改进FOA算法的优化性能， 本文对9个基准测试函数进行了求最小值问题的优化仿真实验， 测试函数名称、 表达式、 定义域、 维数、 理论极值、 目标极值见表 1.

为验证FOABASS算法的性能， 设计了3个实验与SFOA算法、 反向认知的高效果蝇算法(BWFOA)[5]、 基于历史认知的果蝇优化算法(FOABHC)[6]进行比较.

参数设置为： 置种群规模sizepop=15， 最大迭代代数maxgen=150， 初始化果蝇群体位置为定义域中的任意位置， 标准FOA算法中搜索步长step=1. 这里把将(5)， (6)所确定的算法记为算法Ⅰ， 把式(5)～式(8)所确定的算法即FOABASS算法记为算法Ⅱ.

表 1 测试函数

表 2 给出了各算法独立运行20次后的平均优化结果. 其中， 最好解、 最差解、 平均值、 标准差分别是独立运行20次得到的最小优化结果、 最大优化结果、 优化结果的平均值、 标准差； 成功率是达到目标极值的运行次数/总的试验次数； 平均迭代次数是达到目标极值的迭代次数平均值.

表 2 FOABASS算法与SFOA的性能比较

从表 2 可以看出， 对9个测试函数， 算法Ⅰ和算法Ⅱ的优化结果全面优于标准果蝇优化算法SFOA. 算法Ⅱ对 sphere, rastrigrin, ackley等3个函数的优化结果平均值略劣于算法Ⅰ， 占全部测试函数的33.3%； 对Schaffer函数的优化结果与算法Ⅰ完全相同， 占11.1%； 对其它5个函数的优化结果平均值优于算法Ⅰ， 占全部测试函数的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种算法从相同初始点出发开始寻优. 3个函数ackley, rastrigin, branins的适应度的最小值分别为0, 0, 0.397 887， 有两点很清楚， 一是算法Ⅰ和算法Ⅱ在收敛速度和精度上要优于SFOA算法； 二是在优化过程初期， 算法Ⅱ的收敛速度更快.

图 4 branins函数适应度进化曲线Fig.4 The fitness curve of branins

表 3 给出了FOABASS与反向认知的果蝇优化算法(BWFOA)优化结果平均值的仿真结果, BWFOA的优化结果取自文献[5]. 种群规模sizepop=15， 最大迭代次数maxgen=150. FOABASS的优化结果取自表 2. FOABASS对4个函数的优化结果均优于BWFOA.

表 3 FOABASS与BWFOA算法优化结果平均值的比较

表 4 给出了FOABASS算法和基于历史认知的果蝇优化算法(FOABHC)的仿真结果, FOABHC的优化结果取自文献[6]. 种群规模sizepop=15， 最大迭代次数maxgen=200. 表中FOABASS算法对 sphere函数的优化结果平均值略劣于FOABHC算法， 对函数schaffer、 griewank、 rastrigrin的优化结果与FOABHC算法相同； 对其它两个函数rosenbrock, ackley的优化结果平均值优于FOABHC算法.

表 4 FOABASS算法与FOABHC算法优化结果平均值的比较

4 结 论

本文在对标准果蝇优化算法中果蝇个体生成机制进行深入分析的基础上， 针对固定搜索步长下SFOA算法寻优速度慢， 收敛精度不高， 容易陷于局部极值的不足， 提出了一种基于自适应步长的改进FOA算法(FOABASS)， 新算法采用随种群当前位置、 当前优化代数变化而变化的可变搜索步长生成果蝇个体， 使得果蝇群体具备较强的全局勘探能力， 同时兼顾了全局勘探能力和局部开发能力的平衡. 对9个典型测试函数的优化仿真结果表明， FOABASS算法较SFOA算法和其它几种改进FOA算法具有更好的优化性能. 需要进一步研究的工作有： ① 对自适应步长果蝇优化算法的稳定性进行分析； ② 对果蝇优化算法的收敛性进行分析； ③ 对步长调节系数w的递减模型做进一步的研究.

[1]潘文超. 应用果蝇优化算法优化广义回归神经网络进行企业经营绩效评估[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]韩俊英, 刘成忠. 自适应混沌果蝇优化算法[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]韩俊英, 刘成忠. 反向认知的高效果蝇优化算法[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]韩俊英, 刘成忠. 基于历史认知的果蝇优化算法[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]韩俊英, 刘成忠. 自适应调整参数的果蝇优化算法[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]王欣, 杜康, 秦斌, 等. 基于果蝇优化算法的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]李泓泽, 郭森, 李春杰. 果蝇优化最小二乘支持向量机混合预测模型[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)； 山西省优秀研究生创新项目(20113121)； 国家自然科学基金青年项目(61003053)

郭晓东(1977-)， 男， 讲师， 博士生， 主要从事智能计算与智能控制的研究.

TP18

A

10.3969/j.issn.1673-3193.2016.06.004