MOCAD — OC

Optimisation combinatoire multi-objectif

Arnaud Liefooghe


Cours

  • Séance du lundi 09 novembre 2020 : Introduction à l'optimisation combinatoire multi-objectif [ slides ]
  • Séance du lundi 16 novembre 2020 : Métaheuristiques pour l'optimisation combinatoire multi-objectif [ slides ]
  • Séance du lundi 23 novembre 2020 : Analyse expérimentale de métaheuristiques [ slides ]
  • Lundi 14 décembre 2020 : rendu du projet (dépôt Git + rapport) par e-mail


Projet

Présentation générale du projet

Le but du projet est de développer des solutions algorithmiques pour approcher l’ensemble Pareto du TSP multi-objectif.

Le cheminement général du projet est le suivant :

  1. Lire les instances du problème, et savoir évaluer une solution (pour tous les objectifs)
  2. Filtrer les solutions dominées (off-line et on-line)
  3. Proposer au moins deux approches pour la résolution du problème avec deux objectifs (une approche de type scalaire et une approche de type Pareto)
  4. Bonus : Proposer une approche pour la résolution du problème à plus de deux objectifs et/ou proposer une approche hybridant plusieurs algorithmes
  5. Évaluer et analyse la performance de vos algorithmes
  6. Rapport expliquant les choix que vous avez effectués, les problèmes que vous avez rencontrés, et présentant les approches que vous avez développées ainsi que vos résultats

Planning prédictif :

  • Séance du lundi 09 novembre 2020 : lecture des instances et développement de filtres
  • Séance du lundi 16 novembre 2020 : choix et développement des algorithmes
  • Séance du lundi 23 novembre 2020 : fin du développement des algorithmes et évaluation des performances
  • En parallèle : expérimentations et rédaction du rapport
  • Rapport et dépôt Git à rendre par e-mail lundi 14 décembre 2020


1. TSP multi-objectif

Le TSP (problème du voyageur de commerce, ou travelling salesman problem) est un problème classique de l’optimisation combinatoire. Étant donné un ensemble de villes, il s’agit de trouver le chemin ‘optimal’ qui relie toutes les villes, sans passer plus d’une fois par la même. L’optimalité se rapporte généralement à une distance parcourue. Dans sa variante mono-objectif, le TSP est connu comme un problème NP-difficile : on ne connait pas d'algorithme permettant de trouver une solution exacte en un temps polynomial. Néanmoins, de nombreuses applications réelles se résument en un problème de TSP, ou se doivent de résoudre le TSP comme sous-problème.

Dans sa variante multi-objectif, le mTSP (multi-objective TSP, avec m objectifs) vise non seulement à minimiser la distance totale, mais également le temps total, le coût total, etc. Par conséquent, il est supposé que plusieurs quantités, telles que la distance, le temps et le coût, sont affectées à chaque paire de villes.

Plus formellement, le mTSP peut être défini par un graphe complet G = (V,E), où V = {v1,v2,...,vn} est un ensemble de noeuds (les villes) et E = {[vi,vj], vi,vj ∈ V} est un ensemble d’arcs. À chaque arc [vi,vj] ∈ E est affecté un coût positif ck(i,j) par fonction objectif k ∈ {1,...,m}. À chaque objectif correspond donc une matrice de coûts. Le but est de trouver l’ensemble des permutations cycliques simples π de taille n qui sont Pareto optimales pour {f1,f2,...,fm}, avec :

fk(π) = ∑ ck(π(i),π(i+1)) + ck(π(n),π(1))

Dans le cas général, le mTSP est NP-difficile, et la taille de l’ensemble Pareto optimal croit exponentiellement avec la taille du problème (le nombre de noeuds n).


2. Instances

Les instances que nous allons utiliser proviennent de la page web de L. Paquete (instances de type aléatoires, à 100 villes). Un fichier d’instance contient les valeurs pour un seul type de coût entre chaque paire de noeuds (un fichier = une matrice de coûts = un objectif). Il faut donc lire autant de fichiers d’instance que d’objectifs que l’on veut prendre en compte.

Nous nous intéressons aux 6 fichiers d’instances suivants (les fichiers correspondants sont disponibles en bas de page) :

À partir de ces fichiers, nous nous intéressons particulièrement aux 3 instances de mTSP à deux objectifs (m=2) suivantes :

  • randomAB100 (objectif 1 : randomA100.tsp, objectif 2 : randomB100.tsp)
  • randomCD100 (objectif 1 : randomC100.tsp, objectif 2 : randomD100.tsp)
  • randomEF100 (objectif 1 : randomE100.tsp, objectif 2 : randomF100.tsp)

Les meilleurs fronts connus correspondant à ces instances :

Remarque : Pour les instances à trois objectifs, nous allons considérer randomABC100 et randomDEF100 (pas de meilleurs fronts connus... pour le moment).

Afin de charger la matrice de coûts associée à un fichier d’instance, il faut lire les coûts entre chaque paire de noeuds. Attention, les instances sont de type symétrique : ck(vi,vj) = ck(vj,vi). Le fichier contient la matrice sous forme triangulaire, les données sont donc du type :

c(1,1) = 0

c(1,2)

c(1,3)

...

c(1,n)

c(2,2) = 0

...

c(n,n) = 0

À faire :

  • Lire les fichiers randomA100.tsp et randomB100.tsp afin de construire l’instance à deux objectifs randomAB100
  • Faire de même pour les instances randomCD100 et randomEF100
  • Développer la fonction d’évaluation (pour tous les objectifs)
  • Générer une solution aléatoire (une permutation) et l’évaluer


3. Filtrer les solutions dominées

Un des challenges de l’optimisation multi-objectif est de pouvoir filtrer efficacement les solutions dominées d’un ensemble de points, afin de ne conserver que les solutions non-dominées (les solutions qui nous intéressent).

Off-line. Dans uns stratégie «off-line», tous les points que l’on désire filtrer sont connus «en même temps». L’algorithme prend un ensemble de solutions en entrée et retourne le sous-ensemble de solutions non-dominées. On pourra éventuellement préciser, pour chaque objectif, s’il est à minimiser ou à maximiser.

On-line. Dans une stratégie «on-line», l’algorithme maintient un ensemble de solutions que l’on appelle une archive A (initialement un ensemble vide). De nouvelles solutions lui arrivent l’une après l’autre. À chaque fois qu’il prend une nouvelle solution x en entrée, l’algorithme doit décider s’il ajoute la solution x à l’archive A, et doit éventuellement supprimer les solutions de A qui sont dominées par x.

Se pose alors la question d’une structure de données adaptées pour stocker le contenu de l’archive (en particulier dans le cas à deux objectifs).

Dans un premier temps, nous nous contenterons de tester les algorithmes à l’aide de solutions du mTSP générées aléatoirement, et de vérifier visuellement le bon fonctionnement de l’algorithme à l’aide de gnuplot.

À faire :

  • Développer un algorithme de filtrage off-line pour 2 objectifs
  • À partir de chacune des instances, générer 500 solutions aléatoires et filtrer les solutions dominées suivant l’algorithme off-line
  • Vérifier le bon fonctionnement de l'algorithme à l’aide de gnuplot
  • Développer un algorithme de filtrage on-line pour 2 objectifs
  • À partir de chacune des instances, générer P solutions aléatoires, et mettre l’archive à jour séquentiellement avec chacune des solutions
  • Vérifier le bon fonctionnement de l'algorithme à l’aide de gnuplot
  • Étudier le nombre de comparaisons (ou le temps d’exécution) en fonction de P
  • Bonus : proposer une solution pour plus de 2 objectifs


4. Algorithmes pour le mTSP

Afin de résoudre le mTSP, nous allons nous intéresser à deux types d’approches : une approche scalaire et une approche Pareto.

Une approche scalaire recherche itérativement une solution Pareto approchée en se basant sur une fonction d'agrégation (transformant donc le problème initial en un problème mono-objectif) et en faisant varier (de façon intelligente) les paramètres de la fonction d'agrégation. Par exemple, en considérant une somme pondérée, on peut définir un certain nombre de poids possibles de façon à balayer l’ensemble du front Pareto. Pour chaque vecteur de poids, on obtiendra une solution à l’aide de la métaheuristique de votre choix. Il suffira ensuite de filtrer l’ensemble des solutions obtenues afin d’écarter les solutions dominées.

Concernant le choix de la métaheuristique à utiliser, inspirez vous de ce que vous avez vu en optimisation mono-objectif. Un opérateur de voisinage simple est efficace pour le TSP est l’opérateur 2-opt.

Une approche Pareto ne maintient pas une solution unique, mais un ensemble de solutions. Elle se base généralement sur la relation de dominance Pareto. Elle vise à améliorer l’ensemble de solutions en même temps (et pas chaque solution l’une à la suite de l’autre). En règle général, une archive ou une population est maintenue et, à chaque itération, de nouvelles solutions sont crées (à l’aide d’opérateurs de voisinage ou de variations) et ajoutées dans l’archive. Il s’agit alors de mettre l’archive à jour en ne conservant que les meilleures solutions. Pour cela, vous pourrez développer une recherche locale Pareto, ou un algorithme évolutionnaire multi-objectif.

Deux exemples d’algorithmes de recherche locale scalaires et Pareto pour le mTSP sont présentés dans cet article.

À faire :

  • Développer un algorithme de type scalaire pour le mTSP à 2 objectifs
  • Vérifier le comportement de votre algorithme visuellement (avec gnuplot)
  • Développer un algorithme de type Pareto pour le mTSP à 2 objectifs
  • Vérifier le comportement de votre algorithme visuellement (avec gnuplot)
  • Identifier clairement les paramètres et différentes variantes de vos algorithmes
  • Bonus : proposer une solution pour plus de 2 objectifs
  • Bonus : proposer une hybridation entre votre deux algorithmes


5. Évaluation des performances

Afin d’évaluer les performances de vos algorithmes et de les comparer, nous allons procéder à l’analyse expérimentale suivante.

Tout d’abord, il faut décider d’un (ou plusieurs) critère(s) d’arrêt pour vos algorithmes. Il s’agit généralement d’un temps d'exécution ou d’un nombre maximum d’évaluations (par exemple, 2 minutes).

Pour chacune des instances, vous allez exécuter vos algorithmes. Vos algorithmes sont-ils déterministes ? Si non, il convient d'exécuter chaque algorithme plusieurs fois d’afin d’éviter les exécutions «chanceuses» ou «malheureuses» (au moins 10 fois par instance). Pour chaque instance et chaque algorithme, on obtient donc 10 approximations du front Pareto. Ce sont ces ensembles qu’il s’agit de comparer.

Une première solution basique est de visualiser graphiquement les fronts obtenus et de les comparer visuellement. Une meilleure approche consiste à utiliser un ou plusieurs indicateurs de qualité, comme ceux que nous avons vu en cours (indicateur hypervolume, epsilon, etc.).

À faire :

  • Décrire clairement vos conditions expérimentales (choix des variantes algorithmiques, des paramètres, des instances, du critère d’arrêt) : vos algorithmes doivent être reproductibles !
  • Effectuer les différentes exécutions nécessaires pour chaque algorithme et chaque instance
  • Analyser les fronts approchés obtenus graphiquement (avec gnuplot)
  • Choisissez un ou plusieurs indicateurs de qualité, et évaluer les valeurs obtenues lors des exécutions de chaque algorithme sur chaque instance
  • Synthétiser vos résultats à l'aide de plusieurs tableaux et figures pertinents


Liens