| Titre : | Revisiting the big valley search space structure in the TSP (2011) |
| Auteurs : | Hains, D. R., Auteur ; Whitley, L. D., Auteur ; Howe, A. E., Auteur |
| Type de document : | Article : texte imprimé |
| Dans : | Journal of the operational research society (JORS) (Vol. 62 N° 2 Special issue, Fevrier 2011) |
| Article en page(s) : | pp. 305–312 |
| Note générale : | Recherche opérationnelle |
| Langues : | Anglais |
| Index. décimale : | 001.424 |
| Tags : | Combinatorial optimization Local search Travelling salesman problem |
| Résumé : | The solution space of the travelling salesman problem under 2-opt moves has been characterized as having a big-valley structure, in which the evaluation of a tour is positively correlated to the distance of the tour from the global optimum. We examine the big-valley hypothesis more closely and show that while the big-valley structure does appear in much of the solution space, it breaks down around local optima that have solutions whose evaluation is very close to that of the global optimum; multiple funnels appear around local optima with evaluations close to the global optimum. The appearance of multiple funnels explains why certain iterated local search heuristics can quickly find high-quality solutions, but fail to consistently find the global optimum. We then investigate a novel search operator, which is demonstrated to have the ability to escape funnels at evaluations close to the global optimum. |
| DEWEY : | 001.424 |
| ISSN : | 0160-5682 |
| En ligne : | http://www.palgrave-journals.com/jors/journal/v62/n2/abs/jors2010116a.html |
