Learning-driven optimization approaches for combinatorial search problems
Institution:
AngersDisciplines:
Directors:
Abstract EN:
This thesis is devoted to developing learning-driven optimization approaches for solving hard Combinatorial Optimization Problems (COPs). We particularly consider three important categories of COPs, including grouping problems such as Graph Coloring Problem (GCP), subset selection problems such as Maximum Diversity Problem (MDP), and permutation problems such as Quadratic Assignment Problem (QAP). These three classes of problems are of important theoretical significance, and have a wide range of practical applications. Given that they usually belong to the NP-hard problems, it is computationally difficult to solve them in the general case. This thesis concentrates on designing learning-driven heuristic optimization approaches for solving these problems.With the help of machine learning techniques,heuristic approaches will be able to benefit from their past search history such as discovering promising regions and useful patterns to find better solutions. In this thesis, we propose three learning-driven heuristic approaches for the three categories of considered COPs. We develop a probability learning based local search for grouping problems, especially for GCP; an opposition-based memetic search for MDP; and a frequent pattern based search for QAP. All the proposed approaches were experimentally assessed based on benchmarks, and experimental results show that they compete favorably with state-of-the-art methods. Also, the beneficial effects of the introduced learning techniques are confirmed by experimental evidence
Abstract FR:
Cette thèse vise à développer des approches de résolution heuristique renforcées par des méthodes d'apprentissage pour résoudre des problèmes d'optimisation combinatoire difficiles (COPs). Nous considérons notamment trois types importants de COPs, les problèmes de groupement comme la coloration de graphe (GCP), les problèmes de sélection de sous-ensembles comme la diversité maximum (MDP) et les problèmes de permutation comme l'assignation quadratique (QAP). Ces trois classes de problèmes ont de nombreuses applications pratiques, mais ils sont dans le cas général N P-difficiles. Cette thèse s'attache à proposer des méthodes heuristiques renforcées par des méthodes d’apprentissage. Les méthodes d'apprentissage permettent d'exploiter les traces des explorations déjà effectuées afin de découvrir des régions prometteuses et des motifs intéressants conduisant à des meilleures solutions. Nous proposons trois approches de résolution combinées à des stratégies d'apprentissage adaptées pour les trois classes de COPs considérés.Nous développons une recherche locale combinée à un apprentissage de probabilités pour les problèmes de groupement comme GCP, une recherche mémétique avec apprentissage par opposition pour MDP et une recherche exploitant des motifs fréquents pour QAP. Toutes les approches proposées ont été validées expérimentalement sur des instances benchmark, et les résultats obtenus montrent quelles sont compétitives par rapport aux méthodes de l’état de l’art.