Comparaison empirique de deux stratégies de recherche locale

Le Problème du Voyageur de Commerce (TSP) est un problème d’optimisation combinatoire NP-difficile. Une étude comparative des stratégies de recherche locale "First Improvement" ou Premier améliorant (PA) et "Best Improvement" ou Meilleur améliorant (MA) a été réalisée pour le TSP dans l’article intitulé "First vs Best Improvement : an empirical study" par Hansen et Mladenovic, 2006 [1]. Cette étude a comparé empiriquement ces deux stratégies et a recommandé une règle pour choisir la meilleure option en fonction de la qualité de la solution initiale. La règle proposée par Hansen et Mladenovic, 2006 [1] est la suivante : si la solution initiale est choisie de manière aléatoire, la stratégie de recherche locale PA donne en moyenne une solution finale de meilleure qualité. En revanche, si la solution initiale est obtenue à l’aide d’une heuristique gloutonne, la stratégie MA donne en moyenne de meilleurs résultats. Cette étude est devenue une référence dans la littérature de recherche, avec de nombreuses citations, et elle est utilisée comme base pour d’autres problèmes NP-difficiles. Ce mémoire vise à vérifier la validité de la règle proposée par Hansen et Mladenovic, 2006 [1] pour le Problème du Voyageur de Commerce (TSP) et à déterminer si cette règle peut également s’appliquer à d’autres problèmes NP-difficiles. L’accent sera mis sur le TSP pour vérifier les résultats de Hansen et Mladenovic, 2006 [1]. Cependant, afin d’évaluer l’applicabilité de cette règle à d’autres problèmes NP-difficiles, nous examinerons également le Problème de regroupements avec Minimisation de la Somme des Carrés (MSSC) et le MAXSAT-pondéré. Ces problèmes serviront d’exemples pour montrer que les conclusions de [1] ne sont pas nécessairement applicables à d’autres problèmes NP-difficiles, en fonction des ensembles de données, des initialisations utilisées et des voisinages utilisés. Ainsi, l’objectif est de mener une étude approfondie pour comprendre dans quelle mesure la règle proposée par Hansen et Mladenovic, 2006 [1] peut être généralisée ou non à différents problèmes NP-difficiles.