Laboratoire de Génie Informatique et d’Automatique de l’Artois

Séminaire

Hybridation de métaheuristiques pour la résolution distribuée de problèmes d’optimisation spatialisés

Le 12 octobre 2010 à 14h00 Salle des séminaires du LGI2A, FSA, Béthune
Jean-Charles CREPUT --- Universite de Technologie de Belfort Montbeliard (UTBM)

Les problèmes d’optimisation spatialisés font intervenir des entités (clients, demandes, trafic) réparties sur une étendue (la donnée) et des dispositifs physiques (antennes, véhicules) qui doivent leur être associés de manière optimale. Pour résoudre ce type de problème, nous nous intéressons aux algorithmes à structure intermédiaire, aux recherches locales et aux approches de résolution collective selon des métaphores de systèmes naturels et biologiques. Le but est par exemple de prendre en compte dès le départ la potentialité d’application à des problèmes dynamiques et stochastiques, de fournir un canevas à la mise en ouvre distribuée possible des algorithmes, et de résoudre des problèmes de grandes tailles. La résolution du problème résulte de la multiplicité d’opérations élémentaires locales réparties dans le plan et d’une dynamique de plus haut-niveau exprimée dans un schéma d’heuristique à base de population de solutions. Également, nous proposons des approches de résolution collective de problème. Par exemple, nous procédons à une relecture des méthodes de recherche locale à voisinage variable dans le cadre des systèmes multi-agents. Des mécanismes d’apprentissage des choix d’opérateurs sont introduits dans des agents de recherche autonomes et en coopération dans un contexte d’exécution asynchrone et décentralisé. Ces approches de résolution heuristiques sont appliquées à des problèmes d’optimisation (NP-hard) statiques et dynamiques des réseaux de communication cellulaires et des transports terrestres et évaluées en comparaison avec les heuristiques puissantes et récentes de la recherche opérationnelle.