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
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Decision theory, game theory and multi-criteria optimisation |
| Keywords | : | Optimisation combinatoire ; Algorithmes mémétiques ; Problèmes multi ; objectifs ; Auto ; partage |
| PDF version | : |  PDF version |
