Gray Box Optimization for Mk Landscapes (NK Landscapes and MAX-kSAT)
研究了由M个子函数组成的伪布尔优化问题的灰盒优化方法，每个子函数最多接受k个变量，称为Mk景观。灰盒优化可在多项式时间内求解非欺骗问题和有界可分问题，并比暴力方法更快枚举所有局部最优。
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.