Lower and Upper Bounds for Linkage Discovery
Sung-Soon Choi, Kyomin Jung, Byung-Ro Moon · IEEE Transactions on Evolutionary Computation · 2009
For a real-valued functionfdefined on {0,1}n, the linkage graph offis a hypergraph that represents the interactions among the input variables with respect tof. In this paper, lower and upper bounds for the number of function evaluations required to discover the linkage graph are rigorously analyzed in the black box scenario. First, a lower bound for discovering linkage graph is presented. To the best of our knowledge, this is the first result on the lower bound for linkage discovery. The investigation on the lower bound is based on Yao's minimax principle. For the upper bounds, a simple randomized algorithm for linkage discovery is analyzed. Based on the Kruskal-Katona theorem, we present an upper bound for discovering the linkage graph. As a corollary, we rigorously prove thatO(n2logn) function evaluations are enough for bounded functions when the number of hyperedges isO(n), which was suggested but not proven in previous works. To see the typical behavior of the algorithm for linkage discovery, three random models of fitness functions are considered. Using probabilistic methods, we prove that the number of function evaluations on the random models is generally smaller than the bound for the arbitrary case. Finally, from the relation between the linkage graph and the Walsh coefficients, it is shown that, for bounded functions, the proposed bounds are eventually the bounds for finding the Walsh coefficients.