On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms
From MaRDI portal
Publication:2211362
Abstract: It is generally accepted that populations are useful for the global exploration of multi-modal optimisation problems. Indeed, several theoretical results are available showing such advantages over single-trajectory search heuristics. In this paper we provide evidence that evolving populations via crossover and mutation may also benefit the optimisation time for hillclimbing unimodal functions. In particular, we prove bounds on the expected runtime of the standard (+1)~GA for OneMax that are lower than its unary black box complexity and decrease in the leading constant with the population size up to . Our analysis suggests that the optimal mutation strategy is to flip two bits most of the time. To achieve the results we provide two interesting contributions to the theory of randomised search heuristics: 1) A novel application of drift analysis which compares absorption times of different Markov chains without defining an explicit potential function. 2) The inversion of fundamental matrices to calculate the absorption times of the Markov chains. The latter strategy was previously proposed in the literature but to the best of our knowledge this is the first time is has been used to show non-trivial bounds on expected runtimes.
Recommendations
- Population size versus runtime of a simple evolutionary algorithm
- Exponential slowdown for larger populations. The (+1)-EA on monotone functions
- Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions
- On the runtime analysis of the simple genetic algorithm
- Improved time complexity analysis of the simple genetic algorithm
Cites work
- A study of drift analysis for estimating computation time of evolutionary algorithms
- Analyzing evolutionary algorithms. The computer science perspective.
- Black-box search by unbiased variation
- Crossover can be constructive when computing unique input-output sequences
- Crossover can provably be useful in evolutionary computation
- Exponential slowdown for larger populations. The (+1)-EA on monotone functions
- scientific article; zbMATH DE number 6019547 (Why is no real title available?)
- scientific article; zbMATH DE number 960162 (Why is no real title available?)
- Improved time complexity analysis of the simple genetic algorithm
- Introduction to evolutionary computing
- On the inverses of general tridiagonal matrices
- On the runtime analysis of the simple genetic algorithm
- Optimal parameter choices via precise black-box analysis
- The analysis of evolutionary algorithms -- A proof that crossover really can help
- Theory of evolutionary computation. Recent developments in discrete optimization
- Tight bounds on the optimization time of a randomized search heuristic on linear functions
- Towards an analytic framework for analysing the computation time of evolutionary algorithms
Cited in
(13)- Exponential slowdown for larger populations: the \(( \mu + 1)\)-EA on monotone functions
- Tight bounds on the expected runtime of a standard steady state genetic algorithm
- Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
- Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem
- On the impact of the performance metric on efficient algorithm configuration
- scientific article; zbMATH DE number 2040673 (Why is no real title available?)
- Exponential slowdown for larger populations. The (+1)-EA on monotone functions
- The cost of randomness in evolutionary algorithms: crossover can save random bits
- (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error
- An extended jump functions benchmark for the analysis of randomized search heuristics
- Analysing equilibrium states for population diversity
- Diversity-preserving exploitation of crossover
- Improved time complexity analysis of the simple genetic algorithm
This page was built for publication: On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2211362)
