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

research-article

Gap finding and validation in evolutionary multi- and many-objective optimization

Authors:

Pablo Valledor Pellicer,

Miguel Iglesias Escudero,

Silvino Fernández Alzueta,

Kalyanmoy DebAuthors Info & Claims

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

Pages 578 - 586

https://doi.org/10.1145/3377930.3389835

Published: 26 June 2020 Publication History

Abstract

Over 30 years, evolutionary multi- and many-objective optimization (EMO/EMaO) algorithms have been extensively applied to find well-distributed Pareto-optimal (PO) solutions in a single run. However, in real-world problems, the PO front may not always be a single continuous hyper-surface, rather several irregularities may exist involving disjointed surfaces, holes within the surface, or patches of mixed-dimensional surfaces. When a set of trade-off solutions are obtained by EMO/EMaO algorithms, there may exist less dense or no solutions (we refer as 'gaps') in certain parts of the front. This can happen for at least two reasons: (i) gaps naturally exist in the PO front, or (ii) no natural gaps exists, but the chosen EMO/EMaO algorithm is not able to find any solution in the apparent gaps. To make a confident judgement, we propose a three-step procedure here. First, we suggest a computational procedure to identify gaps, if any, in the EMO/EMaO-obtained PO front. Second, we propose a computational method to identify well-distributed gap-points in the gap regions. Third, we apply a focused EMO/EMaO algorithm to search for possible representative trade-off points in the gaps. We then propose two metrics to qualitatively establish whether a gap truly exists in the obtained dataset, and if yes, whether the gap naturally exists on the true Pareto-set. Procedures are supported by results on two to five-objective test problems and on a five-objective scheduling problem from a steel-making industry.

References

[1]

Hussein Abbass. 2004. An Inexpensive Cognitive Approach for Bi-objective Optimization Using Bliss Points and Interaction, Vol. 3242. 712--721.

[2]

J. Blank and K. Deb. 2019. pymoo - Multi-objective Optimization in Python. https://pymoo.org.

[3]

V. Chankong and Y. Y. Haimes. 1983. Multiobjective Decision Making Theory and Methodology. New York: North-Holland.

[4]

C. A. C. Coello, D. A. VanVeldhuizen, and G. Lamont. 2002. Evolutionary Algorithms for Solving Multi-Objective Problems. Boston, MA: Kluwer.

[5]

I. Das and J.E. Dennis. 1999. An improved technique for choosing parameters for Pareto surface generation using normal-boundary intersection. In Proceedings of the Third World Congress on Structutal and Multidisciplinary Optimization.

[6]

K. Deb. 2001. Multi-objective optimization using evolutionary algorithms. Wiley, Chichester, UK.

Digital Library

[7]

K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. 2002. A fast and Elitist multi-objective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182--197.

Digital Library

[8]

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 Transactions on Evolutionary Computation 18, 4 (2014), 577--601.

[9]

K. Deb, J. Sundar, N. Uday, and S. Chaudhuri. 2006. Reference Point Based Multi-Objective Optimization Using Evolutionary Algorithms. International Journal of Computational Intelligence Research (IJCIR) 2, 6 (2006), 273--286.

[10]

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

[11]

S. Fernandez, S. Alvarez, D. Díaz, M. Iglesias, and B. Ena. 2014. Scheduling a Galvanizing Line by Ant Colony Optimization. In Proceedings of the Swarm Intelligence: 9th International Conference, ANTS 2014, Brussels, Belgium. 146--157.

[12]

Leonard Kaufman and Peter J. Rousseeuw. 1987. Clustering by means of medoids., 405--416 pages.

[13]

J. D. Knowles and D. W. Corne. 2000. Approximating the non-dominated front using the Pareto archived evolution strategy. Evolutionary Computation Journal 8, 2 (2000), 149--172.

Digital Library

[14]

H. Li, Q. Zhang, and J. Deng. 2017. Biased multiobjective optimization and decomposition algorithm. IEEE transactions on cybernetics 47, 1 (2017), 52--66.

[15]

V. Boiteau M. Charrad, N. Ghazzali and A. Niknafs. 2014. NbClust: An R Package for Determining the Relevant Number of Clusters in a Data Set. Journal of Statistical Software 61 (2014). Issue 6.

[16]

Alessandro Maddaloni, Giacomo Filippo Porzio, Gianluca Nastasi, Valentina Colla, and Teresa Branca. 2015. Multi-objective optimization applied to retrofit analysis: A case study for the iron and steel industry. Applied Thermal Engineering 91 (12 2015), 638--646.

[17]

K. Miettinen. 1999. Nonlinear Multiobjective Optimization. Kluwer, Boston.

[18]

G. Pison, A. Struyf, and P.J. Rousseeuw. 1999. Displaying a Clustering with CLUSPLOT. Computational Statistics and Data Analysis 30 (1999), 381--392.

Digital Library

[19]

Peter Rousseeuw, Mia Hubert, and Anja Struyf. 1997. Clustering in an Object-Oriented Environment. Journal of Statistical Software 01 (02 1997).

[20]

O. Schutze, M. Laumanns, E. Tantar, C. A. C. Coello, and E.-G. Talbi. 2010. Computing Gap-free Pareto Front Approximations with Stochastic Search Algorithms. Evolutionary Computation 18, 1 (2010), 65--96.

Digital Library

[21]

Pablo Valledor, Alberto Gomez, Paolo Priore, and Javier Puente. 2018. Solving multi-objective rescheduling problems in dynamic permutation flow shop environments with disruptions. International Journal of Production Research 56, 19 (2018), 6363--6377.

[22]

Y. Vesikar, K. Deb, and J. Blank. 2018. Reference Point Based NSGA-III for Preferred Solutions. In IEEE Symposium Series on Computational Intelligence (SSCI-2018).

[23]

Jianping Yang, Bailin Wang, Caoyun Zou, Xiang Li, Tieke Li, and Qing Liu. 2018. Optimal Charge Planning Model of Steelmaking Based on Multi-Objective Evolutionary Algorithm. Metals 8 (06 2018), 483.

[24]

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

Digital Library

[25]

E. Zitzler, K. Deb, and L. Thiele. 2000. Comparison of multiobjective evolutionary algorithms: Empirical Results. Evolutionary Computation Journal 8, 2 (2000), 125--148.

Digital Library

[26]

E. Zitzler, M. Laumanns, and L. Thiele. 2001. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization. In Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, K. C. Giannakoglou et al. (Ed.). International Center for Numerical Methods in Engineering (CIMNE), 95--100.

Cited By

Suresh ADeb K(2024)Machine Learning-Based Prediction of New Pareto-Optimal Solutions From Pseudo-WeightsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.331949428:5(1351-1365)Online publication date: Oct-2024
https://doi.org/10.1109/TEVC.2023.3319494
Deb KLopes CMartins FWanner E(2024)Identifying Pareto Fronts Reliably Using a Multistage Reference-Vector-Based FrameworkIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324692228:1(252-266)Online publication date: Feb-2024
https://doi.org/10.1109/TEVC.2023.3246922
Tran Binh Minh Nguyen Long Thai Trung Kien (2023)An adaptive reference point technique to improve the quality of decomposition based multi-objective evolutionary algorithmJournal of Military Science and Technology10.54939/1859-1043.j.mst.CSCE7.2023.3-14(3-14)Online publication date: 30-Dec-2023
https://doi.org/10.54939/1859-1043.j.mst.CSCE7.2023.3-14
Show More Cited By

Index Terms

Gap finding and validation in evolutionary multi- and many-objective optimization

Recommendations

Approximate non-dominated sorting for evolutionary many-objective optimization

Non-dominated sorting has widely been adopted and shown to be very effective in dominance based evolutionary multi-objective optimization where the number of objectives is two or three. In dealing with many-objective optimization problems, where the ...
An improved NSGA-III procedure for evolutionary many-objective optimization
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

Many-objective (four or more objectives) optimization problems pose a great challenge to the classical Pareto-dominance based multi-objective evolutionary algorithms (MOEAs), such as NSGA-II and SPEA2. This is mainly due to the fact that the selection ...
A many-objective evolutionary algorithm based on rotated grid
Graphical abstract
A two-dimensional example for the rotating grid coordinates.

Display Omitted
Highlights
- An algorithm using rotary grid technology to partition the objective space was proposed to solve many-objective optimization problems.
Abstract
Evolutionary optimization algorithms, a meta-heuristic approach, often encounter considerable challenges in many-objective optimization problems (MaOPs). The Pareto-based dominance loses its effectiveness in MaOPs, which are defined as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference

June 2020

1349 pages

ISBN:9781450371285

DOI:10.1145/3377930

General Chair:
Carlos Artemio Coello Coello
CINVESTAV-IPN

Copyright © 2020 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: 26 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '20

Sponsor:

SIGEVO

GECCO '20: Genetic and Evolutionary Computation Conference

July 8 - 12, 2020

Cancún, Mexico

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
132
Total Downloads

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

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Suresh ADeb K(2024)Machine Learning-Based Prediction of New Pareto-Optimal Solutions From Pseudo-WeightsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.331949428:5(1351-1365)Online publication date: Oct-2024
https://doi.org/10.1109/TEVC.2023.3319494
Deb KLopes CMartins FWanner E(2024)Identifying Pareto Fronts Reliably Using a Multistage Reference-Vector-Based FrameworkIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.324692228:1(252-266)Online publication date: Feb-2024
https://doi.org/10.1109/TEVC.2023.3246922
Tran Binh Minh Nguyen Long Thai Trung Kien (2023)An adaptive reference point technique to improve the quality of decomposition based multi-objective evolutionary algorithmJournal of Military Science and Technology10.54939/1859-1043.j.mst.CSCE7.2023.3-14(3-14)Online publication date: 30-Dec-2023
https://doi.org/10.54939/1859-1043.j.mst.CSCE7.2023.3-14
Spieck JSixdenier PEsper KWildermann STeich JZhu Qvon Hanxleden RStephen EBrandt J(2023)Hybrid Genetic Reinforcement Learning for Generating Run-Time Requirement EnforcersProceedings of the 21st ACM-IEEE International Conference on Formal Methods and Models for System Design10.1145/3610579.3611091(23-35)Online publication date: 21-Sep-2023
https://dl.acm.org/doi/10.1145/3610579.3611091
Suresh ADeb K(2023)On the Choice of Unique Identifiers for Predicting Pareto-Optimal Solutions Using Machine Learning2023 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI52147.2023.10371981(1479-1484)Online publication date: 5-Dec-2023
https://doi.org/10.1109/SSCI52147.2023.10371981
Deb KGondkar AAnirudh S(2023)Learning to Predict Pareto-Optimal Solutions from Pseudo-weightsEvolutionary Multi-Criterion Optimization10.1007/978-3-031-27250-9_14(191-204)Online publication date: 9-Mar-2023
https://doi.org/10.1007/978-3-031-27250-9_14
Nuhu AYan XOpoku DHomaifar AKrawiec K(2021)A niching framework based on fitness proportionate sharing for multi-objective genetic algorithm (MOGA-FPS)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3459566(191-192)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3459566
Ergezer H(2021)Multi-Objective Trajectory Planning for Slung-Load Quadrotor SystemIEEE Access10.1109/ACCESS.2021.31292659(155003-155017)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3129265

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.

Figures

Tables

Media

View Table of Conten