Algorithmes mémétiques et optimisation multiob jectif

Algorithmes mémétiques et optimisation multiob jectif

Ce chapitre est consacré à l’élaboration d’une métaheuristique multiobjectif hybride. Elle a été expérimentée sur un problème réel de localisation de stations pour un service d’auto-partage.Dans un premier temps, une présentation des caractéristiques propres aux algorithmes mémétiques est faite. Ensuite, nous détaillons l’élaboration et le fonctionnementde l’algorithme proposé MEMO. La troisième partie de ce chapitre traite d’un cas d’étude : la localisation de stations d’auto-partage. Dans cette partie est présentéle problème, ainsi que sa modélisation sous la forme d’un problème multiobjectif.La partie suivante fournit une analyse comparative détaillée entre les approches de référence NSGA-II, PLS et FLSMO, et l’algorithme MEMO. Enfin une dernière partie aborde le problème de l’aide à la décision en contexte multiobjectif, avec la proposition de la plate-forme logicielle geoLogic. Après avoir présenté un état de l’art des approches permettant de résoudre des problèmes multiobjectifs (Multiobjective Optimization Problem – MOP), puis la façon de modéliser la manière dont les personnes se déplacent sur un territoire, nous nous attachons dans ce chapitre à définir une heuristique de type mémétique pour résoudre des problèmes multiobjectifs. Le cas d’étude retenu ici est la localisation de stations pour un service d’auto-partage, problème mêlant modélisation de la mobilité et optimisation.

Parmi les nombreuses difficultés que posent les MOP, une des principales est liée au fait que cette classe de problèmes donne lieu à une variété de solutions. En effet, il existe rarement une solution optimale unique, qui soit la meilleure sur tous les objectifs. Le résultat est donc un ensemble de solutions, dites de meilleur compromis. Dès lors il apparait indispensable de distinguer deux étapes dans la résolution d’un MOP : la construction de l’ensemble des solutions non-dominées (processus d’optimisation multicritère) puis le choix de la solution à retenir (processus d’aide à la décision multicritère). Dans ce chapitre nous nous focaliserons dans un premier temps sur la construction de l’ensemble Pareto [Coello 2004], ensemble qui a pour image dans l’espace des critères le front de Pareto (Pareto Front – FP). La façon d’aider le décideur à choisir la solution à implémenter fait l’objet de la fin de ce chapitre.Les approches de type hybride tel que les algorithmes mémétiques ont déjà faitleurs preuves dans le domaine mono-objectif en permettant de résoudre de nombreux problèmes. Le concept même de mémétique fut introduit par Pablo Moscato [Moscato 1989] pour parler d’une heuristique à base de population incluant une recherche locale.Parmi les problèmes où l’approche mémétique fournit de très bon résultats, on citera l’exemple du problème académique de coloriage de graphe, connu pour être très difficile, et qui est résolu avec de très bonnes performances [Galinier 2013].

Les résultats obtenus par les approches mémétiques en mono-objectif ont incité les chercheurs à transposer ce mécanisme d’hybridation au contexte multiobjectif [Talbi 2001][Jaszkiewicz 2002]. Le mécanisme consistant à introduire une recherche locale dans un algorithme génétique (AG) est alors généralement utilisé pour accélérer le déroulement de l’algorithme, mais pas uniquement. L’hybridation joue également un rôle dans la façon d’explorer l’espace de recherche ; le but étant de fournir denouvelles propriétés permettant d’améliorer l’ensemble des solutions trouvées. En effet les AG utilisés seuls ont souvent tendance à faire progresser la population dans certaines régions de l’espace de recherche, ce qui a pour conséquence de créer des clusters. L’introduction de la recherche locale permet quant à elle de se focaliser sur une direction, souvent choisie vers le front de Pareto (meilleure intensification), mais parfois aussi de façon à obtenir une meilleure répartition sur le font de Pareto (meilleure diversification). La recherche locale dans un AG permet ainsi de guider la progression de la population pour garantir les propriétés souhaitées. Dès lors que sont hybridées deux métaheuristiques, recherche locale et algorithme génétique, connues pour être très performantes toutes les deux, se pose la question de l’apport de chacune d’elles. Aussi nous nous intéresserons également dans ce chapitre à identifier si, à travers l’hybridation, l’algorithme mémétique bénéficie des avantages de chaque métaheuristique, ou si de nouvelles propriétés sont engendrées.Nous présenterons tout d’abord le principe fondateur des algorithmes mémétiques. Dans une deuxième partie, l’algorithme hybride MEMO que nous proposons sera détaillé. Ensuite nous introduirons le problème auquel nous avons appliqué l’algorithme MEMO, un problème de localisation de stations pour un service d’auto-partagede type autoLib’. La section suivante sera consacrée à une comparaison entre les résultats obtenus avec l’approche hybride et les résultats issus de métaheuristiques pures, que ce soit des approches génétiques ou des recherches locales. Enfin, une dernière partie introduira le problème de l’aide à la décision dans un contexte multiobjectif, avec une présentation de la plate-forme geoLogic.