一种正交反向学习萤火虫算法

周凌云; 丁立新; 马懋德; 唐菀

doi:10.11999/JEIT180187

一种正交反向学习萤火虫算法

doi: 10.11999/JEIT180187

周凌云^{1, 2},
丁立新^1, ,,
马懋德^{2, 3},
唐菀²

1.
武汉大学计算机学院武汉 430072
2.
中南民族大学计算机科学学院武汉 430074
3.
南洋理工大学电气电子工程学院新加坡 639798

基金项目: 国家自然科学基金(61379059)，中南民族大学中央高校基本科研业务费专项资金(CZY18012)

详细信息

作者简介:
周凌云：女，1979年生，讲师，研究方向为计算智能

丁立新：男，1967年生，教授，研究方向为计算智能与机器学习

马懋德：男，1957年生，教授，研究方向主要为无线网络

唐菀：女，1974年生，教授，研究方向主要为数据中心网络

通讯作者:
丁立新　lxding@whu.edu.cn

中图分类号: TP301.6
计量
- 文章访问数: 1734
- HTML全文浏览量: 865
- PDF下载量: 111
- 被引次数: 0
出版历程
- 收稿日期: 2018-02-10
- 修回日期: 2018-08-23
- 网络出版日期: 2018-08-29
- 刊出日期: 2019-01-01

Orthogonal Opposition Based Firefly Algorithm

Lingyun ZHOU^{1, 2},
Lixin DING^{1
, ,},
Maode MA^{2, 3},
Wan TANG²

1.
Computer School, Wuhan University, Wuhan 430072, China
2.
College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China
3.
School of Electrical and Electronic Engineering, Nanyang Technological University, 639798, Singapore

Funds: The National Natural Science Foundation of China (61379059), The Fundamental Research Funds for the Central Universities, South-Central University for Nationalities (CZY18012)

摘要

摘要:
针对萤火虫算法求解复杂优化问题时收敛精度较低的问题，该文提出一种正交反向学习策略，嵌入萤火虫算法，得到一种正交反向学习萤火虫算法。正交反向学习策略中，采用重心反向计算，利用群体搜索经验的同时避免搜索依赖坐标；采用正交试验设计，构建部分维上取反向值的正交反向候选解，充分挖掘个体和反向个体在不同维度上的有利信息。在标准测试集上进行验证，实验结果说明了正交反向学习策略的有效性。与多种新近的改进萤火虫算法相比，该算法在大多数函数上获得更高的求解精度。
- 萤火虫算法 /
- 反向学习 /
- 优化 /
- 正交试验设计 /
- 收敛精度
Abstract:
Firefly Algorithm (FA) may suffer from the defect of low convergence accuracy depending on the complexity of the optimization problem. To overcome the drawback, a novel learning strategy named Orthogonal Opposition Based Learning (OOBL) is proposed and integrated into FA. In OOBL, first, the opposite is calculated by the centroid opposition, making full use of the population search experience and avoiding depending on the system of coordinates. Second, the orthogonal opposite candidate solutions are constructed by orthogonal experiment design, combining the useful information from the individual and its opposite. The proposed algorithm is tested on the standard benchmark suite and compared with some recently introduced FA variants. The experimental results verify the effectiveness of OOBL and show the outstanding convergence accuracy of the proposed algorithm on most of the test functions.
- Firefly algorithm /
- Opposition-based learning /
- Optimization /
- Orthogonal experimental design /
- Convergence accuracy

HTML全文

图 1 试验解的构建

下载: 全尺寸图片幻灯片

图 2 FA与OOFA在函数f₁, f₄, f₉和f₁₂上的收敛曲线

下载: 全尺寸图片幻灯片

表 1 算法1：OOBL策略

输入：种群X，一个个体的索引ind和正交表L；
输出：新种群X。
步骤：
(1) 根据式(5)计算当前种群重心G；
(2) 根据式(6)计算指定个体的反向个体ox；
(3) 根据式(7)更新群体边界；根据式(8)对ox进行边界检查；
(4) for i=1: L的行数M
(5) 　for j=1: 问题维数D
(6)　　 if L(i, j)==1
(7)　　　oox(i, j)=X(ind, j)；
(8) 　　else
(9)　　　 oox(i, j)=ox( j)；
(10)　　end if
(11)　end for
(12) end for
(13) 评估正交反向候选解，评估次数FEs=FEs+M–1；
(14) 从X和正交反向候选解中选出适应值最优的N个个体。

下载: 导出CSV

表 2 算法2：OOFA算法

输入：目标函数；
输出：全局最优位置及适应值。
步骤：
(1) 随机初始化有N个个体的种群X；
(2) 评估初始种群f(X)，当前函数评估次数FEs=N；
(3) 根据种群适应值排序；
(4) 根据函数维数D，生成2水平D因素的正交表L；
(5) while 未达迭代终止条件
(6)　　 for i=1:N
(7)　　　 for j=1: i
(8) 　　　　根据式(1)和式(2)，第i个个体向第j个个体移位；
(9) 　　　end for
(10) 　end for
(11) 　对种群进行边界检查；
(12) 　评估种群，函数评估次数FEs=FEs+N；
(13) 　随机选择群体中一个个体，执行OOBL；
(14)　根据式(3)更新步长因子；
(15) end while

下载: 导出CSV

表 3 FA与OOFA的比较结果

函数	FA				OOFA				加速比R
函数	Mean	SD	FEs	T (s)	Mean	SD	FEs	T (s)	加速比R
f₁	5.16E+04	6.35E+03	80232	3.85	1.70E–10	8.44E–10	1091	0.03	73.54
f₂	7.30E+08	2.15E+08	72314	3.82	3.39E+07	1.04E+07	1704	0.06	42.44
f₃	4.74E+16	1.43E+17	16662	0.94	1.61E+09	8.63E+08	616	0.02	27.05
f₄	9.36E+04	1.29E+04	37973	1.94	7.25E+04	1.22E+04	5669	0.17	6.70
f₅	1.58E+04	3.90E+03	44544	2.25	1.06E+02	3.32E+01	1421	0.04	31.35
f₆	8.71E+03	2.01E+03	36463	1.85	6.90E+01	2.47E+01	904	0.03	40.34
f₇	1.08E+05	1.13E+05	32322	2.11	4.11E+01	1.12E+01	1082	0.05	29.87
f₈	2.10E+01	5.29E–02	82741	4.87	2.10E+01	6.09E–02	85977	3.23	0.96
f₉	4.28E+01	1.42E+00	64643	18.07	2.14E+01	4.18E+00	4178	1.08	15.47
f₁₀	6.79E+03	1.12E+03	72373	3.95	1.67E+01	1.19E+01	1094	0.04	66.15
f₁₁	8.38E+02	9.77E+01	52407	2.85	1.13E+01	3.35E+00	989	0.03	52.99
f₁₂	8.43E+02	9.43E+01	56517	3.51	1.05E+02	3.38E+01	1133	0.05	49.88
f₁₃	8.17E+02	9.91E+01	60595	3.89	8.64E+01	3.04E+01	1304	0.06	46.47
f₁₄	8.10E+03	3.23E+02	80418	4.48	1.55E+03	5.45E+02	5359	0.19	15.01
f₁₅	8.07E+03	3.59E+02	72859	4.24	4.41E+03	7.63E+02	5598	0.21	13.02
f₁₆	3.19E+00	5.04E–01	57793	11.01	1.79E+00	5.38E–01	10998	1.86	5.25
f₁₇	1.40E+03	1.91E+02	56622	2.95	4.09E+01	3.16E+00	1955	0.06	28.96
f₁₈	1.44E+03	1.68E+02	52612	3.01	1.06E+02	2.98E+01	1484	0.05	35.45
f₁₉	1.04E+06	4.38E+05	52422	2.75	3.34E+00	7.17E–01	1230	0.04	42.62
f₂₀	1.50E+01	1.43E–05	8888	0.51	1.50E+01	3.14E–05	962	0.04	9.24
f₂₁	3.57E+03	1.80E+02	64395	5.24	2.92E+02	2.75E+01	1901	0.12	33.87
f₂₂	8.87E+03	3.07E+02	61069	4.75	1.91E+03	1.25E+03	4629	0.27	13.19
f₂₃	9.05E+03	4.02E+02	49134	4.21	5.61E+03	1.21E+03	4437	0.29	11.07
f₂₄	4.15E+02	2.78E+01	32295	10.01	2.17E+02	6.37E+00	652	0.19	49.53
f₂₅	4.09E+02	1.66E+01	44404	13.74	2.70E+02	1.38E+01	728	0.21	60.99
f₂₆	3.08E+02	4.83E+01	64359	20.94	2.95E+02	2.03E+01	41667	12.63	1.54
f₂₇	1.64E+03	5.93E+01	32762	10.50	4.51E+02	6.27E+01	955	0.29	34.31
f₂₈	6.25E+03	5.82E+02	48551	4.94	3.00E+02	6.06E–03	1499	0.12	32.39

下载: 导出CSV

表 4 各FA变种算法结果的比较(Mean±SD)

函数	MFA	VSSFA	OFA	RaFA	ODFA	OOFA
f₁	3.58E+04±5.83E+03	3.45E+04±4.31E+03	2.42E+04±5.28E+03	4.03E+02±7.35E+02	1.32E+04±5.63E+03	1.70E–10±8.44E–10
f₂	5.03E+08±1.67E+08	3.73E+08±7.44E+07	3.34E+08±1.65E+08	3.71E+07±2.17E+07	2.19E+08±8.17E+07	3.39E+07±1.04E+07
f₃	1.47E+15±2.87E+15	1.68E+13±2.15E+13	2.01E+14±5.77E+14	2.62E+10±1.55E+10	6.04E+14±2.98E+15	1.61E+09±8.63E+08
f₄	9.27E+04±1.08E+04	8.04E+04±8.81E+03	8.68E+04±1.27E+04	1.04E+05±3.33E+04	8.21E+04±2.27E+04	7.25E+04±1.22E+04
f₅	9.85E+03±4.47E+03	8.56E+03±1.64E+03	5.70E+03±1.94E+03	4.99E+02±1.01E+03	1.14E+03±6.20E+02	1.06E+02±3.32E+01
f₆	5.84E+03±1.72E+03	4.49E+03±5.99E+02	3.48E+03±1.19E+03	1.71E+02±7.17E+01	1.64E+03±1.07E+03	6.90E+01±2.47E+01
f₇	2.52E+04±2.64E+04	2.61E+03±1.28E+03	6.42E+03±1.09E+04	3.03E+04±4.31E+04	2.40E+04±5.81E+04	4.11E+01±1.12E+01
f₈	2.10E+01±6.57E–02	2.10E+01±5.85E–02	2.10E+01±6.54E–02	2.11E+01±5.93E–02	2.10E+01±5.39E–02	2.10E+01±6.09E–02
f₉	4.16E+01±1.81E+00	4.05E+01±9.64E–01	3.83E+01±3.17E+00	3.96E+01±2.48E+00	3.72E+01±3.35E+00	2.14E+01±4.18E+00
f₁₀	5.14E+03±1.10E+03	4.59E+03±5.23E+02	3.29E+03±8.44E+02	1.49E+02±1.23E+02	1.97E+03±9.37E+02	1.67E+01±1.19E+01
f₁₁	6.54E+02±1.11E+02	6.50E+02±4.33E+01	4.60E+02±9.00E+01	1.52E+02±5.41E+01	4.65E+02±9.63E+01	1.13E+01±3.35E+00
f₁₂	7.40E+02±8.81E+01	6.52E+02±4.22E+01	5.13E+02±9.01E+01	8.69E+02±1.54E+02	6.73E+02±1.39E+02	1.05E+02±3.38E+01
f₁₃	7.42E+02±9.14E+01	6.50E+02±5.49E+01	5.48E+02±7.61E+01	8.81E+02±1.31E+02	6.86E+02±9.57E+01	8.64E+01±3.04E+01
f₁₄	7.44E+03±4.96E+02	7.66E+03±2.56E+02	5.83E+03±6.32E+02	1.62E+03±3.60E+02	7.27E+03±6.99E+02	1.55E+03±5.45E+02
f₁₅	7.56E+03±5.92E+02	7.65E+03±3.13E+02	5.72E+03±7.14E+02	4.89E+03±1.01E+03	7.26E+03±4.44E+02	4.41E+03±7.63E+02
f₁₆	2.70E+00±4.78E–01	2.76E+00±3.05E–01	1.47E+00±4.45E–01	1.95E+00±5.61E–01	2.46E+00±4.73E–01	1.79E+00±5.38E–01
f₁₇	1.26E+03±1.41E+02	1.18E+03±8.23E+01	6.52E+02±1.04E+02	9.87E+01±4.59E+01	8.98E+02±1.68E+02	4.09E+01±3.16E+00
f₁₈	1.28E+03±2.00E+02	1.16E+03±9.17E+01	7.18E+02±1.52E+02	1.55E+03±2.47E+02	1.03E+03±1.92E+02	1.06E+02±2.98E+01
f₁₉	2.75E+05±2.01E+05	2.39E+05±6.70E+04	5.00E+04±3.86E+04	7.96E+01±1.68E+02	2.68E+04±5.41E+04	3.34E+00±7.17E–01
f₂₀	1.50E+01±3.72E–02	1.50E+01±2.29E–02	1.50E+01±6.32E–08	1.49E+01±1.78E–01	1.37E+01±8.18E–01	1.50E+01±3.14E–05
f₂₁	3.03E+03±2.98E+02	3.10E+03±1.43E+02	2.47E+03±1.64E+02	4.57E+02±1.71E+02	2.16E+03±3.59E+02	2.92E+02±2.75E+01
f₂₂	8.43E+03±4.74E+02	8.29E+03±2.74E+02	6.77E+03±1.01E+03	2.07E+03±5.70E+02	7.63E+03±9.75E+02	1.91E+03±1.25E+03
f₂₃	8.16E+03±4.96E+02	8.28E+03±2.43E+02	6.82E+03±8.01E+02	6.38E+03±9.46E+02	7.58E+03±6.23E+02	5.61E+03±1.21E+03
f₂₄	3.83E+02±2.26E+01	3.57E+02±8.70E+00	3.45E+02±1.59E+01	3.69E+02±2.90E+01	3.48E+02±1.61E+01	2.17E+02±6.37E+00
f₂₅	4.02E+02±1.31E+01	3.76E+02±6.32E+00	3.85E+02±1.81E+01	3.94E+02±1.78E+01	3.74E+02±1.73E+01	2.70E+02±1.38E+01
f₂₆	2.73E+02±4.82E+01	2.50E+02±1.53E+01	2.62E+02±5.77E+01	3.31E+02±1.08E+02	3.04E+02±9.55E+01	2.95E+02±2.03E+01
f₂₇	1.56E+03±6.16E+01	1.47E+03±3.89E+01	1.41E+03±4.78E+01	1.60E+03±1.07E+02	1.46E+03±9.06E+01	4.51E+02±6.27E+01
f₂₈	5.60E+03±5.24E+02	4.96E+03±2.87E+02	4.56E+03±5.53E+02	6.00E+03±1.08E+03	4.45E+03±6.04E+02	3.00E+02±6.06E–03
–/≈/+	25/2/1	25/2/1	24/2/2	27/0/1	26/1/1	—
P-value	1.18E–5	1.18E–5	1.33E–5	4.46E–6	7.03E–6	—
Friedman	5.30	4.30	3.13	3.61	3.32	1.34

下载: 导出CSV

参考文献(23)

YANG Xinshe. Firefly algorithms for multimodal optimization[C]. International Symposium on Stochastic Algorithms, Berlin, Germany, 2009: 169–178.

HASSANZADEH T and KANAN H R. Fuzzy FA: A modified firefly algorithm[J]. Applied Artificial Intelligence, 2014, 28(1): 47–65. doi: 10.1080/08839514.2014.862773

HAJI V H and MONJE C A. Fractional-order PID control of a chopper-fed DC motor drive using a novel firefly algorithm with dynamic control mechanism[J]. Soft Computing, 2018, 22(18): 6135–6146. doi: 10.1007/s00500-017-2677-5

ZHANG Yong, SONG Xianfang, and GONG Dunwei. A return-cost-based binary firefly algorithm for feature selection[J]. Information Sciences, 2017, 418: 561–574. doi: 10.1016/j.ins.2017.08.047

FISTER I, FISTER Jr I, YANG X S, et al. A comprehensive review of firefly algorithms[J]. Swarm and Evolutionary Computation, 2013, 13: 34–46. doi: 10.1016/j.swevo.2013.06.001

YU Shuhao, ZHU Shenglong, MA Yanyu, et al. A variable step size firefly algorithm for numerical optimization[J]. Applied Mathematics and Computation, 2015, 263: 214–220. doi: 10.1016/j.amc.2015.04.065

WANG Hui, ZHOU Xinyu, SUN Hui, et al. Firefly algorithm with adaptive control parameters[J]. Soft Computing, 2017, 21(17): 5091–5102. doi: 10.1007/s00500-016-2104-3

WANG Hui, WANG Wenjun, SUN Hui, et al. Firefly algorithm with random attraction[J]. International Journal of Bio-Inspired Computation, 2016, 8(1): 33–41. doi: 10.1504/ijbic.2016.074630

VERMA O P, AGGARWAL D, PATODI T, et al. Opposition and dimensional based modified firefly algorithm[J]. Expert Systems with Applications, 2016, 44: 168–176. doi: 10.1016/j.eswa.2015.08.054

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

TIZHOOSH H R. Opposition-based learning: A new scheme for machine intelligence[C]. International Conference on Computational Intelligence for Modelling, Control and Automation, Vienna, Austria, 2005: 695–701.

RAHNAMAYAN H, TIZHOOSH H R, and SALAMA M. Opposition-based differential evolution[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(1): 64–79. doi: 10.1109/TEVC.2007.894200

WANG Hui, WU Zhijian, RAHNAMAYAN S, et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181(20): 4699–4714. doi: 10.1016/j.ins.2011.03.016

YU Shuhao, ZHU Shenglong, MA Yan, et al. Enhancing firefly algorithm using generalized opposition-based learning[J]. Computing, Springer Vienna, 2015, 97(7): 741–754. doi: 10.1007/s00607-015-0456-7

PARK S Y and LEE J J. Stochastic opposition-based learning using a beta distribution in differential evolution[J]. IEEE Transactions on Cybernetics, 2016, 46(10): 2184–2194. doi: 10.1109/TCYB.2015.2469722

YANG Xinshe. Cuckoo Search and Firefly Algorithm[M]. London, UK: Springer, 2014: 1–26. doi: 10.1007/978-3-319-02141-6.

RAHNAMAYAN S, JESUTHASAN J, BOURENNANI F, et al. Computing opposition by involving entire population[C]. IEEE Congress on Evolutionary Computation, Beijin, China, 2014: 1800–1807.

方开泰, 刘民千, 周永道. 试验设计与建模[M]. 北京: 高等教育出版社, 2011: 81–101.

FANG Kaitai, LIU Minqian, and ZHOU Yongdao. Design and Modeling of Experiments[M]. Beijing: Higher Education Press, 2011: 81–101.

ZHAN Zhihui, ZHANG Jun, LI Yun, et al. Orthogonal learning particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(6): 832–847. doi: 10.1109/TEVC.2010.2052054

SUGANTHAN P N, HANSEN N, LIANG J J, et al. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization[R]. Computational Intelligence Laboratory, Zhengzhou University, China and Nanyang Technological, Singapore, Technical Report 201212, 2013.

TILAHUN S L and ONG H C. Modified firefly algorithm[J]. Journal of Applied Mathematics, 2012, 12: 2428–2439. doi: 10.1155/2012/467631

DERRAC J, CARCIA S, MOLINA D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(11): 3–18. doi: 10.1016/j.swevo.2011.02.002

周凌云, 丁立新, 彭虎, 等. 一种邻域重心反向学习的粒子群优化算法[J]. 电子学报, 2017, 45(11): 2815–2824. doi: 10.3969/j.issn.0372-2112.2017.11.032

ZHOU Lingyun, DING Lixin, PENG Hu, et al. Neighborhood centroid opposition-based particle swarm optimization[J]. Acta Electronica Sinica, 2017, 45(11): 2815–2824. doi: 10.3969/j.issn.0372-2112.2017.11.032

施引文献

资源附件(0)

访问统计