Upload
joel-thebault
View
131
Download
2
Embed Size (px)
Citation preview
Automate Cellulaire
A.C et complexité
2D A.C : Conway’s Game of Life
1D A.C : Automate Cellulaire de Wolfram
UNSA – Maîtrise Informatique - Option SAC
Automate Cellulaire
Simulation informatique qui émule les lois de la nature
Cellules = "agents" répondant à des stimuli selon des
règles simples, mais collectives
2-d : Game of Life (Conway 1970)
1-d : Automate Cellulaire (Wolfram 1980)
UNSA – Maîtrise Informatique - Option SAC
Automate Cellulaire et Complexité
Avant 1980, on pensait que les équations mathématiques étaient le meilleur moyen de modéliser la nature
En 1980, Stephen Wolfram proposa des modèles basés directement sur de simples programmes informatique
Même si les règles sont très simples, le comportement peut être complexe et imiter des phénomènes naturels
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life: un automate cellulaire
Le Jeu de la Vie montre comment un automate cellulaire simple, gouverné par des règles de transition simples peut exhiber des "propriétés émergentes" :
Un haut degré de complexité semble être plus que la simple somme de ses composants
On est tenté de faire un parallèle avec la vie réelle, ou les particules obéissant aux lois de la physique ont, au cours de l'évolution, permis l'émergence d'un monde complexe
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life: un automate cellulaire
Inventé par le mathématicien Conway 1970
Les "individus vivent" sur une grille rectangulaire (2D)
Un case est vide ou occupée (automate à 2 états)
Une case a 8 voisinsVoisinage de Moore
1 2 3
4
567
8
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life 2 ou 3 voisines pour survivre, 3 pour naître
A chaque génération l'état de chaque case à la génération suivante est fonction de son état et de celui des 8 cellules qui
l'entourent
n états, v voisins
nn^(v+1) = 22^(8+1) = 2512 règles
NaissanceSi 3 voisins sont vivants, naissance dans un site vide
DécèsIsolation : moins de 2 voisins vivants (0 ou 1)
Sur-population : plus de 3 voisins vivants (4,5,6,7 ou 8)
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Survie : 2 ou 3 voisins
3
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Mort : 4 voisins ou plus
4
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Mort : 0 ou1 voisin
0
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Naissance : 3 voisins
3
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Un exemple à la main …
1
4
3
3
3
3
3
33
3
1
1
111
1
1
1
1 1 1
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Un exemple à la main …
8 4
4
4
4
2
2 2
2 2
2
22
2
2
2 23
3
3
3
1
1 1
1
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Un exemple à la main …
2
2
22
2
2
2 2 1
11
1
4
3
3
3
3
2
2
2
2
2
2 2
2
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Un exemple à la main …
1
1 1
1
3
3
3 3
3
3
33
3
3
3
3
8
4
44
4
5
5
5
5
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Un exemple à la main …
2
22
2
2 2
2
2
22
2
2
2 2
2
2
0
4
44
4 3
3
3
33
3
3
3
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Un oscillateur et d'autres exemples ...
1
2
3
1
3
1
2
22
2
1
1
000
1
1
1
0 0 0
UNSA – Maîtrise Informatique - Option SAC
Conway's Game of Life
Période 3 !
UNSA – Maîtrise Informatique - Option SAC
Un double oscillateur : temps/espace
UNSA – Maîtrise Informatique - Option SAC
Un double oscillateur : temps/espace
UNSA – Maîtrise Informatique - Option SAC
Un double oscillateur : temps/espace
UNSA – Maîtrise Informatique - Option SAC
Un double oscillateur : temps/espace
UNSA – Maîtrise Informatique - Option SAC
Un double oscillateur : temps/espace
UNSA – Maîtrise Informatique - Option SAC
The glider gun
UNSA – Maîtrise Informatique - Option SAC
Eco-système Proie / Prédateur
Comportement des loups• Reproduction : 2 loups adultes côte à côte• Nourriture : le loup mange un mouton, s'il y en a un
à côté de lui• Le loup choisit la nourriture avant la reproduction
Comportement des moutons • Reproduction : 2 moutons adultes côte à côte• Nourriture : Le mouton mange de l'herbe, s'il y en a
à côté de lui• Le mouton choisit la reproduction en priorité
Mort d'un animal• Atteint la limite d'âge• Dépasse la durée maximal de jeûne
UNSA – Maîtrise Informatique - Option SAC
Un Calculateur Universel
Peut-on créer des courants de glisseurs et les faire interagir
entre eux pour obtenir des portes logiques et,ou, non, comme
dans un circuit électronique ?
Les éléments de base pour construire un ordinateur universel
(c’est-à-dire capable de calculer toute fonction calculable) sont
donc présents
Il est donc possible de faire calculer les nombres premiers à
une configuration, ou les coefficients du binôme ou tout ce
qu’un ordinateur sait calculer
UNSA – Maîtrise Informatique - Option SAC
Un Calculateur Universel
Un automate qui permet de construire des circuits composé de "fils" dans lesquels se propagent des signaux composés chacun d'un électron et de sa trace
4 états : vide , fil , électron , trace
Règles de transitions : •Une cellule vide reste vide•Un électron devient trace•Une trace devient fil•Un fil devient un électron si le nombre d'électrons parmi les huit cellules voisines est 1ou 2, sinon le fil reste un fil
UNSA – Maîtrise Informatique - Option SAC
Un peu d'électronique ...
UNSA – Maîtrise Informatique - Option SAC
Porte logique OU
UNSA – Maîtrise Informatique - Option SAC
Porte logique XOR
UNSA – Maîtrise Informatique - Option SAC
Automate auto-réplicatif de Langton
Automate proposé en 1978• 8 états• voisinage de 5 cellules
La 'machine' de base est une boucle de 86 cellules– formant un conduit de circulation de données fermé
(cellules bleues)– entouré par une gaine (cellules rouges)
comprend également un bras de projection qui permet sa duplication
UNSA – Maîtrise Informatique - Option SAC
Automate auto-réplicatif de Langton
Le conduit permet la circulation de l'information sous forme de signaux : couples de cellules (bleu clair-noir ou jaune-noir)qui constituent en fait le matériau génétique de la structure (génome) et en permet la reproduction
Au moment ou les signaux 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 du processus biologique
UNSA – Maîtrise Informatique - Option SAC
Automate auto-réplicatif de Langton
En arrivant au bout du bras, les signaux sont transformés en instructions. C'est l'équivalent de la translation du processus biologique
Le bras s'étend selon ces mêmes instructions pour former
une autre structure similaire à la première et contenant le même patrimoine informationnel permettant la réplication
UNSA – Maîtrise Informatique - Option SAC
Automate auto-réplicatif de Langton
UNSA – Maîtrise Informatique - Option SAC
Où Est L'intérêt ?
Permet, à partir de règles simples, de faire émerger des
phénomènes complexes
Le « jeu de la vie » est considéré comme une référence
par les chercheurs s'intéressant à la vie artificielle
– il montre que des règles très simples peuvent permettre de
mettre en évidences des fonctionnements non triviaux
– pouvant simuler la richesse et la diversité de la vie
– même si personne ne prétendra que le Jeu de la Vie est aussi
riche que la vie
UNSA – Maîtrise Informatique - Option SAC
1-D Cellular Automata Le Jeu de la Vie est encore trop compliqué pour être étudié de façon
approfondie
Stephen Wolfram introduit un AC plus simple (1982)
Automate Cellulaire de dimension 1– 1 dimension spatiale
– 2 états possibles par cellule
– Voisinage de rayon 1 (état dépend de son propre état et de celui de ses deux
voisins)
– 28 = 256 Règles de transitions :
règle 22 =00010110
111 110 101 100 011 010 001 000
0 0 0 1 0 1 1 0
UNSA – Maîtrise Informatique - Option SAC
Avantage de l’automate cellulaire 1-D Dynamique visible sur une image 2-D 256 règles de transition seulement
– On peut examiner la dynamique pour toutes les règles– K = # états r = rayon du voisinage– # automates = k^k^(2r+1)
Un tel système peut-il engendrer des comportements complexes ?
Le réponse est « oui ». Les règles conduisent à un état– statique– périodique– chaotique– intermédiaire, un état "complexe", l’état de la vie biologique
UNSA – Maîtrise Informatique - Option SAC
Règle 4 (0000100)
010 donne 1, sinon 0
Règle très simple
Configuration limite– contient des ‘1’ isolés– Obtenue en 1 cycle
UNSA – Maîtrise Informatique - Option SAC
Règle 110 (01101110)
001,010,011,101,110 donne 1 sinon 0
Une des plus complexes Membre de la Classe 4 de Wolfram Nombreux glisseurs (gliders) qui se propagent
périodiquement Entre l’ordre et le chaos
UNSA – Maîtrise Informatique - Option SAC
Règle 30 (00011110)
001, 100, 010, 011 donne 1 sinon 0
Génère des configurations avec un haut degré d’aléatoire
Exploité en cryptographie
UNSA – Maîtrise Informatique - Option SAC
Un automate cellulaire en action
UNSA – Maîtrise Informatique - Option SAC
Propriétés
Auto-organisation• Émergence de formes (pattern)• Même si l’état initial est aléatoire, les règles
« forcent » l’émergence
Comportement « Life-like »• Disparition (die)• Stable• Cyclique avec une période fixe• Expansion à vitesse constante• Expansion et contraction irrégulières
UNSA – Maîtrise Informatique - Option SAC
Classification de Wolfram Classification proposée par Stephen Wolfram (1984)
– Classe 1 – état limite homogène (indépendant état initial)
– Classe 2 – état limite périodique (effet local des modifications)
– Classe 3 – chaotique
– Classe 4 – complexe (capable de computation universelle)
Existe-t-il un paramètre qui détermine l’appartenance à chaque classe ?
UNSA – Maîtrise Informatique - Option SAC
Classe 2 : état limite périodique
Voisinage : 6# Etats : 3Règle : 111443344111
Motifs périodiques (petite période) ou stable
http://www.irdp.ch/math-eco/articles/automa7.htm
UNSA – Maîtrise Informatique - Option SAC
Classe 4 : complexe (computation universelle)
Voisinage : 3 # Etats : 4Règle: 0201313201
Beaucoup de cellules « meurt »Quelques motifs périodiquesCapacité de calcul universel : game of life Dynamique irréversible
UNSA – Maîtrise Informatique - Option SAC
Classe 3 : chaos
Voisinage : 3 # Etats : 5Règle: 012344444014
Motifs apériodiques – chaotiquesPrédiction difficileMotifs fractals (self-similar)
UNSA – Maîtrise Informatique - Option SAC
On the Edge of Chaos
Concept introduit par Christopher Langton– Etat le plus « créatif » d’un système dynamique– Aller-retour permanent entre ordre et chaos
Problème : trouver un paramètre qui caractérise la transition entre l’ordre et le chaos
Langton propose le paramètre :– Probabilité qu’une cellule devienne active à la
génération suivante
UNSA – Maîtrise Informatique - Option SAC
On the Edge of Chaos
0Pas de développement
near 0une cellule « meurt » rapidement
0 << < 0,3classe 2 – motifs périodiques
Point "critique" ~ 0,3classe 4
~ 0,5classe 3
UNSA – Maîtrise Informatique - Option SAC
Intérêts Montre que même si notre univers nous
apparaît complexe, cela n'entraîne pas que ses lois le sont nécessairement
Principe du rasoir d'Occam :– minimiser ce qu’on fait intervenir dans une
explication– exploration du minimum générant la complexité
Travail scientifique aussi important que bien d’autres qui ne sont pas toujours aussi
amusantes et esthétiques!
UNSA – Maîtrise Informatique - Option SAC
Applications
Cellular automata applications are diverse and numerous. Fundamentally, cellular automata constitute completely known universes. Our Universe is submitted to the laws of physics. These laws are only partly known and appear to be highly complex. In a cellular automaton laws are simple and completely known. One can then test and analyse the global behaviour of a simplified universe, for example :
1. Simulation of gas behaviour. A gas is composed of a set of molecules whose behaviour depends on the one of neighbouring molecules.
2. Study of ferromagnetism according to Ising model : this model (1925) represents the material as a network in which each node is in a given magnetic state. This state - in this case one of the two orientations of the spins of certain electrons - depends on the state of the neighbouring nodes.
3. Simulation of percolation process. 4. Simulation of forest fire propagation. 5. In a different field, cellular automata can be used as an alternative to differential equations9. 6. Conception of massive parallel computers. 7. Simulation and study of urban development10. 8. Simulation of crystallisation process. 9. (...)
In a more daily field, cellular automata can be used as graphic generators11. The several images below, generated with Capow, show some graphic effects.
But it is undoubtedly in the field of artificial life that cellular automata are most known.