research-article

An improved version of a reference-based multi-objective evolutionary algorithm based on IGD⁺

Authors:

Edgar Manoatl Lopez,

Carlos A. Coello CoelloAuthors Info & Claims

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

Pages 713 - 720

https://doi.org/10.1145/3205455.3205530

Published: 02 July 2018 Publication History

Abstract

In recent years, the design of new selection mechanisms has become a popular trend in the development of Multi-Objective Evolutionary Algorithms (MOEAs). This trend has been motivated by the aim of maintaining a good balance between convergence and diversity of the solutions. Reference-based selection is, with no doubt, one of the most promising schemes in this area. However, reference-based MOEAs are known to have difficulties for solving multi-objective problems with complicated Pareto fronts, mainly because they rely on the consistency between the Pareto front shape and the distribution of the reference weight vectors. In this paper, we propose a reference-based MOEA, which uses the Inverted Generational Distance plus (IGD⁺) indicator. The proposed approach adopts a novel method for approximating the reference set, based on an hypercube-based method. Our results indicate that our proposed approach is able to obtain solutions of a similar quality to those obtained by RVEA, MOEA/DD, NSGA-III and MOMBI-II in several test problems traditionally adopted in the specialized literature, and is able to outperform them in problems with complicated Pareto fronts.

References

[1]

Nicola Beume, Boris Naujoks, and Michael Emmerich. 2007. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 181, 3 (16 September 2007), 1653--1669.

[2]

François Bourgeois and Jean-Claude Lassalle. 1971. An Extension of the Munkres Algorithm for the Assignment Problem to Rectangular Matrices. Commun. ACM 14, 12 (Dec. 1971), 802--804.

Digital Library

[3]

Dimo Brockhoff, Tobias Wagner, and Heike Trautmann. 2012. On the Properties of the R2 Indicator. In 2012 Genetic and Evolutionary Computation Conference (GECCO'2012). ACM Press, Philadelphia, USA, 465--472. ISBN: 978-1-4503-1177-9.

Digital Library

[4]

Ran Cheng, Yaochu Jin, Markus Olhofer, and Bernhard Sendhoff. 2016. A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization. IEEE Transactions on Evolutionary Computation 20, 5 (October 2016), 773--791.

[5]

Ran Cheng, Miqing Li, Ye Tian, Xingyi Zhang, Shengxiang Yang, Yaochu Jin, and Xin Yao. 2017. A benchmark test suite for evolutionary many-objective optimization. Complex & Intelligent Systems 3, 1 (01 Mar 2017), 67--81.

[6]

Carlos A. Coello Coello and Margarita Reyes Sierra. 2004. A Study of the Parallelization of a Coevolutionary Multi-Objective Evolutionary Algorithm. In Proceedings of the Third Mexican International Conference on Artificial Intelligence (MICAI'2004), Raúl Monroy, Gustavo Arroyo-Figueroa, Luis Enrique Sucar, and Humberto Sossa (Eds.). Springer Verlag. Lecture Notes in Artificial Intelligence Vol. 2972, 688--697.

[7]

Kalyanmoy Deb and Himanshu Jain. 2014. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE Transactions on Evolutionary Computation 18, 4 (August 2014), 577--601.

[8]

Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (April 2002), 182--197.

Digital Library

[9]

Kalyanmoy Deb, Lothar Thiele, Marco Laumanns, and Eckart Zitzler. 2005. Scalable Test Problems for Evolutionary Multiobjective Optimization. In Evolutionary Multiobjective Optimization. Theoretical Advances and Applications, Ajith Abraham, Lakhmi Jain, and Robert Goldberg (Eds.). Springer, USA, 105--145.

[10]

K. Gerstl, G. Rudolph, O. Schütze, and H. Trautmann. 2011. Finding Evenly Spaced Fronts for Multiobjective Control via Averaging Hausdorff-Measure. In The 2011 8th International Conference on Electrical Engineering, Computer Science and Automatic Control (CCE'2011). IEEE Press, Mérida, Yucatán, México, 975--980.

[11]

Raquel Hernández Gómez and Carlos A. Coello Coello. 2013. MOMBI: A New Metaheuristic for Many-Objective Optimization Based on the R2 Indicator. In 2013 IEEE Congress on Evolutionary Computation (CEC'2013). IEEE Press, Cancún, México, 2488--2495. ISBN 978-1-4799-0454-9.

[12]

Raquel Hernández Gómez and Carlos A. Coello Coello. 2015. Improved Metaheuristic Based on the R2 Indicator for Many-Objective Optimization. In 2015 Genetic and Evolutionary Computation Conference (GECCO 2015). ACM Press, Madrid, Spain, 679--686. ISBN 978-1-4503-3472-3.

Digital Library

[13]

Simon Huband, Phil Hingston, Luigi Barone, and Lyndon While. 2006. A Review of Multiobjective Test Problems and a Scalable Test Problem Toolkit. IEEE Transactions on Evolutionary Computation 10, 5 (October 2006), 477--506.

Digital Library

[14]

Hisao Ishibuchi, Hiroyuki Masuda, Yuki Tanigaki, and Yusuke Nojima. 2015. Modified Distance Calculation in Generational Distance and Inverted Generational Distance. In Evolutionary Multi-Criterion Optimization, 8th International Conference, EMO 2015, António Gaspar-Cunha, Carlos Henggeler Antunes, and Carlos Coello Coello (Eds.). Springer. Lecture Notes in Computer Science Vol. 9019, Guimarães, Portugal, 110--125.

[15]

Hisao Ishibuchi, Noritaka Tsukamoto, and Yusuke Nojima. 2008. Evolutionary many-objective optimization: A short review. In 2008 Congress on Evolutionary Computation (CEC'2008). IEEE Service Center, Hong Kong, 2424--2431.

[16]

H. W. Kuhn and Bryn Yaw. 1955. The Hungarian method for the assignment problem. Naval Res. Logist. Quart (1955), 83--97.

[17]

Ke Li, Kalyanmoy Deb, Qingfu Zhang, and Sam Kwong. 2015. An Evolutionary Many-Objective Optimization Algorithm Based on Dominance and Decomposition. IEEE Transactions on Evolutionary Computation 19, 5 (October 2015), 694--716.

Digital Library

[18]

Edgar Manoatl Lopez and Carlos A. Coello Coello. 2016. IGD+-EMOA: A Multi-Objective Evolutionary Algorithm based on IGD+. In 2016 IEEE Congress on Evolutionary Computation (CEC'2016). IEEE Press, Vancouver, Canada, 999--1006. ISBN 978-1-5090-0623-9.

[19]

Edgar Manoatl Lopez and Carlos A. Coello Coello. 2017. Improving the Integration of the IGD+ Indicator into the Selection Mechanism of a Multi-objective Evolutionary Algorithm. In 2017 IEEE Congress on Evolutionary Computation (CEC'2017). IEEE Press, San Sebastián, Spain, 2683--2690. ISBN 978-1-5090-4601-0.

[20]

Adriana Menchaca-Mendez, Carlos Hernández, and Carlos A. Coello Coello. 2016. Δp-MOEA: A New Multi-Objective Evolutionary Algorithm Based on the Δp Indicator. In 2016 IEEE Congress on Evolutionary Computation (CEC'2016). IEEE Press, Vancouver, Canada, 3753--3760. ISBN 978-1-5090-0623-9.

[21]

Cynthia A. Rodríguez Villalobos and Carlos A. Coello Coello. 2012. A New Multi-Objective Evolutionary Algorithm Based on a Performance Assessment Indicator. In 2012 Genetic and Evolutionary Computation Conference (GECCO'2012). ACM Press, Philadelphia, USA, 505--512. ISBN: 978-1-4503-1177-9.

Digital Library

[22]

Oliver Schütze, Xavier Esquivel, Adriana Lara, and Carlos A. Coello Coello. 2012. Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multiobjective Optimization. IEEE Transactions on Evolutionary Computation 16, 4 (August 2012), 504--522.

Digital Library

[23]

Heike Trautmann, Günter Rudolph, Christian Dominguez-Medina, and Oliver Schütze. 2012. Finding Evenly Spaced Pareto Fronts for Three-Objective Optimization Problems. In EVOLVE - A Bridge between Probability Set Oriented Numerics, and Evolutionary Computation II, Oliver Schütze, Carlos A. Coello Coello, Alexandru-Adrian Tantar, Emilia Tantar, Pascal Bouvry, Pierre Del Moral, and Pierrick Legrand (Eds.). Springer, Advances in Intelligent Systems and Computing Vol. 175, Berlin, Germany, 89--105. ISBN 978-3-642-31519-0.

[24]

David A. Van Veldhuizen. 1999. Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations. Ph.D. Dissertation. Department of Electrical and Computer Engineering. Graduate School of Engineering. Air Force Institute of Technology, Wright-Patterson AFB, Ohio, USA.

Digital Library

[25]

Saúl Zapotecas Martínez, Víctor A. Sosa Hernández, Hernán Aguirre, Kiyoshi Tanaka, and Carlos A. Coello Coello. 2014. Using a Family of Curves to Approximate the Pareto Front of a Multi-Objective Optimization Problem. In Parallel Problem Solving from Nature - PPSN XIII, 13th International Conference, Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič, and Jim Smith (Eds.). Springer. Lecture Notes in Computer Science Vol. 8672, Ljubljana, Slovenia, 682--691.

[26]

Qingfu Zhang and Hui Li. 2007. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation 11, 6 (December 2007), 712--731.

Digital Library

[27]

Eckart Zitzler and Simon Künzli. 2004. Indicator-based Selection in Multiobjective Search. In Parallel Problem Solving from Nature - PPSN VIII, Xin Yao et al. (Ed.). Springer-Verlag. Lecture Notes in Computer Science Vol. 3242, Birmingham, UK, 832--842.

Cited By

Liang MWang LWang LZhong Y(2024)A hypervolume-based cuckoo search algorithm with enhanced diversity and adaptive scaling factorApplied Soft Computing10.1016/j.asoc.2023.111073151(111073)Online publication date: Jan-2024
https://doi.org/10.1016/j.asoc.2023.111073
Kouka NBenSaid FFdhila RFourati RHussain AAlimi A(2023)A novel approach of many-objective particle swarm optimization with cooperative agents based on an inverted generational distance indicatorInformation Sciences: an International Journal10.1016/j.ins.2022.12.021623:C(220-241)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.ins.2022.12.021
Coello Coello C(2023)Recent Research Topics in Evolutionary Multiobjective Optimization: A Personal PerspectiveComputational Intelligence10.1007/978-3-031-46221-4_5(90-120)Online publication date: 3-Nov-2023
https://doi.org/10.1007/978-3-031-46221-4_5
Show More Cited By

Index Terms

An improved version of a reference-based multi-objective evolutionary algorithm based on IGD⁺
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Continuous space search

Recommendations

IGD<sup>+</sup>-EMOA: A multi-objective evolutionary algorithm based on IGD<sup>+</sup>
2016 IEEE Congress on Evolutionary Computation (CEC)
In recent years, the design of selection mechanisms based on performance indicators has become a very popular trend in the development of new Multi-Objective Evolutionary Algorithms (MOEAs). The main motivation has been the well-known limitations of ...
Reference point based multi-objective optimization using evolutionary algorithms
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Evolutionary multi-objective optimization (EMO) methodologies have been amply applied to find a representative set of Pareto-optimal solutions in the past decade and beyond. Although there are advantages of knowing the range of each objective for Pareto-...
Multi-objective optimization using teaching-learning-based optimization algorithm

Two major goals in multi-objective optimization are to obtain a set of nondominated solutions as closely as possible to the true Pareto front (PF) and maintain a well-distributed solution set along the Pareto front. In this paper, we propose a teaching-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

July 2018

1578 pages

ISBN:9781450356183

DOI:10.1145/3205455

Editor:
Hernan Aguirre
Shinshu University
,
General Chair:
Keiki Takadama
The University of Electro-Communications

Copyright © 2018 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 ACM 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: 02 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '18

Sponsor:

SIGEVO

GECCO '18: Genetic and Evolutionary Computation Conference

July 15 - 19, 2018

Kyoto, Japan

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
129
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liang MWang LWang LZhong Y(2024)A hypervolume-based cuckoo search algorithm with enhanced diversity and adaptive scaling factorApplied Soft Computing10.1016/j.asoc.2023.111073151(111073)Online publication date: Jan-2024
https://doi.org/10.1016/j.asoc.2023.111073
Kouka NBenSaid FFdhila RFourati RHussain AAlimi A(2023)A novel approach of many-objective particle swarm optimization with cooperative agents based on an inverted generational distance indicatorInformation Sciences: an International Journal10.1016/j.ins.2022.12.021623:C(220-241)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.ins.2022.12.021
Coello Coello C(2023)Recent Research Topics in Evolutionary Multiobjective Optimization: A Personal PerspectiveComputational Intelligence10.1007/978-3-031-46221-4_5(90-120)Online publication date: 3-Nov-2023
https://doi.org/10.1007/978-3-031-46221-4_5
Cortellessa VDi Pompeo DTucci M(2023)Performance of Genetic Algorithms in the Context of Software Model RefactoringComputer Performance Engineering and Stochastic Modelling10.1007/978-3-031-43185-2_16(234-248)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1007/978-3-031-43185-2_16
Fan QZhang YLi N(2022)An Autoselection Strategy of Multiobjective Evolutionary Algorithms Based on Performance Indicator and its ApplicationIEEE Transactions on Automation Science and Engineering10.1109/TASE.2021.308474119:3(2422-2436)Online publication date: Jul-2022
https://doi.org/10.1109/TASE.2021.3084741
Ishibuchi HImada RMasuyama NNojima Y(2019)Comparison of Hypervolume, IGD and IGD+ from the Viewpoint of Optimal Distributions of SolutionsEvolutionary Multi-Criterion Optimization10.1007/978-3-030-12598-1_27(332-345)Online publication date: 10-Mar-2019
https://dl.acm.org/doi/10.1007/978-3-030-12598-1_27

View Options

Get Access

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