Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation
Author: Doerr, B.
Neumann, F.
Sutton, A.
Citation: Proceedings of the 2015 Genetic and Evolutionary Computation Conference, 2015 / Silva, S. (ed./s), pp.1415-1422
Publisher: Association for Ccomputing Machinery
Issue Date: 2015
ISBN: 9781450334723
Conference Name: 2015 Genetic and Evolutionary Computation Conference (GECCO 2015) (11 Jul 2015 - 15 Jul 2015 : Madrid, Spain)
Statement of
Benjamin Doerr, Frank Neumann, Andrew M. Sutton
Abstract: With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942{951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time O(n log n) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To 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: © 2015 Copyright held by the owner/author(s). Publication rights licensed to ACM.
RMID: 0030042086
DOI: 10.1145/2739480.2754659
Grant ID:
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_109185.pdfRestricted Access833.75 kBAdobe PDFView/Open

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