DEUM: a framework for an estimation of distribution algorithm based on Markov random fields.

Shakya, Siddhartha K.

Abstract

Estimation of Distribution Algorithms (EDAs) belong to the class of population based optimisation algorithms. They are motivated by the idea of discovering and exploiting the interaction between variables in the solution. They estimate a probability distribution from population of solutions, and sample it to generate the next population. Many EDAs use probabilistic graphical modelling techniques for this purpose. In particular, directed graphical models (Bayesian networks) have been widely used in EDA. This thesis proposes an undirected graphical model (Markov Random Field (MRF)) approach to estimate and sample the distribution in EDAs. The interaction between variables in the solution is modelled as an undirected graph and the joint probability of a solution is factorised as a Gibbs distribution. The thesis describes a model of fitness function that approximates the energy in the Gibbs distribution, and shows how this model can be fitted to a population of solutions to estimate the parameters of the MRF. The estimated MRF is then sampled to generate the next population. This approach is applied to estimation of distribution in a general framework of an EDA, called Distribution Estimation using Markov Random Fields (DEUM). The thesis then proposes several variants of DEUM using different sampling techniques and tests their performance on a range of optimisation problems. The results show that, for most of the tested problems, the DEUM algorithms significantly outperform other EDAs, both in terms of number of fitness evaluations and the quality of the solutions found by them. There are two main explanations for the success of DEUM algorithms. Firstly, DEUM builds a model of fitness function to approximate the MRF. This contrasts with other EDAs, which build a model of selected solutions. This allows DEUM to use fitness in variation part of the evolution. Secondly, DEUM exploits the temperature coefficient in the Gibbs distribution to regulate the behaviour of the algorithm. In particular, with higher temperature, the distribution is closer to being uniform and with lower temperature it concentrates near some global optima. This gives DEUM an explicit control over the convergence of the algorithm, resulting in better optimisation.

Citation

SHAKYA, S.K. 2006. DEUM: a framework for an estimation of distribution algorithm based on Markov random fields. Robert Gordon University, PhD thesis.

• Thesis Type: Thesis
• Deposit Date: Nov 9, 2006
• Publicly Available Date: Nov 9, 2006
• Keywords: Estimation of distribution algorithm; Evolutionary; Computation; Genetic algorithm; EDA; Probabilistic; Graphical models; Markov Random Fields; Bayesian Networks; Optimisation; Algorithms; Heuristic based optimisation
• Public URL: http://hdl.handle.net/10059/39
• Contract Date: Nov 9, 2006
• Award Date: Apr 30, 2006