Stage Recherche M2 2013-2014


Sujet

Framework Générique et Parallèle pour
l'Optimisation Scalaire Multiobjectif


Équipe Dolphin INRIA Lille Nord Europe, LIFL, Université Lille 1

Durée : 6 mois

Contexte/Problématique

Un problème d'optimisation multi-objectif consiste à optimiser non pas une seule fonction de coût; mais plusieurs fonctions de coûts (les objectifs) de façon simultanée. Cependant, les objectifs sont en général contradictoires/conflictuels de telle sorte que résoudre un problème multi-objectif consiste à trouver un ensemble de solutions permettant d'avoir différents compromis par rapport aux différents objectifs. Trouver un tel ensemble (appelé aussi Front Pareto) est une tâche difficile, largement étudiée et pour laquelle plusieurs approches existent dans la littérature, e.g. [3].

Dans ce travail on s'intéresse à un type d'approches qui se basent sur l'agrégation des objectifs et utilisant plusieurs fonctions scalaires pour calculer un ensemble de bonne qualité, e.g. [1,2]. Ces méthodes, relativement récentes, suscitent un intérêt grandissant dans la communauté. En particulier, elles offrent l'avantage d'être simples, effectives et computationnellement efficace par rapport à d'autres approches classiques établies depuis plus longtemps. Cependant, de part la complexité des problèmes d'optimisation considérés, et la difficulté du processus d'optimisation, plusieurs questions restent ouverte quant à la possibilité d'affiner ces méthodes et de les étendre.

Dans ce contexte, les calculs distribués offre une alternative particulièreremnt intéressante [4] et non encore complètement explorée. En effet, les calculs sous-jacent à ces approches présentent à priori certains degrés d'indépendances; ce qui suggère que leur déploiement sur des plate-formes distribués large échelle pourrait être effective. Quelques tentatives existent bel bien dans cette direction. Cependant, ces tentatives ont révélé que, même si un gain en temps de calcul peut être obtenu, le processus de distribution des calculs peut avoir un impact négatif sur la qualité du processus d'optimisation et peut détériorer la qualité de l'ensemble de solutions en comparaison à un modèle séquentiel. On remarque aussi que la plus part de ces tentatives essayent de rester le plus possible fidèle aux versions séquentielles existantes et ne cherche pas à proposer des nouveaux modèles de distribution.

Au delà de l'aspect purement parallèle, les approches scalaires offrent un degré de localité qui pourraient s'avérer extrêment utile pour adapter le processus d'optimisation en fonction des problèmes ou des instances considérés. Notre objectif est d'exploiter cette localité pour améliorer la robustesse de ces méthodes face au large panel de problèmes d'optimisation auxquelles on est confronté tout en gardant leur nature parallélisabe et distribuable à large échelle.


Réalisation

Dans ce travail, il s'agit de réfléchir à la conception d'un framework d'algorithmes parallèles scalaires efficaces pour l'optimisation multi-objectif. La méthodologie que l'on souhaite adopter est de s'inspirer des méthodes existantes pour concevoir de nouveaux algorithmes qui (i) peuvent être déployés de façon efficace, et (ii) qui préservent la qualité du processus d'optimisation. Autrement dit, il ne s'agit pas de 'simplement' paralléliser les approches existantes en fonction des problèmes d'optimisation considérés; mais de proposer de nouvelles stratégies génériques qui sont par essence distribuable sur un grand nombre de processus.

La réalisation des objectifs précedents est une tâche complexe qui englobe plusieurs niveaux de difficulités:
  1. Au niveau algorithmique, les approches scalaires existantes peuvent être améliorées selon différentes perspectives. L'aspect local et parallèle lors de la conception de ces appraoches, ainsi que l'adaptation du processus d'optimisation sont des ingrédients cruciaux à ce niveau.

  2. Au niveau généricité, les méthodes à developper devront se détacher des problèmes finaux à resoudre. Pour cela on s'interessera à une conception qui prend en compte une représentation haut niveau (binaire, permutation, etc) sans être tributaire d'un problème particulier.

  3. Au niveau des problèmes d'optimisation considérées, on souhaite à long terme pouvoir étudier la performance des algorithmes developpés sur un large panel de problèmes, e.g., Knapsack, Flowshop, etc. Le but ici est d'analyser la qualité des algorithmes proposés pour pouvoir mieux cerner leurs dynamiques et leurs propriétés; permettant ainsi d'améliorer leurs conceptions.

Ces différents niveaux seront considérés de façon incrémentale au cours du stage. D'un point de vue pédadagogique, l'étudiant devra les assimiler, en comprendre les enjeux, et proposer les bases d'une solution péreine à long terme.



Bibliographie
  1. E. J. Hughes. Multiple Single Objective Pareto Sampling. In Congress on Evolutionary Computation (CEC), pages 2678–2684. 2003.
  2. Q. Zhang and H. Li. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decom- position. IEEE Transactions on Evolutionary Computation, 11(6), pages 712–731, 2007.
  3. T. Wagner, N. Beume, B. Naujoks. Pareto-, Aggregation-, and Indicator-based Methods in Many-objective Optimization. Conference on Evolutionary Multi-Criterion Optimization (EMO). pp. 742–756. Springer 2007.
  4. Van Veldhuizen, D. A., Zydallis, J. B., Lamont, G. B., 2003. Considerations in engineering parallel multiobjective evolutionary algorithms. IEEE Transactions on Evolutionary Computation 7 (2), 144–173.
Contacts et informations supplémentaires: