Tutoriel : Les algorithmes génétiques
Introduction
Les algorithmes génétiques sont des méthodes de résolution de problèmes basées sur la conception Darwinienne de la nature, et sur le dicton "La nature fait bien les choses" :) .Ainsi, par analogies aux êtres vivants qui ont évolués pendant des millénaires pour s'adapter aux conditions naturelles afin de survivre (les ours polaire ont une fourrure pour se protéger du froid, les poissons ont des bronchies pour pouvoir respirer sous l'eau...), un algorithme génétique (AG) propose de faire la même chose mais à une échelle différente.
Schéma général des AG
Tous les algorithmes génétiques suivent en fait un même schéma :A) Initialisaton
Génération aléatoire des individus
B) Corps du programme
1) Test de chacun des individus pour savoir lequel est le plus adapté. On appelle cela un test de fitting.
2) Choix des individus qui ont survécu par une méthode de sélection : élitiste, roulette russe (roulette wheel),tournoi...
3) Etablissement de la descendance aux moyens de crossing over et de mutations...
4) Recommencer l'étape B tant que les individus ne sont pas assez satisfaisant.
Construire son algorithme génétique
Avant de créer un algorithme génétique, il faut tout d'abord trois choses :-une population (ça peut être une suite de chiffre, la solution à un problème, un algorithme, un ensemble de règles, ou même un réseau de neurones... (on verra ça plus tard)). Chaque individu doit posséder des "gènes" facilement indentifiables, pour pouvoir faire des crossing over plus tard.
-Par conséquent il vous faut donc des gènes, c'est à dire une des multiples caractéristique de votre individu.
-un algorithme de fitting : c'est cet algorithme qui donne une note à chaque individu et ainsi décider de son sort.
Exemples :
1) Vous voulez trouver le maximum d'une fonction donnée
La population sera alors le nombre solution, écrit en binaire pour favoriser les crossing overs.
Les gènes seront alors chacun des bits qui composent le résultat.
La fonction de fitting renverra tout simplement un résultat proportionnel à votre nombre (l'individu), puisque vous cherchez un maximum
2) Vous voulez designer une voiture tout terrain
La population sera alors la voiture
Les gènes seront alors les dimensions, les angles, et les points d'attache des différentes formes géométriques qui composent votre véhicule
La fonction de fitting renverra alors la distance parcouru par votre véhicule avant de s'arrêter.
Exemple : le site Box2D
3) Vous voulez créer des créatures qui évoluent dans un but précis
La population sera alors la créature, doté d'un réseau de neurons (nous verrons cela plus tard)
Les gènes seront alors les différents poids de chaque neurone du réseau.
La fonction de fitting renverra alors la capacité d'adapatation de la créature, différente selon les cas.
Exemple : une expérience que j'ai réalisée