Solving the MAXSAT problem using a multivariate EDA based on Markov networks

ABSTRACT

Markov Networks (also known as Markov Random Fields) have been proposed as a new approach to probabilistic modelling in Estimation of Distribution Algorithms (EDAs). An EDA employing this approach called Distribution Estimation Using Markov Networks (DEUM) has been proposed and shown to work well on a variety of problems, using a unique fitness modelling approach. Previously DEUM has only been demonstrated on univariate and bivariate complexity problems. Here we show that it can be extended to a difficult multivariate problem and is capable of accurately modelling a fitness function and locating an optimum with a very small number of function evaluations.

REFERENCES

• 1: Deryck F. Brown , A. Beatriz Garmendia-Doval , John A. W. McCall, Markov Random Field Modelling of Royal Road Genetic Algorithms, Selected Papers from the 5th European Conference on Artificial Evolution, p.65-76, October 29-31, 2001
• 2: HOOS, H. H. AND STÜTZLE, T. 2000. SATLIB: An Online Resource for Research on SAT. In SAT 2000, I. P. GENT, H. V. MAAREN AND T. WALSH, Eds. IOS Press, 283--292.
• 3: David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
• 4: KINDERMANN, R. AND SNELL, J. L. 1980. Markov Random Fields and their Applications. AMS Press, Providence, RI, USA.
• 5: KIRKPATRICK, S., GERLATT, C. D. AND VECCHI, M. P. 1983. Optimization by Simulated Annealing. Science 220, 671--680.
• 6: LARRAÑAGA, P. AND LOZANO, J. A. 2002. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, Boston.
• 7: LUCEY, T. 1984. Quantatitive Techniques: An Instructional Manual. D. P. Publications, Eastleigh, Hampshire, UK.
• 8: PELIKAN, M., GOLDBERG, D. E. AND LOBO, F. 1999. A Survey of Optimization by Building and Using Probabilistic Models. Technical Report IlliGAL Report 99018, University of Illinois at Urbana-Champaing.
• 9: PELIKAN, M. AND GOLDBERG, D. 2003. Hierarchical BOA solves Ising spin glasses and MAXSAT. In Proceedings of the Genetic and Evolutionary Computation Conference 2003 (GECCO-2003), 2003, Springer-Verlag, 1271--1282.
• 10: William H. Press , Brian P. Flannery , Saul A. Teukolsky , William T. Vetterling, Numerical recipes: the art of scientific computing, Cambridge University Press, New York, NY, 1986
• 11: SHAKYA, S., MCCALL, J. AND BROWN, D. 2004. Updating the Probability Vector using MRF Technique for a Univariate EDA. In Proceedings of STAIRS 2004, IOS Press, 15--25.
• 12: SHAKYA, S.K. 2006. DEUM: A framework for an Estimation of Distribution Algorithm based on Markov Random Fields. PhD Thesis, The Robert Gordon University, Aberdeen, UK.
• 13: SHAKYA, S. K., MCCALL, J. A. W. AND BROWN, D. F. 2006. Solving the Ising Spin Glass Problem using a bivariate EDA based on Markov Random Fields. In Proceedings of IEEE Congress on Evolutionary Computation (IEEE CEC 2006), Vancouver, Canada, 16-21 July 2006, IEEE Press.
• 14: ZHANG, Q., SUN, J. AND TSANG, E. 2005. An evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Trans. Evolutionary Computation, vol 9, issue 2. Pp 192--200.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Stochastic processes

General Terms:
Algorithms, Performance, Theory

Keywords:
estimation of distribution algorithms, evolutionary algorithms, probabilistic modelling