A large population size can be unhelpful in evolutionary algorithms

Tianshi CHEN, Ke TANG, Guoliang CHEN, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

90 Citations (Scopus)

Abstract

The utilization of populations is one of the most important features of evolutionary algorithms (EAs). There have been many studies analyzing the impact of different population sizes on the performance of EAs. However, most of such studies are based on computational experiments, except for a few cases. The common wisdom so far appears to be that a large population would increase the population diversity and thus help an EA. Indeed, increasing the population size has been a commonly used strategy in tuning an EA when it did not perform as well as expected for a given problem. He and Yao (2002) [8] showed theoretically that for some problem instance classes, a population can help to reduce the runtime of an EA from exponential to polynomial time. This paper analyzes the role of population further in EAs and shows rigorously that large populations may not always be useful. Conditions, under which large populations can be harmful, are discussed in this paper. Although the theoretical analysis was carried out on one multimodal problem using a specific type of EAs, it has much wider implications. The analysis has revealed certain problem characteristics, which can be either the problem considered here or other problems, that lead to the disadvantages of large population sizes. The analytical approach developed in this paper can also be applied to analyzing EAs on other problems. © 2011 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)54-70
Number of pages17
JournalTheoretical Computer Science
Volume436
Early online date20 Feb 2011
DOIs
Publication statusPublished - Jun 2012
Externally publishedYes

Bibliographical note

Tianshi Chen would like to thank Dr. Jun He for his kind help over the years, and he is also grateful to Dr. Per Kristian Lehre for discussing the analysis of takeover time. This work is partially supported by the Natural Science Foundation of China grants (No. 61033009, No. 61028009, No. 61003064, and No. U0835002), National S&T Major Project (No. 2010ZX01036-001-002), and an Engineering and Physical Science Research Council grant in UK (No. EP/D052785/1).

Keywords

  • Combinatorial optimization
  • Computational time complexity
  • Evolutionary algorithms
  • Evolutionary computation
  • Runtime analysis

Fingerprint

Dive into the research topics of 'A large population size can be unhelpful in evolutionary algorithms'. Together they form a unique fingerprint.

Cite this