改进萤火虫算法及其收敛性分析

doi:10.12305/j.issn.1001-506X.2022.04.27

摘要/Abstract

摘要：

萤火虫算法因具有结构简单、控制参数少、易于实现的特点而得到广泛的关注和应用, 但其易陷入局部最优导致过早收敛, 从而影响寻优精度。针对这一问题, 本文在位置更新规则中加入随机扰动因子, 并剔除了冗余的随机项, 以提高算法搜索能力; 引入位置置换变异和差分进化算法中的最优变异策略, 在保持种群多样性的同时, 增强算法跳出局部最优的能力。采用马尔可夫过程证明了算法以概率1收敛到全局最优。利用基准函数和装箱问题对算法进行仿真测试, 结果表明, 改进后的算法能够有效跳出局部最优, 对给出的所有问题均能找到理论最优解, 寻优精度和成功率有明显提升。

关键词: 萤火虫算法, 随机扰动, 变异策略, 马尔可夫过程, 函数优化, 装箱问题

Abstract:

The firefly algorithm has been widely concerned and applied because of its characteristics of simple structure, few control parameters and easy implementation, but it is easy to fall into local optimum, which leads to premature convergence and affects the optimization accuracy. To solve this problem, this paper adds a random factor into the individual location update rule to improve search capabilities, and the redundant random items are eliminated. To maintain the diversity of the population and enhance the capabilities of the algorithm to jump out of the local optimum, a position substitution mutation strategy and an optimal mutation strategy which come from the differential evolution algorithm are introduced. The Markov process is used to theoretically analyze the improved algorithm, and it is proved that the algorithm converges to the global optimum with probability of 1. The improved algorithm is simulated and tested using classic benchmark functions and the bin packing problem. Simulation results show that the improved algorithm can effectively jump out of the local optimum and find the theoretical optimal solution for all the given problems with better optimization accuracy and success rate.

Key words: firefly algorithm, stochastic disturbance, mutation strategy, Markov process, function optimization, bin packing problem

中图分类号:

N945.15

张大力, 夏红伟, 张朝兴, 马广程, 王常虹. 改进萤火虫算法及其收敛性分析[J]. 系统工程与电子技术, 2022, 44(4): 1291-1300.

Dali ZHANG, Hongwei XIA, Chaoxing ZHANG, Guangcheng MA, Changhong WANG. Improved firefly algorithm and its convergence analysis[J]. Systems Engineering and Electronics, 2022, 44(4): 1291-1300.

图/表 12

图1

图2

图3

图4

图5

表1

表2

表3

图6

图7

图8

表4

参考文献 32

1	GHAREHCHOPOGH F S , GHOLIZADEH H . A comprehensive survey: whale optimization algorithm and its applications[J]. Swarm and Evolutionary Computation, 2019, 48, 1- 24. doi: 10.1016/j.swevo.2019.03.004
2	COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]//Proc. of the First European Confe-rence on Artificial Life, 1991: 134-142.
3	KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proc. of the IEEE International Conference on Neural Networks, 1995: 1942-1948.
4	KARABOGA D , BASTURK B . A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39 (3): 459- 471. doi: 10.1007/s10898-007-9149-x
5	SAYADI M K , HAFEZALKOTOB A , NAINI S G J . Firefly-inspired algorithm for discrete optimization problems: an application to manufacturing cell formation[J]. Journal of Manufacturing Systems, 2013, 32 (1): 78- 84. doi: 10.1016/j.jmsy.2012.06.004
6	YANG X S . Nature-inspired metaheuristic algorithms[M]. Frome: Luniver Press, 2008.
7	DARWISH S M . Combining firefly algorithm and Bayesian clas-sifier: new direction for automatic multilabel image annotation[J]. IET Image Processing, 2016, 10 (10): 763- 772. doi: 10.1049/iet-ipr.2015.0492
8	张笑笑, 丁洁玉. 萤火虫算法求解多体系统动力学微分-代数方程[J]. 动力学与控制学报, 2021, 19 (2): 85- 90.
	ZHANG X X , DING J Y . Firefly algorithm for multi-body system dynamics differential-algebraic equations[J]. Journal of Dynamics and Control, 2021, 19 (2): 85- 90.
9	TRIPATHI S . A brief review of firefly algorithm: application in structural optimization problem[J]. Journal of the Institute of Engineering, 2020, 15 (2): 183- 191.
10	BABBAR A , PRAKASH C , GUPTA M K , et al. Application of hybrid nature-inspired algorithm: single and bi-objective constrained optimization of magnetic abrasive finishing process parameters[J]. Journal of Materials Research and Technology, 2020, 9 (4): 7961- 7974. doi: 10.1016/j.jmrt.2020.05.003
11	GANDOMI A H , YANG X S , TALATAHARI S , et al. Firefly algorithm with chaos[J]. Communications in Nonlinear Science and Numerical Simulation, 2013, 18 (1): 89- 98. doi: 10.1016/j.cnsns.2012.06.009
12	YU S H , YANG S L , SU S B . Self-adaptive step firefly algorithm[J]. Journal of Applied Mathematics, 2013, 832718.
13	ALTAY E Y , ULUTA G . Self-adaptive step firefly algorithm based robust watermarking method in DWT-SVD domain[J]. Multimedia Tools and Applications, 2021, 80, 23457- 23484. doi: 10.1007/s11042-020-10251-7
14	VERMA O P , AGGARWAL D , PATODI T . Opposition and dimensional based modified firefly algorithm[J]. Expert Systems with Applications, 2016, 44, 168- 176. doi: 10.1016/j.eswa.2015.08.054
15	MANJU A , NIGAM M J . An improved quantum inspired firefly algorithm with interpolation operator[J]. Advances in Intelligent Systems and Computing, 2014, 258, 69- 84.
16	柳长源, 任宇艳, 毕晓君. 基于改进萤火虫算法的区域交通信号配时优化[J]. 控制与决策, 2020, 35 (12): 2829- 2834.
	LIU C Y , REN Y Y , BI X J . Timing optimization of regional traffic signals based on improved firefly algorithm[J]. Control and Decision, 2020, 35 (12): 2829- 2834.
17	刘景森, 毛艺楠, 李煜. 具有振荡约束的自然选择萤火虫优化算法[J]. 控制与决策, 2020, 35 (10): 2363- 2371.
	LIU J S , MAO Y N , LI Y . Natural selection firefly optimization algorithm with oscillation and constraint[J]. Control and Decision, 2020, 35 (10): 2363- 2371.
18	WANG H , WANG W J , ZHOU X Y , et al. Firefly algorithm with neighborhood attraction[J]. Information Sciences, 2017, 382, 374- 387.
19	DHAL K G , DAS A , RAY S , et al. Randomly attracted rough firefly algorithm for histogram based fuzzy image clustering[J]. Knowledge-Based Systems, 2021, 216 (1): 106814.
20	SHAN J , PAN J S , CHANG C K , et al. A distributed parallel firefly algorithm with communication strategies and its application for the control of variable pitch wind turbine[J]. ISA Transactions, 2021, 115, 79- 94. doi: 10.1016/j.isatra.2021.01.026
21	ELAKKIYA E, SELVAKUMAR S, VELUSAMY R L. CIFAS: community inspired firefly algorithm with fuzzy cross-entropy for feature selection in Twitter Spam detection[C]//Proc. of the 11th International Conference on Computing, Communication and Networking Technologies, 2020.
22	ZHAO J , CHEN W P , XIAO R B , et al. Firefly algorithm with division of roles for complex optimal scheduling[J]. Frontiers of Information Technology and Electronic Engineering, 2021, 22 (10): 1311- 1333. doi: 10.1631/FITEE.2000691
23	XING H X , WU H , CHEN Y , et al. A cooperative interfe-rence resource allocation method based on improved firefly algorithm[J]. Defence Technology, 2021, 17 (4): 1352- 1360. doi: 10.1016/j.dt.2020.07.006
24	薛晗, 邵哲平, 潘家财, 等. 基于文化萤火虫算法-广义回归神经网络的船舶交通流量预测[J]. 上海交通大学学报, 2020, 54 (4): 421- 429.
	XUE H , SHAO Z P , PAN J C , et al. Vessel traffic flow prediction based on CFA-GRNN algorithm[J]. Journal of Shanghai Jiaotong University, 2020, 54 (4): 421- 429.
25	GUPTA D K , SONI A K , JHA A V , et al. Hybrid gravitational-firefly algorithm-based load frequency control for hydrothermal two-area system[J]. Mathematics, 2021, 9 (7): 712. doi: 10.3390/math9070712
26	CHENG Z W , SONG H H , CHANG T Z , et al. An improved mixed-coded hybrid firefly algorithm for the mixed-discrete SSCGR problem[J]. Expert Systems with Applications, 2022, 188, 116050. doi: 10.1016/j.eswa.2021.116050
27	XUE X S , CHEN J F . Optimizing sensor ontology alignment through compact co-firefly algorithm[J]. Sensors, 2020, 20 (7): 2056. doi: 10.3390/s20072056
28	WETS J B . Minimization by random search techniques[J]. Mathematics of Operations Research, 1981, 6 (1): 19- 30. doi: 10.1287/moor.6.1.19
29	刘晓东, 孙丽君, 陈天飞. 布谷鸟算法的收敛性分析及性能比较[J]. 计算机科学与探索, 2020, 14 (10): 1644- 1655. doi: 10.3778/j.issn.1673-9418.1912014
	LIU X D , SUN L J , CHEN T F . Convergence analysis and performance comparison of cuckoo search algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14 (10): 1644- 1655. doi: 10.3778/j.issn.1673-9418.1912014
30	JIAO B , LIAN Z G , GU X S . A dynamic inertia weight particle swarm optimization algorithm[J]. Chaos, Solitons & Fractals, 2008, 37 (3): 698- 705.
31	DAS S, KONAR A, CHAKRABORTY U K. Improved diffe-rential evolution algrithms for handling noisy optimization problems[C]//Proc. of the IEEE Congress on Evolutionary Computation, 2005: 1691-1698.
32	JOHNSON D S. Near-optimal bin packing algorithms[D]. Massachusetts: Massachusetts Institute of Technology, 1973.

函数名	数学表达式	规模	最优值
Sphere	$f_{1}(x)=\sum\limits_{i=1}^{D} x_{i}^{2}$	±100	0
Rosenbrock	$f_{2}(x)=\sum\limits_{i=1}^{D-1}\left[100\left(x_{i+1}-\right.\right.\left.\left.x_{i}^{2}\right)^{2}+\left(x_{i}-1\right)^{2}\right]$	±30	0
Rastrigin	$f_{3}(x)=\sum\limits_{i=1}^{D}\left[x_{i}^{2}-10 \cos \left(2 \pi x_{i}+10\right)\right]$	±5.12	0
Griewank	$f_{4}(x)=\frac{1}{4000} \sum\limits_{i=1}^{D} x_{i}^{2}-\prod\limits_{i=1}^{D} \cos \left(\frac{x_{i}}{\sqrt{i}}\right)+1$	±600	0

扰动因子	f₁			f₂			f₃			f₄
扰动因子	最优值	时间/s	SR/%	最优值	时间/s	SR/%	最优值	时间/s	SR/%	最优值	时间/s	SR/%
GIFA	2.301 3e-154	95.899 8	100	4.146 1e-09	82.201	0	0	15.544 3	10	0	24.261 5	10
CIFA	3.051 1e-109	41.303 4	100	0.001 065 2	46.112 3	0	60.357 1	17.461 3	0	0	24.782 4	50
LIFA	3.877 7e-105	534.637 7	100	1.060 1e-04	145.988 4	0	95.542 1	15.591 9	0	0	38.973 5	10
RIFA	0	25.457 8	100	1.384 9e-27	21.950 9	70	0	11.521 1	100	0	13.181 7	100

算法	f₁			f₂			f₃			f₄
算法	最优值	时间/s	SR/%	最优值	时间/s	SR/%	最优值	时间/s	SR/%	最优值	时间/s	SR/%
PSO	1.455 7e-57	2.909 6	100	19.565 6	2.373 9	0	26.863 9	2.149 3	0	3.330 7e-16	2.647 6	23.3
DE	5.758 9e-29	2.696 9	100	24.598 4	2.799 9	0	23.737 9	2.290 8	0	0	3.038 3	70
FA	8.378 4e-88	14.653 8	100	0.007 324 5	8.805 5	0	21.838 7	1.185	0	0	3.024 9	90
IFA	0	25.457 8	100	2.258 8e-26	21.950 9	70	0	11.521 1	100	0	13.181 7	100

参数	算法
参数	PSO	DE	FA	IFA
TT/s	43.070 4	13.112 2	21.155 9	22.640 1
CT/s	5.728 4	12.495 9	1.404 3	5.569 5
Best	7	7	7	6

[1]	汤安迪, 韩统, 徐登武, 周欢, 谢磊. 使用高斯分布估计策略的改进樽海鞘群算法[J]. 系统工程与电子技术, 2022, 44(7): 2229-2240.
[2]	陈发堂, 贾俊文, 张杰棠, 杨玲. 基于改进二维随机游动的跟踪区域列表优化[J]. 系统工程与电子技术, 2022, 44(2): 703-712.
[3]	来磊, 邹鲲, 吴德伟, 李保中. 交互策略改进MOFA进化的多UAV协同航迹规划[J]. 系统工程与电子技术, 2021, 43(8): 2282-2289.
[4]	来磊, 吴德伟, 邹鲲, 韩昆, 李海林. 基于多准则交互膜进化算法的UAV三维航迹规划[J]. 系统工程与电子技术, 2021, 43(1): 138-146.
[5]	李岩, 陈云翔, 罗承昆, 蔡忠义. 基于FA-ER的装备保障资源供给能力评估方法[J]. 系统工程与电子技术, 2020, 42(3): 630-637.
[6]	史跃东, 金家善, 徐一帆. 半马尔可夫跃迁历程下装备复杂系统多状态可靠性分析与评估[J]. 系统工程与电子技术, 2019, 41(2): 444-452.
[7]	冯晓, 郭霖瀚, 宋常浩, 孔丹丹. 基于CTMC族的多部件装备群稳态可用度建模方法[J]. 系统工程与电子技术, 2018, 40(6): 1405-1410.
[8]	王尔申, 张晴, 曲萍萍, 蓝晓宇, 庞涛, 姜毅. 基于马尔可夫过程的GNSS星座可用性评估[J]. 系统工程与电子技术, 2017, 39(4): 814-820.
[9]	殷蓓蓓, 方蕴宇, 宁高容, 王宾. 网络上的非对称信息对抗及其纳什策略[J]. 系统工程与电子技术, 2017, 39(10): 2270-2277.
[10]	崔锋哲, 王秀坤, 滕弘飞. 双系统合作式协同进化算法求解不可分解函数[J]. 系统工程与电子技术, 2016, 38(11): 2660-2669.
[11]	程美英，倪志伟，朱旭辉. 融合粗糙集和扩散二元萤火虫算法的属性约简方法[J]. 系统工程与电子技术, 2016, 38(10): 2449-2456.
[12]	陈洁钰，姚佩阳，王勃，税冬东. 基于结构熵和IGSO-BP算法的动态威胁评估[J]. 系统工程与电子技术, 2015, 37(5): 1076-1083.
[13]	范阳涛, 汪民乐, 文苗苗, 陈大雷. 基于萤火虫算法层次分析法的弹道导弹突防效能分析[J]. 系统工程与电子技术, 2015, 37(4): 845-850.
[14]	李牧东, 赵辉, 翁兴伟. 具有广泛学习策略的回溯搜索优化算法[J]. 系统工程与电子技术, 2015, 37(4): 958-963.
[15]	杨小龙, 谭学治. 认知无线电网络中授权用户参数估计[J]. 系统工程与电子技术, 2015, 37(2): 406-411.