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 1022. 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.
Haiping Ma, Dan Simon, Minrui Fei, and Hongwei Mo, “Interactive Markov Models of Evolutionary Algorithms,” submitted for publication - pdf, 669 KB
Last Revised: July 28, 2014