- En vol
- Cible atteinte
- Écrasées
- Meilleur vol de la dernière génération
- Cible atteinte
- Écrasées
Terrain de jeu d'algorithme génétique
Un algorithme génétique résout un problème comme l'évolution façonne les êtres vivants : essayer de nombreuses réponses au hasard, garder les meilleures, les mélanger, en modifier quelques éléments au hasard, et recommencer. Ici, les réponses sont des fusées. Chacune suit une liste de poussées aléatoires et rien d'autre, et au début elles tourbillonnent sans but. Appuyez sur « Lancer » et regardez la population s'améliorer génération après génération, jusqu'à ce que la plupart des fusées contournent les murs pour rejoindre la cible, sans que personne ne leur dise où aller. Appuyez sur « Lancer » et regardez une population de fusées essayer d'atteindre la cible verte. Chaque fusée ne suit que ses gènes, une liste de petites poussées, une pour chaque instant de son vol. Après chaque vol, les fusées qui se sont le plus approchées, et surtout celles qui sont arrivées, ont le plus de chances de devenir les parents de la génération suivante ; leurs gènes sont mélangés et quelques-uns sont modifiés au hasard. « Génération suivante » saute le reste d'un vol. Faites glisser sur le terrain pour dessiner un mur, et cliquez sur un mur pour le supprimer.
Comment ça marche
- Choisissez des obstacles, ou faites glisser sur le terrain pour dessiner vos propres murs, et réglez la population, le taux de mutation et la durée de vie.
- Appuyez sur « Lancer » et regardez voler chaque génération ; « Génération suivante » saute le reste d'un vol.
- Suivez dans les tuiles et le graphique la part qui atteint la cible, et essayez d'autres taux de mutation et méthodes de sélection.
Comment les fusées évoluent
Chaque fusée porte des gènes : une petite poussée pour chaque instant de son vol. Les gènes de la première génération sont aléatoires. Après le vol, chaque fusée reçoit un score de fitness, maximal pour une arrivée précoce, puis d'autant plus élevé qu'elle a fini près de la cible, et divisé par dix après un crash. Les parents de la génération suivante sont choisis au hasard, mais les fusées les plus aptes ont plus de chances d'être choisies. Chaque enfant prend la première partie de ses gènes chez un parent et le reste chez l'autre, et quelques gènes sont remplacés par des poussées aléatoires : les mutations. Au fil des générations, les bons plans de vol se répandent et s'améliorent.
Ce que changent les réglages
Une population plus grande explore davantage de plans de vol à la fois et risque moins de rester bloquée, mais chaque génération prend plus de temps. Le taux de mutation équilibre l'exploration et la conservation de ce qui fonctionne : sans mutation, la population est vite à court d'idées nouvelles ; avec trop de mutation, elle oublie les bons vols plus vite qu'elle ne les trouve. La sélection par roulette choisit les parents proportionnellement à leur fitness, tandis qu'un tournoi prend la meilleure de trois fusées tirées au hasard, ce qui est moins sensible à l'échelle de la fitness. L'élitisme copie la meilleure fusée sans changement dans la génération suivante, si bien que le meilleur résultat ne se dégrade jamais.
Questions fréquemment posées
Pourquoi les fusées restent-elles bloquées derrière les murs décalés ?
Leur fitness mesure la distance à vol d'oiseau jusqu'à la cible, si bien qu'une fusée qui fonce dans le mur sous la cible obtient un meilleur score qu'une fusée qui s'éloigne pour trouver le passage. La population s'entasse dans cette impasse, un optimum local. Des populations plus grandes, davantage de mutation ou la sélection par tournoi l'aident à s'en échapper, et une fitness qui mesurerait le vrai trajet autour des murs éviterait le piège. Choisir une bonne fonction de fitness est la partie la plus difficile de l'utilisation d'un algorithme génétique.
Est-ce ainsi que fonctionne l'évolution dans la nature ?
Dans les grandes lignes : la variation par mutation et recombinaison, l'hérédité des gènes et la sélection des plus aptes sont les ingrédients de Darwin. Les différences sont toutefois importantes. La nature n'a ni cible ni formule de fitness, seulement la survie et la reproduction, et les vrais génomes construisent des corps par le développement au lieu de dresser une liste d'actions.
À quoi servent les algorithmes génétiques ?
À des problèmes qui ont un immense espace de réponses possibles et un moyen simple d'évaluer un candidat : façonner des antennes, des ailes et des pièces automobiles, établir des emplois du temps, régler les paramètres d'autres algorithmes, concevoir des réseaux de neurones, et créer de l'art et des stratégies de jeu. L'antenne évoluée de la NASA sur les satellites ST5 de 2006 en est un exemple célèbre.
Pourquoi la meilleure fusée vole-t-elle parfois moins bien à la génération suivante ?
Sans élitisme, la meilleure fusée n'est pas copiée : ses gènes ne survivent que mélangés à d'autres et éventuellement mutés, si bien que la génération suivante peut perdre son vol exact. Avec l'élitisme activé, la meilleure fusée est conservée sans changement et le meilleur résultat ne se dégrade jamais.
Quelque chose est-il envoyé à un serveur ?
Non. Les fusées volent et évoluent dans votre navigateur, et les murs que vous dessinez restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur