Semaine 8 - Génétique
La programmation génétique est une méthode automatique inspirée par le mécanisme de la sélection naturelle tel qu'il a été établi par Charles Darwin pour expliquer l'adaptation plus ou moins optimale des organismes à leur milieu. Elle a pour but de trouver par approximations successives des programmes répondant au mieux à une tâche donnée.
[Cette technique permet] à un programme informatique d'apprendre, par un algorithme évolutionniste, à optimiser peu à peu une population d'autres programmes pour augmenter leur degré d'adaptation (fitness) à réaliser une tâche demandée par un utilisateur.
Le principe de la programmation génétique présenté pour représenter des programmes répondant au problème donné. Voici un algorithme synthétique pour la programmation génétique :
- Génération aléatoire de la population (1 individu = 1 programme)
- Évaluation du fitness de chacun des individus de la population
- Application des opérateurs de croisement, mutation, reproduction sur la population afin de créer une nouvelle population
- Sélection des individus les mieux adaptés à leur environnement
- Répéter les étapes 2, 3 et 4 un certain nombre de fois
À la génération de ce monde, chaque individu possède les gènes suivants générés aléatoirement :
- Position X
- Position Y
- Vélocité horizontale
- Vélocité verticale
- Teinte de rouge
- Teinte de vert
- Teinte de bleu
Les gènes de position X et Y servent à connaître la position de l'individu dans le monde. Les gènes de vélocité horizontale et verticale définissent le vecteur de direction de l'individu. Les gènes de teinte rouge, verte et bleue sont mis ensemble pour connaître la couleur finale de l'individu. De toute sa durée de vie, un individu ne peut changer ni ses gènes, ni son comportement.
Chaque individu est créé avec une certaine quantité d'énergie. Avec le temps, cette quantité descend jusqu'à la mort de l'individu. S'il passe du temps près d'une source de nourriture, l'individu regagne de l'énergie. Chaque individu a aussi une espérance de vie définie qui va aussi amener sa mort si ce laps de temps est dépassé.
Plusieurs fois par seconde, trois individus seront sélectionnés au hasard. Les deux dont la quantité d'énergie est la plus haute à ce moment seront croisés pour former un nouvel individu qui remplacera le troisième.
Ce nouvel individu se placera quelque part entre ses parents, prendra une direction semblable à la leur et aura une couleur leur ressemblant. Chacun de ses gènes (sauf ceux de sa couleur) auront aussi la chance (3% de chance) de subir une légère mutation (±15% de mutation).
Lorsqu'un individu meurt, par manque d'énergie ou à la fin de son espérance de vie, un nouveau individu aléatoire est intégré au monde.
Ainsi, la simulation créer une population qui évolue en adoptant des comportements capables de faire survivre ses membres en suivant les règles cités ci-dessus.