面向大规模问题精英贡献两阶段动态分组算法

doi:10.19678/j.issn.1000-3428.0067039

摘要/Abstract

摘要： 协同进化框架是解决大规模全局优化问题的有效方法，设计合理的决策变量分组方法是提高协同进化算法的关键，而利用精英决策变量动态构建精英子组件可以有效提高进化效率，针对大规模优化时，其可能将无关系的变量分配到同一子组件，造成无法充分利用分组提高进化协同进化效率的问题，提出一种精英贡献两阶段动态分组算法（Elite Contribution Two-stage Dynamic Grouping，EC-TSDG）：首先，分组前阶段对变量进行随机分组，然后评估变量的贡献程度，从众多变量贡献中寻找精英贡献变量；其次，分组后阶段利用变量的相关关系，寻找与精英决策变量存在相互作用的剩余变量，并将其合并形成精英子组件，使得精英子组件内部的变量两两相关，以此提高变量分组的准确性以及算法的收敛速度，避免子组件之间的相关干扰。最后采用具有外部存档的自适应差分进化算法作为优化器进化各个子组件。在CEC2013测试函数集上与其它先进算法进行比较，提出的算法收敛速度快于对比算法，Friedman检验的平均排序为1.43，高于对比算法36.78%。

Abstract: The coevolution framework is an effective method for solving large-scale global optimization problems. Designing a reasonable decision variable grouping method is the key to improving the coevolution algorithm. Using elite decision variables to construct elite subcomponents dynamically can improve evolutionary efficiency. This chapter will focus on the characteristics of inseparable variables in large-scale optimization problems that are difficult to divide. The existing strategy may assign unrelated variables to the same subcomponent of the grouping problem. A two-stage dynamic grouping algorithm of elite contribution (EC-TSDG) is proposed: first, the variables are randomly grouped in the pre-grouping stage, and then the contribution of variables is evaluated, and the elite contribution variables are found from many variable contributions; Secondly, in the post-grouping stage, the correlation relationship of variables is used to find the remaining variables that interact with the elite decision-making variables, and merge them to form the elite sub-component, so that the variables inside the elite subcomponent are correlated in pairs, to improve the accuracy of variable grouping and the convergence speed of the algorithm, and avoid the correlation interference between the subcomponents. Finally, the adaptive differential evolution algorithm with an external archive is used as the optimizer to optimize each subcomponent. Compared with other advanced algorithms on the CEC2013 test function set, the proposed algorithm has a faster rate of convergence than the comparison algorithm. The average ranking of Friedman test is 1.43, which is 36.78% higher than the comparison algorithm.

王彬, 张娇 , 李薇, 王晓帆, 金海燕. 面向大规模问题精英贡献两阶段动态分组算法[J]. 计算机工程, doi: 10.19678/j.issn.1000-3428.0067039.

WANG Bin, ZHANG Jiao, LI Wei, WANG Xiaofan, JIN Haiyan. Elite contribution two-stage dynamic grouping algorithm for large-scale optimization[J]. Computer Engineering, doi: 10.19678/j.issn.1000-3428.0067039.

参考文献

[1] SHI Y, TENG H, LI Z. Cooperative Co-evolutionary Differential Evolution for Function Optimization[J]. Lecture Notes in Computer Science, 2005, 3611:1080-1088.
[2] OMIDVAR M N, LI X, XINY. Smart Use of Computational Resources Based on Contribution for Cooperative Co-evolutionary Algorithms[C]// 13th Annual Genetic and Evolutionary Computation Conference, GECCO 2011, Proceedings, Dublin, Ireland, July 12-16, 2011. 2011.
[3] KESHK M, SINGH H, ABBASS H. Automatic estimation of differential evolution parameters using Hidden Markov Models[J]. Evolutionary Intelligence, 2018, 10(3/4): 77-93.
[4] DENG L B. An adaptive dimension level adjustment framework for differential evolution[J]. Knowledge-Based Systems, 2020, 206(4): 1-20.
[5] Transactions on Evolutionary Computation, 2011, 15(1): 55-66. [5] MALLIPEDDI R. Differential evolution algorithm with ensemble of parameters and mutation strategies[J]. Applied Soft Computing, 2011, 11(2): 1679-1696.
[6] SUN G J, WU Y R, DENG L B, et al. Elite representative based individual adaptive regeneration framework for differential evolution[J]. IEEE Access, 2020, 8: 61226-61245.
[7] SEMNANI A, KAMYAB M, REKANOS I T. Reconstruction of one-dimensional dielectric scatterers using differential evolution and particle swarm optimization[J]. IEEE Geoscience and Remote Sensing Letters, 2009, 6(4): 671-675.
[8] LaTorre , Muelas S, pen a M. A MOS-based Dynamic Memetic Differential Evolution Algorithm for Continuous Optimization: A Scalability Test[J]. Soft Computing, 2011, 15(11): 2187-2199..
[9] YANG Z, TANG K, YAO X. Large scale evolutionary optimization using cooperative coevolution[J]. Information Sciences, 2008, 178(15):2985-2999.
[10] Tseng L Y, Chen C. Multiple trajectory search for Large Scale Global Optimization[C]// IEEE Congress on Evolutionary Computation. IEEE, 2008.
[11] Maniezzo V, Gambardella L M, Luigi FD. Ant Colony Optimization[J]. Springer BerlinHeidelberg, 2004.
[12] Molina D, Lozano M, Mari A, et al. Memetic algorithms based on local search chains for large scale continuous optimization problems: MA-SSW-Chains[J]. Soft Computing A Fusion of Foundations, Methodologies and Applications, 2011.
[13] Yen G G, Daneshyari M. Diversity-based information exchange among multiple swarms in particle swarm optimization[J]. International Journal of Computational Intelligence and Applications, 2008, 7(01): 57-75.
[14] M. Diversity-based information exchange among multiple swarms in particle swarm optimization[J]. International Journal of Computational Intelligence and Applications, 2008, 7(01): 57-75.
[15] Mohapatra P, Das K N, Roy S. A modified competitive swarm optimizer for large scale optimization problems[J]. Applied Soft Computing, 2017, 59: 340-362.
[16] Mohapatra P, Das K N, Roy S. Inherited Competitive Swarm Optimizer for Large-Scale Optimization Problems[M]//Harmony Search and Nature Inspired Optimization Algorithms. Springer, Singapore, 2019: 85-95.
[17] Cheng R , Jin Y . A competitive swarm optimizer for large scale optimization[J]. IEEE Transactions on Cybernetics, 2014.
[18] 王磊 , 林鸿飞 , 滕弘飞 . 并行协同差异进化算法研究 [J]. 计算机工程 , 2012(04):188-190+196. WANG Lei, LIN Hongfei, TENG Hongfei. Research on parallel collaborative difference evolution algorithm[J]. Computer Engineering, 2012(04):188-190+196.(in Chinese)
[19] Collange G, Reynaud S, Hansen N. Covariance matrix adaptation evolution strategy for multidisciplinary optimization of expendable launcher family[C]//13th AIAA/ISSMO Multidisciplinary Analysis Optimization Conference. 2010: 9088.
[20] 刘方洁.基于分组与局部搜索的大规模全局优化新算法[D].西安电子科技大学,2017. Liu Fangjie. New algorithm of large-scale global optimization based on grouping and local search[D]. Xidian University, 2017. (in Chinese)
[21] Yang Z, Tang K, Yao X. Large scale evolutionary optimization using cooperative coevolution[J]. Information Sciences, 2008, 178(15):2985-2999.
[22] OMIDVAR M N, Li X, Mei Y et al. Cooperative co-evolution with differential grouping for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3):378-393.
[23] YUAN S, KIRLEY M, HALGAMUGE S K. Extended Differential Grouping for Large Scale Global Optimization with Direct and Indirect Variable Interactions[C]// The Genetic and Evolutionary Computation Conference. ACM, 2015.
[24] ZHANG X Y, GONGY J, YING, et al. Dynamic cooperative coevolution for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(6):935-948.
[25] Y. WANG, Z. CAI, and Q. ZHANG. Differential evolution with composite trial vector generation and control parameters[J]. IEEE Transactions on Evolutionary Computation, 2011,15: 55-66.
[26] Zhenyu Yang,Ke Tang,Xin Yao. Large scale evolutionary optimization using cooperative coevolution[J]. Information Sciences,2008,178(15).
[27] Li X, Tang K, Omidvar M N, et al. Benchmark functions for the CEC 2013 special session and competition on large-scale global optimization[J]. gene, 2013, 7(33): 8.
[28] J. ZHANG and A. C. SANDERSON. JADE: Adaptive differential evolution with optional external archive[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 945-958.
[29] Z. YANG, K. TANG and X. YAO. Self-adaptive Differential Evolution with Neighborhood Search[C]. In Proceeding of IEEE Congress on Evolutionary Computation. Piscataway, NJ: The IEEE Press, 2008:1110-1116.

选择文件类型/文献管理软件名称

选择包含的内容