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 :
Planning prédictif :
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 :
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 :
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 :
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 :
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 :
Liens