More Web Proxy on the site http://driver.im/

research-article

Effects of Dominance Modification on Hypervolume-based and IGD-based Performance Evaluation Results of NSGA-II

Authors:

Hisao Ishibuchi,

Ke ShangAuthors Info & Claims

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 679 - 687

https://doi.org/10.1145/3583131.3590437

Published: 12 July 2023 Publication History

Abstract

In the field of evolutionary multi-objective optimization, it is well known that dominance-based algorithms do not work well on many-objective problems. This is because almost all solutions in a population become non-dominated in early generations. Two approaches have been proposed to decrease the number of non-dominated solutions. One is to increase the dominated region by each solution: dominance modification. The other is to increase the correlation among objectives: objective modification. In this paper, first we show that these two approaches can be viewed as the same approach. We also explain that some regions of the Pareto front are dominated when the dominated region is increased. Next, we numerically examine the effects of dominance modification on the performance of NSGA-II on many-objective test problems. Through computational experiments, we demonstrate that its positive and negative effects are clearly shown by the hypervolume (HV) and inverted generational distance (IGD) indicators, respectively. Then, we discuss why these two indicators emphasize different effects of dominance modification using the optimal distribution of solutions for each indicator. Finally, we explain that objective space normalization is needed in dominance modification whereas it has no effects on the Pareto dominance relation.

References

[1]

J. Bader and E. Zitzler. 2011. HypE: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation 19, 1 (2011), 45--76.

Digital Library

[2]

N. Beume, B. Naujoks, and M. Emmerich. 2007. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 181, 3 (2007), 1653--1669.

[3]

J. Branke, T. Kaußler, and H. Schmeck. 2001.Guidance in evolutionary multiobjective optimization. Advances in Engineering Software 32, 6 (2001), 499--507.

[4]

D. Brockhoff. 2010. Optimal μ-distributions for the hypervolume indicator for problems with linear bi-objective fronts: Exact and exhaustive results. In Proceedings of the 8th International Conference on Simulated Evolution and Learning (SEAL 2010), Springer, Kanpur, India, 24--34.

Digital Library

[5]

C. A. C. Coello and M. R. Sierra. 2004. A study of the parallelization of a coevolutionary multi-objective evolutionary algorithm. In Proceeding of the Third Mexican International Conference on Artificial Intelligence (MICAI 2004), Springer, Mexico City, Mexico, 688--697.

[6]

K. Deb and H. Jain. 2014. An evolutionary many-objective optimization algorithm using reference-point-based non-dominated sorting approach, Part I: Solving problems with box constraints. IEEE Trans. on Evolutionary Computation 18, 4 (2014) 577--601.

[7]

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation 6, 2 (2002) 182--197.

Digital Library

[8]

K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. 2002. Scalable multi-objective optimization test problems. In Proceedings of 2002 Congress on Evolutionary Computation (CEC 2002), IEEE, Honolulu, USA, 825--830.

[9]

K. Deb, P. Zope, and A. Jain. (2003) Distributed computing of Pareto-optimal solutions with evolutionary algorithms. In Proceedings of the Second International Conference on Evolutionary Multi-Criterion Optimization (EMO 2003), Springer, Faro, Portugal, 534--549.

Digital Library

[10]

M. Emmerich, N. Beume, and B. Naujoks. 2005. An EMO algorithm using the hypervolume measure as selection criterion. In Proceedings of the Third International Conference on Evolutionary Multi-Criterion Optimization (EMO 2005), Springer, Guanajuato, Mexico, 62--76.

Digital Library

[11]

S. Huband, P. Hingston, L. Barone, and L. While. 2006. A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. on Evolutionary Computation 10, 5 (2006), 477--506.

Digital Library

[12]

K. Ikeda, H. Kita, and S. Kobayashi. 2001. Failure of Pareto-based MOEAs: Does non-dominated really mean near to optimal? In Proceedings of 2001 Congress on Evolutionary Computation (CEC 2001), IEEE, Seoul, Korea, 957--962.

[13]

H. Ishibuchi, N. Akedo, and Y. Nojima. 2015. Behavior of multi-objective evolutionary algorithms on many-objective knapsack problems. IEEE Trans. on Evolutionary Computation 19, 2 (2015), 264--283.

Digital Library

[14]

H. Ishibuchi, N. Akedo, H. Ohyanagi, and Y. Nojima. 2011. Behavior of EMO algorithms on many-objective optimization problems with correlated objectives. In Proceedings of 2011 IEEE Congress on Evolutionary Computation, (IEEE CEC 2011), IEEE, New Orleans, USA, 1465--1472.

[15]

H. Ishibuchi, R. Imada, N. Masuyama, and Y. Nojima. 2019. Comparison of hypervolume, IGD and IGD⁺ from the viewpoint of optimal distributions of solutions. In Proceeding of the 10th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2019), Springer, East Lansing, USA, 332--345.

Digital Library

[16]

H. Ishibuchi, R. Imada, Y. Setoguchi, and Y. Nojima. 2018. How to specify a reference point in hypervolume calculation for fair performance comparison. Evolutionary Computation 26, 3 (2018) 411--440.

Digital Library

[17]

H. Ishibuchi, R. Imada, Y. Setoguchi, and Y. Nojima. 2018. Reference point specification in inverted generational distance for triangular linear Pareto front. IEEE Trans. on Evolutionary Computation 22, 6 (2018) 961--975.

Digital Library

[18]

H. Ishibuchi, L. M. Pang, and K. Shang. 2022. Difficulties in fair performance comparison of multi-objective evolutionary algorithms. IEEE Computational Intelligence Magazine 17, 1 (2022) 86--101.

Digital Library

[19]

H. Ishibuchi, Y. Setoguchi, H. Masuda, and Y. Nojima. 2017. Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes. IEEE Trans. on Evolutionary Computation 21, 2 (2017) 169--190.

Digital Library

[20]

H. Ishibuchi, N. Tsukamoto, and Y. Nojima. 2008. Evolutionary many-objective optimization: A short review. Proceedings of 2008 IEEE Congress on Evolutionary Computation (CEC 2008), IEEE, Hong Kong, China, 2419--2426.

[21]

S. Mostaghim and H. Schmeck. 2008. Distance based ranking in many-objective particle swarm optimization. In Proceedings of the 10th International Conference on Parallel Problem Solving from Nature (PPSN X), Springer, Dortmund, Germany, 753--762.

[22]

L. M. Pang, H. Ishibuchi, and K. Shang. 2020. NSGA-II with simple modification works well on a wide variety of many-objective problems. IEEE Access 8 (2020), 190240--190250.

[23]

C. Ramirez-Atencia, S. Mostaghim, and D. Camacho. 2017. A knee point based evolutionary multi-objective optimization for mission planning problems. In Proceeding of 2017 Genetic Evolutionary Computation Conference (GECCO 2017), ACM, Berlin, Germany, 1216--1223.

[24]

H. Sato, H. E. Aguirre, and K. Tanaka. 2007. Controlling dominance area of solutions and its impact on the performance of MOEAs. In Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2007), Springer, Sendai, Japan, 5--20.

[25]

O. Schütze, A. Lara, and C. A. C. Coello. 2011. On the influence of the number of objectives on the hardness of a multiobjective optimization problem. IEEE Trans. on Evolutionary Computation 15, 4 (2011) 444--455.

Digital Library

[26]

Y. Tian, R. Cheng, X. Zhang, and Y. Jin. 2017. PlatEMO: A MATLAB platform for evolutionary multi-objective optimization. IEEE Computational Intelligence Magazine 12, 4 (2017), 73--87.

Digital Library

[27]

T. Wagner, N. Beume, and B. Naujoks. 2007. Pareto-, aggregation-, and indicator-based methods in many-objective optimization. In Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2007), Springer, Sendai, Japan. 742--756.

Digital Library

[28]

Q. Zhang and H. Li. 2007. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation 11, 6 (2007), 712--731.

Digital Library

[29]

E. Zitzler, D. Brockhoff, and L. Thiele. 2007. The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration. In Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2007), Springer, Sendai, Japan, 862--876.

Digital Library

[30]

E. Zitzler, M. Laumanns, and L. Thiele. 2001. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-Report 103, Computer Engineering and Networks Laboratory (TIK), Department of Electrical Engineering, ETH, Zurich.

[31]

E. Zitzler and L. Thiele. 1998. Multiobjective optimization using evolutionary algorithms - A comparative case study. In Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSN V), Springer, Amsterdam, Netherlands, 292--301.

Digital Library

Cited By

Kalita KJangir PPandya SShanmugasundar GAbualigah L(2024)Unveiling the Many-Objective Dragonfly Algorithm's (MaODA) efficacy in complex optimizationEvolutionary Intelligence10.1007/s12065-024-00942-717:5-6(3505-3533)Online publication date: 27-Apr-2024
https://doi.org/10.1007/s12065-024-00942-7
Zhang MWang JLiu YSong HHou JWang YWang M(2023)Multi-objective optimization algorithm based on clustering guided binary equilibrium optimizer and NSGA-III to solve high-dimensional feature selection problemInformation Sciences10.1016/j.ins.2023.119638648(119638)Online publication date: Nov-2023
https://doi.org/10.1016/j.ins.2023.119638

Index Terms

Effects of Dominance Modification on Hypervolume-based and IGD-based Performance Evaluation Results of NSGA-II
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

Effects of dominance resistant solutions on the performance of evolutionary multi-objective and many-objective algorithms
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Dominance resistant solutions (DRSs) in multi-objective problems have very good values for some objectives and very bad values for other objectives. Whereas DRSs are far away from the Pareto front, they are hardly dominated by other solutions due to ...
Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations
SMC'09: Proceedings of the 2009 IEEE international conference on Systems, Man and Cybernetics

Evolutionary multiobjective optimization (EMO) is an active research area in the field of evolutionary computation. EMO algorithms are designed to find a non-dominated solution set that approximates the entire Pareto front of a multiobjective ...
Single-objective and multi-objective formulations of solution selection for hypervolume maximization
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

A new trend in evolutionary multi-objective optimization (EMO) is the handling of a multi-objective problem as an optimization problem of an indicator function. A number of approaches have been proposed under the name of indicator-based evolutionary ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

July 2023

1667 pages

ISBN:9798400701191

DOI:10.1145/3583131

Chair:
Sara Silva,
Program Chair:
Luís Paquete

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China
Guangdong Provincial Key Laboratory
the Program for Guangdong Introducing Innovative and Enterpreneurial Teams
The Stable Support Plan Program of Shenzhen Natural Science Fund
Shenzhen Science and Technology Program

Conference

GECCO '23

Sponsor:

SIGEVO

GECCO '23: Genetic and Evolutionary Computation Conference

July 15 - 19, 2023

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
114
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kalita KJangir PPandya SShanmugasundar GAbualigah L(2024)Unveiling the Many-Objective Dragonfly Algorithm's (MaODA) efficacy in complex optimizationEvolutionary Intelligence10.1007/s12065-024-00942-717:5-6(3505-3533)Online publication date: 27-Apr-2024
https://doi.org/10.1007/s12065-024-00942-7
Zhang MWang JLiu YSong HHou JWang YWang M(2023)Multi-objective optimization algorithm based on clustering guided binary equilibrium optimizer and NSGA-III to solve high-dimensional feature selection problemInformation Sciences10.1016/j.ins.2023.119638648(119638)Online publication date: Nov-2023
https://doi.org/10.1016/j.ins.2023.119638

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents