×

zbMATH — the first resource for mathematics

MOEA/D with a self-adaptive weight vector adjustment strategy based on chain segmentation. (English) Zbl 1458.90572
Summary: MOEA/D (multi-objective evolutionary algorithm based on decomposition) decomposes a multi-objective optimization problem (MOP) into a series of single-objective sub-problems through a scalarizing function and a set of uniformly distributed weight vectors, and optimizes these sub-problems simultaneously in a collaborative way. However, when the shape of the true Pareto front (PF) of the multi-objective problem has the characteristic of long tail and sharp peak, the performance of MOEA/D will be greatly affected, that is, the performance of the decomposition-based multi-objective evolutionary algorithm depends heavily on the shape of the true PF. In order to efficiently deal with this situation, a self-adaptive weight vector adjustment strategy based on chain segmentation strategy (CS) is proposed. More specifically, a chain structure is firstly derived from the current population distribution to approximate the shape of the true PF. Then each chain is evenly segmented, and the direction vector from the origin to each segment point is used as the new weight vector. Finally, a set of reasonably distributed weight vectors are obtained to improve the performance of the algorithm. In the experimental section, we integrate CS strategy with three variants of MOEA/D, and the results demonstrate the effectiveness of the proposed strategy. Furthermore, we use MOEA/D-DE (a variant of MOEA/D, which is based on differential evolution operator) as a paradigm to integrate the CS strategy, and compare it with five state-of-the-art algorithms to illustrate that the algorithm integrating the CS strategy is very competitive.
MSC:
90C29 Multi-objective and goal programming
68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
90C59 Approximation methods and heuristics in mathematical programming
Software:
GDE3; jMetal; NBI; MOEA/D; PlatEMO; HypE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akhtar, T.; Shoemaker, C. A., Multi objective optimization of computationally expensive multi-modal functions with rbf surrogates and multi-rule selection, J. Global Optim., 64, 1, 17-32 (2016) · Zbl 1339.90293
[2] Asafuddoula, M.; Ray, T.; Sarker, R.; Alam, K., An adaptive constraint handling approach embedded MOEA/D, 2012 IEEE Congress on Evolutionary Computation, 1-8 (2012)
[3] U. Asan, S. Ercan, An Introduction to Self-Organizing Maps, Atlantis Press, Paris, pp. 295-315.
[4] Bader, J.; Zitzler, E., HypE: An algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 1, 45-76 (2011)
[5] Bosman, P. A.N.; Thierens, D., The balance between proximity and diversity in multiobjective evolutionary algorithms, IEEE Trans. Evol. Comput., 7, 2, 174-188 (2003)
[6] Cheng, R.; Jin, Y.; Olhofer, M.; Sendhoff, B., A reference vector guided evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 20, 5, 773-791 (2016)
[7] Das, I.; Dennis, J. E., Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems, SIAM J. Optim., 8, 3, 631-657 (1998) · Zbl 0911.90287
[8] 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. Evol. Comput., 18, 4, 577-601 (2014)
[9] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., 6, 2, 182-197 (2002)
[10] Durillo, J. J.; Nebro, A. J., jMetal: a Java framework for multi-objective optimization, Adv. Eng. Software, 42, 10, 760-771 (2011)
[11] Emmerich, M.; Beume, N.; Naujoks, B., An EMO algorithm using the hypervolume measure as selection criterion, Proceedings of the Third International Conference on Evolutionary Multi-Criterion Optimization. Proceedings of the Third International Conference on Evolutionary Multi-Criterion Optimization, EMO’05, 62-76 (2005), Springer-Verlag: Springer-Verlag Berlin, Heidelberg · Zbl 1109.68595
[12] de Farias, L. R.C.; Braga, P. H.M.; Bassani, H. F.; Araújo, A. F.R., MOEA/D with uniformly randomly adaptive weights, Proceedings of the Genetic and Evolutionary Computation Conference. Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’18, 641-648 (2018), ACM: ACM New York, NY, USA
[13] Gee, S. B.; Arokiasami, W. A.; Jiang, J.; Tan, K. C., Decomposition-based multi-objective evolutionary algorithm for vehicle routing problem with stochastic demands, Soft Comput., 20, 9, 3443-3453 (2016)
[14] Gong, M.; Ma, L.; Zhang, Q.; Jiao, L., Community detection in networks by using multiobjective evolutionary algorithm with decomposition, Physica A, 391, 15, 4050-4060 (2012)
[15] Gu, F.; Cheung, Y., Self-organizing map-based weight design for decomposition-based many-objective evolutionary algorithm, IEEE Trans. Evol. Comput., 22, 2, 211-225 (2018)
[16] Gu, F.; Liu, H. L.; Tan, K. C., A multiobjective evolutionary algorithm using dynamic weight design method, Int. J. Innovat. Comput.Inf. Control, 8, 5(B), 3677-3688 (2012)
[17] Han, D.; Du, W.; Du, W.; Jin, Y.; Wu, C., An adaptive decomposition-based evolutionary algorithm for many-objective optimization, Inf. Sci., 491, 204-222 (2019)
[18] Huband, S.; Hingston, P.; Barone, L.; While, L., A review of multiobjective test problems and a scalable test problem toolkit, IEEE Trans. Evol. Comput., 10, 5, 477-506 (2006)
[19] Ishibuchi, H.; Setoguchi, Y.; Masuda, H.; Nojima, Y., Performance of decomposition-based many-objective algorithms strongly depends on pareto front shapes, IEEE Trans. Evol. Comput., 21, 2, 169-190 (2017)
[20] Jain, H.; Deb, K., An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part II: handling constraints and extending to an adaptive approach, IEEE Trans. Evol. Comput., 18, 4, 602-622 (2014)
[21] Jan, M. A.; Zhang, Q., MOEA/D for constrained multiobjective optimization: Some preliminary experimental results, 2010 UK Workshop on Computational Intelligence (UKCI), 1-6 (2010)
[22] Jaszkiewicz, A., On the performance of multiple-objective genetic local search on the 0/1 knapsack problem - a comparative experiment, IEEE Trans. Evol. Comput., 6, 4, 402-412 (2002)
[23] Jiang, S.; Yang, S., An improved multiobjective optimization evolutionary algorithm based on decomposition for complex pareto fronts, IEEE Trans. Cybern., 46, 2, 421-437 (2016)
[24] Kukkonen, S.; Lampinen, J., GDE3: the third evolution step of generalized differential evolution, 2005 IEEE Congress on Evolutionary Computation, 1, 443-450 (2005)
[25] Kurpati, A.; Azarm, S.; Wu, J., Constraint handling improvements for multiobjective genetic algorithms, Struct. Multidiscip. Optim., 23, 3, 204-213 (2002)
[26] Li, H.; Zhang, Q., Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II, IEEE Trans. Evol. Comput., 13, 2, 284-302 (2009)
[27] Li, K.; Fialho, A.; Kwong, S.; Zhang, Q., Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 18, 1, 114-130 (2014)
[28] Li, K.; Zhang, Q.; Kwong, S.; Li, M.; Wang, R., Stable matching-based selection in evolutionary multiobjective optimization, IEEE Trans. Evol. Comput., 18, 6, 909-923 (2014)
[29] Liu, H.; Gu, F.; Zhang, Q., Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems, IEEE Trans. Evol. Comput., 18, 3, 450-455 (2014)
[30] Liu, Y.; Qin, H.; Zhang, Z.; Yao, L.; Wang, C.; Mo, L.; Ouyang, S.; Li, J., A region search evolutionary algorithm for many-objective optimization, Inf. Sci., 488, 19-40 (2019)
[31] Miettinen, K., Nonlinear multiobjective optimization (1999), Kluwer Academic Publishers, Boston · Zbl 0949.90082
[32] Pamulapati, T.; Mallipeddi, R.; Suganthan, P. N., \(I_{S D E^+}\) â;;an indicator for multi and many-objective optimization, IEEE Trans. Evol. Comput., 23, 2, 346-352 (2019)
[33] Pescador-Rojas, M.; Hernández Gómez, R.; Montero, E.; Rojas-Morales, N.; Riff, M.-C.; Coello Coello, C. A., An overview of weighted and unconstrained scalarizing functions, 9th International Conference on Evolutionary Multi-Criterion Optimization-Volume 10173, 499-513 (2017), Springer-Verlag New York, Inc.
[34] Qi, Y.; Ma, X.; Liu, F.; Jiao, L.; Sun, J.; Wu, J., MOEA/D with adaptive weight adjustment, Evol. Comput., 22, 2, 231-264 (2014)
[35] Rasmussen, C. E.; Williams, C. K.I., Gaussian Processes for Machine Learning (2006), The MIT Press · Zbl 1177.68165
[36] Saborido, R.; Ruiz, A. B.; Luque, M., Global WASF-GA: an evolutionary algorithm in multiobjective optimization to approximate the whole pareto optimal front, Evol. Comput., 25, 2, 309-349 (2017)
[37] Storn, R.; Price, K., Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim., 11, 4, 341-359 (1997) · Zbl 0888.90135
[38] Tang, L.; Wang, X.; Dong, Z., Adaptive multiobjective differential evolution with reference axis vicinity mechanism, IEEE Trans. Cybern., 49, 9, 3571-3585 (2019)
[39] Tian, Y.; Cheng, R.; Zhang, X.; Jin, Y., PlatEMO: a MATLAB platform for evolutionary multi-objective optimization, IEEE Comput. Intell. Mag., 12, 4, 73-87 (2017)
[40] Wang, J.; Weng, T.; Zhang, Q., A two-stage multiobjective evolutionary algorithm for multiobjective multidepot vehicle routing problem with time windows, IEEE Trans. Cybern., 49, 7, 2467-2478 (2019)
[41] Wang, R.; Zhang, Q.; Zhang, T., Decomposition-based algorithms using pareto adaptive scalarizing methods, IEEE Trans. Evol. Comput., 20, 6, 821-837 (2016)
[42] Wang, X.; Dong, Z.; Tang, L., Multiobjective differential evolution with personal archive and biased self-adaptive mutation selection, IEEE Trans. Syst. Man Cybern. Syst., 1-13 (2018)
[43] Wu, M.; Li, K.; Kwong, S.; Zhang, Q.; Zhang, J., Learning to decompose: A paradigm for decomposition-based multiobjective optimization, IEEE Trans. Evol. Comput., 23, 3, 376-390 (2019)
[44] Yao, S.; Dong, Z.; Wang, X.; Ren, L., A multiobjective multifactorial optimization algorithm based on decomposition and dynamic resource allocation strategy, Inf. Sci., 511, 18-35 (2020)
[45] Yaseen, Z. M.; Sulaiman, S. O.; Deo, R. C.; Chau, K.-W., An enhanced extreme learning machine model for river flow forecasting: State-of-the-art, practical applications in water resource engineering area and future research direction, J. Hydrol., 569, 387-408 (2019)
[46] Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (2007)
[47] Zhang, Q.; Liu, W.; Li, H., The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances, 2009 IEEE Congress on Evolutionary Computation, 203-208 (2009)
[48] Zhang, Q.; Liu, W.; Tsang, E.; Virginas, B., Expensive multiobjective optimization by MOEA/D with gaussian process model, IEEE Trans. Evol. Comput., 14, 3, 456-474 (2010)
[49] Zou, J.; Fu, L.; Yang, S.; Zheng, J.; Ruan, G.; Pei, T.; Wang, L., An adaptation reference-point-based multiobjective evolutionary algorithm, Inf. Sci., 488, 41-57 (2019)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.