Algorithmes génétiques
Les algorithmes génétiques sont des algorithmes stochastiques itératifs qui opèrent sur des individus à partir d’une population initiale.
Dans les algorithmes génétiques, la population évolue de la génération k à la génération k+1 à l’aide de trois opérateurs :
- un opérateur de Sélection
- un opérateur de Croisement
- un opérateur de Mutation.
Le processus provient de l’évolution génétique. On part avec une population de solutions potentielles initiales arbitrairement choisies. On évalue leur performance relative (fitness). Sur la base de ces performances, on crée une nouvelle population de solutions potentielles en utilisant les opérateurs. On recommence ce cycle jusqu’à avec une solution satisfaisante.
Programmation génétique et algorithmes génétiques
- Population de base générée aléatoirement : n vecteurs de solution (individus)
- Évaluation de chaque individu, cette évaluation retourne une valeur quantitative (fitness)
- Sélection par tirage au sort d’un sous-ensemble d’individus par une roue biaisée, par rang, par tournoi ou par eugénisme. Chaque individu a une probabilité d’être choisi proportionnelle à son évaluation (ou adaptation au problème).
- Croisements et Mutations des individus sélectionnés.
Les croisements et mutations des algorithmes génétiques ne donnent pas forcément des solutions admissibles au problème. Ils opèrent par altération, copie, remplacement, etc, du vecteur de solution d’un ou plusieurs individus pour en former un nouveau.
Exemple
Nous cherchons le maximum de f(x)=4x*(1-x) sur l’intervalle [0,1]. Nous prenons une population initiale de 4 éléments codés sur 8 bits (qui seront convertis en une valeur entre 0 et 1). Les nouvelles générations comporteront toujours 4 individus. Le tableau de valeur de la génération initiale est le suivant :
Élément | f(x) | % / total | cumul |
10111010 | 0.794678 | 0.79/2.59=0.31 | 0.31 |
11011110 | 0.460693 | 0.18 | 0.49 |
00011010 | 0.364990 | 0.14 | 0.63 |
01101100 | 0.9775586 | 0.37 | 1.00 |
– | 2.595947 | – | – |
Élément représente les individus, f(x) la valeur de la fonction objectif, % / total est le pourcentage de la valeur de la fonction objectif d’un élément par rapport à la somme des valeurs de la fonction objectif, cumul est la somme des pourcentages. Nous avons donc au final l’importance de chaque individu compte tenu de la valeur de la fonction objectif.
Maintenant que l’évaluation est faite, nous devons sélectionner des individus pour le croisement. Puisque nous avons une échelle d’importance de chaque individu, nous pouvons tirer au sort des individus. En effet, plus la valeur objectif d’un individu est grande, plus il a de chance d’être tiré au sort. On tire quatre nombres aléatoires entre 0 et 1 : 0.34, 0.02, 0.64 et 0.77. Nous avons donc sélectionné ces individus : 11011110, 10111010, 01101100, 01101100.
Nous avons sélectionné les parents, il faut désormais effectuer le croisement. Pour cela, nous choisissons un marqueur aléatoire dans la chaine de bit, et nous permutons la partie droite de la chaîne :
La population de la prochaine génération est composée des quatre enfants ainsi créés. En général, nous éviterons d’effectuer un croisement entre deux individus identiques.
