I.      HISTORIQUE ET DEFINITION

Vie Artificielle

Une découverte fondamentale du XXe siècle reste l’ordinateur qui joue un rôle important. En fait tous les ordinateurs actuels sont les descendants de la « machine de Turing » conçue en 1935 par Alan Mathison Turing. Ce mathématicien britannique est également un pionnier de l’intelligence artificielle. Il a proposé même un test – fameux, mais controversé – permettant de déterminer si un ordinateur « pense », cependant à cette époque il n’y avait pas d’ordinateur pour le confirmer. Mais ça était l’origin des domaines de l’Intelligente artificielle et la vie artificielle.

La vie artificielle a été définie par Christopher Langton en 1989 comme étant "l’étude de systèmes construits par l’homme qui présentent des comportements caractéristiques des systèmes vivants". Ainsi la définition de la vie artificielle est étroitement dépendante de celle de la vie.

La vie artificielle est d'une conception proche de celle de l'intelligence artificielle (IA), mais il y a des différentes entre les deux :

L'IA prend  la cognition humaine comme référence et s’intéresse à la conception de machines pouvant simuler la cognition humaine. Quant à la vie artificielle, elle tend à se rapprocher des fonctionnements biologiques et se rapproche plus des comportements "réflexes" que des raisonnements logiques ou des actes cognitifs. Son domaine d’étude est plus vaste, elle explore les caractéristiques du vivant en général.

Automate Cellulaire

Dans les années 40, le mathématicien John Von Neumann a été le premier à s'intéresser à la manière par laquelle une machine pourrait se reproduire, c'est à dire produire une copie d'elle-même. Avec l’aide de son collègue Stanislaw Ulam, pour résoudre son problème sur des système auto-réplicatifs il a conçu un modèle mathématique abstrait qui est le premier automate cellulaire : il était basé sur une grille à deux dimensions.

Un automate cellulaire consiste en une grille de « cellules » pouvant chacune prendre à un instant donné un « état » parmi un ensemble fini. Le temps est également discret et l'état d'une cellule au temps t est fonction de l'état au temps t-1 d'un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées pour toutes les cellules de la grille, produisant une nouvelle « génération » de cellules dépendant entièrement de la génération précédente.

On peut définir un automate cellulaire (AC) par le quadruplet A= (d, G, S, f), avec :

n      d,  le nombre de dimensions : Le plus généralement 1 (AC élémentaire) ou 2 (AC type Life), il n'y a pas de limite à la dimension d'un automate, si ce n'est pas la puissance de calcul des machines sensées le reproduire.

n      G, le voisinage cellulaire, soit l’ensemble des cellules qui sont prises en compte dans la détermination du voisinage. Pour les automates à deux dimensions, les voisinages les plus courants sont :

      ---Von NEUMANN (figure 2.1), on ne considère que les seuls voisins nord / sud/ est/ ouest.

      ---Moore (figure 2.2), on ajoute les diagonales au voisinage de Von NEUMANN, soit les 8 voisins.

      ---Moore étendu, on étend la distance d’un voisinage de Moore au-delà de 1.

Figure 2.1                                                                               Figure 2.2

n      S,  un ensemble fini d’états. Le plus souvent limité à 2, il n'y a aucune limite théorique. Pratiquement, ces états sont représentés par des couleurs, qui permettent de suivre les évolutions de l'automate.

n      f,  la fonction de transition. C'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écèdent de son voisinage.
Pour un automate à n états et avec un voisinage de k cellules, il peut y avoir n^k configurations de voisinage différentes.
pour n=2 et k=3, n^k=8 voisinages différents (AC élémentaire de wolfram).
pour n=2 et k=9, n^k=512 voisinages différents (jeu de la vie).
De plus, la fonction de transition est créée en associant à chaque voisinage un état de sortie. Il y a donc potentiellement n^(n^k) fonctions de transition pour un automate cellulaire à n états ayant un voisinage de k cellules.

 

Classification de Stephen Wolfram

Stephen Wolfram, le mathématicien créateur du fameux logiciel Mathematica, s’est beaucoup intéressé aux automates cellulaires. Pour lui, la question se posait de l’élaboration de règles générales de classification de ces automates.

Il a essentiellement considéré les automates à une dimension, l’objectif étant de parvenir à une analyse exhaustive dans un cadre donné, la multiplication des dimensions aurait rendu la tâche insurmontable. Généralisant ses résultats, il en a déduit que la plupart des automates entrent dans quatre grandes catégories :

1.                                2.                                3.                                4.

Figure: Wolfram classe exemples

Classe I :

L'évolution de l'automate conduit à un état homogène (par exemple, toutes les cellules mortes).
La prédictibilité 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ériodiques, mais en tous cas simples et séparées.
La prédictibilité d'évolution reste faisable. Les effets d'une cellule se propagent à 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, les automates sont caractérisés par une succession de configurations chaotiques. Malgré leur caractère désordonné et leur instabilité au niveau local, on peut dire que l’on obtient certaine forme de stabilité dynamique au niveau global.

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.

Le terme ‘attracteur’ comme des comportements physiques sont utilisés pour désire les classes de Wolfram. Ici, les attracteurs sont les boucles dans l’espace des états, et la période de l'attracteur signifie  le temps de parcours de la boucle. Si cette période est 1, l'attracteur est un point fixe. la période est supérieure à 1, l'attracteur est cyclique. L'ensemble des configurations évoluant vers un attracteur donné constitue un bassin d'attraction.

La classe I de Wolfram correspond à un attracteur fixe, la classe II à un attracteur cyclique et la classe III à un attracteur étrange ( ou chaotique). Dans le cas de la classe IV le lien avec des comportements physiques connus n’est pas aussi évident. Leur comportement est complexe et imprévisible.

***********************************************************************************************************************************************************

II. Jeu de La Vie de Conway

A la fin des années soixante, le mathématicien anglais John Conway s’est intéressé aux travaux de Von Neumann concernant les automates cellulaires. Pour lui, il devait être possible de réaliser un automate cellulaire beaucoup plus simple que celui de Neumann, tout en ayant des capacités de calcul universel au sens de Turing. Après deux ans de travail et d’essais, il a abouti à ce que l’on connaît maintenant sous le nom de ‘ jeu de la vie’ (Game of Life), qui devenait rapidement la vedette des récréations informatiques.

Principe

Le jeu de la vie est le meilleur exemple d'automate cellulaire 2D. On peut expliquer cet automate cellulaire par le quadruplet A= (d, G, S, f) qu’on a parlé avant.

Pour le jeu de la vie, d=2 ( 2 dimensions) ; la configuration de voisinage G est le type de Moore ; Quant à l’état S, chaque cellule peut prendre deux valeurs que l’on peut assimiler pour les besoins de l’exposé au couple vie(1)/mort(0), ou actif(1)/inactif(0). Et la fonction de transition f se compose de seulement trois règles élémentaires :

---R1 : une cellule morte (0) entourée d’exactement 3 cellules vivantes ‘naît’ (elle passe à l’état 1.)

---R2 : une cellule vivante (1) entourée de 2 ou 3 cellules vivantes reste en vie (elle reste à l’état 1.)

---R3 : dans tous les autres cas la cellule ‘meurt’ (elle passe à l’état 0.)

Le succès du jeu de la vie de Conway doit une bonne part de son succès à sa règle de transition, qui, malgré sa simplicité, produit une grande variété de structures et des dynamiques complexes évoquant l’émergence du vivant dans une soupe primitive.

 Caractéristique

Une des caractéristiques de la règle de Conway réside dans son déterminisme. En effet, elle ne fait intervenir aucun aléa ni un quelconque tirage au sort. A partir d’une configuration initiale donnée, on obtient toujours la même succession de configurations de la matrice cellulaire.

En partant d’une configuration arbitraire de cellules à l’état 1 ou 0, après seulement quelques dizaines d’itérations, la population de cellules vivantes diminue sensiblement. L’écran se peuple alors des structures étranges, de motifs géométriques qui oscillent et changent de forme. On peut s' interroger : comment cette complexité peut-elle provenir d’une règle aussi simple ?

L’autre caractéristique est sur les structures remarquables produit par cette règle :

Voici quelques structures très simples que l'on peut observer :

• structure stables (1-périodique) :

• structure 2-périodiques :

• Des structures un peu plus évoluées comme les ‘planeur’ apparaissent également. (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 :

Formalisme de Carter Bays

Pour étudier les conditions différentes d’émergence de règle de jeu de la vie, à partir de 1987, Carter Bays, a proposé dans un ensemble d'articles une approche plus formelle du Jeu de la Vie. Chaque type de jeu peut être écrit avec une règle de la forme :
                   EbEhFbFh

Où Eb représente le nombre minimum de voisins d'une cellule vivante pour lui garantir sa survie, Fb définit le nombre minimum de voisins nécessaires à une cellule morte pour la faire passer à l'état vivant. Les valeurs Eh et Fh sont les bornes supérieures correspondantes. Ainsi, le Jeu de la Vie standard de J. Conway se note dans ce formalisme : "Life 2333".

Les règles peuvent aussi être généralisé comme les suivantes :

n      Si [(St=0) ET (Nt>=Fb) ET (Nt<=Fh)] OU [(St=1) ET (Nt>=Eb) ET (Nt<=Eh)] alors St+1:=1

n      Sinon St+1:=0

  Où St représente l'état de la cellule à l'instant t et Nt le nombre de cellules voisines vivantes.

En faisant varier les valeurs des quatre paramètres Eb, Eh, Fb et Fh entre1 et 8 de manière à obtenir des intervalles valides, on obtient un ensemble de 1296 règles de transitions différentes. Des variations sur les valeurs EbEhFbFh aboutissent à des résultats très divers, d'états très stables à des états très chaotiques