Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas

DOI10.1007/S00453-016-0190-3MaRDI QIDQ2362359zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, F. Neumann, Andrew M. Sutton

Publication date 7 July 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-016-0190-3

zbMATH Keywords

satisfiabilityruntime analysisfitness-distance correlation

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Why almost all satisfiable k-CNF formulas are easy
• A better algorithm for random \(k\)-SAT
• scientific article; zbMATH DE number 1555929
• A Better Algorithm for Random k-SAT
• On the analysis of the \((1+1)\) evolutionary algorithm

Cites work

• scientific article; zbMATH DE number 1664964 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• A Theoretical Analysis of Search in GSAT
• A spectral technique for random satisfiable 3CNF formulas
• Adaptive drift analysis
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Analyzing Walksat on random formulas
• Analyzing evolutionary algorithms. The computer science perspective.
• Analyzing randomized search heuristics: tools from probability theory
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Component structure in the evolution of random hypergraphs
• Cores in random hypergraphs and Boolean formulas
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Experimental results on the crossover point in random 3-SAT
• Exponential bounds for the random walk algorithm on random planted 3-SAT
• Finding large cliques in sparse semi-random graphs by simple randomized search heuristics
• Fitness levels with tail bounds for the analysis of randomized search heuristics
• Linear Upper Bounds for Random Walk on Small Density Random 3‐CNFs
• Multiplicative drift analysis
• On the analysis of the \((1+1)\) evolutionary algorithm
• On the greedy algorithm for satisfiability
• On the solution-space geometry of random constraint satisfaction problems
• Performance analysis of randomised search heuristics operating with a fixed budget
• Phase transition for local search on planted SAT
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Proof of the satisfiability conjecture for large \(k\)
• STACS 2005
• Solving random satisfiable 3CNF formulas in expected polynomial time
• The asymptotic k-SAT threshold
• When do evolutionary algorithms optimize separable functions in parallel?
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP

Cited in

(5)

• Solving non-uniform planted and filtered random SAT formulas greedily
• A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions
• Choosing the right algorithm with hints from complexity theory
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• Fixed-Parameter Tractability of the (1 + 1) Evolutionary Algorithm on Random Planted Vertex Covers

This page was built for publication: Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas

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