Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/109185
Citations | ||
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) |
Editor: | Silva, S. |
Statement of Responsibility: | 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. |
DOI: | 10.1145/2739480.2754659 |
Grant ID: | http://purl.org/au-research/grants/arc/DP140103400 |
Published version: | http://dx.doi.org/10.1145/2739480.2754659 |
Appears in Collections: | Aurora harvest 3 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_109185.pdf Restricted Access | Restricted Access | 833.75 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.