Program > By author > Lamrous Sid

Wednesday 26
Decision theory, game theory and multi-criteria optimisation
Laurent Moalic
› 12:00 - 12:30 (30min)
› Bât. B - TD 44
Optimisation combinatoire multi-objectif : gestion de la diversification pour une meilleure intensification
Laurent Moalic  1@  , Sid Lamrous  1@  , Alexandre Caminada  1@  
1 : Laboratoire Systèmes et Transports  (IRTES - SET)  -  Website
Institut de Recherche sur les Transports, l'Energie et la Société - IRTES, Université de Technologie de Belfort-Montbeliard
90010 Belfort cedex -  France

De nombreux problèmes réels nécessitent d'optimiser plusieurs objectifs, souvent en conflit les uns avec les autres. Cette famille de problèmes appelés multi-objectifs (MOP) n'admet pas une solution unique mais un ensemble de solutions de compromis dit non-dominé. Les algorithmes multi-objectifs visent à construire les solutions se rapprochant au mieux de l'ensemble Pareto optimal, ensemble qui domine l'espace de recherche.

L'hybridation de plusieurs métaheuristiques pour résoudre les MOP s'est particulièrement développée ses dernières années. Parmi les algorithmes les plus performants figurent les approches mémétiques, hybridant recherches locales et algorithmes génétiques. L'algorithme MEMO que nous présentons repose sur une recherche locale basée sur une descente simple et sur l'algorithme génétique NSGA-II.

Un des éléments les plus délicats à aborder est l'équilibre entre intensification (meilleures exploitation d'une solution) et diversification (meilleure exploration de l'espace de recherche). Différents composants d'un algorithme mémétique permettent d'agir tant sur la diversification que sur l'intensification. Ainsi par exemple, le croisement de deux solutions tend à fournir plus de diversité alors que la recherche locale tend à fournir une meilleure intensification. Mais cette tendance peut toutefois être modulée selon le croisement choisi ou la recherche locale.

Nous proposons ici une étude détaillée de l'influence de cet équilibre entre intensification et diversification sur la qualité de l'ensemble des solutions non-dominées trouvées par MEMO. Le cas d'étude retenu est le problème de localisation de stations d'auto-partage électrique, modéliser sous forme d'un problème à trois objectifs. De plus, les résultats obtenus par l'algorithme MEMO sont comparés aux résultats obtenus avec les approches génétiques et locales seules. Il s'est révélé être particulièrement performant.

Pour plus de détail sur l'algorithme et le problème de localisation de stations d'auto-partage :
http://dl.acm.org/citation.cfm?id=2464627&dl=ACM&coll=DL&CFID=381215587&CFTOKEN=78886318


Online user: 1