Theoretical analysis and approximation of infinite population models for evolutionary algorithms

Abstract

Evolutionary algorithms are general purpose optimization algorithms. Despite their successes in many real-world applications, the theoretical analyses of the underlying evolutionary processes and of the behaviors of these algorithms remain incomplete.

This thesis focuses on one major approach of studying evolutionary algorithms theoretically — the dynamical system approach. More specifically, we are concerned with the theoretical foundations and practical approximations of infinite population models of evolutionary algorithms on continuous optimization problems. Infinite population models are generally derived from general state space Markov chains by exploiting symmetry between individuals in the population and analyzing the limiting case when the population size goes to infinity. They are usually described by difference equations (or transition equations) between marginal probability density functions of consecutive generations.

Previously, there are very few studies on the theoretical foundations of infinite population models of evolutionary algorithms. In the first part of this thesis, we show that the convergence proofs in a widely cited study in this area were in fact wrong and incomplete. We further show that the modeling assumption of exchangeability of individuals in that study cannot yield the transition equation in general.

This essentially creates a vacuum in the theoretical foundations of infinite population models. In order to fill the gap, we build a novel analytical framework based on convergence in distribution for random elements taking values in the metric space of infinite sequences. The framework is concise and mathematically rigorous. It provides an infrastructure for studying the convergence of the stacking of operators and of iterating the algorithm which previous studies failed to address.

Then, we use the framework to analyze various operators of the simple evolutionary algorithm. The mutation operator and the k-ary recombination operator are readily analyzed. Our analyses show that for these operators, they have the property of producing identically and independently distributed populations, in the sense that if the initial population is identically and independently distributed, as the population size goes to infinity, in the limit all subsequent generations are also identically and independently distributed. This means that for these operators, the transition equations derived for independently and identically distributed populations can actually predict the real population dynamics as the population size goes to infinity. This provides a theoretical justification for infinite population models. For the infinite population model of proportionate selection, although we have not proved its convergence, we carry out various analyses and report our results.

Finally, to bridge the gap between theory and practice, we propose a general approximation scheme for the transition equations of infinite population models. This scheme is based on Gaussian mixture approximation of functions, and in general it can solve the transition equations in closed form. We prove that given any generation number k, by choosing appropriate values of parameters, the approximation error between our scheme and the infinite population model can be arbitrarily small for all populations before the kth generation. Experimental results show that the proposed scheme is useful in simulating and examining the population dynamics of evolutionary algorithms.