A large population size can be unhelpful in evolutionary algorithms

DOI10.1016/J.TCS.2011.02.016zbMATH Open1242.68286arXiv1208.2345OpenAlexW2091342063MaRDI QIDQ428903FDOQ428903

Authors: Tianshi Chen, Ke Tang, Xin Yao, Guoliang Chen 

Publication date: 25 June 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

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 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) 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 multi-modal 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.

Full work available at URL: https://arxiv.org/abs/1208.2345

Recommendations

• Population size versus runtime of a simple evolutionary algorithm
• Global versus local search: the impact of population sizes on evolutionary algorithm performance
• Exponential slowdown for larger populations. The \((\mu+1)\)-EA on monotone functions
• Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions
• Populations can be essential in tracking dynamic optima

zbMATH Keywords

combinatorial optimizationevolutionary algorithmsevolutionary computationruntime analysiscomputational time complexity

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A study of drift analysis for estimating computation time of evolutionary algorithms
• Drift analysis and average time complexity of evolutionary algorithms
• On the impact of the mutation-selection balance on the runtime of evolutionary algorithms
• Choosing selection pressure for wide-gap problems
• On the analysis of the \((1+1)\) evolutionary algorithm

Cited In (11)

• Deep clustering of the traveling salesman problem to parallelize its solution
• An image-guided computational approach to inversely determine \textit{in vivo} material properties and model flow-structure interactions of fish fins
• Title not available (Why is that?)
• The use of tail inequalities on the probable computational time of randomized search heuristics
• Global versus local search: the impact of population sizes on evolutionary algorithm performance
• An evolutionary approach to optimizing teleportation cost in distributed quantum computation
• On the genetic algorithm with adaptive mutation rate and selected statistical applications
• On the equality constraints tolerance of constrained optimization problems
• Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem
• Fault trees from data: efficient learning with an evolutionary algorithm
• Evolutionary optimization: pitfalls and booby traps

This page was built for publication: A large population size can be unhelpful in evolutionary algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428903)