Fixed Point Evolution Algorithm
-
摘要:
为设计高效稳定的演化算法,本文首次将方程求根的不动点迭代思想引入到优化领域,通过将演化算法的寻优过程看作为在迭代框架下方程不动点的逐步显示化过程,设计出一种基于数学模型的演化新算法,即不动点演化算法(fixed point evolution algorithm,FPEA). 该算法的繁殖算子是由Aitken加速的不动点迭代模型导出的二次多项式,其整体框架继承传统演化算法(如差分演化算法)基于种群的迭代模式. 实验结果表明:在CEC2014、CEC2019基准函数集上,该算法最优值的平均排名在所有比较算法中排名第一;在4个工程约束设计问题上,FPEQ与CSA、GPE等多个算法相比,能以较少的计算开销获得最高的求解精度.
Abstract:In order to design an efficient and robust evolution algorithm, the fixed point iteration idea in solving equations was first introduced into the optimization field. The optimization process of an evolution algorithm was regarded as the gradual display process of the fixed point of an equation in an iterative framework. On this basis, a novel evolution algorithm based on a mathematical model was developed, named fixed point evolution algorithm (FPEA). The reproduction operator of FPEA is a quadratic polynomial which is derived from a fixed point iteration model with the Aitken method. The overall framework of FPEA inherits the population-based iterative model of traditional evolution algorithms such as differential evolution algorithm. The experimental results show that the average ranking of the optimal value of FPEA ranks first among all the compared algorithms on CEC2014 and CEC2019 benchmark functions. The proposed algorithm can achieve the highest solution accuracy with a low computational overhead on four engineering constraint design problems among the compared algorithms including CSA and GPE.
-
表 1 比较算法的参数设置
Table 1. Parameter settings of compared algorithms
算法 参数 DE F=0.60,CR=0.80 PSO c1=c2=2.0,ω=1.00 GPE th=0.01 GPEae th=0.01 AO α=0.10,δ=0.10 FPEA λ=1.40,CR=0.80 表 2 FPEA关于四个工程约束设计问题的参数设置
Table 2. Parameter setting of FPEA on four engineering constraint design problems
工程约束
设计问题种群
大小最大迭代
次数优化参数
数量三杆桁架 20 500 2 焊接梁 20 2000 4 齿轮组 20 500 4 管形柱 20 2000 2 表 3 在CEC2014的10维上,DE、PSO、GPE、GPEae、AO、JS和FPEA的平均排名比较
Table 3. Comparison of average rankings of DE, PSO, GPE, GPEae, AO, JS, and FPEA on 10-dimensional CEC2014 benchmark functions
算法 平均排名 最优值 平均值 标准差 DE 2.93 2.60 2.10 PSO 5.57 5.63 5.47 GPE 4.27 4.40 4.30 GPEae 3.53 3.80 4.33 AO 5.63 5.57 5.07 JS 3.37 3.17 3.70 FPEA 2.20 2.33 2.83 注:D=10,FEs= 100000 表 4 在CEC2014的50维上,DE、PSO、GPE、GPEae、AO、JS和FPEA的平均排名比较
Table 4. Comparison of average rankings of DE, PSO, GPE, GPEae, AO, JS, and FPEA on 50-dimensional CEC2014 benchmark functions
算法 平均排名 最优值 平均值 标准差 DE 3.33 2.97 2.20 PSO 5.00 5.00 4.93 GPE 4.20 4.40 5.23 GPEae 4.73 5.10 5.03 AO 4.43 4.27 4.27 JS 3.30 3.20 3.33 FPEA 2.80 2.87 3.00 注:D=50,FEs= 500000 表 5 在CEC2019上,DE、PSO、GPE、GPEae、AO、JS和FPEA的平均排名比较
Table 5. Comparison of average rankings of DE, PSO, GPE, GPEae, AO, JS, and FPEA on CEC2019 benchmark functions
DE PSO GPE GPEae AO JS FPEA 平均排名 最优值 5.30 5.60 3.60 3.20 4.80 2.50 2.30 平均值 4.10 6.10 4.10 4.30 4.40 2.10 2.30 标准差 2.40 5.70 4.60 5.10 3.90 3.10 3.20 表 6 FPEA的Wilcoxon秩和检验结果
Table 6. Wilcoxon rank sum test results of FPEA
FPEA vs. R + R− p值 α=0.05 DE 1013 1198 0.554589 NO PSO 2139 346 1.55E-07 YES GPE 1847 568 1.32E-04 YES GPEae 1939 476 1.20E-05 YES AO 1884 601 1.74E-04 YES JS 1597 888 0.038024 YES 表 7 三杆桁架设计问题统计结果比较
Table 7. Comparison of results on the three-bar truss design problem
最优值 平均值 最差值 标准差 最大函数评估次数 CSA 263.895843 263.895843 263.895843 1.01E-10 25000 BSA 263.895843 263.895843 263.895845 2.64E-07 13720 SAR 263.895843 263.895843 263.895843 2.68E-14 7000 BSAISA 263.895843 263.895843 263.895843 5.75E-13 8400 GPE 263.895713 263.897016 263.907528 2.20E-03 10000 GPEae 263.895712 263.896676 263.901731 1.40E-03 7700 FPEA 263.895711 263.895711 263.895711 1.22E-11 6520 表 8 焊接梁设计问题统计结果比较
Table 8. Comparison of results on the welded beam design problem
最优值 平均值 最差值 标准差 最大函数评估次数 TEO 1.725284 1.768040 1.931161 5.82E-02 20000 IAFOA 1.724856 1.724856 1.724856 8.99E-07 240000 DDB-BC 1.724852 1.724855 1.724890 6.97E-06 18000 CSA 1.724852 1.724852 1.724852 1.19E-15 100000 GPE 1.724851 1.725037 1.732281 1.10E-03 36100 GPEae 1.724851 1.724914 1.727964 4.40E-04 35860 FPEA 1.724851 1.871685 3.062050 2.70E-01 17780 表 9 齿轮组设计问题统计结果比较
Table 9. Comparison of results on the gear train design problem
最优值 平均值 最差值 标准差 最大函数评估次数 ALO 2.70E-12 N/A N/A N/A 120 ABC 2.70E-12 3.60E-10 N. A 5.52E-10 60 CSA 2.70E-12 2.06E-09 3.20E-08 5.10E-09 100000 GPE 2.70E-12 6.88E-10 3.45E-09 8.76E-10 900 GPEae 2.70E-12 1.17E-09 1.12E-08 1.77E-09 1060 FPEA 2.70E-12 1.71E-09 1.83E-08 3.53E-09 640 表 10 管形柱设计问题统计结果比较
Table 10. Comparison of results on the tubular column design problem
最优值 平均值 最差值 标准差 最大函数评估次数 CS 26.532170 26.535040 26.539720 1.93E-03 15000 SAR 26.531328 26.531328 26.531328 1.51E-07 4000 CSA 26.532170 26.535040 26.539720 1.93E-03 15000 GPE 26.531312 26.531312 26.531312 3.59E-15 20400 GPEae 26.531312 26.531330 26.532191 1.24E-04 18300 FPEA 26.531312 26.531312 26.531312 3.59E-15 6360 -
[1] BOUSSAÏD I, LEPAGNOT J, SIARRY P. A survey on optimization metaheuristics[J]. Information Sciences, 2013, 237: 82-117. doi: 10.1016/j.ins.2013.02.041 [2] LARRANAGA P, LOZANO J. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation[M]. Boston: Kluwer Press, 2001. [3] HANSEN N, OSTERMEIER A. Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation[C]//Proceedings of IEEE International Conference on Evolutionary Computation. Nagoya: IEEE, 1996: 312-317. [4] MIRJALILI S. SCA: a Sine Cosine Algorithm for solving optimization problems[J]. Knowledge-Based Systems, 2016, 96: 120-133. doi: 10.1016/j.knosys.2015.12.022 [5] HU Z B, XU X L, SU Q H, et al. Grey prediction evolution algorithm for global optimization[J]. Applied Mathematical Modelling, 2020, 79: 145-160. doi: 10.1016/j.apm.2019.10.026 [6] XU X L, HU Z B, SU Q H, et al. Multivariable grey prediction evolution algorithm: a new metaheuristic[J]. Applied Soft Computing, 2020, 89: 106086. doi: 10.1016/j.asoc.2020.106086 [7] GAO C, HU Z B, XIONG Z G, et al. Grey prediction evolution algorithm based on accelerated even grey model[J]. IEEE Access, 2020, 8: 107941-107957. doi: 10.1109/ACCESS.2020.3001194 [8] HU Z B, GAO C, SU Q H. A novel evolutionary algorithm based on even difference grey model[J]. Expert Systems with Applications, 2021, 176: 114898. doi: 10.1016/j.eswa.2021.114898 [9] ZHOU T, HU Z B, ZHOU Q, et al. A novel grey prediction evolution algorithm for multimodal multiobjective optimization[J]. Engineering Applications of Artificial Intelligence, 2021, 100: 104173.1-104173.13. doi: 10.1016/j.engappai.2021.104173 [10] HU Z B, LI Z, DAI C Y, et al. Multiobjective grey prediction evolution algorithm for environmental/economic dispatch problem[J]. IEEE Access, 2020, 8: 84162-84176. doi: 10.1109/ACCESS.2020.2992116 [11] CAI G C, SU Q H, HU Z B. Automated test case generation for path coverage by using grey prediction evolution algorithm with improved scatter search strategy[J]. Engineering Applications of Artificial Intelligence, 2021, 106: 104454.1-104454.13. doi: 10.1016/j.engappai.2021.104454 [12] AHMADIANFAR I, BOZORG-HADDAD O, CHU X F. Gradient-based optimizer: a new metaheuristic optimization algorithm[J]. Information Sciences, 2020, 540: 131-159. doi: 10.1016/j.ins.2020.06.037 [13] GAO C, HU Z B, TONG W Y. Linear prediction evolution algorithm: a simplest evolutionary optimizer[J]. Memetic Computing, 2021, 13(3): 319-339. doi: 10.1007/s12293-021-00340-x [14] CHOW Y K, KAY S. On the aitken acceleration method for nonlinear problems[J]. Computers & Structures, 1984, 19(5/6): 757-761. [15] 胡长军,魏硕,张纪林,等. 一种基于SMP的并行逐次超松弛迭代法[J]. 计算机研究与发展,2007,44(10): 1688-1693. doi: 10.1360/crad20071009HU Changjun, WEI Shuo, ZHANG Jilin, et al. A parallel SOR algorithm for linear systems on SMP[J]. Journal of Computer Research and Development, 2007, 44(10): 1688-1693. doi: 10.1360/crad20071009 [16] LI Z, HU Z B, MIAO Y F, et al. Deep-mining backtracking search optimization algorithm guided by collective wisdom[J]. Mathematical Problems in Engineering, 2019, 2019: 2540102.1-2540102.30. doi: 10.1155/2019/2540102 [17] STORN R, PRICE K. Differential Evolution–A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J]. Journal of Global Optimization, 1997, 11(4): 341-359. doi: 10.1023/A:1008202821328 [18] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of ICNN'95-International Conference on Neural Networks. Perth: IEEE, 1995: 1942-948. [19] CHOU J S, TRUONG D N. A novel metaheuristic optimizer inspired by behavior of jellyfish in ocean[J]. Applied Mathematics and Computation, 2021, 389: 125535.1-125535.47. doi: 10.1016/j.amc.2020.125535 [20] ABUALIGAH L, YOUSRI D, ABD ELAZIZ M, et al. Aquila Optimizer: a novel meta-heuristic optimization algorithm[J]. Computers & Industrial Engineering, 2021, 157: 107250.1-107250.37. [21] AZIZI M. Atomic orbital search: a novel metaheuristic algorithm[J]. Applied Mathematical Modelling, 2021, 93: 657-683. doi: 10.1016/j.apm.2020.12.021 [22] BOGAR E, BEYHAN S. Adolescent Identity Search Algorithm (AISA): a novel metaheuristic approach for solving optimization problems[J]. Applied Soft Computing, 2020, 95: 106503.1-106503.43. doi: 10.1016/j.asoc.2020.106503 [23] ASKARZADEH A. A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm[J]. Computers & Structures, 2016, 169: 1-12. [24] WANG H L, HU Z B, SUN Y Q, et al. Modified backtracking search optimization algorithm inspired by simulated annealing for constrained engineering optimization problems[J]. Computational Intelligence and Neuroscience, 2018, 2018: 9167414.1-9167414.27. [25] SHABANI A, ASGARIAN B, SALIDO M, et al. Search and rescue optimization algorithm: a new optimization method for solving constrained engineering optimization problems[J]. Expert Systems with Applications, 2020, 161: 113698.1-113698.15. doi: 10.1016/j.eswa.2020.113698 [26] KAVEH A, DADRAS A. A novel meta-heuristic optimization algorithm: thermal exchange optimization[J]. Advances in Engineering Software, 2017, 110: 69-84. doi: 10.1016/j.advengsoft.2017.03.014 [27] WU L, LIU Q, TIAN X, et al. A new improved fruit fly optimization algorithm IAFOA and its application to solve engineering optimization problems[J]. Knowledge-Based Systems, 2018, 144: 153-173. doi: 10.1016/j.knosys.2017.12.031 [28] PRAYOGO D, CHENG M Y, WU Y W, et al. Differential Big Bang - Big Crunch algorithm for construction-engineering design optimization[J]. Automation in Construction, 2018, 85: 290-304. doi: 10.1016/j.autcon.2017.10.019 [29] MIRJALILI S. The ant lion optimizer[J]. Advances in Engineering Software, 2015, 83: 80-98. doi: 10.1016/j.advengsoft.2015.01.010 [30] GANDOMI A H, YANG X S, ALAVI A H. Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems[J]. Engineering with Computers, 2013, 29(1): 17-35. doi: 10.1007/s00366-011-0241-y