Search

Local search and its variants simulated annealing and tabu search are very popular meta-heuristics to approximatively solve NP-hard optimization problems. Several experimental studies in the literature have shown that in practice some problems (e.g. the Traveling Salesman Problem, Quadratic Assignment Problem) behave very well with these heuristics, whereas others do not (e.g. the Low Autocorrelation Binary String Problem). The autocorrelation function, introduced by Weinberger, measures the ruggedness of a landscape which is formed by a cost function and a neighborhood. We use a derived parameter, named the autocorrelation coefficient, as a tool to better understand these phenomena. In this paper we mainly study cost functions including penalty terms. Our results can be viewed as a first attempt to theoretically justify why it is often better in practice to enlarge the solution space and add penalty terms than to work solely on feasible solutions. Moreover, some new results as well as previously known results allow us to obtain a hierarchy of combinatorial optimization problems relatively to their ruggedness. Comparing this classification with experimental results reported in the literature yields a good agreement between ruggedness and difficulty for local search methods. In this way, we are also able to justify theoretically why a neighborhood is better than another for a given problem.

In this article we provide an exact expression for computing the autocorrelation coefficient $\xi$ and the autocorrelation length $\ell$ of any arbitrary instance of the Quadratic Assignment Problem (QAP) in polynomial time using its elementary landscape decomposition. We also provide empirical evidence of the autocorrelation length conjecture in QAP and compute the parameters $\xi$ and $\ell$ for the 137 instances of the QAPLIB. Our goal is to better characterize the difficulty of this important class of problems to ease the future definition of new optimization methods. Also, the advance that this represents helps to consolidate QAP as an interesting and now better understood problem. Spanish Ministry of Science and Innovation and FEDER under contract TIN2008-06491-C04-01 (M* project) and the Andalusian Government under contract P07-TIC-03044 (DIRICOM project).