Upper and lower bounds for randomized search heuristics in black-box optimization

DOI10.1007/s00224-004-1177-zzbMath1103.68115OpenAlexW1981482533MaRDI QIDQ2432545

Ingo Wegener, Stefan Droste, Thomas Jansen

Publication date: 25 October 2006

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2003/5451

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items

Black-box complexity: advantages of memory usage ⋮ \textsc{OneMax} in black-box models with several restrictions ⋮ Populations can be essential in tracking dynamic optima ⋮ Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems ⋮ A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions ⋮ Multiobjective optimization: when objectives exhibit non-uniform latencies ⋮ Black-Box Complexity for Bounding the Performance of Randomized Search Heuristics ⋮ Enhance chaotic gravitational search algorithm (CGSA) by balance adjustment mechanism and sine randomness function for continuous optimization problems ⋮ Playing Several Variants of Mastermind with Constant-Size Memory is not Harder than with Unbounded Memory ⋮ Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints ⋮ Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax ⋮ Analysis of runtime of optimization algorithms for noisy functions over discrete codomains ⋮ Runtime Analysis of a Co-Evolutionary Algorithm ⋮ Running time analysis of ant colony optimization for shortest path problems ⋮ Analyzing different variants of immune inspired somatic contiguous hypermutations ⋮ Choosing the right algorithm with hints from complexity theory ⋮ More precise runtime analyses of non-elitist evolutionary algorithms in uncertain environments ⋮ Black-box search by unbiased variation ⋮ Do additional target points speed up evolutionary algorithms? ⋮ Towards implementation of a generalized architecture for high-level quantum programming language ⋮ Illustration of fairness in evolutionary multi-objective optimization ⋮ Simplified drift analysis for proving lower bounds in evolutionary computation ⋮ How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys ⋮ The unbiased black-box complexity of partition is polynomial ⋮ From black-box complexity to designing new genetic algorithms ⋮ On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization ⋮ Lower bounds for randomized direct search with isotropic sampling ⋮ The query complexity of a permutation-based variant of mastermind ⋮ Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity ⋮ The runtime of the compact genetic algorithm on jump functions ⋮ Tight Bounds for Blind Search on the Integers and the Reals ⋮ The \((1+1)\) elitist black-box complexity of LeadingOnes ⋮ Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm ⋮ Static and self-adjusting mutation strengths for multi-valued decision variables ⋮ Reducing the arity in unbiased black-box complexity ⋮ Ranking-based black-box complexity ⋮ Playing mastermind with constant-size memory ⋮ Optimal parameter choices via precise black-box analysis ⋮ Working principles of binary differential evolution ⋮ Single-solution simulated Kalman filter algorithm for global optimisation problems ⋮ A multi-strategy enhanced sine cosine algorithm for global optimization and constrained practical engineering problems ⋮ Population size versus runtime of a simple evolutionary algorithm ⋮ Toward a unifying framework for evolutionary processes ⋮ Theoretical Analysis of Local Search in Software Testing ⋮ Memory-restricted black-box complexity of OneMax ⋮ Unbiasedness of estimation-of-distribution algorithms