Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Adaptation 1 Problème de voyageur de commerce (TSP) avec l’algorithme de Coloni

Adaptation 1 Problème de voyageur de commerce (TSP) avec l’algorithme de Colonie de Fourmis Pr. Elhilali Alaoui FST de Fès Pr. Elhilali Alaoui FST de Fès À l’origine, l’optimisation par colonies de fourmis a été conçue pour résoudre le problème de voyageur de commerce. Instance à 92 villes Solution  Problème de voyageur de commerce Application au problème de voyageur de commerce 2 Pr. Elhilali Alaoui FST de Fès Un voyageur de commerce doit visiter n villes données en passant par chaque ville exactement une fois. Il commence par une ville quelconque et termine en retournant à la ville de départ. Les distances entre les villes sont connues à l’avance. Le problème est de trouver le ou les circuits les plus courts. Notons que la notion de distance peut être remplacée par d’autres notions comme le temps qu’il met ou l’argent qu’il dépense.  Problème de voyageur de commerce Application au problème de voyageur de commerce 3 Pr. Elhilali Alaoui FST de Fès Nous définissons le TSP (Travel Sealsman Problem) comme suit : Etant donnée un ensemble de nœuds et d’arêtes munis de coûts. L’idée est de trouver un circuit Hamiltonien, c’est-à-dire le circuit passant par tous les nœuds une fois et une seule, tout en minimisant le coût total de transport lié aux arcs empruntés par le voyageur. Ce problème est classé NP-difficile, c'est-à-dire qu’il n’existe pas d’algorithmes de résolution exacte en un temps polynomial capable de le résoudre.  Problème de voyageur de commerce Application au problème de voyageur de commerce 4  Modèle mathématique La formulation mathématique du problème de voyageur de commerce a été présentée pour la première fois en 1954 par Dantzig. Etant donné un ensemble N de n nœuds, pour chaque deux nœuds i et j on associe le coût cij au trajet entre eux. La variable binaire xij prend la valeur 1 si (i,j) est emprunté et 0 sinon. S étant un sous ensemble quelconque de N avec : Application au problème de voyageur de commerce 5 Pr. Elhilali Alaoui FST de Fès  Modèle mathématique Le problème de voyageur de commerce se modélise comme suit : Application au problème de voyageur de commerce 6 Pr. Elhilali Alaoui FST de Fès  Modèle mathématique Le problème de voyageur de commerce se modélise comme suit : La minimisation du coût de transport Application au problème de voyageur de commerce 7 Pr. Elhilali Alaoui FST de Fès  Modèle mathématique Le problème de voyageur de commerce se modélise comme suit : le voyageur entre et sort une seule fois de chaque ville Application au problème de voyageur de commerce 8 Pr. Elhilali Alaoui FST de Fès  Modèle mathématique Le problème de voyageur de commerce se modélise comme suit : Formulation classique pour éviter les sous-tours Application au problème de voyageur de commerce 9 Pr. Elhilali Alaoui FST de Fès Pr. Elhilali Alaoui FST de Fès  L’ensemble des sommets S du graphe G représente l’ensemble des villes  L’ensemble des arrêtes L défini la succession possibles des villes dans une solution du problème considéré Adaptation Application au problème de voyageur de commerce 1 0 Pr. Elhilali Alaoui FST de Fès L’algorithme de base: Ant System Le Ant-System pour le TSP est l’un des trois premiers algorithmes proposés par Dorigo en 1991. Celui-ci mettait en avant le comportement coopératif des fourmis pour la résolution du TSP. Ces trois algorithmes sont AS-density, AS-quantity et AS-cycle. La seule différence entres ces variantes réside dans la mise à jour des traces de phéromone. Application au problème de voyageur de commerce 1 1 Pr. Elhilali Alaoui FST de Fès Initialisation Transition dépôt et Évaporation Algorithme de base: Ant System A chaque itération t Pour chaque fourmi k=1…,m Pour chaque ville i non visitée Choisir la ville suivante j selon: Application au problème de voyageur de commerce 1 2           sinon J j si ) ( )) t ( ( ) ( )) t ( ( ) t ( P k i J l il il ij ij k ij i k 0         Pr. Elhilali Alaoui FST de Fès Initialisation Transition dépôt et Évaporation Algorithme de base: Ant System Pour chaque fourmi k Pour chaque ville non visitée Choisir la ville suivante j selon: Intensité de la piste L’inverse des distances inter villes Villes non visitées et l’importance relative des traces de phéromone et de l’information heuristique Application au problème de voyageur de commerce 1 3           sinon J j si ) ( )) t ( ( ) ( )) t ( ( ) t ( P k i J j ij il ij ij k ij i k 0           Pr. Elhilali Alaoui FST de Fès Initialisation Transition dépôt et Évaporation Algorithme de base: Ant System La mise à jour globale des pistes  Dépôt des pistes selon:  Évaporation des pistes selon: Application au problème de voyageur de commerce 1 4         sinon 0 ) ( T j) (i, si ) ( L Q k k ij t t k  (t) : où (t) (t) ) - (1 1) (t 1 ij ij ij ij ij        m k k       Pr. Elhilali Alaoui FST de Fès Initialisation Transition dépôt et Évaporation Algorithme de base: Ant System La mise à jour globale des pistes  Dépôt des pistes selon:  Évaporation des pistes selon: Q et un paramètre fixé de l’algorithme Longueur de la tourné Facteur d’évaporation entre 0 et 1 Application au problème de voyageur de commerce 1 5         sinon 0 ) ( T j) (i, si ) ( L Q k k ij t t k  (t) : où (t) (t) ) - (1 1) (t 1 ij ij ij ij ij        m k k       Pr. Elhilali Alaoui FST de Fès Début Initialisation placer aléatoirement les fourmis sur les villes initialiser la phéromone à une quantité Pour t=1,…, tmax Pour chaque fourmi k=1,…,m Pour chaque ville non visitée i Choisir une ville j, dans la liste Ji k des villes restantes, Selon la formule : Fin Pour Fin Pour Mettre à jour les pistes de phéromones selon la formule : avec: Fin pour Fin Algorithme de base: Ant System 1 6 0                    sinon 0 J j si ) ( )) t ( ( ) ( )) t ( ( ) t ( P k i J j ij il ij ij k ij i k (t) : où (t) (t) ) - (1 1) (t m 1 k ij k ij ij ij ij                       sinon 0 ) ( T j) (i, si ) ( L Q k k ij t t k  uploads/Voyage/ ch4-ro.pdf