您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（工学版）》

山东大学学报 (工学版) ›› 2019, Vol. 49 ›› Issue (3): 22-31.doi: 10.6040/j.issn.1672-3961.0.2017.418

• 机器学习与数据挖掘 • 上一篇    下一篇

一种新的双策略进化果蝇优化算法

方波1,2(),陈红梅1,2,*()   

  1. 1. 西南交通大学信息科学与技术学院, 四川 成都 611756
    2. 云计算与智能技术高校重点实验室(西南交通大学), 四川 成都 611756
  • 收稿日期:2017-08-24 出版日期:2019-06-20 发布日期:2019-06-27
  • 通讯作者: 陈红梅 E-mail:fangbo@my.swjtu.edu.cn;hmchen@swjtu.edu.cn
  • 作者简介:方波(1991-),男,浙江杭州人,硕士研究生,主要研究方向为数据挖掘,机器学习. fangbo@my.swjtu.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(61572406)

A novel double strategies evolutionary fruit fly optimization algorithm

Bo FANG1,2(),Hongmei CHEN1,2,*()   

  1. 1. School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, Sichuan, China
    2. Key Laboratory of Cloud Computing and Intelligent Technology (Southwest Jiaotong University), Chengdu 611756, Sichuan, China
  • Received:2017-08-24 Online:2019-06-20 Published:2019-06-27
  • Contact: Hongmei CHEN E-mail:fangbo@my.swjtu.edu.cn;hmchen@swjtu.edu.cn
  • Supported by:
    国家自然科学基金资助项目(61572406)

RichHTML

4

PDF (PC)

227

摘要：

标准果蝇优化算法(fruit fly optimization algorithm, FOA)在迭代寻优的过程中,整个果蝇群体只向最优个体靠近,这导致算法极易陷入局部最优,从而引起早熟收敛的问题。针对该问题,提出一种新的双策略进化果蝇优化算法(a novel double strategies evolutionary fruit fly optimization algorithm, DSEFOA)。提出的一种新的群体分割策略,将果蝇群体动态地划分为精英子群和普通子群;对于精英子群,引入混沌变量引导果蝇个体在其附近搜索食物,优化其局部搜索能力;对于普通子群,引入权重因子改进标准FOA的随机搜索方式,执行全局搜索,加快收敛速度。DSEFOA算法针对不同进化水平的果蝇个体采用不同的策略更新进化,充分地提升了整个群体的寻优搜索能力。8个测试函数的仿真试验结果表明, DSEFOA算法有比标准FOA算法更好的优化性能。

关键词: 果蝇优化算法, 群体分割策略, 混沌变量, 权重因子

Abstract:

The problem of premature convergence caused by trapping into local optimum, which resulted form the fact that all the individuals were only attracted by the best one in the standard fruit fly optimization algorithm (FOA), was common. In order to overcome this demerit, a novel double strategies evolutionary fruit fly optimization algorithm (DSEFOA) was proposed. The whole group was divided into elite subgroup and ordinary subgroup dynamically based on a proposed new group partitioning strategy. Then an improved searching method with chaotic variable was used in the elite subgroup to improve the individual's local searching capability. Meanwhile, an improved standard FOA-based random searching method with weighting factors was used in the ordinary subgroup to enhance its global searching capability, as well accelerated the convergence. The searching capability of both superior and inferior individuals could be effectively improved in DSEFOA by using different strategies on different evolutionary levels of these individuals. The experimental results showed that DSEFOA had better optimization performance than the standard FOA.

Key words: fruit fly optimization algorithm, group partitioning strategy, chaotic variable, weighting factor

中图分类号: 

  • TP301.6

表1

8个基准测试函数"

函数 函数形式 搜索区间 最优值
Sphere ${f_1}(x) = \sum\limits_{i = 1}^n {x_i^2} $ [-100, 100] 0
Schwefels problem 2.22 ${f_2}(x) = \sum\limits_{i = 1}^n {\left| {{x_i}} \right|} + \prod\limits_{i = 1}^n {\left| {{x_i}} \right|} $ [-10, 10] 0
Exponential problem ${f_3}(x) = 1- \exp \left({ - 0.5\sum\limits_{i = 1}^n {x_i^2} } \right)$ [-1, 1] 0
Sum of different power ${f_4}(x) = \sum\limits_{i = 1}^n {{{\left| {{x_i}} \right|}^{i + 1}}} $ [-1, 1] 0
Rastrigin ${f_5}(x) = \sum\limits_{i = 1}^n {\left[{x_i^2- 10\cos \left({2\pi {x_i}} \right) + 10} \right]} $ [-5.12，5.12] 0
Griewank ${f_6}(x) = 1 + \frac{1}{{4000}}\sum\limits_{i = 1}^n {x_i^2} - \prod\limits_{i = 1}^n {\cos } \left({\frac{{{x_i}}}{{\sqrt i }}} \right)$ [-600, 600] 0
Diff griewank ${f_7}(x) = |\sum\limits_{i = 1}^n {{{\left[{\sin \left({{x_i}} \right)} \right]}^2}} - 0.1\prod\limits_{i = 1}^n {\exp } \left({ - x_i^2} \right) + 0.1$ [-10, 10] 0
Ackley $\begin{array}{l}{f_8}(x) = 20 + e - 20\exp \left({ - 0.2\sqrt {\frac{1}{n}\sum\limits_{i = 1}^n {x_i^2} } } \right) - \\\; \; \; \; \; \; \; \; \; \; \; \; \exp \left[{- \frac{1}{n}\sum\limits_{i = 1}^n {\cos } \left({2\pi {x_i}} \right)} \right]\end{array}$ [-32, 32] 0

图1

群体规模与函数优化均值关系曲线"

表2

较低迭代次数下算法试验结果"

函数 维数 算法 最优值 优化均值 标准差
] f1 30 DSEFOA 4.906 4×10-05 7.583 3×10-05 1.576 6×10-05
FOA 1.332 8×10-03 2.001 4×10-03 5.161 1×10-04
CFOA 2.769 6×10-04 3.685 5×10-04 9.093 3×10-05
PSO 0.524 8 2.523 6 1.916 6
f2 30 DSEFOA 1.876 0×10-02 2.128 1×10-02 1.719 0×10-03
FOA 0.176 2 0.218 4 2.496 4×10-02
CFOA 7.514 7×10-02 9.291 0×10-02 1.146 2×10-02
PSO 2.215 0 6.540 9 2.862 9
f3 30 DSEFOA 2.101 7×10-05 4.174 4×10-05 1.229 3×10-05
FOA 5.276 6×10-04 9.409 7×10-04 2.027 9×10-04
CFOA 1.409 1×10-04 2.136 4×10-04 5.749 3×10-05
PSO 2.923 9×10-03 1.309 6×10-02 9.455 6×10-03
f4 30 DSEFOA 6.084 6×10-04 9.523 1×10-04 2.930 3×10-04
FOA 2.595 0×10-03 4.555 1×10-03 1.609 3×10-03
CFOA 1.296 7×10-02 2.215 1×10-02 7.545 1×10-03
PSO 1.463 7×10-06 1.017 3×10-03 1.805 7×10-03
f5 30 DSEFOA 1.121 2×10-02 1.792 3×10-02 4.067 9×10-03
FOA 0.265 7 0.394 1 8.265 5×10-02
CFOA 0.143 1 0.293 3 8.938 3×10-02
PSO 36.601 0 104.530 2 34.715 6
f6 30 DSEFOA 6.140 6×10-10 1.379 0×10-09 3.207 5×10-10
FOA 8.604 7×10-06 1.32 37×10-05 2.982 0×10-06
CFOA 2.936 3×10-09 5.800 9×10-09 2.573 8×10-09
PSO 0.713 4 1.036 9 0.149 5
f7 30 DSEFOA 1.306 3×10-05 2.3402×10-05 5.3770×10-06
FOA 1.092 4×10-03 2.137 4×10-03 6.1559×10-04
CFOA 2.602 8×10-04 4.572 8×10-04 1.0832×10-04
PSO 2.191 5 4.571 0 1.478 0
f8 30 DSEFOA 7.922 2×10-04 1.031 9×10-03 1.530 3×10-04
FOA 2.856 8×10-02 3.627 5×10-02 4.780 2×10-03
CFOA 3.241 4×10-03 4.454 3×10-03 7.805 0×10-04
PSO 4.414 2 6.001 1 1.056 1

图2

较低迭代次数下函数优化均值进化曲线"

表3

较高迭代次数下算法试验结果"

函数 维数 算法 最优值 优化均值 标准差
f1 30 DSEFOA 9.330 2×10-06 1.363 3×10-05 3.008 6×10-06
FOA 2.091 4×10-04 3.501 9×10-04 8.792 5×10-05
CFOA 3.290 5×10-05 5.741 7×10-05 1.366 6×10-05
f2 30 DSEFOA 7.266 0×10-03 8.570 6×10-03 5.729 2×10-04
FOA 7.252 9×10-02 8.982 6×10-02 1.023 5×10-02
CFOA 3.004 6×10-02 3.992 1×10-02 4.257 0×10-03
f3 30 DSEFOA 4.794 0×10-06 6.722 9×10-06 1.307 9×10-06
FOA 9.663 5×10-05 1.583 8×10-04 4.095 6×10-05
CFOA 2.058 8×10-05 3.228 9×10-05 8.965 8×10-06
f4 30 DSEFOA 1.812 1×10-04 3.712 5×10-04 1.364 7×10-04
FOA 9.584 0×10-04 1.875 9×10-03 5.559 2×10-04
CFOA 5.035 8×10-03 8.204 6×10-03 3.094 1×10-03
f5 30 DSEFOA 1.724 8×10-03 2.801 3×10-03 5.114 3×10-04
FOA 4.317 4×10-02 6.579 5×10-02 1.197 3×10-02
CFOA 2.700 4×10-02 4.679 4×10-02 1.574 7×10-02
f6 30 DSEFOA 1.304 7×10-10 2.330 6×10-10 9.277 2×10-11
FOA 5.150 0×10-06 9.087 3×10-06 1.991 0×10-06
CFOA 5.904 7×10-10 8.880 0×10-10 2.358 6×10-10
f7 30 DSEFOA 2.564 2×10-06 3.969 3×10-06 1.161 8×10-06
FOA 1.994 6×10-04 3.592 8×10-04 9.645 4×10-05
CFOA 4.327 5×10-05 7.419 0×10-05 1.858 5×10-05
f8 30 DSEFOA 3.382 7×10-04 4.384 4×10-04 6.702 1×10-05
FOA 1.061 5×10-02 1.365 9×10-02 1.635 3×10-03
CFOA 1.270 0×10-03 1.838 4×10-03 2.723 4×10-04

图3

较高迭代次数下函数优化均值进化曲线"

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 潘文超. 果蝇最佳化演算法[M]. 台中,中国: 沧海书局, 2011: 10- 12.
3 KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of ICNN'95: (IEEE International Conference on Neural Networks). Perth, Australia: IEEE, 1995: 1942-1948.
4 DORIGO M , MANIEZZO V , COLORNI A . Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man, and Cybernetics: Part B (Cybernetics), 1996, 26 (1): 29- 41.
doi: 10.1109/3477.484436
5 潘文超. 应用果蝇优化算法优化广义回归神经网络进行企业经营绩效评估[J]. 太原理工大学学报(社会科学版), 2011, 29 (4): 1- 5.
doi: 10.3969/j.issn.1009-5837.2011.04.002
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.
doi: 10.3969/j.issn.1009-5837.2011.04.002
6 CAO G H , WU L J . Support vector regression with fruit fly optimization algorithm for seasonal electricity consumption forecasting[J]. Energy, 2016, 115 (1): 734- 745.
7 LI M W , GENG J , HAN D F , et al. Ship motion prediction using dynamic seasonal RvSVR with phase space reconstruction and the chaos adaptive efficient FOA[J]. Neurocomputing, 2016, 174 (3): 661- 680.
8 王欣, 杜康, 秦斌, 等. 基于果蝇优化算法的LSSVR干燥速率建模[J]. 控制工程, 2012, 19 (4): 630- 633, 638.
doi: 10.3969/j.issn.1671-7848.2012.04.021
WANG Xin , DU Kang , QIN Bin , et al. Drying rate modeling based on FOALSSVR[J]. Control Engineering of China, 2012, 19 (4): 630- 633, 638.
doi: 10.3969/j.issn.1671-7848.2012.04.021
9 ZHENG X L , WANG L , WANG S Y . A novel binary fruit fly optimization algorithm for the semiconductor final testing scheduling problem[J]. Knowledge-Based Systems, 2014, 57 (2): 95- 103.
10 韩俊英, 刘成忠. 自适应混沌果蝇优化算法[J]. 计算机应用, 2013, 33 (5): 1313- 1316, 1333.
HAN Junying , LIU Chengzhong . Adaptive chaos fruit fly optimization algorithm[J]. Journal of Computer Applications, 2013, 33 (5): 1313- 1316, 1333.
11 韩俊英, 刘成忠, 王联国, 等. 动态双子群协同进化果蝇优化算法[J]. 模式识别与人工智能, 2013, 26 (11): 1057- 1067.
doi: 10.3969/j.issn.1003-6059.2013.11.009
HAN Junying , LIU Chengzhong , WANG Lianguo , et al. Dynamic double subgroups cooperative fruit fly optimization algorithm[J]. Pattern Recognition and Artificial Intelligence, 2013, 26 (11): 1057- 1067.
doi: 10.3969/j.issn.1003-6059.2013.11.009
12 YUAN X F , DAI X S , ZHAO J Y , et al. On a novel multi-swarm fruit fly optimization algorithm and its application[J]. Applied Mathematics and Computation, 2014, 233 (3): 260- 271.
13 MITIC' M , VUKOVIC' N , PETROVIC' M , et al. Chaotic fruit fly optimization algorithm[J]. Knowledge-Based Systems, 2015, 89 (C): 446- 458.
14 韩虎. 果蝇优化算法的分析[J]. 计算机系统应用, 2017, 26 (2): 9- 17.
HAN Hu . Analysis on fruit fly optimization algorithm[J]. Computer Systems & Applications, 2017, 26 (2): 9- 17.
15 ZHANG Y W , CUI G M , WU J T , et al. A novel multi-scale cooperative mutation fruit fly optimization algorithm[J]. Knowledge-Based Systems, 2016, 114, 24- 35.
doi: 10.1016/j.knosys.2016.09.027
[1] 赵加敏,冯爱民*,刘学军. 局部密度嵌入的结构单类支持向量机[J]. 山东大学学报(工学版), 2012, 42(4): 13-18.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 陈瑞,李红伟,田靖. 磁极数对径向磁轴承承载力的影响[J]. 山东大学学报(工学版), 2018, 48(2): 81 -85 .
[2] 李可,刘常春,李同磊 . 一种改进的最大互信息医学图像配准算法[J]. 山东大学学报(工学版), 2006, 36(2): 107 -110 .
[3] 浦剑1 ,张军平1 ，黄华2 . 超分辨率算法研究综述[J]. 山东大学学报(工学版), 2009, 39(1): 27 -32 .
[4] 秦通,孙丰荣*,王丽梅,王庆浩,李新彩. 基于极大圆盘引导的形状插值实现三维表面重建[J]. 山东大学学报(工学版), 2010, 40(3): 1 -5 .
[5] 刘文亮,朱维红,陈涤,张泓泉. 基于雷达图像的运动目标形态检测及跟踪技术[J]. 山东大学学报(工学版), 2010, 40(3): 31 -36 .
[6] 王丽君,黄奇成,王兆旭 . 敏感性问题中的均方误差与模型比较[J]. 山东大学学报(工学版), 2006, 36(6): 51 -56 .
[7] 孙殿柱,朱昌志,李延瑞 . 散乱点云边界特征快速提取算法[J]. 山东大学学报(工学版), 2009, 39(1): 84 -86 .
[8] 岳远征. 远离平衡态玻璃的弛豫[J]. 山东大学学报(工学版), 2009, 39(5): 1 -20 .
[9] 程代展，李志强. 非线性系统线性化综述(英文)[J]. 山东大学学报(工学版), 2009, 39(2): 26 -36 .
[10] 李辉平, 赵国群, 张雷, 贺连芳. 超高强度钢板热冲压及模内淬火工艺的发展现状[J]. 山东大学学报(工学版), 2010, 40(3): 69 -74 .
版权所有 © 2018 《山东大学学报(工学版)》编辑部　
地址: 济南市山大南路27号（250100）　 电话: 0531-88366735　 E-mail: xbgxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发