DEUM – A Fully Multivariate EDA Based on Markov Networks

Citation

Shakya S, Brownlee A, McCall J, Fournier FA & Owusu G (2010) DEUM – A Fully Multivariate EDA Based on Markov Networks. In: Chen Y (ed.) Exploitation of Linkage Learning in Evolutionary Algorithms. Evolutionary Learning and Optimization, 3. Berlin Heidelberg: Springer, pp. 71-93. http://link.springer.com/chapter/10.1007/978-3-642-12834-9_4

Abstract
Recent years have seen an increasing interest in Markov networks as an alternative approach to probabilistic modelling in estimation of distribution algorithms (EDAs). Distribution Estimation Using Markov network (DEUM) is one of the early EDAs to use this approach. Over the years, several different versions of DEUM have been proposed using different Markov network structures, and are shown to work well in a number of different optimisation problems. One of the key similarities between all of the DEUM algorithms proposed so far is that they all assume the interaction between variables in the problem to be pre-given. In other words, they do not learn the structure of Markov network, and assume that it is known in advance. This work presents a recent development in DEUM framework - a fully multivariate DEUM algorithm that can automatically learn the undirected structure of the problem, automatically find the cliques from the structure and automatically estimate a joint probability model of the Markov network. This model is then sampled using Monte Carlo samplers. The chapter also reviews some of the key works on use of Markov networks in EDAs, and explains the fitness modelling concept used by DEUM. The proposed DEUM algorithm can be applied to any general optimisation problems even when the structure is not known.