 |
|
|
|
 |
 |
||
 |
 |
 |
|
|
En 1997, le Laboratoire de systèmes logiques a conçu un système matériel évolutif, appelé Firefly, mettant en oeuvre les principes de la programmation génétique afin qu'un ensemble de machines cellulaires résolve un problème spécifique. Le problème en question est une tâche de synchronisation: à partir de n'importe quelle configuration initiale, l'automate cellulaire non uniforme doit atteindre, en M pas de temps, une configuration finale dans laquelle toutes ses cellules oscillent en parfait synchronisme entre des 0 partout et des 1 partout, lors de pas de temps successifs. La nouveauté introduite par le système Firefly, c'est qu'il fonctionne sans dispositif externe (tel qu'un ordinateur exécutant les opérations génétiques) et réalise ainsi une évolution autonome en ligne. Alors que la machine Firefly originale résolvait le problème à l'aide d'un automate cellulaire unidimensionnel, la machine obtenue par évolution sur le BioWall réalise la tâche de synchronisation à deux dimensions. Les bases théoriques de l'extension de la solution de 1D à 2D sont décrites dans le livre cité en référence. L'implémentation sur le BioWall correspond à un automate cellulaire non uniforme à deux états, dans lequel chaque cellule (chaque FPGA du BioWall) peut exécuter une règle différente. Les tables de règles des cellules sont encodées sous forme d'une chaîne de bits, appelée génome. Pour notre automate cellulaire 2D, dont le voisinage est égal à 5, cette chaîne comporte 25=32 bits. Au lieu de recourir à une population d'automates cellulaires évolutifs, notre algorithme procède à l'évolution d'un seul automate non uniforme de la taille du BioWall entier (2000 cellules, soit une cellule par unité) dont les règles sont initialisées de manière aléatoire. De même, on génère aléatoirement plusieurs configurations initiales et chacune d'elle est exécutée pendant M pas de temps. Le fitness de chaque cellule est ainsi accumulé pendant C configurations initiales: le résultat de chaque exécution vaut 1 si la cellule se retrouve dans l'état correct après M+4 itérations, 0 dans le cas contraire. Le fitness relatif à la tâche de synchronisation est assigné à chaque cellule en considérant les quatre derniers pas de temps (M+1 à M+4): si la séquence d'états au cours de ces pas est précisément 0-1-0-1, le fitness de la cellule vaut 1, autrement 0. Toutes les C configurations, les règles sont modifiées par croisement et mutation. Ce processus évolutif est réalisé de manière locale car les opérateurs génétiques ne sont appliqués qu'aux cellules présentant une interconnexion directe. Contrairement aux algorithmes génétiques classiques, dans lesquels une population de solutions indépendantes d'un problème évolue globalement, notre approche met en oeuvre une grille de règles qui co-évoluent localement. L'automate cellulaire implémenté sur le BioWall opère de manière locale car ses cellules n'ont accès qu'aux états de leurs voisines immédiates. Le processus évolutif est également local, puisqu'aussi bien l'application des opérateurs génétiques que le calcul du fitness s'effectuent localement. Cette approche de programmation cellulaire sur le BioWall démontre qu'il est possible de résoudre le problème de la synchronisation en évoluant un automate cellulaire non uniforme de rayon 1. Après avoir trouvé un ensemble de règles adéquates, il est possible de changer l'état de chaque cellule de l'automate en pressant sur sa membrane tactile. L'utilisateur peut ainsi observer comment la machine synchronise ses 2000 cellules. Pour en savoir plus
Ressources
|
