Apprentissage Automatique et Résolution Pratique des Problèmes NP-Difficiles

Les problèmes NP-difficiles se trouvent dans beaucoup d'applications industrielles et académiques et il faut apporter des solutions à ces problèmes malgré la NP-difficulté. Il y actuellement deux types d'algorithmes dans la résolution pratique de ces problèmes: algorithmes heuristiques ou méta-heuristiques et algorithmes complets ou exacts. Un point en common de ces algorithmes est qu'ils ont en général besoin de prendre des décisions à chaque étape de la résolution. Beaucoup d'effort ont été faits dans la littérature pour améliorer la pertinence de ces décisions qui est cruciale pour la performance pratique de ces algorithmes. Mais assurer les meilleures décisions à chaque étape de la résolution pourrait être aussi difficile que le problème lui-même.

L'apprentissage automatique est un outil puissant de l'intelligence artificielle qui a fait ses preuves dans beaucoup de domaines, permettant par exemple à un programme de battre les meilleurs joueurs du jeu de GO humains. Une tendance apparaît ainsi dans la littérature pour utiliser l'apprentissage automatique pour aider les algorithmes des problèmes NP-difficiles à prendre et améliorer des décisions à chaque étape de la résolution.

L'objectif de ce cour est d'enseigner le principe d'application de l'apprentissage automatique pour améliorer les algorithmes des problèmes NP-difficile. Le contenu du cours est le suivant:

- Problèmes NP-difficiles et leur application
- Algorithmes existants des problèmes NP-difficiles
- Principe de l'apprentissage automatique et de l'apprentissage par renforcement en particulier
- Intégration de l'apprentissage automatique dans les algorithmes des problèmes NP-difficiles
- Etude de cas