L-System Genetic Encoding for Scalable Neural Network Evolution: A Comparison with Direct Matrix Encoding

Résumé Technique : Codage Génétique par L-Systèmes pour l'Évolution Scalable de Réseaux de Neurones

Problématique

L'optimisation des architectures de réseaux de neurones artificiels (neuroévolution) via des algorithmes génétiques (AG) se heurte souvent à un problème d'évolutivité (scalability). La méthode standard, le codage matriciel direct, consiste à représenter la topologie du réseau par une matrice de connectivité. Cependant, cette méthode présente une complexité de $O(n^2)$ (où $n$ est le nombre de neurones), ce qui entraîne une explosion de la taille du génotype et une augmentation exponentielle du temps de convergence à mesure que le réseau s'agrandit. Le défi est de trouver un mode de codage plus compact et efficace qui permette une recherche évolutive plus rapide et une meilleure généralisation.

Méthodologie

Les auteurs introduisent une nouvelle méthode de codage appelée Lsys, basée sur les L-Systèmes (grammaires formelles utilisées pour modéliser la croissance biologique).

1. Approche Lsys : Contrairement à la matrice directe, le codage Lsys utilise des règles de production récursives pour générer la topologie. Les auteurs prouvent mathématiquement que cette méthode permet un codage avec une complexité de croissance de seulement $O(\log_2 n)$, offrant une compression massive de l'information structurelle.
2. Environnement de test : Des "animats" (agents artificiels) dotés de réseaux de neurones hebbiens sont placés dans un monde virtuel composé de barrières et de nourriture. La performance est mesurée par la quantité de nourriture collectée.
3. Comparaison expérimentale : L'étude compare trois conditions sur 24 essais :
   • Lsys : Codage par L-Systèmes.
   • Matrix : Codage matriciel standard.
   • MatrixLSG (Contrôle) : Populations initialisées avec des génotypes Lsys mais évoluées avec des opérateurs matriciels (pour isoler si l'avantage vient de la structure initiale ou du processus évolutif lui-même).
4. Outil de simulation : Un outil nommé Wp1hgn a été développé pour gérer l'évolution et la simulation.

Contributions Clés

• Nouveau formalisme de codage : L'introduction de l'alphabet génétique Lsys, qui permet de décrire des structures neuronales complexes de manière parsimonieuse.
• Preuve de complexité : La démonstration théorique que le codage par L-Systèmes réduit la croissance du génotype de $O(n^2)$ à $O(\log_2 n)$.
• Outil logiciel : La création de Wp1hgn, un cadre de modélisation pour l'optimisation de réseaux de neurones hebbiens.

Résultats Principaux

Les résultats démontrent une supériorité écrasante du codage Lsys :

• Performance et Convergence : À la génération 1000, Lsys a atteint un score moyen de nourriture de $3802 \pm 197$, contre seulement $1388 \pm 610$ pour le codage matriciel (un avantage de 2,74x).
• Fiabilité : Lsys est beaucoup plus stable. Le coefficient de variation est de 5,2 % pour Lsys contre 44,0 % pour Matrix, soit une amélioration de la cohérence par 8,5. Toutes les populations Lsys ont réussi l'apprentissage, tandis que 50 % des populations Matrix ont échoué.
• Généralisation : Lors du transfert dans un nouvel environnement (un labyrinthe inconnu), les populations Lsys ont maintenu une performance robuste ($2455 \pm 176$), alors que les populations Matrix se sont effondrées ($422 \pm 212$), montrant un avantage de 5,82x en termes de transfert de compétences.
• Validation du mécanisme : L'expérience MatrixLSG a prouvé que l'avantage de Lsys provient de l'opération continue de l'algorithme génétique sur l'alphabet symbolique compressé, et non simplement de la structure de la population initiale.

Signification et Implications

Cette recherche démontre que la structure hiérarchique et récursive des L-Systèmes capture des propriétés fondamentales de l'organisation neuronale biologique. En passant d'un codage direct à un codage symbolique compressé, on ne gagne pas seulement en efficacité de stockage, mais on guide l'évolution vers des stratégies de navigation plus robustes et généralisables. Cela ouvre la voie à l'évolution de réseaux de neurones beaucoup plus vastes (plusieurs milliers de neurones) avec des ressources computationnelles limitées, remettant en question l'idée que la performance dépend uniquement de l'augmentation brute du nombre de paramètres.