Mining probabilistic models learned by EDAs in the optimization of multi-objective problems

ABSTRACT

One of the uses of the probabilistic models learned by estimation of distribution algorithms is to reveal previous unknown information about the problem structure. In this paper we investigate the mapping between the problem structure and the dependencies captured in the probabilistic models learned by EDAs for a set of multi-objective satisfiability problems. We present and discuss the application of different data mining and visualization techniques for processing and visualizing relevant information from the structure of the learned probabilistic models. We show that also in the case of multi-objective optimization problems, some features of the original problem structure can be translated to the probabilistic models and unveiled by using algorithms that mine the model structures.

REFERENCES

• 1: L. A. N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley. Classes of small-world networks. Proceedings of the National Academy of Sciences (PNAS), 97(21):11149--11152, 2000.
• 2: E. Bengoetxea. Inexact Graph Matching Using Estimation of Distribution Algorithms. PhD thesis, Ecole Nationale Supérieure des Télécommunications, 2003.
• 3: P. A. Bosman. Design and Application of Iterated Density-Estimation Evolutionary Algorithms. PhD thesis, Universiteit Utrecht, Utrecht, The Netherlands, 2003.
• 4: C. Echegoyen, R. Santana, J. A. Lozano, and P. Larrañaga. The impact of probabilistic learning algorithms in EDAs based on Bayesian networks. In Linkage in Evolutionary Computation, Studies in Computational Intelligence, pages 109--139. Springer, 2008.
• 5: R. Etxeberria and P. Larrañaga. Global optimization using Bayesian networks. In A. Ochoa, M. R. Soto, and R. Santana, editors, Proceedings of the Second Symposium on Artificial Intelligence (CIMAF-99), pages 151--173, Havana, Cuba, 1999.
• 6: B. J. Frey and D. Dueck. Clustering by passing messages between data points. Science, 315:972--976, 2007.
• 7: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 8: Mark Hauschild , Martin Pelikan , Claudio F. Lima , Kumara Sastry, Analyzing probabilistic models in hierarchical BOA on traps and spin glasses, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277070]
• 9: M. Hauschild, M. Pelikan, K. Sastry, and D. E. Goldberg. Using previous models to bias structural learning in the hierarchical BOA. MEDAL Report No. 2008003, Missouri Estimation of Distribution Algorithms Laboratory (MEDAL), 2008.
• 10: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 11: Alfred Inselberg, Parallel Coordinates, Springer-Verlag New York, Inc., Secaucus, NJ, 2009
• 12: S. C. Johnson. Hierarchical clustering schemes. Psychometrika, 2:241--254, 1967.
• 13: N. Khan, D. E. Goldberg, and M. Pelikan. Multi-objective Bayesian optimization algorithm. IlliGAL Report No. 2002009, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2002.
• 14: P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation. Kluwer Academic Publishers, Boston/Dordrecht/London, 2002.
• 15: Marco Laumanns , Jiri Ocenasek, Bayesian Optimization Algorithms for Multi-objective Optimization, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.298-307, September 07-11, 2002
• 16: Claudio F. Lima , Fernando G. Lobo , Martin Pelikan, From mating pool distributions to model overfitting, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389174]
• 17: C. F. Lima, M. Pelikan, D. E. Goldberg, F. G. Lobo, K. Sastry, and M. Hauschild. Influence of selection and replacement strategies on linkage learning in BOA. In Proceedings of the 2007 Congress on Evolutionary Computation CEC-2007, pages 1083--1090. IEEE Press, 2007.
• 18: Heinz Mühlenbein , Robin Höns, The Estimation of Distributions and the Minimum Relative Entropy Principle, Evolutionary Computation, v.13 n.1, p.1-27, January 2005 [doi>10.1162/1063656053583469]
• 19: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 20: K. Murphy. The BayesNet toolbox for Matlab. Computer science and Statistics: Proceedings of Interface, 33, 2001.
• 21: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]
• 22: M. Pelikan, K. Sastry, and D. E. Goldberg. Multiobjective hBOA, clustering and scalability. IlliGAL Report No. 2005005, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, February 2005.
• 23: R. Santana, C. Echegoyen, A. Mendiburu, C. Bielza, J. A. Lozano, P. Larrañaga, R. Armañanzas, and S. Shakya. MATEDA: A suite of EDA programs in Matlab. Technical Report EHU-KZAA-I2/09, Department of Computer Science and Artificial Intelligence, University of the Basque Country, February 2009.
• 24: R. Santana, P. Larrañaga, and J. A. Lozano. The role of a priori information in the minimization of contact potentials by means of estimation of distribution algorithms. In Proceedings of the Fifth European Conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, volume 4447 of Lecture Notes in Computer Science, pages 247--257. Springer Verlag, 2007.
• 25: James J. Thomas , Kristin A. Cook, A Visual Analytics Agenda, IEEE Computer Graphics and Applications, v.26 n.1, p.10-13, January 2006 [doi>10.1109/MCG.2006.5]
• 26: Matthew O. Ward, A taxonomy of glyph placement strategies for multidimensional data visualization, Information Visualization, v.1 n.3/4, p.194-210, December 2002 [doi>10.1057/palgrave.ivs.9500025]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Performance

Keywords:
estimation of distribution algorithms, probabilistic modeling, problem structure, visualization