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

Citation

Brownlee A, McCall J & Brown DF (2007) Solving the MAXSAT problem using a multivariate EDA based on Markov networks. In: Proceedings of GECCO 2007: Genetic and Evolutionary Computation Conference, Companion Material. GECCO '07 Proceedings of the 9th annual conference companion on Genetic and evolutionary computation, London, 07.07.2007-11.07.2007. New York, NY: ACM, pp. 2423-2428. http://dl.acm.org/citation.cfm?id=1274005; https://doi.org/10.1145/1274000.1274005

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.