Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas
Author: Doerr, B.
Neumann, F.
Sutton, A.
Citation: Algorithmica, 2017; 78(2):561-586
Publisher: Springer
Issue Date: 2017
ISSN: 0178-4617
Statement of
Benjamin Doerr, Frank Neumann, Andrew M. Sutton
Abstract: We contribute to the theoretical understanding of randomized search heuristics by investigating their optimization behavior on satisfiable random k-satisfiability instances both in the planted solution model and the uniform model conditional on satisfiability. Denoting the number of variables by n, our main technical result is that the simple (1+1) evolutionary algorithm with high probability finds a satisfying assignment in time O(nlogn) when the clause-variable density is at least logarithmic. For low density instances, evolutionary algorithms seem to be less effective, and all we can show is a subexponential upper bound on the runtime for densities below 1k(k−1). We complement these mathematical results with numerical experiments on a broader density spectrum. They indicate that, indeed, the (1+1)EA is less efficient on lower densities. Our experiments also suggest that the implicit constants hidden in our main runtime guarantee are low. Our main result extends and considerably improves the result obtained by Sutton and Neumann (Lect Notes Comput Sci 8672:942–951, 2014) in terms of runtime, minimum density, and clause length. These improvements are made possible by establishing a close fitness-distance correlation in certain parts of the search space. This approach might be of independent interest and could be useful for other average-case analyses of randomized search heuristics. While the notion of a fitness-distance correlation has been around for a long time, to the best of our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.
Keywords: Runtime analysis; satisfiability; fitness-distance correlation
Rights: © Springer Science+Business Media New York 2016
RMID: 0030054732
DOI: 10.1007/s00453-016-0190-3
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.