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

L'intelligence artificielle

Optimisation par essaims particulaires

James McCaffrey

Télécharger l'exemple de code

Optimisation d'essaim de particules (PSO) est une technique d'intelligence artificielle (IA) qui peut être utilisée pour trouver des solutions approximatives à des extrêmement difficiles, voire impossibles, optimisation et minimisation problèmes numériques. La version du PSO que j'ai décrit dans cet article a été présentée en premier dans un document de recherche de 1995 par j. Kennedy et r. Eberhart. PSO est faiblement modélisé sur le comportement de groupe, telles que les oiseaux flocage et poissons schooling. Le meilleur moyen pour vous pour avoir une idée Nouveautés PSO et pour voir où je m'apprête à ici consiste à examiner Figure 1.

La première partie de la figure décrit un problème factice en cours de résolution par un programme PSO de démonstration. L'objectif est de rechercher des valeurs de x 0 et 1 x dans ce cas la valeur de la fonction f = 3 + 0 x ^ 2 + 1 x ^ 2 est réduite. Ici, j'utilise la notation ^ 2 pour indiquer l'opération élévation au carré. Notez que j'ai choisi délibérément un problème simple réaliste pour conserver les idées des PSO clair. Il est évident que la solution à ce problème est x 0 = 0,0 et x 1 = 0,0, ce qui donne une valeur minimale de fonction de 3.0, donc à l'aide du PSO n'est pas vraiment nécessaire. J'aborde les problèmes plus réalistes qui peuvent être résolus par PSO plus loin dans cet article. Dans cet exemple, la dimension de la fonction afin de minimiser est 2, car nous devons résoudre pour les valeurs numériques 2. En règle générale, PSO est bien adaptée aux problèmes numériques avec des dimensions de 2 ou supérieure. Dans la plupart des cas, PSO doit avoir certaines contraintes sur la plage de valeurs x possible. X 0 et 1 x Voici arbitrairement limités à la plage -100.0 sur 100,0.

Figure 1 particules essaim optimisation démo s'exécute

La partie suivante de Figure 1 indique que le programme PSO utilise 10 des particules et que le programme effectuera une itération 1 000 fois. Comme vous le verrez bientôt, chaque particule représente une solution possible au problème PSO en cours de résolution. PSO est une technique itérative et dans la plupart des cas, il n'est pas possible de savoir quand une solution optimale a été trouvée. Par conséquent, les algorithmes PSO généralement doivent avoir une limite sur le nombre d'itérations pour exécuter.

Les lignes en regard de Figure 1 indiquent que chacune des particules dans l'essaim 10 est initialisée à une position aléatoire. La position d'une particule représente une solution possible au problème d'optimisation à résoudre. Le meilleur généré aléatoirement la position initiale est x 0 = 26.53 et x 1 =-6.09, qui correspond à la remise en forme (la mesure de qualité de la solution) de 3 + 26.53 ^ 2 + (-6.09) ^ 2 = 744.12. L'algorithme PSO entre ensuite dans une boucle de traitement principal où mises à jour de la position de chaque particule à chaque passage dans la boucle. La procédure de mise à jour est le cœur du PSO et je vais l'expliquer en détail plus loin dans cet article. Au bout de 1 000 itérations, l'algorithme PSO s'est en fait trouver la solution optimale de x 0 = 0,0 et x 1 = 0,0, mais laissez-moi vous soulignez le fait que la plupart des cas, que vous ne saurez pas si un programme PSO a trouvé une solution optimale.

Dans cet article, j'expliquer en détail l'algorithme PSO et ligne par ligne via le programme en exécution à vous guider tout Figure 1. J'ai codé le programme de démonstration dans C#, mais vous devez être capable de s'adapter facilement le code présenté ici à une autre langue, tel que Visual Basic.NET ou Python. Le code source complet pour le programme présenté dans cet article est disponible à l'adresse code.msdn.microsoft.com/mag201108PSO. Cet article suppose que vous disposez des compétences de codage intermédiaires avec un langage procédural moderne, mais n'assume pas de que vous savoir quoi que ce soit sur PSO ou techniques AI associées.

Particules

Lorsque vous utilisez PSO, une solution possible au problème d'optimisation numérique à l'étude est représentée par la position d'une particule. En outre, chaque particule a une vitesse en cours, ce qui représente une amplitude et la direction vers un nouveau, vraisemblablement une meilleure solution/position. Une particule possède également une mesure de la qualité de sa position actuelle, la position de la particule surtout connue (autrement dit, une position précédente avec la qualité surtout connue) et la qualité de la position surtout connue. J'ai codé une classe de particules, comme illustré à la Figure 2.

Figure 2 définition de particules

public class Particle
{
  public double[] position;
  public double fitness;
  public double[] velocity;

  public double[] bestPosition;
  public double bestFitness;

  public Particle(double[] position, double fitness,
   double[] velocity, double[] bestPosition, double bestFitness)
  {
    this.position = new double[position.Length];
    position.CopyTo(this.position, 0);
    this.fitness = fitness;
    this.velocity = new double[velocity.Length];
    velocity.CopyTo(this.velocity, 0);
    this.bestPosition = new double[bestPosition.Length];
    bestPosition.CopyTo(this.bestPosition, 0);
    this.bestFitness = bestFitness;
  }

  public override string ToString()
  {
    string s = "";
    s += "==========================\n";
    s += "Position: ";
    for (int i = 0; i < this.position.Length; ++i)
      s += this.position[i].ToString("F2") + " ";
    s += "\n";
    s += "Fitness = " + this.fitness.ToString("F4") + "\n";
    s += "Velocity: ";
    for (int i = 0; i < this.velocity.Length; ++i)
      s += this.velocity[i].ToString("F2") + " ";
    s += "\n";
    s += "Best Position: ";
    for (int i = 0; i < this.bestPosition.Length; ++i)
      s += this.bestPosition[i].ToString("F2") + " ";
    s += "\n";
    s += "Best Fitness = " + this.bestFitness.ToString("F4") + "\n";
    s += "==========================\n";
    return s;
  }
} // class Particle

La classe de particules a cinq membres de données publique : position, de capacité, vitesse, bestPosition et bestFitness. Lorsqu'à l'aide de PSO, par souci de simplicité je préfère utiliser des champs de la portée publique, mais vous souhaiterez peut-être utiliser des champs privés ainsi que récupérer et définir les propriétés à la place. Le champ nommé position est un tableau de type double et représente une solution possible au problème d'optimisation à l'étude. Bien que PSO peut être utilisé pour résoudre les problèmes non numérique, il est généralement conviennent le mieux pour résoudre des problèmes numériques. Adéquation du champ est une mesure de la qualité est de la solution représentée par position. Pour les problèmes de minimisation, qui sont les plus courants de problèmes sont résolus par PSO, plus petites valeurs du champ adéquation sont préférables à des valeurs plus élevées ; pour les problèmes d'optimisation, des valeurs plus élevées d'adéquation sont préférables.

Vitesse de champ est un tableau de type double et représente les informations nécessaires pour mettre à jour la position/solution en cours d'une particule. Je reviendrai bientôt velocity de particules en détail. Les champs de la quatrième et cinquième dans le type de particules sont bestPosition et bestFitness. Ces champs contiennent la meilleure position/solution trouvée par l'objet de particules et de l'aptitude à l'associé de la position idéale.

La classe de particules a un seul constructeur qui accepte cinq paramètres qui correspondent à chacun des cinq champs de données de la particule. Le constructeur de copie simplement chaque valeur de paramètre à son champ de données correspondante. Dans la mesure où tous les cinq champs de particules ont une portée publique, j'ai auraient pu omis le constructeur et ensuite simplement utilisé des instructions d'assignation de champ dans le code PSO, mais je pense que le constructeur conduit à un code plus propre.

La définition de classe de particules contient une méthode ToString qui reproduit en écho les valeurs des champs de cinq données. Comme avec le constructeur, car j'ai déclaré la position, l'adéquation, la vitesse, bestPosition et bestFitness les champs avec une portée publique, j'ai vraiment inutile une méthode ToString pour afficher les valeurs de l'objet d'une particule, mais y compris il simplifie l'affichage les champs et il l'utile pour le débogage de style WriteLine au cours du développement. Dans la méthode ToString, j'utilise la concaténation de chaînes plutôt que la classe StringBuilder plus efficace pour faciliter la refactoriser mon code pour un non-Microsoft.Langage basé sur le NET Framework si vous le souhaitez.

L'algorithme PSO

Bien que le cœur de l'algorithme thePSO est plutôt simple, vous devrez comprendre soigneusement afin de modifier le code dans cet article pour répondre à vos propres besoins. PSO est un processus itératif. À chaque itération de la boucle principale de traitement PSO, les vitesse actuelle de chaque particule est tout d'abord actualisé en fonction de vitesse actuelle de la particule, les informations locales de la particule et informations essaim global. Ensuite, la position de chaque particule est mis à jour à l'aide de la vitesse de nouveau la particule. En mathématique termes que les deux mettre à jour les équations sont les suivantes :

v(t+1) = (w * v(t)) + (c1 * r1 * (p(t) – x(t)) + (c2 * r2 * (g(t) – x(t))

x(t+1) = x(t) + v(t+1)

Laissez-moi m'expliquer ici ; le processus de mise à jour de position est en fait beaucoup plus simple que de proposer ces équations. La première équation met à jour la vitesse de la particule. Le terme v(t + 1) signifie que la vitesse au temps t + 1. Notez que v est en gras, indiquant cette vitesse est une valeur de vecteur et comporte plusieurs composants, tels que {1.55,-0.33}, plutôt que d'être une valeur scalaire unique. La nouvelle vitesse dépend de trois termes. Le premier terme est w * v(t). Le facteur w est appelé la masse d'inertie et est simplement une constante comme 0,73 (plus loin) ; v(t) est la vitesse actuelle au temps t. Le second terme est c1 * r1 * (p(t) – x(t)). Le facteur de c1 est une constante appelée le poids COGNITIF (ou personnel ou local). Le facteur de r1 est une variable aléatoire dans la plage [0, 1), qui est supérieure ou égale à 0 et strictement inférieur à 1. Le pvaleur de vecteur (t) est la position idéale de la particule trouvée jusqu'à présent. Le xvaleur de vecteur (t) est la position actuelle de la particule. Est le terme dans l'équation de la mise à jour velocity (c2 * r2 * (g(t) – x(t)). Le facteur de c2 est une constante nommée sociale — ou globale — poids. Le facteur de r2 est une variable aléatoire dans la plage de [0, 1). La **g (**t) valeur de vecteur est la position surtout connue trouvée par une partie jusque dans l'essaim. Une fois la vitesse de nouveau, v(t+1), a été déterminé, il est utilisé pour calculer la nouvelle position de particules x(t + 1).

Un exemple concret aidera à rendre le processus de mise à jour à effacer. Supposons que vous essayez de réduire de 3 + 0 x ^ 2 + 1 x ^ 2 comme décrit dans la section d'introduction de cet article. La fonction est tracée à la Figure 3. La base du cube contenant dans Figure 3 représente les valeurs de x 0 et 1 x et l'axe vertical représente la valeur de la fonction. Notez que la surface de traçage est réduit au minimum avec f = 3 lorsque x 0 = 0 et x 1 = 0.

Figure 3 traçage de f = 3 + 0 x ^ 2 + 1 x ^ 2

Supposons que par une particule de l'actuelle position, x(t), est {x 1, x 0} = {3.0, 4.0}, et que la particule actuelle du velocity, v(t), est {-1,0,-1.5}. Supposons également que constante w = 0,7, constante c1 = 1.4, constante c2 = 1.4, et que des nombres aléatoires r1 et r2 sont 0,5 et 0.6 respectivement. Enfin, supposons que la particule de notoriété position est p(t) = {2.5, 3.6} et la position globale surtout connue par une partie de l'essaim est g(t) = {2.3, 3.4}. Puis les nouvelles valeurs de vitesse et la position sont :

v(t + 1) = (0,7 * {-1,0,-1.5}) +

         (1.4 * 0.5 * {2.5, 3.6} - {3.0, 4.0}) +

         (1.4 * 0.6 * {2.3, 3.4} – {3.0, 4.0})

       = {-0.70, -1.05} + {-0.35, -0.28} + {-0.59, -0.50}

       = {-1.64, -1.83}

x(t + 1) = {3.0, 4.0} + {-1.64,-1.83}

       = {1.36, 2.17}

Rappelez-vous que la solution optimale est {x 1, x 0} = (0.0, 0.0}. Observez que le processus de mise à jour a amélioré l'ancienne position/solution à partir de (3.0, 4.0} à {1,36, 2,17}. Si vous chauffer et épicer un peu sur le processus de mise à jour, vous verrez que la nouvelle vitesse est la vitesse de l'ancienne (multiplié par un poids) plus un facteur qui dépend surtout connue position d'une particule, plus un autre facteur qui dépend de la position surtout connue à partir de toutes les particules dans l'essaim. Par conséquent, nouvelle position de la particule tend à déplacer vers une meilleure position en fonction de la position surtout connue de la particule et la notoriété de toutes les particules. Le graphique de Figure 4 montre comment déplacer des particules exécution pendant les huit premières itérations de la démonstration PSO. La particule commence à 0 x = 100.0, x 1 = 80,4 et tend à se déplacera vers la solution optimale de x 0 = 0 x 1 = 0. Le mouvement en spirale est caractéristique des PSO.

Figure 4 mouvement des particules vers la Solution optimale

Mise en œuvre de l'algorithme PSO

Figure 5 présente la structure globale du programme PSO qui a produit le programme d'exécution illustré Figure 1. J'ai utilisé Visual Studio pour créer un C# projet d'application console nommé ParticleSwarmOptimization. Code PSO est plutôt basique, par conséquent, n'importe quelle version de la.NET Framework (1.1 à 4) fonctionnent bien. J'ai supprimé tous les Visual Studio généré à l'aide d'instructions à l'exception de la référence à l'espace de noms du système principal. J'ai déclaré un objet de portée de la classe de type aléatoire pour générer des nombres aléatoires cognitives et sociales décrits dans la section précédente. J'ai également utilisé l'objet Random pour générer des vitesses initiales aléatoires et positions pour chaque objet de particules. À l'intérieur de la méthode Main j'encapsule mon tout le code dans un seul, un haut niveau instruction pour intercepter des exceptions try.

Figure 5 Structure de programme PSO

using System;
namespace ParticleSwarmOptimization
{
  class Program
  {
    static Random ran = null;
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin PSO demo\n");
        ran = new Random(0);

        int numberParticles = 10;
        int numberIterations = 1000;
        int iteration = 0;
        int Dim = 2; // dimensions
        double minX = -100.0;
        double maxX = 100.0;

        Particle[] swarm = new Particle[numberParticles];
        double[] bestGlobalPosition = new double[Dim];
        double bestGlobalFitness = double.MaxValue; 

        double minV = -1.0 * maxX;
        double maxV = maxX;

        // Initialize all Particle objects

        double w = 0.729; // inertia weight
        double c1 = 1.49445; // cognitive weight
        double c2 = 1.49445; // social weight
        double r1, r2; // randomizations

        // Main processing loop

        // Display results
        Console.WriteLine("\nEnd PSO demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal error: " + ex.Message);
      }
    } // Main()

    static double ObjectiveFunction(double[] x)
    {
      return 3.0 + (x[0] * x[0]) + (x[1] * x[1]);
    }

  } // class Program

  public class Particle
  {
    // Definition here 
  }

} // ns

Après l'instanciation de l'objet Random avec une valeur de départ arbitraire de 0, j'initialise certaines variables PSO clés :

int numberParticles = 10;
int numberIterations = 1000;
int iteration = 0;
int Dim = 2;
double minX = -100.0;
double maxX = 100.0;

J'utilise 10 objets de particules. En règle générale, plusieurs objets de particules valent mieux qu'un inférieur, mais plus peuvent diminuer considérablement les performances du programme. J'ai défini le nombre d'itérations de boucle principale de traitement à 1 000. Le nombre d'itérations que vous devrez utiliser dépend de la complexité du problème que vous tentez d'optimiser et de la puissance de traitement de votre machine hôte. En règle générale, les programmes PSO utilisent une valeur comprise entre 1 000 et 100 000. La variable nommée itération est un compteur pour suivre le nombre d'itérations de la boucle principale. La variable Dim contient le nombre de valeurs x dans une solution/position. Étant donné que le problème de mon exemple doit rechercher les valeurs de x 0 et 1 x qui minimisent 3 + 0 x ^ 2 + 1 x ^ 2, j'ai défini Dim sur 2. Comme je l'ai mentionné plus haut, dans la plupart des situations PSO vous voudrez limiter les valeurs x constituant le vecteur position/solution par rapport à des plages dépendant du problème. Sans certaines limites, vous recherchez efficacement de double.MinValue en double.MaxValue. Ici je limitent de façon arbitraire x 0 et 1 x [-100.0, +100.0].

Ensuite, j'ai préparer instancier l'essaim de particules :

Particle[] swarm = new Particle[numberParticles];
double[] bestGlobalPosition = new double[Dim];
double bestGlobalFitness = double.MaxValue; 
double minV = -1.0 * maxX;
double maxV = maxX;

Je crée un tableau d'objets nommés par essaim de particule. J'ai également configuré un tableau à détenir la position surtout connue globale déterminée par une partie des — désigné par g(t) dans l'algorithme — et l'aptitude de ce tableau de la position correspondante. J'ai défini des contraintes pour les valeurs maximales et minimales pour une vitesse de nouveau. L'idée ici est que dans la mesure où une nouvelle vitesse détermine la nouvelle position de la particule, je ne veux pas l'ampleur d'une des composantes de vitesse pour être énorme.

Le code pour initialiser l'essaim est comme suit :

for (int i = 0; i < swarm.Length; ++i)
{ 
  double[] randomPosition = new double[Dim];
  for (int j = 0; j < randomPosition.Length; ++j) {
    double lo = minX;
    double hi = maxX;
    randomPosition[j] = (hi - lo) * ran.NextDouble() + lo; 
  }
...

J'ai itérer sur chaque objet de particules dans un tableau nommé essaim. Je déclare un tableau de taille Dim à détenir une position aléatoire pour la particule en cours. Pour chaque valeur x de la position, je génère une valeur aléatoire comprise entre minX (-100.0) et maxX (+100.0). Dans de nombreux problèmes PSO réalistes, la plage pour chaque valeur x sera différente, afin que vous devrez ajouter du code pour traiter séparément chaque valeur de x dans le tableau des positions.

Maintenant je continuer le processus d'initialisation :

double fitness = ObjectiveFunction(randomPosition);
double[] randomVelocity = new double[Dim];
for (int j = 0; j < randomVelocity.Length; ++j) {
  double lo = -1.0 * Math.Abs(maxX - minX);
  double hi = Math.Abs(maxX - minX);
  randomVelocity[j] = (hi - lo) * ran.NextDouble() + lo;
}
swarm[i] = new Particle(randomPosition, fitness, randomVelocity,
  randomPosition, fitness);
...

Tout d'abord, je calcule la qualité de la baie de position aléatoire actuelle en transmettant ce tableau à la méthode ObjectiveFunction. Si vous revenez à Figure 5, vous verrez que la méthode ObjectiveFunction traite simplement la valeur de la fonction que j'essaie de réduire, à savoir 3 + x 0 ^ 2 + 1 x ^ 2. Ensuite, je calcule une vitesse aléatoire pour l'objet en cours de la particule. Une fois que j'ai une position aléatoire, l'aptitude de la position aléatoire et une vitesse aléatoire, je transmets ces valeurs au constructeur de particules. Rappelez-vous que les quatrième et cinquième paramètres sont position surtout connue de la particule et son adéquation associée, afin que lors de l'initialisation d'une particule initial aléatoire position et adéquation sont les valeurs surtout connus.

Le code d'initialisation essaim se termine avec :

...
if (swarm[i].fitness < bestGlobalFitness) {
    bestGlobalFitness = swarm[i].fitness;
    swarm[i].position.CopyTo(bestGlobalPosition, 0);
  }
} // End initialization loop

Je vérifie si l'adéquation de la particule en cours est la meilleure (plus petit dans le cas d'un problème de minimisation) adéquation trouvée jusqu'à présent. Si tel est le cas, je mettre à jour bestGlobalPosition du tableau et le bestGlobalFitness de variable correspondante.

Ensuite, je vous préparer à entrer dans la boucle de traitement PSO principale :

double w = 0.729; // inertia weight
double c1 = 1.49445; // cognitive weight
double c2 = 1.49445; // social weight
double r1, r2; // randomizers

Je définis la valeur de l'ouest, la masse d'inertie, sur 0.729. Cette valeur a été recommandée par un document de recherche examiné les effets sur les différentes valeurs de paramètre PSO sur un ensemble de problèmes de minimisation de banc d'essai. Au lieu d'une valeur unique et constante pour w, une autre approche consiste à faire varier la valeur de w. Par exemple, si votre algorithme PSO est défini pour effectuer une itération de 10 000 fois, vous pourriez initialement la valeur w 0.90 et diminuer progressivement w pour 0,40 en réduisant w par 0.10 après chaque 2 000 itérations. L'idée d'un w dynamique est qu'au début de l'algorithme que vous souhaitez Explorer les modifications plus importantes en position, mais ultérieurement vous pouvez plus petits mouvements de particules. J'ai défini les valeurs pour les deux c1 et c2, les poids cognitives et sociales, à 1.49445. Là encore, cette valeur a été recommandée par une étude de recherche. Si vous définissez la valeur de c1 supérieure à la valeur de c2, vous favorisent de position surtout connue d'une particule que sur la position de notoriété globale de l'essaim et vice versa. Les variables aléatoires r1 et r2 ajouter un composant aléatoire à l'algorithme PSO et empêcher que l'algorithme bloqué à une solution non optimale locale minimale ou maximale.

Ensuite, je commence la boucle de traitement PSO principale :

for (int i = 0; i < swarm.Length; ++i) 
{
  Particle currP= swarm[i];
            
  for (int j = 0; j < currP.velocity.Length; ++j) 
  {
    r1 = ran.NextDouble();
    r2 = ran.NextDouble();

    newVelocity[j] = (w * currP.velocity[j]) +
      (c1 * r1* (currP.bestPosition[j] - currP.position[j])) +
      (c2 * r2 * (bestGlobalPosition[j] - currP.position[j]));
    ...

J'ai itérer sur chaque objet de particules dans le tableau de l'essaim à l'aide de i comme une variable d'index. Création d'une référence à l'objet en cours de particules nommé currP pour simplifier mon code, mais j'aurais pu utiliser essaim [i] directement. Comme expliqué dans la section précédente, la première étape consiste à mettre à jour de vecteur de vitesse de chaque particule. Pour l'objet en cours de la particule, j'ai guident tout au long de chacun d'eux des valeurs dans le tableau de vitesse de l'objet, générer des r2 et r1 variables aléatoires et ensuite mettre à jour de chaque composant de vitesse comme expliqué dans la section précédente.

Une fois que je calcule un nouveau composant de vitesse pour l'objet en cours de la particule, je vérifie si ce composant est entre les valeurs minimales et maximales pour un composant velocity :

if (newVelocity[j] < minV)
    newVelocity[j] = minV;
  else if (newVelocity[j] > maxV)
    newVelocity[j] = maxV;
} // each j
newVelocity.CopyTo(currP.velocity, 0);
...

Si le composant est hors limites, j'ai la mettre dans la plage. L'idée ici est que je ne veux pas les valeurs extrêmes pour le composant de vitesse dans la mesure où les valeurs extrêmes peuvent provoquer une mon nouveau poste de tourner en dehors des limites. Une fois toutes les composantes de vitesse ont été calculées, tableau de vitesse de l'objet de particules en cours à l'aide de la pratique mise à jour.Méthode CopyTo NET.

Une fois la vitesse de la particule en cours a été déterminée, je peux utiliser la nouvelle vitesse pour calculer et mettre à jour de la position de la particule en cours :

for (int j = 0; j < currP.position.Length; ++j)
{
  newPosition[j] = currP.position[j] + newVelocity[j];
  if (newPosition[j] < minX)
    newPosition[j] = minX;
  else if (newPosition[j] > maxX)
    newPosition[j] = maxX;
}
newPosition.CopyTo(currP.position, 0);
...

J'ai effectuez à nouveau un contrôle de plage, cette fois sur chacun des nouveaux composants de position de la particule en cours. Dans un sens, il s'agit d'une vérification redondante, car j'ai déjà contraint la valeur de chaque composant de vitesse, mais à mon avis la vérification supplémentaire s'impose ici.

Maintenant que j'ai la nouvelle position de l'objet de particules en cours, j'ai calculer la nouvelle valeur de l'adéquation et mettre à jour de champ d'adéquation de l'objet :

newFitness = ObjectiveFunction(newPosition);
    currP.fitness = newFitness;

    if (newFitness < currP.bestFitness) {
      newPosition.CopyTo(currP.bestPosition, 0);
      currP.bestFitness = newFitness;
    }
    if (newFitness < bestGlobalFitness) {
      newPosition.CopyTo(bestGlobalPosition, 0);
      bestGlobalFitness = newFitness;
    }

  } // each Particle
} // main PSO loop
...

Après la mise à jour de la particule en cours, je vérifie si la nouvelle position est la position surtout connue de la particule ; Je vérifie également si la nouvelle position est une meilleure position essaim global. Notez que logiquement, il peut y avoir une nouvelle position best globale uniquement s'il existe une meilleure position locale, afin que je pourrais avez imbriqué la vérification globale optimale à l'intérieur de la vérification pour un meilleur emplacement local.

À ce stade mon boucle d'algorithme PSO principale est terminée et je peux afficher mes résultats :

Console.WriteLine("\nProcessing complete");
    Console.Write("Final best fitness = ");
    Console.WriteLine(bestGlobalFitness.ToString("F4"));
    Console.WriteLine("Best position/solution:");
    for (int i = 0; i < bestGlobalPosition.Length; ++i){
      Console.Write("x" + i + " = " );
      Console.WriteLine(bestGlobalPosition[i].ToString("F4") + " ");
    }
    Console.WriteLine("");
    Console.WriteLine("\nEnd PSO demonstration\n");
  }
  catch (Exception ex)
  {
    Console.WriteLine("Fatal error: " + ex.Message);
  }
} // Main()

Extension et la modification

Maintenant que vous avez vu comment écrire une base PSO, examinons comment vous pouvez étendre et modifier le code que j'ai présentée. J'ai résolu le problème d'exemple est artificiel en ce sens qu'il est inutile d'utiliser PSO pour trouver une solution approximative, car le problème peut être résolu exactement. Où PSO est réellement utile est lorsque le problème numérique à l'étude est extrêmement difficile ou impossible à résoudre à l'aide des techniques standard. Prenez le problème suivant. Vous voulez prévoir le score d'un jeu de football (américain) entre les équipes a et b. Vous avez des données historiques consistant en les résultats précédents de a et b par rapport aux autres équipes. Vous modélisez mathématiquement l'indice historique d'une équipe x de telle sorte que si l'équipe gagne un jeu, monte d'évaluation de l'équipe par une valeur fixe (par exemple 16 points) et une autre valeur qui dépend de la différence entre les évaluations des équipes (par exemple, si l'équipe évaluation de x est inférieure à l'équipe adverse 0,04 fois, la différence). En outre, vous modéliser la marge prévue de la victoire d'une équipe comme une fonction de la différence entre les évaluations de l'équipe ; par exemple, si l'équipe x est classé 1,720 et l'équipe y est classé 1,620, votre modèle prévoit une marge de la victoire pour x de 3,5 points. En bref, vous avez une grande quantité de données et que vous devez déterminer plusieurs valeurs numériques (par exemple, le 16 et le 0,04) minimiser vos erreurs de prévision. Cette estimation contrôlées par les données de paramètre est le type de problème est droite haut alley du PSO.

PSO est simplement une des techniques de AI disponibles en fonction du comportement des systèmes naturels. La technique le plus proche des algorithmes PSO est sans doute des algorithmes génétiques (gaz). Ces deux techniques sont bien adaptés à des problèmes numériques difficiles. Gaz ont énormément été étudiées depuis des décennies. Un avantage de l'objet PSO gaz est que les algorithmes PSO sont beaucoup plus simples à implémenter que gaz. Il n'est pas clair pour l'instant si l'objet PSO n'est plus ou moins efficaces que les gaz ou à peu près égale.

La version du PSO que j'ai présentée ici peut être modifiée de différentes façons. Une simple modification particulièrement intéressante consiste à utiliser plusieurs sub-swarms de particules, et non un essaim global. With such a design, each particle belongs to a sub-swarm and the new velocity of a particle could depend on four terms rather than three: the old velocity, the particle’s best known position, the best known position of any particle in the sub-swarm, and the best known position of any particle. L'idée de cette conception sub-swarm consiste à réduire les risques de l'algorithme PSO bloqué dans une solution non optimale. À ma connaissance ce type de conception n'a pas encore été analysée soigneusement.

Dr. James McCaffrey travaille pour Volt Information Sciences Inc., où il gère la formation technique d'ingénieurs logiciels travaillant sur le Microsoft Redmond, Wash., campus. Il a collaboré à plusieurs produits Microsoft, comme Internet Explorer et MSN Search. Dr. McCaffrey est l'auteur de ".NET Test Automation Recipes » (Apress, 2006) et peut être contacté à jammc@microsoft.com.

Grâce aux experts techniques Microsoft suivants pour la révision de cet article : Paul Koch, Dan Liebling, Anne Loomis Thompson et Shane Williams