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.

Abstract

The Traveling Salesman Problem (TSP) is a computationally challenging combinatorial optimization problem. A comparative study of the local search strategies "First Improvement" and "Best Improvement" was conducted for the TSP in the article titled "First vs Best Improvement: an empirical study" by Hansen et Mladenovic, 2006 [1]. This study empirically compared these two strategies and recommended a rule for choosing the best option based on the quality of the initial solution. The rule proposed by Hansen et Mladenovic, 2006 [1] is as follows: if the initial solution is chosen randomly, the First Improvement strategy (PA) on average yields a better final solution. However, if the initial solution is obtained using a greedy heuristic, the Best Improvement strategy (MA) on average produces better results. This study has become a reference in the research literature, with numerous citations, and is used as a basis for other NP-hard problems. This thesis aims to verify the validity of the rule proposed by Hansen et Mladenovic, 2006 [1] for the TSP and determine if this rule can also be applied to other NP-hard problems. The focus will be on the TSP to verify Hansen et Mladenovic, 2006 [1]’s results. However, in order to evaluate the applicability of this rule to other NP-hard problems, we will also examine the Minimum Set Cover (MSSC) and the Weighted Maximum Satisfiability (MAXSAT-pondéré) problems. These problems will serve as examples to demonstrate that the conclusions of Hansen et Mladenovic, 2006 [1] may not necessarily be applicable to other NP-hard problems, depending on the datasets, initializations used, and neighborhoods considered. Thus, the objective is to conduct a comprehensive study to understand to what extent the rule proposed by Hansen et al. [1] can be generalized or not to different NP-hard problems