Automates cellulaires

Comment des interactions simples entre des entités extrêmement simples peuvent-elles engendrer des comportements complexes, jusqu'à des mécanismes auto-reproducteurs ?

Les automates cellulaires sont des modèles abstraits simulant le fonctionnement des ordinateurs. Par là, ils sont à rapprocher des machines de Turing. Si cet aspect est important, ce n'est pas celui sur lequel nous allons nous concentrer dans le cadre de ce cours. C'est sur leurs capacités de modéliser des systèmes complexes que nous allons nous focaliser. Ces derniers sont constitués d’un grand nombre d’entités en interaction qui évoluent au cours du temps. Le comportement des entités dépend à la fois de l'environnement et des autres entités qu’elles peuvent observer localement autour d’elles. On peut citer différents exemples comme le trafic routier, les nuées d’oiseaux, occupation de nids d’abeille, tissus cellulaires ...

À partir de règles simples les automates cellulaires permettent de générer des évolutions extrêmement riches.

Les automates cellulaires ont été proposés dans les années 1950 par John von Neumann suite à une suggestion de son ami le mathématicien Stanislaw Ulam. Alors qu'il s'interrogeait sur comment concevoir une machine capable de s'auto-reproduire, Ulam l'orienta vers une question moins vaste : quelle organisation logique est suffisante pour un automate pour être capable de s'autoreproduire ?

Von Neumann fait alors le choix de considérer le problème dans un espace mathématique simple, métaphore du monde réel. L'espace est une grille régulière composée de cellules qui ont un état choisi dans un ensemble fini d'états possibles. L'évolution se fait à chaque pas de temps en fonction de règles locales.

Cette vision initiera tout un développement encore très actif autour des automates cellulaires, c'est ce que nous allons exposer partiellement dans la suite.

Description

Les automates cellulaires sont des machines à états finis évoluant sur une grille infinie, le plus souvent, et de dimension n. Les dimensions habituelles sont généralement 1 ou 2. La grille définit un espace discret et un voisinage pour chacune des cases de la grille. Cette grille peut être régulière ou non et les cases peuvent prendre différentes formes (rectangulaire, hexagonale ....). On associe à chaque case de la grille une cellule, cette dernière va alors avoir un état, ce dernier est déterminé par l'état de la cellule considérée, le voisinage et une règle de transition. L'automate cellulaire évolue en fonction de ces modifications qui peuvent se faire de façon synchrone ou asynchrone. Dans ce qui suit nous considérerons uniquement le premier cas.

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 :
  f : S^n \rightarrow S
  ;
• Un automate cellulaire est défini par le 4-tuple :
  (L, S, N, f)
  ;
• Une configuration
  C_1 : L \rightarrow S
  est une fonction qui associe un état à chaque cellule du réseau ;
• Le rôle de la fonction de transition
  f
  est de changer
  C_i
  en
  C_{i+1}
  selon la relation :
  C_{i+1}(r) = f(\{C_i(j) | j \in N(r)\})
  , avec
  N(r)
  qui désigne l'ensemble des voisins de le cellule
  r
  .

Automates de dimension 1

Considérons un ruban infini des deux cotés, subdivisé en cellules. Chaque cellule pouvant prendre une valeur dans un ensemble fini. Par commodité de représentation on va transcrire ces valeurs en une couleur. Ainsi on va utiliser deux couleurs blanc et bleu :

Chaque cellule va alors changer de couleur en fonction de la couleur de ses voisines. L’évolution d'un automate cellulaire de dimension 1 est alors représenté par un diagramme espace-temps.

Si on défini on a la fonction de transition suivante : une cellule est coloriée en bleu au temps

si au temps , parmi les deux cellules voisines immédiates, à sa gauche et à sa droite, il y a exactement une cellule bleue. L'état initial est constitué d’un ruban blanc avec une seule cellule bleue. On obtient le diagramme espace-temps suivant :

Cela n'est pas sans rappeler les triangles de Sierpiński !

En effet certains automates exhibent des diagrammes espaces-temps fractaux.

Classes d'automate

Wolfram ¹ s'est penché sur le cas des automates de dimension 1 à deux états, en considérant le voisinage immédiat. Pour une case donnée il reste donc à définir l'évolution. On peut rapidement se convaincre qu'il n'y a que 8 états à considérer :

Il n’y a donc que

règles possibles. On attribue à chaque règle la représentation en binaire de sa définition par des cases noires et blanches.La régle présentée ici est donc .

Dans son atlas, Wolfram énumère et étudie les différentes règles.

On peut déjà constater sur les exemples proposés la diversité de comportement de nos automates cellulaires. Le 126 nous produit une structure fractale alors que le 254 nous offre une pyramide noire.

En modifiant une seule transition pour créer la règle 250 vous obtenez une structure périodique.

La règle 30 est elle plus surprenante car elle nous propose un diagramme espace-temps étonnant.

Au début l'automate cellulaire semble se comporter de manière régulière et d'ailleurs cette impression subsiste si l'on considère la partie gauche du diagramme.

Sur la droite on voit apparaître des triangle de tailles différentes, sans une forme de régularité ou une "logique" sous-jacente. Wolfram a montré que le comportement de cet automate était chaotique. Des règles simples et déterministes peuvent engendrer le chaos !

Poursuivons encore l'exploration de ce bestiaire la règle 110 nous réserve des surprises. En effet l'automate correspondant à un comportement intéressant à la frontière du chaos. Si l'on regarde son évolution sur la droite il reste totalement blanc sur la droite. Sur la gauche, ce n'est pas la même chose.

Le motif bien qu'ayant l’air régulier, il apparait et disparait des séries de triangles blanc qui se propagennt et des bandes noires diagonales. Ces structures semblent interagir : elles apparaissent, se rencontrent, disparaissent. Cook a montré que cela constituait une machine universelle, cela implique que n'importe quel programme peut être simulé sur cet automate.

Classification de Wolfram

Ces classes sont encore discutées, néanmoins elles suffisent pour notre propos. Wolfram a proposé quatre classes de complexité pour les automates cellulaires en fonction leur diagramme espace-temps.

• La classe 1, le comportement est monotone, il produisent un motif homogène. Pratiquement toutes les configurations initiales conduisent à la même configuration fixe et homogène.
• La classe 2, le comportement est plus sophistiqué. Pratiquement toutes les configurations initiales conduisent à des configurations qui se répètent périodiquement. La périodicité constatée souvent ne fait que refléter la configuration initiale, néanmoins certains automates cellulaires de classe 2 ont des diagrammes espace-temps sans que la configuration initiale le soit.
• La classe 3, le comportement semble chaotique. Leurs diagrammes espace-temps semblent irréguliers. Ils ont généralement une grande sensibilité aux conditions initiales : une légère modification de la configuration initiale change fortement les diagrammes ou semble avoir des conséquences très lointaines.
• La classe 4, il y a émergence de structures localisées avec des interactions complexes. Ce type d'automate se rapproche fortement des définitions de la vie artificielle. Il y a émergence de structure.

Exercice

Réaliser en NetLogo une étude de ces automates à 1 dimension à 2 états. On écrira le programme le plus général possible auquel on fournira la règle et la situation initiale.

Automates de dimension 2

Le jeu de la vie

Conception

Automates auto-reproducteurs

Vocabulaire

Point fixe : un automate a atteint un point fixe lorsqu'il ne change plus de configuration quelque soit les itérations suivantes.

Densité : elle est mesurée par rapport à un état de chaque cellule, c'est donc le nombre de cellules d'un état donné sur le nombre total de cellules.

Synchrone : l'évolution d'un automate est synchrone lorsque chaque cellule de l’automate est mise à jour à chaque itération.

Asynchrone : une ou plusieurs cellules sont mises à jour mais pas la totalité lors d'une itération.

α-asynchronisme : à chaque itération chaque cellule est mise à jour avec une probabilité α.

Asynchronisme total : à chaque itération une seule cellule, choisie aléatoirement, est mise à jour. Il existe deux types d’asynchronisme total : (1) à mémoire : si l'automate possède

n

cellules, alors on conserve une trace des cellules mises à jour de sorte que durant toutes les

n

itérations, chaque cellule n’est mise à jour qu’une seule fois. (2) Sans mémoire : à chaque itération une cellule est choisie aléatoirement sans tenir compte du passé.

Robuste : un automate est dit robuste au sens du synchronisme s'il conserve ses propriétés quel que soit le type de synchronisme / asynchronisme choisi.

1. S. Wolfram. (2002) A new kind of science. Champaign, IL: Wolfram Media