File Download
Supplementary

Citations:
 Appears in Collections:
postgraduate thesis: Theoretical analysis and approximation of infinite population models for evolutionary algorithms
Title  Theoretical analysis and approximation of infinite population models for evolutionary algorithms 

Authors  
Issue Date  2015 
Publisher  The University of Hong Kong (Pokfulam, Hong Kong) 
Citation  Song, B. [宋博]. (2015). Theoretical analysis and approximation of infinite population models for evolutionary algorithms. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5558992 
Abstract  Evolutionary algorithms are general purpose optimization algorithms. Despite their successes in many realworld 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 kary 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. 
Degree  Doctor of Philosophy 
Subject  Evolutionary computation Algorithms 
Dept/Program  Electrical and Electronic Engineering 
Persistent Identifier  http://hdl.handle.net/10722/216256 
HKU Library Item ID  b5558992 
DC Field  Value  Language 

dc.contributor.author  Song, Bo   
dc.contributor.author  宋博   
dc.date.accessioned  20150908T23:11:33Z   
dc.date.available  20150908T23:11:33Z   
dc.date.issued  2015   
dc.identifier.citation  Song, B. [宋博]. (2015). Theoretical analysis and approximation of infinite population models for evolutionary algorithms. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5558992   
dc.identifier.uri  http://hdl.handle.net/10722/216256   
dc.description.abstract  Evolutionary algorithms are general purpose optimization algorithms. Despite their successes in many realworld 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 kary 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.   
dc.language  eng   
dc.publisher  The University of Hong Kong (Pokfulam, Hong Kong)   
dc.relation.ispartof  HKU Theses Online (HKUTO)   
dc.rights  The author retains all proprietary rights, (such as patent rights) and the right to use in future works.   
dc.rights  Creative Commons: AttributionNonCommerical 3.0 Hong Kong License   
dc.subject.lcsh  Evolutionary computation   
dc.subject.lcsh  Algorithms   
dc.title  Theoretical analysis and approximation of infinite population models for evolutionary algorithms   
dc.type  PG_Thesis   
dc.identifier.hkul  b5558992   
dc.description.thesisname  Doctor of Philosophy   
dc.description.thesislevel  Doctoral   
dc.description.thesisdiscipline  Electrical and Electronic Engineering   
dc.description.nature  published_or_final_version   