A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT

Andrew M. Sutton, Jareth Day, Frank Neumann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationGECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation
Pages433-440
Number of pages8
DOIs
StatePublished - Aug 13 2012
Event14th International Conference on Genetic and Evolutionary Computation, GECCO'12 - Philadelphia, PA, United States
Duration: Jul 7 2012Jul 11 2012

Publication series

NameGECCO'12 - Proceedings of the 14th International Conference on Genetic and Evolutionary Computation

Other

Other14th International Conference on Genetic and Evolutionary Computation, GECCO'12
CountryUnited States
CityPhiladelphia, PA
Period7/7/127/11/12

Keywords

  • combinatorial optimization
  • maxsat
  • runtime analysis
  • theory

Fingerprint Dive into the research topics of 'A parameterized runtime analysis of evolutionary algorithms for MAX-2-SAT'. Together they form a unique fingerprint.

Cite this