Article

Are All Objectives Necessary? On Dimensionality Reduction in Evolutionary Multiobjective Optimization

Authors:

Dimo Brockhoff,

Eckart ZitzlerAuthors Info & Claims

Parallel Problem Solving from Nature - PPSN IX: 9th International Conference, Reykjavik, Iceland, September 9-13, 2006, Proceedings

Pages 533 - 542

https://doi.org/10.1007/11844297_54

Published: 09 September 2006 Publication History

Abstract

Most of the available multiobjective evolutionary algorithms (MOEA) for approximating the Pareto set have been designed for and tested on low dimensional problems (≤3 objectives). However, it is known that problems with a high number of objectives cause additional difficulties in terms of the quality of the Pareto set approximation and running time. Furthermore, the decision making process becomes the harder the more objectives are involved. In this context, the question arises whether all objectives are necessary to preserve the problem characteristics. One may also ask under which conditions such an objective reduction is feasible, and how a minimum set of objectives can be computed. In this paper, we propose a general mathematical framework, suited to answer these three questions, and corresponding algorithms, exact and heuristic ones. The heuristic variants are geared towards direct integration into the evolutionary search process. Moreover, extensive experiments for four well-known test problems show that substantial dimensionality reductions are possible on the basis of the proposed methodology.

References

[1]

Coello Coello C.A., Van Veldhuizen D.A., and Lamont G.B. Evolutionary Algorithms for Solving Multi-Objective Problems 2002 New York Kluwer Academic Publishers

[2]

Paechter B., Rankin R.C., Cumming A., and Fogarty T.C. Eiben A.E., Bäck T., Schoenauer M., and Schwefel H.-P. Timetabling the classes of an entire university with an evolutionary algorithm Parallel Problem Solving from Nature - PPSN V 1998 Heidelberg Springer 865-874

[3]

Coello Coello C.A. and Hernández Aguirre A. Design of Combinational Logic Circuits through an Evolutionary Multiobjective Optimization Approach Artificial Intelligence for Engineering, Design, Analysis and Manufacture 2002 16 1 39-53

[4]

Deb K., Thiele L., Laumanns M., and Zitzler E. Abraham A., Jain R., and Goldberg R. Scalable test problems for evolutionary multi-objective optimization Evolutionary Multiobjective Optimization: Theoretical Advances and Applications 2005 Heidelberg Springer 105-145

[5]

Emmerich M., Beume N., and Naujoks B. Coello Coello C.A., Hernández Aguirre A., and Zitzler E. An emo algorithm using the hypervolume measure as selection criterion Evolutionary Multi-Criterion Optimization 2005 Heidelberg Springer 62-76

[6]

Knowles J. and Corne D. Properties of an adaptive archiving algorithm for storing nondominated vectors IEEE Transactions on Evolutionary Computation 2003 7 2 100-116

[7]

While L. Coello Coello C.A., Hernández Aguirre A., and Zitzler E. A new analysis of the lebmeasure algorithm for calculating hypervolume Evolutionary Multi-Criterion Optimization 2005 Heidelberg Springer 326-340

[8]

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

[9]

Purshouse R.C. and Fleming P.J. Fonseca C.M., Fleming P.J., Zitzler E., Deb K., and Thiele L. Conflict, harmony, and independence: Relationships in evolutionary multi-criterion optimisation Evolutionary Multi-Criterion Optimization 2003 Heidelberg Springer 16-30

[10]

Tan K.C., Khor E.F., and Lee T.H. Multiobjective Evolutionary Algorithms and Applications 2005 London Springer

[11]

Deb, K., Saxena, D.K.: On finding pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. Kangal report no. 2005011, Kanpur Genetic Algorithms Laboratory (KanGAL) (2005)

[12]

Brockhoff, D., Zitzler, E.: On Objective Conflicts and Objective Reduction in Multiple Criteria Optimization. TIK Report 243, ETH Zurich, Zurich, Switzerland (2006); Operations Research 2006 (submitted)

[13]

Zitzler E., Thiele L., Laumanns M., Foneseca C.M., and Grunert da Fonseca V. Performance assessment of multiobjective optimizers: An analysis and review IEEE Transactions on Evolutionary Computation 2003 7 2 117-132

[14]

Brockhoff, D., Zitzler, E.: Dimensionality Reduction in Multiobjective Optimization with (Partial) Dominance Structure Preservation: Generalized Minimum Objective Subset Problems. TIK Report 247, ETH Zurich, Zurich, Switzerland (2006)

[15]

Zitzler E. and Künzli S. Yao X., Burke E.K., Lozano J.A., Smith J., Merelo-Guervós J.J., Bullinaria J.A., Rowe J.E., Tiňo P., Kabán A., and Schwefel H.-P. Indicator-based selection in multiobjective search Parallel Problem Solving from Nature - PPSN VIII 2004 Heidelberg Springer 832-842

[16]

Zitzler E. and Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach IEEE Transactions on Evolutionary Computation 1999 3 4 257-271

Cited By

Knowles JZheng WLi XHandl J(2024)Evolutionary Multiobjective Optimization (EMO)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648415(1432-1459)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648415
Bai YShi QGrimson MFlecker AGomes C(2023)Efficiently Approximating High-Dimensional Pareto Frontiers for Tree-Structured Networks Using Expansion and CompressionIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-031-33271-5_1(1-17)Online publication date: 29-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-33271-5_1
Gaspar-Cunha ACosta PMonaco FDelbem A(2023)Scalability of Multi-objective Evolutionary Algorithms for Solving Real-World Complex Optimization ProblemsEvolutionary Multi-Criterion Optimization10.1007/978-3-031-27250-9_7(86-100)Online publication date: 20-Mar-2023
https://dl.acm.org/doi/10.1007/978-3-031-27250-9_7
Show More Cited By

Index Terms

Are All Objectives Necessary? On Dimensionality Reduction in Evolutionary Multiobjective Optimization

Index terms have been assigned to the content through auto-classification.

Recommendations

Objective reduction in evolutionary multiobjective optimization: Theory and applications

Many-objective problems represent a major challenge in the field of evolutionary multiobjective optimization---in terms of search efficiency, computational cost, decision making, visualization, and so on. This leads to various research questions, in ...
Evolutionary multiobjective optimization
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation

Many optimization problems are multiobjective in nature in the sense that multiple, conflicting criteria need to be optimized simultaneously. Due to the conflict between objectives, usually, no single optimal solution exists. Instead, the optimum ...
GECCO 2016 Tutorial on Evolutionary Multiobjective Optimization
GECCO '16 Companion: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion

Many optimization problems are multiobjective in nature in the sense that multiple, conflicting criteria need to be optimized simultaneously. Due to the conflict between objectives, usually, no single optimal solution exists. Instead, the optimum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Parallel Problem Solving from Nature - PPSN IX: 9th International Conference, Reykjavik, Iceland, September 9-13, 2006, Proceedings

Sep 2006

1057 pages

ISBN:978-3-540-38990-3

DOI:10.1007/11844297

Editors:
Thomas Philip Runarsson
Science Institute, University of Iceland, P.O. Box, Iceland
,
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Hochschulstr. 1, A-6850, Dornbirn, Austria
,
Edmund Burke
Automated Scheduling, Optimisation and Planning Group, School of Computer Science & IT, University of Nottingham, NG8 1BB, Nottingham, UK
,
Juan J. Merelo-Guervós
Depto. Arquitectura y Tecnologa de Computadores, ETS Ingeiera Informtica, C/Daniel Saucedo Aranda, s/n, 18071, Granada, Spain
,
L. Darrell Whitley
Colorado State University, 80523, Fort Collins, CO, USA
,
Xin Yao
University of Birmingham, Birmingham, UK

© Springer-Verlag Berlin Heidelberg 2006.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 09 September 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Knowles JZheng WLi XHandl J(2024)Evolutionary Multiobjective Optimization (EMO)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3648415(1432-1459)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3648415
Bai YShi QGrimson MFlecker AGomes C(2023)Efficiently Approximating High-Dimensional Pareto Frontiers for Tree-Structured Networks Using Expansion and CompressionIntegration of Constraint Programming, Artificial Intelligence, and Operations Research10.1007/978-3-031-33271-5_1(1-17)Online publication date: 29-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-33271-5_1
Gaspar-Cunha ACosta PMonaco FDelbem A(2023)Scalability of Multi-objective Evolutionary Algorithms for Solving Real-World Complex Optimization ProblemsEvolutionary Multi-Criterion Optimization10.1007/978-3-031-27250-9_7(86-100)Online publication date: 20-Mar-2023
https://dl.acm.org/doi/10.1007/978-3-031-27250-9_7
Shavarani SLópez-Ibáñez MAllmendinger RKnowles J(2023)An Interactive Decision Tree-Based Evolutionary Multi-objective AlgorithmEvolutionary Multi-Criterion Optimization10.1007/978-3-031-27250-9_44(620-634)Online publication date: 20-Mar-2023
https://dl.acm.org/doi/10.1007/978-3-031-27250-9_44
Dai GZhou CWang MLi X(2018)Indicator and reference points co-guided evolutionary algorithm for many-objective optimization problemsKnowledge-Based Systems10.1016/j.knosys.2017.10.025140:C(50-63)Online publication date: 15-Jan-2018
https://dl.acm.org/doi/10.1016/j.knosys.2017.10.025
Luo NLi XLin Q(2018)Objective reduction for many-objective optimization problems using objective subspace extractionSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-017-2498-622:4(1159-1173)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s00500-017-2498-6
(2017)EFA-BMFMInformation Fusion10.1016/j.inffus.2017.03.00138:C(104-121)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1016/j.inffus.2017.03.001
Guo XWang YWang X(2016)An objective reduction algorithm using representative Pareto solution search for many-objective optimization problemsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1776-420:12(4881-4895)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s00500-015-1776-4
Li BLi JTang KYao X(2015)Many-Objective Evolutionary AlgorithmsACM Computing Surveys10.1145/279298448:1(1-35)Online publication date: 29-Sep-2015
https://dl.acm.org/doi/10.1145/2792984
Yousefi Zowj ABongard JSkalka CEsparcia-Alcázar A(2015)A Genetic Programming Approach to Cost-Sensitive Control in Resource Constrained Sensor SystemsProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754751(1295-1302)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754751
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents