Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/77338
Citations | ||
Scopus | Web of ScienceĀ® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT |
Author: | Sutton, A. Day, J. Neumann, F. |
Citation: | Proceedings of the 14th International Conference on Genetic and Evolutionary Computation, held in Philadelphia, Pennsylvania, 7-11 July, 2012 / T. Soule (ed.): pp.433-440 |
Publisher: | Association for Computing Machinery |
Publisher Place: | online |
Issue Date: | 2012 |
ISBN: | 9781450311779 |
Conference Name: | Genetic and Evolutionary Computation Conference (14th : 2012 : Philadelphia, Pennsylvania) |
Editor: | Soule, T. |
Statement of Responsibility: | Andrew M. Sutton, Jareth Day and Frank Neumann |
Abstract: | We investigate the MAX-2-SAT problem and study evolutionary algorithms by parameterized runtime analysis. The parameterized runtime analysis of evolutionary algorithms has been initiated recently and reveals new insights into which type of instances of NP-hard combinatorial optimization problems are hard to solve by evolutionary computing methods. We show that a variant of the (1+1) EA is a fixed-parameter evolutionary algorithm with respect to the standard parameterization for MAX-2-SAT. Furthermore, we study how the dependencies between the variables affect problem difficulty and present fixed-parameter evolutionary algorithms for the MAX-(2,3)-SAT problem where the studied parameter is the diameter of the variable graph. |
Keywords: | Combinatoria optimization MAXSAT theory runtime analysis |
Rights: | Copyright 2012 ACM |
DOI: | 10.1145/2330163.2330225 |
Published version: | http://dx.doi.org/10.1145/2330163.2330225 |
Appears in Collections: | Aurora harvest 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.