Trouver un extremum à l’aide d’un algorithme génétique

Algorithmes génétiques
dimanche 3 septembre 2006
par  Bernard Vuilleumier
popularité : 2%

Dans un algorithme génétique, les chromosomes sont typiquement représentés par une chaîne de variables. Chaque variable peut prendre différentes valeurs qui sont le pendant des allèles. Un tel algorithme s’inspire de la génétique et de la théorie de l’évolution et en utilise le vocabulaire.

Étapes de la démarche d’optimisation

  1. Commencer avec une population d’individus générés aléatoirement
  2. Déterminer l’adaptation de chaque individu dans la population
  3. Sélectionner l’individu le mieux adapté
  4. Utiliser cet individu pour produire la nouvelle génération
  5. Faire évoluer la population en répétant les étapes 2 à 4.

Liste des composantes de la fonction à minimiser :

Contraintes imposées sur les composantes de la fonction :

Représentation des composantes de la fonction :

Composantes de la fonction à minimiser

Composantes de la fonction à minimiser

Écriture de l’algorithme génétique

- 1. Composer un « chromosome »

Les valeurs xi prises par chaque composante peuvent être considérées comme les « allèles » ou valeurs des « gènes » d’un « chromosome ». Tirons au hasard ces valeurs dans les domaines de définition des composantes de la fonction :

- 2. Déterminer l’« adaptation » du « chromosome »

Calculons l’écart (en valeur absolue) entre la somme des composantes et le « but » :

Ainsi que la valeur de la fonction en utilisant les valeurs xi obtenues :

Le « chromosome » le mieux adapté sera celui qui minimise une certaine « distance ». Nous utilisons ici l’écart au but comme distance pour mesurer l’« adaptation ».

- 3. Sélectionner dans une population un « chromosome » bien adapté

Générons une population de n « chromosomes » et trions-la par ordre décroissant des distances :

Sélectionnons maintenant un « chromosome » parmi les mieux adaptés (jusqu’à une profondeur « prof ») :

- 4. Générer une population à partir d’un « chromosome »

Pour générer une nouvelle population à partir du chromosome retenu, nous utiliserons la fonction « boole » qui donne « vrai » lorsque la probabilité p de muter est supérieure ou égale à un nombre tiré au hasard :

La fonction « muter » nous permettra ainsi de modifier, avec une probabilité p, la valeur d’un gène g. En cas de mutation, la nouvelle valeur du gène est une de celles du chromosome retenu :

Rassemblons les instructions permettant d’obtenir :

  • la liste des valeurs initiales
  • l’écart au but (pour les valeurs initiales)
  • la valeur de la fonction (pour les valeurs initiales)
  • la nouvelle génération
  • les valeurs de l’individu le mieux adapté de cette génération

- 5. Faire évoluer la population

Pour faire évoluer la population, nous retenons les valeurs de l’individu le mieux adapté et nous recommençons le cycle (étapes 2 à 4).

Pour en savoir plus
- James. A. Freeman, Simulating Neural Network with Mathematica, Assison-Wesley, 1994. Ce livre qui traîte d’un autre sujet comporte un chapitre dévolu aux algorithmes génétiques car ces derniers peuvent être utilisés pour l’« entraînement » des réseaux neuronaux (processus d’apprentissage).
- Quelques solutions approchées pour la fonction et la contrainte utilisées dans cet exemple.


Documents joints

Notebook Mathematica

Commentaires  forum ferme