Equipe 3: Optimisation combinatoire multi-objectif

Les problèmes d'optimisation multi-objectifs sont présents dans divers domaines tels que les télécommunications, la biologie, la physique, la chimie, les finances, les systèmes embarqués, etc. Résoudre ces problèmes consiste à trouver des solutions de compromis qui optimisent plusieurs objectifs généralement contradictoires. Dans le domaine des systèmes embarqués, par exemple, un des problèmes d'optimisation multi-objectifs posés est de trouver un mapping de tâches aux processeurs qui minimise à la fois le temps d'exécution et la consommation d'énergie.

Pour optimiser ces problèmes, deux classes de méthodes existent: les méthodes exactes (le branch-and-bound, la programmation dynamique, etc.) et les métaheuristiques (les méthodes de recherche locale, les algorithmes évolutionnaires, etc.) Les méthodes exactes retournent les solutions optimales mais ne sont applicables qu'à des instances de petite taille et/ou un nombre réduit d'objectifs car les délais de traitement croient exponentiellement avec la taille du problème et le nombre d'objectifs. Les métaheuristiques, par contre, retournent des solutions dans des délais raisonnables mais sans preuve d'optimalité.

Les méthodes d'optimisation doivent présenter un bon compromis entre le temps d'exécution et la qualité des solutions. Ceci nécessite, en général, la coopération (l'hybridation) de plusieurs méthodes de résolution présentant les propriétés diversification/intensification complémentaires. Cette coopération peut faire intervenir des métaheuristiques uniquement (coopération d'un algorithme évolutif avec une recherche locale, par exemple) ou des méthodes exactes avec les métaheuristiques (par exemple, améliorer la borne d'un problème avec une recherche locale avant de démarrer une recherche arborescente). Les méthodes qui en résultent sont gourmandes en temps de calcul importants et nécessitent l'utilisation des moyens de calcul de haute performance.

    Email : lapeci@univ-oran.dz. Téléphone : 0770 31 42 55. Fax : 041 29 02 65.