Réunion ATOM du vendredi 27 juin 2014

La prochaine réunion du groupe ATOM (Application et Théorie de l'Optimisation Multiobjectif) groupe de travail du GDR RO transversal au pôle Décision/Evaluation/Modélisation et au pôle Fondements de l'Optimisation soutenu par la ROADEF <http://www.roadef.org/> aura lieu le vendredi 27 juin à l'Université Pierre et Marie Curie (sur le site de Jussieu), salle Noguez numéro 101, tour 26-00.

Voici le programme de la journée :

9h30 Accueil

10h Présentation invitée : DHAENENS Clarisse - Université Lille 1 - "Big Data : de nouveaux challenges pour l'optimisation multi-objectif ?"

Big Data?
Derrière ce mot clé différents verrous scientifiques. L'un d'entre eux concerne la capacité à extraire de la connaissance de grandes bases de données.
Or l'utilisation de méthodes d'optimisation combinatoire et plus généralement de la recherche opérationnelle pour la résolution efficace de problèmes d'extraction de connaissances est maintenant reconnue. En particulier, différentes modélisations de ces prob! lèmes et des résolutions par métaheuristiques ont été proposées pour la résolution de problèmes de grandes tailles.
Dans cette présentation nous nous focaliserons sur l'apport du multi-objectif pour une modélisation pertinente de ces problèmes. Aussi, après avoir présenté les enjeux des problèmes d'extraction de connaissances, nous nous focaliserons sur 2 tâches particulières : la recherche de règles d'association, et le clustering. Pour chacune de ces tâches nous discuterons de leur modélisation en problèmes d’optimisation et verrons l’apport du multi-objectif.

11h GUENOCHE Alain - Institut de Mathématiques de Marseille - CNRS - "Factorization of a tournament for the median linear order problem"

Le problème de la construction d'un ordre médian dans un ensemble d'ordres totaux (de taille n) se pose généralement dans le cadre de la théeorie du choix social (vote) ou de l'agrégation des préférences. De façon générale, il s'agit de construire un ordre consensus à partir d'un ensemble d'ordres donné. Le problème se modélise à l'aide d'un tournoi (graphe complet orienté à n sommets) dont les arcs correspondent aux préférences majoritaires. Construire un ordre total dont l'écart au tournoi est minimum, revient à le rendre transitif par un nombre minimum d'opérations de retournement d'arcs. Le calcul s'effectue par une méthode de Branch and Bound qui devient inapplicable dès que n atteint quelques dizaines. Dans ce texte nous abordons la question de la décomposition d'un tournoi de grande taille en sous-tournois plus facilement traitables et de la composition des ordres obtenus sur chaque sous-tournoi en un ordre unique. Nous montrons, à l'aide de simulations sur des tournois aléatoires, que cette stratégie de décomposition est efficace.

11h45 BLOT Aymeric - ENS/INRIA Lille Nord Europe - "Analyse de paysage et algorithmes de recherche locale en multi-objectif"

Metaheuristics, and in particular local search approaches, dedicated to multi-objective combinatorial optimization use successive local
improvement moves to identify a set of non-dominated solutions. This work investigates the use of one characteristic of the fitness
landscape, the neutrality, for directing the choice of moves in order to improve the general behavior of the algorithms. After presenting a
multi-objective neutrality concept, several propositions are made to include this characteristic in the conception of multi-objective local
search algorithms. Experiments conducted show that exploiting this neutrality allows to improve performance of the methods.

12h30 Repas

14h DUBOIS-LACOSTE Jérémie - IRIDIA/ULB Belgique - "Optimisation combinatoire "anytime" et configuration automatique avec des algorithmes multi-objectifs hybrides"

Deux paradigmes différents sous-tendent la majorité des algorithmes d'optimisation combinatoire multi-objectif (au sens de Pareto). Le premier est de scalariser le problème initial en une série de problèmes mono-objectif et de résoudre ces différents problèmes successivement. Le second est de compter uniquement sur la relation de Pareto dominance entre solutions, c'est le cas par exemple des algorithms évolutionnaires basés sur une population de solutions. L'hybridization de ces deux paradigmes a depuis quelque années permis d'améliorer l'état de l'art pour des problèmes bien connus comme le Traveling Salesman Problem ou le Permutation Flowshop Scheduling Problem.
Dans ma présentation, portant sur de tels algorithmes hybrides, j'expliquerai un nouvel aspect rarement considéré pour l'optimisation, qui plus est multi-objectif: l'aspect "anytime". Un algorithme anytime cherche à atteindre la meilleure qualité possible à chaque instant de l'exécution, et pas seulement après un temps ou un nombre d'itérations prédéfini. Cet aspect est très utile pour les applications ou le temps alloué à l'algorithme n'est pas connu en avance, ou bien varie à chaque exécution. Je démontrerai également l'intérêt des méthodes de configuration automatique pour le design d'algorithmes multi-objectif, aussi bien pour optimiser "classiquement" la qualité obtenue après un temps donné, que pour l'aspect anytime.

14h45 WANG Weijia - TAO INRIA - "Hypervolume indicator and Dominance reward based Multi-objective Monte-Carlo Tree Search"

This paper is concerned with multi-objective sequential decision making (MOSDM). The motivation is twofold. On the one hand, many decision problems in the domains of e.g., robotics, scheduling or games, involve the optimization of sequences of decisions. On the other hand, many real-world applications are most naturally formulated in terms of multi-objective optimization (MOO).
The proposed approach extends the well-known Monte-Carlo tree search (MCTS) framework to the MOO setting, with the goal of discovering several optimal sequences of decisions through growing a single search tree. The main challenge is to propose a new reward, able to guide the exploration of the tree although the MOO setting does not enforce a total order among solutions.
The main contribution of the work is to propose and experimentally study two such rewards, inspired from the MOO literature and assessing a solution with respect to the archive of previous solutions (Pareto archive): the hypervolume indicator and the Pareto dominance reward.
The study shows the complementarity of these two criteria. The hypervolume indicator suffers from its known computational complexity; however the proposed extension thereof provides fine-grained information about the quality of solutions with respect to the current archive. Quite the contrary, the Pareto-dominance reward is linear but it provides increasingly rare information.
Proofs of principle of the approach are given on artificial problems and challenges, and confirm the merits of the approach. In particular, MOMCTS is able to discover policies lying in non-convex regions of the Pareto front, contrasting with the state of the art: existing Multi-Objective Reinforcement Learning algorithms are based on linear-scalarization and thus fail to sample such non-convex regions.
Finally MOMCTS honorably competes with the state of the art on the 2013 MOPTSP competition.

15h30-15h45 : Pause

15h45 MBAYA Abir - NESSYN - "Approximate Graph Matching Through Multiobjective Optimization"

Le travail que je vais présenter proposera une nouvelle approche de classification de graphes basée sur une nouvelle méthode approximative de comparaison des graphes, associée à l’algorithme génétique NSGA II. L'idée clé de la nouvelle méthode consiste à effectuer la comparaison sur des graphes plus simples tout en gardant la structure des graphes originaux afin de réduire la complexité et par conséquent le temps d’exécution. Tout d'abord, je vais présenter et évaluer la nouvelle solution qui évalue la similitude entre des graphes larges dans un temps polynomial. Cette approche est basée sur la décomposition modulaire et des graphes plus simples appelés primaires. Ainsi, la classification des grands graphes revient à une classification des graphes primaires qui sont obtenus après l’exécution de la décomposition modulaire sur les graphes originaux. Par la suite, nous introduisons NSGA II, qui est un algorithme génétique rapide et élitiste, afin d’améliorer la qualité de la classification. Les valeurs qui doivent être optimisées sont le taux de reconnaissance et le taux de confusion. Je présenterais et discuterais ensuite les résultats de mes expérimentations.

16h15 YASSA Sonia - LARIS - "Ordonnancement multiobjectif de workflows dans les environnements de cloud computing"

Le Cloud Computing est de plus en plus reconnu comme une nouvelle façon d'utiliser, à la demande, les services de calcul, de stockage et de réseau d’une manière transparente et efficace. Dans cette présentation, nous abordons le problème d'ordonnancement de workflows dans les environnements du Cloud Computing. Les approches d’ordonnancement de workflows existantes se concentrent principalement sur l'optimisation biobjectif du makespan et du coût sans prendre en compte d’autres métriques telles que la fiabilité, l’énergie et autre. Dans cette présentation, nous proposons des algorithmes d’ordonnancement de workflows basés sur des métaheuristiques qui optimisent plusieurs métriques de QoS simultanément. Les résultats des simulations soulignent la bonne performance de nos approches d’ordonnancement multiobjectif.

16h45 Discussions

Plus d'informations sont disponibles sur le site du groupe <http://www.lifl.fr/ATOM>

Il est encore possible d'assister aux présentations, pour cela, merci de vous inscrire sur le site :
https://docs.google.com/forms/d/1oPbfnDnqf3CLeS17OymP6xlwm4hQliWo3qSZSsPL8jI/viewform

Les coordinateurs du groupe ATOM,
Matthieu Basseur (matthieu.basseur_at_info.univ-angers.fr)
Laetitia Jourdan (laetitia.jourdan_at_lifl.fr)
Thibaut Lust (thibaut.lust_at_lip6.fr)

ps : pour s'abonner à la liste ATOM, écrire à sympa@inria.fr avec le sujet : subscribe atom Prénom Nom