Advancements in Tabu Search Algorithms: From Learning Approaches to Hyperparameter Optimization

Cette thèse porte sur l’amélioration de l’algorithme de recherche tabou (TS) afin de résoudre des problèmes d’optimisation complexes de manière plus efficace. Bien que TS soit une méta-heuristique puissante pour une large gamme de problèmes d’optimisation, ses performances peuvent être considérablement améliorées. L’objectif principal de cette recherche est dou-ble: (1) améliorer le processus de recherche de TS et (2) développer des méthodes efficaces d’optimisation des hyperparamètres (HPO) dans divers contextes de problèmes. Pour atteindre ces objectifs, nous avons intégré des techniques d’apprentissage automatique, telles que la régression logistique et les arbres de décision, dans le cadre de TS, afin d’améliorer son processus de recherche. Ces méthodes d’apprentissage ont permis d’affiner l’exploration de l’algorithme en réduisant l’espace de recherche et en améliorant la prise de décision au cours de la recherche. De plus, nous avons évalué la performance de TS en utilisant trois méthodes de HPO : MADS, IRACE et la recherche sur grille (Grid Search). La thèse est structurée autour de deux études principales. Dans la première, nous avons intégré l’apprentissage automatique à TS pour résoudre un problème d’ordonnancement des médecins, démontrant des améliorations significatives des performances dans un environ-nement stochastique et des résultats comparables dans des conditions déterministes. La deux-ième étude est relative à l’optimisation des hyperparamètres de TS à l’aide des méthodes men-tionnées plus haut, appliquées à deux problèmes distincts : le problème d’ordonnancement des médecins et le problème généralisé d’affectation multi-ressources. Nos résultats montrent que ces techniques d’optimisation améliorent les performances globales de TS, offrant une approche adaptable et efficace pour résoudre divers problèmes d’optimisation complexes. De manière générale, cette recherche contribue au développement d’algorithmes TS plus robustes et adaptatifs grâce à des améliorations basées sur l’apprentissage et des méthodes d’optimisation des hyperparamètres, proposant ainsi des solutions pratiques à une variété de défis d’optimisation.