Revisiting the big valley search space structure in the TSP / Hains, D. R. in Journal of the operational research society (JORS), Vol. 62 N° 2 Special issue (Fevrier 2011)  

Public ISBD [article]  inJournal of the operational research society (JORS) > Vol. 62 N° 2 Special issue (Fevrier 2011) . - pp. 305–312 Titre : Revisiting the big valley search space structure in the TSP Type de document : texte imprimé Auteurs : Hains, D. R., Auteur ; Whitley, L. D., Auteur ; Howe, A. E., Auteur Année de publication : 2011 Article en page(s) : pp. 305–312 Note générale : Recherche opérationnelle Langues : Anglais (eng) Mots-clés : Combinatorial optimization Local search Travelling salesman problem Index. décimale : 001.424 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 [article] Revisiting the big valley search space structure in the TSP [texte imprimé] / Hains, D. R., Auteur ; Whitley, L. D., Auteur ; Howe, A. E., Auteur . - 2011 . - pp. 305–312. Recherche opérationnelle Langues : Anglais (eng) in Journal of the operational research society (JORS) > Vol. 62 N° 2 Special issue (Fevrier 2011) . - pp. 305–312 Mots-clés : Combinatorial optimization Local search Travelling salesman problem Index. décimale : 001.424 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

Exemplaires

Code-barres	Cote	Support	Localisation	Section	Disponibilité
aucun exemplaire