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

doi:10.19678/j.issn.1000-3428.0067039

摘要/Abstract

摘要：

协同进化框架是解决大规模全局优化问题的有效方法, 设计合理的决策变量分组方法是提高协同进化算法性能的关键, 而利用精英决策变量动态构建精英子组件可以有效提高进化效率, 但在进行大规模优化时, 其可能将无关的变量分配到同一子组件, 从而无法充分利用分组提高协同进化效率。针对该问题, 提出一种精英贡献两阶段动态分组算法(EC-TSDG)。在分组前阶段, 对变量进行随机分组, 评估变量的贡献程度, 从众多变量中寻找精英贡献变量; 在分组后阶段, 利用变量的相关关系寻找与精英决策变量存在相互作用的剩余变量, 并将其合并形成精英子组件, 使得精英子组件内部的变量两两相关, 以此提高变量分组的准确性以及算法的收敛速度, 避免子组件之间的相关干扰。最后, 采用具有外部存档的自适应差分进化算法作为优化器进化各个子组件。在CEC'2013测试集上与其他先进算法进行比较, 实验结果表明, EC-TSDG收敛速度快于对比算法, Friedman检验值为1.43, 平均排序较对比的动态分组算法DCC平均提升36.78%。

关键词: 协同进化, 大规模优化问题, 两阶段动态分组, 贡献信息, 精英子组件

Abstract:

The co-evolution framework is an effective method for solving large-scale global optimization problems. Designing a reasonable decision variable grouping method is key to improving the performance of co-evolution algorithm. Using elite decision variables to dynamically construct elite subcomponents can improve evolutionary efficiency. This paper focuses 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 subcomponents of the grouping problem. To address this issue, this paper proposes the Elite Contribution based Two-Stage Dynamic Grouping algorithm(EC-TSDG). First, the variables are randomly grouped in the pre-grouping stage. Subsequently, the contributions of variables are evaluated, and the elite contribution variables are obtained from several variable contributions. Second, in the post-grouping stage, the correlation among the variables is used to determine the remaining variables that interact with the elite decision variables and to merge them to form the elite subcomponent. This enables the variables within the elite subcomponent to correlate in pairs so as to improve the accuracy of variable grouping and convergence speed of the algorithm and to avoid correlation interference between the subcomponents. Finally, an adaptive differential evolution algorithm with an external archive is used as the optimizer for each subcomponent. Compared with other advanced algorithms on the CEC'2013 test set, the proposed algorithm exhibits a faster convergence speed than comparative algorithms. Experimental result show that the Friedman test value of EC-TSDG is 1.43, and its average ranking is 36.78% higher than that of the comparative dynamic grouping algorithm, DCC.

Key words: co-evolution, large-scale optimization problem, two-stage dynamic grouping, contribution information, elite subcomponent

王彬, 张娇, 李薇, 王晓帆, 金海燕. 面向大规模优化问题的精英贡献两阶段动态分组算法[J]. 计算机工程, 2024, 50(7): 154-163.

Bin WANG, Jiao ZHANG, Wei LI, Xiaofan WANG, Haiyan JIN. Elite Contribution Based Two-Stage Dynamic Grouping Algorithm for Large-Scale Optimization Problem[J]. Computer Engineering, 2024, 50(7): 154-163.

https://www.ecice06.com/CN/Y2024/V50/I7/154

图/表 7

图1 大规模优化问题示例

Fig.1 Examples of large-scale optimization problem

图2 EC-TSDG算法流程

Fig.2 Procedure of EC-TSDG algorithm

图3 EC-TSDG算法流程

Fig.3 Procedure of EC-TSDG algorithm

图4 各算法在D=1 000测试集上的平均收敛结果

Fig.4 Average convergence result of each algorithm on the test set when D=1 000

参考文献 25

1	SHI Y J, TENG H F, LI Z Q. Cooperative co-evolutionary differential evolution for function optimization[C]//Proceedings of the 1st International Conference on Natural Computation. Berlin, Germany: Springer, 2005: 1080-1088.
2	OMIDVAR M N, LI X D, YAO X. Smart use of computational resources based on contribution for cooperative co-evolutionary algorithms[C]//Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM Press, 2011: 1115-1122.
3	KESHK M, SINGH H, ABBASS H. Automatic estimation of differential evolution parameters using hidden Markov models. Evolutionary Intelligence, 2018, 10(3): 77- 93.
4	DENG L B, LI C L, SUN G J. An adaptive dimension level adjustment framework for differential evolution. Knowledge-Based Systems, 2020, 206, 106388. doi: 10.1016/j.knosys.2020.106388
5	MALLIPEDDI R, SUGANTHAN P N, PAN Q K, et al. Differential evolution algorithm with ensemble of parameters and mutation strategies. Applied Soft Computing, 2011, 11(2): 1679- 1696. doi: 10.1016/j.asoc.2010.04.024
6	SUN G J, WU Y R, DENG L B, et al. Elite representative based individual adaptive regeneration framework for differential evolution. IEEE Access, 2020, 8, 61226- 61245. doi: 10.1109/ACCESS.2020.2983840
7	SEMNANI A, KAMYAB M, REKANOS I T. Reconstruction of one-dimensional dielectric scatterers using differential evolution and particle swarm optimization. IEEE Geoscience and Remote Sensing Letters, 2009, 6(4): 671- 675. doi: 10.1109/LGRS.2009.2023246
8	王磊, 林鸿飞, 滕弘飞. 并行协同差异进化算法研究. 计算机工程, 2012, 38(4): 182-184, 190. URL
	WANG L, LIN H F, TENG H F. Research on parallel cooperative coevolutionary differential evolution algorithm. Computer Engineering, 2012, 38(4): 182-184, 190. URL
9	TSENG L Y, CHEN C. Multiple trajectory search for large scale global optimization[C]//Proceedings of the IEEE World Congress on Computational Intelligence. Washington D. C., USA: IEEE Press, 2008: 3052-3059.
10	MANIEZZO V, GAMBARDELLA L M, de LUIGI F. Ant colony optimization[M]//ONWUBOLU G C, BABU B V. New optimization techniques in engineering. Berlin, Germany: Springer, 2004: 101-121.
11	MOLINA D, LOZANO M, SÁNCHEZ A M, et al. Memetic algorithms based on local search chains for large scale continuous optimisation problems: MA-SSW-Chains. Soft Computing: A Fusion of Foundations, Methodologies and Applications, 2011, 15(11): 2201- 2220.
12	YEN G G, DANESHYARI M. Diversity-based information exchange among multiple swarms in particle swarm optimization. International Journal of Computational Intelligence and Applications, 2008, 7(1): 57- 75. doi: 10.1142/S1469026808002144
13	MOHAPATRA P, DAS K N, ROY S. A modified competitive swarm optimizer for large scale optimization problems. Applied Soft Computing, 2017, 59(C): 340- 362.
14	MOHAPATRA P, DAS K N, ROY S. Inherited competitive swarm optimizer for large-scale optimization problems[M]//YADAV N, YADAV A, BANSAL J, et al. Harmony search and nature inspired optimization algorithms. Berlin, Germany: Springer, 2019: 85-95.
15	CHENG R, JIN Y C. A competitive swarm optimizer for large scale optimization. IEEE Transactions on Cybernetics, 2015, 45(2): 191- 204. doi: 10.1109/TCYB.2014.2322602
16	COLLANGE G, REYNAUD S, HANSEN N. Covariance matrix adaptation evolution strategy for multidisciplinary optimization of expendable launcher family[C]//Proceedings of the 13th AIAA/ISSMO Multidisciplinary Analysis Optimization Conference. Washington D. C., USA: IEEE Press, 2010: 9088.
17	刘方洁. 基于分组与局部搜索的大规模全局优化新算法[D]. 西安: 西安电子科技大学, 2017.
	LIU F J. New algorithms based on decomposing and local search for large scale global optimization[D]. Xi'an: Xidian University, 2017. (in Chinese)
18	YANG Z Y, TANG K, YAO X. Large scale evolutionary optimization using cooperative coevolution. Information Sciences: An International Journal, 2008, 178(15): 2985- 2999. doi: 10.1016/j.ins.2008.02.017
19	OMIDVAR M N, LI X D, MEI Y, et al. Cooperative co-evolution with differential grouping for large scale optimization. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 378- 393. doi: 10.1109/TEVC.2013.2281543
20	SUN Y, KIRLEY M, HALGAMUGE S K. Extended differential grouping for large scale global optimization with direct and indirect variable interactions[C]//Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM Press, 2015: 313-320.
21	ZHANG X Y, GONG Y J, LIN Y, et al. Dynamic cooperative coevolution for large scale optimization. IEEE Transactions on Evolutionary Computation, 2019, 23(6): 935- 948. doi: 10.1109/TEVC.2019.2895860
22	WANG Y, CAI Z X, ZHANG Q F. Differential evolution with composite trial vector generation strategies and control parameters. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 55- 66. doi: 10.1109/TEVC.2010.2087271
23	LI X, TANG K, OMIDVAR M N, et al. Benchmark functions for the CEC'2013 special session and competition on large-scale global optimization. Gene, 2013, 7(33): 8.
24	ZHANG J Q, SANDERSON A C. JADE: adaptive differential evolution with optional external archive. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 945- 958. doi: 10.1109/TEVC.2009.2014613
25	YANG Z Y, TANG K, YAO X. Self-adaptive differential evolution with neighborhood search[C]//Proceedings of the IEEE World Congress on Computational Intelligence. Washington D. C., USA: IEEE Press, 2008: 1110-1116.

[1]	徐冰纯, 葛洪伟, 王燕燕. 基于多种群多模型协同进化的粒子群优化算法[J]. 计算机工程, 2013, 39(5): 200-203,208.
[2]	刘海龙，张凤斌，席亮. 基于协同进化的免疫检测器分布优化算法[J]. 计算机工程, 2013, 39(11): 154-157.
[3]	王磊, 林鸿飞, 滕弘飞. 并行协同差异进化算法研究[J]. 计算机工程, 2012, 38(04): 182-184.
[4]	陈峰, 武小悦. 带局部交互的多星TT&C调度合作协同进化[J]. 计算机工程, 2011, 37(6): 250-252.
[5]	邵增珍, 王洪国, 刘弘, 赵学臣. 具有趋向向量及迁移特征的协同PSO算法[J]. 计算机工程, 2011, 37(21): 185-187,193.
[6]	陈旺, 史彦军, 滕弘飞. 一种求解RCPSP的协同进化分布估计算法[J]. 计算机工程, 2011, 37(14): 134-136.
[7]	陈羲, 李淼, 袁媛, 高会议, 郑高伟. 基于协同进化遗传算法的模型拟合研究[J]. 计算机工程, 2010, 36(24): 147-149.
[8]	臧文科, 杨杰, 韩秀萍. 基于动态小生境集的多种群协同进化模型[J]. 计算机工程, 2010, 36(18): 226-228.
[9]	袁勇;梁永全. 基于协同进化遗传算法的多议题谈判[J]. 计算机工程, 2009, 35(4): 187-189.
[10]	杨城;谢志龙. 复杂适应系统的多层级建模研究[J]. 计算机工程, 2009, 35(22): 244-247.
[11]	胡桂武. 基于迁徙差分进化算法集成的模体识别[J]. 计算机工程, 2008, 34(11): 12-14.
[12]	刘升;王行愚;游晓明. 基于免疫计算的Multi-agent系统设计方法[J]. 计算机工程, 2007, 33(22): 238-239，.
[13]	袁勇;梁永全. 基于协同进化遗传算法的自动谈判[J]. 计算机工程, 2007, 33(20): 190-192.
[14]	高坚;崔志燮. 多Agent系统中的协同进化研究[J]. 计算机工程, 2006, 32(16): 188-189,.

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

选择包含的内容