Cet article a fait l'objet d'une traduction automatique.

Série de tests

Luciole algorithme optimisation

James McCaffrey

Téléchargez l'exemple de Code(VB)

En apprentissage machine, un algorithme d'optimisation numérique est souvent utilisé pour trouver un ensemble de valeurs pour les variables, généralement appelé poids — que minimiser une certaine erreur. Par exemple, classification de la régression logistique utilise une équation mathématique où, s'il y a des variables prédictives n, il existe n + 1 poids valeurs qui doivent être déterminées. Le processus consistant à déterminer les valeurs des poids s'appelle le modèle de formation. L'idée est d'utiliser une collection de données d'apprentissage qui connaît les valeurs de sortie correct. Un algorithme d'optimisation est utilisé pour rechercher les valeurs des poids qui réduisent au minimum l'erreur, qui est la différence entre les valeurs de sortie calculées et les valeurs de sortie correcte.

Il existe de nombreux algorithmes d'optimisation différents. Cet article explique une relativement nouvelle (première publication en 2009) technique appelée optimisation algorithme (FA) de firefly. Optimisation de FA vaguement modélise le comportement d'une nuée de lucioles.

Un bon moyen pour avoir une idée de ce que FA l'optimisation est et de voir où va cet article doit avoir un regard sur le programme de démonstration en Figure 1. Le programme de démonstration vise à utiliser l'optimisation de la FA pour trouver la valeur minimale de la fonction Muika avec cinq variables d'entrée. La fonction Muika est une norme standard utilisé pour évaluer l'efficacité des algorithmes d'optimisation numérique. Avec cinq valeurs d'entrée, la fonction a une valeur minimale de z =-4.6877 situé à x = (1.2850, 1.9231, 2.2029 1.5707, 1.7205).

Figure 1 l'optimisation d'algorithme Firefly en Action

La fonction Muika est difficile pour la plupart des algorithmes optimisation car il possède plusieurs valeurs minimales locales et plusieurs zones plates (où toutes les valeurs de z sont presque égaux). Il n'est pas possible de visualiser facilement la fonction Muika avec cinq valeurs d'entrée, mais vous pouvez avoir une idée des caractéristiques de la fonction de l'examen­ining un graphe de la fonction pour deux valeurs d'entrée, montré dans Figure 2. Sa définition en termes mathématiques est affichée au bas de la figure.

Figure 2 la fonction de Muika de deux Variables

Le programme de démonstration définit le nombre des lucioles à 40. Chaque luciole a une position virtuelle qui représente une solution possible au problème de minimisation. Lucioles plus augmentent les chances de trouver la vraie solution optimale au détriment de la performance. Optimisation de FA utilise généralement de 15 à 40 lucioles.

La démo définit la dimension du problème à 5 car il y a cinq valeurs d'entrée. FA est un processus itératif et requiert une valeur de compteur de boucle maximale. Une variable de compteur de boucle dans l'optimisation d'apprentissage machine est souvent nommée époque et les ensembles de démo, le maximum de valeur à 1 000 itérations. Le nombre maximal d'itérations variera d'un problème à un problème, mais 1 000 est une valeur raisonnable. FA a un élément de hasard et la démo définit la valeur de départ pour le générateur de nombres aléatoires à une valeur arbitraire de 0.

Dans la démo en Figure 1, l'erreur (plus petit) meilleur associé à la meilleure position trouvée jusqu'à présent a été affichée chaque 100 époques. Une fois terminée l'algorithme, la meilleure position trouvée pour n'importe quel firefly a été x = (2.2033, 1.5711, 1.2793, 1.1134, 2.2216). Cette solution est proche, mais pas tout à fait égal à, la solution optimale de x = (1.2850, 1.9231, 2.2029 1.5707, 1.7205). La valeur de la fonction Muika à la solution trouvée par FA était-4.45, qui se trouve à proximité de la vraie valeur minimale de-4.69. L'erreur de la solution de FA est 0,0561.

Cet article suppose que vous avez au moins intermédiaire de compétences en programmation, mais n'assume pas que vous savez quelque chose sur l'optimisation numérique ou l'algorithme de firefly. Le programme de démonstration est codé à l'aide de c#, mais vous ne devriez pas avoir trop de difficultés la refactorisation du code dans une autre langue, tels que JavaScript ou Python.

Le code de démonstration complète, avec quelques modifications mineures pour économiser l'espace, est présenté dans cet article. La démo est également disponible dans le téléchargement de code qui accompagne cet article. Le code de démo a enlevé à limiter les principales idées aussi claire que possible et la taille du code de vérification des erreurs normales tous les.

Structure globale du programme

La structure globale du programme est présentée en Figure 3. Pour créer la démo, j'ai lancé Visual Studio et créé une nouvelle application de console c# nommée FireflyAlgorithm. La démo n'a aucune dépendance significative de Microsoft .NET Framework, donc toute version récente de Visual Studio fonctionnera.

Structure du programme figure 3 Firefly Demo

using System;
namespace FireflyAlgorithm
{
  class FireflyProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin firefly demo");
      // Code here
      Console.WriteLine("End firefly demo");
      Console.ReadLine();
    }
    static void ShowVector(double[] v, int dec, bool nl)
    {
      for (int i = 0; i < v.Length; ++i)
        Console.Write(v[i].ToString("F" + dec) + " ");
      if (nl == true)
        Console.WriteLine("");
    }
    static double[] Solve(int numFireflies, int dim,
      int seed, int maxEpochs) { . . }
    static double Distance(double[] posA,
      double[] posB) { . . }
    static double Michalewicz(double[] xValues) { . . }
    static double Error(double[] xValues) { . . }
  } // Program
  public class Firefly : IComparable<Firefly>
  {
    // Defined here
  }
}

Après que le code du modèle chargé dans l'éditeur de Visual Studio , dans Explorateur de solutions, fenêtre j'ai renommé le fichier Program.cs pour les FireflyProgram.cs et les Visual Studio plus descriptif automatiquement renommé classe programme pour moi. En haut du code source, j'ai supprimé tous les inutiles à l'aide de déclarations, laissant juste la référence au système.

J'ai codé la démo en utilisant une technique principalement statique-méthode au lieu d'utiliser une approche de programmation orienté-objet complet. La démo a toute la logique du contrôle dans la Main. La méthode Main commence en affichant l'objectif de la démo :

Console.WriteLine("Goal is to solve the Michalewicz benchmark function");
Console.WriteLine("The function has a known minimum value of -4.687658");
Console.WriteLine("x = 2.2029 1.5707 1.2850 1.9231 1.7205");

Ensuite, les paramètres nécessaires de FA sont définies :

int numFireflies = 40;
int dim = 5;
int maxEpochs = 1000;
int seed = 0;

Les valeurs des paramètres sont affichés avec ces déclarations :

Console.WriteLine("Setting numFireflies = " + numFireflies);
Console.WriteLine("Setting problem dim = " + dim);
Console.WriteLine("Setting maxEpochs = " + maxEpochs);
Console.WriteLine("Setting initialization seed = " + seed);

L'algorithme de firefly est appelé comme ceci :

Console.WriteLine("Starting firefly algorithm");
double[] bestPosition = Solve(numFireflies, dim, seed, maxEpochs);
Console.WriteLine("Finished");

La méthode Main se termine en affichant les résultats de FA :

Console.WriteLine("Best solution found: ");
Console.Write("x = ");
ShowVector(bestPosition, 4, true);
double z = Michalewicz(bestPosition);
Console.Write("Value of function at best position = ");
Console.WriteLine(z.ToString("F6"));
double error = Error(bestPosition);
Console.Write("Error at best position = ");
Console.WriteLine(error.ToString("F4"));

L'algorithme de firefly est vraiment plus d'un méta heuristiques qu'un algorithme normatif. J'entends par là que FA est un ensemble de directives de conception pouvant être adaptée pour différents types de problèmes d'optimisation.

Compréhension de l'algorithme de Firefly

L'algorithme de firefly présenté dans cet article est basé sur le cahier de 2009 recherche « Firefly algorithmes pour Multimodal Optimization » par Yang Xin-She. Le processus d'algorithme de firefly est illustré dans le graphique en Figure 4. Le graphique représente un problème de minimisation de factice simplifiée dans laquelle il y a seulement deux valeurs d'entrée, X et Y, et la valeur minimale globale est à X = 0 et Y = 0. Il y a trois lucioles. Luciole [0] est à (2, 1) et est donc le plus proche de la solution correcte. Luciole [1] est à (-4, -4). Luciole [2] est à (-8, 8) et est le plus éloigné de la solution.

Figure 4 l'algorithme Firefly

Véritables lucioles sont insectes volants cette lueur à l'aide de la bioluminescence, probablement pour attirer des compagnons. Chaque luciole peut briller avec une intensité différente. En FA, les lucioles qui sont mieux, ce qui signifie une erreur plus petite, ont une plus forte intensité. Dans Figure 4, puis, Luciole [0] possède la plus haute intensité, Luciole [1] a intensité moyenne et Luciole [2] a faible intensité.

L'idée fondamentale de la FA est qu'une luciole seront attirés par tout autre luciole qui a une intensité plus élevée, et que l'attractivité (la distance déplacé vers une luciole plus intense) est plus forte si la distance entre les deux lucioles est plus petite. Donc, en Figure 4, firefly [0] est la plus haute intensité et ne bougera pas. Luciole [1] et firefly [2] seront tous les deux attirés par et de progresser vers la luciole [0]. Luciole [1] étant moins de Luciole [2] de la luciole [0], Luciole [1] se déplace plus loin qu'une luciole [2].

Exprimé en pseudo-code de très haut niveau, l'algorithme de firefly est présentée dans Figure 5. À première vue, l'algorithme semble très simple ; Toutefois, il est assez subtile, comme vous le verrez lorsque l'implémentation du code est présentée.

La première grande question est de définir l'intensité d'une luciole. Parce que la FA est un méta heuristiques, vous êtes libre de définir l'intensité comme bon vous semble, tant qu'une intensité plus élevée est associée à une meilleure solution/position. Le prochain enjeu majeur est de définir l'attraction afin que les lucioles plus étroites seront déplace vers une cible plus intense plus lointaine lucioles seront déplacera.

Figure 5 Firefly Algorithm

initialize n fireflies to random positions
loop maxEpochs times
  for i := 0 to n-1
    for j := 0 to n-1
      if intensity(i) < intensity(j)
        compute attractiveness
        move firefly(i) toward firefly(j)
        update firefly(i) intensity
      end for
    end for
  sort fireflies
end loop
return best position found

Mise en œuvre de l'algorithme de Firefly

La définition de méthode Solve commence comme :

static double[] Solve(int numFireflies, int dim, int seed, int maxEpochs)
{
  Random rnd = new Random(seed);
  double minX = 0.0;
  double maxX = 3.2;
  double B0 = 1.0;
  double g = 1.0;
  double a = 0.20;
  int displayInterval = maxEpochs / 10;
...

MaxX et minX variables locales fixent des limites pour la position de chaque firefly. Les valeurs utilisées ici, 0,0 et 3.2 (environ Pi) sont spécifiques à la fonction Muika. Pour machine optimisation avec données normalisées d'apprentissage, les valeurs de-10, 0 et + 10,0 sont communs.

Variables locales B0 (base bêta), g (gamma) et a (alpha) contrôlent l'attractivité d'une luciole à l'autre. Les valeurs utilisées (1.0, 1.0 et 0,20) ont été recommandées par le rapport de recherche de source. DisplayInterval de variable locale contrôle la fréquence d'affichage d'un message de progression.

Ensuite, un essaim de vide des lucioles est créé :

double bestError = double.MaxValue;
double[] bestPosition = new double[dim]; // Best ever
Firefly[] swarm = new Firefly[numFireflies]; // All null

Un objet de Firefly est défini par le programme et encapsule une position, une erreur associée et l'intensité correspondante. Au départ, tous les lucioles sont des objets null. La définition de classe de Firefly sera présentée dans la section suivante de cet article. Ensuite, l'essaim est instancié et placé au hasard des positions. Pour chaque luciole, le constructeur de Firefly est appelé :

for (int i = 0; i < numFireflies; ++i)
{
  swarm[i] = new Firefly(dim);
  for (int k = 0; k < dim; ++k) // Random position
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
...

Le constructeur affecte implicitement la position de (0.0, 0.0, 0.0, 0.0, 0.0) et l'erreur associés et l'intensité des valeurs factices de 0,0. Chaque composant du tableau position est définie avec une valeur aléatoire entre minX et maxX (0.0 et 3.2). Ensuite, l'erreur et l'intensité de la luciole actuelle sont calculées :

swarm[i].error = Error(swarm[i].position);
  swarm[i].intensity = 1 / (swarm[i].error + 1);
...

La fonction d'erreur est présentée prochainement. Ici, l'intensité de la luciole est définie pour être l'inverse de l'erreur afin que les valeurs de petite erreur aura de forte intensité et valeurs grande erreur aura de faible intensité. Le 1 au dénominateur empêche la division par zéro lorsque l'erreur est égale à zéro. Initialisation conclut en vérifiant la luciole nouvellement créée pour voir si il a la meilleure position trouvée :

...
  if (swarm[i].error < bestError)
  {
    bestError = swarm[i].error;
    for (int k = 0; k < dim; ++k)
      bestPosition[k] = swarm[i].position[k];
  }
} // For each firefly

La boucle de traitement principale commence par ces déclarations :

int epoch = 0;
while (epoch < maxEpochs)
{
  if (epoch % displayInterval == 0 && epoch < maxEpochs)
  {
    string sEpoch = epoch.ToString().PadLeft(6);
    Console.Write("epoch = " + sEpoch);
    Console.WriteLine(" error = " + bestError.ToString("F14"));
  }
...

Une alternative à un nombre fixe d'itérations est de rompre lorsque la valeur de bestError est inférieure à une valeur seuil petit (0,00001 est commun). Chaque luciole est comparée avec tous les autres lucioles utilisant imbriqués pour les boucles :

for (int i = 0; i < numFireflies; ++i) // Each firefly
{
  for (int j = 0; j < numFireflies; ++j) // Others
  {
    if (swarm[i].intensity < swarm[j].intensity)
    {
      // Move firefly(i) toward firefly(j)
...

Notez que parce que chacun d'eux pour l'index de la boucle commence à 0, chaque paire de lucioles est comparé deux fois dans chaque itération du while boucle. Afin de déplacer une luciole vers un autre firefly avec une intensité plus élevée, tout d'abord l'attrait doit être calculée :

double r = Distance(swarm[i].position, swarm[j].position);
double beta = B0 * Math.Exp(-g * r * r);
...

Beta variable définit l'attraction et sera utilisé pour déplacer la luciole [i] dans un instant. Sa valeur dépend du carré de la distance entre les lucioles [i] et [j], qui est calculé à l'aide de la méthode d'assistance Distance. Méthode Distance renvoie la distance euclidienne entre deux positions. Par exemple, si la luciole [i] en deux dimensions est à (3.0, 4.0) et Luciole [j] est à (5.0, 9.0), la distance entre eux est sqrt ((5-3) ^ 2 + (9-4) ^ 2) = sqrt (4 + 25) = sqrt(29) = 5,4. Notez que beta utilise la distance au carré, qui est l'inverse de l'opération racine carrée, donc le calcul du bêta pourrait être simplifié, au détriment de la souplesse, si vous avez décidé d'utiliser une mesure différente de la distance.

Le mouvement réel est accompli avec ces déclarations :

for (int k = 0; k < dim; ++k)
{
  swarm[i].position[k] += beta *
    (swarm[j].position[k] - swarm[i].position[k]);
  swarm[i].position[k] += a * (rnd.NextDouble() - 0.5);
  if (swarm[i].position[k] < minX)
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
  if (swarm[i].position[k] > maxX)
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
}
...

Le composant de kth de la position de la luciole [i] est déplacé un bêta -­fraction de la distance entre la luciole [i] et firefly [j] vers Luciole [j]. Ensuite un petit terme aléatoire est ajouté à chaque composante de position kth. Cela permet d'éviter l'algorithme de rester coincé dans des solutions non optimale. Chaque composante de la position est vérifié pour voir si il est allé hors de portée, et dans l'affirmative, une valeur dans l'échelle aléatoire est attribuée.

Le code de mouvement de boucles imbriquées se termine en mettant à jour l'erreur et l'intensité de la luciole juste-déplacé :

swarm[i].error = Error(swarm[i].position);
      swarm[i].intensity = 1 / (swarm[i].error + 1);
    } // If firefly(i) < firefly(j)
  } // j
} // i each firefly
...

Méthode résoudre se termine par ces déclarations :

...
   Array.Sort(swarm); // low error to high
    if (swarm[0].error < bestError)
    {
      bestError = swarm[0].error;
      for (int k = 0; k < dim; ++k)
        bestPosition[k] = swarm[0].position[k];
    }
    ++epoch;
  } // While
  return bestPosition;
} // Solve

Après chaque paire de lucioles a été comparé et moins intenses lucioles ont déménagé vers les lucioles plus intenses, le tableau d'objets Firefly est trié de faible erreur d'erreur élevé afin que le meilleur est à essaim [0]. Cet objet est vérifié pour voir si une nouvelle meilleure solution a été trouvée. Trier le tableau d'objets Firefly a également l'effet important de l'évolution de leur emplacement dans le tableau pour que les objets sont traités dans un ordre différent à chaque fois par le tout en boucle.

Les méthodes d'assistance

Résoudre méthode appelle les méthodes d'assistance Distance et erreur, qui appelle ensuite la méthode d'assistance Muika. Méthode d'assistance Distance est définie comme :

static double Distance(double[] posA, double[] posB)
{
  double ssd = 0.0; // sum squared diffrences
  for (int i = 0; i < posA.Length; ++i)
    ssd += (posA[i] - posB[i]) * (posA[i] - posB[i]);
  return Math.Sqrt(ssd);
}

Méthode d'assistance Muika est défini comme :

static double Michalewicz(double[] xValues)
{
  double result = 0.0;
  for (int i = 0; i < xValues.Length; ++i) {
    double a = Math.Sin(xValues[i]);
    double b = Math.Sin(((i+1) * xValues[i] * xValues[i]) / Math.PI);
    double c = Math.Pow(b, 20);
    result += a * c;
  }
  return -1.0 * result;
}

Si vous faites référence à la définition mathématique de la fonction Muika au bas de Figure 2, vous verrez que la fonction a un exposant de 2 m. Toutefois, la valeur de m est généralement sur 10, donc dans le code, une valeur constante de 20 est utilisée. Méthode d'assistance erreur est défini comme :

static double Error(double[] xValues)
{
  int dim = xValues.Length;
  double trueMin = 0.0;
  if (dim == 2)
    trueMin = -1.8013; // Approx.
  else if (dim == 5)
    trueMin = -4.687658; // Approx.
  double calculated = Michalewicz(xValues);
  return (trueMin - calculated) * (trueMin - calculated);
}

La méthode d'erreur renvoie juste le produit de la carré de la différence entre la valeur minimale connue de la fonction Muika et la valeur calculée. Cette fonction d'erreur factice peut calculer très rapidement, mais dans la plupart de machine scénarios d'apprentissage, la fonction d'erreur peut être très chronophage.

La classe de Firefly

La définition de classe de Firefly commence par :

public class Firefly : IComparable<Firefly>
{
  public double[] position;
  public double error;
  public double intensity;
...

La classe hérite de l'interface IComparable afin que des tableaux et des listes contenant l'objet peuvent être triées automatiquement. Les champs de données sont définies à l'aide de portée publique pour plus de simplicité. Parce qu'il y a une bijection entre l'erreur et l'intensité, ou l'autre de ces deux champs pouvaient être supprimées. Le constructeur de classe est :

public Firefly(int dim)
{
  this.position = new double[dim];
  this.error = 0.0;
  this.intensity = 0.0;
}

Il existe de nombreuses alternatives de conception, que vous pouvez envisager. Ici le constructeur alloue simplement l'espace pour le tableau de la situation. La seule autre méthode publique est CompareTo :

public int CompareTo(Firefly other)
  {
    if (this.error < other.error) return -1;
    else if (this.error > other.error) return +1;
    else return 0;
  }
} // Class Firefly

La méthode CompareTo ordres objets de Firefly d'erreur bas vers haut. Une alternative équivalente est à l'ordre de haute intensité au plus bas.

Quelques commentaires

L'implémentation de l'algorithme de firefly présenté dans cet article est basée sur le livre de 2009 de la graine. L'algorithme d'origine a donné naissance à plusieurs variantes. L'étude présente quelques données qui suggèrent la que FA est supérieure à optimisation essaim de particules, au moins sur certains problèmes d'optimisation de référence factice. Je suis un peu sceptique. Toutefois, à mon avis, un scénario dans lequel FA est très utile est lorsque la fonction objectif être réduits au minimum a des solutions multiples. Même si ce n'est pas tout à fait évident, il s'avère que, FA automatiquement s'organise en essaims secondaires qui peuvent trouver des solutions multiples simultanément.

---

Dr. James McCaffrey travaille pour Microsoft Research à Redmond, Washington  Il a travaillé sur plusieurs produits Microsoft, y compris Internet Explorer et Bing. Dr. McCaffrey est joignable au jammc@microsoft.com.

Merci aux experts techniques Microsoft suivants d'avoir relu cet article : Todd Bello, Marciano Moreno Diaz Covarrubias et Alisson Sol