 |
    |
An Empirical Evaluation of O(1) Steepest Descent for NK-Landscapes
Darrell Whitley, Wenxiang Chen, and Adele Howe
Colorado State University, Fort Collins, CO, USAAbstract. New methods make it possible to do approximate steepest descent in O(1) time per move for k-bounded pseudo-Boolean functions using stochastic local search. It is also possible to use the average fitness over the Hamming distance 2 neighborhood as a surrogate fitness function and still retain the O(1) time per move. These are average complexity results. In light of these new results, we examine three factors that can influence both the computational cost and the effectiveness of stochastic local search: 1) Fitness function: f(x) or a surrogate; 2) Local optimum escape method: hard random or soft restarts; 3) Descent strategy: next or steepest. We empirically assess these factors in a study of local search for solving NK-landscape problems.
Keywords: Stochastic Local Search, NK-Landscapes, Surrogate Fitness
LNCS 7491, p. 92 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012