##### 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.