A Markovianity based optimisation algorithm

Siddhartha Shakya, Roberto Santana, Jose A. Lozano

Research output: Contribution to journalArticlepeer-review

24 Scopus citations


Several Estimation of Distribution Algorithms (EDAs) based on Markov networks have been recently proposed. The key idea behind these EDAs was to factorise the joint probability distribution of solution variables in terms of cliques in the undirected graph. As such, they made use of the global Markov property of the Markov network in one form or another. This paper presents a Markov Network based EDA that is based on the use of the local Markov property, the Markovianity, and does not directly model the joint distribution. We call it Markovianity based Optimisation Algorithm. The algorithm combines a novel method for extracting the neighbourhood structure from the mutual information between the variables, with a Gibbs sampler method to generate new points. We present an extensive empirical validation of the algorithm on problems with complex interactions, comparing its performance with other EDAs that use higher order interactions. We extend the analysis to other functions with discrete representation, where EDA results are scarce, comparing the algorithm with state of the art EDAs that use marginal product factorisations.

Original languageBritish English
Pages (from-to)159-195
Number of pages37
JournalGenetic Programming and Evolvable Machines
Issue number2
StatePublished - Jun 2012


  • Competent genetic algorithms
  • Estimation of distribution algorithms
  • Markov networks


Dive into the research topics of 'A Markovianity based optimisation algorithm'. Together they form a unique fingerprint.

Cite this