Aller au contenuAller au menuAller à la rechercheAller à la page d'actualités

Soutenance de thèse | Yangming ZHOU - Université Angers

Soutenance de thèse | Yangming ZHOU

  • Partager la page sur les réseaux sociaux
  • Envoyer cette page par mail

    Envoyer par mail


    Séparés par des virgules
  • Imprimer cette page

Soutenance de thèse de Monsieur Yangming ZHOU

14h00 | Faculté des Sciences | AMPHI L003 | 2, boulevard Lavoisier | ANGERS

Le 15 décembre 2017

Sujet : Approches de résolution renforcées par des méthodes d’apprentissage en optimisation combinatoire

Directeur de thèse : Monsieur Jin-Kao HAO

RÉSUMÉ

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 COPSs, les problèmes de groupement comme le problème de coloration de graphe (GCP), les problèmes de sélection de sous-ensembles comme le problème de diversité maximum (MDP) et les problèmes de permutation comme le problème d’assignation quadratique (QAP). Ces trois classes de problèmes ont de nombreuses applications pratiques, mais ils sont dans le cas général NP-difficiles. Cette thèse s’attache à proposer des méthodes de résolutions 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 heuristique combinées à des stratégies d’apprentissage adaptées pour les trois classes de COPs considérés. Nous avons développé une recherche locale combinée à un apprentissage de probabilités pour les problèmes de goupement 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 qu’elles sont aussi ou plus performantes que les meilleures méthodes de l’état de l’art. Nos expérimentations mettent également en évidence l’apport des techniques d’apprentissage pour les résolutions heuristiques.