Double adaptive selection strategy for MOEA/D

doi:10.21629/JSEE.2019.01.13

Abstract

Abstract:

Since most parameter control methods are based on prior knowledge, it is difficult for them to solve various problems. In this paper, an adaptive selection method used for operators and parameters is proposed and named double adaptive selection (DAS) strategy. Firstly, some experiments about the operator search ability are given and the performance of operators with different donate vectors is analyzed. Then, DAS is presented by inducing the upper confidence bound strategy, which chooses suitable combination of operators and donates sets to optimize solutions without prior knowledge. Finally, the DAS is used under the framework of the multi-objective evolutionary algorithm based on decomposition, and the multi-objective evolutionary algorithm based on DAS (MOEA/D-DAS) is compared to state-of-the-art MOEAs. Simulation results validate that the MOEA/D-DAS could select the suitable combination of operators and donate sets to optimize problems and the proposed algorithm has better convergence and distribution.

Key words: multi-objective optimization, adaptive operator selection, adaptive neighbor selection, decomposition

Jiale GAO, Qinghua XING, Chengli FAN, Zhibing LIANG. Double adaptive selection strategy for MOEA/D[J]. Journal of Systems Engineering and Electronics, 2019, 30(1): 132-143.

Figures/Tables 11

Fig 1

Fig 2

Table 1

Table 2

Table 3

Fig 3

Fig 4

Fig 5

Table 4

Table 5

Table 6

References 24

1	XU X L, CAO L L, WANG X H. Resource pre-allocation algorithms for low-energy task scheduling of cloud computing. Journal of Systems Engineering and Electronics, 2016, 27 (2): 457- 469. doi: 10.1109/JSEE.2016.00047
2	TAVANA M, LI Z, MOBIN M, et al. Multi-objective control chart design optimization using NSGA-III and MOPSO enhanced with DEA and TOPSIS. Expert Systems with Applications an International Journal, 2016, 50 (C): 17- 39.
3	DEB K, AGRAWAL R B. Simulated binary crossover for continuous search space. Complex Systems, 1994, 9 (3): 115- 148.
4	STORN R, PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11 (4): 341- 359. doi: 10.1023/A:1008202821328
5	LIN Q, CHEN J, ZHAN Z H, et al. A hybrid evolutionary immune algorithm for multiobjective optimization problems. IEEE Trans. on Evolutionary Computation, 2016, 20 (5): 711- 729.
6	QI Y, HOU Z, YIN M, et al. An immune multi-objective optimization algorithm with differential evolution inspired recombination. Applied Soft Computing, 2015, 29 (C): 395- 410.
7	ZHU Q, LIN Q, DU Z, et al. A novel adaptive hybrid crossover operator for multiobjective evolutionary algorithm. Information Sciences, 2016, 345 (C): 177- 198.
8	VENSKE S M, GONÇALVES R A, DELGADO M R. ADEMO/D:multiobjective optimization by an adaptive differential evolution algorithm. Neurocomputing, 2014, 127 (127): 65- 77.
9	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 (1): 114- 130.
10	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 (C): 332- 352.
11	WANG Z, ZHANG Q, ZHOU A, et al. Adaptive replacement strategies for MOEA/D. IEEE Trans. on Cybernetics, 2017, 46 (2): 474- 486.
12	ZHANG Q, LI H. MOEA/D:a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2007, 11 (6): 712- 731.
13	ZHANG Q F, LIU W, LI H. The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances. Proc. of the IEEE Congress on Evolutionary Computation, 2009: 203-208.
14	HILLERMEIER C. Nonlinear multiobjective optimization. Heidelberg: Birkhaüser Verlag, 2001.
15	SINDHYA K, RUUSKA S, HAANPÄÜ T, et al. A new hybrid mutation operator for multiobjective optimization with differential evolution. Soft Computing, 2011, 15 (10): 2041- 2055. doi: 10.1007/s00500-011-0704-5
16	ELSAYED S M, SARKER R A, ESSAM D L. GA with a new multi-parent crossover for constrained optimization. Proc. of the IEEE Evolutionary Computation, 2011: 857-864.
17	QIN A K, HUANG V L, SUGANTHAN P N. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans. on Evolutionary Computation, 2009, 13 (2): 398- 417.
18	LI H, ZHANG Q. Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II. IEEE Trans. on Evolutionary Computation, 2009, 13 (2): 284- 302.
19	DEB K, THIELE L, LAUMANNS M, et al. Scalable multiobjective optimization test problems. Proc. of the IEEE Congress on Evolutionary Computation, 2002: 825-830.
20	HUBAND S, BARONE L, WHILE L, et al. A scalable multiobjective test problem toolkit. Lecture Notes in Computer Science, 2005, 3410, 280- 295.
21	DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Trans. on Evolutionary Computation, 2002, 6 (2): 182- 197.
22	COELLO C A C, CORTÉS N C. Solving multiobjective optimization problems using an artificial immune system. Genetic Programming & Evolvable Machines, 2005, 6 (2): 163- 190.
23	MENCHACA-MENDEZ A, COELLO C A C. Selection mechanisms based on the maximin fitness function to solve multi-objective optimization problems. Information Sciences, 2016, 332 (C): 131- 152.
24	DEB K, BEYER H G. Self-adaptive genetic algorithms with simulated binary crossover. Evolutionary Computation, 2001, 9 (2): 197- 221.

Name	$n$	$m$	Range	Characteristics
F1	30	2	$x_{i}\in [0, 1]$, $1\le i\le n$	Convex, unimodal
F2	30	2	$x_{1}\in [0, 1]$, $x_{i}\in [0, 1]$, $1<i\le n$	Convex, multimodal
F3	30	2	$x_{1}\in [0, 1]$, $x_{i}\in [0, 1]$, $1<i\le n$	Convex, multimodal
F4	30	2	$x_{1}\in [0, 1]$, $x_{i}\in [0, 1]$, $1<i\le n$	Convex, multimodal
WFG1	12	3	$x_{i}\in [0, 2i]$, $1\le i\le n$	Convex, unimodal, mixed
WFG2	12	3	$x_{i}\in [0, 2i]$, $1\le i\le n$	Convex, multimodal, disconnected
WFG3	12	3	$x_{i}\in [0, 2i]$, $1\le i\le n$	Liner, unimodal, degenerate
WFG4	12	3	$x_{i}\in [0, 2i]$, $1\le i\le n$	Convex, multimodal
DTLZ1	10	3	$x_{i}\in [0, 1]$, $1\le i\le n$	Nonconvex, multimodal
DTLZ2	10	3	$x_{i}\in [0, 1]$, $1\le i\le n$	Nonconvex, unimodal

Problem		DAS3	DAS2	DAS1
F1	Mean	3.268E-02	1.990E-03	1.999E-03
	IQR	3.400E-03	2.420E-05	1.700E-05
	Rank	3	1	2
F2	Mean	3.737E-02	4.276E-03	4.430E-03
	IQR	3.520E-03	1.140E-03	1.280E-03
	Rank	3	1	2
F3	Mean	4.169E-02	3.295E-03	4.354E-03
	IQR	3.540E-03	4.560E-04	2.050E-03
	Rank	3	1	2
F4	Mean	4.672E-02	5.277E-03	3.145E-03
	IQR	9.310E-03	3.550E-03	7.630E-04
	Rank	3	2	1
WFG1	Mean	4.122E-01	3.059E-01	2.884E-01
	IQR	4.050E-02	5.610E-02	4.220E-02
	Rank	3	2$\approx $	1
WFG2	Mean	4.855E-01	4.540E-01	4.316E-01
	IQR	8.220E-03	4.000E-02	5.910E-02
	Rank	3	2$\approx $	1
WFG3	Mean	4.890E-02	4.619E-02	4.627E-02
	IQR	8.210E-04	1.890E-04	8.410E-03
	Rank	3	1	2
WFG4	Mean	2.614E-01	2.320E-01	2.304E-01
	IQR	8.400E-03	4.000E-03	2.210E-03
	Rank	3	2$\approx $	1
DTLZ1	Mean	1.465E-02	1.360E-02	1.370E-02
	IQR	1.010E-04	5.470E-05	3.610E-07
	Rank	3	1	2
DTLZ2	Mean	5.076E-02	4.900E-02	4.886E-02
	IQR	1.430E-04	1.780E-04	2.020E-04
	Rank	3	2$\approx $	1
Rank sum		30	15	15
$+/-/\approx $		0/10/0	5/1/4

Problem		DAS3	DAS2	DAS1
F1	Mean	1.103E-02	3.008E-03	2.934E-03
	IQR	1.850E-02	6.510E-05	2.800E-04
	Rank	3	2$\approx $	1
F2	Mean	4.143E-02	2.119E-02	2.145E-02
	IQR	1.080E-01	4.730E-02	2.290E-02
	Rank	3	1	2
F3	Mean	3.468E-03	3.255E-03	4.910E-03
	IQR	4.090E-03	2.360E-03	3.860E-03
	Rank	2	1	3
F4	Mean	5.601E-03	3.271E-03	2.749E-03
	IQR	4.590E-03	3.180E-03	4.580E-04
	Rank	3	2	1
WFG1	Mean	8.347E-02	1.135E-01	8.561E-02
	IQR	1.600E-02	2.130E-02	1.960E-02
	Rank	1	3	2
WFG2	Mean	7.098E-02	7.427E-02	7.920E-02
	IQR	4.050E-02	2.000E-02	2.930E-03
	Rank	1	2	3
WFG3	Mean	1.910E-01	1.908E-01	1.840E-01
	IQR	3.930E-03	3.430E-03	3.900E-04
	Rank	3	2$\approx $	1
WFG4	Mean	1.870E-01	1.889E-01	1.703E-01
	IQR	9.660E-03	1.020E-02	3.650E-03
	Rank	2	3	1
DTLZ1	Mean	7.696E-02	7.810E-02	7.871E-05
	IQR	1.070E-05	5.660E-05	1.010E-05
	Rank	1	2	3
DTLZ2	Mean	3.699E-02	3.808E-02	3.796E-02
	IQR	1.210E-03	7.870E-04	9.510E-06
	Rank	1	3$\approx $	2
Rank sum		20	21	19
$+/-/\approx $		4/6/0	2/5/3

Problem		NSGAII	MOEAD	MOEAD-DRA	MOEAD-AGR	MOEAD-DAS
F1	Mean	2.014E-03	4.173E-03	1.996E-03	3.425E-03	1.999E-03
	IQR	1.160E-05	8.710E-04	6.790E-06	1.010E-04	1.700E-05
	Rank	3	5	1	4	2
F2	Mean	1.794E-02	1.695E-01	4.848E-03	2.593E-02	4.430E-03
	IQR	3.360E-03	7.210E-02	3.570E-04	6.510E-03	1.280E-03
	Rank	3	5	2	4	1
F3	Mean	6.468E-03	4.851E-02	4.742E-03	1.143E-02	4.354E-03
	IQR	5.480E-04	2.600E-02	2.210E-04	4.030E-03	2.050E-03
	Rank	3	5	2	4	1
F4	Mean	8.164E-03	6.125E-02	6.740E-03	6.945E-03	3.145E-03
	IQR	9.820E-04	3.050E-02	1.180E-03	8.760E-04	7.630E-04
	Rank	4	5	2	3	1
WFG1	Mean	1.659E+00	2.356E-01	1.242E+00	1.800E-01	2.884E-01
	IQR	5.330E-02	5.900E-03	9.650E-02	1.280E-02	4.220E-02
	Rank	5	2	4	1	3
WFG2	Mean	4.400E-01	6.749E-01	4.391E-01	1.307E-01	4.316E-01
	IQR	1.500E-02	1.720E-01	4.080E-02	4.570E-03	5.910E-02
	Rank	4	5	3$\approx $	1	2
WFG3	Mean	5.775E-02	8.325E-02	5.531E-02	5.494E-02	4.627E-02
	IQR	1.450E-03	7.420E-04	3.990E-04	3.260E-04	8.410E-03
	Rank	4	5	3	2	1
WFG4	Mean	2.436E-01	1.784E-01	2.525E-01	1.884E-01	2.304E-01
	IQR	2.870E-03	3.440E-03	5.040E-03	3.090E-03	2.210E-03
	Rank	4	1	5	2	3
DTLZ1	Mean	1.984E-02	1.975E-02	1.979E-02	1.901E-02	1.370E-02
	IQR	2.540E-05	3.130E-05	3.000E-05	5.340E-04	3.610E-07
	Rank	5	3	4	2	1
DTLZ2	Mean	4.894E-02	3.638E-02	4.878E-02	4.772E-02	4.886E-02
	IQR	1.550E-04	3.490E-07	1.350E-04	7.550E-04	2.020E-04
	Rank	5$\approx $	1	3	2	4
Rank sum		40	37	29	25	19
$+/-/\approx $		0/9/1	2/8/0	1/8/1	2/8/0

Problem		NSGAII	MOEAD	ADEMO/D	MOEA/D-AGR	MOEA/D-DAS
F1	Mean	5.138E-03	5.240E-03	5.077E-03	3.712E-03	2.934E-03
	IQR	1.010E-04	6.710E-05	1.300E-04	2.390E-04	2.800E-04
	Rank	4	5	3	2	1
F2	Mean	8.175E-02	9.165E-03	1.411E-02	1.904E-02	2.145E-02
	IQR	7.140E-02	3.190E-03	8.670E-03	2.350E-02	2.290E-02
	Rank	5	1	2	3	4
F3	Mean	6.476E-02	6.509E-03	1.553E-02	6.150E-03	4.910E-03
	IQR	7.130E-02	7.270E-04	2.090E-02	4.340E-03	3.860E-03
	Rank	5	3	4	2	1
F4	Mean	2.158E-02	1.612E-02	1.023E-02	2.110E-02	2.749E-03
	IQR	2.560E-02	1.350E-02	4.770E-03	1.640E-02	4.580E-04
	Rank	5	4	3	2	1
WFG1	Mean	1.258E-01	1.751E-01	1.472E-01	1.110E-01	8.561E-02
	IQR	2.400E-02	1.190E-01	1.350E-01	9.730E-03	1.960E-02
	Rank	3	5	4	2	1
WFG2	Mean	1.301E-01	1.224E-01	1.117E-01	1.518E-01	7.920E-02
	IQR	6.360E-02	2.690E-02	9.160E-03	4.990E-02	2.930E-03
	Rank	4	3	2	5	1
WFG3	Mean	1.494E-01	1.551E-01	1.478E-01	8.373E-02	1.840E-01
	IQR	2.150E-03	3.320E-03	2.970E-03	3.900E-03	3.900E-04
	Rank	3	4	2	1	5
WFG4	Mean	2.444E-01	2.682E-01	2.632E-01	1.507E-01	1.703E-01
	IQR	1.070E-02	1.120E-02	6.560E-03	4.980E-03	3.650E-03
	Rank	3	5	4	1	2
DTLZ1	Mean	2.020E-02	2.027E-02	1.571E-02	1.562E-02	7.871E-05
	IQR	3.900E-04	3.160E-04	3.850E-04	5.360E-04	1.010E-05
	Rank	4	5	3	2	1
DTLZ2	Mean	5.773E-02	5.563E-02	5.674E-02	3.764E-02	3.796E-02
	IQR	4.520E-04	1.820E-03	7.820E-04	2.560E-03	9.510E-06
	Rank	5	3	4	1	2
Rang sum		41	38	31	21	19
$+/-/\approx $		0/10/0	1/9/0	0/10/0	3/7/0