
OpenAIR @ RGU >
Design and Technology >
Computing >
Theses (Computing) >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10059/39
Title:  DEUM: A Framework for an Estimation of
Distribution Algorithm based on Markov Random Fields 
Authors:  Shakya, Siddhartha 
Supervisors:  McCall, John Brown, Deryck 
Keywords:  Estimation of Distribution Algorithm Evolutionary Computation Genetic Algorithm EDA Probabilistic Graphical Models Markov Random Fields Bayesian Networks Optimisation Algorithms Heuristic Based Optimisation 
Issue Date:  Apr2006 
Publisher:  The Robert Gordon University 
Citation:  Shakya, S.K., McCall, J.A.W. & 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), IEEE press, Vancouver, Canada. Shakya, S.K., McCall, J.A.W. & Brown, D.F. (2005c). Incorporating a metropolis method in a distribution estimation using markov random field algorithm. In proceedings of IEEE Congress on Evolutionary Computation (IEEE CEC 2005), vol. 3, 2576–2583, IEEE press, Edinburgh, UK. Shakya, S., McCall, J. & Brown, D. (2005b). Using a Markov Network Model in a Univariate EDA: An Emperical CostBenefit Analysis. In proceedings of Genetic and Evolutionary Computation COnference (GECCO2005), 727–734, ACM, Washington, D.C., USA. Shakya, S., McCall, J. & Brown, D. (2005a). Estimating the distribution in an EDA. In B. Ribeiro, R.F. Albrechet, A. Dobnikar, D.W. Pearson & N.C. Steele, eds., In proceedings of the International Conference on Adaptive and Natural computiNG Algorithms (ICANNGA 2005), 202–205, SpringerVerlag, Wien, Coimbra, Portugal. Shakya, S.K., McCall, J.A.W. & Brown, D.F. (2004b). Updating the probability vector using MRF technique for a Univariate EDA. In E. Onaindia & S. Staab, eds., Proceedings of the Second Starting AI Researchers’ Symposium, volume 109 of Frontiers in artificial Intelligence and Applications, 15–25, IOS press, Valencia, Spain. Shakya, S.K., McCall, J.A.W. & Brown, D.F. (2004a). Preliminary results on Evolution without Selection. In Proceedings of Postgraduate Research Conference in Electronics, Photonics, Communications and Networks, and Computing Science (PREP 2004), Hertfordshire, UK. 
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. 
Appears in Collections:  Theses (Computing)

All items in OpenAIR are protected by copyright, with all rights reserved.
