Embed Size (px)
Citation preview
Grégory BeurierLIRMM – Université Montpellier II – CNRS
Mercredi 19 décembre 2007
Codage indirect de formes dans les SMA:émergence multi-niveaux, évolution et morphogénèse
sous la direction de Jacques Ferber
Soutenance de thèse – Grégory Beurier
2
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Comment produire la forme dans un système complexe artificiel ?
La notion de forme[Bourgine, 2006]
Forme
Stabilité dynamique
Optimisationfonctionelle
FonctionSystème
Fonctions
Formes
Mécanismesmorphogénétiques
Soutenance de thèse – Grégory Beurier
3
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Concepts généraux et état de l'art
• Systèmes complexes• Emergence multi-niveaux
Une embryogénie multi-agents
• Inspirations biologiques• Modèle
Simulations et extensions
• TurtleKit 2• Le problème des drapeaux• Extension et hybridation du modèle
Conclusion et perspectives
PLAN
4
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
CONCEPTS GÉNÉRAUXProblématique et état de l’art
Soutenance de thèse – Grégory Beurier
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Soutenance de thèse – Grégory Beurier
6
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Outils d'étude des systèmes complexes
Description
Niveau Macro-
Comportementglobal
Niveau micro-
Comportementslocaux
Théorie de l'information[Shannon 1948]
Théorie de la complexité
[Kolmogorov 1930]
Thermodynamique,Fonctions logistiques,
Equations différentielles,
etc.
Automates Cellulaires[Conway 1970, Wolfram 1982]
Systèmes multi-agents[Ferber 1995,
Wooldridge 1995]
Soutenance de thèse – Grégory Beurier
7
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Approchesgrammaticales
Approcheschimiques
Travaux bio-inspirés sur la forme
L-Systems[Lindenmayer, 1990]
Amorphous Computing[Coore, 1999]
Agrégation émergente[Vaario, 1995]
Modèles Réaction/diffusion[Turing, 1952]
Programmation génétique cartésienne
[Miller, 2003]
Réseaux de régulations[Eggenberger, 1997]
Soutenance de thèse – Grégory Beurier
8
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Codage indirect[De Garis, 2001]
CODAGE DIRECT CODAGE INDIRECT
0101110101001010101010
FORME
0101110101001010101010
FORME
Codage
Comportement
Codage
Soutenance de thèse – Grégory Beurier
9
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Modèle d'émergence multi-niveauxPrincipe général
Soutenance de thèse – Grégory Beurier
10
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Mécanismes récursifs d'agrégationUn modèle de système multi-agents pour l'émergence multi-niveaux.
Beurier, Simonin, Ferber. JFSMA 03
Perception
Mutation
Perception
Mutation
Emission dephéromones
Attraction
état i
état i+1état i+2
Soutenance de thèse – Grégory Beurier
11
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Exemple de SimulationEnvironnement: 100x100
Phéromones: Att- Rep - Pre
Attracteur: circulaire
12
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
UNE EMBRYOGÉNIE MULTI-AGENTS
Soutenance de thèse – Grégory Beurier
13
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Morphogénèse
Principe généralS’inspirer des mécanismes naturels
Evolution
Soutenance de thèse – Grégory Beurier
14
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Régulation génique
Facteurs deTranscription
Gène(ADN)
ARN
Protéines
Elements Régulateurs Partie Codante
Soutenance de thèse – Grégory Beurier
15
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Le modèle du drapeau français[Wolpert, 1968]
BLEU BLANC ROUGE
Conc
entr
ation
de
mor
phog
ène
Seuilsd’activation
gène gène gène
Soutenance de thèse – Grégory Beurier
16
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Morphogénèse de la drosophile
Nanos BicoidsGapPair-rulesSegment Polarity Ubx
Morphogènes maternels
Gènes de segmentation
Gènes de sélecteurs
Soutenance de thèse – Grégory Beurier
17
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Transfert au modèle de SMA
10
01
11
00
11
01
10
01
11
00
11
01
Perception RégulationActionEmission
Gradients maternels
1001
1100
1101
1001
1100
1101
Gène sélecteur
Gène de segmentation
Soutenance de thèse – Grégory Beurier
18
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Principe d'un algorithme évolutionniste
FinProblèmeà résoudre
Condition d’arrêt
Début
Problèmerésolu
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Soutenance de thèse – Grégory Beurier
19
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
FinProblèmeà résoudre
Condition d’arrêt
Début
Problèmerésolu
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Soutenance de thèse – Grégory Beurier
20
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Trouver les bons paramètres des gènesProblème d’optimisation Parcours de l’espace des formes
Problème à résoudre
1001
1100
1101
1001
1100
1101
+
Soutenance de thèse – Grégory Beurier
21
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
FinProblèmeà résoudre
Condition d’arrêt
Début
Problèmerésolu
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Soutenance de thèse – Grégory Beurier
22
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
10
01
11
00
11
01
Codage des gènes / des agents
100111001101
100111001101
Perception RégulationActionEmission
Morphogène A
Morphogène B
Morphogène C
Morphogène D
120
20
50
80
Quantité
10
01
11
00
11
01
10
01
11
00
11
01
Eléments régulateurs
Partie codante
AB*D**
8010*
50**Fa
cteu
rs d
e tr
ansc
riptio
n
Seui
ls d
’acti
vatio
n
Si (r
egul
é =
vrai
) al
ors
expr
ime(
parti
e co
dant
e);
110100 | 8-1-0-5-0-
0 | 10
Facteurs de transcriptions
Réaction régulatrice
Unité de réaction
getMorphogenes();
Soutenance de thèse – Grégory Beurier
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Zone d'expression d'un gène 23
Morphogène A
Morphogène B
Zone d’expression
facteurs | réaction | unité
Eléments régulateurs
0
200
140
0 40 200
AB| 7-2 | 200
70100
0
100
50
AB| 5-10 | 10
0
100
70
A| 35 | 20
3040
AB| 0 - 8 | 5
Soutenance de thèse – Grégory Beurier
24
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Expression: partie codante
10
01
11
00
11
01
10
01
11
00
11
01
Gène de segmentation
Gène sélecteur
Nom | Coeff diffusion | Taux évaporationemitMorphogene( );
do( );Action Action();
do( );Action | paramètres Action(paramètres);
do( );B
CA Si (A()) alors B() sinon C();
Soutenance de thèse – Grégory Beurier
25
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Actions
do( );Mitos
eRéplication 8-connexe();
do( ); Réplication 8-connexe(taux);Mitose |
taux
do( );Apoptose
Suicide();
do( ); SuicideDans(retard);Apoptose | retard
do( ); ChangerCouleur(couleur);Couleur | couleur
Soutenance de thèse – Grégory Beurier
26
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
FinProblèmeà résoudre
Condition d’arrêt
Début
Problèmerésolu
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Soutenance de thèse – Grégory Beurier
27
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
FinProblèmeà résoudre
Condition d’arrêt
Début
Problèmerésolu
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Soutenance de thèse – Grégory Beurier
28
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
FinProblèmeà résoudre
Condition d’arrêt
Début
Problèmerésolu
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Soutenance de thèse – Grégory Beurier
29
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
FinProblèmeà résoudre
Condition d’arrêt
Début
Problèmerésolu
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Soutenance de thèse – Grégory Beurier
30
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Ressemblance = Calcul()Si (ressemblance> seuil)Renvoyer ArrêtSinonRenvoyer Continuer
Evaluation & Conditions d'arrêt
Motif de référence
Fitness
Soutenance de thèse – Grégory Beurier
31
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
FinProblèmeà résoudre
Condition d’arrêt
Début
Problèmerésolu
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Soutenance de thèse – Grégory Beurier
32
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
FinProblèmeà résoudre
Condition d’arrêt
Début
Problèmerésolu
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Soutenance de thèse – Grégory Beurier
33
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Opérateurs génétiques[Koza, 1996][Holland, 1987][Fogel, 1966]
Sélection
• Baker• Elitisme• Jumeaux
Croisement• Crossing-over
• 1-point• 2-points• Uniforme
• Permutations
Mutation
• Aléatoire sur des bits
Soutenance de thèse – Grégory Beurier
34
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
FinProblèmeà résoudre
Condition d’arrêt
Début
ProblèmeRésolu
(comportement +gènes)
Choix ducodage des
agents
Génération d’une population aléatoire
Evaluation des agents
Application des opérateurs génétiques
Génération d’une nouvelle
population
Sélection des parents
non
oui
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
SIMULATIONS & EXTENSIONS
Soutenance de thèse – Grégory Beurier
36
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
TurtleKit & TurtleKit 2
1()
2()
4()
3()
Launcher Scheduler
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
Manager
XMLLauncher
Observer
The TurtleKit Simulation Platform: Application to complex systemsMichel, Beurier, Ferber. SITIS 2005.
Fitn
ess
Soutenance de thèse – Grégory Beurier
37
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Le drapeau français[Miller, 2003]
BLEU BLANC ROUGE
Genes sélecteurs: bleu, blanc, rouge, mitose
Environment: 4 gradients maternels. 100x100.
Population: 30. Generations: 250.
Motif de référence
Soutenance de thèse – Grégory Beurier
38
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Le drapeau japonaisA morphogenesis model for multiagent embryogeny
Beurier, Michel, Ferber. Alife X, 2006.
Motif de référence
Gènes sélecteurs: rouge, mitose
Gènes de segmentation: 1
Environment: 4 gradients maternels. 100x100.
Population: 30. Generations: 250.
Réutilisation du gène de mitose
Population: 30. Generations: 200.
Soutenance de thèse – Grégory Beurier
39
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Simu 3
Simu 2
Simu 1
Evolution incrémentaleRéutilisation des gènes
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
Simu 4
10
01
11
00
11
01
10
01
11
00
11
01
10
01
11
00
11
01
Soutenance de thèse – Grégory Beurier
40
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
L'embryogénie "LiRmm"
Gènes sélecteurs: mitose, apoptose
Gènes de segmentations: 12
Environment: 4 gradients maternels. 100x100.
Population: 30. Generations: évolution incrémentale.
Soutenance de thèse – Grégory Beurier
41
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Reconstruction embryogéniqueHybridation des modèles
do( );Mitose
Emission Attractif();
do( );Apoptose
Emission Repulsif(); Fuite();
Modèle d’agrégation
Soutenance de thèse – Grégory Beurier
42
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Agrégation "LiRmm"Hybridation des modèles
43
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
CONCLUSION
Soutenance de thèse – Grégory Beurier
44
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Modèle d’émergence multi-niveauxComportements récursifsRègles d’agrégations
Modèle d’embryogénie multi-agentsMorphogénèse animaleAlgorithmique évolutionnisteEvolution incrémentaleHybridation avec des règles d’agrégations
Plate-forme de simulation TurtleKit2Gestionnaire de simulations: XML, sauvegarde, etc.API génétique: populations, observers, etc.Outils de visualisation et d’interaction temps réel
ConclusionContributions
Soutenance de thèse – Grégory Beurier
45
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Perspectives La fonction
Fonctions implicites Fonctions explicites
Forme =
Fonction
Forme =
Propriétés
Eléments micro =
PropriétésLIRM
M
Forme
Stabilité dynamique
Optimisationfonctionelle
Fonction
Temps de convergence
Soutenance de thèse – Grégory Beurier
46
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Accélérer le processus de convergenceEvolution incrémentaleBibliothèque génétique de formes, langage de formesOpérateurs génétiques "intelligents"
Augmenter l'expressivité du modèleAméliorer la réaction régulatrice (programmation génétique)
Supprimer les gradients maternelsModèle assymétrique de réaction/diffusionIngénierie de l'environnement
PerspectivesTravaux futurs et applications
Merci de votre attention
48
Soutenance de thèse – Grégory Beurier
49
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Comparaison Tk – Tk2 ViewersEmergence multi-niveaux
Soutenance de thèse – Grégory Beurier
50
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Simulations (échecs)
Soutenance de thèse – Grégory Beurier
51
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Simulation de la voileRépulsion des coins
Soutenance de thèse – Grégory Beurier
52
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Autopoièse
Soutenance de thèse – Grégory Beurier
53
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Invariance d'échelleInformation spatiale dans les gradients
Soutenance de thèse – Grégory Beurier
54
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Emergence multi-niveaux [Heilighen 99, Simon 62]
« Le tout est plus que la somme des parties »
Soutenance de thèse – Grégory Beurier
55
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Mécanismes de la forme et attracteur
Soutenance de thèse – Grégory Beurier
56
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Modèle formel agent: une modèle récursifUn modèle de système multi-agents pour l'émergence multi-niveaux.
Beurier, Simonin, Ferber. JFSMA 03
Soutenance de thèse – Grégory Beurier
57
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Le développement de la drosophile
Séminaire LORIA
Soutenance de thèse – Grégory Beurier
58
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Universalité des gènes homéotiques
Séminaire LORIA
Soutenance de thèse – Grégory Beurier
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Le développement de la drosophile
Soutenance de thèse – Grégory Beurier
60
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Les gènes hox dans le vivant
Soutenance de thèse – Grégory Beurier
61
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Analyse
RobustesseComportement autopoïétique
Modèle récursifGénération de formesFaible complexité globale
Conception aiséePrincipes génériques
Faible expressivitéFormes peu complexesHomogénéité requise
LenteurModèle de diffusion sur « longues distances »
Définition de la structurePas d’apprentissage ni d ’évolution du modèle
Intérêts Limites
Soutenance de thèse – Grégory Beurier
62
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Analyse
ExpressivitéSuffisante pour représenter des
caractèresRéutilisation
Langage génétique de formesConception aisée
Produire une forme de référenceIndépendance métrique
Information dans l'environnement
ExpressivitéRéaction de régulation limitée
Gradients maternelsGradients indispensables
Lenteur de convergenceProcessus d'évolution trés longLimites machines
RéplicationDifficile à implémenter sur du réel
LimitesIntérêts
Soutenance de thèse – Grégory Beurier
63
Introduction et état de l’art
Une Em
bryogénieM
ulti-agentsSim
ulations &Extensions
Conclusion &Perspectives
Constat:Difficulté croissante de la conception de systèmes complexes artificiels
Besoins:Auto-diagnostic, auto-réparationStabilité dynamique, robustesse, fiabilitéAdaptation aux changements d'échelles
Solutions:Systèmes autonomes [Horn, 2001]Codage indirect du comportement macro par le niveau microInspiration du vivant : Vie Artificielle [Langton, 1987]
Epigénèse et génération d'ordre [Bedau, 1996]
Problématique
