A $\boldsymbol{\varepsilon}$-indicator-based shuffled frog leaping algorithm for many-objective optimization problems

doi:10.21629/JSEE.2020.01.15

Journal of Systems Engineering and Electronics ›› 2020, Vol. 31 ›› Issue (1): 142-155.doi: 10.21629/JSEE.2020.01.15

• Systems Engineering • Previous Articles Next Articles

A $\boldsymbol{\varepsilon}$-indicator-based shuffled frog leaping algorithm for many-objective optimization problems

Na WANG^1,^2,*(), Yuchao SU¹(), Xiaohong CHEN¹(), Xia LI^1,²(), Dui LIU¹()

¹ College of Electronics and Information Engineering, Shenzhen University, Shenzhen 518060, China
² Guangdong Key Laboratory of Intelligent Information Processing, Shenzhen University, Shenzhen 518060, China

Received:2018-08-13 Online:2020-02-20 Published:2020-02-25
Contact: Na WANG E-mail:wangna@szu.edu.cn;yuchaosu@126.com;chenxh@szu.edu.cn;lixia@szu.edu.cn;liud@szu.edu.cn
About author:WANG Na was born in 1977. She received her B.S. degree in electronic engineering from Dalian Maritime University in 1998. She later took a successive postgraduate and doctoral programs of study and was conferred a Ph.D. degree on signal and information processing by Dalian Maritime University in 2003. Now she is a professor of College of Electronics and Information Engineering at Shenzhen University. Her main research interests include intelligent computing, machine learning and pattern recognition. E-mail: wangna@szu.edu.cn|SU Yuchao was born in 1992. He received his B.S. degree from Minnan Normal University, Zhang-zhou, China in 2016. He is pursuing his M.S. degree in Shenzhen University, China. His research interests include single-, multi-, and many-objective optimization, and artificial neural network. E-mail: yuchaosu@126.com|CHEN Xiaohong was born in 1977. She received her B.S. and M.S. degrees in electronic engineering and signal and information processing from Liaoning University in 2003 and 2006 respectively. She later was conferred a Ph.D. degree on signal and information processing by Shenzhen University in 2015. Her main research interests include intelligent computing, machine learning and pattern recognition. E-mail: chenxh@szu.edu.cn|LI Xia was born in 1968. She received her B.S. and M.S. degrees in electronic engineering and signal and information processing from Xidian University in 1989 and 1992 respectively. She was later conferred a Ph.D. degree in Department of Information Engineering by the Chinese University of Hong Kong in 1997. She is a director of Shenzhen Key Laboratory of Advanced Communication and Information Processing. Her research interests include intelligent computing and its applications, image processing and pattern recognition. E-mail: lixia@szu.edu.cn|LIU Dui was born in 1995. He received his B.S. degree from the College of Electronics and Information Engineering of Shenzhen University in 2017, where he is currently pursuing his M.S. degree. His main research interests include intelligent computing and machine learning. E-mail: liud@szu.edu.cn
Supported by:
the Shenzhen Innovation Technology Program(JCYJ20160422112909302);This work was supported by the Shenzhen Innovation Technology Program (JCYJ20160422112909302)

Abstract

Abstract:

Many-objective optimization problems take challenges to multi-objective evolutionary algorithms. A number of non-dominated solutions in population cause a difficult selection towards the Pareto front. To tackle this issue, a series of indicator-based multi-objective evolutionary algorithms (MOEAs) have been proposed to guide the evolution progress and shown promising performance. This paper proposes an indicator-based many-objective evolutionary algorithm called $ \boldsymbol{\varepsilon} $ -indicator-based shuffled frog leaping algorithm ($\boldsymbol{\varepsilon}$ -MaOSFLA), which adopts the shuffled frog leaping algorithm as an evolutionary strategy and a simple and effective $\boldsymbol{\varepsilon}$ -indicator as a fitness assignment scheme to press the population towards the Pareto front. Compared with four state-of-the-art MOEAs on several standard test problems with up to 50 objectives, the experimental results show that $\boldsymbol{\varepsilon}$ -MaOSFLA outperforms the competitors.

Key words: evolutionary algorithm, many-objective optimization, shuffled frog leaping algorithm (SFLA), $\boldsymbol{\varepsilon}$

Na WANG, Yuchao SU, Xiaohong CHEN, Xia LI, Dui LIU. A $\boldsymbol{\varepsilon}$-indicator-based shuffled frog leaping algorithm for many-objective optimization problems[J]. Journal of Systems Engineering and Electronics, 2020, 31(1): 142-155.

Figures/Tables 15

Table 1

Table 2

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Fig 11

Table 3

Table 4

References 45

1	CHAND S, WAGNER M. Evolutionary many-objective optimization: a quick-start guide. Surveys in Operations Research and Management Science, 2015, 20 (2): 35- 42. doi: 10.1016/j.sorms.2015.08.001
2	BECHIKH S, ELARBI M, SAID L B. Many-objective optimization using evolutionary algorithms: a survey. Recent Advances in Evolutionary Multi-objective Optimization, 2017, 20, 105- 137.
3	DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimisation: NSGA-Ⅱ. 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. Technical Report 103. Zurich: Swiss Federal Institute of Technology, 2001.
5	FARINA M, AMATO P. On the optimal solution definition for many-criteria optimization problems. Annual Meeting of the North American Fuzzy Information Processing Society Proceedings, 2002, 233- 238.
6	LIN Q Z, CHEN J Y, ZHAN Z H, et al. A hybrid evolutionary immune algorithm for multi-objective optimization problems. IEEE Trans. on Evolutionary Computation, 2016, 20 (5): 711- 729.
7	SU Y C, LIN Q Z, WANG J, et al. A constrained solution update strategy for multiobjective evolutionary algorithm based on decomposition. Complexity, 2019, 3251349.
8	LI B D, TANG K, LI J L, et al. Stochastic ranking algorithm for many-objective optimization based on multiple indicators. IEEE Trans. on Evolutionary Computation, 2016, 20 (6): 924- 938. doi: 10.1109/TEVC.2016.2549267
9	WANG H D, YAO Y. Corner sort for Pareto-based many-objective optimization. IEEE Trans. on Cybernetics, 2014, 44 (1): 92- 102. doi: 10.1109/TCYB.2013.2247594
10	HE Z N, YEN G G, ZHANG J. Fuzzy-based Pareto optimality for many-objective evolutionary algorithms. IEEE Trans. on Evolutionary Computation, 2014, 18 (2): 269- 285. doi: 10.1109/TEVC.2013.2258025
11	ELARBI M, BECHIKH S, GUPTA A, et al. A new decomposition-based NSGA-Ⅱ for many-objective optimization. IEEE Trans. on Systems, Man, and Cyberentics: Systems, 2018, 48 (7): 1191- 1210. doi: 10.1109/TSMC.2017.2654301
12	LI M Q, 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
13	DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point based non-dominated 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	LI K, DEB K, ZHANG Q F, et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Trans. on Evolutionary Computation, 2015, 19 (5): 694- 716. doi: 10.1109/TEVC.2014.2373386
15	ZHANG Q F, LI H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2017, 11 (6): 712- 731.
16	WANG L P, ZHANG Q F, ZHOU A M, et al. Constrained subproblems in a decomposition-based multiobjective evolutionary algorithm. IEEE Trans. on Evolutionary Computation, 2016, 20 (3): 475- 480. doi: 10.1109/TEVC.2015.2457616
17	CAI X Y, YANG Z X, FAN Z, et al. Decomposition-based-sorting and angle-based-selection for evolutionary multiobjective and many-objective optimization. IEEE Trans. on Cybernetics, 2017, 47 (9): 2824- 2837. doi: 10.1109/TCYB.2016.2586191
18	ROSTAMI S, NERI F. A fast hypervolume driven selection mechanism for many-objective optimisation problems. Swarm and Evolutionary Computation, 2017, 34, 50- 67. doi: 10.1016/j.swevo.2016.12.002
19	VO{\ss} T, FRIEDRICH T, BRINGMANN K, et al. Scaling up indicator-based MOEAs by approximating the least hypervolume contributor: a preliminary study. Proc. of the 12th Annual Conference on Genetic and Evolutionary Computation, 2010: 1975-1978.
20	ISHIBUCHI H, TSUKAMOTO N, SAKANE Y, et al. Indicator-based evolutionary algorithm with hypervolume approximation by achievement scalarizing functions. Proc. of the 12th Annual Conference on Genetic and Evolutionary Computation, 2010: 527-534.
21	ZITZLER E, KNZLI S. Indicator-based selection in multiobjective search. Proc. of the 8th International Conference on Parallel Problem Solving from Nature (PPSN Ⅷ), 2004: 832-842.
22	MA X L, ZHANG Q F, TIAN G D, et al. On Tchebycheff decomposition approaches formulti-objective evolutionary optimization. IEEE Trans. on Evolutionary Computation, 2018, 22 (2): 226- 244. doi: 10.1109/TEVC.2017.2704118
23	ALAN D M, GREGORIO T P, JOSE H B Z, et al. R2-based multi/many-objective particle swarm optimization. Computational Intelligence and Neuroscience, 2016, 1898527.
24	EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm. Journal of Water Resources Planning and Management, 2003, 129 (3): 210- 225. doi: 10.1061/(ASCE)0733-9496(2003)129:3(210)
25	LUO J P, LI X, CHEN M. Improved shuffled frog leaping algorithm for solving CVRP. Journal of Electronics and Information Technology, 2011, 33 (2): 429- 434. doi: 10.3724/SP.J.1146.2010.00328
26	WANG N, LI X, CHEN X H. Fast three-dimensional Otsu thresholding with shuffled frog leaping algorithm. Pattern Recognition Letters, 2010, 31 (13): 1809- 1815. doi: 10.1016/j.patrec.2010.06.002
27	RAHIMI-VAHED A, MIRZAEI A H. Solving a bi-criteria permutation flow-shop problem using shuffled frog leaping algorithm. Soft Computing, 2008, 12 (5): 435- 452. doi: 10.1007/s00500-007-0210-y
28	RAHIMI-VAHED A, DANGCHI M, RAFIEI H, et al. A novel hybrid multi-objective shuffled frog leaping algorithm for a bi-criteria permutation flow shop scheduling problem. International Journal of Advanced Manufacturing Technology, 2009, 41 (11): 1227- 1239.
29	RAHIMI-VAHED A, MIRZAEI A H. A hybrid multi-objective shuffled frog leaping algorithm for a mixed-model assembly line sequencing problem. Computers and Industrial Engineering, 2007, 53 (4): 642- 666. doi: 10.1016/j.cie.2007.06.007
30	ZHANG Y H, GONG Y J, GU T L, et al. DECAL: decomposition-based coevolutionary algorithm for many-objective optimization. IEEE Trans. on Cybernetics, 2019, 49 (1): 27- 41. doi: 10.1109/TCYB.2017.2762701
31	MIETTINEN K. Nonlinear multi-objective optimization. USA: Kluwer Academic, 2001.
32	ZITZLER E, KNZLI S. Indicator-based selection in multiobjective search. Proc. of the 8th International Conference on Parallel Problem Solving from Nature (PPSN Ⅷ), 2004: 832-842.
33	ZITZLER E, THIELE L, LAUMANNS M, et al. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. on Evolutionary Computation, 2003, 7 (2): 117- 132. doi: 10.1109/TEVC.2003.810758
34	BASSEUR M, LIEFOOGHE A, LE K, et al. The efficiency of indicator-based local search for multi-objective combinatorial optimization problems. Journal of Heuristics, 2012, 18 (2): 263- 296. doi: 10.1007/s10732-011-9178-y
35	DEB K, THIELE L, LAUMANNS M, et al. Scalable test problems for evolutionary multiobjective optimization. Advanced Information and Knowledge Processing Series. Berlin, Germany: Springer, 2005: 105-145.
36	HUBAND S, BARONE L, WHILE L, et al. A scalable multi-objective test problem toolkit. Lecture Notes in Computer Science, 2005, 3410, 280- 295.
37	HUBAND S, HINGSTON P, BARONE L, et al. A review of multi-objective test problems and a scalable test problem toolkit. IEEE Trans. on Evolutionary Computation, 2006, 10 (5): 477- 506. doi: 10.1109/TEVC.2005.861417
38	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
39	RAQUEL H G, 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.
40	KNOWLES J, THIELE L, ZITZLER E. A tutorial on the performance assessment of stochastive multiobjective optimizers. Technical report TIK-Report No. 214. Zurich: Computer Engineering and Networks Laboratory, ETH, 2005.
41	LI M Q, YANG S X, LIU X H, et al. A comparative study on evolutionary algorithms for many-objective optimization. Proc. of the 7th International Conference on Evolutionary Multi-Criterion Optimization, 2013: 261-275.
42	BLEULER S, LAUMANNS M, THIELE L, et al. PISA——a platform and programming language independent interface for search algorithms. Proc. of the International Conference on Evolutionary Multi-Criterion Optimization, 2003: 494-508.
43	SU Y C, WANG J, MA L J, et al. A hybridized angle-encouragement-based decomposition approach for many-objective optimization problems. Applied Soft Computing, 2019, 78, 355- 372. doi: 10.1016/j.asoc.2019.02.026
44	BEUME N, NAUJOKS B, EMMERICH M. SMS-EMOA: multiobjective selection based on dominated hypervolume. European Journal on Operational Research, 2007, 181 (3): 1653- 1669. doi: 10.1016/j.ejor.2006.08.008
45	SCHOTT J R. Fault tolerant design using single and multi-criteria genetic algorithm optimization. Boston, USA: Massachusetts Institute of Technology, 1995.

Problem	Number of variables	Geometry of PF
DTLZ1	$M$+4	Linear
DTLZ2	$M$+9	Concave
DTLZ3	$M$+9	Concave
DTLZ4	$M$ +9	Concave
DTLZ7	$M$ +9	Disconnected, mixed
WFG2	$M$ +19	Convex, disconnected
WFG3	$M$ +19	Linear, degenerate
WFG4	$M$ +19	Concave

Test problem	Reference point
DTLZ1	$(1.5, 1.5, \ldots)$
DTLZ2-4	$(2, 2, \ldots)$
DTLZ7	$(2, 2, \ldots, 2M+1)$
WFG2-4	$(3, 5, \ldots, 2M+1)$

$M$	2$\times $50	4$\times $25	5$\times $20	10$\times $10
3	7.292 8	7.388 8	7.374 8	7.364 8
5	31.566 9	31.573 6	31.512 1	31.419 6
10	1 020	1 022	1.020	1 016

$M$	$t = 0.8m$	$t = m$	$t = 1.2 m$
3	7.374 1	7.381 5	7.379 0
5	31.476 0	31.559 9	31.529 1
10	1 021	1 019	1 021

[1]	Kewei YANG, Boyuan XIA, Gang CHEN, Zhiwei YANG, Minghao LI. Multi-objective optimization of operation loop recommendation for kill web [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 969-985.
[2]	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.
[3]	Alireza MOHSENI, Vincent DUCHAINE, Tony WONG. Experimental study of path planning problem using EMCOA for a holonomic mobile robot [J]. Journal of Systems Engineering and Electronics, 2021, 32(6): 1450-1462.
[4]	Cuiyu WANG, Yang LI, Xinyu LI. Solving flexible job shop scheduling problem by a multi-swarm collaborative genetic algorithm [J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 261-271.
[5]	Xiuli WU, Junjian PENG, Zirun XIE, Ning ZHAO, Shaomin WU. An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches [J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 272-285.
[6]	Huixiang ZHEN, Wenyin GONG, Ling WANG. Data-driven evolutionary sampling optimization for expensive problems [J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 318-330.
[7]	Chengzhong LYU, Weimin LI. Evolutionary many objective optimization based on bidirectional decomposition [J]. Journal of Systems Engineering and Electronics, 2019, 30(2): 319-326.
[8]	Shu Wang, Xinyu Da, Mudong Li, and Tong Han. Adaptive backtracking search optimization algorithm with pattern search for numerical optimization [J]. Journal of Systems Engineering and Electronics, 2016, 27(2): 395-406.
[9]	Ying Zhang, Rennong Yang, Jialiang Zuo, and Xiaoning Jing. Enhancing MOEA/D with uniform population initialization, weight vector design and adjustment using uniform design [J]. Journal of Systems Engineering and Electronics, 2015, 26(5): 1010-1022.
[10]	Yu Xue, Yi Zhuang, Tianquan Ni, Jian Ouyang, and Zhou Wang. Enhanced self-adaptive evolutionary algorithm for numerical optimization [J]. Journal of Systems Engineering and Electronics, 2012, 23(6): 921-928.
[11]	Liu Chun’an & Wang Yuping. Multiobjective evolutionary algorithm for dynamic nonlinear constrained optimization problems [J]. Journal of Systems Engineering and Electronics, 2009, 20(1): 204-210.

A $\boldsymbol{\varepsilon}$-indicator-based shuffled frog leaping algorithm for many-objective optimization problems

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 15

References 45

Related Articles 11

Recommended Articles

Metrics

Comments