Série de tests

Algorithmes d'optimisation évolutionnaire

James McCaffrey

Télécharger l'exemple de code

Un algorithme d'optimisation évolutionnaire est une implémentation spécifique d'une métaheuristique, modélisée sur le comportement de l'évolution biologique. Ces algorithmes permettent de rechercher des solutions approximatives à des problèmes de minimisation numérique difficiles ou insolubles. Pourquoi devriez-vous vous intéresser aux algorithmes d'optimisation évolutionnaire ? D'abord, savoir coder ces algorithmes pourrait être une compétence utile à un développeur, un responsable ou un testeur. Ensuite, certaines des techniques utilisées, comme la sélection par tournoi, peuvent être réemployées dans d'autres algorithmes et scénarios de codage. Enfin, de nombreux ingénieurs trouvent ces algorithmes intéressants en eux-mêmes.

Un algorithme d'optimisation évolutionnaire est en essence un type d'algorithme génétique dans lequel les chromosomes virtuels sont composés de valeurs réelles au lieu d'une forme ou d'un autre de représentation de données. Pour voir où je veux en venir, jetez un coup d'œil aux figure 1 et figure 2.

Figure 1 Fonction de Schwefel

Figure 2 Démonstration d'optimisation évolutionnaire

Le graphique de la figure 1 illustre la fonction de Schwefel, un problème de minimisation numérique, utilisé comme banc d'essai standard. La fonction de Schwefel est définie ainsi :

f(x,y) = (-x * sin(sqrt(abs(x)))) + (-y * sin(sqrt(abs(y))))

La valeur minimale de la fonction est de -837,9658 où x = y = 420,9687. Dans la figure 1 cette valeur minimale est située dans le coin à l'extrême gauche du graphique. La fonction est délibérément conçue pour être difficile à résoudre par des algorithmes d'optimisation en raison des nombreuses valeurs minimales locales erronées.

La capture d'écran dans la figure 2 présente la sortie d'une application de console en C#. Après l'affichage de quelques messages d'information, le programme défini huit paramètres, puis utilise un algorithme évolutionnaire pour rechercher la solution optimale. Dans cet exemple, l'algorithme produit une meilleure solution de (420,9688 ; 420,9687), qui est extrêmement proche, mais pas égale, à la solution optimale de (420,9687 ; 420,9687).

Les algorithmes d'optimisation évolutionnaire copient des solutions comme le fait un chromosome dans un individu. Le pseudo-code général permettant d'implémenter l'algorithme présenté à la figure 2est :

initialize a population of random solutions
determine best solution in population
loop
  select two parents from population
  make two children from the parents
  place children into population
  make and place an immigrant into population
  check if a new best solution exists
end loop
return best solution found

Dans les sections suivantes, je vais vous présenter l'intégralité du code qui a permit d'obtenir la capture d'écran de la figure 2. Vous pouvez trouver ce code ici : archive.msdn.microsoft.com/mag201206TestRun. Pour cet article, nous partons du principe que vous disposez de connaissances de programmation intermédiaires ou avancées et que vous avez quelques notions de base sur les algorithmes génétiques. J'ai codé le programme de démonstration en C#, mais vous ne devriez avoir aucun mal à le refactoriser dans d'autres langages tels que Visual Basic .NET ou IronPython.

Structure du programme

La structure générale du programme est présentée dans la figure 3. J'ai utilisé Visual Studio 2010 pour créer un nouveau projet d'application de console en C#, appelé EvolutionaryOptimization. Dans la fenêtre de l'explorateur de solutions, j'ai renommé Program.cs en EvolutionaryOptimizationProgram.cs, ce qui a eu pour effet de renommer automatiquement la classe Program. J'ai également supprimé tous les éléments inutiles générés par des modèles à l'aide d'instructions.

Figure 3 Structure générale du programme EvolutionaryOptimization

using System;
namespace EvolutionaryOptimization
{
  class EvolutionaryOptimizationProgram
  {
    static void Main(string[] args)
    {
      try
      {
        int popSize = 100;
        int numGenes = 2;
        double minGene = -500.0; double maxGene = 500.0;
        double mutateRate = 1.0 / numGenes;
        double precision = 0.0001;
        double tau = 0.40;
        int maxGeneration = 8000;
        Evolver ev = new Evolver(popSize, numGenes, 
          minGene, maxGene, mutateRate,
          precision, tau, maxGeneration);
        double[] best = ev.Evolve();
        Console.WriteLine("\nBest solution found:");
        for (int i = 0; i < best.Length; ++i)
          Console.Write(best[i].ToString("F4") + " ");
        double fitness = Problem.Fitness(best);
        Console.WriteLine("\nFitness of best solution = " 
          + fitness.ToString("F4"));
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    }
  }
  public class Evolver
  {
    // Member fields
    public Evolver(int popSize, int numGenes, 
      double minGene, double maxGene,
      double mutateRate, double precision, 
      double tau, int maxGeneration) { ... }
    public double[] Evolve() { ... }
    private Individual[] Select(int n) { ... }
    private void ShuffleIndexes() { ... }
    private Individual[] Reproduce(Individual parent1, 
      Individual parent2) { ... }
    private void Accept(Individual child1, 
      Individual child2) { ... }
    private void Immigrate() { ... }
  }
  public class Individual : IComparable<Individual>
  {
    // Member fields
    public Individual(int numGenes, 
      double minGene, double maxGene,
      double mutateRate, double precision) { ... }
    public void Mutate() { ... }
    public int CompareTo(Individual other) { ... }
  }
  public class Problem
  {
    public static double Fitness(double[] chromosome) { ... }
  }
} // NS

En plus de la principale classe de programme, la démonstration EvolutionaryOptimization compte trois classes définies par programmation. La classe Evolver contient la majeure partie de la logique de l'algorithme. La classe Individual modélise une solution possible au problème de minimisation. La classe Problem détermine la fonction à minimiser, la fonction de Schwefel dans cet exemple. Une autre structure de conception possible serait de placer la classe Individual à l'intérieur de la classe Evolver.

Classe Individual

La définition de la classe Individual commence ainsi :

public class Individual : IComparable<Individual>
{
  public double[] chromosome;
  public double fitness;
  private int numGenes;
  private double minGene;
  private double maxGene;
  private double mutateRate;
  private double precision;
  static Random rnd = new Random(0);
...

La classe hérite de l'interface IComparable afin que les tableaux des objets Individual puissent être triés automatiquement en fonction de leur pertinence (fitness). La classe compte huit membres de données. Le tableau de chromosomes représente une solution possible au problème cible. Notez que le tableau de chromosomes est un tableau de type double, non pas un tableau comportant une forme ou une autre de représentation de données comme c'est souvent le cas dans les algorithmes génétiques. Les algorithmes d'optimisation évolutionnaire sont parfois appelés algorithmes génétiques à valeurs réelles.

Le champ Fitness (pertinence) constitue une évaluation de la qualité de la solution chromosomique. Pour les problèmes de minimisation, les valeurs de fitness (pertinence) faibles sont meilleurs que les valeurs élevées. Pour simplifier, chromosome et fitness sont déclarés avec une étendue publique pour qu'ils soient visibles par la logique dans la classe Evolver. Un gène correspond à une valeur dans le tableau de chromosomes et le champ numGenes contient le nombre de valeurs réelles dans une solution possible. Pour la fonction de Schwefel, cette valeur est définie sur 2. Avec de nombreux problèmes d'optimisation numérique, les valeurs minimales et maximales de chaque gène peuvent être spécifiées et stockées dans minGene et maxGene. Si ces valeurs ne sont pas connues, minGene et maxGene peuvent être définis comme double.MinValue et double.MaxValue. Je vous parlerai de mutateRate (taux de mutation) et des champs de précision lorsque j'aborderai le code qui les utilise.

La définition de la classe Individual continue avec le constructeur de classe :

public Individual(int numGenes, double minGene, double maxGene,
  double mutateRate, double precision)
{
  this.numGenes = numGenes;
  this.minGene = minGene;
  this.maxGene = maxGene;
  this.mutateRate = mutateRate;
  this.precision = precision;
  this.chromosome = new double[numGenes];
  for (int i = 0; i < this.chromosome.Length; ++i)
    this.chromosome[i] = (maxGene - minGene) 
    * rnd.NextDouble() + minGene;
  this.fitness = Problem.Fitness(chromosome);
}

Le constructeur alloue de la mémoire pour le tableau de chromosomes et attribue des valeurs aléatoires comprises dans la plage (minGene, maxGene) à chaque cellule de gène. Vous pouvez constater que la valeur du champ de fitness (pertinence) est déterminée en appelant la méthode Fitness (pertinence) définie en externe. Vous pourriez également transmettre au constructeur une référence vers la méthode Fitness (pertinence) par l'intermédiaire d'un délégué. La méthode Mutate (mutation) est définie ainsi :

public void Mutate()
{
  double hi = precision * maxGene;
  double lo = -hi;
  for (int i = 0; i < chromosome.Length; ++i) {
    if (rnd.NextDouble() < mutateRate)
      chromosome[i] += (hi - lo) * rnd.NextDouble() + lo;
  }
}

L'opération de mutation traverse le tableau de chromosomes, en modifiant des gènes sélectionnés aléatoirement et leur attribue des valeurs aléatoires comprises dans la plage (minimum, maximum). La plage de valeurs à attribuer est déterminée par les valeurs de membre précision et maxGene. Dans l'exemple de la figure 2, la précision est définie sur 0,0001 et maxGene sur 500. La valeur de mutation de gène la plus élevée possible est de 0,0001 * 500 = 0,05. Cela signifie que si le gène mute, sa nouvelle valeur sera égale à l'ancienne valeur plus ou moins une valeur aléatoire comprise entre -0,05 et +0,05. Notez que la valeur de précision correspond au nombre de chiffres après la virgule dans la solution. Cela constitue une bonne heuristique à utiliser pour la valeur de précision. La valeur du taux de mutation contrôle le nombre de gènes du chromosome qui pourront être modifiés. Une heuristique possible pour le champ mutateRate est d'utiliser 1,0/numGenes afin qu'en moyenne un gène du chromosome subisse une mutation chaque fois que la méthode Mutate (mutation) est appelée.

La définition de la classe Individual se termine avec la méthode CompareTo (comparaison) :

...
  public int CompareTo(Individual other)
  {
    if (this.fitness < other.fitness) return -1;
    else if (this.fitness > other.fitness) return 1;
    else return 0;
  }
}

La méthode CompareTo (comparaison) définit un ordre de tri par défaut pour les objets Individual. Ici l'ordre de tri est de la plus petite pertinence (du meilleur) à la plus grande pertinence.

Classe Problem

La classe Problem incorpore le problème cible destiné à l'algorithme évolutionnaire :

public class Problem
{
  public static double Fitness(double[] chromosome)
  {
    double result = 0.0;
    for (int i = 0; i < chromosome.Length; ++i)
      result += (-1.0 * chromosome[i]) *
        Math.Sin(Math.Sqrt(Math.Abs(chromosome[i])));
    return result;
  }
}

Comme le tableau de chromosomes représente une solution possible, il est transmis en tant que paramètre d'entrée à la méthode Fitness (pertinence). Avec les problèmes de minimisation arbitraire, la fonction cible à minimiser est habituellement appelée fonction de coût. Dans le contexte d'algorithmes évolutionnaires et génétiques, cependant, cette fonction est habituellement appelée fonction de pertinence (fitness). Cette terminologie est un peu ambiguë, car les valeurs faibles de pertinence correspondent à de meilleurs résultats que les valeurs élevées. Dans notre exemple, la fonction de pertinence fonctionne en autarcie. Souvent dans les problèmes d'optimisation, la fonction de pertinence nécessite des paramètres d'entrée supplémentaires, tels qu'une matrice des données ou une référence à un fichier de données externe.

Classe Evolver

La définition de la classe Evolver commence ainsi :

public class Evolver
{
  private int popSize;
  private Individual[] population;
  private int numGenes;
  private double minGene;
  private double maxGene;
  private double mutateRate;
  private double precision;
  private double tau;
  private int[] indexes;
  private int maxGeneration;
  private static Random rnd = null;
...

Le membre popSize (taille de la population) contient le nombre d'individus de la population. Plus la valeur de popSize est élevée, plus l'algorithme a de chances de donner des résultats exacts, mais cela réduit en revanche la vitesse. En général, les algorithmes évolutionnaires sont beaucoup plus rapides que les algorithmes génétiques ordinaires, car ils fonctionnent à partir de valeurs réelles et ne sont donc pas ralentis par la charge que représente la conversion et la manipulation des représentations de données. Le cœur de la classe Evolver est un tableau d'objets Individual appelé population. Le tau et les membres d'index sont utilisés par la méthode de sélection, comme vous le verrez bientôt.

La définition de la classe Evolver continue avec la définition du constructeur présentée dans la figure 4.

Figure 4 Constructeur de la classe Evolver

public Evolver(int popSize, int numGenes, double minGene, double maxGene,
  double mutateRate, double precision, double tau, int maxGeneration)
{
  this.popSize = popSize;
  this.population = new Individual[popSize];
  for (int i = 0; i < population.Length; ++i)
    population[i] = new Individual(numGenes, minGene, maxGene,
      mutateRate, precision);
  this.numGenes = numGenes;
  this.minGene = minGene;
  this.maxGene = maxGene;
  this.mutateRate = mutateRate;
  this.precision = precision;
  this.tau = tau;
  this.indexes = new int[popSize];
  for (int i = 0; i < indexes.Length; ++i)
    this.indexes[i] = i;
  this.maxGeneration = maxGeneration;
  rnd = new Random(0);
}

Le constructeur alloue de la mémoire pour l'ensemble Population et utilise ensuite le constructeur Individual pour remplir l'ensemble de tableau avec des individus ayant des valeurs génétiques aléatoires. Le tableau intitulé indexes est utilisé par la méthode Select (sélection), qui sélectionne deux parents. Je reviendrai plus tard sur les index, mais veuillez noter que le constructeur alloue une cellule par individu et attribue, de façon séquentielle, des entiers de 0 à popSize-1.

La méthode Evolve (évolution), répertoriée dans la figure 5, est étonnement courte.

Figure 5 Méthode Evolve

public double[] Evolve()
{
  double bestFitness = this.population[0].fitness;
  double[] bestChomosome = new double[numGenes];
  population[0].chromosome.CopyTo(bestChomosome, 0);
  int gen = 0;
  while (gen < maxGeneration)  {
    Individual[] parents = Select(2);
    Individual[] children = Reproduce(parents[0], parents[1]);
    Accept(children[0], children[1]);
    Immigrate();
    for (int i = popSize - 3; i < popSize; ++i)  {
      if (population[i].fitness < bestFitness)  {
        bestFitness = population[i].fitness;
        population[i].chromosome.CopyTo(bestChomosome, 0);
      }
    }
    ++gen;
  }
  return bestChomosome;
}

La méthode Evolve (évolution) retourne la meilleure solution trouvée dans un tableau de type double. L'autre possibilité est de retourner un objet Individual dans lequel le chromosome contient la meilleure solution trouvée La méthode Evolve (évolution) commence par initialiser la meilleure pertinence (fitness) et les meilleurs chromosomes par rapport aux premiers de la population. La méthode effectue exactement autant d'itérations que le nombre de maxGenerations, utilisant gen (génération) comme compteur de boucles. Il ya a plusieurs possibilités. L'une d'elles est d'arrêter lorsqu'il n'y a pas eu d'amélioration depuis un certain nombre d'itérations. La méthode Select (sélection) retourne deux bons individus, mais pas forcément les meilleurs, de la population. Ces deux parents sont transmis à la méthode Reproduce (reproduction), qui crée et retourne deux enfants. La méthode Accept (acceptation) place les deux enfants dans la population, en remplacement de deux individus existants. La méthode Immigrate (immigration) génère un nouvel individu aléatoire et le place dans la population. La nouvelle population est ensuite analysée pour voir si un des trois nouveaux individus de la population constitue une nouvelle meilleure solution.

La méthode Select (sélection) est définie comme :

private Individual[] Select(int n)
{
  int tournSize = (int)(tau * popSize);
  if (tournSize < n) tournSize = n;
  Individual[] candidates = new Individual[tournSize];
  ShuffleIndexes();
  for (int i = 0; i < tournSize; ++i)
    candidates[i] = population[indexes[i]];
  Array.Sort(candidates);
  Individual[] results = new Individual[n];
  for (int i = 0; i < n; ++i)
    results[i] = candidates[i];
  return results;
}

La méthode accepte le nombre de bons individus à sélectionner et les retourne dans un tableau de type Individual. Pour limiter le volume de code, j'ai omis le contrôle d'erreurs habituel, par exemple la vérification que le nombre d'individus requis est inférieur à la taille de la population totale. La méthode Select (sélection) utilise une technique appelée sélection par tournoi. Un sous-ensemble aléatoire d'individus candidats est généré et les meilleurs n sont retournés. Le nombre de candidats est calculé et inséré dans la variable tournSize, qui correspond à une certaine fraction, tau, du total de la population. Des valeurs plus élevées de tau augmentent la probabilité que les deux meilleurs individus soient sélectionnés.

Souvenez-vous que la classe Evolver contient un tableau de membres intitulé indexes comprenant des valeurs de 0..popSize-1. La méthode d'assistance ShuffleIndexes (mélange d'index) réorganise les valeurs des index de tableau dans un ordre aléatoire. Les n premiers de ces index aléatoires sont utilisés pour choisir des candidats dans la population. La méthode Array.Sort (tri du tableau) trie ensuite les individus candidats de la plus petite pertinence (meilleur) à la plus grande. Les n premiers individus parmi les candidats triés sont retournés. Il existe de nombreux algorithmes de sélection évolutionnaire différents. Un des avantages de la sélection par tournoi par rapport à la plupart des autres techniques est que la pression de la sélection peut être ajustée en modifiant le paramètre tau.

La méthode d'assistance ShuffleIndexes utilise l'algorithme de mélange Fisher-Yates standard :

private void ShuffleIndexes()
{
  for (int i = 0; i < this.indexes.Length; ++i) {
    int r = rnd.Next(i, indexes.Length);
    int tmp = indexes[r];
    indexes[r] = indexes[i];
    indexes[i] = tmp;
  }
}

La méthode Reproduce (reproduction) est présentée dans la figure 6. Elle commence par générer un point de croisement aléatoire. L'indexation est un peu complexe, mais l'enfant child1 est créé à partir de la partie gauche du parent1 et la partie droite du parent2. L'enfant child2 est créé à partir de la partie gauche du parent2 et la partie droite du parent1. Le concept est illustré dans la figure 7, où sont présentés deux parents avec cinq gènes et un point de croisement de 2. Une autre possibilité de conception fréquemment utilisée est d'avoir recours à plusieurs points de croisement. Après leur création, les objets enfants Individual sont mutés et leur nouvelle pertinence est calculée.

Figure 6 Méthode Reproduce

private Individual[] Reproduce(Individual parent1, Individual parent2)
{
  int cross = rnd.Next(0, numGenes - 1);
  Individual child1 = new Individual(numGenes, minGene, maxGene,
    mutateRate, precision);
  Individual child2 = new Individual(numGenes, minGene, maxGene,
     mutateRate, precision);
  for (int i = 0; i <= cross; ++i)
    child1.chromosome[i] = parent1.chromosome[i];
  for (int i = cross + 1; i < numGenes; ++i)
    child2.chromosome[i] = parent1.chromosome[i];
  for (int i = 0; i <= cross; ++i)
    child2.chromosome[i] = parent2.chromosome[i];
  for (int i = cross + 1; i < numGenes; ++i)
    child1.chromosome[i] = parent2.chromosome[i];
  child1.Mutate(); child2.Mutate();
  child1.fitness = Problem.Fitness(child1.chromosome);
  child2.fitness = Problem.Fitness(child2.chromosome);
  Individual[] result = new Individual[2];
  result[0] = child1; result[1] = child2;
  return result;
}

Figure 7 Mécanisme de croisement

La méthode Accept (acceptation) place les deux individus enfants créés par la méthode Reproduce (reproduction) dans la population :

private void Accept(Individual child1, Individual child2)
{
  Array.Sort(this.population);
  population[popSize - 1] = child1;
  population[popSize - 2] = child2;
}

Le tableau de population est trié par pertinence, ce qui place les deux individus les moins bons dans les deux dernières cellules du tableau où ils sont ensuite remplacés par les enfants. Il existe plusieurs autres approches possibles afin de choisir les deux individus à éliminer. Une des possibilités est d'utiliser la technique de sélection à la roulette pour sélectionner par probabilité les deux individus à remplacer. Les individus les moins bons ont une plus forte probabilité d'être éliminés.

La méthode Immigrate (immigration) génère un nouvel individu aléatoire et le place dans la population juste au-dessus de l'emplacement des deux enfants qui viennent d'être générés (l'immigration aide à éviter les blocages de l'algorithme évolutionnaire dans des solutions de minimum local ; des variantes de conception consistent à créer plusieurs immigrants et les placer à des emplacements aléatoires de la population) :

private void Immigrate()
{
  Individual immigrant =
    new Individual(numGenes, minGene, maxGene, mutateRate, precision);
  population[popSize - 3] = immigrant;
}

Point de départ pour l'expérimentation

Dans cet article, l'optimisation évolutionnaire est utilisée pour évaluer la valeur minimale d'une équation mathématique. Bien que les algorithmes d'optimisation évolutionnaire puissent être utilisés dans ce cadre, ils sont le plus souvent utilisés pour trouver des valeurs pour un ensemble de paramètres numériques à l'échelle d'un problème d'optimisation plus vaste pour lequel il n'existe pas d'algorithme déterministe efficace. Par exemple, lorsque vous utilisez un réseau neuronal pour classifier les données existantes afin d'établir des prédictions quant aux données futures, le plus grand défi est de définir un ensemble de poids et de biais de neurone. L'algorithme d'optimisation évolutionnaire est une des approches permettant d'évaluer les valeurs optimales de poids et de biais. Dans la plupart des cas, les algorithmes d'optimisation évolutionnaire sont mal adaptés aux problèmes d'optimisation de combinaisons non-numériques, tels que le problème du voyageur de commerce, pour lequel il s'agit d'identifier la combinaison de villes représentant le trajet le plus court.

Les algorithmes évolutionnaires, comme les algorithmes de génétique pure, sont des métaheuristiques. Cela signifie qu'ils constituent un environnement global et un ensemble de consignes conceptuelles pouvant être utilisés pour créer un algorithme spécifique en réponse à un problème spécifique. Donc l'exemple présenté dans cet article peut être considéré comme un point de départ pour l'expérimentation et la création de code d'optimisation évolutionnaire plutôt que comme une base de code figée et immuable.

Le Dr. James McCaffrey travaille pour Volt Information Sciences Inc., où il gère la formation technique d'ingénieurs logiciels travaillant sur le Campus Microsoft à Redmond (État de Washington). Il a collaboré à plusieurs produits Microsoft, comme Internet Explorer et MSN Search. Il est l’auteur de « NET Test Automation Recipes » (Apress, 2006). Vous pouvez le contacter à l’adresse jammc@microsoft.com.

Merci à l'experte technique Microsoft suivante d'avoir relu cet article : Anne Loomis Thompson