Plan du cours - Laboratoire IBISC · 2010-09-18 · 3 Introduction - Jeux basés sur les automates cellulaires Le jeu de la vie [Conway 1970] Présenté à l’origine comme un jeu

1

Automates cellulaires

Guillaume HutzlerIBISC (Informatique Biologie Intégrative et SystèmesComplexes)Equipe LIS (Langages Interaction et Simulation)[email protected]://www.ibisc.univ-evry.fr/~hutzler/Cours/GBI_MSA

Plan du cours

Introduction Exemples simples Petit historique

Détail des choix de conception possibles Considérations théoriques Application à la modélisation et à la simulation de

systèmes biologiques Conclusion

Introduction

Un exemple simple pour commencer

L’automate élémentaire à 1 dimension Modèle à 1 dimension

– Tableau de cellules à une dimension

Espace d’états limité– Chaque cellule prend ses valeurs dans l’ensemble {0, 1}

Voisinage réduit– Le voisinage d’une cellule se réduit aux deux cellules adjacentes

Règles de transition simples– L’automate progresse par générations successives– L’état d’une cellule à la génération suivante est fonction de son état

et de l’état de ses voisines à la génération courante– Toutes les cellules changent d’état de manière synchrone

Etudié de manière systématique par S. Wolfram

Introduction - Un exemple simple pour commencer

Les règles de transition

Principe de base

Pour une cellule donnée 8 configurations possibles (23) 2 nouveaux états possibles pour

chaque configuration Au total 256 automates possibles (28) ex. : règle 18

– f(111)=0 – f(110)=0

– f(101)=0 – f(100)=1

– f(011)=0 – f(010)=0

– f(001)=1 – f(000)=0

n° règle = f(111)f(110)f(101)f(100)f(011)f(010)f(001)f(000)

Diagramme espace-temps


Un modèle de morphogénèse?

Observation Les patterns obtenus par certains automates ressemblent aux

motifs exhibés par certains coquillages Peut modéliser un processus de diffusion simple [Meinhardt &

Klingler 1987]« Shell patterns are time records of a one-dimensional pattern forming process

along the growing edge. Oblique lines result from travelling waves ofactivation (pigment production). Branches and crossing result from atemporary shift from an oscillatory into a steady mode of pigmentproduction... »


Considérations générales

Domaine très expérimental un automate est entièrement décrit par sa spécification Mais : impossible de prédire a priori l’état d’un automate sans

l’exécuter

Mais également des résultats théoriques Classes de complexité Réversibilité Jardins d’Eden et ensembles limites Lois de conservation Universalité

Applications simulation de phénomènes spatio-temporels (physique, chimie,

biologie mais aussi ingénierie, trafic, sociologie, etc.) traitement d’image et classification

2

Introduction

Petit retour historique (1)

Stanislaw M. Ulam S’intéressait à l’évolution de constructions graphiques engendrées à

partir de règles simples Principe

– Espace à deux dimensions divisé en « cellules » (sorte de feuille quadrillée)– Chacune des cellules pouvait avoir deux états : allumé ou éteint– Partant d'une configuration donnée, la génération suivante était déterminée

en fonction de règles de voisinage– Ex. si une cellule donnée était en contact avec deux cellules allumées elle

s'allumait sinon elle s'éteignait

Résultats– génération de figures complexes et esthétiques– dans certains cas, ces figures pouvaient se répliquer

Questionnements– ces mécanismes récursifs peuvent-ils expliquer la complexité du réel?– cette complexité n'est-elle qu'apparente, les lois fondamentales étant elles-

mêmes simples?

Introduction - S. Ulam

La croix de Malte (1)

http://algorithmicbotany.org/vmm-deluxe/QT/Maltese/maltese.qt

Introduction - S. Ulam

La croix de Malte (2)

http://algorithmicbotany.org/vmm-deluxe/JPEG/Maltese/maltese_obst.jpg

[Greene 1991]

Introduction


John von Neumann Travaillait à la conception d’une machine auto-réplicatrice, le

kinématon– Capable de produire n’importe quelle machine décrite dans son

programme, y compris une copie d’elle-même, à partir de matériauxtrouvés dans l’environnement

Problèmes– autoréférence de la description

– La machine doit avoir une description d’elle-même, donc également unedescription de la description...

– La description est considérée à la fois comme un programme et uncomposant

– La description est interprétée pour construire la nouvelle machine– Elle est ensuite copiée

– Similaire au fonctionnement de l’ADN (découvert plus tard)

– Conditions physiques de réalisation de la machine

Introduction


Les automates auto-reproducteurs Ulam a suggéré à von Neumann d'utiliser ce qu'il appelait les « espaces

cellulaires » (cellular spaces) pour construire sa machine– « En axiomatisant les automates [autoréplicateurs] de cette manière, on (...)

s'est résigné à ne pas expliquer comment ces éléments sont constitués dechoses réelles, particulièrement comment ces éléments sont constitués departicules élémentaires ou même de molécules (...) on considérerasimplement que des particules élémentaires dotées de certaines propriétésexistent. La question à laquelle on espère répondre, ou au moins examiner,est : quels principes sont mis en œuvre dans l'organisation de ces moléculesdans les êtres vivants fonctionnels (...) »

chaque cellule est un automate à états finis– AC à 2 dimensions avec 200 000 cellules et 29 états

– Transport de signal– Opérations logiques

– Architecture logique– Un constructeur universel– Une bande de cellules

Introduction - Petit retour historique

Les développements ultérieurs

Développements dans différentes directions Complément des travaux de Von Neumann sur les automates

cellulaires [Burks 70] Extension des travaux de Von Neumann sur les machines auto-

reproductrices [Codd 68, Langton 84] Jeux basés sur les automates cellulaires

– Jeu de la vie [Conway 70]– Brian’s brain [Silverman 84]

Etude théorique des propriétés des automates cellulaires Extension du modèle originel (coupled map lattices) Application à la modélisation de systèmes complexes (biologie,

physique, sociologie, etc.)

3

Introduction - Jeux basés sur les automates cellulaires

Le jeu de la vie [Conway 1970]

Présenté à l’origine comme un jeu mathématique grille carrée de cellules chaque cellule est dans l’état « vivante » ou « morte » l’état des cellules est initialisé de manière aléatoire à l’instant t+1, l’état de chaque cellule dépend de son propre état

et de l’état de ses 8 voisines à l’instant t– une cellule naît si elle possède trois cellules voisines vivantes

(reproduction)– une cellule meurt si elle possède

– moins de deux cellules voisines vivantes (mort par isolement)– plus de trois cellules voisines vivantes (mort par sur-population)

Résultat apparition de structures dynamiques émergentes variantes : différentes règles pour l’évolution des cellules

Introduction - Le jeu de la vie

Un exemple simple

Cellules numérotées(vivantes en jaune, mortes en rouge)

Voisinage de la cellule 12

Nombre de voisins par cellule Etat de l’automate à la générationsuivante

Introduction - Le jeu de la vie

Exemple de dynamiqueIntroduction - Le jeu de la vie

Structures particulières

Structures stables (1-périodiques)

Structures 2-périodiques

Planeur

Caractérisation des automates cellulaires

Description informelle

Framework pour une large classe de modèles discrets àinteractions homogènes

Ces modèles ont les propriétés suivantes: Discrétisation

– spatiale : espace décomposé en une grille de cellules– temporelle : évolution par pas de temps discrets

Parallélisme– les cellules évoluent simultanément et de manière indépendante

Localité– chaque cellule évolue en fonction de son propre état et de celui d’un

ensemble fini de cellules voisines Homogénéité

– la topologie des cellules est régulière– la relation de voisinage est uniforme– les règles de transition sont identiques pour toutes les cellules


Exemple simple : Greenberg-Hastings

Modèle de milieu excitable état de repos (0) état d’excitation (2) état réfractaire (ou de rémission)

Paramètres de l’automate réseau carré voisinage 4 voisins règles

– si pas de voisin

– si au – 1 voisin

–

–

4


Evolution avec 1 cellule excitée

Soit L un réseau régulier (ses éléments sont des cellules) S un ensemble fini d’états N un ensemble fini d’indices de voisinage (de taille n) tels que

une fonction de transition :

Un automate cellulaire est défini par le 4-tuple Une configuration est une fonction qui associe

un état à chaque cellule du réseau Le rôle de la fonction de transition f est de changer en

selon la relation : où désigne l’ensemble des voisins de la cellule r


Définition formelle


Choix de conception

Géométrie du réseau Voisinage Conditions aux bords Conditions initiales Ensemble d’états Règles de transition

Caractérisation des automates cellulaires - Choix de conception

Géométrie du réseau

réseau régulier = pavage périodique d’un espaceà d dimensions les cellules remplissent entièrement l’espace à d dimensions le réseau se reproduit à l’identique par des translations dans d

directions indépendantes

solutions à 1, 2, 3 dimensions


Espace à 1 dimension

Une seule possibilité tableau linéaire de cellules


Espace à 2 dimensions (1)

3 réseaux réguliers triangulaire

carré

hexagonal

5


Espace à 2 dimensions (2)

réseau triangulaire avantage = petit nombre de voisins (3) désavantage = difficile à représenter et à visualiser

réseau carré avantage = représentation et visualisation simple désavantage = anisotropie

réseau hexagonal avantage = plus faible anisotropie des trois désavantage = difficile à représenter et à visualiser


Espace à 3 dimensions

Beaucoup de réseaux possibles plus simple = réseau cubique pas de réseaux suffisamment symétriques pour les pbs

d’hydrodynamique

Problèmes spécifiques de visualisation représentation 3D

représentation par tranches 2D


Taille et forme du voisinage (1)

voisinage = ensemble des cellules avec lesquellesune cellule donnée pourra interagir

description du voisinage = ensemble des cellulesqui font partie du voisinage de la cellule (i,j)


Taille et forme du voisinage (2)

voisinage de von Neumann

voisinage de Moore

voisinage de von Neumann généralisé (rayon r)

voisinage de Moore généralisé (rayon r)


Conditions aux limites

Définition formelle donnée dans le cadre deréseaux de dimensions infinies raisonnable et nécessaire du point de vue théorique inapplicable en pratique certains problèmes ont des frontières naturelles

3 types de frontières périodique réfléchissante à valeur fixe


Frontière périoique

Extension périodique du réseau version à 1 dimension

souvent utilisé car se rapproche le plus d’un réseau de tailleinfinie

version à 2 dimensions : tore pas possible d’obtenir une sphère

6


Frontière réflechissante

Répétition du réseau à la frontière version à 1 dimension

adapté lorsque le système à simuler a des frontières

version à 2 dimensions


Conditions fixes

Valeur fixe donnée aux cellules qui constituent lafrontière


Conditions mixtes

les 3 types de conditions peuvent être combinées les différentes frontières ont des conditions différentes si une frontière a un bord périodique, le bord opposé aura

également les mêmes conditions une tube long peut être simulé en imposant des conditions

périodiques dans une dimension et des conditions réfléchissantesdans l’autre

Autres solutions étendre le réseau quand les structures dans l’AC touchent les

bords– pb = certaines structures se développent très rapidement

adopter des règles de transition spéciales pour les frontières– pb = potentiellement beaucoup de cas particuliers


Conditions initiales

Les conditions initiales déterminent souventl’évolution future de l’automate construction génération aléatoire

Considérations importantes beaucoup d’automates conservent certaines quantités

– propres au modèle : nb de particules, énergie, etc.– particulières au réseau : nb de particules dans une ligne ou une

colonne

choix de manière à ce que– les 1ères soient vérifiées– les secondes ne soient pas gênantes


Exemple : greenberg-hastings

si que des cellules rouges vague qui se propage et disparaît

si barre rouge au-dessus d’une barre jaune spirale sans fin à chaque extrémité de la barre cas particulier = une cellule rouge à côté d’une cellule jaune ->

centre d’émission de vagues périodiques

le nombre de spirales est conservé!


Espace d’états

AC = automate à états finis nb d’état fini en général petit

– pour pouvoir explorer systématiquement tous les ACs– pour s états et n voisins, le nb d’ACs est

– pour pouvoir spécifier les règles de transition explicitement et les stockerdans une table (de taille )

grand nombre d’état intéressant pour augmenter la précision– mais on pourra préférer une modélisation par équations aux dérivées

partielles si grande précision souhaitée– ACs adaptés pour systèmes avec fluctuations, où les interactions locales

sont importantes

7


Généralisation de greenberg-hastings

n états différents possibles règle de transition:

Période réfractaire plus grande


Extension = Coupled-map lattices

Espace d’états continu au lieu d’être discret


Etats à plusieurs variables

l’espace d’état S est le produit en croix desespaces de chacune des variables

médium excitable caractérisé par variable d’excitation u

– u=1 -> excité– u=0 -> au repos

variable de phase v– u=1 -> v est le temps pendant lequel la cellule est excitée– u=0 -> v est le temps avant que la cellule soit à nouveau excitable


Règles de transition

l’aspect le plus important des ACs conditionné par

la géométrie le voisinage l’espace détats

même si la règle de transition déterminedirectement l’évolution de l’AC, il est souventimpossible de prédire son évolution autrementqu’en le simulant


Spécification directe vs implicite

spécification directe = règles de transition pourtous les cas de voisinages possibles pour l’automate à 1 dimension

long et pénible possible d’introduire des « wildcards »

spécification implicite = règles données sousforme de formules


Spécification directe + wildcards

La même règle en utilisant des wildcards

faire attention à ce que la spécification permette la constructionde la table entière de manière consistante

reste plus compliquée que la spécification donnée en introduction

extension en ordonnant l’application des règles

8


Spécification directe + wildcards + symétrie

simplification en groupant les états en fonctionde la symétrie du réseau

même nb de cas que dans la spécification donnée en intro

encore plus important en 2 dimensions

la 1ère règle est valide pour toutes les configurations obtenuespar rotation du réseau

la table complète a une taille de !!!


Petits changements dans la table

un changement même infime dans la table desrègles peut conduire à des modifications trèsimportantes de la dynamique finale ex1:


Règles totalistiques (1)

Beaucoup d’ACs ne se préoccupent pas de ladisposition des cellules mais seulement du nb devoisins dans un certain état permet de simplifier la table de transition

AC totalistique ne tient compte que que de la somme des états des cellules du

voisinage

AC « outer totalistic » dépend aussi de l’état courant de la cellule concernée


Règles totalistiques (2)

La plupart du temps, on ne somme que pour unsous-ensemble des états ex: greenberg-hastings = somme des cellules dans l’état 2

dans l’exemple:– g(0) = 0– g(1) = 0– g(2) = 1– f(0,0) = 0– f(0, x>0) = 2– f(1,x) = 0– f(2,x) = 1

Un automate 1D totalistique à 3 étatsCaractérisation des automates cellulaires - Choix de conception

Règles probabilistes (1)

le nouvel état de la cellule dépend de la configuration de son voisinage des probabilités associées aux différents états possibles (la somme

des probabilités devant être égale à 1) les choix probabilistes des cellules sont indépendants les uns des

autres La fonction de transition devient :

– G vérifiant

– en général, G n’est non nul que pour quelques valeurs de sortie

important pour simuler un grand nombre desystèmes dans lesquels le fonctionnement estbruité

9


Règles probabilistes (2)

Exemple

prend en compte le fait que la propagation ne s’effectue pastoujours

front irrégulier mais plus circulaire

Un automate 1D probabiliste

Considération théoriques - Classification

Classification des automates [wolfram 84]

Classe I Pratiquement toutes les configurations initiales conduisent à la

même configuration fixe et homogène

Automate 1D élémentaire : k=2, r=1, Règle 160



Classe II Pratiquement toutes les configurations initiales conduisent à des

configurations qui se répètent périodiquement




Classe III Pratiquement toutes les configurations initiales conduisent à des

comportements qui apparaissent essentiellement aléatoires




Classe IV Emergence de structures localisées avec des interactions

complexes


10

Considération théoriques

Retour sur les automates 1D élémentaires

Théorème [Cook et Wolfram 02] La règle 110 est un calculateur universel

Modélisation de systèmes complexes

Le jeu de la vie n’est pas réversible ne présente pas de lois de conservation (ni du moment, ni de

l’énergie, ni de rien d’autre...) pas ou peu de comportement structuré à grande échelle

Réversibilité [Margolus]

Conservation de l’information Pb de la conservation exacte

la même information est visible depuis différentes positions pour inverser la dynamique, un nème de l’info de chaque voisin

doit être replacée au centre

Conservation [Margolus]

Dans les automates cellulaires classiques, laconservation n’est pas une propriété locale

Solution Redéfinir les AC pour que la conservation soit une propriété

manifestement locale AC = calcul régulier dans l’espace et le temps

– Régulier dans l’espace = structure répétée– Régulier dans le temps = séquences répétées d’étapes

Réversibilité et conservation [Margolus]

Double structure spatiale et temporelle depériode 2 Découpage de l’espace

– double structure de blocs 2x2 (lignes pleines et lignes pointillées)

Découpage du temps– distinction des pas de temps pairs (lignes pleines) et impairs (lignes

pointillées)

Lattice Gas Automata (LGA)

Exemple : règle de diffusion [Margolus]

Pas de temps pairs– rotation aléatoire horaire ou contra-horaire

Pas de temps impairs– rotation aléatoire horaire ou contra-horaire

11

Exemple : règle de diffusion [Margolus] Exemple 2 : TM Gas [Margolus]

Pas de temps pairs– rotation horaire

Pas de temps impairs– rotation contra-horaire

Sauf– 2 uns sur la diagonale -> inchangé Etape 0 : carrés continusEtape 1 : carrés pointillésEtape 2 : carrés continusEtape 4 : carrés continusEtape 3 : carrés pointillésEtape 5 : carrés pointillés

Exemple 2 : TM Gas [Margolus] Exemple 3 : dynamique de fluides [Margolus]

LGA à 6 directions avec un obstacle

Ex. 4 : Croissance d’une structure cristalline[Margolus]

Structure en échiquier or/argent

Mise à jour du sous-réseau orDiffusion du gaz et de la chaleurMise à jour du sous-réseau argentDiffusion du gaz et de la chaleur

Pas de temps pairs : mise à jour du sous-réseau or

Pas de temps impairs : mise à jour du sous-réseauargent

Quand une particule de gaz diffuse à côté d’une particule de cristal exactement, elle cristallise et émetune particule de chaleur. L’inverse peut aussi se produire

Ex. 4 : Croissance d’une structure cristalline[Margolus]

Documents

Plan du cours - Laboratoire IBISC · 2010-09-18 · 3 Introduction - Jeux basés sur les automates cellulaires Le jeu de la vie [Conway 1970] Présenté à l’origine comme un jeu