  This paper aims to study how the population size affects the computation time
of evolutionary algorithms in a rigorous way. The computation time of an
evolutionary algorithm can be measured by either the expected number of
generations (hitting time) or the expected 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 presented for
comparing the expected hitting time of two algorithms and estimating lower and
upper bounds on population scalability. Several intuitive beliefs are
rigorously analysed. It is prove 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 unimodal functions in terms of the time-fitness landscape, but
this is not true in terms of the distance-based fitness landscape; (3) using a
population cannot always reduce the expected running time on fully-deceptive
functions, which depends on the benchmark algorithm using elitist selection or
random selection.
