Image Gauche Titre Espace Biogame Image Gauche Titre Espace Biogame

Principes généraux des Automates Cellulaires.

Qu'est-ce qu'un Automate Cellulaire ?

Les Automates Cellulaires se présentent sous la forme d'une grille formée de cases adjacentes. Le plus souvent il s'agit d'une grille orthogonale, ce qui veut dire qu'elle est formée de cases (ou "cellules") carrées, dont on considère les 4 ou les 8 voisines. Mais on verra qu'il existe de multiples variantes possibles. . .

Les cases sont occupées par différents types de pions, dont on va suivre les transformations. Les premiers Automates Cellulaires ne différenciaient que 2 types de cases, celles occupées par un pion, et les cases vides.

La grille et ses pions forment la face visible d'un Automates Cellulaire : sa face cachée, c'est la règle (ou l'algorithme) qui régit la transformation des cases (le remplacement d'un type de pion par un autre ou par une case vide).

▼ L'intérêt des Automates Cellulaires. . .

L'intérêt des Automates Cellulaires consiste à étudier l'évolution des populations de pions qui se transforment et de guetter les configurations qu'elles prennent. Selon les cas on parle d'amas de pions (plus ou moins chaotiques ou homogènes), de regroupements caractéristiques auxquels on donne un nom. Ces configurations prennent un aspect plus ou moins ordonné, inattendu; certaines d'entres elles se transforment de façon périodiques, et donnent même l'impression de se reproduire.

Ces figures évolutives paraissent donc avoir leurs propriétés propres, si bien que l'on parle de leurs propriétés émergentes : les règles élémentaires de transformation des pions ne permettent que difficilement de prévoir leur comportement dans leur globalité. . . Une modification minime de ces règles semble diriger leur évolution de façon tout à fait différente.

On verra apparaître sur la grille des regroupements qui semblent se déplacer (tels les "planeurs" de l'algorithme du Jeu de la Vie de Conway), mais ce qui est caractéristique des Automates Cellulaires, c'est que ces déplacements sont des artefacts qui résultent de l'algorithme choisi : aucun pion ni groupe de pions ne se déplace effectivement, seule l'occupation des cases change. . . Les algorithmes d'Automates Cellulaires ne sont pas des algorithmes à objets (qui décriraient les propriétés de tel groupe de pions), mais des algorithmes à états (qui décrivent l'état d'occupation des cases, dont les changements donnent l'impression du déplacement d'objets).

C'est là aussi un des motifs d'intérêt pour les Automates Cellulaires : comment des algorithmes qui ne décrivent que des règles de transformation locales, donnent naissance à des regroupements plus ou moins étendus, qui paraissent avoir leur autonomie propre, leur organisation typique : on parle alors d'auto-organisation et d'émergence d'un ordre à partir d'un état considéré au départ comme amorphe ou chaotique.

▼ L'exécution d'un Automates Cellulaires. . .

L'exécution d'un Automate Cellulaire s'effectue par cycles, les cases se transforment toutes en même temps lors du passage au cycle suivant. On parle donc de Générations pour évoquer l'évolution des populations de pions au long des cycles d'exécution de l'algorithme.

Chaque Automate Cellulaire est caractérisé par le type de grille auquel il s'applique (le Type de Voisinage) et par la règle qui précise la façon dont les transformations s'effectuent pour chaque case en fonction de son état actuel (= son occupation par tel type de pion) et en fonction de l'état de ses voisines (= l'occupation de chacune des cases voisines). C'est dire que si l'algorithme d'un Automate Cellulaire est le même pour toute une grille, il s'applique différemment en chaque lieu selon les types de pions qui sont présents dans le voisinage.

Certains Automates Cellulaires sont définis pour des grilles comprenant des cases vides, d'autres ne s'appliquent qu'à des grilles dont toutes les cases sont occupées ("grilles pleines"). A vrai dire c'est une distinction arbitraire sur le plan logique : les "cases vides" ne sont jamais que des cases occupées par un type particulier de pions, que l'on appelle "vide". Mais la distinction est importante sur le plan algorithmique : globalement lorsque la grille est "pleine" l'algorithme est plus lent, à moins de d'utiliser un mode d'exécution de l'algorithme qui ne scrutera que les cases susceptibles de changer d'une génération à la suivante.

▼ Totalité, déterminisme, Calculabilité. . .

Tous ces Algorithmes sont "totaux" en ce sens que tous les cas de voisinages possibles sont définis, et appellent une seule transformation possible (ou l'absence de transformation). Il n'existe pas d'événement imprévu (en dehors du cas ou cet algorithme ferait appel à des facteurs aléatoires, ce qui constitue une famille particulière d'Automates Cellulaires). Ceci a pour conséquence qu'un Automate Cellulaire, à la différence d'une programme informatique, ne "plante" jamais : il peut certes avoir un comportement imprévu par son concepteur, mais rien ne le fera "boguer" au sens propre du terme.

Il n'en reste pas moins que les Automates Cellulaires sont "déterministes" : L'évolution d'une grille donnée sera toujours la même. Chaque groupe de pions identique se transformera toujours de la même façon quelque soit son emplacement sur la grille ; plusieurs groupes de pions identiques se transformeront à distance de la même façon (et au même rythme). . . sauf quand ils entreront en contact l'un avec l'autre. Bref une grille, aussi grande soit-elle, constitue un espace doté d'un temps universel. . . à la différence du temps physique décrit par la relativité einsteinienne (on pourrait parler de synchronicité pour décrire l'évolution identique de groupes de pions à distance, reliés par "rien" . . . d'autre que leur appartenance à un même espace).

Par contre l'évolution des populations de pions n'est pas calculable (à moins que l'algorithme fasse apparaître des groupes de pions périodiques. On peut alors anticiper l'état de la grille n cycles plus tard). Cela veut dire qu'il n'existe aucun procédé mathématique, permettant de prévoir par un calcul l'état des cases n générations plus tard. Pour savoir ce qu'un algorithme va donner, il faut donc le faire s'exécuter en l'appliquant à différentes populations de pions. Deux populations de pions qui paraissent semblables pourront avoir des "destins" tout à fait différents. . .

Le contraste entre déterminisme et non calculabilité est un des motifs de l'intérêt des mathématiciens pour les Automates Cellulaires. L'autre motif d'intérêt relève du contraste entre la simplicité des algorithmes défini et la complexité des figures produites ; ou encore le contraste entre le caractère régulier des règles utilisés et la variabilité des évolutions possibles dès qu'on en modifie seulement un paramètre.

► Quelques familles d'Automates Cellulaires, principales variantes : Diverses variétés d'Automates Cellulaires