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.

Abstract

This thesis focuses on advancing the tabu search (TS) algorithm to address complex opti-mization problems more efficiently and effectively. Although TS has proven to be a powerful metaheuristic for solving a wide range of optimization problems, its performance can be sig-nificantly improved. The primary objective of this research is twofold: (1) to improve the search process of TS, and (2) to develop effective methods for hyperparameter optimization (HPO) across various problem contexts. To achieve these objectives, we introduce machine learning techniques such as logistic regres-sion and decision trees into the TS framework to enhance its search process. These learning methods help refine the algorithm’s exploration by reducing the search space and improving decision-making during the search. In addition, we evaluate the performance of TS using three HPO methods: MADS, IRACE, and Grid Search. The thesis is structured around two key studies. In the first study, we integrate machine learning into TS to solve a physician scheduling problem, demonstrating significant perfor-mance improvements in a stochastic environment and comparable results in deterministic settings. The second study focuses on optimizing the TS hyperparameters using the men-tioned tuning methods for two distinct problems: the Physician Scheduling Problem and the Multi-Resource Generalized Assignment Problem. Our findings reveal that these optimiza-tion techniques enhance the overall performance of TS, providing an adaptable and efficient approach to solving various hard optimization problems. In general, this research contributes to the development of more robust and adaptable TS algorithms through learning-based enhancements and HPO methods, offering practical solu-tions to a variety of challenging optimization tasks.