Projet de optimisation stochastique : optimisation évolutionnaire de FSM 1)
Trouver le meilleur algorithme par évolution artificielle. Fonction d'évaluation : % tondu (ou nb de cases restantes) après 100 000 pas. Evaluation de la qualité sur une moyenne de 30 runs.
Le choix de la représentation de l'automate est primordiale pour plusieurs raisons : ça conditionne les possibilités de croisement et de mutation, et ça influence le fonctionnement de la fonction d'évaluation (fitness). Notre choix est porté sur une représentation très classique : chaque état est une table de réponses à chaque signal possible en entrée, la réponse étant composée d'un “voeu” de déplacement à l'indication de sa transition d'état (y compris “pas de changement”).
Etant donné que l'énoncé ne mentionne que trois sortes de détection (ou absence de détection), la liste des signaux possibles en entrée peut n'être que de huit (2*2*2). Cependant, pour éviter à l'automate de mémoriser sa dernière voeu de déplacement, nous le lui renvoyons, ce qui multiplie le nombre de cas possibles par neuf ({-1,0,1}x{-1,0,1}). Il est envisageable d'avoir plusieurs réponses possibles pour un même signal; nous n'avons pas pris cette option.
L'initialisation (“conception”) de chaque individu attribue à chacune des 72 signaux d'entrée possibles des chacun de ses états, des réponses choisies au hasard pour les voeux de déplacement horizontal, vertical, et changement d'état. Le changement d'état se spécifie non par “matricule” de l'état successeur, mais par décalage par rapport à l'état courant.
Chaque individu sera doté de sept états 2), dont certains pourront “s'atrophier” si transition vers eux se révèlent désavantageuse.
La fonction de fitness “exécute” chaque automate de la façon suivante, pour un jardin et emplacement de départ donnés3) :
Grande question (pour ne pas entrer un biais) : si elle se déplace en diagonale, elle va occuper 19 (potentiellement) nouvelles cases; est-ce qu'elle coupe les 19? Si oui, est-ce que ça compte un pas ou deux? Logiquement, on peut estimer que ça compte deux pas, ou plus généralement, qu'on compte un pas pour chaque 1 ou -1 dans un voeu. Mais cette règle du jeu n'est pas clairement définie.
Après discussion,
Il y a beaucoup de choix stratégiques dans ce domaine :
Nous n'avons pas trouvé les réponses facilement, et expérimentons encore pour améliorer notre choix.
Les possibilités :
Pour la première série de tests, pas de mutation. Si on constate une convergence trop rapide, on introduira des mutations.
Notre choix pour le développement s'est porte sur EASEA, ce qui nous permet de concentrer nos efforts de développement sur les fonctions de fitness et de croisement (et représentation et initialisation, évidement).
En cours d'évaluation et mise au point.