Pattern identification in pareto-set approximations

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.
• 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: Kalyanmoy Deb , Aravind Srinivasan, Innovization: innovating design principles through optimization, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144266]
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
• 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.
• 8: John H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, MIT Press, Cambridge, MA, 1992
• 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.
• 10: Mirko Křivánek , Jaroslav Morávek, NP-hard problems in hierarchical-tree clustering, Acta Informatica, v.23 n.3, p.311-323, June 1986 [doi>10.1007/BF00289116]
• 11: Sara C. Madeira , Arlindo L. Oliveira, Biclustering Algorithms for Biological Data Analysis: A Survey, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.24-45, January 2004 [doi>10.1109/TCBB.2004.2]
• 12: S. Obayashi. Pareto Solutions of Multipoint Design of Supersonic Wings Using Evolutionary Algorithms. Adaptive Computing in Design and Manufacture V, 2002.
• 13: Amela Prelić , Stefan Bleuler , Philip Zimmermann , Anja Wille , Peter Bühlmann , Wilhelm Gruissem , Lars Hennig , Lothar Thiele , Eckart Zitzler, A systematic comparison and evaluation of biclustering methods for gene expression data, Bioinformatics, v.22 n.9, p.1122-1129, May 2006 [doi>10.1093/bioinformatics/btl060]
• 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.
• 15: Kumara Sastry , David E. Goldberg , Xavier Llora, Towards billion-bit optimization via a parallel estimation of distribution algorithm, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277077]
• 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: David A. Van Veldhuizen , Gary B. Lamont, Multiobjective optimization with messy genetic algorithms, Proceedings of the 2000 ACM symposium on Applied computing, p.470-476, March 2000, Como, Italy [doi>10.1145/335603.335914]
• 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.
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
decision making, heuristics, multi-objective optimization, representations