An ε -domination based two-archive 2 algorithm for many-objective optimization

doi:10.23919/JSEE.2022.000016

Journal of Systems Engineering and Electronics ›› 2022, Vol. 33 ›› Issue (1): 156-169.doi: 10.23919/JSEE.2022.000016

• SYSTEMS ENGINEERING • Previous Articles Next Articles

An ε -domination based two-archive 2 algorithm for many-objective optimization

Tianwei WU¹^,²(), Siguang AN¹^,²^,*(), Jianqiang HAN¹^,²(), Nanying SHENTU¹^,²()

¹ College of Mechanical and Electrical Engineering, China Jiliang University, Hangzhou 310018, China
² Key Laboratory of Intelligent Manufacturing Quality Big Data Tracing and Analysis of Zhejiang Province, China jiliang University, Hangzhou 310018, China

Received:2020-12-09 Accepted:2021-12-13 Online:2022-02-18 Published:2022-02-22
Contact: Siguang AN E-mail:554729930@qq.com;annsg@126.com;hjqsmx@sina.com;stnying@163.com
About author:
WU Tianwei was born in 1996. He received his B.S. degree in engineering degree from Hefei Normal University, China in 2017. He is currently working toward his M.S. degree in control engineering at China Jiliang University, Hangzhou, China. His research interests include many-objective optimization problems and objective reduction optimization algorithms. E-mail: 554729930@qq.com

AN Siguang was born in 1981. She received her M.S. and Ph.D. degrees in electrical engineering from Zhejiang University, Hangzhou, China, in 2006 and 2012. From 2006 to 2014, she was a research assistant in China Jiliang University, Hangzhou, China. Since 2015, she has been an assistant professor with the Electrical Engineering Department, China Jiliang University. Her research interests include optimization algorithms, electromagnetic inverse problems, and the computational method on electromagnetic devices. E-mail: annsg@126.com

HAN Jianqiang was born in 1970. He received his Ph.D. degree in electron science and technology from Xi’an Jiaotong University in 2003. He was a post-doctoral fellow with the State Key Laboratory of Transducer Technology, Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, from 2004 to 2005. Since 2006, he has been working as a professor with the College of Mechanical and Electrical Engineering, China Jiliang University. His research interests are micromachined resonant accelerometers, resonant IR detectors, and thin-film thermal converter. E-mail: hjqsmx@sina.com

SHENTU Nanying was born in 1977. She received her B.S. and M.S. degrees from Chongqing University, Chongqing, China, in 1999 and 2003, respectively. She is currently pursuing her Ph.D. degree at National Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou, Zhejiang, China. She is a lecturer at China Jiliang University, Hangzhou, Zhejiang. Her research interests cover industrial field parameter measurement, design, fabrication and theoretical modeling of sensors, and geohazard monitoring. E-mail: stnying@163.com
Supported by:
This work was supported by the National Natural Science Foundation of China, Natural Science Foundation of Zhejiang Province (52077203; LY19E070003) and the Fundamental Research Funds for the Provincial Universities of Zhejiang (2021YW06)

Abstract

Abstract:

The two-archive 2 algorithm (Two_Arch2) is a many-objective evolutionary algorithm for balancing the convergence, diversity, and complexity using diversity archive (DA) and convergence archive (CA). However, the individuals in DA are selected based on the traditional Pareto dominance which decreases the selection pressure in the high-dimensional problems. The traditional algorithm even cannot converge due to the weak selection pressure. Meanwhile, Two_Arch2 adopts DA as the output of the algorithm which is hard to maintain diversity and coverage of the final solutions synchronously and increase the complexity of the algorithm. To increase the evolutionary pressure of the algorithm and improve distribution and convergence of the final solutions, an ${\textit{ε}} $-domination based Two_Arch2 algorithm (${\textit{ε}} $-Two_Arch2) for many-objective problems (MaOPs) is proposed in this paper. In ${\textit{ε}} $-Two_Arch2, to decrease the computational complexity and speed up the convergence, a novel evolutionary framework with a fast update strategy is proposed; to increase the selection pressure, ${\textit{ε}} $-domination is assigned to update the individuals in DA; to guarantee the uniform distribution of the solution, a boundary protection strategy based on $ {\mathit{I}}_{\mathit{{\textit{ε}} }+} $ indicator is designated as two steps selection strategies to update individuals in CA. To evaluate the performance of the proposed algorithm, a series of benchmark functions with different numbers of objectives is solved. The results demonstrate that the proposed method is competitive with the state-of-the-art multi-objective evolutionary algorithms and the efficiency of the algorithm is significantly improved compared with Two_Arch2.

Key words: many-objective optimization, $\varepsilon $-domination, boundary protection strategy, two-archive algorithm

Tianwei WU, Siguang AN, Jianqiang HAN, Nanying SHENTU. An ε -domination based two-archive 2 algorithm for many-objective optimization[J]. Journal of Systems Engineering and Electronics, 2022, 33(1): 156-169.

Figures/Tables 20

Fig 1

Fig 2

Table 1

Table 2

Table 3

Table 4

Table 5

Table 6

Table 7

Table 8

Table 9

Table 10

Table 11

Table 12

Table 13

Table 14

Fig 3

Fig 4

References 11

12	LIU Y, ZHU N B, LI K L, et al An angle dominance criterion for evolutionary many-objective optimization. Information Sciences, 2020, 509, 376- 399. doi: 10.1016/j.ins.2018.12.078
13	DEB K, JAIN H An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Trans. on Evolutionary Computation, 2014, 18 (4): 577- 601. doi: 10.1109/TEVC.2013.2281535
14	YANG S X, LI M Q, LIU X H, et al A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans. on Evolutionary Computation, 2013, 17 (5): 721- 736. doi: 10.1109/TEVC.2012.2227145
15	ASAFUDDOULA M, RAY T, SARKER R A decomposition-based evolutionary algorithm for many objective optimization. IEEE Trans. on Evolutionary Computation, 2015, 19 (3): 445- 460. doi: 10.1109/TEVC.2014.2339823
16	YUAN Y, XU H, WANG B, et al Balancing convergence and diversity in decomposition-based many-objective optimizers. IEEE Trans. on Evolutionary Computation, 2016, 20 (2): 180- 198. doi: 10.1109/TEVC.2015.2443001
17	LYU C Z, LI W M Evolutionary many objective optimization based on bidirectional decomposition. Journal of Systems Engineering and Electronics, 2019, 30 (2): 319- 326. doi: 10.21629/JSEE.2019.02.11
18	BADER J, ZITZLER E HypE: an algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation, 2011, 19 (1): 45- 76. doi: 10.1162/EVCO_a_00009
19	BADER J, ZITZLER E. A hypervolume-based optimizer for high-dimensional objective spaces. JONES D, TAMIZ M, RIES J. ed. New developments in multiple objective and goal programming. Berlin: Springer, 2010.
20	BROCKHOFF D, WAGNER T, TRAUTMANN H On the properties of the R2 indicator. Proc. of the 14th Annual Conference on Genetic and Evolutionary Computation, 2012, 465- 472.
21	GOMEZ R H, COELLO COELLO C A Improved metaheuristic based on the R2 indicator for many-objective optimization. Proc. of the Annual Conference on Genetic and Evolutionary Computation, 2015, 679- 686.
22	SUN Y N, YEN G G, YI Z IGD indicator-based evolutionary algorithm for many-objective optimization problems. IEEE Trans. on Evolutionary Computation, 2019, 23 (2): 173- 187. doi: 10.1109/TEVC.2018.2791283
23	SAXENA D K, DEB K Non-linear dimensionality reduction procedures for certain large-dimensional multi-objective optimization problems: employing correntropy and a novel maximum variance unfolding. Proc. of the 4th International Conference on Evolutionary Multi-criterion Optimization, 2007, 772- 787.
24	FREITAS A R R, FLEMING P J, GUIMARAES F G A non-parametric harmony-based objective reduction method for many-objective optimization. Proc. of the IEEE International Conference on Systems, 2013, 651- 656.
25	YUAN Y, ONG Y, GUPTA A, et al Objective reduction in many-objective optimization: evolutionary multiobjective approaches and comprehensive analysis. IEEE Trans. on Evolutionary Computation, 2018, 22 (2): 189- 210. doi: 10.1109/TEVC.2017.2672668
26	LI M H, WEI J X, SONG A, et al Objective reduction using objective sampling and affinity propagation for many-objective optimization problems. IEEE Access, 2019, 7, 68392- 68403. doi: 10.1109/ACCESS.2019.2914069
27	PRADITWONG K, YAO X A new multi-objective evolutionary optimisation algorithm: the two-archive algorithm. Proc. of the International Conference on Computational Intelligence and Security, 2006, 286- 291.
28	LI B D, LI J L, TANG K, et al An improved two archive algorithm for many-objective optimization. Proc. of the IEEE Congress on Evolutionary Computation, 2014, 2869- 2876.
29	DAI C Two-archive evolutionary algorithm based on multi-search strategy for many-objective optimization. IEEE Access, 2019, 7, 79277- 79286. doi: 10.1109/ACCESS.2019.2917899
30	WANG H D, JIAO L C, YAO X Two_Arch2: an improved two-archive algorithm for many-objective optimization. IEEE Trans. on Evolutionary Computation, 2015, 19 (4): 524- 541. doi: 10.1109/TEVC.2014.2350987
31	LIANG Z P, LUO T T, HU K F, et al An indicator-based many-objective evolutionary algorithm with boundary protection. IEEE Trans. on Cybernetics, 2021, 51 (9): 4553- 4566. doi: 10.1109/TCYB.2019.2960302
32	ZHANG X Y, TIAN Y, JIN Y C A knee point-driven evolutionary algorithm for many-objective optimization. IEEE Trans. on Evolutionary Computation, 2015, 19 (6): 761- 776. doi: 10.1109/TEVC.2014.2378512
33	WANG R, ZHANG Q F, ZHANG T Pareto adaptive scalarising functions for decomposition based algorithms. Proc. of the International Conference on Evolutionary Multi-Criterion Optimization, 2015, 248- 262.
34	DEB K, THIELE L, LAUMANNS M, et al Scalable multi- objective optimization test problems. Proc. of the Congress on Evolutionary Computation, 2002, 825- 830.
35	HUBAND S, HINGSTON P, BARONE L, et al A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. on Evolutionary Computation, 2006, 10 (5): 477- 506. doi: 10.1109/TEVC.2005.861417
36	ZHANG Q F, ZHOU A, ZHAO S Z, et al. Multiobjective optimization test instances for the CEC 2009 special session and competition. http://www.al-roomi.org/multimedia/CEC_Database/CEC2009/MultiObjectiveEA/CEC2009_MultiObjectiveEA_TechnicalReport.pdf.
37	ZITZLER E, THIELE L Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Trans. on Evolutionary Computation, 1999, 3 (4): 257- 271. doi: 10.1109/4235.797969
38	DEB K, AGRAWAL R B Simulated binary crossover for continuous search space. Complex Systems, 1994, 9 (3): 115- 148.
1	DEB K. Multi-objective optimization using evolutionary algorithms. New York: John Wiley & Sons, 2001.
2	MIETTINEN K. Nonlinear multiobjective optimization. Berlin: Springer, 1999.
3	DEB K, AGARWAL S, PRATAP A, et al A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. Proc. of the 6th International Conference on Parallel Problem Solving from Nature, 2000, 849- 858.
4	ZITZLER E, LAUMANNS M, THIELE L. SPEA2: improving the strength pareto evolutionary algorithm. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.5073&rep=rep1&type=pdf. DOI: 10.3929/ethz-a-004284029.
5	PRADITWONG K, YAO X How well do multi-objective evolutionary algorithms scale to large problems. Proc. of the IEEE Congress on Evolutionary Computation, 2007, 3959- 3966.
6	ISHIBUCHI H, TSUKAMOTO N, NOJIMA Y Evolutionary many-objective optimization: a short review. Proc. of the IEEE Congress on Evolutionary Computation, 2008, 2419- 2426.
7	HERNANDEZ-DIAZ A G, SANTANA-QUINTERO L V, COELLO COELLO C A, et al Pareto-adaptive ε-dominance. Evolutionary Computation, 2007, 15 (4): 493- 517. doi: 10.1162/evco.2007.15.4.493
8	DEB K, MOHAN M, MISHRA S Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions. Evolutionary Computation, 2005, 13 (4): 501- 525. doi: 10.1162/106365605774666895
9	WANG R, PURSHOUSE R C, FLEMING P J Preference-inspired coevolutionary algorithms for many-objective optimization. IEEE Trans. on Evolutionary Computation, 2013, 17 (4): 474- 494. doi: 10.1109/TEVC.2012.2204264
10	LI M, YANG S X, LIU X H Shift-based density estimation for pareto-based algorithms in many-objective optimization. IEEE Trans. on Evolutionary Computation, 2014, 18 (3): 348- 365. doi: 10.1109/TEVC.2013.2262178
11	DAI C, WANG Y P, HU L J An improved α-dominance strategy for many-objective optimization problems. Soft Computing, 2016, 20 (3): 1105- 1111. doi: 10.1007/s00500-014-1570-8

Parameter	Value
Crossover probability	1.0
Mutation probability	1/n
${\text{ε} }\; in \;(1)$	0.06
P in (4)	0.3

Problem	Number of objectives	ε-Two_Arch2	Two_Arch2	NSGA-III	PICEA-g	GrEA	SPEA2+SDE
DTLZ1	4	0.2615(5)	0.2734(6)	0.0401(1)	0.2608(4)	0.1336(3)	0.0418(2)
	5	0.2518(4)	0.2700(5)	0.0620(2)	0.2991(6)	0.1985(3)	0.0619(1)
	6	0.2420(3)	0.2662(5)	0.1176(2)	0.3291(6)	0.2521 (4)	0.0793(1)
	7	0.2572(3)	0.2636(4)	0.1078(2)	0.3857 (6)	0.3273(5)	0.0981(1)
	8	0.2517(3)	0.2621(4)	0.1304(2)	0.3979(6)	0.3891(5)	0.1068(1)
	9	0.2605(3)	0.2677(4)	0.2476(2)	0.4467(6)	0.4012(5)	0.1367(1)
	10	0.2732(3)	0.2736(4)	0.1098(1)	0.3697(5)	0.3937(6)	0.1204(2)

Problem	Number of objectives	ε-Two_Arch2	Two_Arch2	NSGA-III	PICEA-g	GrEA	SPEA2+SDE
DTLZ2	4	0.1055(1)	0.1377(4)	0.1161(2)	0.1880(6)	0.1247 (3)	0.1418(5)
	5	0.1394(1)	0.2183(5)	0.1897(2)	0.2583(6)	0.1902(3)	0.2089(4)
	6	0.1736(1)	0.2940(5)	0.2572(3)	0.3218(6)	0.2549(2)	0.2665(4)
	7	0.2029(1)	0.3627(5)	0.3318(3)	0.4101(6)	0.3262(2)	0.3331(4)
	8	0.2273(1)	0.4248(5)	0.3558(3)	0.4609(6)	0.4015(4)	0.3455(2)
	9	0.2331(1)	0.4804(3)	0.4924(4)	0.7169(5)	0.8121(6)	0.4140(2)
	10	0.2808(1)	0.5192(5)	0.3806(3)	0.4513(4)	0.9781(6)	0.3561(2)

Problem	Number of objectives	ε-Two_Arch2	Two_Arch2	NSGA-III	PICEA-g	GrEA	SPEA2+SDE
DTLZ3	4	0.0958(1)	0.1335(3)	0.1170(2)	0.5167(5)	0.8396(6)	0.1409(4)
	5	0.1384(1)	0.2091(3)	0.1927(2)	0.5899(5)	0.8499(6)	0.2071(4)
	6	0.1815(1)	0.2827(3)	1.3700(6)	0.7024(4)	1.1058(5)	0.2683(2)
	7	0.2069(1)	0.3481(3)	0.7919(4)	0.8489(5)	1.9463(6)	0.3425(2)
	8	0.2200(1)	0.4129(3)	1.8506(5)	0.8660(4)	3.7406(6)	0.3454(2)
	9	0.2409(1)	0.4692(3)	8.7805(6)	0.9951(4)	2.5892(5)	0.4314(2)
	10	0.2585(1)	0.5175(3)	1.6335(6)	0.9302(5)	1.5928(5)	0.3538(2)

Problem	Number of objectives	ε-Two_Arch2	Two_Arch2	NSGA-III	PICEA-g	GrEA	SPEA2+SDE
DTLZ4	4	0.1015(1)	0.1388(2)	0.1498(4)	0.2107(6)	0.1932(5)	0.1438(3)
	5	0.1309(1)	0.2222(4)	0.1953(3)	0.3015(6)	0.1926(2)	0.2282(5)
	6	0.1621(1)	0.3016(4)	0.3032(5)	0.3402(6)	0.2570(2)	0.2811(3)
	7	0.1873(1)	0.3727(5)	0.3647(4)	0.4894(6)	0.3071(2)	0.3408(3)
	8	0.1890(1)	0.4360(6)	0.3944(4)	0.4261(5)	0.3855(3)	0.3499(2)
	9	0.2596(1)	0.4997(5)	0.4695(3)	0.5554(6)	0.4862(4)	0.4424(2)
	10	0.3079(1)	0.5349(5)	0.4077(3)	0.4107(4)	0.5389(6)	0.3714(2)

An ε -domination based two-archive 2 algorithm for many-objective optimization

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 20

References 11

Related Articles 1

Recommended Articles

Metrics

Comments

Problem	Number of objectives	ε-Two_Arch2	Two_Arch2	NSGA-III	PICEA-g	GrEA	SPEA2+SDE
WFG1	4	1.9249(6)	1.3681(5)	0.2915(1)	0.3620(3)	0.4261(4)	0.3124(2)
	5	2.1207(6)	1.6050(5)	0.4355(1)	0.5168(3)	0.5635(4)	0.4803(2)
	6	2.3325(6)	1.7400(5)	0.6402(1)	0.7368(3)	0.8636(4)	0.6932(2)
	7	2.5507(6)	2.0164(5)	0.8739(1)	0.9932(3)	1.2685(4)	0.9732(2)
	8	2.8387(6)	2.1617(5)	1.0830(1)	1.3254(2)	1.9771(4)	1.4427(3)
	9	3.2123(6)	2.4915(5)	1.2732(1)	2.1385(4)	2.1214(3)	1.7623(2)
	10	3.4066(6)	2.7621(4)	1.3463(1)	2.8271(5)	2.1551(3)	1.8376(2)

Problem	Number of objectives	ε-Two_Arch2	Two_Arch2	NSGA-III	PICEA-g	GrEA	SPEA2+SDE
WFG2	4	0.6035(4)	0.7598(6)	0.3542(1)	0.6799(5)	0.4649(3)	0.4325(2)
	5	0.6718(3)	1.0610(6)	0.6269(2)	0.8379(5)	0.6003(1)	0.6908(4)
	6	0.8332(1)	1.0692(4)	0.9738(3)	1.1085(6)	0.8967(2)	1.0851(5)
	7	1.0245(1)	1.1016(2)	1.1326(3)	1.6732(5)	1.3346(4)	1.6784(6)
	8	1.1918(2)	1.0861(1)	1.3148(3)	2.1291(6)	1.4504(4)	1.8792(5)
	9	1.4244(2)	1.3746(1)	1.4245(3)	2.6895(6)	1.6641(4)	2.3498(5)
	10	1.5496(1)	1.5913(3)	1.5758(2)	2.8271(6)	1.8796(4)	2.4723(5)

Problem	Number of objectives	ε-Two_Arch2	Two_Arch2	NSGA-III	PICEA-g	GrEA	SPEA2+SDE
WFG3	4	0.4015(6)	0.2302(3)	0.2595(4)	0.1051(1)	0.1886(2)	0.3917(5)
	5	0.4641(4)	0.4368(3)	0.4826(5)	0.1619(1)	0.1750(2)	0.7476(6)
	6	0.6939(5)	0.6680(4)	0.4316(3)	0.1367(1)	0.1576(2)	0.9573(6)
	7	0.7021(2)	0.8558(4)	0.8874(5)	0.8301(3)	0.2385(1)	1.4632(6)
	8	1.0605(3)	1.1274(4)	0.9637(2)	1.3544(5)	0.2802(1)	1.7383(6)
	9	1.1837(3)	1.3415(4)	0.9674(2)	1.4762(5)	0.3067(1)	1.9325(6)
	10	1.2162(3)	1.4811(4)	0.9933(2)	1.9196(5)	0.4649(1)	1.9692(6)

Problem	Number of objectives	ε-Two_Arch2	Two_Arch2	NSGA-III	PICEA-g	GrEA	SPEA2+SDE
WFG4	4	0.5396(1)	0.6539(4)	0.6047(3)	0.7776(6)	0.5904(2)	0.7050(5)
	5	1.0659(1)	1.2381(4)	1.1243(3)	1.3414(6)	1.0675(2)	1.2414(5)
	6	1.4878(1)	1.9047(5)	1.7626(3)	3.4694(6)	1.6227(2)	1.8411(4)
	7	2.1132(1)	2.6881(5)	2.4735(2)	3.9842(6)	2.5321(3)	2.6742(4)
	8	2.0494(1)	3.4703(5)	2.9879(3)	4.3705(6)	2.8534(5)	2.9891(4)
	9	2.5717(1)	4.3499(5)	2.8734(2)	5.0312(6)	3.1595(3)	3.6849(4)
	10	3.0694(2)	5.1960(5)	2.7989(1)	5.2501(6)	3.8251(3)	3.8387(4)