Chapitre 2

Automates Cellulaires

Processus Cognitifs Distribués

Jean-Paul Sansonnet

1 Principe des Automates Cellulaires

2 Automates à une dimension

3 Le Jeu de la Vie de Conway

4 Automate Autoreproducteur de Langton

1 Principe des Automates Cellulaires

• Automates Euclidiens

• Espace substrat des états

Les automates cellulaires ont pour caractéristique de posséder un espace substrat des états qui est muni d'une géométrie. Souvent, cette géométrie est de type euclidien ; on travaille dans un tableau fini, à N dimensions :
    - N = 1 : on a un vecteur,
    - N = 2 : on a une matrice,
    - etc.

On peut imaginer d'autres types de réseaux que le réseau “carré” (on dit aussi Manhattan) ci-dessus

Certains types de voisinages sont équivalents à des réseaux carrés ou bien présentent des dualités entre-eux.

• Types de voisinages dans une matrice

Si on considère un espace euclidien à deux dimensions, i.e. une simple matrice, on eput définir plusieurs types de voisinages pour un point de la matrice :
-- des voisinages d'ordre 1 : les cases à une distance de d = 1 d'un point quelconque ,
-- des voisinages d'ordre k > 1 : toutes les cases à une distance d <= k d'un point quelconque ,

Pour un voisinage d'ordre 1 on considère généralement trois types de schémas classiques :

Le voisinage de Moore est l'union du voisinage NEWS (pour North, East, West, South) et du voisinage en croix.

• Fonctions élémentaires d'accès aux voisins

Nous nous plaçons dans le cas d'un espace euclidien borné à N dimensions défini par une liste de bornes de dimensions ld, possédant N éléments. La position d'une case est donnée par une liste d'indices li, possédant N éléments.

On définit les deux fonctions d'accès aux voisins élémentaires : ISucc et IPred. Elles prennent comme arguments li, ld et l'axe a (la dimension sur laquelle on veut accéder à un voisin). Elles renvoient l'adresse du successeur (respectivement du prédécesseur) de la case désignée par li.

• Espace euclidien torique

Un argument optionnel w des fonctions IPred et ISucc permet de spécifier la valeur des cases aux bords de l'espace substrat ; si w = wrap alors on considère que l'espace euclidien est torique, i.e. que le successeur de la dernière case d'un axe a est la première case de cet axe (resp. le prédécesseur de la première case est la dernière du même axe).

• Trois voisinages typiques : News, Cross, Moore

A partir des fonctions primitives IPred et ISucc on peut définir les trois fonctions de voisinage typiques : INews, ICross, IMoore :

Les fonctions de voisinage ci-dessus définissent un champ local autour de la case d'adresse li={i,j}. On peut demander, pour un tableau t au point li, les valeurs de ce champ grâce à Fieldvalue

•Fonction d'inversion du champ : WhoHasValue

Inversement, la fonction WhoHasvalue interroge le champ autour d'un case et renvoie la liste des indices des cases qui possèdent une valeur v que l'on spécifie

• Accès élémentaires aux voisins

Soit la matrice lettres de dimensions 5 × 5 qui possède comme état initial les valeurs suivantes

Exemple 1 : On cherche le prédécesseur de la lettre "l" qui est à l'adresse {3,2} sur la colonne (i.e. selon la dimension 1 de la matrice). On obtient l'indice de l'élément désiré par

Ensuite, on peut demander la valeur de la case i

Exemple 2 : On cherche le successeur en ligne (i.e. selon la dimension 2 de la matrice) de la lettre "o" d'adresse {3,5}. On utilise l'option par défaut (wrap) qui spécifie que la matrice est rebouclée sur elle-même en un tore à deux dimensions

• Champ de valeurs sur un voisinage

On peut demander la liste des adresses des voisins de "m" selon une fonction de voisinage comme Moore

Ensuite, il est possible de demander le champ des valeurs assocées à ce voisinage

Si on se trouve au bord, on peut utiliser l'option par défaut (wrap) ou bien spécifier la valeur que doit avoir toute case qui se situe hors de la matrice lettres

On voit que trois des cases demandées sont dans le vide.

• Etude d'un processus de lissage : Smooth

• Le processus de lissage : Smooth

Le processus de lissage Smooth est un processus discret. Au temps n+1, il  fait la moyenne des valeurs entre une case x et ses quatre voisines en mode News au temps n. Cela correspond à la formule

La fonction Smooth reprend cette formule et l'applique en parallèle à tous les éléments d'un tableau t

Exemple : Une valeur isolée (1) est placée au centre d'un tableau à deux dimensions, nommé pic, contenant une valeur neutre (0)

• Lissage d'un pic

Nous prenons comme condition initiale du processus de lissage Smooth le tableau pic défini plus haut

Le pic se répand sur la surface de l'automate comme une tâche d'huile. Au bout d'un certain nombre d'étapes, toutes les cases ont la même valeur.

• Visualisation bidimensionnelle de Smooth

La fonction de service SmoothTable2D effectue l'affichage en 2D de la séquence de tableaux qui constitue la trajectoire du processus Smooth

•Smooth appliqué  à une CI choisie aléatoirement

On part d'un tableau rempli initialement avec des valeurs aléatoires. Au bout d'un certain temps, on voit apparaître une configuration fixe

Entre deux étapes, il y a conservation de l'énergie globale, c'est juste un déplacement des valeurs sur l'échiquier. Si on calcule la somme des valeurs sur un échiquier elle est constante au cours du processus :

• Image fantôme

En considérant des conditions initiales aléatoires, on constate qu'il apparaît une forme lors de l'affichage

• Calcul de la "Dérivée" de Smooth

On calcule de la "dérivée" du processus Smooth i.e. on plote les différences entre les tableaux successifs. On voit que le processus Smooth est qualitativement (i.e. en valeur relative) égal à sa dérivée

Le processus dérivé a le même comportement que le processus de lissage Smooth : il tend qualitativement (i.e. en valeur relative) vers une forme stable.

• Application au lissage d'une image

On se donne une image noir et blanc 32 × 32 comme condition initiale

• Problématique de l'évolution d'une population d'habitants bicolores

On considère une zone urbaine vierge où l'on installe deux groupes de population présentant une différence quelconque : un groupe est dit clair et l'autre foncé. Les deux groupes sont mélangés au départ. On considère que les habitants ont le comportement suivant selon la nature de leur voisinage immédiat

1. Si leur voisinage leur ressemble, ils restent,
2. Si ils n'ont pas assez de voisins du même groupe, ils déménagent un peu plus loin, là où il y a de la place.

   

• Fonction de transition  de la population

La fonction d'évolution de la population travaille sur un voisinage de Moore. On calcule le champ (FieldValue) associé à un habitant et on compte combien il y a d'habitants de même groupe dans ce champ. Si le compte <= p alors on cherche une case vide dans le voisinage de Moore (WhoHasValue[...,0]) et si il y en a on en tire une au sort et on déménage vers cette case.

• Exemple d'évolution : p = 3

La population initiale est placée dans une zone M1 ayant 5 × 8 cases possibles. Elle est composée de manière aléatoire et équirépartie de case vides (état 0) de cases occupées par un habitant Cyan-clair (état 1) et de cases occupées par un habitant Rouge-foncé (état 2).

• Exemples d'évolution : p = 2, p = 4.

Exemple : p = 2. Le regroupement est accéléré (à vérifier )

Exemple : p = 4. Le regroupement ne se fait pas.

• Code des fonctions pour les automates

2  Automates à une dimension

• Automates à une dimension et trois entrées

• Automates à une dimension

Un automate linéaire ou à une dimension est composé d'une structure spatiale à une dimension (un vecteur) dont chaque élément possède un état local et d'une fonction de transition locale. Le processus lié à l'automate consiste à itérer la fonction de transition locale en parallèle sur tout le vecteur d'états.

Dans un automate à une dimension, la structure de voisinage est très simple : chaque cellule possède un voisin de gauche et un voisin de droite. Concernant les bords, on peut prendre trois décisions :

• Automates Linéaires Booléens

Les automates linéaires booléens ont des états locaux ϵ {0,1}. La fonction de transition locale prend trois entrées :
    - la valeur locale,
    - la valeur du voisin de gauche,
    - la valeur du voisin de droite.

Une configuration est donc représentée par un triplet de bits. Il existe donc configurations d'entrée différentes. Une fonction de transition est définie en spécifiant pour chacune de ces 8 entrées l'état résultant € {0,1}. Il y a donc combinaisons possibles qui définissent 256 fonctions de transition locales possibles.

Ci-dessus, la fonction n° 90 (soit 01011010 en binaire)

• Définition de la fonction de transition globale

La fonction de transition LinearStep globale sur l'automate L calcule pour chaque état L[[i]] de l'automate, la configuration binaire v en combinant le voisin de gauche, la case courante et le voisin de droite en base 2 :

La valeur de la  nouvelle case est donnée par la fonction de transition locale f appliquée à v.

Pour la première case et la dernière case, il manque un voisin : on décide qu'il s'agira pour la première case de la dernière et vice versa.

• Fonctions d'affichage des trajectoires

• Evolution à partir d'une configuration aléatoire

On construit un automate linéaire L0 de 16 cases ayant pour condition initiale des valeurs aléatoires ϵ {0,1}.

Les fonctions de transition locales possibles sont numérotés de 0 à 255 i.e. vont de la configuration de trois entrées = à la configuration = . Pour obtenir la configuration n° i  on peut utiliser l'opérateur IntegerDigits[i, base=2, longueur=8]

• Visualisation de la trajectoire de f90

    - La taille de l'automate est de 100 cases,
    - La condition initiale est aléatoire,
    - La fonction locale de transition est f90.
    - La fonction globale de transition est itérée 100 fois.

• Les trajectoires sont circulaires

L'automate linéaire ayant un nombre de cases fini : n ϵ Ν, le nombre total d'états est lui aussi fini et égal à . Il s'ensuit que la trajectoire du processus doit être circulaire : au bout de k <= étapes, on doit repasser par une configuration déjà rencontrée.

On voit que la longueur de trajectoire la plus longue (sans repasser par un état déjà parcouru) est de  k =10 étapes, ce qui est très inférieur à la borne théorique : = 256.

• Trajectoires à partir d'une CI simple

• Evolution des 256 fonctions de transition à partir de la condition initiale {0, 1, 0, 1, 0, 1, 0, 1, ...}

• Table des 256 fonctions de transition

La fonction de service LinearFunctionTable travaille sur un automate linéaire en anneau de 8 cases. Elle prend :

    - une seule condition initiale L,
    - 256 fonctions de transition locales.

C'est la fonction LinearFunctionTable quicalcule les fonctions de transition locales p <= nf < q  et les fait évoluer en itérant ns fois LinearStep sur la condition locale. On obtient une table contenant q-p petites matrices booléennes où chaque petite matrice (de ns lignes et 8 colonnes) est une trajectoire associée à une des q-p fonctions de transition locales.

Parmi le grand  nombre de conditions initiales possibles (pour 8 cases seulement on a = 256) nous avons choisi

qui correspond à une distribution homogène de la condition initiale sur l'automate.

• L = {0,1,0,1,0,1,0,1};   Fonctions : 0 .. 63

• L = {0,1,0,1,0,1,0,1};   Fonctions : 64 .. 127

• L = {0,1,0,1,0,1,0,1};    Fonctions : 128 .. 191

• L = {0,1,0,1,0,1,0,1};    Fonctions : 192 .. 255

• Evolution en fonction de conditions initiales

• Evolution en fonction des conditions initiales

La fonction de service LinearCITable prend une seule fonction de transition 0 <= nf < 255 et un automate linéaire en anneau de 8 cases. Elle calcule les configurations initiales allant de p à q et les fait évoluer en itérant ns fois LinearStep. On obtient une table contenant q-p petites matrices booléennes où chaque petite matrice (de ns lignes et 8 colonnes) est une trajectoire associée à une condition initiale.

Nous avons choisi dans les tables précédentes (portant sur la seule condition initiale {0,1,0,1,0,1,...})des fonctions qui présentent des formes caractéristisques. On constate que pour la très grande majorité des conditions initiales (considérées sur un espace de 8 cases seulement !), les trajectoires exhibent bien qualitativement la même forme. On peut donc dire que chaque fonction de transition a son “caractère” ; certaines fonctions ont plus de caractère que d'autres, au sens où
    - elles exhibent une forme très reconnaissable,
    - elles sont quasi-indépendantes des CIs.

• Fonction = 250;    L = 0 .. 255

• Fonction = 192;    L = 0 .. 255

• Fonction = 80;    L = 0 .. 255

• Fonction = 35;    L = 0 .. 255

• Espace des phases pour un automate à 8 cases

Considérons un automate à une dimension possédant 8 cases rebouclées, à 3 entrées. L'espace des phases global est l'ensemble de tous les états possibles. Il est fonction de :
-- la taille de l'automate : 8 cases => 256 états,
-- le nombre max d'itérations non circulaires : 256,
-- que multiplie le nombre de fonction à 3 entrées : 256.

Le nombre total de bits nécessaires à l'exploration exhaustive de ce processus est de 16 Méga bits, ce qui peut loger en mémoire d'un ordinateur moderne.

• Analyse des comportements observés

Faute d'avoir pu effectuer l'exploration exhaustive de l'espace des phase global associé à un automate à une dimension possédant 8 cases rebouclées, et une fonction de transition locale à 3 entrées, nous avons effectué deux types d'expérimentations :
-- faire varier les fonctions de transition pour un CI fixée,
-- faire varier les CIs pour une fonction de transition fixée.

On observe que la variation des fonctions de transition produit des comportements :
-- assez caractéristiques (ayant une forme décrivable),
-- classables en catégories (comportement quasi équivalents).

On observe que la variation des CIs produit des comportements relativement homogènes, qui semblent caractéristiques de la fonction de transition fixée. Il ressort de tout ceci que les comportements observés sont plus le fait des fonctions de transition que des CIs choisies.

• Interprétation en termes sociobiologiques

Nous pouvons essayer de nous servir de ce phénomène pour en tirer une interprétation portant sur des créatures vivantes possédant un génotype (l'inné) et qui sont plongées dans une culture, dans un environnement (l'acquis).

Deux interprétations complétement opposées de ce schéma sont possibles :

Interprétation 1 : fonction = gènes, CIs = environnement

On considère que la fonction de transition est le "caractère" de la créature et que les CIs correspondent aux conditions contingentes de sa naissance. On en conclut que le caractère l'emporte sur l'environnement de naissance, i.e. que l'inné est plus fort que l'acquis.

Interprétation 2 : fonction = environnement, CIs = gènes

On considère que la fonction de transition est le moteur environnemental (culturel) qui va façonner la créature à partir d'une donnée initiale : son phénotype propre, issu de ses gènes qui correspondent aux CIs. On en conclut que le modelage environnemental l'emporte sur le phénotype propre, i.e. que l'acquis est plus fort que l'inné.

Moralité : le modèle est neutre !

3 Le Jeu de la Vie de Conway

Le modèle de J. Conway

Principe du Jeu de la Vie

En 1974, J. Conway a proposé un automate cellulaire dont le fonctionnement est très simple mais dont la richesse des comportements et la puissance de calcul formel étonnent encore.

Le jeu de la Vie fonctionne sur une matrice booléenne (les valeurs d'une case ϵ {0,1}) rebouclée en tore à deux dimensions (il n'y a pas de bords). On part d'une configuration initiale aléatoire ou bien ad hoc et on itére le processus suivant :

Soit (t) l'état de la case . On calcule le nombre v de voisins à 1 dans le voisinage de Moore (8 voisins) de celle case. L'état (t+1) est définit par :
    - si v = 2 : (t),
    - si v = 3 : 1
    - sinon : 0.

Intuitivement, dans une vision PPSN, cela correspond à la modélisation du comportement naturel suivant :
-- Si une cellule est à 0 et qu'elle est entourée de 3 voisins elle “naît”
-- Si une cellule est à 1, elle reste à 1 si elle possède 2 ou  3 voisins à 1. Dans les autres cas, elle “meurt” d'isolement
      (0 voisin à 1) ou d'étouffement (4, 5, 6, 7, 8 voisins à 1).

• Construction de la matrice du jeu de la Vie

La fonction de service MakeRandLife construit une matrice initialisée avec des valeurs {0,1} choisies aléatoirement. Elle laisse tout autour de la matrice, une bordure d'épaisseur une-case remplie de valeurs 0.

Dans notre implémentation, cette bordure permet de ne pas tenir compte des bords ce qui simplifie et accélère la fonction LifeStep qui effectue une transition du processus sur une matrice m

• Exécution du jeu de la Vie

La fonction de service LifeTable permet de visualiser les différentes étapes du jeu de la vie sous forme d'une table de matrices

• Exemples de trajectoires

Dancs ces exemples, on constate que l'évolution converge vers certaines configurations qui sont stables : ce sont des attracteurs de la dynamique du jeu de la Vie.

• Exemples de patterns typiques du jeu de la vie

• Patterns  typiques : états fixes

Ce pattern évolue vers un état stable : un carré

Ce pattern évolue aussi vers un état stable : rond ou nid d'abeille

• Patterns  typiques : clignotants

Ce pattern évolue vers un cycle de période 2. On appelle ce type de patterns des clignotants

• Gliders

Un glider est un pattern qui a et n'a pas de période. En fait sa forme a une période 4 mais elle se trouve translatée d'une case à droite et d'une case en bas.Ce déplacement linéaire en diagonale fait que ce pattern, placé sur une matrice infinie, possède une période infinie. Le pattern d'un glider est défini par :

La fonction de service PatternCopy permet de copier un pattern sur une matrice plus vaste

• Un autre Glider de quasi-période 4

• Canon à Gliders

• Le pattern : Glider Gun

On peut construire des configurations qui ont des comportements non triviaux : par exemple le "canon à gliders” ci-dessous est une configuration qui possède une quasi-période longue de 30 cycles et qui produit un glider. Ce glider se déplace et peut être vu comme "éjecté" du canon

• Exécution du canon à gliders

On constate que la configuration 30 (première à gauche de la ligne du bas) est égale à la configuration de départ 0 (première à gauche de la ligne du haut), à ceci près qu'elle a émis deux scories (deux nids d'abeilles fixes) et un glider que l'on voit planer vers le nord-est (configurations  31 à 39 ... etc.) alors que le canon reprend une phase de 30 cycles qui produira un nouveau glider.

• Pattern : Eater

La configuration connue sous le nom de Eater (mangeur) possède une période 15 Cycles. Elle peut entrer en collision avec un glider et le détruire sans être pour autant elle-même perturbée.

• Visualisation de la trajectoire d'un Eater

La configuration Eater possède une période de 15 cycles. Elle passe par 14 formes différentes très caractéristiques :

• Construction d'une situation de eating

On construit une situation (bien synchronisée !) où le glider éjecté arrive près d'un eater dans la position relative suivante

Le type de Glider éjecté par un canon à gliders peut prendre à un moment donné la forme suivante

•Eating d'un glider envoyé par un canon

Le Eater a mangé le glider et a repris sa forme initiale.

•Fonctions du jeu de la vie

4 Automate Autoreproducteur de Langton

• Présentation de l'automate de C. Langton

• Le concept d'automate autoreproducteur de Von Neumann

Au début des années 50, John Von Neumann a étudié le problème de l'autoreproduction des automates cellulaires. Il s'agit de construire un automate cellulaire capable de reproduire la forme initiale qu'il possède sur sa matrice cellulaire. Cette forme initiale est formée de l'image des états internes de l'automate. John Von Neumann a découvert un automate à 29 états qui possède cette propriété mais sa table de transition est d'une complexité extrême.

En 1984, C. Langton a proposé un automate cellulaire capable de se reproduire et ne possédant que 8 états internes : 0, 1, 2, 3, 4, 5, 7. Dans les années 80, cet automate est devenu le fer de lance de l'école "Artificial Life" auquel il a servi de paradigme (depuis, Byl a proposé une version ayant moins d'états mais elle est moins "lisible").

L'automate de Langton est un système dynamique discret : Le temps se déroule en étapes énumérables : à chaque nouvelle étape n+1 correspond une nouvelle matrice M[n+1] = LF[M[n]] où LF est la fonction de transition spécifique à l'automate de Langton.

• Forme initiale de l'automate de Langton

La forme initiale de l'automate de Langton est donnée par la matrice 10 ×15 d'états suivante

Afin de pouvoir mieux visualiser la forme définie par cette matrice, on construit des fonctions de service : SeeStates, SeeGray et SeeColors

Les états ayant pour valeur 0 sont représentés par des "."

• Fonctions d'affichages : SeeStates, SeeGray, SeeColors

• Construction de l'automate cellulaire de Langton

Pour définir l'automate cellulaire proprement dit, il faut placer la forme initiale Langton sur une matrice plus vaste où les états ont pour valeur par défaut 0. cela est fait par la fonction MakeLangton qui construit une matrice nl × nc et recopie la forme Langton en i,j.

Nous construisons l'état initial de l'automate : M1

La matrice cellulaire M1 est plus grande que Langton pour laisser de la place afin que la forme puisse se reproduire (à droite). Les états sont représentés par des niveaux de gris allant de 0 (blanc) à 7 (noir).

• Visualisation  tridimensionnelle  de l'automate

On peut donner un peu de vie à la forme de Langton en la “gauffrant" sur une surface en papier. Ceci se fait grâce à la fonction ListPlot3D

Les pics correspondent à la présence de l'état 7. On remarque clairement le rôle de “tuyau“ ou de “mur” joué par l'état 2.

• La fonction de Transition de l'automate de Langton

• La Fonction de Transition  de Langton

La fonction de Transition de l'automate de langton, LangtonFunction, est de type classique : Pour un élément (t) de la matrice cellulaire à l'instant t, la valeur de cet élément à l'instant t+1 est calculé en fonction de la valeur v de cet élément à l'instant t et des valeurs des 4 voisins (voisinage NEWS) à l'instant t.

La fonction de transition est construite à partir d'une table de transition, appelée LangtonTable, qui est de la forme :

• Une étape de Langton

La fonction LangtonStep effectue un seul pas discret de calcul. A partir d'une matrice m, elle fournit la matrice à l'instant suivant en appliquant à chaque élément de m la fonction de transition

Cette fonction est optimisée de deux manières :

Pour accélérer notablement les calculs, on teste et on traite à part la configuration par défaut :
{v, n, s, e, w} === {0, 0, 0, 0, 0},

Pour éviter que la table de transition ne soit trop grande, on tire profit des symétries (a, b, c) de la configuration
x = news.

• Exemples d'exécutions

• Les 8 premières étapes de Langton