×

zbMATH — the first resource for mathematics

A new resource allocation strategy based on the relationship between subproblems for MOEA/D. (English) Zbl 1453.90156
Summary: Multi-objective evolutionary algorithms based on decomposition (MOEA/D) decomposes a multi-objective optimization problem (MOP) into a set of simple scalar objective optimization sub-problems and solves them in a collaborative way. Since the sub-problems are different in optimization difficulty and computational resource demanding, it is critical to reasonably allocate computational resources among them, which can optimize the usage of resources and improve the performance of an algorithm. This paper proposes a new resource allocation strategy based on the relationship between sub-problems for MOEA/D. A probability vector is maintained based on the relationship between sub-problems, which is used to guide the selection of sub-problems for optimization. In the optimization process, we explored the role of priority optimization of boundary sub-problems and used it to assist in the update of probability vector in the early optimization phase. A steady-state algorithm is designed and tested experimentally. The results suggest that the designed algorithms have some advantages over existing state-of-the-art algorithms.
MSC:
90C29 Multi-objective and goal programming
68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
90C59 Approximation methods and heuristics in mathematical programming
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bader, J.; Zitzler, E., Hype: an algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 1, 45-76 (2011)
[2] Basseur, M.; Zitzler, E., A preliminary study on handling uncertainty in indicator-based multiobjective optimization, (Rothlauf, F.; Branke, J.; Cagnoni, S.; Costa, E.; Cotta, C.; Drechsler, R.; Lutton, E.; Machado, P.; Moore, J. H.; Romero, J.; Smith, G. D.; Squillero, G.; Takagi, H., Applications of Evolutionary Computing, EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC, Budapest, Hungary, April 10-12, 2006, Proceedings. Applications of Evolutionary Computing, EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC, Budapest, Hungary, April 10-12, 2006, Proceedings, Lecture Notes in Computer Science, 3907 (2006), Springer), 727-739
[3] Beume, N.; Naujoks, B.; Emmerich, M. T.M., SMS-EMOA: multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 3, 1653-1669 (2007) · Zbl 1123.90064
[4] Cai, X.; Mei, Z.; Fan, Z., A decomposition-based many-objective evolutionary algorithm with two types of adjustments for direction vectors, IEEE Trans. Cybern., 8, 2335-2348 (2018)
[5] Cheng, R.; Jin, Y.; Narukawa, K.; Sendhoff, B., A multiobjective evolutionary algorithm using gaussian process-based inverse modeling, IEEE Trans. Evol. Comput., 19, 6, 838-856 (2015)
[6] Chiang, T.; Lai, Y., MOEA/D-AMS: improving MOEA/D by an adaptive mating selection mechanism, Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2011, New Orleans, LA, USA, 5-8 June, 2011, 1473-1480 (2011), IEEE
[7] Coello, C. A.C.; Lamont, G. B.; Veldhuizen, D. A.V., Evolutionary Algorithms for Solving Multi-Objective Problems (2007), New York, NY, USA: Springer · Zbl 1142.90029
[8] Das, S.; Suganthan, P. N., Differential evolution: a survey of the state-of-the-art, IEEE Trans. Evol. Comput., 15, 1, 4-31 (2011)
[9] Datta, S.; Ghosh, A.; Sanyal, K.; Das, S., A radial boundary intersection aided interior point method for multi-objective optimization, Inf. Sci., 377, 1-16 (2017) · Zbl 1428.90175
[10] Deb, K.; Goyal, M., A combined genetic adaptive search (geneas) for engineering design, Comput. Sci. Informat, 26, 4, 30-45 (1996)
[11] 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. Evol. Comput., 18, 4, 577-601 (2014)
[12] 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)
[13] Giagkiozis, I.; Fleming, P. J., Methods for multi-objective optimization: an analysis, Inf. Sci., 293, 338-350 (2015) · Zbl 1355.90090
[14] Giagkiozis, I.; Purshouse, R. C.; Fleming, P. J., Generalized decomposition and cross entropy methods for many-objective optimization, Inf. Sci., 282, 363-387 (2014) · Zbl 1355.90091
[15] Gong, D.; Sun, J.; Miao, Z., A set-based genetic algorithm for interval many-objective optimization problems, IEEE Trans. Evol. Comput., 22, 1, 47-60 (2018)
[16] 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)
[17] Igel, C.; Hansen, N.; Roth, S., Covariance matrix adaptation for multi-objective optimization, Evol. Comput., 15, 1, 1-28 (2007)
[18] Ishibuchi, H.; Akedo, N.; Nojima, Y., Relation between neighborhood size and MOEA/D performance on many-objective problems, Evolutionary Multi-Criterion Optimization (EMO) (LNCS 7811)., 459-474 (2013), Springer: Springer Berlin, Germany
[19] Ishibuchi, H.; Murata, T., A multi-objective genetic local search algorithm and its application to flowshop scheduling, IEEE Trans. Syst. Man Cybern. Part C, 28, 3, 392-403 (1998)
[20] Ishibuchi, H.; Sakane, Y.; Tsukamoto, N.; Nojima, Y., Effects of using two neighborhood structures on the performance of cellular evolutionary algorithms for many-objective optimization, Proc. IEEE Congr. Evol. Comput. (CEC), 2508-2515 (2009)
[21] Jin, Y.; Okabe, T.; Sendhoff, B., Adapting weighted aggregation for multiobjective evolution strategies, (Zitzler, E.; Deb, K.; Thiele, L.; Coello, C. A.C.; Corne, D., Evolutionary Multi-Criterion Optimization, First International Conference, EMO 2001, Zurich, Switzerland, March 7-9, 2001, Proceedings. Evolutionary Multi-Criterion Optimization, First International Conference, EMO 2001, Zurich, Switzerland, March 7-9, 2001, Proceedings, Lecture Notes in Computer Science, 1993 (2001), Springer), 96-110
[22] 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)
[23] Li, K.; Kwong, S.; Zhang, Q.; Deb, K., Interrelationship-based selection for decomposition multiobjective optimization, IEEE Trans. Cybern., 45, 10, 2076-2088 (2015)
[24] Li, M.; Yang, S.; Liu, X., Shift-based density estimation for pareto-based algorithms in many-objective optimization, IEEE Trans. Evol. Comput., 18, 3, 348-365 (2014)
[25] Lin, Q.; Liu, Z.; Yan, Q.; Du, Z.; Coello, C. A.C.; Liang, Z.; Wang, W.; Chen, J., Adaptive composite operator selection and parameter control for multiobjective evolutionary algorithm, Inf. Sci., 339, 332-352 (2016)
[26] Martí, L.; García, J.; Berlanga, A.; Molina, J. M., A stopping criterion for multi-objective optimization evolutionary algorithms, Inf. Sci., 367-368, 700-718 (2016) · Zbl 1428.90184
[27] Miettinen, K., Nonlinear Multiobjective Optimization (1999), Boston, MA, USA: Kluwer · Zbl 0949.90082
[28] Mirjalili, S.; Jangir, P.; Mirjalili, S. Z.; Saremi, S.; Trivedi, I. N., Optimization of problems with multiple objectives using the multi-verse optimization algorithm, Knowl.-Based Syst., 134, 50-71 (2017)
[29] Murata, T.; Ishibuchi, H.; Gen, M., Specification of genetic search directions in cellular multi-objective genetic algorithms, Evolutionary Multi-Criterion Optimization, 82-95 (2001), Springer
[30] 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)
[31] Schutze, O.; Esquivel, X.; Lara, A.; Coello, C. A.C., Using the averaged Hausdorff distance as a performance measure in evolutionary multiobjective optimization, IEEE Trans. Evol. Comput., 16, 4, 504-522 (2012)
[32] Sun, Y.; Yen, G. G.; Yi, Z., Reference line-based estimation of distribution algorithm for many-objective optimization, Knowl.-Based Syst., 132, 129-143 (2017)
[33] Tian, Y.; Cheng, R.; Zhang, X.; Cheng, F.; Jin, Y., An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility, IEEE Trans. Evol. Comput., 22, 4, 609-622 (2018)
[34] Trivedi, A.; Srinivasan, D.; Sanyal, K.; Ghosh, A., A survey of multiobjective evolutionary algorithms based on decomposition, IEEE Trans. Evol. Comput., 21, 3, 440-462 (2017)
[35] Wang, L.; Zhang, Q.; Zhou, A.; Gong, M.; Jiao, L., Constrained subproblems in a decomposition-based multiobjective evolutionary algorithm, IEEE Trans. Evol. Comput., 20, 3, 475-480 (2016)
[36] Wang, P.; Liao, B.; Zhu, W.; Cai, L.; Ren, S.; Chen, M.; Li, Z.; Li, K., Adaptive region adjustment to improve the balance of convergenceand diversity in moea/d, Appl. Soft Comput., 70, 797-813 (2018)
[37] Wang, Z.; Zhang, Q.; Zhou, A.; Gong, M.; Jiao, L., Adaptive replacement strategies for MOEA/D, IEEE Trans. Cybern., 46, 2, 474-486 (2016)
[38] Wong, C. S.Y.; Al-Dujaili, A.; Suresh, S.; Sundararajan, N., Pareto-aware strategies for faster convergence in multi-objective multi-scale search optimization, Inf. Sci., 454-455, 1-15 (2018)
[39] Yen, G. G.; Lu, H., Dynamic multiobjective evolutionary algorithm: adaptive cell-based rank and density estimation, IEEE Trans. Evol. Comput., 7, 3, 253-274 (2003)
[40] Yuan, Y.; Ong, Y.-S.; Gupta, A.; Xu, H., Objective reduction in many-objective optimization: evolutionary multiobjective approaches and comprehensive analysis, IEEE Trans. Evol. Comput., 22, 2, 189-210 (2018)
[41] Zhang, Q.; Li, H., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (2007)
[42] Zhang, Q.; Liu, W.; Li, H., The performance of a new version of moea/d on cec09 unconstrained mop test instances, Proc. IEEE Congr. Evol. Comput. (CEC), 203-208 (2009)
[43] Zhang, Q.; Zhou, A.; Jin, Y., RM-MEDA: A regularity model-based multiobjective estimation of distribution algorithm, IEEE Trans. Evol. Comput., 12, 1, 41-63 (2008)
[44] Zhou, A.; Qu, B.; Li, H.; Zhao, S.; Suganthan, P. N.; Zhang, Q., Multiobjective evolutionary algorithms: a survey of the state of the art, Swarm Evol. Comput., 1, 1, 32-49 (2011)
[45] Zhou, A.; Zhang, Q., Are all the subproblems equally important? resource allocation in decomposition-based multiobjective evolutionary algorithms, IEEE Trans. Evol. Comput., 20, 1, 52-64 (2016)
[46] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA2: Improving the strength pareto evolutionary algorithm for multiobjective optimization, Proc. Evol. Methods Design Optim. Control Appl. Ind. Probl. (EUROGEN), 95-100 (2001)
[47] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach, IEEE Trans. Evol. Comput., 3, 4, 257-271 (1999)
[48] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; da Fonseca, V. G., Performance assessment of multiobjective optimizers: an analysis and review, IEEE Trans. Evol. Comput., 7, 2, 117-132 (2003)
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.