Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (5): 1348-1354.DOI: 10.11772/j.issn.1001-9081.2024020255
Special Issue: 进化计算专题(2024年第5期“进化计算专题”导读,全文已上线)
• Special issue on evolutionary calculation • Previous Articles Next Articles
Maojiang TIAN, Mingke CHEN, Wei DU(), Wenli DU
Received:
2024-03-12
Revised:
2024-04-05
Accepted:
2024-04-07
Online:
2024-04-26
Published:
2024-05-10
Contact:
Wei DU
About author:
TIAN Maojiang, born in 2000, Ph. D. candidate. His research interests include evolutionary computation, large-scale optimization.Supported by:
通讯作者:
堵威
作者简介:
田茂江(2000—),男,山东淄博人,博士研究生,主要研究方向:进化计算、大规模优化基金资助:
CLC Number:
Maojiang TIAN, Mingke CHEN, Wei DU, Wenli DU. Two-stage differential grouping method for large-scale overlapping problems[J]. Journal of Computer Applications, 2024, 44(5): 1348-1354.
田茂江, 陈鸣科, 堵威, 杜文莉. 面向大规模重叠问题的两阶段差分分组方法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1348-1354.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2024020255
函数 | 类型 | 子组规模 | 基函数 |
---|---|---|---|
一致 | 100×5+50×5+25×10 | Schwefel | |
冲突 | 100×5+50×5+25×10 | ||
一致 | 50×20 | ||
冲突 | 50×20 | ||
一致 | 100×5+50×5+25×10 | Elliptic | |
冲突 | 100×5+50×5+25×10 | ||
一致 | 50×20 | ||
冲突 | 50×20 |
Tab. 1 Large-scale overlapping benchmark functions
函数 | 类型 | 子组规模 | 基函数 |
---|---|---|---|
一致 | 100×5+50×5+25×10 | Schwefel | |
冲突 | 100×5+50×5+25×10 | ||
一致 | 50×20 | ||
冲突 | 50×20 | ||
一致 | 100×5+50×5+25×10 | Elliptic | |
冲突 | 100×5+50×5+25×10 | ||
一致 | 50×20 | ||
冲突 | 50×20 |
函数 | TSDG | RDG3 | ORDG | CBCCO | ||||
---|---|---|---|---|---|---|---|---|
DA/% | FE | DA/% | FE | DA/% | FE | DA/% | FE | |
100 | 24 173 | 76.28 | 16 424 | 87.47 | 15 822 | 100 | 409 966 | |
100 | 23 876 | 76.32 | 16 437 | 83.17 | 15 815 | 100 | 409 966 | |
100 | 26 075 | 70.07 | 18 195 | 80.83 | 17 729 | 100 | 409 966 | |
100 | 25 853 | 70.48 | 18 295 | 71.50 | 17 691 | 100 | 409 966 | |
100 | 24 215 | 76.65 | 16 461 | 83.67 | 16 189 | 100 | 409 966 | |
100 | 24 056 | 76.18 | 16 325 | 83.92 | 15 822 | 100 | 409 966 | |
100 | 26 372 | 69.87 | 18 169 | 74.67 | 17 681 | 100 | 409 966 | |
100 | 26 063 | 69.68 | 18 128 | 75.83 | 18 178 | 100 | 409 966 |
Tab. 2 Decomposition results of each algorithm on large-scale overlapping problems
函数 | TSDG | RDG3 | ORDG | CBCCO | ||||
---|---|---|---|---|---|---|---|---|
DA/% | FE | DA/% | FE | DA/% | FE | DA/% | FE | |
100 | 24 173 | 76.28 | 16 424 | 87.47 | 15 822 | 100 | 409 966 | |
100 | 23 876 | 76.32 | 16 437 | 83.17 | 15 815 | 100 | 409 966 | |
100 | 26 075 | 70.07 | 18 195 | 80.83 | 17 729 | 100 | 409 966 | |
100 | 25 853 | 70.48 | 18 295 | 71.50 | 17 691 | 100 | 409 966 | |
100 | 24 215 | 76.65 | 16 461 | 83.67 | 16 189 | 100 | 409 966 | |
100 | 24 056 | 76.18 | 16 325 | 83.92 | 15 822 | 100 | 409 966 | |
100 | 26 372 | 69.87 | 18 169 | 74.67 | 17 681 | 100 | 409 966 | |
100 | 26 063 | 69.68 | 18 128 | 75.83 | 18 178 | 100 | 409 966 |
函数 | 对比项 | CSO | GL-SHADE | MLSHADE-SPA | DCC | RDG3 | ORDG | CBCCO | TSDG |
---|---|---|---|---|---|---|---|---|---|
Mean | 7.50E+08(+) | 9.12E+04(+) | 1.27E+08(+) | 7.00E+07(+) | 9.01E+03(+) | 2.17E+04(+) | 6.10E+01(+) | 2.35E+00 | |
Std. | 3.28E+08 | 4.54E+04 | 1.15E+08 | 1.27E+08 | 3.52E+03 | 2.68E+04 | 6.61E+01 | 6.45E+00 | |
Mean | 4.86E+09(+) | 4.86E+06(+) | 1.41E+07(+) | 7.71E+08(+) | 5.64E+06(+) | 5.14E+06(+) | 4.42E+06(+) | 4.40E+06 | |
Std. | 4.96E+09 | 1.57E+05 | 1.86E+06 | 3.70E+09 | 5.82E+05 | 4.99E+05 | 4.33E+04 | 4.41E+04 | |
Mean | 6.40E+08(+) | 1.53E+04(+) | 1.42E+07(+) | 2.24E+07(+) | 5.97E+04(+) | 1.33E+00(+) | 4.93E-08(+) | 2.20E-10 | |
Std. | 2.30E+08 | 1.23E+04 | 1.84E+07 | 3.33E+07 | 3.73E+04 | 3.72E+00 | 1.48E-07 | 5.37E-10 | |
Mean | 7.58E+09(+) | 4.29E+06(+) | 6.26E+07(+) | 8.66E+08(+) | 5.85E+06(+) | 5.13E+06(+) | 4.08E+06(=) | 4.07E+06 | |
Std. | 3.63E+09 | 1.22E+05 | 6.71E+07 | 2.54E+09 | 4.79E+05 | 1.40E+06 | 8.60E+04 | 5.58E+04 | |
Mean | 3.25E+11(+) | 7.34E+09(+) | 5.22E+10(+) | 8.16E+10(+) | 5.12E+07(+) | 5.04E+08(+) | 8.10E+06(+) | 2.72E+06 | |
Std. | 2.61E+10 | 2.57E+09 | 9.62E+09 | 1.95E+10 | 1.66E+07 | 9.36E+07 | 3.36E+06 | 1.32E+06 | |
Mean | 3.10E+12(+) | 6.09E+10(+) | 1.00E+12(+) | 1.03E+02(+) | 2.53E+10(+) | 2.22E+09(+) | 8.15E+08(+) | 8.12E+08 | |
Std. | 4.00E+11 | 3.07E+10 | 1.81E+11 | 3.51E+11 | 1.39E+10 | 1.60E+09 | 3.37E+06 | 2.59E+06 | |
Mean | 6.91E+11(+) | 1.27E+10(+) | 1.97E+11(+) | 2.56E+11(+) | 1.43E+08(+) | 7.54E+08(+) | 7.22E+04(+) | 3.91E+04 | |
Std. | 6.66E+11 | 2.75E+09 | 3.25E+10 | 5.66E+11120 | 6.81E+07 | 1.50E+09 | 3.95E+04 | 1.74E+04 | |
Mean | 1.06E+13(+) | 1.61E+11(+) | 2.26E+12(+) | 3.00E+12(+) | 2.20E+11(+) | 6.62E+10(+) | 2.35E+08(=) | 2.35E+08 | |
Std. | 1.17E+12 | 6.51E+10 | 2.31E+11 | 1.15E+12 | 7.58E+10 | 7.47E+10 | 4.63E+06 | 4.30E+06 | |
对比结果(胜/平/负) | 8/0/0 | 8/0/0 | 8/0/0 | 8/0/0 | 8/0/0 | 8/0/0 | 6/0/2 |
Tab. 3 Optimization results of TSDG and comparison algorithms
函数 | 对比项 | CSO | GL-SHADE | MLSHADE-SPA | DCC | RDG3 | ORDG | CBCCO | TSDG |
---|---|---|---|---|---|---|---|---|---|
Mean | 7.50E+08(+) | 9.12E+04(+) | 1.27E+08(+) | 7.00E+07(+) | 9.01E+03(+) | 2.17E+04(+) | 6.10E+01(+) | 2.35E+00 | |
Std. | 3.28E+08 | 4.54E+04 | 1.15E+08 | 1.27E+08 | 3.52E+03 | 2.68E+04 | 6.61E+01 | 6.45E+00 | |
Mean | 4.86E+09(+) | 4.86E+06(+) | 1.41E+07(+) | 7.71E+08(+) | 5.64E+06(+) | 5.14E+06(+) | 4.42E+06(+) | 4.40E+06 | |
Std. | 4.96E+09 | 1.57E+05 | 1.86E+06 | 3.70E+09 | 5.82E+05 | 4.99E+05 | 4.33E+04 | 4.41E+04 | |
Mean | 6.40E+08(+) | 1.53E+04(+) | 1.42E+07(+) | 2.24E+07(+) | 5.97E+04(+) | 1.33E+00(+) | 4.93E-08(+) | 2.20E-10 | |
Std. | 2.30E+08 | 1.23E+04 | 1.84E+07 | 3.33E+07 | 3.73E+04 | 3.72E+00 | 1.48E-07 | 5.37E-10 | |
Mean | 7.58E+09(+) | 4.29E+06(+) | 6.26E+07(+) | 8.66E+08(+) | 5.85E+06(+) | 5.13E+06(+) | 4.08E+06(=) | 4.07E+06 | |
Std. | 3.63E+09 | 1.22E+05 | 6.71E+07 | 2.54E+09 | 4.79E+05 | 1.40E+06 | 8.60E+04 | 5.58E+04 | |
Mean | 3.25E+11(+) | 7.34E+09(+) | 5.22E+10(+) | 8.16E+10(+) | 5.12E+07(+) | 5.04E+08(+) | 8.10E+06(+) | 2.72E+06 | |
Std. | 2.61E+10 | 2.57E+09 | 9.62E+09 | 1.95E+10 | 1.66E+07 | 9.36E+07 | 3.36E+06 | 1.32E+06 | |
Mean | 3.10E+12(+) | 6.09E+10(+) | 1.00E+12(+) | 1.03E+02(+) | 2.53E+10(+) | 2.22E+09(+) | 8.15E+08(+) | 8.12E+08 | |
Std. | 4.00E+11 | 3.07E+10 | 1.81E+11 | 3.51E+11 | 1.39E+10 | 1.60E+09 | 3.37E+06 | 2.59E+06 | |
Mean | 6.91E+11(+) | 1.27E+10(+) | 1.97E+11(+) | 2.56E+11(+) | 1.43E+08(+) | 7.54E+08(+) | 7.22E+04(+) | 3.91E+04 | |
Std. | 6.66E+11 | 2.75E+09 | 3.25E+10 | 5.66E+11120 | 6.81E+07 | 1.50E+09 | 3.95E+04 | 1.74E+04 | |
Mean | 1.06E+13(+) | 1.61E+11(+) | 2.26E+12(+) | 3.00E+12(+) | 2.20E+11(+) | 6.62E+10(+) | 2.35E+08(=) | 2.35E+08 | |
Std. | 1.17E+12 | 6.51E+10 | 2.31E+11 | 1.15E+12 | 7.58E+10 | 7.47E+10 | 4.63E+06 | 4.30E+06 | |
对比结果(胜/平/负) | 8/0/0 | 8/0/0 | 8/0/0 | 8/0/0 | 8/0/0 | 8/0/0 | 6/0/2 |
1 | 梁静,刘睿,瞿博阳,等.进化算法在大规模优化问题中的应用综述[J].郑州大学学报(工学版),2018,39(3):15-21. 10.13705/j.issn.1671-6833.2017.06.016 |
LIANG J, LIU R, QU B Y, et al. A survey of evolutionary algorithms for large scale optimization problem[J]. Journal of Zhengzhou University (Engineering Science), 2018,39(3):15-21. 10.13705/j.issn.1671-6833.2017.06.016 | |
2 | 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. |
3 | 黄志鹏,李兴权,朱文兴.超大规模集成电路布局的优化模型与算法[J].运筹学学报,2021,25(3):15-36. |
HUANG Z P, LI X Q, ZHU W X. Optimization models and algorithms for placement of very large scale integrated circuits[J]. Operations Research Transactions, 2021, 25(3): 15-36. | |
4 | 王伟权,丁鼎,曹淑艳.混合变邻域搜索算法求解大规模电动车辆路径优化问题[J].系统仿真学报, 2022, 34(4):910-919. 10.16182/j.issn1004731x.joss.21-1133 |
WANG W Q, DING D, CAO S Y. Hybrid variable neighborhood search algorithm for the multi-trip and heterogeneous-fleet electric vehicle routing problem[J]. Journal of System Simulation, 2022, 34(4):910-919. 10.16182/j.issn1004731x.joss.21-1133 | |
5 | VILLAGRA A, PANDOLFI D, LEGUIZAMÓN G, et al. Optimization of potable water networks with hybrid metaheuristics[C]// Proceedings of the 2017 XVII Workshop on Information Processing and Control. Piscataway: IEEE, 2017: 1-6. 10.23919/rpic.2017.8211619 |
6 | CHENG R, JIN Y. A competitive swarm optimizer for large scale optimization[J]. IEEE Transactions on Cybernetics, 2014, 45(2): 191-204. 10.1109/tcyb.2014.2322602 |
7 | WANG Z J, JIAN J R, ZHAN Z H, et al. Gene targeting differential evolution: a simple and efficient method for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2023, 27(4): 964-979. 10.1109/tevc.2022.3185665 |
8 | HE X, ZHENG Z, ZHOU Y. MMES: mixture model-based evolution strategy for large-scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 25(2): 320-333. 10.1109/tevc.2020.3034769 |
9 | JIA Y H, MEI Y, ZHANG M. Contribution-based cooperative co‑evolution for nonseparable large-scale problems with overlapping subcomponents[J]. IEEE Transactions on Cybernetics, 2020, 52(6): 4246-4259. 10.1109/TCYB.2020.3025577 |
10 | SUN Y, LI X, ERNST A, et al. Decomposition for large-scale optimization problems with overlapping components[C]// Proceedings of the 2019 IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2019: 326-333. 10.1109/cec.2019.8790204 |
11 | POTTER M A, DE JONG K A. A cooperative coevolutionary approach to function optimization[C]// Proceedings of the 1994 International Conference on Parallel Problem Solving from Nature. Berlin: Springer, 1994: 249-257. 10.1007/3-540-58484-6_269 |
12 | OMIDVAR M N, LI X, 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: ACM, 2011: 1115-1122. 10.1145/2001576.2001727 |
13 | JIA Y H, CHEN W N, GU T, et al. Distributed cooperative co-evolution with adaptive computing resource allocation for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2018, 23(2): 188-202. 10.1109/tevc.2018.2817889 |
14 | SHI Y-J, TENG H-F, LI Z-Q. Cooperative co-evolutionary differential evolution for function optimization[C]// Proceedings of the 2006 International Conference on Natural Computation, LNTCS 3611. Berlin: Springer, 2005: 1080-1088. |
15 | YANG Z, TANG K, YAO X. Large scale evolutionary optimization using cooperative coevolution[J]. Information Sciences, 2008, 178(15): 2985-2999. 10.1016/j.ins.2008.02.017 |
16 | 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, 2013, 18(3): 378-393. 10.1109/tevc.2013.2281543 |
17 | CHEN W, WEISE T, YANG Z, et al. Large-scale global optimization using cooperative coevolution with variable interaction learning[C]// Proceedings of the 2010 International Conference on Parallel Problem Solving from Nature, LNTCS 6239. Berlin: Springer, 2010: 300-309. |
18 | CHEN M, DU W, TANG Y, et al. A decomposition method for both additively and non-additively separable problems[J]. IEEE Transactions on Evolutionary Computation, 2022, 27(6): 1720-1734. 10.1109/tevc.2022.3218375 |
19 | IRAWAN D, NAUJOKS B, EMMERICH M. Cooperative-coevolution-CMA-ES with two-stage grouping[C]// Proceedings of the 2020 IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2020: 1-8. 10.1109/cec48606.2020.9185616 |
20 | LIU H, WANG Y, FAN N. A hybrid deep grouping algorithm for large scale global optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(6): 1112-1124. 10.1109/tevc.2020.2985672 |
21 | BLANCHARD J, BEAUTHIER C, CARLETTI T. Investigating overlapped strategies to solve overlapping problems in a cooperative co-evolutionary framework[C]// Proceedings of the 2021 International Conference on Optimization and Learning. Cham: Springer, 2021: 254-266. 10.1007/978-3-030-85672-4_19 |
22 | OMIDVAR M N, YANG M, MEI Y, et al. DG2: a faster and more accurate differential grouping for large-scale black-box optimization[J]. IEEE Transactions on Evolutionary Computation, 2017, 21(6): 929-942. 10.1109/tevc.2017.2694221 |
23 | ZHANG X Y, GONG Y J, LIN Y, et al. Dynamic cooperative coevolution for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(6): 935-948. 10.1109/tevc.2019.2895860 |
24 | SUN Y, OMIDVAR M N, KIRLEY M, et al. Adaptive threshold parameter estimation with recursive differential grouping for problem decomposition[C]// Proceedings of the 2018 Genetic and Evolutionary Computation Conference. New York: ACM, 2018: 889-896. 10.1145/3205455.3205483 |
25 | JIA Y-H, ZHOU Y-R, LIN Y, et al. A distributed cooperative co-evolutionary CMA evolution strategy for global optimization of large-scale overlapping problems[J]. IEEE Access, 2019, 7: 19821-19834. 10.1109/access.2019.2897282 |
26 | TANG K, LI X, SUGANTHAN P N, et al. Benchmark functions for the CEC’2010 special session and competition on large-scale global optimization[R/OL]. Hefei: University of Science and Technology of China. School of Computer Science and Technology. Nature Inspired Computation and Applications Laboratory, 2007, 24: 1-18 [2024-01-13]. . |
27 | OMIDVAR M N, LI X, TANG K. Designing benchmark problems for large-scale continuous optimization[J]. Information Sciences, 2015, 316: 419-436. 10.1016/j.ins.2014.12.062 |
28 | PACHECO-DEL-MORAL O, COELLO COELLO C A. A shade-based algorithm for large scale global optimization[C]// Proceedings of the 2020 International Conference on Parallel Problem Solving from Nature. Cham: Springer, 2020: 650-663. 10.1007/978-3-030-58112-1_45 |
29 | HADI A A, MOHAMED A W, JAMBI K M. LSHADE-SPA memetic framework for solving large-scale optimization problems[J]. Complex & Intelligent Systems, 2019, 5(1): 25-40. 10.1007/s40747-018-0086-8 |
30 | HANSEN N. The CMA evolution strategy: a tutorial[EB/OL]. [2023-11-10]. . |
[1] | Wanting ZHANG, Wenli DU, Wei DU. Multi-timescale cooperative evolutionary algorithm for large-scale crude oil scheduling [J]. Journal of Computer Applications, 2024, 44(5): 1355-1363. |
[2] | Jiawei ZHAO, Xuefeng CHEN, Liang FENG, Yaqing HOU, Zexuan ZHU, Yew‑Soon Ong. Review of evolutionary multitasking from the perspective of optimization scenarios [J]. Journal of Computer Applications, 2024, 44(5): 1325-1337. |
[3] | Kaiwen ZHAO, Peng WANG, Xiangrong TONG. Two-stage search-based constrained evolutionary multitasking optimization algorithm [J]. Journal of Computer Applications, 2024, 44(5): 1415-1422. |
[4] | Ye TIAN, Jinjin CHEN, Xingyi ZHANG. Hybrid optimizer combining evolutionary computation and gradient descent for constrained multi-objective optimization [J]. Journal of Computer Applications, 2024, 44(5): 1386-1392. |
[5] | Jie HUANG, Ruizi WU, Junli LI. Efficient adaptive robustness optimization algorithm for complex networks [J]. Journal of Computer Applications, 2024, 44(11): 3530-3539. |
[6] | Maozu GUO, Yazhe ZHANG, Lingling ZHAO. Electric vehicle charging station siting method based on spatial semantics and individual activities [J]. Journal of Computer Applications, 2023, 43(9): 2819-2827. |
[7] | Saijuan XU, Zhenyu PEI, Jiawei LIN, Genggeng LIU. Constrained multi-objective evolutionary algorithm based on multi-stage search [J]. Journal of Computer Applications, 2023, 43(8): 2345-2351. |
[8] | Erchao LI, Yanli CHENG. Dynamic multi-objective optimization algorithm based on weight vector clustering [J]. Journal of Computer Applications, 2023, 43(7): 2226-2236. |
[9] | Zhihui GAO, Meng HAN, Shujuan LIU, Ang LI, Dongliang MU. Survey of high utility itemset mining methods based on intelligent optimization algorithm [J]. Journal of Computer Applications, 2023, 43(6): 1676-1686. |
[10] | Bin WANG, Tian XIANG, Yidong LYU, Xiaofan WANG. Adaptive multi-scale feature channel grouping optimization algorithm based on NSGA‑Ⅱ [J]. Journal of Computer Applications, 2023, 43(5): 1401-1408. |
[11] | Erchao LI, Shenghui ZHANG. Dynamic multi-objective optimization algorithm based on adaptive prediction of new evaluation index [J]. Journal of Computer Applications, 2023, 43(10): 3178-3187. |
[12] | Kuineng CHEN, Xiaofang YUAN. Multi-objective hybrid evolutionary algorithm for solving open-shop scheduling problem with controllable processing time [J]. Journal of Computer Applications, 2022, 42(8): 2617-2627. |
[13] | Yu SHEN, Hecheng LI, Lijuan CHEN. Evolutionary algorithm based on approximation technique for solving bilevel programming problems [J]. Journal of Computer Applications, 2022, 42(8): 2511-2518. |
[14] | Wei LI, Yaochi FAN, Qiaoyong JIANG, Lei WANG, Qingzheng XU. Variable convolutional autoencoder method based on teaching-learning-based optimization for medical image classification [J]. Journal of Computer Applications, 2022, 42(2): 592-598. |
[15] | Feifan SHI, Xuhua SHI. Adaptive reference vector based constrained multi-objective evolutionary algorithm [J]. Journal of Computer Applications, 2022, 42(2): 542-549. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||