Les Algorithmes génétiques – une brève introduction

Avant de pouvoir utiliser un algorithme génétique pour résoudre un problème, il faut trouver un moyen pour encoder une solution potentielle à ce problème. Cela peut être une chaîne de nombres ou, comme c’est le cas la plupart du temps, une chaîne binaire. A partir de maintenant, je me référerais à cette chaîne de bits en tant que chromosome.

Un chromosome typique peut avoir la forme suivante :

10010101110101001010011101101110111111101

(Ne vous inquiétez pas, si rien à de sens pour le moment, cela va devenir clair bientôt. Pour l’instant, relaxez-vous et continuez la lecture)

Un algorithme génétique démarre avec la création d’une large population de chromosomes générés aléatoirement. Après décodage, chacun des chromosomes représentera une solution différente au problème. En partant du fait qu’il y a N chromosomes dans la population initiale.Les étapes suivantes seront alors répétées jusqu’à trouver une solution

Tester chaque chromosome pour son aptitude à résoudre le problème, en fonction lui assigner une valeur d'aptitude (fitness score)
Sélectionner deux membres de la population actuelle. La chance d'ête séléctionné est proportionnelle à l'aptitude de chacun des chromosomes. La séléction par la méthode Roulette Wheel (Si vous connaissez un meilleur terme, contactez-moi [NTDR]) est celle utilisée le plus courament. En fonction du taux de croisement (crossover rate), croiser les bits de chacun des chromosomes choisis à un endroit pris au hasard
En fonction du taux de mutation (mutation rate), inverser les bits des chromosomes choisis
Répéter les étapes 2,3 et 4 jusqu'à ce qu'une nouvelle population de N menbres a pu êttre crée.

Plus de détails sur la sélection Roulette Wheel

C’est une manière de choisir des membres d’une population de chromosomes de façon proportionnelle à leurs aptitudes. Ceci ne garanti pas que le membre le plus apte survivra à la prochaine génération, sachant qu’il à de grandes chances d’y parvenir. Cela se passe ainsi :Imaginez que l’aptitude de toute la population est représentée par un graphique en forme de camembert, ou roulette wheel. Vous définissez maintenant une tranche de ce graphique à chaque membre de la population. La taille de la tranche est proportionnelle au taux d’aptitude (fitness score) de chacun des chromosomes.C’est à dire: le membre le plus adapté à la tranche la plus grosse. Maintenant, pour choisir un chromosome, tout ce que vous devez faire est de faire tourner une boulle dessus (comme une roulette de casino [NTTDR] ) et prendre le chromosome sur lequel elle s’arrête .

Qu’est ce que le taux de croisement ( Crossover Rate)

C’est tout simplement la possibilité qu’on deux chromosomes d’inverser leurs bits. Une valeur acceptable est de 0.7.Le croisement est effectué en sélectionnant un gène au hasard dans un chromosome et d’inverser tous les gènes à partir de ce point.

Par exemple, étant donné deux chromosomes

10001001110010010

01010001001000011

Choisir un endroit aléatoirement, par exemple le 9e bit, et inverser chacun des bits après ce point, ce qui donne :

10001001101000011

01010001010010010

Qu’est ce que le Taux de Mutation (Mutation Rate)

C’est la possibilité qu’à un bit dans un chromosome d’être inversé (0 devient1 et 1 devient 0). En général une valeur très faible est utilisée pour les gènes binaires, disons 0.001.Ainsi lorsque des chromosomes sont sélectionnés dans une population, l’algorithme vérifie d’abord si le croisement devrait être appliqué et par conséquent boucle tout au long de chacun des chromosomes en mutant les bits si possible.

1 2 3 Home