Interactive Markov Models of Evolutionary Algorithms

Haiping
Ma, Dan Simon, Minrui
Fei, and Hongwei Mo

Interactive Markov models are used
in this research to model evolutionary algorithms. Standard Markov models have
been used in the past (including our own work), but they do not model the interaction
of the individuals in the algorithm; instead they model the
population as a whole. This gives rise to relatively simple models, but the model
orders are intractable for even small problems. For example, for a problem with
a search space cardinality of 100 and a population size of 20, the standard
Markov model is on the order of 10^{22}.
On the other hand, interactive Markov models provide models for the behavior of
the population in a way that accounts for interactions between individuals. So the
transition matrix is much more complex, but a problem with a search space cardinality
of 100 and a population size of 20 can be modeled with a transition matrix that
has a dimension of only 100, which is a size that can easily be handled.

The paper below proposes a couple of simple evolutionary algorithms and shows how they can be modeled with interactive Markov models. The MATLAB software that was used to derive the results in the paper can be downloaded in a zip file.

*Reference*

Haiping Ma, Dan Simon, Minrui Fei, and Hongwei Mo, “Interactive Markov Models of Evolutionary Algorithms,” submitted for publication - pdf, 669 KB

Department of Electrical and Computer Engineering

Last Revised: July 28, 2014