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 [Formula: see text] time. Bounded separable problems are also solved in [Formula: see text] time. As a result, Gray Box Optimization is able to solve many commonly used problems from the evolutional computation literature in [Formula: see text] 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.
Keywords: Genetic algorithms; MAX-kSAT; Mk Landscapes; NK Landscapes; Walsh analysis; deception; gray box optimization; tree decomposition.