Approche par algorithmes génétiques

NB : non mise en oeuvre faute de temps.

Détaillons en tout de même les idées principales.
On a vu qu'une approche mathématique déterministe exigeait du RCX des capacités de calcul auxquelles il ne saurait prétendre. On a vu également durant les phases de développement qu'intervenaient dans la majorité des portions du code des temporisations, des paramètres divers, qui ont été introduits parce que cela marchait mieux avec que sans.

Un ajustement grossier de ces paramètres a permis d'obtenir certains résultats, mais vu le nombre de ces paramètres et leur interdépendance, la complexité de cet ajustement devient rapidement insurmontable. C'est la qu'une approche par AG est envisageable. En effet, on va comme il se doit considérer une population d'individus. Ces individus ne seront que des vecteurs (gènes) contenant une valeur pour chacun des paramètres évoqués ci-dessus. Ces valeurs sont bien sûr empreintes d'aléatoire, de sorte que les individus sont a priori différents.

À chaque individu correspond donc un code C mettant en jeu ces paramètres, et donc également un exécutable pour le RCX après compilation^2.5. La population d'individus se trouvera bien évidemment sur le PC et on testera l'ensemble des individus de la population originelle sous la forme de binaires downloadés tour à tour sur le robot. Chaque individu de la population doit être évalué, afin de connaître son adéquation au problème posé. Pour ceci, on prendra de facon naturelle comme fonction d'adéquation le temps pendant lequel le pendule est resté en l'air durant l'essai. Chaque test d'individu se solde donc par une évaluation de sa performance. Le robot renvoie ses résultats sur le PC qui renvoie de son côté un nouvel individu sur le RCX et commence son évaluation.

Il est alors possible de classer sur le PC les individus de la population selon leur adéquation au problème. Lors de la génération suivante seuls seront autorisés à y contribuer les individus ayant présenté de bonnes performances, la population originelle sera ainsi remplacée par une population d'individus généralement mieux adaptés au problème. Lors de la constitution de cette nouvelle population intervient l'arsenal des métaphores biologiques classiques. On parle alors de croisements, mutations, crossing-over de génotypes.

D'une génération sur l'autre, les individus les mieux adaptés seront plus performants que les anciens et la population entière sera globalement plus adaptée. On a donc une convergence de la population d'individus vers un individu "optimal". En pratique, il est nécessaire de jouer sur des paramètres comme la taille des populations, le nombre de générations,le taux de mutation, le type de croisements employés, de façon à obtenir une convergence suffisamment rapide, sans remettre en cause une diversité dans la population essentielle pour une bonne exploration du domaine de solutions.

On s'expose par cette méthode à de sévères contraintes de temps, vu qu'on ne peut évaluer les individus que l'un après l'autre et qu'en general il faut faire un certain nombre de tests pour apprécier les performances d'un robot, tant la moindre vibration malvenue peut être fatale. Il faut compter environ deux minutes pour une session compilation / download / test / upload, avec un minimum d'une centaine d'individus par génération, et également une centaine de générations, soit 40 jours de tests intenses à raison de 8 heures par jour (excellent sujet de stage pour un étudiant patient ;-). C'est difficile à mettre en place en parallèle faute de robots identiques. Il faut prévoir aussi un budget piles important, au moins douze par jour !

Lors de l'évaluation, on sent la nécessité d'avoir une procédure de mise en route identique (standardisée) pour tous les individus, ceci afin de ne pas fausser ce processus d'évaluation. Pas question donc de caler à la main chaque individu avant de le faire évoluer, car on introduirait une influence externe. Peut-être que le temps passé en l'air par le pendule n'est pas la fonction d'adéquation au problème idéale, peut-être faut-il aussi prendre en considération le style et comportement global du robot.

Le sujet est donc intéressant, et mériterait d'être exploré de façon plus profonde. On verrait peut-être apparaître de nouvelles façons de gérer ce problème, une sous-population de vibreurs parmi une majorité d'oscillateurs ? Bien évidemment, le seul regret c'est qu'on ne puisse agir de même au niveau matériel...