title: An evaluation of methods for estimating the number of local optima in combinatorial optimization problems.
abstract: The solution of many combinatorial optimization problems is carried out by metaheuristics, which generally make use of local search algorithms. These algorithms use some kind of neighborhood structure over the search space. The performance of the algorithms strongly depends on the properties that the neighborhood imposes on the search space. One of these properties is the number of local optima. Given an instance of a combinatorial optimization problem and a neighborhood, the estimation of the number of local optima can help not only to measure the complexity of the instance, but also to choose the most convenient neighborhood to solve it. In this paper we review and evaluate several methods to estimate the number of local optima in combinatorial optimization problems. The methods reviewed not only come from the combinatorial optimization literature, but also from the statistical literature. A thorough evaluation in synthetic as well as real problems is given. We conclude by providing recommendations of methods for several scenarios.
authors.affiliation: Intelligent Systems Group, Department of Computer Science and Artificial Intelligence, University of the Basque Country UPV/EHU, 20018 San Sebastián, Spain leticia.hernando@ehu.es.
authors.forename: Leticia
authors.initials: L
authors.lastname: Hernando
authors.forename: Alexander
authors.initials: A
authors.lastname: Mendiburu
authors.forename: Jose A
authors.initials: JA
authors.lastname: Lozano
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D005716:Game Theory; D013223:Statistics as Topic