Rigorous Performance Analysis of ...
Type de document :
Communication dans un congrès avec actes
Titre :
Rigorous Performance Analysis of State-of-the-Art TSP Heuristic Solvers
Auteur(s) :
Mcmenemy, Paul [Auteur]
University of Stirling
Veerapen, Nadarajen [Auteur]
Operational Research, Knowledge And Data [ORKAD]
Adair, Jason [Auteur]
University of Stirling
Ochoa, Gabriela [Auteur]
University of Stirling
University of Stirling
Veerapen, Nadarajen [Auteur]

Operational Research, Knowledge And Data [ORKAD]
Adair, Jason [Auteur]
University of Stirling
Ochoa, Gabriela [Auteur]
University of Stirling
Titre de la manifestation scientifique :
European Conference on Evolutionary Computation in Combinatorial Optimization
Ville :
Leipzig
Pays :
Allemagne
Date de début de la manifestation scientifique :
2019-04-24
Titre de la revue :
Lecture Notes in Computer Science
Date de publication :
2019-03-28
Mot(s)-clé(s) en anglais :
TSP
Algorithm Selection
EAX
GPX
Performance Analysis
Algorithm Selection
EAX
GPX
Performance Analysis
Discipline(s) HAL :
Informatique [cs]/Intelligence artificielle [cs.AI]
Computer Science [cs]/Operations Research [math.OC]
Computer Science [cs]/Operations Research [math.OC]
Résumé en anglais : [en]
Understanding why some problems are better solved by one algorithm rather than another is still an open problem, and the symmetric Travelling Salesperson Problem (TSP) is no exception. We apply three state-of-the-art ...
Lire la suite >Understanding why some problems are better solved by one algorithm rather than another is still an open problem, and the symmetric Travelling Salesperson Problem (TSP) is no exception. We apply three state-of-the-art heuristic solvers to a large set of TSP instances of varying structure and size, identifying which heuristics solve specific instances to optimality faster than others. The first two solvers considered are variants of the multi-trial Helsgaun’s Lin-Kernighan Heuristic (a form of iterated local search), with each utilising a different form of Partition Crossover; the third solver is a genetic algorithm (GA) using Edge Assembly Crossover. Our results show that the GA with Edge Assembly Crossover is the best solver, shown to significantly outperform the other algorithms in 73% of the instances analysed. A comprehensive set of features for all instances is also extracted, and decision trees are used to identify main features which could best inform algorithm selection. The most prominent features identified a high proportion of instances where the GA with Edge Assembly Crossover performed significantly better when solving to optimality.Lire moins >
Lire la suite >Understanding why some problems are better solved by one algorithm rather than another is still an open problem, and the symmetric Travelling Salesperson Problem (TSP) is no exception. We apply three state-of-the-art heuristic solvers to a large set of TSP instances of varying structure and size, identifying which heuristics solve specific instances to optimality faster than others. The first two solvers considered are variants of the multi-trial Helsgaun’s Lin-Kernighan Heuristic (a form of iterated local search), with each utilising a different form of Partition Crossover; the third solver is a genetic algorithm (GA) using Edge Assembly Crossover. Our results show that the GA with Edge Assembly Crossover is the best solver, shown to significantly outperform the other algorithms in 73% of the instances analysed. A comprehensive set of features for all instances is also extracted, and decision trees are used to identify main features which could best inform algorithm selection. The most prominent features identified a high proportion of instances where the GA with Edge Assembly Crossover performed significantly better when solving to optimality.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-02095416/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02095416/document
- Accès libre
- Accéder au document
- http://dspace.stir.ac.uk/bitstream/1893/29359/1/McMenemy.pdf
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-02095416/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- evocop2019-performance_analysis_tsp.pdf
- Accès libre
- Accéder au document
- McMenemy.pdf
- Accès libre
- Accéder au document