Les problèmes d’optimisation combinatoire de grandes tailles sont en général difficiles à résoudre de façon optimale due à des temps de calcul trop élevés. Afin de pallier ce problème, des algorithmes d’approximation tels que les heuristiques et les métaheuristiques sont utilisés pour trouver rapidement des solutions approchées de bonne qualité. Les heuristiques sont des approches développées spécifiquement pour un problème et permettent d’obtenir des solutions très rapidement. Les métaheuristiques sont des approches génériques, indépendantes du problème, permettant de trouver des solutions de bonne qualité. Ces approches présentent chacune leurs avantages et inconvénients. Nous proposons dans ces travaux de tirer parti des avantages de ces deux approches, c’est-à-dire intégrer des connaissances spécifiques à un problème, telles que celles utilisées dans les heuristiques, dans les mécanismes génériques des métaheuristiques, afin de concevoir des nouvelles approches efficaces. Ainsi, dans ces travaux, nous passons d’abord en revue dans la littérature les approches avec intégration de connaissances afin de proposer une taxonomie de classification de ces approches. Puis nous nous focalisons sur l’intégration de connaissances pour deux problèmes différents : le problème d’ordonnancement de type Flowshop sans temps d’attente, et le problème de sélection d’attributs en classification. Enfin, nous étudions dans ces problèmes l’impact de l’intégration de connaissances dans différents mécanismes des métaheuristiques : l’initialisation, l’opérateur de voisinage et la sélection du voisinage.
- Nicolas JOZEFOWIEZ, Professeur des Universités, Université de Lorraine (Rapporteur) - Adrien GOEFFON, Maître de conférences, HDR, Université d’Angers (Rapporteur) - Sophie TISON, Professeur des Universités, Université de Lille (Examinatrice) - Lhassane IDOUMGHAR, Professeur des Universités, Université de Haute Alsace (Examinateur) - Marie-Eléonore KESSACI, Maître de conférences, Université de Lille (Co-encadrante) - Clarisse DHAENENS, Professeur des Universités, Université de Lille (Directrice de thèse)
Thesis of the team ORKAD defended on 28/11/2018
français
English