Name
Abstract | ||
|---|---|---|
Meta-heuristics are a powerful way to approximately solve hard combinatorial optimization problems. However, for a problem, the quality of results can vary considerably from one instance to another. Understanding such a behaviour is important from a theoretical point of view, but also has practical applications such as for the generation of instances during the evaluation stage of a heuristic.In this paper we propose a new complexity measure for the Quadratic Assignment Problem in the context of metaheuristics based on local search, e.g. simulated annealing. We show how the ruggedness coefficient previously introduced by the authors, in conjunction with the well known concept of dominance, provides important features of the search space explored during a local search algorithm, and gives a rather precise idea of the complexity of an instance for these heuristics. We comment previous experimental studies concerning tabu search methods and genetic algorithms with local search in the light of our complexity measure. New computational results with simulated annealing and taboo search are presented. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1023/A:1015454612213 | Journal of Heuristics |
Keywords | Field | DocType |
complexity measures,complexity measure,simulated annealing,important feature,local search algorithm,new computational result,taboo search,search space,new complexity measure,quadratic assignment problem,tabu search method,local search | Hill climbing,Mathematical optimization,Search algorithm,Guided Local Search,Beam search,Artificial intelligence,Local search (optimization),Combinatorial search,Mathematics,Machine learning,Tabu search,Metaheuristic | Journal |
Volume | Issue | ISSN |
8 | 4 | 1381-1231 |
Citations | PageRank | References |
14 | 0.87 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Angel | 1 | 14 | 0.87 |
| Vassilis Zissimopoulos | 2 | 137 | 15.20 |