Projects per year
Abstract
This paper aims to study how the population size affects the computation time of evolutionary algorithms in a rigorous way. The computation time of evolutionary algorithms can be measured by either the number of generations (hitting time) or the number of fitness evaluations (running time) to find an optimal solution. Population scalability is the ratio of the expected hitting time between a benchmark algorithm and an algorithm using a larger population size. Average drift analysis is introduced to compare the expected hitting time of two algorithms and to estimate lower and upper bounds on the population scalability. Several intuitive beliefs are rigorously analysed. It is proven that (1) using a population sometimes increases rather than decreases the expected hitting time; (2) using a population cannot shorten the expected running time of
any elitist evolutionary algorithm on any unimodal function on the timefitness landscape, however this statement is not true in terms of the distancebased fitness landscape; (3) using a population cannot always reduce the expected running time on deceptive functions, which depends on whether the benchmark
algorithm uses elitist selection or random selection.
any elitist evolutionary algorithm on any unimodal function on the timefitness landscape, however this statement is not true in terms of the distancebased fitness landscape; (3) using a population cannot always reduce the expected running time on deceptive functions, which depends on whether the benchmark
algorithm uses elitist selection or random selection.
Original language  English 

Pages (fromto)  426439 
Number of pages  26 
Journal  IEEE Transactions on Evolutionary Computation 
Volume  21 
Issue number  3 
Early online date  29 Sep 2016 
DOIs  
Publication status  Published  Jun 2017 
Fingerprint
Dive into the research topics of 'Average Drift Analysis and Population Scalability'. Together they form a unique fingerprint.Projects
 2 Finished

Evolutionary Computation for Dynamic Optimisation in Network Environments
Engineering & Physical Science Research Council
25/02/13 → 17/08/17
Project: Research Councils

Evolutionary Approximation Algorithms for Optimisation: Algorithm Design and Complexity Analysis
Engineering & Physical Science Research Council
29/04/11 → 28/10/15
Project: Research Councils