• Langue : Français
• Discipline : Informatique
• Identifiant : Inconnu
• Type de mémoire : Habilitation à diriger des recherches
• Date de soutenance : 01/01/2005

Résumé en langue originale

L'optimisation combinatoire regroupe une large classe de problèmes ayant des applications dans de nombreux domaines de l'industrie et des services. La plupart de ces problèmes sont de nature multi-objectif puisque différents critères sont à considérer simultanément. L'optimisation combinatoire multi-objectif traite donc de ces problèmes et représente un domaine de recherche plein de challenges. La particularité de ce domaine est l'existence d'un ensemble de solutions optimales, appelées solutions de meilleurs compromis entre les critères. Le manuscrit traite de la recherche efficace de cet ensemble de solutions de compromis pour des problèmes de forte complexité (problèmes NP-difficiles). Pour cela, le premier chapitre pose le cadre de travail en mettant en évidence les problématiques particulières liées à l'optimisation multi-objectif. Puis, une première partie est consacrée à la coopération de méthodes en vue d'améliorer leur efficacité. Cette partie utilise un problème d'ordonnancement, un problème de flowshop biobjectif, à titre d'exemple. Un chapitre est dédié à la proposition d'une nouvelle méthode exacte pour des problèmes à deux objectifs. Cette méthode est validée sur le problème du flowshop. Puis le chapitre suivant s'intéresse à la résolution heuristique du problème avec, en particulier, la coopération entre méthodes heuristiques et la méthode exacte. Des expérimentations sont présentées. Une deuxième partie est consacrée à un autre domaine d'application : l'extraction de connaissances. En effet, de nombreux problèmes d'extraction de connaissances peuvent être modélisés en des problèmes d'optimisation combinatoire. Dans un premier chapitre, nous montrons l'apport des modélisations multi-objectifs pour ces types de problèmes. Puis une étude plus approfondie est réalisée sur la problématique de recherche de règles d'association. Pour ce problème, nous exposons une modélisation multi-objectif ainsi que des méthodes de résolution développées. Le chapitre suivant présente deux approches coopératives : une approche coopérative parallèle, mettant en jeux plusieurs métaheuristiques et une coopération avec une méthode exacte. Enfin le dernier chapitre donne des indications sur le contexte applicatif, à savoir l'étude de données issues de la bioinformatique. Les conclusions et perspectives présentées au cours des chapitres sont récapitulées. Pour n'en citer que trois, les conclusions montrent que des efforts restent à faire en terme de coopération de méthodes, où en général, les schémas proposés sont rarement originaux. De plus dans le contexte de la résolution exacte en multi-objectif, des améliorations peuvent encore être réalisées, notamment avec une utilisation plus intensive du parallélisme. Enfin, concernant l'optimisation multi-objectif dans son contexte d'application, le décideur a une place très importante qui est souvent oubliée dans le processus d'optimisation. Plus d'interactions avec le décideur permettrait d'orienter les recherches et donc de les rendre plus efficaces.