An Analytical Framework for Runtime of a Class of Continuous Evolutionary Algorithms

Although there have been many studies on the runtime of evolutionary algorithms in discrete optimization, relatively few theoretical results have been proposed on continuous optimization, such as evolutionary programming (EP). This paper proposes an analysis of the runtime of two EP algorithms based on Gaussian and Cauchy mutations, using an absorbing Markov chain. Given a constant variation, we calculate the runtime upper bound of special Gaussian mutation EP and Cauchy mutation EP. Our analysis reveals that the upper bounds are impacted by individual number, problem dimension number n, searching range, and the Lebesgue measure of the optimal neighborhood. Furthermore, we provide conditions whereby the average runtime of the considered EP can be no more than a polynomial of n. The condition is that the Lebesgue measure of the optimal neighborhood is larger than a combinatorial calculation of an exponential and the given polynomial of n.

• Publication year

  2015

• Venue

  Computational Intelligence and Neuroscience

• Publication date

  2015-08-12

• Fields of study

  Mathematics, Computer Science, Medicine

• Identifiers
  DOI 10.1155/2015/485215PMID 26366166PMCID 4556928
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Evolutionary Algorithms for Parameter Optimization—Thirty Years Later

  2023cited by this paper
• Approximation and Parameterized Runtime Analysis of Evolutionary Algorithms for the Maximum Cut Problem

  2015cited by this paper
• Performance Analysis of the (1+1) Evolutionary Algorithm for the Multiprocessor Scheduling Problem

  2015cited by this paper
• Performance Analysis of Evolutionary Algorithms for the Minimum Label Spanning Tree Problem

  2014cited by this paper
• Fitness levels with tail bounds for the analysis of randomized search heuristics

  2014cited by this paper
• Runtime analysis of the (1 + 1) EA on computing unique input output sequences

  2014influential reference
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions†

  2013cited by this paper
• Evolutionary algorithms for continuous-space optimisation

  2013cited by this paper
• Convergence of evolutionary algorithms on the n-dimensional continuous space

  2013cited by this paper
• A New Method for Lower Bounds on the Running Time of Evolutionary Algorithms

  2011cited by this paper
• Drift conditions for estimating the first hitting times of evolutionary algorithms

  2011cited by this paper
• On the Impact of Mutation-Selection Balance on the Runtime of Evolutionary Algorithms

  2010cited by this paper
• On the approximation ability of evolutionary optimization with application to minimum set cover

  2010cited by this paper
• Analysis of the $(1+1)$-EA for Finding Approximate Solutions to Vertex Cover Problems

  2009cited by this paper
• A New Approach for Analyzing Average Time Complexity of Population-Based Evolutionary Algorithms on Unimodal Problems

  2009cited by this paper
• A comparative runtime analysis of heuristic algorithms for satisfiability problems

  2009cited by this paper
• Population size versus runtime of a simple evolutionary algorithm

  2008cited by this paper
• General lower bounds for randomized direct search with isotropic sampling

  2007cited by this paper
• Algorithmic analysis of a basic evolutionary algorithm for continuous optimization

  2007cited by this paper
• A new approach to estimating the expected first hitting time of evolutionary algorithms

  2006cited by this paper
• Analysis of a Multiobjective Evolutionary Algorithm on the 0-1 knapsack problem

  2006cited by this paper
• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem

  2004cited by this paper
• Evolutionary programming using mutations based on the Levy probability distribution

  2004influential reference
• Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions

  2004cited by this paper
• On the analysis of the (1+1) evolutionary algorithm

  2002cited by this paper
• Drift analysis and average time complexity of evolutionary algorithms

  2001cited by this paper
• Self-adaptive mutations may lead to premature convergence

  2001cited by this paper
• Evolutionary programming made faster

  1999influential reference
• Convergence of evolutionary algorithms in general search spaces

  1996cited by this paper
• Evolution and optimum seeking

  1995cited by this paper
• Convergence of non-elitist strategies

  1994cited by this paper
• Applying evolutionary programming to selected traveling salesman problems

  1993influential reference
• An Overview of Evolutionary Algorithms for Parameter Optimization

  1993influential reference
• Evolution and Optimum Seeking: The Sixth Generation

  1993cited by this paper
• Evolving artificial intelligence

  1992cited by this paper
• System Identification Through Simulated Evolution: A Machine Learning Approach to Modeling

  1991influential reference
• Artificial Intelligence through Simulated Evolution

  1966cited by this paper
• could affect the content, and all legal disclaimers that apply to the journal pertain

  year unknowncited by this paper

• No citing papers are available for this paper.