Towards an analytic framework for analysing the computation time of evolutionary algorithms

DOI10.1016/S0004-3702(02)00381-8zbMath1082.68802MaRDI QIDQ814443

Xin Yao, Jun He

Publication date: 7 February 2006

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

Markov chainEvolutionary algorithmsTime complexityFirst hitting time

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (19)

A comparative runtime analysis of heuristic algorithms for satisfiability problems ⋮ Choosing selection pressure for wide-gap problems ⋮ Understanding measure-driven algorithms solving irreversibly ill-conditioned problems ⋮ A new approach to estimating the expected first hitting time of evolutionary algorithms ⋮ Evolutionary optimization: pitfalls and booby traps ⋮ The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems ⋮ Practical performance models of algorithms in evolutionary program induction and other domains ⋮ A dual-population algorithm based on alternative evolution and degeneration for solving constrained multi-objective optimization problems ⋮ The use of tail inequalities on the probable computational time of randomized search heuristics ⋮ Free lunches on the discrete Lipschitz class ⋮ On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms ⋮ Backward-chaining evolutionary algorithms ⋮ Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes ⋮ Markov chain analysis of evolutionary algorithms on OneMax function -- from coupon collector's problem to (1 + 1) EA ⋮ The time complexity analysis of a class of gene expression programming ⋮ Recent advances in evolutionary computation ⋮ Coevolutionary systems and PageRank ⋮ Population size versus runtime of a simple evolutionary algorithm ⋮ Estimation of distribution algorithms on non-separable problems

Uses Software

• Genocop

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Markov chains and stochastic stability
• Inertia characteristics of self-adjoint matrix polynomials
• Modeling genetic algorithms with Markov chains.
• Evolutionary algorithms. The role of mutation and recombination
• On the analysis of the \((1+1)\) evolutionary algorithm
• Erratum to: ``Drift analysis and average time complexity of evolutionary algorithms
• Theory of evolutionary algorithms: A bird's eye view
• On the convergence rates of genetic algorithms
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: Towards an analytic framework for analysing the computation time of evolutionary algorithms