Bandeau
S’informer et apprendre en ligne
OWL, LMS, iLES.

Les sites des iLES proposent des ressources en mathématiques et en sciences. Ils scrutent l’actualité statistique et culturelle. Ils utilisent des CDF et des widgets. Ils offrent de l’interaction entre apprenants.

Rechercher dans ces sites

CMS LMS
Apprendre en ligne (nouvelle version) iLES
Arts-Scènes
Optimisation
Trouver un extremum à l’aide d’un algorithme génétique
Algorithmes génétiques

Utilisation d’un algorithme génétique pour trouver le minimum d’une fonction Y définie à partir d’une somme de fonctions y=f(y). Chacune des composantes y=f(x) a son domaine de définition et la somme des valeurs des x pris dans ces domaines est soumise à une contrainte.

Article mis en ligne le 3 septembre 2006
dernière modification le 2 février 2009

par bernard.vuilleumier

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.