Machine Learning Algorithms for Combinatorial Optimization

Une variété de tâches de décision dans la science et l'industrie modernes sont des problèmes d'optimisation combinatoire. Pour résoudre ces problèmes difficiles, des recherches étonnantes ont été menées dans le domaine au cours des dernières décennies. Bien que les méthodes et les techniques d'optimisation développées aient conduit à une multitude d'outils d'optimisation et aient été appliquées avec succès pour résoudre régulièrement un grand nombre de problèmes, il existe encore de nombreux cas pratiques où les techniques existantes ne sont pas adéquates et il est toujours impératif de concevoir et de mettre en œuvre de nouveaux algorithmes et stratégies d'optimisation combinatoire. L'apprentissage automatique est un sous-domaine de l'intelligence artificielle. Ces dernières années, l'application des techniques d'apprentissage automatique dans l'optimisation combinatoire est devenue un domaine de recherche émergent. Dans cette thèse, nous visons à renforcer cette direction et nous soutenons que l'apprentissage automatique est un complément prometteur à l'optimisation combinatoire. Plus précisément, nous étudions différents paradigmes pour appliquer l'apprentissage automatique en combinaison avec l'optimisation combinatoire et présentons trois contributions ci-dessous. Tout d'abord, nous considérons un problème d'optimisation combinatoire spécifique et proposons un cadre pour l'apprentissage d'heuristiques constructives produisant des solutions de haute qualité. Les résultats montrent que notre approche d'apprentissage atteint des performances de généralisation remarquables sur des graphes de plus grande taille et d'une distribution différente. Deuxièmement, nous considérons l'application de l'apprentissage automatique pour les décisions au sein d'algorithmes d'optimisation combinatoire et proposons un cadre d'apprentissage pour prédire et pour adapter la taille du voisinage de l'heuristique, le branchement local, pour la programmation en nombres entiers. Nous montrons informatiquement que les décisions algorithmiques critiques au sein de l'heuristique peuvent en effet être apprises par apprentissage automatique. L'algorithme résultant se généralise bien à la fois au niveau de la taille de l'instance et, remarquablement, entre les instances. Enfin, nous présentons une contribution méthodologique pour l'intégration de l'apprentissage automatique dans les métaheuristiques pour la résolution de problèmes généraux d'optimisation combinatoire. Plus précisément, nous proposons un cadre général d'apprentissage automatique pour la génération de voisins dans la recherche de métaheuristiques. La clé de la méthodologie proposée réside dans la définition et la génération de voisinages de solutions prometteuses. Nous proposons un cadre de classification qui exploite les propriétés structurelles du problème et des solutions de haute qualité et qui sélectionne un sous-ensemble de variables pour définir un voisinage de recherche prometteur pour la recherche métaheuristique. Nous démontrons l'efficacité de notre cadre sur deux schémas métaheuristiques, et les résultats expérimentaux indiquent que notre approche permet d'apprendre un compromis satisfaisant entre l'exploration d'un espace de solutions plus large et l'exploitation de régions locales prometteuses.