Titre : Robustesse et émergence dans les systèmes complexes : le modèle des automates cellulaires. Ci-dessous une partie des résumés qu'il ma fallu écrire à diverses occasions administratives. Ils concernent tous la même thèse, seule la longueur change.
Vous pouvez télécharger ma thèse ici. L'introduction devrait être lisible par le grand public, tandis que les résumés ci-dessous sont destinés à des collègues. Certains chapitres sont repris des articles suivants : Coalescing cellular automata, Coalescing cellular automata: Synchronization by common random source, An exhaustive experimental study of synchronization by forcing on elementary cellular automata et Combined effect of topology and synchronism perturbation on cellular automata: Preliminary results.
Thèse soutenue le 8 décembre 2008, devant la commission d'examen formée de :
| Directeur de thèse : | Michel Morvan |
| Rapporteurs : | Jacques Demongeot et Eric Goles |
| Examinateurs : | Hugues Berry, Paul Bourgine et Bruno Durand |
The first part studies experimentally the apparition of directed percolation in cellular automata, in particular in the framework of damage spreading. The last chapter of this part proves an equivalence between a class of probabilistic cellular automata and asynchronous cellular automata.
The second part studies in a first chapter the interplay of both mentioned perturbations: asynchronism and topology. While the usual model is defined on a Zd grid, we study a grid where some links are temporarily broken. The a second chapter proves a few theoretical properties of the minority rule when the topology is a tree.
In this thesis, we conducted both experimental and theoretical studies. A transverse question is formal simulations between models. The aim of those works is, in the long term, to know how to get systems with a predefined global behavior, or how to make robust against some perturbations a given complex system.
L'objet de ce travail est de mieux comprendre ce qui se produit lorsque l'on perturbe un système complexe, en utilisant les automates cellulaires comme modèle. Nous nous intéressons principalement à deux perturbations. La première concerne l'écoulement du temps : contrairement au modèle habituel, nous utilisons des mises à jour asynchrones, c'est-à-dire que, à chaque étape, seulement une partie des cellules sont mises à jour. L'autre perturbation concerne la topologie, c'est-à-dire le graphe d'interaction entre les cellules.
Une première partie étudie expérimentalement l'apparition de la percolation dirigée dans les automates cellulaires, notamment dans le cadre du « damage spreading ». Le dernier chapitre de cette partie prouve une équivalence entre une classe d'automates cellulaires probabilistes et les automates cellulaires asynchrones.
La seconde partie étudie dans un premier chapitre l'interaction des deux perturbations évoquées : asynchronisme et topologie. Alors que le modèle habituel utilise une grille Zd, nous étudions une grille où certains liens sont temporairement coupés. Puis un second chapitre démontre des propriétés théoriques sur la règles minorité lorsque la topologie est un arbre.
Nous avons dans cette thèse mené à la fois des études expérimentales et des études théoriques. Une préoccupation transversale est la simulation formelle entre modèles. L'enjeu de ces travaux est, à terme, de savoir comment obtenir des systèmes ayant un comportement global prédéfini, ou bien comment rendre robuste à certaines perturbations un système complexe donné.
L'objet de ce travail est de mieux comprendre ce qui se produit lorsque l'on perturbe un système complexe, en utilisant les automates cellulaires comme modèle. Nous nous intéressons principalement à deux classes de perturbations. La première concerne la dynamique, c'est-à-dire les règles régissant l'évolution du système pour passer d'une étape de temps à la suivante. Par exemple, à chaque étape de temps, on met à jour seulement une partie des cellules (au lieu de mettre à jour toutes les cellules de façon synchrone). La seconde concerne la topologie : on modifie le graphe des connexions entre cellules (le graphe des interactions), par exemple en coupant quelques liens.
Dans une première partie nous utilisons des couplages, ce qui consiste à faire évoluer deux copies d'un système selon la même règle, pour le même nombre d'étapes de calcul, mais avec des conditions initiales différentes.
Au premier chapitre de cette partie (chapitre 3), le couplage consiste à modifier certaines cellules pour qu'elles soient dans le même état entre les deux copies. Le couplage étudié au chapitre 4 se place dans le cadre de la dynamique asynchrone : à chaque pas de temps, une partie seulement des cellules est mise à jour. Le couplage consiste alors à mettre à jour le même ensemble de cellules dans les deux copies. Autrement dit, les deux copies partagent la même source d'aléatoire pour décider où appliquer la règle locale.
Dans ces deux modèles, nous observons que, pour certains paramètres, les deux copies deviennent identiques. Nous appelons ce phénomène coalescence et en proposons quelques interprétations en termes de modélisation et en termes de systèmes dynamiques.
Pour certains automates cellulaires élémentaires, nous observons une transition de phase, qui appartient dans presque tous les cas à la classe d'universalité de la percolation dirigée. Au chapitre 5, nous commençons une validation formelle de cela. Précisément, nous démontrons que certains automates cellulaires déterministes asynchrones font apparaître une transition de phase de percolation dirigée. Pour cela, nous proposons une définition de simulation entre automates cellulaires utilisant une source d'aléatoire ; notion qui conserve la densité asymptotique donc l'exposant critique associé. Nous montrons alors l'équivalence entre une classe d'automates cellulaires probabilistes (où l'on rencontre la percolation dirigée) et les automates cellulaires déterministes asynchrones.
Dans une seconde partie, nous étudions l'interaction de deux perturbations : asynchronisme et modification de la topologie.
Au chapitre 6, nous vérifions l'intérêt de combiner les deux perturbations. Nous observons que pour certains automates, la robustesse à l'asynchronisme est augmentée lorsque la topologie n'est plus régulière. Pour d'autres, les deux perturbations se combinent de façon non linéaire voire non monotone : les deux perturbations appliquées simultanément ont un effet opposé à l'application d'une seule des deux perturbations.
Au chapitre 7, nous poursuivons l'étude de l'influence de la topologie en comparant plusieurs graphes et en appliquant la même règle d'évolution (la règle minorité) à chacun. Pour chaque graphe, nous déterminons le temps transitoire, ou temps pour atteindre l'ensemble limite (hitting time), et décrivons la structure de cet ensemble limite, ou attracteur. On note une distinction sur le temps transitoire (polynomial ou exponentiel) entre les arbres de degré maximum 3 et ceux de degré maximum 4 ou plus.
Nous avons mené à la fois des études expérimentales (classifications des automates cellulaires, mesure de transitions de phase) et des études théoriques (simulations entre modèles, comparaison de topologies pour la règle minorité). L'enjeu de ces études serait, à terme, de savoir obtenir des systèmes ayant un comportement global prédéfini, ou bien de rendre robuste à certaines perturbations un système complexe donné.
L’objet de ce travail est de mieux comprendre ce qui se produit lorsque l’on perturbe un système complexe, en utilisant les automates cellulaires comme modèle. Nous nous intéressons à ce problème dans le cadre de différents types de perturbations. La première classe de perturbations étudiées concerne la dynamique, c’est-à-dire les règles régissant l’évolution du système pour passer d’une étape de temps à la suivante. Par exemple, on ne met plus à jour de façon synchrone toutes les cellules (contrairement au modèle classique d’automate cellulaire). La seconde perturbation concerne la topologie : on modifie le graphe des connexions entre cellules (le graphe des interactions), par exemple en coupant quelques liens d’une grille régulière.
Cette thèse est dans la lignée des travaux de Nazim Fatès qui s’intéressait à la notion de robustesse des automates cellulaires : il a constaté que certains automates cellulaires gardent « le même type de comportement » lorsqu’ils sont perturbés alors que d’autres automates cellulaires changent leur comportement soit de façon continue, soit de façon « brutale » (on parle alors de transition de phase).
La mise en évidence de différents comportements sous les perturbations que nous avons appliquées a permis de dégager plusieurs types questions, que nous nous sommes alors posées tout au long de la thèse.
La suite de notre thèse nous a permis d’aborder ces problèmes généraux ainsi que quelques questions spécifiques à certaines perturbations, et d’y répondre en partie.
La première partie s’intéresse à la comparaison de deux réalisations d’un même système. Nous utilisons la notion de couplage, qui consiste à faire évoluer deux copies d’un système selon la même règle, pour le même nombre d’étapes de calcul. Les deux copies sont dites couplées car on ajoute au modèle un ingrédient qui lie les deux copies.
Nous avons choisi comme ensemble d’automates cellulaires les automates cellulaires « élémentaires » (ce sont les automates cellulaires unidimensionnels de plus proches voisins à deux états). Ils sont parmi les plus simples, et ont donc été largement étudiés, ce qui permet de comparer nos résultats à des classifications existantes.
Dans un premier chapitre, le couplage consiste simplement à modifier certains sites pour qu’ils soient dans le même état entre les deux copies. En d’autres termes, nous modifions de façon exogène l’état d’une copie afin de la rendre plus ressemblante à l’autre copie. Nous observons que seuls deux types de comportement sont possibles face à ce couplage; la classification ainsi obtenue a des points communs avec d’autres classifications connues mais ne leur est pas identique.
Le couplage étudié au deuxième chapitre se place dans le cadre de la dynamique asynchrone.
Formellement, on ajoute à la définition classique la donnée d’une fonction probabiliste,
dite fonction de mise à jour, qui à chaque pas de temps donne l’ensemble des cellules que l’on met à jour.
Plusieurs fonctions sont possibles, qui définissent plusieurs dynamiques :
la dynamique synchrone (mettre à jour toutes les cellules),
la dynamique « totalement asynchrone » (mettre à jour une cellule tirée au sort),
et la dynamique « partiellement asynchrone »
(tirer au sort indépendamment pour chaque cellule si elle est mise à jour ou non).
C’est la dynamique partiellement asynchrone que nous retenons pour ce chapitre.
Le couplage appliqué dans ce chapitre est moins « intrusif » et porte seulement sur le choix des cellules à mettre à jour. Il consiste simplement à choisir pour les deux copies le même sous-ensemble de cellules à mettre à jour. Autrement dit, les deux copies partagent la même source d’aléatoire pour décider où appliquer la règle locale.
Dans ces deux modèles, nous observons que, pour certains paramètres, les deux copies deviennent identiques.
Nous appelons ce phénomène coalescence.
Dans le cas du couplage par les mises à jour, ce phénomène a une première application
lors de simulations numériques de systèmes complexes dans les conditions de coalescence.
En effet, il montre que simuler une évolution permet de prédire toutes les autres partageant la même source d’aléatoire pour les mises à jour.
De plus, quelle que soit la configuration initiale, la simulation atteint rapidement le régime permanent.
Si l’on adopte le point de vu des systèmes dynamiques,
ce phénomène est un exemple de système où deux instances convergent naturellement vers l’ensemble limite,
mais de plus finissent par être sur le même point de cet ensemble en même temps.
Par ailleurs, la source d’aléatoire pour la configuration initiale n’a pas d’influence :
cette dynamique aléatoire avec un comportement irrégulier est insensible aux perturbations de la configuration initiale
et n’entre donc pas dans la définition des systèmes chaotiques.
Nous étudions alors plus précisément quels paramètres font apparaître la coalescence, et observons une grande richesse de comportements, pour lesquels nous proposons une classification. Dans l’une de ces classes, le comportement est une transition de phase. Nous montrons expérimentalement que, pour les deux modèles, cette transition de phase appartient la plupart du temps à la classe d’universalité de la percolation dirigée. Nous obtenons donc de nouveaux modèles de percolation dirigée.
Nous avons donc construit un protocole expérimental après avoir étudié l’effet des différents paramètres qui définissent une expérience (variations de taille des configurations, du taux de synchronisme, etc.). En particulier, nous avons étudié l’effet de la taille du système (le nombre de cellules de l’automate cellulaire). Ceci permet dans le cas des transitions de phase d’écarter toute influence de ce paramètre (pour des tailles suffisamment grandes) et donc de généraliser les résultats à une taille infinie.
Le premier couplage a été publié à la conférence internationale JAC tandis que le second
a été publié dans le Journal of Cellular Automata.
Dans un troisième chapitre, nous avons alors cherché une validation formelle de ce résultat :
démontrer que certains automates cellulaires asynchrones font apparaître une transition de phase de percolation dirigée.
(En effet les deux chapitres précédent n’ont fait que mesurer expérimentalement cette transition de phase.)
Pour cela, nous considérons
d’une part les automates cellulaires asynchrones (pour lesquels la percolation dirigée a été identifiée
par des travaux précédents),
et d’autre part un modèle unanimement reconnu de percolation dirigée : l’automate de Domany-Kinzel.
Nous avons alors montré une simulation formelle entre deux classes d’automates cellulaires.
Pour cela il nous a également fallu proposer une formalisation de la notion de simulation
pour des automates cellulaires faisant intervenir des probabilités.
Ce dernier chapitre sera soumis prochainement pour publication.
Dans une seconde partie, nous nous intéressons à des modifications de la topologie. La topologie est la façon dont est structuré l’espace, c’est-à-dire, dans le cas des automates cellulaires, le graphe d’interaction entre les cellules. Le modèle le plus utilisé d’automate cellulaire est défini sur une topologie régulière de la forme Zd; c’est ce graphe que nous perturbons.
Nous étudions comment des perturbations de la topologie se combinent avec la perturbation du synchronisme définie dans la première partie. Combiner les deux perturbations nous a semblé plus riche que d’étudier seulement la perturbation de la topologie (même si un travail futur pourra se pencher plus spécifiquement sur ce point). En particulier, ceci ouvre des questions telles que « les perturbations se combinent-elles de façon linéaire? », « existe-t-il des automates robustes à plusieurs perturbations? », « une perturbation rend-elle l’automate robuste à l’autre perturbation? ». Par exemple, un comportement intéressant est celui du jeu de la vie : cet automate cellulaire est sensible à l’asynchronisme, mais sa sensibilité est fortement réduite lorsque l’on perturbe légèrement la topologie.
Pour valider cette approche, nous commençons par appliquer ces deux perturbations à l’ensemble des automates cellulaires élémentaires.
Le but est de répondre aux questions précédentes en étudiant les différents comportements possibles,
de découvrir d’éventuels comportement inattendus, et de vérifier que combiner ces deux perturbations a du sens.
Toutes les modifications introduites sont temporaires et tirées au sort à chaque étape :
nous utilisons donc des perturbations dynamiques.
Le protocole expérimental que nous proposons se base sur l’obtention de surfaces dans un espace à trois dimensions où les axes x et y représentent les deux perturbations et où l’axe z représente la densité moyenne du régime permanent, la pertinence de cette quantité ayant été validée par des travaux précédents. Nous regroupons les automates cellulaires en fonction du type de surface mesurée et nous examinons alors les automates cellulaires groupe par groupe. Cet examen détaillé permet de mettre à jour différents comportements bien distincts :
Ce travail a débouché sur la publication d’un article à la conférence internationale ACRI.
En complément de l’étude expérimentale du premier chapitre,
nous étudions dans un second chapitre des aspects théoriques de la combinaison des perturbations du synchronisme et de la topologie
(i.e. du graphe sur lequel sont placées les cellules).
Par une étude comparative de plusieurs graphes sous la dynamique asynchrone, nous espérons mieux comprendre l’influence de la topologie.
Les graphes retenus sont tout d’abord des topologies régulières (cycle, graphe complet) puis
nous nous concentrons sur les arbres.
Les arbres sont en effet une topologie simple, sans boucles, adaptée à une première étude.
Ce sont les arbres qui constituent la principale difficulté de cette étude.
Pour permettre la comparaison de ces topologies, nous appliquons la même règle à chaque graphe. Nous devons choisir une règle qui soit à la fois intéressante et adaptable à tout graphe; la règle minorité répond à ces critères. Cette règle fait partie de la classe des automates à seuil dont l’étude est connue pour être difficile quand le graphe est arbitraire ou quand il y a des interactions de poids négatifs. Puisque nous sommes dans les deux cas en même temps, nous avons choisi des graphes simples et une règle uniforme : toutes les cellules utilisent la même règle (ce qui n’est pas le cas de tous les automates à seuil).
Pour chaque graphe, nous déterminons le temps transitoire, ou temps pour atteindre l’ensemble limite (aussi appelé hitting time), et décrivons la structure de cet ensemble limite, ou attracteur. On note une distinction sur le temps transitoire (polynomial ou exponentiel) entre les arbres de degré maximum 3 et ceux de degré maximum 4. Nous proposons également un algorithme linéaire pour tester l’appartenance d’une configuration à l’ensemble limite.
Ce second chapitre est un travail en commun avec Damien Regnault et Éric Thierry.
Une préoccupation transversale dans la thèse est la simulation formelle entre différents modèles. Parfois nous ramenons un modèle à un autre, ce qui permet de restreindre a priori le champ d’étude sans perte de généralité. Réciproquement, des résultats expérimentaux donnant des valeurs proches suggèrent parfois l’équivalence entre certaines règles, et nous confirmons cela a posteriori de façon formelle.
De plus, un chapitre est consacré à l’équivalence entre une classe d’automates cellulaires probabilistes et les automates cellulaires (déterministes) asynchrones. Nous avons pour ce dernier point été amenés à proposer une définition de simulation entre automates cellulaires utilisant une source d’aléatoire (tels que les automates cellulaires asynchrones et les automates cellulaires probabilistes), généralisant la notion classique de simulation entre automates cellulaires déterministes. Ceci nous permet d’établir l’équivalence entre un modèle de percolation dirigée et les automates cellulaires asynchrones.
Tout au long de la thèse, nous avons développé un outil de simulation permettant de perturber indépendamment les différents constituants d’un automate cellulaire (configuration initiale, synchronisme, règle de transition, topologie...) et d’intégrer de nouvelles idées facilement. En effet, il n’existait pas à notre connaissance d’outils permettant de réaliser ces deux opérations. (Nous avons commencé par utiliser celui de Nazim Fatès, mais nous avions besoin de stocker et échantilloner facilement les paramètres, et surtout nous avions besoin d’une exécution plus rapide que ce que permet Java.) Ce logiciel n’a cessé de s’enrichir au fur et à mesure des besoins qui apparaissaient. Il compte maintenant environ 5000 lignes de code (noter qu’un programme en OCaml est typiquement 4 fois plus compact que son équivalent en C). Le code source est disponible.
L’étude de la robustesse à des perturbations telles que l’asynchronisme ou des modifications de la topologie nous a donc conduit à choisir des paramètres et à construire des protocoles pour distinguer clairement différents comportements. Nous avons montré que de petites modifications de certains paramètres tels que le taux de synchronisme peuvent avoir une grande influence sur l’évolution du système. Formulé dans l’autre sens, ces résultats trouvent une application en modélisation : cela signifie que certains automates ne peuvent être pris comme modèle d’un phénomène biologique réel puisque leur comportement dépend fortement de choix arbitraires faits lors de la modélisation.
Nous avons mené à la fois des études expérimentales (classifications des automates cellulaires, mesure de transitions de phase) et des études théoriques (simulations entre modèles, comparaison de topologies pour la règle minorité). Les techniques que nous avons utilisées doivent maintenant être appliquées sur des types d’automates cellulaires potentiellement « plus complexes », notamment des automates cellulaires modélisant des systèmes réels, ou inspirés par ces derniers. L’enjeu de ces études serait, à terme, de comprendre comment obtenir des systèmes ayant un comportement global prédéfini, ou bien comment rendre robuste à certaines perturbations un système complexe donné.
This document was translated from LATEX by HEVEA.