Evolutionary many objective optimization based on bidirectional decomposition

doi:10.21629/JSEE.2019.02.11

Abstract

Abstract:

The decomposition based approach decomposes a multi-objective problem into a series of single objective subproblems, which are optimized along contours towards the ideal point. But non-dominated solutions cannot spread uniformly, since the Pareto front shows different features, such as concave and convex. To improve the distribution uniformity of non-dominated solutions, a bidirectional decomposition based approach that constructs two search directions is proposed to provide a uniform distribution no matter what features problems have. Since two populations along two search directions show differently on diversity and convergence, an adaptive neighborhood selection approach is presented to choose suitable parents for the offspring generation. In order to avoid the problem of the shrinking search region caused by the close distance of the ideal and nadir points, a reference point update approach is presented. The performance of the proposed algorithm is validated with four state-of-the-art algorithms. Experimental results demonstrate the superiority of the proposed algorithm on all considered test problems.

Key words: many objective optimization, bidirectional decomposition, reference update, evolutionary algorithm

Chengzhong LYU, Weimin LI. Evolutionary many objective optimization based on bidirectional decomposition[J]. Journal of Systems Engineering and Electronics, 2019, 30(2): 319-326.

Figures/Tables 5

Fig 1

Table 1

Table 2

Fig 2

Fig 3

References 23

1	LI J T, ZHANG S, LIU X L, et al. Multi-objective evolutionary optimization for geostationary orbit satellite mission planning. Journal of Systems Engineering and Electronics, 2017, 28 (5): 934- 945. doi: 10.21629/JSEE.2017.05.11
2	LIU A J, PFUND M, FOWLER J. Scheduling optimization of task allocation in integrated manufacturing system based on task decomposition. Journal of Systems Engineering and Electronics, 2016, 27 (2): 422- 433. doi: 10.1109/JSEE.2016.00043
3	LI K L, WANG J. Multi-objective optimization for cloud task scheduling based on the ANP model. Chinese Journal of Electronics, 2017, 26 (5): 889- 898. doi: 10.1049/cje.2017.07.019
4	WANG Z K, ZHANG Q F, ZHOU A M, et al. Adaptive replacement strategies for MOEA/D. IEEE Trans. on Cybernetics, 2016, 46 (2): 474- 486. doi: 10.1109/TCYB.2015.2403849
5	DEB K, AGRAWAL S, PRATAP A, et al. A fast elitist nondominated sorting genetic algorithm for multi-objective optimisation:NSGA-Ⅱ. Proc. of the 6th International Conference on Parallel Problem Solving from Nature, 2000, 849- 858.
6	VILLALOBOS C A R, COELLO C A. A new multiobjective evolutionary algorithm based on a performance assessment indicator. Proc. of the 14th International Conference on Genetic and Evolutionary Computation, 2012, 505- 512.
7	ZHANG Q F, LI H. MOEA/D:a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2007, 11 (6): 712- 731. doi: 10.1109/TEVC.2007.892759
8	LI K, FIALHO A, KWONG S, et al. Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2014, 18 (2): 114- 130.
9	LIN Q Z, LIU Z W, YAN Q, et al. Adaptive composite operator selection and parameter control for multiobjective evolutionary algorithm. Information Sciences, 2016, 339, 332- 352. doi: 10.1016/j.ins.2015.12.022
10	VENSKE S M, GONÇALVES R A, DELGADO M R. ADEMO/D:multiobjective optimization by an adaptive differential evolution algorithm. Neurocomputin, 2014, 127 (2): 65- 77.
11	KAELBLING L P. Associative reinforcement learning:a generate and test algorithm. Machine Learning, 1994, 15 (3): 299- 319.
12	DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part Ⅰ:solving problems with box constraints. IEEE Trans. on Evolutionary Computation, 2014, 18 (4): 577- 601. doi: 10.1109/TEVC.2013.2281535
13	YUAN Y, XU H, WANG B, et al. A new dominance relation based evolutionary algorithm for many-objective optimization. IEEE Trans. on Evolutionary Computation, 2016, 20 (1): 16- 37.
14	LI K, DEB K, ZHANG Q, et al. An evolutionary manyobjective optimization algorithm based on dominance and decomposition. IEEE Trans. on Evolutionary Computation, 2015, 19 (5): 694- 716. doi: 10.1109/TEVC.2014.2373386
15	WU M Y, LI K, KWONG W, et al. Evolutionary manyobjective optimization based on adversarial decomposition. IEEE Trans. on Cybernetics, 2018, 1- 24.
16	DEB K, LOTHAR T, MARCO L, et al. Scalable multiobjective optimization test problems. Proc. of the IEEE Congress on Evolutionary Computation, 2002, 825- 830.
17	GÓMEZ R H, COELLO C A C. Improved metaheuristic based on the R2 indicator for many-objective optimization. Proc. of the IEEE Congress on Evolutionary Computation, 2015, 679- 686.
18	DEB K. Multi-objective optimization using evolutionary algorithms. New York: Wiley, 2001.
19	MIETTINEN K, MAKELA M M. On scalarizing functions in multiobjective optimization. OR Spectrum, 2002, 24 (2): 193- 213. doi: 10.1007/s00291-001-0092-9
20	GOLDBERG D E. Probability matching, the magnitude of reinforcement and classifier system bidding. Machine Learning, 1990, 5, 407- 425.
21	ZITZLER E, THEIELE L, LAUMANNS M, et al. Performance assessment of multiobjective optimizaers:an analysis and review. IEEE Trans. on Evolutionary Computation, 2003, 7 (2): 117- 132. doi: 10.1109/TEVC.2003.810758
22	DEB K, AGRAWAL R B. Simulated binary crossover for continuous search space. Complex Systems, 1995, 9, 115- 148.
23	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

$m$	$H$	NSGA-ⅢMOMBI-Ⅱ	MOEA/DMOEA/AD
3	91	92	91
5	210	212	210
10	275	276	275

Problem	$m$	MOMB-Ⅲ	MOEAD	NSGA-Ⅲ	MOEA/AD	MOEA/BD
DTLZ1	3	1.0739E-02	1.0726E-02	1.0725E-02	1.0725E-02	1.0725E-02
	5	5.2765E-02	5.2714E-02	5.2715E-02	5.2710E-02	5.2708E-02
	10	1.9255E-01	9.6003E-02	9.8537E-02	9.8363E-02	9.7704E-02
DTLZ2	3	2.8559E-02	2.8549E-02	2.8549E-02	2.8549E-02	2.8548E-02
	5	1.6518E-01	1.6514E-01	1.6513E-01	1.6514E-01	1.6512E-01
	10	3.7531E-01	3.7430E-01	3.7564E-01	3.7430E-01	3.7331E-01
DTLZ3	3	2.8591E-02	2.8553E-02	2.8551E-02	2.8554E-02	2.8550E-02
	5	1.6539E-01	1.6526E-01	1.6522E-01	1.6519E-01	1.6514E-01
	10	4.5276E-01	3.7603E-01	4.2979E-01	3.7427E-01	4.0133E-01
DTLZ4	3	2.8566E-02	2.8548E-02	2.8556E-02	2.8549E-02	2.8555E-02
	5	1.6546E-01	1.9545E-01	1.6515E-01	1.6514E-01	1.6512E-01
	10	3.9622E-01	5.4337E-01	3.7335E-01	3.7431E-01	3.7276E-01
DTLZ5	3	7.8736E-03	1.7711E-02	4.0544E-03	1.6214E-02	1.4944E-02
	5	2.4021E-01	3.4838E-01	1.2293E-01	1.1300E-01	2.2730E-02
	10	6.6814E-01	1.5604E-01	4.8070E-01	2.0572E-01	1.8394E-02

[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]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.