Principe et fonctionnement des automates cellulaires

...

1.2.1 Système dynamique à temps continu

Supposons que nous cherchons un modèle permettant d’étudier le mouvement d’un pendule de masse m et de longueur l données. La position du pendule à tout moment du temps est complètement déterminée si l’on connaît l’angle θ(t).

[pic 1]

On peut donc choisir l’angle comme la seule variable d’état de ce système. En utilisant les lois de Newton on peut facilement écrire l’équation différentielle pour θ(t) :

[pic 2]

Ainsi nous avons construit le modèle de notre système.

Dans le cas général un système dynamique en temps continu peut être représenté par une équation différentielle. Selon l’équation, on distingue quelques différents types de systèmes à savoir :

- les systèmes autonomes : , = 0 ;[pic 3][pic 4][pic 5]

- les systèmes non autonomes : , = 0 ;[pic 6][pic 7][pic 8]

- les systèmes avec plusieurs variables d’état (autonomes ou non-autonomes) :

, = [pic 9][pic 10][pic 11][pic 12]

, = [pic 13][pic 14][pic 15][pic 16]

…..

, = [pic 17][pic 18][pic 19][pic 20]

1.2.2 Systèmes dynamiques à temps discret

Une modélisation discrète du temps peut être imposée soit par la nature même du processus soit par le besoin de "discrétiser" un modèle à temps continu pour le traiter numériquement. L’évolution du système est observée en choisissant certains moments du temps que nous allons supposer équidistants. Dans tous les cas le choix de l’unité de temps représente une partie importante de modélisation du système.

Voici un exemple élémentaire d’un processus dynamique à temps discret.

Supposons que nous avons une population de lapins qui au début de notre expérience compte x(0) lapins. Nous savons qu’en une année la population augmente de 10%. Notons par x(n) le nombre de lapins de la nième année. Nous voulons décrire l’évolution de x(n).

Après une année on obtient lapins[pic 21]

[pic 22]

Au cours de la deuxième année, nous avons :

[pic 23]

En continuant pour une année quelconque, on a :

[pic 24]

Ainsi pour chaque période de temps n, on a :

[pic 25]

Avec [pic 26]

Autrement dit, la dynamique de la population peut être décrite, comme dans l’exemple précédent, par l’itération d’une fonction En connaissant cette fonction nous pouvons reconstituer l’état du système à chaque moment du temps.[pic 27]

Dans le cas général, un système dynamique discret est décrit par un système d’équations aux différences finies, autrement dit, par une récurrence. Il existe, comme dans le cas continu, plusieurs types de systèmes.

---------------------------------------------------------------

- Les automates cellulaires

- Définition

Un automate cellulaire consiste en une grille régulière de « cellules » contenant chacune un « état » choisi parmi un ensemble fini et qui peut évoluer au cours du temps. L'état d'une cellule au temps t+1 est fonction de l'état au temps t d'un nombre fini de cellules appelé son « voisinage ». À chaque nouvelle unité de temps, les mêmes règles sont appliquées simultanément à 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.

Formellement un automate cellulaire est un quadruplet où :[pic 28]

- sa dimension, qui est la dimension de son réseau ;[pic 29][pic 30]

- un ensemble fini d’états, appelé alphabet ;[pic 31]

- son voisinage ;[pic 32]

- sa règle locale de transition.[pic 33]

Une configuration de l’automate est une application de de dans : on associe à chaque cellule de l'automate un état.[pic 34][pic 35][pic 36]

Si on note l'ensemble des configurations de , l’automate cellulaire peut être considéré comme un système dynamique discret en munissant de la fonction globale de transition de l’automate , autrement dit de la fonction d’évolution temporelle de la configuration.[pic 37][pic 38][pic 39][pic 40]

Cette fonction est : et est définie cellule par cellule par[pic 41]

[pic 42]

L'automate cellulaire décrit alors le système dynamique

[pic 43]

[pic 44]

- Quelques exemples d’automates cellulaires

- Les automates cellulaires élémentaires (ACE)

Un automate cellulaire élémentaire est un automate cellulaire tel que sa dimension , les cellules ne peuvent prendre que deux états possibles (« 0 » ou « 1 »), le voisinage pour chaque cellule est constitué d’elle-même et des deux cellules qui lui sont adjacentes. Chaque cellule ne peut prendre que deux états, donc on a au total configurations possibles d’un tel voisinage. La règle de transition d’un ACE est une fonction de dans . Pour huit configurations avec deux états possibles, nous avons jusqu’à règles de transition possibles.[pic 45][pic 46][pic 47][pic 48][pic 49]

Toutes les expériences qui suivent seront réalisées avec le logiciel Golly. C’est un simulateur performant d’automates cellulaires. En plus, il est libre, gratuit et multiplateforme. Il permet de programmer les différentes règles gérant les automates et contient déjà beaucoup d’automates cellulaires