Python L1, Devoir maison 2015

Automates cellulaires

Création et visualisation dynamique, à l'aide du Matplotlib

Ceci est la première partie du devoir. La seconde sera un exercice surveillé sur machine. Ce sujet est loin d'être un banal et insipide exercice dont le seul but serait de vous fournir une galère permettant de voir si vous vous débrouillez avec le codage plus long et compliqué. Ceci est un fascinant sujet scientifique, couvert par des milliers d'articles et de livres.


Un automate cellulaire est une collection de "sites" ("cellules") dans l'espace, discret, 1 ou multi-dimensionnel (rien n'empêche l'usage des espaces 3, 4, voire plus dimensionnels, par ex. dans la simulation des systèmes physiques, mais la visualisation devient alors difficile). Chaque cellule est un "organisme" qui possède un état (représenté par la couleurs de la cellule, ou l'orientation d'une flèche, ou un symbole, etc., si on veut le visualiser de manière simple).

Chaque cellule possède aussi son environnement, les cellules voisines. En une dimension il y a 2 voisins immédiats, en 2 dim : 8, etc. Mais parfois on compte aussi les voisins éloignés, par ex. les voisins immédiats des voisins immédiats !

Finalement, le système dispose d'une stratégie (collection de règles) d'évolution dans le temps (discret). Chaque cellule, dont l'état vaut V au moment T, passera à V' une unité de temps plus tard, T+1. La transition dépend de l'état actuel, et de l'état des cellules voisines (Je répète : en principe on peut inclure dans l'environnement les voisins indirects, un peu éloignés, mais on restera dans le cadre de l'environnement local, proche, pas d'"interaction à grande distance").

Les automates les plus primitfs, "de base", en une dimension, ont été bien analysés. Supposons que l'état de le cellule se réduit aux valeurs 0 et 1 (noir - blanc : vivant - mort, etc.) Alors pour connaître l'état futur d'une cellule, il faut connaître trois chiffres binaires : l'état du voisin gauche, de la cellule elle-même, et du voisin droit. Par exemple 0 1 1 1 ; ... 1 1 0 1, etc.

Ainsi, puisque à gauche nous avons des nombres 000=0 ... jusqu'à 111=7 la règle globale se réduit à la séquence, disons, 01100110 de 8 chiffres binaires, un nombre entre 0 et 255, ici : 102.

À gauche nous voyons la définition de la "règle 102" (102 = 64 + 32 + 4 + 2) ; toutes ont été analysées et classées ; le dessin vient du site de Wolfram. la partie supérieure du graphique montre la règle elle-même. En bas nous avons le résultat de l'activation de l'automate dans le temps, le temps ici c'est l'axe des Y, vers le bas. Au moment initial nous avons un seul site 'vivant', les règles locales 010 1 et 001 1 créent deux cellules vivantes sur la ligne 2.

Plusieurs règles sont assez triviales (par ex. produisent quelques lignes diagonales, ou un "damier"), mais quelques autres produisent des patterns très compliquées, voire aléatoires. [Parfois les résultats dépendent fort de la configuration initiale, parfois non].

Donc, on peut imaginer que les patterns résultants des automates avec un nombre de couleurs plus grand, et jouant avec des environnement plus compliqués, sont considérablement plus riches. Mais même ces automates primitifs semblent avoir un rapport avec la Nature.

On découvre que plusieurs textures naturelles (plantes et animaux) montrent des motifs visuels similaires, que la biochimie des tissus fait évoluer ces motifs "comme" des automates cellulaires.

Voici un exemple (Meinhardt, H. (1995). The Algorithmic Beauty of Sea Shells. Springer Verlag. (p. 179, 180)). C'est la comparaison entre la Nature et la simulation grâce à la "règle 30" (16 + 8 + 4 + 2).

Elle donne des résultats un peu chaotiques même si la configuration initiale est : une cellule vivante.
Voir plus dans ce texte.

L'explication scientifique approximative est que les vraies cellules qui produisent la pigmentation d'un organisme (et ceci peut s'appliquer aux patterns sur les fleurs ou les peaux des zèbres, giraffes, poissons et tigres...) interagissent comme des automates cellulares, avec la diffusion des enzymes aux voisins, les inhibitions par le système nerveux qui fait diffuser d'autres enzymes...

Les détails ne sont toujours pas complètement connus.


L'énoncé du devoir

Vous allez faire les choses suivantes.


Modalités

Vous devez m'envoyer le devoir avant la reprise des cours après les vacances de Pâques [13 - 24 avril], au plus tard : lundi 27 avril! Pas d'exception, pas de dérogation, devoir non-livré recevra zéro en toute indépendance de la suite (l'exercice noté). La solution doit avoir la forme de sources Python, et contenir un mini-rapport d'au moins 5 pages, correctement formaté, où vous décrirez brièvement le problème avec vos mots (pas de copier-coller de mes textes), montrez quelques images à vous, et fournissez au lecteur un manuel d'utilisation. Ce rapport doit être assez complet, avec vos noms, page de titre, dates, etc. Une négligence gratuite de votre part aura des conséquences fâcheuses ; commencez à le rédiger simultanément avec le codage ; traitez-le comme un "log" de vos activités, afin d'avoir sous la main la description de vos difficultés, les références et les morceaux de code réutilisables. Zippez les sources avec le rapport, et envoyez le paquetage zip par mail à mon adresse.

Votre devoir surveillé du 29.04 sera basé sur cet exercice, par exemple une petite généralisation de l'espace d'états, non pas deux, mais trois, avec plus de couleurs, etc. Peut-être avec l'environnement (voisinage) généralisé. Donc la généralité de votre solution maison est importante, sinon vous serez obligés de reprendre tout à zéro, et le temps vous manquera.

N'hésitez pas à poser des questions concrètes, je répondrai vite. Les plaintes genre "je ne savais pas comment résoudre un tel ou tel problème technique" seront irrecevables.


Littérature (Internet) sur les automates cellulaires

Bien sûr commencez par Wikipédia, c'est déjà pas mal, si on suit les références.


Commentaires méthodologiques et techniques.

Même si en principe vous pourrez dessiner directement les rectangles de couleur sur la surface de la figure Matplotlib, ceci serait une solution inefficace.

Les tableaux numpy c'est la manière la plus commode de stocker l'information visualisable sous forme de points, ou cellules individuelles. Pour l'affichage, pas besoin d'une interface genre Tkinter ou PyQt, ou wx : ces paquetages de bas niveau sont "couverts" totalement par Matplotlib, qui vous offre les outils de haut niveau. Profitez des exercices faits jusqu'à présent. Je décris comment modifier le tableau affiché sur place, sans faire de nouveaux imshow.

Le scrolling (défilement) avec les tableaux numpy est facile. Regardez dans la documentation du numpy les fonctions roll et pad.

Pour faire de l'animation, vous pourrez utiliser - c'est la solution la plus facile - le dispositif "functional animation" du Matplotlib. Des gens sérieux ne le feront pas, car ce système est vraiment pour les débutants, et peut être bloquant. On a en Python les threads (la possibilité d'exécuter plusieurs morceaux de code en parallèle), les temporiseurs (timers) qui déclenchent une activité périodique, disons, 10 fois par seconde, etc.

J'ai présenté la commande ginput() qui récupère un clic souris, et rend les coordonnées. Ceci parfois est délicat, car ginput utilisé trivialement ne sait même pas dans quel 'axes' se trouve le curseur. Mais d'autres dispositifs "événementiels" existent, et peuvent être plus utiles. Regardez cette partie de la documentation, et cet exemple. Voir aussi la fonction inaxes dans les références ci-dessus, ou ici.

L'icône "men at work" ne signifie pas que l'énoncé ne soit pas complet, mais suggère que si vous posez des questions qui demanderont des explications supplémentaires adressées à tous, le texte peut subir des modifications.



Retour à l'index