Gray Box Optimization for Mk Landscapes (NK Landscapes and MAX-kSAT).

MATHEMATICAL optimization; BOOLEAN functions; GRAPH theory; GENETIC algorithms; DYNAMIC programming; COMPUTATIONAL complexity

This article investigates Gray Box Optimization for pseudo-Boolean optimization problems composed of M subfunctions, where each subfunction accepts at most k variables. We will refer to these as Mk Landscapes. In Gray Box Optimization, the optimizer is given access to the set of M subfunctions. We prove Gray Box Optimization can efficiently compute hyperplane averages to solve non-deceptive problems in O(n) time. Bounded separable problems are also solved in O(n) time. As a result, Gray Box Optimization is able to solve many commonly used problems from the evolutional computation literature in O(1) evaluations. We also introduce a more general class of Mk Landscapes that can be solved using dynamic programming and discuss properties of these functions. For certain type of problems Gray Box Optimization makes it possible to enumerate all local optima faster than brute force methods. We also provide evidence that randomly generated test problems are far less structured than those found in real-world problems. [ABSTRACT FROM AUTHOR]

Copyright of Evolutionary Computation is the property of MIT Press and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)