Efficient identification of improving moves in a ball for Pseudo-Boolean problems

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 Theta(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.