Optimisation par colonies de fourmis

Ant colony Optimization

Nicolas Fayolle Guillaume Martinez

Nicolas Seydoux5IL- OC

Présentation:1. Introduction

a. Métaheuristiqueb. Pourquoi les fourmis?

2. Principe générala. Comportement des fourmisb. Fourmis réelles et virtuellesc. Principe de l’algorithmed. Intensification et diversification

3. Une illustration : Voyageur de commercea. Transformation de notre problème en TSPb. Résolution du TSP obtenu

4. Performances & Compléxité5. Améliorations

I - Introduction1. Métaheuristique:

➢ Algorithme d’optimisation

➢ Algorithme itératif qui progresse vers un optimum global.

➢ Tente d’apprendre les caractéristiques d’un problème afin de trouver une approximation de la meilleure solution

I - Introduction2. Pourquoi les fourmis?➢ Comportement collectif➢ Comportement indépendant: hétérarchie➢ Chaque fourmi est aidée par la communauté➢ Chaque fourmi aide au bon fonctionnement➢ Pistes de phéromones

II - Principe général 1. Comportement des fourmis

II - Principe général 2. Fourmis réelles et virtuelles

Points communs

➢ Chacune trouve une solution➢ Marquage de la piste avec des

phéromones➢ Évaporation des phéromones➢ Recherche du plus court chemin➢ Prise de décision aléatoires

Différences

➢ Monde non-continu➢ Mémoire (parcours, performances, ...)➢ Quantité de phéromones

proportionnelle à la qualité de la solution

➢ Mise à jour à la fin du parcours➢ Retour en arrière

Pas de phéromone = Choix aléatoire

II - Principe général 3. Principe de l’algorithme

➢ Trouver une solution en utilisant les critères de choix: visibilité, quantité de phéromones, aléatoire

➢ Mise à jour des quantité de phéromones (dépôt et évaporation)

Critère de d’arrêt (nb d’itérations)

Initialisation

Itération

Arrêt

II - Principe général4. Intensification et diversification

❖ Paramètre d’intensification: Suivre la piste de phéromones

❖ Paramètre de diversification: Prendre une direction aléatoire

III - Voyageur de commerceTSP

Trouver un circuit hamiltonien de longueur minimale dans un graphe G=(X,U)

1

5

4 3

2

3

4

1

2

24

2

1 4

3

III - Voyageur de commerceConventions et implémentation

m = nombre total de fourmis

Ti,j(t) = le taux de phéromones sur l’arc i, j à l’instant t

n = nombre de ville (soit |X| )

Vi,j = 1/Di,j = la visibilité d’une ville j quand on est sur une ville i

Lk = distance parcouru par la foumi k

Chaque fourmi mémorise l’ensemble des villes parcouruesmise à jour des phéromones se fera à chaque fin de cycle (circuit hamiltonien)

III - Voyageur de commerceInitialisation

m = 5 et Ti,j(0) = 0

p = 0.5 = coefficient d’évaporation des phéromones

Q = 100 = quantité de phéromones disponibles pour chaque fourmis

a = 1 = coefficient d’importance des phéromones

b = 1 = coefficient d’importance de la visibilité

● 1 fourmi ⇔ 1 ville● parcours aléatoire du graphe● on stocke les valeurs des distances

A=13, B=18, C=14, D=12, E=12

1

5

4 3

2

3

1

2

24

2

1 4

3 4

III - Voyageur de commerceChoix de transition

Pour déterminer sur quelle ville j une fourmi k présente en i va aller on utilise la formule:

p= (Ti,j)^a * (Vi,j)^b � (Ti,l)^a*(Vi,l)^b

avec l appartenant à l’ensemble des villes non parcouru

p(A1→2)(1) = 23.16 * 1 / 40.06 = 0.58 ✓p(A1→3)(1) = 21.58 * 0.25 / 40.06 = 0.13p(A1→4)(1) = 12.7 *0.25/ 40.06 = 0.08p(A1→5)(1) = 16.66 * 0.5 / 40.06 = 0.21 p(A2→3)(1) = 8.33 * 0.5 / 18.37 = 0.23p(A2→4)(1) = 29.91 * 0.33 / 18.37 = 0.54 ✓p(A2→5)(1) = 12.7 *0.33/ 18.37 = 0.23

p(A4→3)(1) = 15.47 * 0.5 / 23.755 = 0.33 ✓p(A4→5)(1) = 16.02 * 1 / 23.755 = 0.67

A: 1→ 2 → 4 → 3 → 5 → 1 = 12

III - Voyageur de commercemise à jour des phéromones

fin de cycle:Ti,j(t+n) = p * Ti,j(t) + ∆Ti,j(t)

∆Ti,j(t) = � ∆Tki,j(t)avec Tk taux de phéromones déposés par une fourmi

∆Tki,j(t) = Q/Lk

∆Tai,j(1) = 100/10 = 10∆Tbi,j(1) = 100/11 = 9.09∆Tci,j(1) = 100/10 = 10∆Tdi,j(1) = 100/8 = 12.5∆Tei,j(1) = 100/12 = 8.33

∆T1,2(1) = 49.92

T1,2(2) = 0.5 * 23.16 + 49.92 = 61.5

III - Voyageur de commerceFin de cycle et Résolution

fin de cycle:● MAJ du minimum

○ si convergence ⇒ arrêt

○ sinon RAZ mémoireet nouveau cycle

Arrêt de l’algorithme:● nombre de cycle● stagnation de la solution

l’algorithme converge vite vers :1→ 2 → 3 → 4 → 5 → 1

❖ Évolutions➢ Grosses améliorations des performances sur les problèmes statiques➢ Avancées dans le domaine des algorithmes dynamiques➢ Adaptées aux problèmes où la recherche locale est peu efficaces

IV - Performances❖ Version originale

➢ Performances correctes sur des petites instances du TSP➢ Dépassée par les solveurs dédiés sur les grosses instances

V - Améliorations

❖ Équilibrer exploitation et exploration➢ Favoriser l’émergence de bonnes solutions➢ Empêcher la convergence prématurée

❖ Modifier la gestion des phéromones➢ on-line/off-line➢ Coefficients multiplicateurs➢ Sélection

V.1 - Élitisme❖ Stratégie “off-line”❖ Axée sur l’exploitation❖ Mise en avant du meilleur circuit

➢ IB ou BS

V.1.a - ASrank❖ Mise à jour sélective des phéromones

➢ Seules les meilleures fourmis laissent leur trace➢ L’importance de la mise à jour dépend du classement de la solution de

la fourmi

V.1.b MMAS : Max-Min AS

❖ Introduction d’une borne sur le marquage➢ Quantité de phéromone sur un élément comprise entre τmin et τmax➢ Explicitation de la borne min des autres algorithmes➢ La borne supérieure évolue avec l’exploration

❖ Évolution de la règle d’élitisme➢ IB au début➢ BS à une fréquence croissante

❖ Initialisation du marquage à la borne max➢ Favorise l’exploration initiale

V.1.c ACS: AC System

❖ Choix pseudo-aléatoire proportionnel➢ Choix potentiellement uniquement basé sur heuristique et

phéromones

❖ Accent sur l’exploitation➢ Mise en avant de l’expérience passée➢ Fort coefficient élitiste

❖ Mise à jour dynamique des phéromones➢ Consommation des phéromones par les fourmis➢ Diversifie les chemins pour une itération

V.2 - Recherche locale❖ Approches complémentaires

➢ Affine les solutions trouvées par la métaheuristique➢ Les algorithmes ACO tendent à produire des solutions

grossières➢ Celles-ci sont de très bonnes candidates pour lancer une

recherche locale

❖ Version originale➢ Performances correctes sur des petites instances du TSP➢ Dépassé par les solveurs dédiés sur les grosses instances

V.3 - Problèmes dynamiques❖ AntNet : Algorithme de routage

➢ Marquage aux phéromones pour chaque arc de sa valeur pour chaque sommet

➢ Évaluation du chemin en fonction du nombre de sauts, du débit des arcs empruntés et du trafic

➢ Pas de mise à jour off-line des phéromones➢ Valeur heuristique pour un arc réévaluée à chaque passage

ConclusionCe qu’il faut retenir

- Algorithme à population, itératif et à mémoire- Choix aléatoire paramétrable entre exploration et

exploitation- Algorithme décentralisé adapté aux problèmes

dynamique- Couplable avec de la recherche locale

Merci de votre attention

Sources- Ant colony optimization theory: A survey [Marc Dorigo, Christian Blum] - 2005- A survey on optimization metaheuristics, [Ilhem Boussaïd, Julien Lepagnot, Patrick Siarry] -

2012- The ant colony optimization metaheuristic : algorithms applications, and advances [Marc

Dorigo]- Optimisation par colonies de fourmis [Andrea Costanzo, Thé Van Luong, Guillaume Marill] -

2006