Analyse des performances de l'algorithme d'optimisation dynamique MADO
Julien Lepagnot, doctorant en 2ème année
Sous la direction de:A. Nakib, H. Oulhadj et P. Siarry
Atelier scientifique de l'équipe TIS du LISSI
Les AS de TIS 1
Plan de l’exposé1. Introduction
1. Membres de l’équipe
2. L’optimisation statique
3. Les métaheuristiques
4. L’optimisation dynamique
2. La thèse
1. Choisir les bons ingrédients
2. Mise au point d’une nouvelle métaheuristique
3. Description de MADO
4. Analyse des performances
5. Conclusions et perspectives
Les AS de TIS 2
Plan de l’exposé1. Introduction
1. Membres de l’équipe
2. L’optimisation statique
3. Les métaheuristiques
4. L’optimisation dynamique
2. La thèse
1. Choisir les bons ingrédients
2. Mise au point d’une nouvelle métaheuristique
3. Description de MADO
4. Analyse des performances
5. Conclusions et perspectives
Les AS de TIS 3
1.1. Membres de l’équipe
Les AS de TIS 4
Patrick SIARRY – Professeur des universitésHamouche OULHADJ – Maître de conférencesAmir NAKIB – ATER et consultant R&DJulien LEPAGNOT – Doctorant en 2ème année
Domaines de recherche : Optimisation, métaheuristiques, applications de l’optimisation dans le domaine biomédical, modélisation…
Recalage d’angiographies rétiniennes
Avant recalage Après recalage Translation
Segmentation d’images biomédicales
Image IRM originale Image segmentée
1.2. L’optimisation statique (1 / 2)
Les AS de TIS 5
Problème d’optimisation statique
Formaliser le problème en terme de fonction objectif à maximiser ou minimiser.
Soit :
• un espace de recherche S
• une fonction objectif f
Dans le cas d’une minimisation, on cherche la position s* telle que :
s* = arg min( f(s) \ s S )
Dans le cas d’une maximisation, on se ramène à un problème de minimisation :
Maximiser f Minimiser – f
1.2. L’optimisation statique (2 / 2)
Les AS de TIS 6
Le problème de tournées de véhicules
Dépôt
Le problème d’affectation de tâches
machine 1 machine 2 machine 3
chargecharge charge
Compression du signal
modélisation viaune métaheuristique
Recalage d’imagesAvant recalage Après recalage Translation
Les AS de TIS 7
Classification des méthodes d'optimisation statique
1.3. Les métaheuristiques (1 / 4)
1.3. Les métaheuristiques (2 / 4)
Les AS de TIS 8
Exemple : Algorithmes évolutionnaires [Holland, 1973]
Reposent sur la compétition au sens de Darwin
Population
courante
Population de
descendants
Population de
descendants mutés
Population
évaluée
Croisement
Evaluation
Sélection Mutation
COMPETITION entre agents
1.3. Les métaheuristiques (3 / 4)
Les AS de TIS 9
Exemple : Colonies de fourmis [Dorigo et al., 1996]
INTELLIGENCE EN ESSAIM : COOPERATION INDIRECTE entre agents (via l’environnement)
1.3. Les métaheuristiques (4 / 4)
Les AS de TIS 10
Exemple : Les essaims particulaires [Kennedy et Eberhart, 1995]
)1()()1(
)()()()()()1(2211
tvtxtx
txtgrctxtprctvtv
ii
iiiii
L’OEP simule le comportement social d’un essaim de « particules »
A chaque itération t, chaque
particule i se définit par :
• sa position
• sa vitesse
ω, c1, c2, coefficients de confiance et r1, r2 ]0, 1]
Positionactuelle
Vers sa meilleureperformance
Nouvelleposition
Vers la meilleureperformance del’essaim
Vers le pointaccessible avec lavitesse courante
ix
iv
INTELLIGENCE EN ESSAIM : COOPERATION DIRECTE entre agents
1.4. L’optimisation dynamique (1 / 4)
Les AS de TIS 11
Dans le cas dynamique, la fonction objectif est susceptible de changer au cours du temps. On a :
• un espace de recherche S
• une fonction objectif f
• le temps t
Dans le cas d’une minimisation, on cherche la position s* telle que :
s* = arg min( f(s,t) \ s S )
Problème d’optimisation dynamique
1.4. L’optimisation dynamique (2 / 4)
Les AS de TIS 12
Le problème de tournées de véhicules
Dépôtajout
retrait
Le problème d’affectation de tâches
machine 1 machine 2 machine 3
charge charge
ajoutretrait
panne
Compression du signal
Nouveau modèleà chaque battement
Estimation du mouvement dans une séquence
peu de différences entreles décalages consécutifs
(repartir de l’ancienne solution)
1.4. L’optimisation dynamique (3 / 4)
Les AS de TIS 13
Techniques d’optimisation dynamique
Adaptation des métaheuristiques d’optimisation statique
1.4. L’optimisation dynamique (4 / 4)
Les AS de TIS 14
Benchmarks (tests standards) :
Le « Moving Peaks Benchmark » [J. Branke, 1999]
(beaucoup d’auteurs l’utilisent)
Un ensemble de fonctions de test proposées par W. TFAILI
au LISSI durant sa thèse en 2007
(n'est pas très utilisé)
La compétition de CEC’2009 [Trondheim, Norvège, May 2009]
(en émergence)
Plan de l’exposé1. Introduction
1. L’équipe
2. L’optimisation
3. Les métaheuristiques
4. L’optimisation dynamique
2. La thèse
1. Choisir les bons ingrédients
2. Mise au point d’une nouvelle métaheuristique
3. Description de MADO
4. Analyse des performances
5. Conclusions et perspectives
Les AS de TIS 15
2.1. Choisir les bons ingrédients
Les AS de TIS 16
Métaheuristique à population de
solutions
Essaim particulaires
(consomme trop d’évaluations)
Fourmis(converge trop
lentement)
Evolutionnaires (intéressant en
multipopulation)
Economiser les évaluations de la fonction objectif
Recherche locale spécialisée
Maintenir la diversité tout au
long de la recherche
Utiliser une population
d’agents coordonnés
Mémoriser des informations sur les
« états » passés
Archiver les optima locaux
trouvés
Suivre les déplacements des
optima archivés
2.2. Mise au point d’une nouvelle métaheuristique
Les AS de TIS 17
Agents de recherche locale coordonnés, archivage des optima trouvés :
PSO : Impossible de rattacher la méthode à cette classe
Fourmis : Pas de phéromones, impossible aussi
Evolutionnaires : Impossible aussi
Programmation à Mémoire Adaptative [E. Taillard, 1997] : Tentative…
…échouée
Multi-Agent : Multi-Agent Dynamic Optimization MADO
Hill Climbing à pas adaptatif
Hill Climbing à pas adaptatif
Hill Climbing à pas adaptatif
Hill Climbing à pas adaptatif
Pseudo-parallélisme des recherches locales
Plan de l’exposé1. Introduction
2. La thèse
3. Description de MADO
1. Structure générale de MADO
2. Structure d’un agent de MADO
3. La population initiale d’agents
4. Procédure Agent
5. Détection de changement
4. Analyse des performances
1. Sur le Moving Peaks Benchmark
2. Sur le jeu de test de CEC’2009
5. Conclusions et perspectives
Les AS de TIS 18
3.1. Structure générale de MADO
Les AS de TIS 19
Initialisation
Coordinateur
…
Module de gestion des agents
Critère d’arrêt satisfait ?
Agent 1
Mémoire locale
Agent 2
Mémoire locale
Agent i
Mémoire locale
Fin
Non Oui
Gestionnaire de l'archive
Archive
Module de mémoire
3.2. Structure d’un agent de MADO
Le voisinage d’un agent est constituéd’un nombre N de solutions situées :
► à une distance de l’agent égale à son pas.
► à égale distance les unes des autres.
Le pas d’un agent :
► correspond ainsi à la distance entre sa solutioncourante et ses voisines.
► est adapté à chaque déplacement de l’agent.Rayon =
pas de l’agent
Solutions appartenantau voisinage de l’agent.
La solution courante, sur laquelle se trouve l’agent.
Espace de recherche
Les AS de TIS 20
3.3. La population initiale d’agents
A l’initialisation, le coordinateurordonne la création de na agents, et lesdispose de façon « régulière » dansl’espace de recherche.
► Espacer au maximum les na agentsentre eux, dans l’hyperrectangle T.
Sur cette figure, na = 5, et l’espace est à2 dimensions.
maxre =1
2 na
Espace de recherchenormalisé
Hyperrectangle T oùsont placés les
agents
maxremaxre
maxre
maxre
1
0 1
Les AS de TIS 21
Agent
Les AS de TIS 22
début
Synchronisation
Procédure d’obtention d’une position de
départ (si possible)
Procédure de recherche locale
CoordinateurOuiNon Nouvel
optimum
3.4. Procédure Agent
3.4. Procédure Agent détaillée
Demande d’une nouvelle position et d’un nouveau pas au coordinateur
Début
Synchronisation
Réduire le pas
Se déplacer sur la meilleure
solution voisine
Adapter le pas par le produit
scalaire cumulé
Obtention d’une nouvelle position et d’un nouveau pas
Envoi de l’optimum local trouvé au coordinateur
Synchronisation
Critère d’arrêt d’une recherche locale satisfait?
Peut trouver une meilleure
solution voisine?
Trop proche d’autres agents?
Attente que tous les autres
agents entrent dans un état
Synchronisation
OuiNon
OuiNon
OuiNon
Les AS de TIS 23
3.5. Détection de changement
Le coordinateur détecte un changement dans la fonction objectif par ré-évaluationd’une solution. Si la valeur de cette dernière a changé, les mesures suivantes sontprises :
► toutes les solutions (des agents et de l’archive) sont ré-évaluées.
► pour chaque optimum de l’archive, un agent est créé et positionnésur cet optimum.Ces nouveaux agents sont des agents de suivi des optima. Leur but est de trouver la
nouvelle position d’un optimum après un changement du paysage. Ces agents ne font
donc qu’une seule recherche locale, avant d’être détruits.
► l’archive est ensuite vidée.
Les AS de TIS 24
Plan de l’exposé1. Introduction
2. La thèse
3. Description de MADO
1. Structure générale de MADO
2. Structure d’un agent de MADO
3. La population initiale d’agents
4. Procédure Agent
5. Détection de changement
4. Analyse des performances
1. Sur le Moving Peaks Benchmark
2. Sur le jeu de test de CEC’2009
5. Conclusions et perspectives
Les AS de TIS 25
Le « Moving Peaks Benchmark » (MPB) consiste en un ensemble de pics dont la hauteur, la largeur et la position peuvent varier au cours du temps (après un certain nombre d’évaluations de la fonction).
Ce problème est paramétrable, et a été adopté par une majorité d’auteurs.
(a) Avant un changement (b) Après un changement
4.1. Performances sur le Moving Peaks Benchmark (1 / 4)
Les AS de TIS 26
x xy y
f(x, y) f(x, y)
4.1. Performances sur le Moving Peaks Benchmark (2 / 4)
Convergence de MADO pour chaque time span*.
* Time span : Plage d’itérations durant laquelle la fonction objectif ne change pas.Un changement de la fonction objectif se produit ici toutes les 5000 itérations.
Les AS de TIS 27
itérations changement
Am
plit
ude
4.1. Performances sur le Moving Peaks Benchmark (3 / 4)
* Time span : Plage d’itérations durant laquelle la fonction objectif ne change pas.Un changement de la fonction objectif se produit ici toutes les 5000 itérations.
Convergence moyenne de MADO sur 100 time spans*.
La précision maximale, choisie par l’utilisateur, est atteinte après 2000 évaluations de la fonction objectif.
Les AS de TIS 28
4.1. Performances sur le Moving Peaks Benchmark (4 / 4)
* Offline error : Moyenne des écarts entre l'optimum global et la meilleure solution trouvée à chaque itération.Une erreur de 0 signifie un suivi parfait de l'optimum.
Auteurs Classe d'algorithme Moyenne sur Offline error * Erreur type
Novoa et al. 2009 PSO 50 runs 0.40 0.04
Lepagnot et al. 2009 MADO100 runs50 runs
0.580.59
0.100.10
Moser & Hendtlass 2007 Extremal Optimisation 100 runs 0.66 0.20
Lung & Dumitrescu 2007 Hybride 50 runs 1.38 0.02
Lung & Dumitrescu 2008 Hybride 50 runs 1.53 0.01
Blackwell & Branke 2006 PSO 50 runs 1.72 0.06
Mendes & Mohais 2005 Differential Evolution 50 runs 1.75 0.03
Li et al. 2006 PSO 50 runs 1.93 0.06
Blackwell & Branke 2004 PSO 50 runs 2.16 0.06
Du W. & Li B. 2008 PSO 50 runs 4.02 0.56
Les AS de TIS 29
4.2. Performances sur le jeu de test de CEC’2009 (1 / 4)
Le jeu de test de CEC’2009 est constitué de 49 fonctions dynamiques.
L’ensemble de ces fonctions est supposé être représentatif de la plupart des problèmesd’optimisation dynamique réels.
Divers types de changements, plus ou moins chaotiques et brutaux, ont lieu après uncertain nombre d’évaluations de la fonction (comme sur MPB).
Ce problème est paramétrable, et a été utilisé lors de la compétition de CEC’2009.
Les AS de TIS 30
Plus précisément, chaque fonction dynamique correspond à une fonction statique à laquelle on applique (à chaque time span*) une opération de changement (qui modifie plus ou moins brutalement son paysage).
Il existe 6 fonctions statiques :• F1: Rotation peak function• F2: Composition of Sphere's function• F3: Composition of Rastrigin's function• F4: Composition of Griewank's function• F5: Composition of Ackley's function• F6: Hybrid Composition function
Il existe 7 opérations de changement :• T1: small step• T2: large step• T3: random• T4: chaotic• T5: recurrent• T6: recurrent change with noise• T7: random change with changed dimension
* Time span : Plage d’itérations durant laquelle la fonction objectif ne change pas.
Les AS de TIS 31
4.2. Performances sur le jeu de test de CEC’2009 (2 / 4)
Convergence moyenne de MADO sur chaque classe de fonction.
Les AS de TIS 32
4.2. Performances sur le jeu de test de CEC’2009 (3 / 4)
4.2. Performances sur le jeu de test de CEC’2009 (4 / 4)
*Ce benchmark donne un score sur 100 à la fin de son exécution.
69,7365.21
59,72 58.09 57.57
38.29
0
10
20
30
40
50
60
70
80
Brest et al., 2009Korosec et Silc, 2009 Yu et Suganthan, 2009Li et Yang, 2009França et Von Zuben, 2009
MADO
Les AS de TIS 33
Plan de l’exposé1. Introduction
2. La thèse
3. Description de MADO
1. Structure générale de MADO
2. Structure d’un agent de MADO
3. La population initiale d’agents
4. Procédure Agent
5. Détection de changement
4. Analyse des performances
1. Sur le Moving Peaks Benchmark
2. Sur le jeu de test de CEC’2009
5. Conclusions et perspectives
Les AS de TIS 34
On vient de voir le fonctionnement de MADO, ainsi que ses performances sur les 2 principaux jeuxde test dynamiques.
On constate que les performances de MADO sur des fonctions hautement multimodales, telles queRastrigin, sont médiocres.
Hormis les difficultés rencontrées sur les fonctions telles que Rastrigin, les performances de MADOsont très encourageantes. On constate en effet que MADO est bien classé dans les comparatifs avecles algorithmes concurrents.
Amélioration des performances de MADO sur des problèmes type Rastrigin.
Réduction du nombre de paramètres à la charge de l’utilisateur.
Conclusions et perspectives
Les AS de TIS 35