Les automates cellulaires

Une définition

Un automate cellulaire... Toute la définition de cet objet est dans son nom. Un automate est un mécanisme qui déroule une liste de règles déterminant des actions. Vous connaissez peut-être les automates industriels qui pilotent les chaines de fabrication dans l'industrie ou plus prosaïquement les rouleaux de lavage de la station service de votre quartier. En informatique, nous avons aussi nos automates logiciels, qui eux aussi déroulent des règles pour exécuter des commandes. Mais pourquoi "cellulaire" ? Parce que cet automate s'exécute dans un monde discret, composé de cellules. Chaque cellule peut posséder deux ou plusieurs états et sur chaque cellule du monde de l'automate, s'appliquent ses règles.

Si nous prenons un peu de hauteur conceptuelle, on dira qu'un automate cellulaire présente une analogie très forte avec l'ensemble constitué par un univers et ses lois de la physique. Après tout, que sont les lois de la physique si ce ne sont les règles qui définissent le comportement de l'ensemble des composants (les cellules) de cet univers ? Il y a même des mathématiciens issus de l'école de Fredkin qui affirment que l'univers, le notre, est un automate cellulaire !

Le monde d'un automate cellulaire vit dans un temps discret. A chaque pas de temps, l'automate créé une génération selon ses règles. Là aussi, rien n'empêche fondamentalement de considérer que notre univers ne se comporte pas de cette manière. Après tout, qui sait ce que se passe au-deça du temps de Planck ?

On peut également tenter une définition mathématique, car un automate logiciel est un objet mathématique et la plupart des chercheurs et des déouvreurs sont des mathématiciens. Un automate cellulaire est défini par:

Sur le plan mathématique, un automate cellulaire est un système dynamique qui est déterminé par son état initial, on parle de configuration initiale, et sa définition A = (d,S,V,F).

Un peu d'histoire

La naissance des automates cellulaires, au tout début des années 50, résulte d'un échange fructueux entre un mathématicien et physicien génial John von Neumann (1903-1957), spécialiste de l'informatique théorique, de mécanique quantique et d'analyse fonctionnelle et un mathématicien topologiste non moins génial, Stanislaw Ulam (1909 - 1984), plus connu pour être celui qui se servit de la méthode de Monte-Carlo pour intégrer les intégrales qui permirent de construire la bombe H américaine (et sans doute aussi soviétique).

En 1949, von Neumann travaillait sur l'hypothèse d'une machine auto-reproductible, c'est à dire une machine capable de construire à partir de composants élémentaires une copie d'elle-même. Le problème n'était pas simple, d'autant que von Neumann pensait à une vraie machine physique, avec des interrupteurs, des circuits électriques et des tubes à vide (les transistors et les circuits intégrés n'existaient pas...).

Ulam, lui en bon mathématicien, était plus ... conceptuel. Il travaillait sur des objets géométriques qui se répliquaient sur une matrice infinie, son univers cellulaire, selon des règles simples. Ces objets étaient composés d'un groupe de cellules, l'état de chaque cellule étant déterminé par l'état de ses voisines. Et les résultats étaient surprenants, le comportement des objets de générations en générations étaient imprévisibles et pouvaient déboucher sur des structures très complexes.

Ulam et von Neumann étaient amis et Von Neumann parla à Ulam de sa machine auto-reproductrice. Ulam lui proposa d'utiliser son univers cellulaire pour étudier l'auto-reproduction d'un système. Ce que fit von Neumann. En s'inspirant des travaux d'Ulam et aussi de Turing, il proposa en 1952 un automate auto-reproducteur, dont l'alphabet comportait 29 signes. Il définit aussi un voisinage particulier (adjacent par les cotés) qui porte son nom. Son "monde", la matrice sur laquelle évoluait son automate comportait 200 000 cellules ! Avec les ordinateurs de l'époque, les calculs devaient être très très longs...

Il a fallu attendre la fin des années 1960 et le début 70 pour voir les automates cellulaires sortir du cénacle mathématicien. En partie sans doute parce que les ordinateurs étaient plus puissants et plus disponibles. En 1968, Edgar Codd, un informaticien, inventeur du modèle relationnel des BD, simplifia l'automate de von Neumann en ramenant son alphabet à 8 états. Et surtout, il diffusa le concept d'automate cellulaire en publiant la bible des AC "Cellular Automata".

Mais les automates cellulaires gagnèrent leur lettre de noblesse avec le jeu de la vie (game of life) de John Conway, autre mathématicien, spécialiste des structures. Il publia un livre "On numbers and games" en 1976 qui décrit un automate cellulaire devenu célébre, que nous aborderons plus loin. Pour la petite histoire, Conway a aussi démontré un théorème important en physique quantique en 2004, dit "théorème du libre arbitre", qui fit pas mal de bruit chez les quanticiens !

Depuis, et en suivant l'accroissement phénoménal de la puissance des ordinateurs, les recherches sur les automates cellulaires débordèrent largement des maths pour conquérir le monde de la simulation des systèmes physiques, en particulier la simulation des systèmes complexes et la théorie de l'émergence. Les automates cellulaires sont un domaine de recherche très vif, qui devrait attirer les jeunes physiciens et mathématiciens.

Ses applications

Modéliser un système physique

En physique, nous avons l'habitude de raisonner sur des systèmes physiques dans un espace spatio-temporel continu. Le comportement local de ces systèmes est déterminé par des équations différentielles et nous obtenons le comportement global, macroscopique, en intégrant ces équations différentielles.

L'arrivée de la physique numérique modifie considérablement la donne. Il n'est plus possible de raisonner sur des systèmes continus, nos ordinateurs n'étant pas capables de travailler sur un ensemble des réels ou de complexes. Le monde de la simulation et du calcul numérique est essentiellement discret, tant pour l'espace que pour le temps. Et nous rejoignons là l'univers des automates cellulaires.

Les automates cellulaires permettent une simulation des systèmes physiques discrétisés très similaire à celle que nous avons utilisé avec la méthode des différences finies (voir ici). Dans les deux cas, nous définissons une grille sur laquelle la valeur (l'état) de chaque noeud de la grille (une cellule de notre automate cellulaire) dépend de la valeur de ses voisins (au sens de von Neumann ou de Moore selon les cas). On les retrouve dans les simulations de mécanique des fluides, de physique de la matière condensée et en physique quantique.

Pour ma part, le paradigme discontinu des automates cellulaires me semble coller plus à la réalité physique de la matière, du moins si on reste en physique classique. Et même en physique quantique, rien ne prouve la continuité de notre monde. Aussi, je pense que la simulation par automates cellulaires prendra le pas sur les méthodes classiques de simulation, qui partent d'un modèle continu basé sur des équations différentielles pour s'empresser de les discrètiser parce qu'on ne sait pas faire autrement !

Etudier les phénomènes d'émergence

Qu'est-ce que l'émergence ?

Tous les lycéens apprennent la méthode réductionniste, celle de Descartes. Sans même que l'on dise son nom, d'ailleurs... Elle consiste à décomposer un problème difficile en plusieurs petits problèmes, que l'on suppose plus faciles à résoudre. Et bien sur, on suppose qu'ayant trouvé la solution de tous ces problèmes élémentaires, on aura résolu le problème difficile initial. Quoique que cette hypothèse soit rarement mentionnée.
Dit autrement et de manière plus philosophique, la méthode cartésienne suppose que le "tout est la somme des parties", que les propriétés du "tout" résultent de la somme des propriétés des "parties".

Prenons un exemple simple. Une molécule d'eau H2O possède des propriétés bien particulières, qui lui sont propres et qui sont dues à l'assemblage de deux atomes d'hydrogène et d'un atome d'oxygène, dans une géométrie donnée. Mais qui me dira si cette molécule est un liquide, un solide ou un gaz ? La notion de liquide, de gaz ou de solide n'a de sens que si l'on considère un nombre très important de molécules. Les propriétés de l'eau liquide dépassent les propriétés individuelles d'une molécule d'eau. Il y a émergence de propriétés lorsqu'on rassemble une grand nombre de molécules d'eau à une température donnée.

Plus compliqué, notre corps ! Il est formé d'un ensemble de cellules, qui possèdent toutes leurs propriété individuelles. Leur assemblage, au niveau du tissu puis de l'organe et enfin du corps donne lieu à l'émergence de propriétés très différentes, dont l'intelligence. Un neurone seul ne peut engendrer l'intelligence... Les spécialistes du vivant ont d'ailleurs créé plusieurs sciences pour aborder ces différentes propriétés émergentes : la biologie cellulaire, l'histologie, la physiologie.

Pensez à la démarche la plus courante de la philosophie réductionniste : pour comprendre l'intelligence, il faut comprendre le cerveau, pour comprendre le cerveau il faut comprendre les neurones, les lois de la chimie, qui découlent des lois de la physique, qui découlent des lois de la physique des particules. En résumant, pour comprendre l'intelligence, il faut comprendre le modèle standard ! On y a cru, puis on s'est aperçu que c'est loin d'être évident...

La compréhension des phénomènes d'émergence, en particulier dans l'étude des systèmes complexes, est un domaine majeure de la recherche, dans des domaines aussi diférents que la physique, la chimie, la biologie, les sciences cognitives et la sociologie. Nous ne comprendrons notre monde que lorsque nous aurons compris pourquoi "le tout est plus que la somme des parties", comme l'écrivait le philosophe Christian von Ehrenfels en 1890 déjà ...

L'apport des automates cellulaires dans l'étude des phénomènes émergents

Les premières expériences avec des automates cellulaires, avec le jeu de la vie notamment, ont rapidement laissé apparaître des comportements émergents. Les règles d'évolution très simples, avec des configurations initiales aléatoires, donnent lieu des comportements singuliers et complexes. On observe un comportement similaire à celui de la sélection naturelle, chère à Darwin. D'autres familles d'algorithmes reproduisent la sélection naturelle, comme les algorithmes génétiques. Mais il y a une différence fondamentale : les algorithmes génétiques sont programmés pour embarquer des règles de sélection naturelle. Ce n'est absolument pas le cas des automates cellulaires comme le "jeu de la vie", par exemple. La sélection est un propriété émergente des règles du jeu de la vie. Nous verrons des exemples de ces comportements plus loin.

Par la simplicité de leur mise en oeuvre, le peu de moyens nécessaires et la puissance de leur algorithme, ils contribuent largement à l'étude des phénomènes émergents. On imagine par exemple des grilles immenses qui donneraient lieu à la naissance d'organismes virtuels quasi-intelligents (le quasi est peut-être d'ailleurs inutile). Notre cerveau, siège de notre intelligence, n'est-il pas qu'un assemblage d'atomes tout ce qu'il y a de plus bêtes !

Un exemple d'automate cellulaire - Le jeu de la vie

Pour illustrer le concept d'automate cellulaire (AC), je vous propose un script python qui code le "jeu de la vie" de Conway, GameLife.py. Comme vous allez le constater, il s'agit d'un algorithme très simple, muni de lois très simples, qui donne des résultats suprenants de richesse et d'étendue d'étude, qui dépasse de loin l'informatique théorique.

J'en profite pour introduire l'usage de Tkinter, le module python qui permet de construire des IHM, pour Interface Homme Machine, avec des fenêtres, boutons et autres widgets classiques de Windows (et aussi OsX d'ailleurs...)

La grille de jeu

Comme tous les AC, le jeu de la vie évolue sur une grille matricielle, que l'on choisit habituellement carrée. Sur cette grille, il sera nécessaire de définir la notion de voisinage. Voyons cela en code python.

Sa structure

Après avoir fixer le nombre de lignes NbL et NbC de colonnes de la grille, et la longueur du maillage a :

NbL = 50 # hauteur du tableau

NbC = 50 # largeur du tableau

a = 15 # taille d'une cellule

je définis deux matrices d'entiers, l'une sert à l'affichage (cell) et l'autre est la matrice d'état de mon AC (etat) :

cell = np.zeros((NbL,NbC),dtype=int)

etat = np.zeros((NbL,NbC),dtype=int)

Puis je définis le dictionnaire d'états de mon AC. Chaque cellule peut présenter deux états : "ON" si elle est vivante, active, ou "OFF" si elles morte, inactive.

state = {"OFF":0,"ON":1}

La notion de voisinage

Intuitivement, nous voyons ce qu'est un voisin, quelqu'un qui habite à coté. Soit, mais que signifie "à coté" ? Nous avons vu qu'il existe deux grands types de voisinage: celui de Moore et celui de von Neumann. Dans le jeu de la vie, nous utiliserons le voisinage de Moore, c'est à dire que l'on considère qu'une cellule ets voisine d'une autre cellule si elle la touche par un sommet ou un coté.

Nous verrons que les règles d'évolution du jeu de la vie dépendent du nombre de voisins vivants (état = ON) d'une cellule. Il faut donc les déterminer. Ce qui m'amène à un autre point. Comment procède-t-on sur les bords de la grille ? Pour une cellule situé en haut et à gauche, par exemple, comment déterminer son voisinage ? Dans le jeu de la vie, Conway a fait le choix de la topologie torique. On "colle" le bord haut au bord bas et le bord gauche au bord droit, d'abord un cylindre, puis un tore en collant les deux extrémités du cylindre.
Ce qui fait que notre cellule en haut et à gauche à comme voisine la cellule en bas et à gauche, mais aussi la cellule en haut et à droite... Ainsi, il est toujours possible de calculer le nombre de voisins d'une cellule quelconque de la grille.

Je fais le dénombrement des voisins ON d'une cellule (i,j) avec la fonction voisinageMoore(i,j) dont voici le code:

def voisinageMoore(i,j):

nb_voisins = 0

if etat[(i-1)%NbL][(j+1)%NbC] == state["ON"]:

nb_voisins += 1

if etat[i][(j+1)%NbC] == state["ON"]:

nb_voisins += 1

if etat[(i+1)%NbL][(j+1)%NbC] == state["ON"]:

nb_voisins += 1

if etat[(i-1)%NbL][j] == state["ON"]:

nb_voisins += 1

if etat[(i+1)%NbL][j] == state["ON"]:

nb_voisins += 1

if etat[(i-1)%NbL][(j-1)%NbC] == state["ON"]:

nb_voisins += 1

if etat[i][(j-1)%NbC] == state["ON"]:

nb_voisins += 1

if etat[(i+1)%NbL][(j-1)%NbC] == state["ON"]:

nb_voisins += 1

return nb_voisins

Pour rappel, en Python, l'opérateur % est l'opérateur modulo, qui donne le reste de la division entière. Quand j'écris :

etat[(i+1)%NbL][(j-1)%NbC]

je traite en fait la topologie torique : si i < NbL, je conserve la valeur de i. Mais si i >= NbL, je passe de l'autre coté. Par exemple, sachant que NbL = 50, si i = 40, j'ai (i+1)%NbL = 41. Mais si i = 49, j'obtiens (i+1)%NbL = 0 ( car attention, l'indice i varie entre 0 et 49...). Même raisonnement sur j.

L'initialisation de l'AC

La fonction initialiser_monde()initialise la matrice d'état à OFF pour chaque cellule et créé la grille d'évolution de l'AC. Les cellules sont affichées en blanc, couleur que j'ai choisi pour l'état OFF ou mort.

etat[0:NbL,0:NbC] = state["OFF"]

# création de la grille

for x in range(NbL):

for y in range(NbC):

cell[x,y] = canvas.create_rectangle((x*a, y*a, (x+1)*a, (y+1)*a), outline="gray", fill="white")

Les règles d'évolution

Ce sont nos lois de la physique pour notre AC ! Elles déterminent l'évolution d'une génération vers la génération immédiatement suivante. Les règles varient en fonction de l'AC. Celles du jeu de la vie sont au nombre de quatre, très simples :

Voici ce que cela donne dans le code de la fonction appliquer_regles():

temp = np.zeros((NbL,NbC))

for x in range(NbL):

for y in range(NbC):

nb_voisins = voisinageMoore(x,y)

# Règle 1 - Mort de solitude

if etat[x][y] == state["ON"] and nb_voisins < 2:

temp[x][y] = state["OFF"]

# Règle 2 - Toute cellule avec 2 ou 3 voisins survit.

if etat[x][y] == state["ON"] and (nb_voisins == 2 or nb_voisins == 3):

temp[x][y] = state["ON"]

# Règle 3 - Mort par asphyxie

if etat[x][y] == state["ON"] and nb_voisins > 3:

temp[x][y] = state["OFF"]

# Règle 4 - Naissance

if etat[x][y] == state["OFF"] and nb_voisins == 3:

temp[x][y] = state["ON"]

# copier la matrice temporaire dans l'automate

etat = temp.copy()

Notez que je ne fais pas les calculs dans la matrice etat mais dans une matrice temporaire temp pour ne pas modifier la valeur des cellules d'une même génération avant le passage à la génération suivante. Ce passage se fait lorsque je recopie la matrice temp qui contient les nouveaux états des cellules dans la matrice état.

la partie IHM

La définition de la fenêtre graphique

Les instructions suivantes permettent la création de la fenêtre, intitulée 'Jeu de la vie - Conway', la trace et la mette au premier plan de votre écran.

fenetre = Tk()

fenetre.title("Jeu de la vie - Conway")

canvas = Canvas(fenetre, width=a*NbC+1, height=a*NbL+1, highlightthickness=0)

fenetre.wm_attributes("-topmost", True) # afficher la fenetre on top

La définition des boutons

Nous allons maintenant créer les quatres boutons Exit, Start, Stop et Step, qui permettent respectivement de quitter le programme, démarrer l'AC, arrêter l'AC et le plus intéressant de dérouler l'AC pas à pas:

bou1 = Button(fenetre,text='Exit', width=8, command=fenetre.destroy)

bou1.pack(side=RIGHT)

bou2 = Button(fenetre, text='Start', width=8, command=start)

bou2.pack(side=LEFT)

bou3 = Button(fenetre, text='Stop', width=8, command=stop)

bou3.pack(side=LEFT)

bou4 = Button(fenetre, text='Step', width=8, command=pasapas)

bou4.pack(side=LEFT)

Vous trouverez la définition des fonctions start(), stop() et pasapas() dans le script. Elles ne présentent pas de difficultés particulières.

La fonction de gestion du clic gauche de la souris

Cette fonction est activée lorsque vous cliquez sur le bouton gauche de votre souris, après avoir désigné une cellule avec votre curseur.

def SelectionCellule(event):

x, y = event.x//a, event.y//a

etat[x,y] = (etat[x,y]+1)%2

if etat[x,y]==state["OFF"]:

color = "white"

else:

color = "blue"

canvas.itemconfig(cell[x][y], fill=color)

La fonction change l'état de la cellule et l'affiche avec la couleur correspondante à son état blanc pour OFF et bleu pour ON.

Cette fonction sera utilisée pour fixer un état initial à l'AC qui ne sera pas aléatoire dans le cas de notre AC "jeu de la vie". Vous pourrez ainsi fixer plusieurs états initiales différents interactivement et mener quelques expériences.

Le lancement de l'automate

Ce bout de code n'appelle pas de commentaire particulier. Vous trouverez les fonctions dessiner() et iterer() dans le script.

flag = 0

initialiser_monde()

dessiner()

iterer()

fenetre.mainloop()

Je n'ai pas implémenté de compteur de générations. Cela pourrait être utile...

Un exemple de comportement

Pour illustrer le fonctionnement de l'AC du jeu de la vie, je vais définir la configuration initiale, en sélectionnant les cases ci-dessous :

Un exemple d'évolution - génération 0

puis j'appuie sur le bouton 'Step' pour calculer la génération 1, ce qui me donne :

Un exemple d'évolution - génération 1

Et je continue avec la génération 2 :

Un exemple d'évolution - génération 2

puis la génération 3 :

Un exemple d'évolution - génération 3

et la génération 4 :

Un exemple d'évolution - génération 4

Maintenant continuez : vous observerez que les motifs des générations 3 et 4 alternent indéfiniment...

Vous avez l'outil : à votre tour, tentez vos expériences !

D'autres automates cellulaires

Nous verrons dans d'autres pages de TangenteX.com comment utiliser les automates cellulaires pour modéliser:

Le script Python

Le script Python étudié dans cette page est disponible dans le package GameLife.zip.


Contenu et design par Dominique Lefebvre - www.tangenteX.com janvier 2017    Licence Creative Commons   Contact : PhysiqueX ou

Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Pas de Modification 3.0 France.