Orthogonal Opposition Based Firefly Algorithm
-
摘要:
针对萤火虫算法求解复杂优化问题时收敛精度较低的问题,该文提出一种正交反向学习策略,嵌入萤火虫算法,得到一种正交反向学习萤火虫算法。正交反向学习策略中,采用重心反向计算,利用群体搜索经验的同时避免搜索依赖坐标;采用正交试验设计,构建部分维上取反向值的正交反向候选解,充分挖掘个体和反向个体在不同维度上的有利信息。在标准测试集上进行验证,实验结果说明了正交反向学习策略的有效性。与多种新近的改进萤火虫算法相比,该算法在大多数函数上获得更高的求解精度。
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.
-
表 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个个体。 表 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 表 3 FA与OOFA的比较结果
函数 FA OOFA 加速比R Mean SD FEs T (s) Mean SD FEs T (s) f1 5.16E+04 6.35E+03 80232 3.85 1.70E–10 8.44E–10 1091 0.03 73.54 f2 7.30E+08 2.15E+08 72314 3.82 3.39E+07 1.04E+07 1704 0.06 42.44 f3 4.74E+16 1.43E+17 16662 0.94 1.61E+09 8.63E+08 616 0.02 27.05 f4 9.36E+04 1.29E+04 37973 1.94 7.25E+04 1.22E+04 5669 0.17 6.70 f5 1.58E+04 3.90E+03 44544 2.25 1.06E+02 3.32E+01 1421 0.04 31.35 f6 8.71E+03 2.01E+03 36463 1.85 6.90E+01 2.47E+01 904 0.03 40.34 f7 1.08E+05 1.13E+05 32322 2.11 4.11E+01 1.12E+01 1082 0.05 29.87 f8 2.10E+01 5.29E–02 82741 4.87 2.10E+01 6.09E–02 85977 3.23 0.96 f9 4.28E+01 1.42E+00 64643 18.07 2.14E+01 4.18E+00 4178 1.08 15.47 f10 6.79E+03 1.12E+03 72373 3.95 1.67E+01 1.19E+01 1094 0.04 66.15 f11 8.38E+02 9.77E+01 52407 2.85 1.13E+01 3.35E+00 989 0.03 52.99 f12 8.43E+02 9.43E+01 56517 3.51 1.05E+02 3.38E+01 1133 0.05 49.88 f13 8.17E+02 9.91E+01 60595 3.89 8.64E+01 3.04E+01 1304 0.06 46.47 f14 8.10E+03 3.23E+02 80418 4.48 1.55E+03 5.45E+02 5359 0.19 15.01 f15 8.07E+03 3.59E+02 72859 4.24 4.41E+03 7.63E+02 5598 0.21 13.02 f16 3.19E+00 5.04E–01 57793 11.01 1.79E+00 5.38E–01 10998 1.86 5.25 f17 1.40E+03 1.91E+02 56622 2.95 4.09E+01 3.16E+00 1955 0.06 28.96 f18 1.44E+03 1.68E+02 52612 3.01 1.06E+02 2.98E+01 1484 0.05 35.45 f19 1.04E+06 4.38E+05 52422 2.75 3.34E+00 7.17E–01 1230 0.04 42.62 f20 1.50E+01 1.43E–05 8888 0.51 1.50E+01 3.14E–05 962 0.04 9.24 f21 3.57E+03 1.80E+02 64395 5.24 2.92E+02 2.75E+01 1901 0.12 33.87 f22 8.87E+03 3.07E+02 61069 4.75 1.91E+03 1.25E+03 4629 0.27 13.19 f23 9.05E+03 4.02E+02 49134 4.21 5.61E+03 1.21E+03 4437 0.29 11.07 f24 4.15E+02 2.78E+01 32295 10.01 2.17E+02 6.37E+00 652 0.19 49.53 f25 4.09E+02 1.66E+01 44404 13.74 2.70E+02 1.38E+01 728 0.21 60.99 f26 3.08E+02 4.83E+01 64359 20.94 2.95E+02 2.03E+01 41667 12.63 1.54 f27 1.64E+03 5.93E+01 32762 10.50 4.51E+02 6.27E+01 955 0.29 34.31 f28 6.25E+03 5.82E+02 48551 4.94 3.00E+02 6.06E–03 1499 0.12 32.39 表 4 各FA变种算法结果的比较(Mean±SD)
函数 MFA VSSFA OFA RaFA ODFA OOFA f1 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 f2 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 f3 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 f4 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 f5 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 f6 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 f7 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 f8 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 f9 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 f10 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 f11 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 f12 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 f13 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 f14 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 f15 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 f16 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 f17 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 f18 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 f19 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 f20 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 f21 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 f22 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 f23 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 f24 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 f25 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 f26 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 f27 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 f28 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 -
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.032ZHOU 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