research-article

Pattern identification in pareto-set approximations

Authors:

Dimo Brockhoff,

Eckart ZitzlerAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 737 - 744

https://doi.org/10.1145/1389095.1389236

Published: 12 July 2008 Publication History

Abstract

In a multiobjective setting, evolutionary algorithms can be used to generate a set of compromise solutions. This makes decision making easier for the user as he has alternative solutions at hand which he can directly compare. However, if the number of solutions and the number of decision variables which define the solutions are large, such an analysis may be difficult and corresponding tools are desirable to support a human in separating relevant from irrelevant information.

In this paper, we present a method to extract structural information from Pareto-set approximations which offers the possibility to present and visualize the trade-off surface in a compressed form. The main idea is to identify modules of decision variables that are strongly related to each other. Thereby, the set of decision variables can be reduced to a smaller number of significant modules. Furthermore, at the same time the solutions are grouped in a hierarchical manner according to their module similarity. Overall, the output is a dendrogram where the leaves are the solutions and the nodes are annotated with modules. As will be shown on knapsack problem instances and a network processor design application, this method can be highly useful to reveal hidden structures in compromise solution sets.

References

[1]

S. Bleuler, M. Laumanns, L. Thiele, and E. Zitzler. PISA-A Platform and Programming Language Independent Interface for Search Algorithms. In Conference on Evolutionary Multi-Criterion Optimization (EMO 2003), pages 494--508, Berlin, 2003. Springer.

Digital Library

[2]

D. Brockhoff, D. K. Saxena, K. Deb, and E. Zitzler. On Handling a Large Number of Objectives A Posteriori and During Optimization. In Multi-Objective Problem Solving from Nature: From Concepts to Applications, pages 377--403. Springer, 2007.

[3]

K. Deb and A. Srinivasan. Innovization: Innovating Design Principles through Optimization. In Genetic and Evolutionary Computation Conference (GECCO 2006), pages 1629--1636, 2006.

Digital Library

[4]

M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., 1990.

Digital Library

[5]

D. E. Goldberg, B. Korb, and K. Deb. Messy Genetic Algorithms: Motivation, Analysis, and First Results. Complex Systems, 3:493--530, 1989.

[6]

J. A. Hartigan. Direct Clustering of a Data Matrix. Journal of the American Statistical Association, 67(337):123--129, 1972.

[7]

C. Haubelt, S. Mostaghim, J. Teich, and A. Tyagi. Solving Hierarchical Optimization Problems Using MOEAs. In Conference on Evolutionary Multi-Criterion Optimization (EMO 2003), pages 162--176. Springer, 2003.

Digital Library

[8]

J. H. Holland. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, 1975.

Digital Library

[9]

E. J. Hughes. Radar Waveform Optimization as a Many-Objective Application Benchmark. In Conference on Evolutionary Multi-Criterion Optimization (EMO 2007), pages 700--714, 2007.

Digital Library

[10]

M. Krivánek and J. Morávek. NP-hard Problems in Hierarchical-Tree Clustering. Acta Informatica, 23(3):311--323, 1986.

Digital Library

[11]

S. C. Madeira and A. L. Oliveira. Biclustering Algorithms for Biological Data Analysis: A Survey. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 1(1):24--45, 2004.

Digital Library

[12]

S. Obayashi. Pareto Solutions of Multipoint Design of Supersonic Wings Using Evolutionary Algorithms. Adaptive Computing in Design and Manufacture V, 2002.

[13]

A. Prelić, S. Bleuler, P. Zimmermann, A. Wille, P. Bühlmann, W. Gruissem, L. Hennig, L. Thiele, and E. Zitzler. A Systematic Comparison and Evaluation of Biclustering Methods for Gene Expression Data. Bioinformatics, 22(9):1122--1129, 2006.

Digital Library

[14]

M. Preuss, B. Naujoks, and G. Rudolph. Pareto Set and EMOA Behavior for Simple Multimodal Multiobjective Functions. In Parallel Problem Solving From Nature (PPSN IX), pages 513--522. Springer, 2006.

Digital Library

[15]

K. Sastry, D. E. Goldberg, and X. Llorà. Towards Billion-Bit Optimization via a Parallel Estimation of Distribution Algorithm. In Genetic and Evolutionary Computation Conference (GECCO 2007), pages 577--584. ACM, 2007.

Digital Library

[16]

L. Thiele, S. Chakraborty, M. Gries, and S. Künzli. Design Space Exploration of Network Processor Architectures. In Network Processor Design 2002: Design Principles and Practices. Morgan Kaufmann, 2002.

[17]

D. A. Van Veldhuizen and G. B. Lamont. Multiobjective Optimization with Messy Genetic Algorithms. In ACM Symposium on Applied Computing, 2000.

Digital Library

[18]

E. Zitzler and S. Künzli. Indicator-Based Selection in Multiobjective Search. In Conference on Parallel Problem Solving from Nature (PPSN VIII), pages 832--842. Springer, 2004.

[19]

E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization. In Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), pages 95--100, 2002.

[20]

E. Zitzler and L. Thiele. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation, 3(4):257--271, 1999.

Digital Library

[21]

E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. Grunert da Fonseca. Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation, 7(2):117--132, 2003.

Digital Library

Cited By

Chen WIshibuchi HShang K(2021)Clustering-Based Subset Selection in Evolutionary Multiobjective Optimization2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC52423.2021.9658582(468-475)Online publication date: 17-Oct-2021
https://doi.org/10.1109/SMC52423.2021.9658582
Smedberg HBandaru SNg ADeb K(2020)Trend Mining 2.0: Automating the Discovery of Variable Trends in the Objective Space2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185892(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185892
Brockhoff DAuger AStützle T(2019)Tutorial on evolutionary multiobjective optimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323396(461-484)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323396
Show More Cited By

Index Terms

Pattern identification in pareto-set approximations
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Machine learning

Recommendations

Methodology to select solutions from the pareto-optimal set: a comparative study
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

The resolution of a Multi-Objective Optimization Problem (MOOP) does not end when the Pareto-optimal set is found. In real problems, a single solution must be selected. Ideally, this solution must belong to the non-dominated solutions set and must take ...
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-...
Pareto dominance-based MOEAs on problems with difficult pareto set topologies
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Despite the extensive application of multi-objective evolutionary algorithms (MOEAs) to solve multi-objective optimization problems (MOPs), understanding their working principles is still open to research. One of the most popular and successful MOEA ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
193
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen WIshibuchi HShang K(2021)Clustering-Based Subset Selection in Evolutionary Multiobjective Optimization2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC52423.2021.9658582(468-475)Online publication date: 17-Oct-2021
https://doi.org/10.1109/SMC52423.2021.9658582
Smedberg HBandaru SNg ADeb K(2020)Trend Mining 2.0: Automating the Discovery of Variable Trends in the Objective Space2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185892(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185892
Brockhoff DAuger AStützle T(2019)Tutorial on evolutionary multiobjective optimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323396(461-484)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323396
Brockhoff DTakadama K(2018)GECCO 2018 tutorial on evolutionary multiobjective optimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207864(349-372)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207864
Brockhoff D(2017)GECCO 2017 tutorial on evolutionary multiobjective optimizationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3067708(335-358)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3067708
Bandaru SNg ADeb K(2017)Data mining methods for knowledge discovery in multi-objective optimizationExpert Systems with Applications: An International Journal10.1016/j.eswa.2016.10.01570:C(139-159)Online publication date: 15-Mar-2017
https://dl.acm.org/doi/10.1016/j.eswa.2016.10.015
Brockhoff DWagner TNeumann FSutton A(2016)GECCO 2016 Tutorial on Evolutionary Multiobjective OptimizationProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2926974(201-227)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2926974
Brockhoff DWagner TEsparcia-Alcázar A(2015)Tutorial on Evolutionary Multiobjective OptimizationProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2756574(37-63)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2756574
Gaur ADeb K(2015)Towards an automated innovization method for handling discrete search spaces2015 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2015.7257249(2899-2906)Online publication date: May-2015
https://doi.org/10.1109/CEC.2015.7257249
Brockhoff DArnold D(2014)GECCO 2014 tutorial on evolutionary multiobjective optimizationProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2605339(297-322)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2605339
Show More Cited By

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