Efficient identification of improving moves in a ball for pseudo-boolean problems

Francisco Chicano, Darrell Whitley, Andrew M. Sutton

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

24 Scopus citations

Abstract

Hill climbing algorithms are at the core of many approaches to solve optimization problems. Such algorithms usually require the complete enumeration of a neighborhood of the current solution. In the case of problems defined over binary strings of length n, we define the r-ball neighborhood as the set of solutions at Hamming distance r or less from the current solution. For r ≪ n this neighborhood contains Θ(nr) solutions. In this paper efficient methods are introduced to locate improving moves in the r-ball neighborhood for problems that can be written as a sum of a linear number of subfunctions depending on a bounded number of variables. NK-landscapes and MAX-kSAT are examples of these problems. If the number of subfunctions depending on any given variable is also bounded, then we prove that the method can explore the neighborhood in constant time, despite the fact that the number of solutions in the neighborhood is polynomial in n. We develop a hill climber based on our exploration method and we analyze its efficiency and efficacy using experiments with NKq-landscapes instances.

Original languageEnglish (US)
Title of host publicationGECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Pages437-444
Number of pages8
ISBN (Print)9781450326629
DOIs
StatePublished - 2014
Event16th Genetic and Evolutionary Computation Conference, GECCO 2014 - Vancouver, BC, Canada
Duration: Jul 12 2014Jul 16 2014

Publication series

NameGECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference

Other

Other16th Genetic and Evolutionary Computation Conference, GECCO 2014
CountryCanada
CityVancouver, BC
Period7/12/147/16/14

Keywords

  • Hill climbing
  • Local search
  • NK-landscapes
  • Pseudo-boolean optimization

Fingerprint Dive into the research topics of 'Efficient identification of improving moves in a ball for pseudo-boolean problems'. Together they form a unique fingerprint.

Cite this