~ Automates cellulaires ~  

~ORIGINE
                                                                                                     ~CARACTERISTIQUES:   - Fonctionnelles
                                            - Techniques

~AUTOMATES CELLULAIRES VS SYSTEMES MULTI AGENTS

~EXEMPLES D'AUTOMATES CELLULAIRES:
                                            - Automate de Von Neumann
                                            - La boucle autoreplicante de Langton
                                            - Automate élémentaire de Wolfram
                                            - Le Jeu de la vie, de Conway

~CRITIQUES et DOMAINES D'APPLICATION
                                                                                                                                                          -Retour Page d'Accueil-

        Les automates cellulaires ont comme support une matrice de cellules de dimension 1, 2, 3 ou plus. Un automate évolue  par génération ou "pas de temps" (t0, puis t+1, t+2, ..., t+n). Ces changements d'état successifs font de lui un système dynamique. A chaque nouvelle génération, l'état de chaque cellule est redéfini en fonction de ceux de ses voisines à la génération précedente. La matrice entière est remise à jour de manière synchrone, les transitions des cellules s'effectuant simultanément et en fonction des même règles. Bien qu'appliquant des règles de transitions simples, le déploiement d'un automate cellulaire peut conduire à l'émergence de structures beaucoup plus complexes.

        > > Caractéristiques fonctionnelles: 

        On peut tirer de ce qui précède 5 notions essentielles à la compréhension du fonctionnement d'un automate cellulaire:
1) Le voisinage:
    A chaque génération, le nouvel état de chaque cellule est déterminé à partir de sa position spatiale dans l'univers de l'automate. C'est en fonction des états (allumé/éteint ou vivant/mort) des cellules voisines à t+n que le nouvel état n d'une cellule est défini. Les transitions d'un état à l'autre de l'automate se font localement pour chaque cellule.
2) Le parallélisme:
    Toutes les cellules constituant l'univers de l'automate sont mises à jour de manière simultanée et synchrone, leur transition de l'état t+(n-1) à l'état t+n se produisant en même temps.
3) Le déterminisme:
    Pour une cellule, la donnée des états des cellules voisines détermine à elle seule le nouvel état.
Certains automates cellulaires dits stochastiques introduisent un facteur probabilité dans la transition : une même configuration de voisinage pourra conduire à différentes nouvelles configurations.
4) L'homogènéité:
    Toutes les cellules de l'automate utilisent les même règles de transition pour déterminer leur état suivant.
5) La discrétisation:
   Un automate cellulaire se déroule dans le temps de manière discrète, c'est à dire en opposition avec la plupart des phénomènes physiques se déroulant de façon continue. Le temps de l'univers d'un automate avance par saut (t+0, t+1,...,t+n) génération après génération.

        >> Caractéristiques techniques : 

        On peut décrire un automate cellulaire en fonction de 4 paramètres:
1) Sa dimension:
    Le plus générallement 1 dimension D (une ligne) ou 2D (un plan). Il n'y a pas de limite à la dimension d'un automate.
2) Le voisinage d'une cellule:
    Celui-ci définit l'ensemble des cellules qui auront une influence sur la cellule étudiée. En pratique "r", le voisinage, est souvent limité à la cellule cible et aux cellules adjacentes.  Ci-contre r = 9:
3) Son espace d'états:
    Cet espace correspond à l'ensemble "k" des états que peut prendre une cellule. Le plus souvent limité à deux (ex: vivant/mort; rouge/bleu; allumé/éteint), il n'y a aucune limite théorique. Pour exemple, Von Neumann a étudié mathématiquement un automate à 29 états.
   Ces états sont représentés visuellement par des couleurs, qui permettent de suivre les évolutions de l'automate.
    Lors de modélisation de systèmes, les états des cellules correspondent à des états physiques locaux. Par exemple, dans le Jeu de la Vie de Conway, une cellule est soit "morte" soit "vivante", mais on pourrait très bien imaginer des états transitoires de dégénérescence d'une cellule, en augmentant le nombre d'états de l'automate. (Voir Brian's Brain pour exemple)
4) Sa fonction de transition:
    Pour un automate à "k" états et avec un voisinage de "r" cellules, il peut y avoir "c = k puissance r" configurations de voisinage différentes.
            - pour k = 2 et r = 3,  c =  8      (Automate Cellulaire élémentaire de Wolfram).
            - pour k = 2 et r = 9,  c = 512   (Jeu de la vie de Conway).
La fonction de transition est l'ensemble des règles qui permettent de déterminer le nouvel état d'une cellule en fonction de son état précédent et de l'état précedent de son voisinage. Nombre de règles total  N = k puissance c.
            - pour k = 2,  r = 3 et  c =  8     N = 2 puissance 8 = 256 règles possibles
Lorsque k et r augmentent, le nombre de règles de transition augmente très vite jusqu'à former des espaces de règles vite inexplorables de manière systématique.

        Ce paragraphe, qui est à mettre en lien avec la partie SMA présentée sur ce site, entend souligner la différence existant entre SMA et Automates. Ce texte est un extrait du livre de  Jacques Ferber "Les Systèmes Multi-Agents - Vers une intelligence collective." (InterEditions):

        Les différentes catégories d'automates cellulaires sont légions car il est possible de faire varier l'ensemble des paramètres qui régissent leur univers.
        Le paramètre le plus évident est le nombre de dimensions. Rien n'oblige à ne considérer que des environnements à deux dimensions. L'analyse théorique des automates cellulaires s'est essentiellement effectuée à partir d'automates à une dimension (exemples: Triangle de Pascal (à gauche), Automate Elementaire de Wolfram.). Il est naturellement possible de créer des automates à trois dimensions voire plus.
        Il est également possible de jouer sur la détermination du voisinage. Si l'on considère les automates à deux dimensions, les voisinages les plus courants sont: Von Neumann (voisins Nord/Sud/Est/Ouest.); Moore  (on ajoute les diagonales: cas du Jeu de la vie); Moore étendu  (on étend la distance de voisinage au-delà de un); Margolus (on considère des ensembles de 2x2 éventuellement alternés: ce type de voisinage est utilisé dans la simulation du comportement des gaz).
        On peut aussi jouer sur le nombre d'états qui n'a aucune limite théorique. Brian's Brain  par exemple (ci-dessous), présenté par Brian Silverman en 1984, utilise trois états (vie/fantôme/mort) et peut engendrer une grande diversité de planeurs complexes au sein de configurations graphiques étonnantes. (Pour un automate intéressant à 4 états, voir le site "Wireworld" dans la partie liens).

Sources: http://www.rennard.org

        Automate Cellulaire de John Von Neumann:

        Dans les années quarante, John Von Neumann  fut le premier à s'intéresser à la manière par laquelle une machine  pourrait produire une copie d'elle-même, c'est à dire s'autoreproduire.

    "... living organisms are very complicated aggregations of elementary parts, and by any reasonable theory of probability or thermodynamics highly improbable. That they should occur in the world at all is a miracle of the first magnitude; the only thing which removes, or mitigates, this miracle is that they reproduce themselves. Therefore, if by any peculiar accident there should ever be one of them, from there on the rules of probability do not apply, and there will be many of them, at least if the milieu is reasonable."

John Von Neumann, Theory of Self-Reproducing Automata.
source : The artificial Self-replication page by Moshe Sipper.

     "Von Neumann montrait ici comment résoudre le problème de l'autoréférence de la description. Pour s'autorépliquer, la machine devrait en effet contenir une description d'elle-même, mais pour être complète, cette description doit également être décrite, etc. La solution réside dans la capacité donnée à la machine d'interpréter sa description à la fois comme un programme, une séquence d'instruction, et comme un composant. La description sera d'abord interprétée pour construire la nouvelle machine, elle sera ensuite simplement copiée afin de donner à la nouvelle machine une description d'elle-même. Ce mécanisme correspond de fait à l'interprétation actuelle du fonctionnement de la molécule d'ADN découverte après les travaux de von Neumann.
[...] Cet automate était extrêmement complexe car il intégrait un constructeur universel. En 1968, Edgar Codd a proposé une version simplifiée de l'automate de von Neumann n'utilisant que huit états, mais là encore, Codd intégrait un constructeur universel. Les choses ont changé dans les années 1980 avec Christopher Langton."
 Ci-dessus: Machine de Turing de Von Neumann

        Dans les années 80, Christopher Langton part de l'idée suivante: les organismes vivants sont incapables de construction universelle. Il abandonne donc l'idée d'universalité du réplicateur et cherche à construire une machine plus simple, autoreproductrice sans pour autaut satisfaire aux conditions de construction universelle d'une machine de Turing. S'inspirant des travaux d'Edgar Codd il réalise un automate cellulaire dont les composants, comme l'ADN, constituent l'information nécessaire à sa propre réplication.

        L'automate de Langton est un automate à 8 états, géré par 29 règles. Il est formé de 86 cellules: une part de ces cellules (bleu "à l'état 2") forme une gaine fermée (telle une membrane) repliée en boucle et délimitant un espace de circulation d'information, formée par les cellules restantes. Ce conduit permet la circulation de données sous forme de signaux : couples de cellules (rouge-noir, jaune-noir ou états 0,1,4,7), qui constituent le support "génétique" (l'ADN) de l'automate. La boucle s'achève par une "tige" qui est considérée comme bras de projection où se déroule la duplication.
- Quand les signaux circulants rencontrent la jonction avec le bras de projection, ils sont dupliqués. Une copie est renvoyée dans la boucle, et l'autre copie se propage le long du bras. C'est l'équivalent de la transcription: l'ADN du gène à exprimer est copié sous forme d'une molécule d'ARN.
- En arrivant au bout du bras, les copies de signaux sont transformées en instructions. C'est l'équivalent de la traduction: à partir des instructions présentées sur l'ARN la cellule construit une protéine.
- Le bras s'étend selon ces instructions pour former une autre structure similaire à la première, dont elle se détachera par la suite, et contenant le même patrimoine informationnel permettant la réplication. L'ajout d'une règle de « stérilisation » qui bloque l'évolution au bout d'un certain nombre de générations permet la cristallisation des boucles les plus anciennes et amène à la construction d'une sorte de corail.

Copies d'écran d'une applet JAVA présente sur le site :Self-Replication loops in Cellular Space.

       Ce mécanisme est à mi-chemin entre celui de l'expression du patrimoine génétique, qui permet la création de structures sans qu'il y ait nécéssairement autoreproduction, et celui de la division cellulaire, où la cellule s'autoreproduit par division sans créer de structure nouvelle.
        Les boucles de Langton, comme l'automate de von Neumann, montrent que : « (...) l'une des propriétés fondamentales des organismes vivants, l'autoreproduction, est explicable en termes d'interactions d'éléments simples et qu'elle peut être étudiée dans ses principes logiques indépendamment de sa réalisation physique.» Heudin JC
Mais rappelons qu'en aucune manière, les boucles de Langton ne peuvent être considérées comme « vivantes », elles ne sont qu'une construction autoréplicatrice limitée.

         Automate élémentaire de Wolfram

        Au début des années 80 Stephen Wolfram utilise des automates cellulaires mettant en jeu des règles simples afin d'étudier la complexité dans la nature. Il a systématisé cette approche de la complexité dans son dernier livre A New Kind of Science (2002) et a contribué au domaine des automates cellulaires en en automatisant l'exploration.

        Architecture de l'automate:

        Cet automate est l'un des plus simple et pourtant son étude permet d'envisager la complexité que peut engendrer ce type de système. Il est le seul dont on puisse étudier de manière exhaustive l'ensemble des comportements possibles, en appliquant "à la main" les différentes fonctions de transitions, et en observant l'évolution de l'automate. C'est en ce sens que son étude est particulièrement intéressante.
Caractéristiques:    - 1 dimension (1 ligne de cellules).
                             - k = 2 états (actif (1) / passif (0)). 
                             - Voisinage "r": les deux cellules adjacentes + la cellule cible.
                             - Pour k = 2 et r = 3, il y a 256 régles de transition différentes. 

        Exemple d'évolution : 

On sélectionne 8 règles de transition parmi 256: (cellule cible en mauve et cellules adjacentes en blanc)
                               8 configurations de voisinage possible:  111    110    101    100    011    010    001    000
                               Le nouvel état de la cellule centrale:      101    110    101    110    011    010    011    000

Automate 1D k=2, r =3
- en abscisse, la dimension de l'automate.
- en ordonnée, le temps.

Règle de transition	Evolution de l'automate	Remarques
000 -> 0 001 -> 0 010 -> 0 011 -> 0 100 -> 0 101 -> 0 110 -> 0 111 -> 1		L'évolution de l'automate conduit à un état homogène où toutes les cellules meurent.
000 -> 0 001 -> 0 010 -> 1 011 -> 0 100 -> 0 101 -> 0 110 -> 0 111 -> 1		L'évolution de l'automate conduit à un ensemble stable de structures périodiques, séparées et simples.
000 -> 0 001 -> 1 010 -> 1 011 -> 0 100 -> 1 101 -> 0 110 -> 0 111 -> 1		L'évolution de l'automate conduit à un motif chaotique (aucune régularité apparente).

        Le troisième automate conduit à la remarque suivante : Même si l'univers initial n'a pas de structure, l'évolution de l'automate conduit à l'apparition de structures (triangles clairs). L'apparition spontanée de telles structures est un simple exemple d'auto-organisation, caractéristique de la vie. Pour s'en convaincre, il suffit d'observer que le motif résultant de cet automate montre une grande similitude avec la pigmentation trouvée sur la coquille de certains mollusques. Rien n'empêche de penser que cette pigmentation suive les même règles que celles de cet automate. 

        Classification de Wolfram des automates 1D    

        Wolfram a mis en exergue le résultat suivant : Si chaque règle conduit à des motifs qui diffèrent dans le détail, tous les automates semblent pouvoir appartenir à seulement quatre classes qualitatives distinctes.
    - Classe I
L'évolution de l'automate conduit à un état homogène (par exemple, toutes les cellules mortes).
La prédictabilité d'évolution est triviale. A partir de l'état initial, le système évolue toujours vers un état homogène. 

    - Classe II
L'évolution de l'automate conduit à un ensemble de structures stables ou péridodiques, mais en tous cas simples et séparées.
La prédictabilité d'évolution reste faisable. Les effets d'une cellule se propage à un nombre fini de voisins. La modification d'une cellule de l'état initial n'affectera qu'une région finie entourant cette cellule.
    - Classe III
L'évolution de l'automate conduit à un motif chaotique.
Au contraire des automates de classe II, une cellule propage son information à vitesse constante au cours de l'évolution. Pour connaitre l'état d'une cellule au bout d'un temps très grand, il faudrait connaitre les états initiaux d'un nombre très grand de cellules. Prédire l'évolution reviendrait à connaitre un nombre infini d'états initiaux.
    - Classe IV
L'évolution de l'automate conduit à des structures complexes, parfois persistantes dans le temps. Le degré de non-prédictabilité est encore plus important que dans les automates de classe III.

        Des chercheurs comme Wolfram, vont même jusqu'à proposer les automates cellulaires comme une nouvelle voie vers la compréhension de la complexité de la science et plus généralement de la vie.

Sources: -site officiel de stephen Wolfram : stephenwolfram.com
-Photos: serveur de l'institut de SantaFe.
-http://www.vieartificielle.com (Extraits)

        Présentation de l'automate 2D du Jeu de la Vie:   

        Structures remarquables du Jeu de la Vie:

         L'intérêt de ce jeu est d'avoir montré qu'il était possible d'avoir des configurations dynamiques relativement stables. à partir de règles locales très simples.

             
Soupe:  On appele "soupe" toute répartition plus ou moins aléatoire de cellules dont on observe l'évolution. L'obervation de telles "soupes" conduit à mettre en évidence des structures simples et fréquentes. Il est rare qu'elle donne naissance à des phénomènes plus complexes.

- structures "stables 1-périodique" :	- "lapin":
- structure "2-périodiques" :	- "remplisseur d'écran":       Cette structure remplit l'écran avec un motif régulier.
- "planeur": Le planeur est une des structures les plus répandues du jeu de la vie. Structure simple constituée de 5 cellules, elle se déplace de manière rectiligne dans l'univers du jeu. Périodique, elle se retrouve identique à elle même au bout de 4 générations. Décomposition du cycle d'un planeur :	- "relai ":
Certaines structures ont la particularité de générer des planeurs : - "lanceur": un générateur de planeurs simple:       - "double-lanceur": un double générateur de planeurs :	- "switchen":
- "aqua 40":	- "eden":  Voici un exemple de jardin d'Eden. On nomme ainsi toute structure de l'univers pour laquelle il n'existe pas d'antécédent selon les règles du jeu de la vie.
- "mémoire":

        CRITIQUES et DOMAINES D'APPLICATION

     Critiques:  
    J.H.Conway est le premier à avoir "popularisé" les automates cellaires dans les année 70. Trente ans après, en publiant "A new kind of science" S.Wolfram attire de nouveau, sur les automates, les yeux d'un public de non initiés. C'est en cette période d'engouement massif pour ce domaine qu'il est intéressant de relativiser la portée de la puissance explicative des automates face au monde naturel et de ne pas se hâter de tirer de conclusions à partir de ressemblances troublantes.
Tout d'abord, l'idée qu'un phénomène imprévisible ou complexe puisse naître de la simplicité n'est pas apparue avec les automates cellulaires. En effet un simple objet déposé dans un écoulement de fluide fait apparaître, selon la vitesse de l"écoulement, des tourbillons et turbulences imprévisibles, d'une compléxité bien supérieure à la situation de départ. Ensuite S.Wolfram avance que les automates cellulaires se retrouvent partout, aussi bien dans les motifs ornant les coquillages que dans les nombres premiers. Là encore les automates ne sont pas pioniers: par exemple les théories du chaos s'appliquent aussi bien à la météo qu'aux cours de la bourse. Ainsi même si automates cellulaires semblrent très prometteurs, il est sage de se ranger auprès de Jean-Claude Heudin lorsqu'il avance que "Le "ça fait penser" n'est pas une démonstration. Je reste donc prudent sur les conclusions. Sinon, on a vite fait de sortir de la science." .

    Applications:
    Quant aux nombreuses applications pratiques des automates cellulaires, leurs résultats n'ont jusqu'à présent fait que confirmer la pertinence du choix de leur utilisation dans de nombreux domaines. Comme nous l'avons vus ils constituent un domaine de recherche passionant de par les "curiosités" mathématiques et philosophiques qu'ils soulèvent mais ils permettent aussi une modélisation computationnelle relativement simple de phénomènes physiques dynamiques complexes.
Fondamentalement ils constituent des univers dont on fixe les lois. Notre Univers est soumis aux lois de la Physique. Ces lois ne sont que partiellement connues et apparaissent hautement complexes. Dans un automate cellulaire, les lois sont simples et complètement connues. On peut ainsi tester et analyser le comportement global d'un univers simplifié. Voici quelques exemples d'application :
    - Simulation du comportement d'un gaz. Un gaz est composé d'un ensemble de molécules dont le comportement est fonction de celui des molécules voisines.
    - Étude des matériaux magnétiques selon le modèle d'Ising : ce modèle (1925) représente le matériau à partir d'un réseau dont chaque noeud est dans un état magnétique donné. Cet état (en l'occurrence l'une des deux orientations du moment magnétique) dépend de l'état des noeuds voisins.
    - Simulation des processus de percolation.
    - Dans un domaine différent, les automates cellulaires peuvent être utilisés comme alternative aux équations différentielles.
    - Conception d'ordinateurs massivement parallèles.
    - Simulation et étude du développement urbain.
    - Simulation des processus de cristallisation.
   - Simulation de la propagation des feux de forêt (par le Cirad): par exemple 4 états (sans arbres / arbre vert / -en feu / -en cendres) et des règles du type "si au moins 1 cellule voisine en feu, alors cellule s'enflamme". (Cf partie liens)
Dans un domaine plus quotidien, les automates cellulaires peuvent être utilisés comme générateur graphique. Les quelques figures ci-dessous, construites avec Capow 4 montrent certains effets graphiques.