Automates cellulaires

Texte au format PDF : automates.pdf

Un certain nombre d’algorithmes de calcul, relativement simples dans leur conception, peuvent prétendre à modéliser des phénomènes de base des sciences de la vie, voire de sciences plus dures comme la physique. Un des premiers artisans de ce genre de choses fut John Von Neumann, un des concepteurs des ordinateurs, qui écrivit même un ouvrage sur la question. Un des exemples les plus frappants est certainement le jeu de la vie de John Conway : à partir d’un algorithme simple de vie et de mort, on voit des formes caractéristiques se former, se déplacer, exister ou mourir.

En tout état de cause on peut éventuellement considérer ces automates comme les briques de base de la construction de formes biologiques (ou autres) et de nombreux scientifiques se penchent dessus depuis l’apparition des ordinateurs. De nombreux sites ou ouvrages traitent ce genre de question, voir par exemple

http://www.mines.u-nancy.fr/~tisseran/cours/objet/jeu_vie.html

http://matthieu.walraet.free.fr/automate/automate.html

http://www-ensimag.imag.fr/eleves/Franck.Vivien/maths/automates/auto1.html#SECTION00100000000000000000

et pour les livres : Chaleur et Désordre, Belin (Pour la Science), 1999 (http://www.editions-belin.com/csl/master.asp)

ainsi que La Recherche, janvier 2003 (http://www.larecherche.fr/arch/03/01).

Pour notre part nous allons regarder deux modèles : le premier que nous baptiserons du doux nom de règle 110 et le second baptisé automate de Conway fixe.

L’automate règle 110 est construit ainsi : sur un damier 255x255 chaque cellule est soumise à la règle suivante :

si [cell(x–1, y)=ai et cell(xy)=bi et cell(x+1, y)=ci] alors cell(x, y+1)=d;

les valeurs ai, bi, ci, di sont toutes 0 ou 1 ; il y a donc 8 configurations possibles au rang y (par exemple (ai, bi, ci)=(1, 0, 1)) et pour chacune on donne une valeur di au rang y+1. On a donc 256 règle différentes qui donnent autant de configurations possibles. La décomposition binaire d’un nombre entre 0 et 255 donne toutes les règles possibles, aussi numéroterons nous les-dites règles avec ces valeurs. Par exemple la règle 225 est donnée par

ai

bi

ci

Résultat : di

1

1

1

1

1

1

0

0

1

0

1

0

0

1

1

0

1

0

0

0

0

1

0

1

0

0

1

1

0

0

0

1

(on a bien ).

Nous partons alors d’une graine (une cellule valant 1) en bas à gauche et nous obtenons la représentation suivante en noircissant les cellules valant 1, en laissant blanches les autres :

fig- 1 : règle 225

Cette règle montre grosso-modo les trois types de comportement de l’automate :

* tout l’espace est recouvert par un motif régulier (le triangle noir ou les bandes verticales)

* une partie de l’espace est recouvert par un motif pseudo-régulier

* une partie de l’espace est recouvert par un motif pseudo-régulier pouvant devenir chaotique par endroits.

Voici un semblant de classification des différentes règles :

 

Règles 135 – 141

 

Les trois motifs qui suivent présentent des zones de chaos…

Règles 62 - 114 – 131 - 137

Règles 166 – 172

Règles 60 - 80 à 83 - 88 à 91 – 112 – 113 – 129 – 133 – 153 – 165 - 195

Règles 117 – 126 – 142 – 241

 

 

Règles 145 – 158 – 190 – 193 - 206 – 209 – 238

Ces représentations sont régulières et bizarres à la fois… Toutes les règles donnent des résultats différents.

Règles 138 – 154 – 177 – 181 – 202 – 225 – 229 – 245

On trouve ici une combinaison des différentes règles précédentes.

Autres règles : les motifs obtenus sont réguliers avec des variations quand même assez importantes.

 

Notre deuxième automate se construit de la manière suivante : à chaque étape une cellule a huit voisines qui peuvent être dans l’état 0 (morte) ou 1 (vivante) ; la règle est alors la suivante :

- si la somme des valeurs des cellules environnantes est comprise entre deux valeurs a et b, alors il y a création de cellule (0 devient 1) ou maintien en vie (1 reste 1) ;

- si la somme des valeurs des cellules environnantes est inférieure à c ou supérieure à d alors la cellule meurt (dans le premier cas par manque de contact, dans le deuxième par étouffement) ;

- dans les autres cas il y a maintien de la cellule dans son état précédent.

Le nombre de situations devient nettement plus important, d’autant plus que les conditions initiales vont jouer un rôle important. Il n’empêche que pour beaucoup de situations il y a croissance ou plutôt stabilisation des structures obtenues.

Voici par exemple ce que l’on obtient avec (ab)x(c, d)=(3, 6)x(2, 7) après 130 itérations, les 5 cases du coin bas gauche valent 1 au premier coup puis 0 après.

fig- 2 : automate régulier (130 itérations)

Comme nous sommes désagréables, nous allons changer brutalement la règle du jeu et nous passons à (ab)x(c, d)=(4, 6)x(2, 6) pendant 20 itérations supplémentaires :

fig- 3 : désagrégation du précédent (+20 itérations)

Le résultat est proprement stupéfiant… là où régnaient l’ordre et l’harmonie n’apparaissent plus que chaos et destruction ! Faisons tourner encore quelques temps, nous voyons apparaître une structure plus ordonnée qui est quasiment stable dans le temps. C’est un peu comme dans les systèmes dynamiques, un attracteur apparaît et la structure se stabilise.

ig- 4 : la même 40 coups plus tard

Modifions encore une fois nos valeurs en passant par exemple à (ab)x(c, d)=(3, 5)x(2, 7) ce qui devrait favoriser légèrement la vie :

fig- 5 : (ab)x(c, d)=(3, 5)x(2, 7), coups 380 et 420

Il est intéressant de remarquer que la création de nouveau matériau se fait souvent par bandes plus ou moins régulières, la structure précédente restant identique.

fig- 6 : 520 itérations

On peut remarquer une sorte de membrane qui s’est formée au milieu… la figure obtenue ici est stable ! Elle ne bouge plus.

Pour terminer si vous cliquez sur la vignette ci-dessous vous pouvez charger un petit film (attention au temps de chargement : 3 Mo...) obtenu en démarrant sur un tableau rempli de 1, puis 140 itérations avec (3, 5)x(2, 6) suivies de (3, 5)x(2, 5) quelques coups puis (3, 4)x(2, 5) et enfin (3, 4)x(2, 4) pour zigouiller tout le monde.

 

Voilà tout pour l’instant (01/2003) sur le sujet, mais il y aura sûrement des rajouts ultérieurs (je suis preneur de tout ce qui me sera envoyé bien sûr).