Average drift analysis and population scalability

He, J ORCID: https://orcid.org/0000-0002-5616-4691 and Yao, X, 2017. Average drift analysis and population scalability. IEEE Transactions on Evolutionary Computation, 21 (3), pp. 426-439. ISSN 1089-778X

Preview

Text PubSub10567_He.pdf - Post-print Download (379kB) | Preview

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 time-fitness landscape, however this statement is not true in terms of the distance-based 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.

Item Type:	Journal article
Publication Title:	IEEE Transactions on Evolutionary Computation
Creators:	He, J. and Yao, X.
Publisher:	Institute of Electrical and Electronics Engineers (IEEE)
Date:	June 2017
Volume:	21
Number:	3
ISSN:	1089-778X
Identifiers:	Number Type 10.1109/TEVC.2016.2608420 DOI
Divisions:	Schools > School of Science and Technology
Record created by:	Linda Sullivan
Date Added:	19 Mar 2018 09:55
Last Modified:	19 Mar 2018 10:04
URI:	https://irep.ntu.ac.uk/id/eprint/33015

Actions (login required)

Edit View

Statistics

Views

Downloads