OpenAIR @ RGU >
Design and Technology >
Computing >
Theses (Computing) >

Please use this identifier to cite or link to this item:
This item has been viewed 41 times in the last year. View Statistics

Files in This Item:

File Description SizeFormat
thesis.pdf4.52 MBAdobe PDFView/Open
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
Probabilistic Graphical Models
Markov Random Fields
Bayesian Networks
Optimisation Algorithms
Heuristic Based Optimisation
Issue Date: Apr-2006
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 Cost-Benefit 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, Springer-Verlag, 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.


   Disclaimer | Freedom of Information | Privacy Statement |Copyright ©2012 Robert Gordon University, Garthdee House, Garthdee Road, Aberdeen, AB10 7QB, Scotland, UK: a Scottish charity, registration No. SC013781