×

zbMATH — the first resource for mathematics

A scalarization-based dominance evolutionary algorithm for many-objective optimization. (English) Zbl 1441.90148
Summary: Classical Pareto-dominance based multi-objective evolutionary algorithms underperform when applied to optimization problems with more than three objectives. A class of multi-objective evolutionary algorithms introduced in the literature, utilizing pre-determined reference points acting as target vectors to maintain diversity in the objective space, has shown promising results. Inspired by this approach, we propose a scalarization-based dominance evolutionary algorithm (SDEA) that utilizes a reference point-based method and combine it with a novel sorting strategy that employs fitness values determined via scalarization. SDEA reduces computation complexity by eliminating the need for a Pareto-dominance approach to obtain non-dominated solutions. By means of a set of common benchmark optimization problems with 3- to 15-objectives, we compare the performance of SDEA with state-of-the-art many-objective evolutionary algorithms. The results indicate that SDEA outperforms existing algorithms in undertaking complex optimization problems with a high number of objectives, and has comparable outcomes over low-dimensional objective space benchmark problems.
MSC:
90C29 Multi-objective and goal programming
68W50 Evolutionary algorithms, genetic algorithms (computational aspects)
90C59 Approximation methods and heuristics in mathematical programming
Software:
DistAl; HypE; NBI; SMS-EMOA; SPEA2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aimin, Z.; Qingfu, Z.; Yaochu, J.; Sendhoff, B., Combination of EDA and DE for continuous biobjective optimization, (Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on (2008)), 1447-1454
[2] Auger, A.; Bader, J.; Brockhoff, D.; Zitzler, E., Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point, (Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms. Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, Orlando, Florida, USA (2009)) · Zbl 1369.68293
[3] Bader, J.; Zitzler, E., Hype: an algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 1, 45-76 (2011)
[4] Beume, N.; Naujoks, B.; Emmerich, M., SMS-EMOA: multiobjective selection based on dominated hypervolume, Eur. J. Oper. Res., 181, 3, 1653-1669 (2007) · Zbl 1123.90064
[5] Brockhoff, D.; Friedrich, T.; Neumann, F., Analyzing hypervolume indicator based algorithms, (Rudolph, G.; Jansen, T.; Beume, N.; Lucas, S.; Poloni, C.; Rudolph, G.; Jansen, T.; Beume, N.; Lucas, S.; Poloni, C., Parallel Problem Solving from Nature - PPSN X. Parallel Problem Solving from Nature - PPSN X, Lecture Notes in Computer Science, 5199 (2008), Springer Berlin Heidelberg), 651-660
[6] Cai, L.; Qu, S.; Yuan, Y.; Yao, X., A clustering-ranking method for many-objective optimization, Appl. Soft Comput., 35, Suppl C, 681-694 (2015)
[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] Corne, DavidW.; J., N. R.; Knowles, JoshuaD.; Oates, MartinJ.; Martin, J., PESA-II: region-based selection in evolutionary multiobjective optimization, (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’2001) (2001))
[9] Deb, K.; Agrawal, R. B., Simulated binary crossover for continuous search space, Complex Syst., 9, 2, 115-148 (1995) · Zbl 0843.68023
[10] Deb, K.; Goyal, M., A combined genetic adaptive search (GeneAS) for engineering design, Comput. Sci. Inform., 26, 4, 30-45 (1996)
[11] Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints, Evol. Comput., IEEE Trans., 18, 4, 577-601 (2014)
[12] Deb, K.; Mohan, M.; Mishra, S., Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions, Evol. Comput., 13, 4, 501-525 (2005)
[13] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, Evol. Comput., IEEE Trans., 6, 2, 182-197 (2002)
[14] Deb, K.; Thiele, L.; Laumanns, M.; Zitzler, E., Scalable test problems for evolutionary multiobjective optimization, (Abraham, A.; Jain, L.; Goldberg, R.; Abraham, A.; Jain, L.; Goldberg, R., Evolutionary Multiobjective Optimization. Evolutionary Multiobjective Optimization, Advanced Information and Knowledge Processing (2005), Springer London), 105-145 · Zbl 1078.90567
[15] Drechsler, N.; Drechsler, R.; Becker, B., Multi-objective optimisation based on relation favour, (Zitzler, E.; Thiele, L.; Deb, K.; Coello Coello, C.; Corne, D.; Zitzler, E.; Thiele, L.; Deb, K.; Coello Coello, C.; Corne, D., Evolutionary Multi-Criterion Optimization. Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 1993 (2001), Springer Berlin Heidelberg), 154-166
[16] Fleming, P.; Purshouse, R.; Lygoe, R., Many-objective optimization: an engineering design perspective, (Coello Coello, C.; Hernández Aguirre, A.; Zitzler, E.; Coello Coello, C.; Hernández Aguirre, A.; Zitzler, E., Evolutionary Multi-Criterion Optimization. Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 3410 (2005), Springer Berlin Heidelberg), 14-32 · Zbl 1109.68596
[17] Fogel, D. B., Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, 272 (1995), IEEE Press
[18] Hanoun, S.; Khan, B.; Johnstone, M.; Nahavandi, S.; Creighton, D., An effective heuristic for stockyard planning and machinery scheduling at a coal handling facility, (2013 11th IEEE International Conference on Industrial Informatics (INDIN) (2013)), 206-211
[19] Herrero, J. G.; Berlanga, A.; Lopez, J. M.M., Effective evolutionary algorithms for many-specifications attainment: application to air traffic control tracking filters, Evol. Comput., IEEE Trans., 13, 1, 151-168 (2009)
[20] Huband, S.; Barone, L.; While, L.; Hingston, P., A scalable multi-objective test problem toolkit, (Coello Coello, C. A.; Hernández Aguirre, A.; Zitzler, E., Evolutionary Multi-Criterion Optimization: Third International Conference, EMO 2005, Guanajuato, Mexico, March 9-11, 2005. Proceedings (2005), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 280-295 · Zbl 1109.68603
[21] Hui, L.; Qingfu, Z., Multiobjective optimization problems with complicated pareto sets, MOEA/D and NSGA-II, IEEE Trans. Evol. Comput., 13, 2, 284-302 (2009)
[22] Ikeda, K.; Kita, H.; Kobayashi, S., Failure of Pareto-based MOEAs: does non-dominated really mean near to optimal?, (Evolutionary Computation, 2001. Proceedings of the 2001 Congress on, 2 (2001)), 957-962
[23] Ishibuchi, H.; Hitotsuyanagi, Y.; Tsukamoto, N.; Nojima, Y., Many-objective test problems to visually examine the behavior of multiobjective evolution in a decision space, (Proceedings of the 11th International Conference on Parallel Problem Solving From Nature: Part II. Proceedings of the 11th International Conference on Parallel Problem Solving From Nature: Part II, Kraków, Poland (2010))
[24] Jara, E. C., Multi-objective optimization by using evolutionary algorithms: the \(p\)-optimality criteria, Evol. Comput., IEEE Trans., 18, 2, 167-179 (2014)
[25] Khan, B.; Bhatti, A.; Johnstone, M.; Hanoun, S.; Creighton, D.; Nahavandi, S., Optimal feature subset selection for neuron spike sorting using the genetic algorithm, (Arik, S.; Huang, T.; Lai, K. W.; Liu, Q., Neural Information Processing: 22nd International Conference, ICONIP 2015, Istanbul, Turkey, November 9-12, 2015, Proceedings, Part II (2015), Springer International Publishing: Springer International Publishing Cham), 364-370
[26] Khan, B.; Johnstone, M.; Hanoun, S.; Lim, C. P.; Creighton, D.; Nahavandi, S., Improved NSGA-III using neighborhood information and scalarization, (2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC) (2016)), 003033-003038
[27] Khan, B.; Hanoun, S.; Johnstone, M.; Lim, C. P.; Creighton, D.; Nahavandi, S., A new decomposition-based evolutionary framework for many-objective optimization, (2017 Annual IEEE International Systems Conference (SysCon) (2017)), 1-7
[28] Khan, B.; Hanoun, S.; Johnstone, M.; Lim, C. P.; Creighton, D.; Nahavandi, S., Multi-objective job shop scheduling using I-NSGA-III, (2018 Annual IEEE International Systems Conference (SysCon) (2018)), 1-5
[29] Kruisselbrink, J.; Emmerich, M. M.; Bäck, T.; Bender, A.; Ijzerman, A.; van der Horst, E., Combining aggregation with pareto optimization: a case study in evolutionary molecular design, (Ehrgott, M.; Fonseca, C.; Gandibleux, X.; Hao, J.-K.; Sevaux, M.; Ehrgott, M.; Fonseca, C.; Gandibleux, X.; Hao, J.-K.; Sevaux, M., Evolutionary Multi-Criterion Optimization. Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 5467 (2009), Springer Berlin Heidelberg), 453-467
[30] Li, M.; Yang, S.; Liu, X.; Shen, R., A Comparative Study on Evolutionary Algorithms for Many-Objective Optimization. A Comparative Study on Evolutionary Algorithms for Many-Objective Optimization, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7811, 261-275 (2013)
[31] Liangjun, K.; Qingfu, Z.; Battiti, R., MOEA/D-ACO: a multiobjective evolutionary algorithm using decomposition and antcolony, Cybern., IEEE Trans., 43, 6, 1845-1859 (2013)
[32] Lygoe, R.; Cary, M.; Fleming, P., A real-world application of a many-objective optimisation complexity reduction process, (Purshouse, R.; Fleming, P.; Fonseca, C.; Greco, S.; Shaw, J.; Purshouse, R.; Fleming, P.; Fonseca, C.; Greco, S.; Shaw, J., Evolutionary Multi-Criterion Optimization. Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 7811 (2013), Springer Berlin Heidelberg), 641-655
[33] Ma, X.; Liu, F.; Qi, Y.; Gong, M.; Yin, M.; Li, L.; Jiao, L.; Wu, J., MOEA/D with opposition-based learning for multiobjective optimization problem, Neurocomputing, 146, 48-64 (2014)
[34] Menchaca-Mendez, A.; Coello Coello, C., GD-MOEA: a new multi-objective evolutionary algorithm based on the generational distance indicator, (Gaspar-Cunha, A.; Henggeler Antunes, C.; Coello, C. C.; Gaspar-Cunha, A.; Henggeler Antunes, C.; Coello, C. C., Evolutionary Multi-Criterion Optimization. Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 9018 (2015), Springer International Publishing), 156-170
[35] Miqing, L.; Shengxiang, Y.; Xiaohui, L., Shift-based density estimation for pareto-based algorithms in many-objective optimization, Evol. Comput., IEEE Trans., 18, 3, 348-365 (2014)
[36] Purshouse, R. C.; Fleming, P. J., Evolutionary many-objective optimisation: an exploratory analysis, (Evolutionary Computation, 2003. CEC ’03. The 2003 Congress on, 3 (2003)), 2066-2073
[37] Purshouse, R. C.; Fleming, P. J., On the evolutionary optimization of many conflicting objectives, Evol. Comput., IEEE Trans., 11, 6, 770-784 (2007)
[38] Qingfu, Z.; Hui, L., MOEA/D: a multiobjective evolutionary algorithm based on decomposition, Evol. Comput., IEEE Trans., 11, 6, 712-731 (2007)
[39] Sülflow, A.; Drechsler, N.; Drechsler, R., Robust multi-objective optimization in high dimensional spaces, (Obayashi, S.; Deb, K.; Poloni, C.; Hiroyasu, T.; Murata, T.; Obayashi, S.; Deb, K.; Poloni, C.; Hiroyasu, T.; Murata, T., Evolutionary Multi-Criterion Optimization. Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 4403 (2007), Springer Berlin Heidelberg), 715-726
[40] Tan, Y.-y.; Jiao, Y.-c.; Li, H.; Wang, X.-k., MOEA/D + uniform design: a new version of MOEA/D for optimization problems with many objectives, Comput Oper. Res., 40, 6, 1648-1660 (2013) · Zbl 1348.90566
[41] Tey, J. Y.; Ramli, R., Comparison of computational efficiency of MOEA\D and NSGA-II for passive vehicle suspension optimization, Proceedings - 24th European Conference on Modelling and Simulation, ECMS 2010 (2010)
[42] von Lücken, C.; Barán, B.; Brizuela, C., A survey on multi-objective evolutionary algorithms for many-objective problems, Comput.Optimization Appl., 58, 3, 707-756 (2014) · Zbl 1334.90219
[43] While, L.; Bradstreet, L.; Barone, L., A fast way of calculating exact hypervolumes, Evol. Comput., IEEE Trans., 16, 1, 86-95 (2012)
[44] Wickramasinghe, U. K.; Carrese, R.; Xiaodong, L., Designing airfoils using a reference point based evolutionary many-objective particle swarm optimization algorithm, (Evolutionary Computation (CEC), 2010 IEEE Congress on (2010)), 1-8
[45] Yuan, Y.; Xu, H.; Wang, B.; Yao, X., A new dominance relation-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 20, 1, 16-37 (2016)
[46] Zhenan, H.; Yen, G. G., Diversity improvement in decomposition-based multi-objective evolutionary algorithm for many-objective optimization problems, (Systems, Man and Cybernetics (SMC), 2014 IEEE International Conference on (2014)), 2409-2414
[47] Zhou, A.; Zhang, Q.; Zhang, G., Approximation model guided selection for evolutionary multiobjective optimization, (Purshouse, R.; Fleming, P.; Fonseca, C.; Greco, S.; Shaw, J.; Purshouse, R.; Fleming, P.; Fonseca, C.; Greco, S.; Shaw, J., Evolutionary Multi-Criterion Optimization. Evolutionary Multi-Criterion Optimization, Lecture Notes in Computer Science, 7811 (2013), Springer Berlin Heidelberg), 398-412
[48] Zitzler, E.; Künzli, S.; Yao, X.; etal., Indicator-based selection in multiobjective search, Indicator-based selection in multiobjective search. Indicator-based selection in multiobjective search, Parallel Problem Solving from Nature - PPSN VIII,, 3242, 832-842 (2004)
[49] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA2: improving the strength pareto evolutionary algorithm for multiobjective optimization, (Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems, Athens, Greece (2001))
[50] Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; da Fonseca, V. G., Performance assessment of multiobjective optimizers: an analysis and review, Evol. Comput., IEEE Trans., 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.