Modèles de Structures Aléatoires de Type Réaction-Diffusion - Thèse de Morphologie Mathématique - Luc Decker, Ecole des Mines de Paris (1999)

suivant: 3. Les Gaz sur   remonter: 2. Modèles de diffusion   précédent: 2.2 Marcheurs aléatoires   [Table des matières]

2.3 Automates cellulaires

Vers le début des années 70, le développement de l'informatique a été à l'origine d'un fort engouement pour les automates cellulaires, introduits auparavant par Von Neumann [vonNeumann51,vonNeumann66]. Le plus célèbre d'entre eux est sans aucun doute le Jeu de la Vie de Conway [Gardner70], qui semble avoir initié l'ère des simulations informatiques. Dans cette évolution, les premiers modèles de fluides "volumiques" sont ainsi apparus sous la forme d'automates cellaires. L'espace est y décrit sous la forme d'un réseau régulier: on se donne un ensemble de sites reliés entre eux par un graphe de voisinage de portée unitaire. Les premiers automates cellulaires bidimensionnels ont naturellement été construits sur des grilles carrées avec un graphe de voisinage 4- ou 8- connexe. Chaque site est constitué de $N$ cellules binaires ($N = 1$ pour les premiers automates). Chaque cellule correspond à un emplacement possible pour un élément constitutif du système simulé. La valeur (ou contenu) d'une cellule vaut ainsi $1$ lorsqu'elle est occupée, et 0 lorsqu'elle est libre. Le contenu des cellules est libre de représenter les individus d'une population biologique, les particules élémentaires d'un fluide, des molécules en cours de réaction, ou encore plus simplement les grains d'une texture binaire synthétisée par l'automate [Wolfram84]. L' état d'un site est caractérisé par les nombres d'occupation de ses cellules; il existe donc un nombre fini de configurations ($2^N$) pour tout site. La valeur d'un site consiste en un nombre entier formé par concaténation des contenus binaires des cellules du site. Ce nombre compris entre 0 et $2^N - 1$ n'a en général comme seule signification le codage d'une configuration donnée, avec unicité. Cependant, par extension, des automates cellulaires fondés directement sur la valeur des sites ont été conçus : des concentrations ou des pressions locales peuvent par exemple être représentées sous forme de nombres entiers, avec quelques normalisations. Dans ce dernier cas, c'est la notion de cellule binaire qui n'a plus de signification. Pour une approche plus détaillée des automates cellulaires, on consultera par exemple la référence [Wolfram86].

Remarquons une différence importante par rapport aux systèmes de particules déjà abordés : dans un automate cellulaire, le volume du système peut être rempli de particules avec une densité ou concentration donnée. Alors qu'un système de particules usuel se fonde sur une liste illimitée de particules associées à leur position dans un espace continu, la taille d'un automate cellulaire correspond à son nombre de cellules, qui dépend directement des dimensions du champ de simulation. On passe ainsi de la notion de particules à celle d'emplacements en nombre finis. En contrepartie, la structure d'un automate cellulaire permet d'accéder directement aux particules présentes dans une région donnée de l'espace. Ce point constitue le principal avantage des automates cellulaires. N'oublions pas qu'il s'agit de modèles qui ont - avant tout - été conçu en réponse à de sévères contraintes informatiques. L'objectif premier résidait dans la mise au point de modèles effectivement opérationnels, dont le niveau de complexité était compatible avec les moyens de calcul alors à disposition. La notion de calculabilité s'avère ainsi primordiale; c'est elle qui influence souvent la mise au point d'un modèle.
L'évolution d'un automate cellulaire est fondée sur l'application de transformations locales, à partir d'un état initial. Ces transformations sont appelées les opérateurs de l'automate; elles sont appliquées séquentiellement, dans un processus itératif. Tous les sites du réseau sont traités simultanément en appliquant le même ensemble de règles d'évolution. Une transformation quelconque peut être basée sur une table pré-calculée, qui à partir de la configuration d'un site, donne directement sa nouvelle configuration après l'application de la transformation. Ces structures de données sont appelées des look-up tables; les automates cellulaires leur doivent en grande partie leur rapidité d'exécution. Par ailleurs, l'accès direct aux sites voisins permet d'appliquer efficacement les règles locales.

Les automates cellulaires forment une catégorie de modèles entièrement discrets:

• les éléments dont on simule l'évolution sont representés sous la forme d'ensembles dénombrables: individus, particules, ou nombres entiers;
• l'espace y est couvert par un réseau reliant un ensemble fini de positions;
• le temps est mesuré comme dans tout processus itératif, en nombre d'évolutions élémentaires.

Il en résulte qu'un automate cellulaire peut évoluer indéfiniment, en évitant totalement les erreurs d'arrondis qui caractérisent habituellement les modèles à base de nombres décimaux.

Pour la simulation d'un fluide, l'automate fonctionne à partir d'un unique opérateur de diffusion. Si le modèle fait intervenir des concentrations locales, la diffusion peut être réalisée de manière simple en remplaçant la concentration en un site par la moyenne des concentrations de son voisinage [Weimar94]. Dans le cas d'un modèle à base de particules, celles-ci peuvent à présent interagir puisqu'elles se trouvent toutes simultanément dans le système, contrairement aux marcheurs aléatoires déjà décrits. Dans le cas le plus simple, chaque particule se déplace aléatoirement entre sites voisins, avec par exemple la condition qu'il reste une cellule libre dans le site destination. Ce point nous amène à introduire les gaz sur réseau, qui constituent une classe particulière d'automates cellulaires de conception plus récente. Grâce à leur structure, ils représentent bien plus qu'un modèle de diffusion, comme nous allons l'évoquer au cours du chapitre suivant.

suivant: 3. Les Gaz sur   remonter: 2. Modèles de diffusion   précédent: 2.2 Marcheurs aléatoires   [Table des matières]

Decker, Luc. "Modèles de structures aléatoires de type réaction-diffusion". PhD diss. (191 p.), Paris, ENSMP-CMM, 1999.