• Article

Février 2016

Volume 31, numéro 2

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

Série de tests - Optimisation de la prolifération des cafards

Par James McCaffrey

James McCaffreyRoach infestation optimisation est un algorithme d'optimisation numérique faiblement basé sur le comportement de cafards courants tels que Periplaneta americana. Oui, vous lisez qui correctement. Je vais essayer de m'expliquer plus clairement.

Dans l'apprentissage automatique, un algorithme d'optimisation numérique est souvent utilisé pour rechercher un jeu de valeurs pour les variables (généralement appelé poids) qui minimisent une mesure de l'erreur. Par exemple, la classification de régression logistique utilise une équation mathématique où, s'il existe des variables explicatives n, il y a n + 1 valeurs de poids doivent être déterminés. Le processus de détermination des valeurs de poids est appelé apprentissage du modèle. L'idée est d'utiliser une collection de données d'apprentissage qui présente des valeurs de sortie corrects. Un algorithme d'optimisation numérique est utilisé pour rechercher les valeurs des poids qui minimisent l'erreur entre les valeurs de sortie calculée et les valeurs de sortie corrects connus.

Il existe de nombreux algorithmes d'optimisation numérique. Les plus courantes sont basées sur des dérivés de calcul, mais il existe également des algorithmes qui sont basées sur les comportements des systèmes naturels. Ils sont parfois appelés algorithmes inspiré de bio. Cet article explique relativement nouveau (première publication en 2008) technique appelée optimisation d'infestation roach (RIO). Optimisation de RIO modélise faiblement le comportement butineuses et agrégation d'une collection de roaches.

Un bon moyen pour avoir une idée de ce qui est RIO et voir où cet article est menée consiste à examiner le programme de démonstration dans Figure 1. L'objectif de la démonstration est RIO permettent de trouver la valeur minimale de la fonction Rastrigin avec huit variables d'entrée. La fonction Rastrigin est une fonction de banc d'essai standard utilisée pour évaluer l'efficacité des algorithmes d'optimisation numérique. La fonction a la valeur minimale connue 0.0 situé x = (0, 0,... 0) où le nombre de valeurs de 0 est égal au nombre de valeurs d'entrée.

L'algorithme d'optimisation Infestation Roach en Action
Figure 1 l'algorithme d'optimisation Infestation Roach en Action

La fonction Rastrigin est difficile pour la plupart des algorithmes d'optimisation, car il a plusieurs pics et creux qui créent des valeurs minimales locales capable d'intercepter les algorithmes. Il n'est pas possible de visualiser facilement la fonction Rastrigin avec huit valeurs d'entrée, mais vous pouvez obtenir une bonne idée des caractéristiques de la fonction en examinant un graphique de la fonction de deux valeurs d'entrée, illustré Figure 2.

La fonction Rastrigin avec deux Variables d'entrée
Figure 2 la fonction Rastrigin avec deux Variables d'entrée

Le programme de démonstration définit le nombre de roaches à 20. Chaque roach simulée a une position qui représente une solution possible au problème de minimisation. Roaches plus augmentent les chances de trouver la solution optimale true au détriment des performances. RIO utilise généralement 10 à 100 roaches.

RIO est un processus itératif et requiert une valeur de compteur de boucle maximale. La démonstration définit la valeur maximale de 10 000 itérations. Le nombre maximal d'itérations varient du problème en question, mais les valeurs comprises entre 1 000 et 100 000 sont courantes. RIO possède un élément caractère aléatoire et la démonstration définit la valeur de départ pour le Générateur de nombres aléatoires à 6, car 6 a donné la sortie de démonstration représentatif.

Dans la démonstration illustrée Figure 1, la meilleure erreur (du plus petit) associée à la position roach meilleures trouvée jusqu'à présent a été affichée chaque fois 500 unités. Une fois l'algorithme, le meilleur emplacement trouvé pour n'importe quel roach a x = (0, 0, 0, 0, 0, 0, 0, 0), qui est, en fait, la réponse correcte. Mais notez que si le nombre maximal d'itérations a été défini à 5 000 au lieu de 10 000, RIO ne serait pas trouvé un minimum global. RIO, comme presque tous les algorithmes d'optimisation numérique, n'est pas garanti pour trouver une solution optimale dans des scénarios pratiques.

Cet article suppose que vous disposez d'au moins intermédiaires de compétences en programmation, mais ne suppose pas que vous savez quoi que ce soit sur l'optimisation numérique ou l'algorithme d'optimisation infestation roach. Le programme de démonstration est codé avec c#, mais ne pas avoir trop de difficultés refactoriser le code dans un autre langage tel que Visual Basic ou JavaScript.

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

Structure globale du programme

La structure générale du programme est présentée dans Figure 3. Pour créer la démonstration, j'ai lancé Visual Studio et créé une nouvelle application de console c# nommée RoachOptimization. La démonstration n'a aucune dépendance significative de Microsoft .NET Framework pour n'importe quelle version récente de Visual Studio fonctionne.

Structure du programme de démonstration figure 3 Roach optimisation

using System;
namespace RoachOptimization
{
  class RoachOptimizationProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin roach optimization demo");
      // Code here
      Console.WriteLine("End roach demo");
      Console.ReadLine();
    }
    static double[] SolveRastrigin(int dim, int numRoaches,
      int tMax, int rndSeed) { . . }
    public static double Error(double[] x) { . . }
    static double Distance(double[] pos1,
      double[] pos2) { . . }
    static void Shuffle(int[] indices,
      int seed) { . . }
  } // Program
  public class Roach
  {
    // Defined here
  }
}

Une fois que le code du modèle chargé dans l'éditeur Visual Studio, dans la fenêtre Explorateur de solutions, j'ai renommé le fichier Program.cs pour le RoachOptimizationProgram.cs plus descriptif et Visual Studio renommé automatiquement la classe Program pour moi. En haut du code source, j'ai supprimé tout inutiles à l'aide d'instructions, en laissant uniquement la référence unique au système.

J'ai codé la démonstration en utilisant une approche essentiellement de la méthode statique et non une approche complète de la programmation orientée objet (OOP). La démonstration a toute la logique de contrôle dans la méthode Main. Il commence en définissant les valeurs de paramètre d'entrée algorithme :

Console.WriteLine("Begin roach optimization demo");
int dim = 8;
int numRoaches = 20;
int tMax = 10000;
int rndSeed = 6;

La variable dim Spécifie le nombre de valeurs d'entrée pour la fonction de Rastrigin. Dans un scénario d'apprentissage non-demo, la dimension représente le nombre de poids dans le modèle de prévision. Le nombre de roaches est défini sur 20. Variable tMax est le nombre maximal d'itérations. RIO, comme la plupart des algorithmes bio-inspiré, est probabiliste. Dans ce cas, une valeur de départ aléatoire variable est définie sur 6.

Ensuite, les paramètres RIO sont répercutées dans la console :

Console.WriteLine("Goal is to minimize Rastrigin's " +
  "function in " + dim + " dimensions");
Console.WriteLine("Problem has known min value = 0.0 " +
  "at (0, 0, .. 0) ");
Console.WriteLine("Setting number of roaches = " +
  numRoaches);
Console.WriteLine("Setting maximum iterations = " +
  tMax);
Console.WriteLine("Setting random seed = " + rndSeed);;

L'algorithme d'optimisation roach est appelée comme suit :

Console.WriteLine("Starting roach optimization ");
double[] answer = SolveRastrigin(dim, numRoaches,
  tMax, rndSeed);
Console.WriteLine("Roach algorithm completed");

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

double err = Error(answer);
Console.WriteLine("Best error found = " +
  err.ToString("F6") + " at: ");
for (int i = 0; i < dim; ++i)
  Console.Write(answer[i].ToString("F4") + " ");
Console.WriteLine("");
Console.WriteLine("End roach optimization demo");
Console.ReadLine();

L'algorithme d'optimisation roach présenté dans cet article est basé sur l'article 2008, « Optimisation de l'Infestation Roach », par refuges temporaires T., C. Espagne, N. saumon et J. Keller. Vous pouvez trouver le papier à plusieurs emplacements sur le Web.

Présentation de l'algorithme d'optimisation Roach

Dans RIO, il existe une collection de roaches simulés. Chaque roach a une position de n-dimensions qui représente une solution possible à un problème de minimisation. Comportement de roach simulé est basé sur trois comportements de roaches réels. Tout d'abord, roaches sont susceptibles d'évoluer vers des zones sombres. Deuxièmement, roaches comme à regrouper. Troisièmement, lorsque roaches obtenir gourmand en, ils mettra à leur emplacement actuel pour rechercher des produits alimentaires. Exactement comment simulé modèle roaches ces comportements deviendra claires lorsque le code est présenté.

Exprimé en pseudo-code très haut niveau, l'algorithme d'optimisation roach est présenté dans Figure 4. À première vue, l'algorithme semble assez simple. Toutefois, il existe un grand nombre de détails qui ne sont pas visibles dans le pseudo-code.

Figure 4 l'algorithme Roach à un niveau élevé

initialize n roaches to random positions
loop tMax times
  compute distances between all roaches
  compute median distance
  for-each roach
    compute number neighbors
    exchange data with neighbors
    if not hungry
      compute new velocity
      compute new position
      check if new best position
    else if hungry
      relocate to new position
    end-if
  end-for
end loop
return best position found

La classe Roach

La définition de classe défini par le programme Roach commence par :

public class Roach
{
  public int dim;
  public double[] position;
  public double[] velocity;
  public double error;
...

Le champ de dimension est la dimension de problème, ce qui est de 8 dans le cas de la démonstration. Le champ de position est un tableau conceptuellement représente l'emplacement d'un roach et représente également une solution à un problème de minimisation. Le champ de la vitesse est un tableau de valeurs qui déterminent où se déplacera le roach dans l'unité de temps suivante. Par exemple, si la dimension = 2 et position = (5.0, 3.0) et rapidité = (1.0, -2,0) déplace vers le roach (6.0, 1.0). Le champ d'erreur est l'erreur associée à la position actuelle.

La définition de continue :

public double[] personalBestPos;
public double personalBestErr;
public double[] groupBestPos;
public int hunger;
private Random rnd;

Le champ personalBestPos conserve le meilleur emplacement trouvé par la simulation roach à tout moment au cours de son déplacement. La personalBestError conserve l'erreur qui correspond à personalBestPos. Le champ groupBestPos conserve le meilleur emplacement trouvé par une d'un groupe de roaches de voisin. Le champ de faim est une valeur entière qui représente le mode gourmand en le roach est. Le rnd objet Random est utilisé pour initialiser un roach vers un emplacement aléatoire.

La définition de classe Roach continue en définissant un constructeur :

public Roach(int dim, double minX, double maxX,
  int tHunger, int rndSeed)
{
  this.dim = dim;
  this.position = new double[dim];
  this.velocity = new double[dim];
  this.personalBestPos = new double[dim];
  this.groupBestPos = new double[dim];
...

Les paramètres minX et maxX sont utilisés pour définir des limites pour les composants du vecteur position. Paramètre tHunger est une valeur maximale de faim. Lorsque les faim d'un roach atteint tHunger, le roach se déplace vers un nouvel emplacement. Le constructeur alloue de l'espace pour les champs de tableau de quatre.

Ensuite, le constructeur initialise l'objet Random et il utilise ensuite pour définir la valeur de faim initiale à une valeur aléatoire :

this.rnd = new Random(rndSeed);
this.hunger = this.rnd.Next(0, tHunger);

Ensuite, le constructeur affecte la position initiale velocity, idéalement personnel et tableaux emplacement meilleures de groupe des valeurs aléatoires comprises entre minX et maxX :

for (int i = 0; i < dim; ++i) {
  this.position[i] = (maxX - minX) * rnd.NextDouble() + minX;
  this.velocity[i] = (maxX - minX) * rnd.NextDouble() + minX;
  this.personalBestPos[i] = this.position[i];
  this.groupBestPos[i] = this.position[i];
}

La définition de constructeur Roach se termine comme suit :

...
    error = RoachOptimizationProgram.Error(this.position);
    personalBestErr = this.error;
  } // ctor
} // Roach

Le champ d'erreur est défini en appelant la méthode externe erreur, défini dans la classe de programme appelant. Une autre approche consiste à calculer la valeur d'erreur avant d'appeler le constructeur, puis passe la valeur d'erreur dans en tant que paramètre au constructeur.

L'implémentation de l'algorithme Roach

L'algorithme RIO est contenue dans la méthode statique SolveRastrigin, dont la définition commence par :

static double[] SolveRastrigin(int dim, int numRoaches,
  int tMax, int rndSeed)
{
  double C0 = 0.7;
  double C1 = 1.43;
  double[] A = new double[] { 0.2, 0.3, 0.4 };
...

Constantes C0 et C1 sont utilisées lors de l'informatique vélocité de nouveau d'une roach, comme vous le verrez bientôt. Les valeurs utilisées, 0,7 et 1,43, proviennent de la théorie essaims particulaires. Vous pouvez également examiner les autres valeurs.

Roaches qui sont proches les uns des autres sont appelés voisins. Voisins sont parfois, mais pas toujours, les informations exchange. Le tableau nommé un probabilités de blocages. La première valeur, 0,2, est la probabilité qu'un roach avec un voisin s'échanger des informations avec ce voisin. La deuxième valeur, 0.3, est la probabilité qu'un roach échange des informations si elle a deux voisins. La troisième valeur, 0,4, est la probabilité d'échange d'informations si un roach a trois voisins.

Ces valeurs de probabilité (0,2, 0,3, 0,4) ne sont pas celles qui ont été utilisés dans le document de recherche source. L'étude d'origine utilisé les valeurs de probabilité (0,49 respectivement 0,63, 0,65), qui correspondent au comportement de roach réel, comme indiqué dans un document de recherche biologie. J'ai découvert que les probabilités qui correspond au comportement de roach réel n'étaient pas aussi efficaces que les valeurs de probabilité artificielle utilisés dans la démonstration. La définition de méthode SolveRastrigin continue avec :

int tHunger = tMax / 10;
double minX = -10.0;
double maxX = 10.0;
int extinction = tMax / 4;
Random rnd = new Random(rndSeed);

THunger de variable locale détermine quand un roach deviennent gourmand en et laissez son emplacement actuel et les voisins. Par exemple, si tMax est 10 000 comme dans la démonstration, puis, lorsque le valeur de faim d'un roach atteint le tMax / 10 = 1 000, le roach se déplace vers une nouvelle position.

MaxX et minX de variables définissent des limites sur le vecteur de position d'un roach. Les valeurs (-10.0, +10.0) sont normales pour les poids d'apprentissage et correspondent aux limites habituelles pour la fonction Rastrigin. Par exemple, un problème avec la dimension = 3, le vecteur de position est un tableau de trois cellules, qui ont des valeurs entre-10.0 et +10.0.

Extinction de variable locale détermine quand tous les roaches seront meurent et est devenue à nouvelles positions. Ce mécanisme est un redémarrage et empêche que l'algorithme bloqués à une solution non optimal.

Local rnd d'objet Random est utilisé par l'algorithme pour trois objectifs. L'ordre dans lequel les roaches sont traitées est aléatoire ; l'échange d'informations entre roaches de voisin se produit avec une certaine probabilité ; et il existe un composant à la vélocité de nouveau de chaque roach aléatoire. Méthode SolveRastrigin continue :

Roach[] herd = new Roach[numRoaches];
for (int i = 0; i < numRoaches; ++i)
  herd[i] = new Roach(dim, minX, maxX, tHunger, i);

La collection de simulations roaches est un tableau nommé généalogiques. Il existe toutes sortes de noms intéressants pour les collections d'animaux, comme un bloc de baleines et une poignée de canards. En fait, une collection de cafards est appelée une intrusion de roaches. (Ces informations peuvent rendre un résultat de la barre utile pour vous.)

Notez que la boucle d'index variable, i, est passé au constructeur Roach. La variable d'index agit comme une valeur de départ aléatoire pour l'objet Random qui fait partie de la définition de classe Roach. Passage d'une variable d'index de boucle à utiliser comme une valeur de départ aléatoire est une technique courante dans l'apprentissage. La définition de méthode se poursuit avec :

int t = 0;  // Loop counter (time)
int[] indices = new int[numRoaches];
for (int i = 0; i < numRoaches; ++i)
  indices[i] = i;
double bestError = double.MaxValue;
double[] bestPosition = new double[numRoaches];
int displayInterval = tMax / 20;

Le tableau nommé contient les valeurs d'index (0, 1, 2,... numRoaches-1). Le tableau sera être mélangé dans la boucle de traitement principale afin que l'ordre dans lequel les roaches sont traités est différent à chaque fois. BestError et des variables locales bestPosition conservent la position parfaitement et l'associé erreur trouvée par n'importe quel roach à tout moment. DisplayInterval variable local détermine quand un message de progression s'affichera dans la console. Ensuite, une matrice de style de tableau de tableaux est instanciée pour conserver la distance entre chaque paire de roaches :

double[][] distances = new double[numRoaches][];
for (int i = 0; i < numRoaches; ++i)
  distances[i] = new double[numRoaches];

Par exemple, si des distances [0] [3] = 7,89 distances [3] [0] est également 7,89 et la distance entre roach 0 et roach 3 est 7,89. Notez que les données redondantes n'est pas graves, car dans la plupart des cas, vous n'aurez pas un très grand nombre de roaches. Ensuite, la boucle de traitement principale démarre :

while (t < tMax)
{
  if (t > 0 && t % displayInterval == 0) {
    Console.Write("time = " + t.ToString().PadLeft(6));
    Console.WriteLine(" best error = " +
      bestError.ToString("F5"));
  }
...

Ensuite, les distances entre les roaches est calculée :

for (int i = 0; i < numRoaches - 1; ++i) {
  for (int j = i + 1; j < numRoaches; ++j) {
    double d = Distance(herd[i].position,
                 herd[j].position);
    distances[i][j] = distances[j][i] = d;
  }
}

Les valeurs de distance sont calculées à l'aide de la méthode d'assistance Distance, ce qui s'affiche peu de temps. Le tableau indexation ici est un peu difficile, mais je laisse le soin de vérifier si vous êtes curieux. Ensuite, les valeurs de distance sont copiés de la matrice de distances dans un tableau afin qu'ils peuvent être triées et ensuite la distance médiane peut être déterminée :

double[] sortedDists =
  new double[numRoaches * (numRoaches - 1) / 2];
int k = 0;
for (int i = 0; i < numRoaches - 1; ++i) {
  for (int j = i + 1; j < numRoaches; ++j) {
    sortedDists[k++] = distances[i][j];
  }
}

La taille du tableau est mieux expliquer par exemple. Supposons qu'il y a n = 4 roaches. Puis la matrice de distances aura une taille de 4 x 4. Les valeurs sur la diagonale, [0] [0], [1] [1], [2] [2] et [3] [3] est 0.0 et ne doit pas être inclus. Qui conserve les 6 valeurs au [0] [1], [0] [2], [0] [3], [1] [2], [1] [3] et [2] [3]. Vous n'avez pas besoin les valeurs de distance identiques aux symétrique index [1] [0], [2] [0] et ainsi de suite. Il y a n * (n-1) / 2 distinctes des valeurs distances. Ensuite, la distance entre roaches médiane est calculée et les indices de roach sont aléatoires :

Array.Sort(sortedDists);
double medianDist = sortedDists[sortedDists.Length / 4];
Shuffle(indices, t); // t is used as a random seed

Ici, car je diviser par 4, la distance est un quart à partir du début du tableau de distances trié donc le résultat n'est pas vraiment une médiane, il s'agit d'un quartile. L'article d'origine utilisé la valeur médiane réelle (en divisant par 2), mais j'ai découvert que le quartile fonctionnait mieux que la valeur médiane. L'idée est que la valeur médiane ou quartile détermine le nombre de voisins un roach a, qui influence à son tour degré les roaches sont groupées. À l'aide de la fonction quartile conserve le roaches plus éloignés, en leur donnant une plus grande chance pour trouver la valeur minimale globale difficile pour la fonction cible à minimiser.

Les indices de roach sont aléatoires à l'aide de la méthode d'assistance aléatoire, qui sera présenté sous peu. Notez que le temps d'index variable, t, est passé à la méthode de lecture aléatoire et agit comme une valeur de départ pour le Générateur de nombres aléatoires de lecture aléatoire. Ensuite, la boucle pour traiter chaque roach commence ainsi :

for (int i = 0; i < numRoaches; ++i)  // Each roach
{
  int idx = indices[i]; // Roach index
  Roach curr = herd[idx]; // Ref to current roach
  int numNeighbors = 0;
...

Une référence à le roach actuel, généalogiques [idx], est créée et nommée Dr. Il s'agit simplement par commodité. Ensuite, le nombre de voisins de le roach actuel est calculé :

for (int j = 0; j < numRoaches; ++j) {
  if (j == idx) continue;
  double d = distances[idx][j];
  if (d < medianDist) // Is a neighbor
    ++numNeighbors;
}

La condition j == idx est utilisée pour empêcher que l'actuel roach comptabilisé comme un voisin à elle-même. Ensuite, le nombre de voisins est déterminé :

int effectiveNeighbors = numNeighbors;
if (effectiveNeighbors >= 3)
  effectiveNeighbors = 3;

Rappelez-vous que l'objectif du calcul du nombre de voisins consiste à déterminer la probabilité que les voisins échangent des informations. Mais la probabilité d'échange d'informations est le même pour les voisins de 3 ou plus. Ensuite, l'algorithme détermine si les informations doivent être échangées :

for (int j = 0; j < numRoaches; ++j) {
  if (j == idx) continue;
  if (effectiveNeighbors == 0) continue;
  double prob = rnd.NextDouble();
  if (prob > A[effectiveNeighbors - 1]) continue;
...

Le roach actuelle est comparée à toutes les autres roaches. Si le roach actuel n'a aucun voisin n'existe aucun échange d'informations. Si le roach actuel a un ou plusieurs des voisins, le tableau A de probabilités est utilisé pour décider si les informations doivent être échangées ou non. Suivant :

double d = distances[idx][j];
if (d < medianDist) { // a neighbor
  if (curr.error < herd[j].error) { // curr better than [j]
    for (int p = 0; p < dim; ++p) {
      herd[j].groupBestPos[p] = curr.personalBestPos[p];
      curr.groupBestPos[p] = curr.personalBestPos[p];
    }
  }
...

En cas d'échange d'informations entre roaches de voisin, la position idéale de groupe et l'erreur associée de mieux les deux roaches est copié dans le pire roach. La deuxième branche du code d'informations exchange est :

...
    else { // [j] is better than curr
      for (int p = 0; p < dim; ++p) {
        curr.groupBestPos[p] = herd[j].personalBestPos[p];
        herd[j].groupBestPos[p] = herd[j].personalBestPos[p];
      }
    }
  } // If a neighbor
} // j, each neighbor

Une fois que l'échange d'informations entre roaches de voisin est prise en charge, l'actuel roach déplace si elle n'est pas gourmand en. La première partie du processus de déplacement consiste à calculer la vélocité de nouveau du roach actuel :

if (curr.hunger < tHunger) {
  for (int p = 0; p < dim; ++p)
    curr.velocity[p] = (C0 * curr.velocity[p]) +
     (C1 * rnd.NextDouble() * (curr.personalBestPos[p] -
       curr.position[p])) +
     (C1 * rnd.NextDouble() * (curr.groupBestPos[p] -
       curr.position[p]));

La vitesse de nouveau comporte trois composants. Le premier composant est la rapidité anciennes, parfois appelé l'inertie dans la terminologie des essaims particulaires. L'inertie agit pour conserver un roach dans la même direction. Le deuxième composant est la position plus connue de le roach, ce qui est parfois appelée le terme COGNITIF. Le composant COGNITIF empêche une roach de déplacer les positions incorrecte. Le troisième composant est la position plus connue les voisins de la roach. Ce composant n'est plus ou moins unique à RIO et n'a pas un nom standard. Ce terme fait Office pour maintenir des groupes de roaches ensemble.

Une fois la rapidité de la roach en cours a été calculée, le roach est déplacé :

for (int p = 0; p < dim; ++p)
  curr.position[p] = curr.position[p] + curr.velocity[p];
double e = Error(curr.position);
curr.error = e;

Après que le roach actuel est déplacé, son nouvel emplacement est vérifié pour voir s'il s'agit d'un nouveau idéal pour le roach :

if (curr.error < curr.personalBestErr) {
  curr.personalBestErr = curr.error;
  for (int p = 0; p < dim; ++p)
    curr.personalBestPos[p] = curr.position[p];
}

Ensuite, la nouvelle position est vérifiée pour voir s'il est un nouveau meilleur global, et le compteur de faim est incrémenté :

if (curr.error < bestError) {
    bestError = curr.error;
    for (int p = 0; p < dim; ++p)
      bestPosition[p] = curr.position[p];
  }
  ++curr.hunger;
} // If not hungry

La boucle de chaque roach se termine à cause des roaches gourmand en :

else { // Roach is hungry
  {
    herd[idx] = new Roach(dim, minX, maxX, tHunger, t);
  }
} // j each roach

Si le compteur de faim d'un roach atteint le seuil tHunger, le roach se déplace vers un nouvel emplacement aléatoire. Une fois que tous les roaches ont été traités, l'algorithme se termine en vérifier s'il est temps pour une extinction globale, en incrémentant le compteur temps principal et en retournant le mieux en toute roach :

if (t > 0 && t % extinction == 0) { // Extinction?
      Console.WriteLine("Mass extinction at t = " +
        t.ToString().PadLeft(6));
      for (int i = 0; i < numRoaches; ++i)
        herd[i] = new Roach(dim, minX, maxX, tHunger, i);
    }
    ++t;
  } // Main while loop
  return bestPosition;
} // Solve

Notez que l'algorithme est contenu dans une méthode nommée SolveRastrigin plutôt qu'un nom plus général telles que de résoudre. L'idée est que RIO est vraiment une métaheuristique, au lieu d'un algorithme normatives et doivent être personnalisés pour tout problème de minimisation vous cherchez à résoudre.

Les méthodes d'assistance

Méthode SolveRastrigin appelle les méthodes d'assistance Distance, erreur et la réorganisation. Méthode d'assistance Distance retourne la distance EUCLIDIENNE (racine carrée de la somme des différences de terme au carré) :

static double Distance(double[] pos1, double[] pos2)
{
  double sum = 0.0;
  for (int i = 0; i < pos1.Length; ++i)
    sum += (pos1[i] - pos2[i]) * (pos1[i] - pos2[i]);
  return Math.Sqrt(sum);
}

Méthode d'assistance erreur retourne le carré de la différence entre la valeur calculée de la fonction de Rastrigin à un roach donné position x et la valeur true minimale égale à zéro :

public static double Error(double[] x)
{
  double trueMin = 0.0; double rastrigin = 0.0;
  for (int i = 0; i < x.Length; ++i) {
    double xi = x[i];
    rastrigin += (xi * xi) - (10 * Math.Cos(2 * Math.PI * xi)) + 10;
  }
  return (rastrigin - trueMin) * (rastrigin - trueMin);
}

Méthode Shuffle rend aléatoire l'ordre des valeurs dans un tableau à l'aide de l'algorithme de Fisher-Yates mini :

static void Shuffle(int[] indices, int seed)
{
  Random rnd = new Random(seed);
  for (int i = 0; i < indices.Length; ++i) {
    int r = rnd.Next(i, indices.Length);
    int tmp = indices[r]; indices[r] = indices[i];
    indices[i] = tmp;
  }
}

La version d'origine de la recherche de RIO ne Randomiser l'ordre de traitement roach, mais j'ai découvert que cette approche améliore presque toujours l'exactitude des algorithmes d'optimisation s'inspirant de bio.

Quelques commentaires

Optimisation roach inspirés par rapport à d'autres techniques d'optimisation numérique est donc simplement l'efficacité ? Selon certaines expériences limités que j'ai effectué, RIO semble résoudre certains problèmes de banc d'essai mieux que d'autres algorithmes, mais est plus faible sur les autres problèmes. Je conclure que RIO n'est pas un nouvel algorithme d'optimisation à usage général fantastique, il n'est pas promesse et peut être utile pour certains problèmes de minimisation spécifiques. Et sûr, l'optimisation infestation roach possède l'une des noms plus insolite tous de l'informatique.

Récupération d'urgence. James McCaffreytravaille pour Microsoft Research à Redmond, Wash. Il a travaillé sur plusieurs produits Microsoft, notamment Internet Explorer et Bing. Dr. Vous pouvez contacter James McCaffrey àjammc@microsoft.com.

Remercie les experts techniques Microsoft suivants pour avoir relu cet article : Todd Bello, Marciano Moreno Duprez Covarrubias et Alisson SQL