Algorithmes d'optimisation de la population : Recherche en Banc de Poisson - Fish School Search (FSS)

Sommaire

1. Introduction
2. Description de l'algorithme
3. Résultats des tests

1. Introduction

Une agrégation de poissons, ou regroupement de poissons, est le terme général pour toute collection de poissons qui se sont rassemblés dans un endroit donné. Les regroupements de poissons peuvent être structurés ou non. Une agrégation non structurée peut être un groupe d'espèces et de tailles diverses qui se sont rassemblées au hasard près d'une ressource locale, comme de la nourriture ou des sites de nidification.

Si l'agrégation se fait également de manière interactive et sociale, il s'agit alors d'un banc de poissons. La plupart d'entre eux se trouvent dans la même phase de leur cycle de vie, sont en contact actif les uns avec les autres et peuvent à tout moment présenter des activités biologiques actives et organisées utiles aux membres du groupe.
Contrairement à l'individu, le mode de vie grégaire est un compromis entre les avantages de la vie en groupe en termes de protection accrue contre les prédateurs et la concurrence accrue pour l'obtention de nourriture.

Dans la nature, les poissons forment des bancs de plusieurs façons. En règle générale, ils préfèrent les grands bancs, composés uniquement d'individus de leur propre espèce. Tout membre du banc qui se distingue par son apparence ou qui présente une différence quelconque devient une cible de choix pour les prédateurs. Ce fait explique pourquoi les poissons préfèrent les bancs d'individus identiques. L'homogénéité de l'ensemble du banc est ainsi assurée.

Un banc est organisé de manière assez rigide lorsque les poissons nagent de manière synchronisée, à la même vitesse et dans la même direction. Cela est dû au fait que les poissons de la même espèce, du même âge et de la même taille se déplacent à une certaine distance les uns des autres. Les bancs de poissons sont capables d'effectuer des manœuvres complexes, comme s'ils étaient dotés d'une intelligence de groupe et d'un esprit commun.
Les subtilités de la formation en banc sont loin d'être comprises, en particulier les aspects liés au mouvement et aux modes d'alimentation.

De nombreuses hypothèses ont été avancées pour expliquer le comportement grégaire, notamment une meilleure orientation, la synchronisation de la chasse, la confusion des prédateurs et la réduction du risque d'être capturé. Les poissons en bancs semblent partager des informations contrôlant le comportement des autres à une distance rapprochée. Le comportement alimentaire d'un poisson stimule rapidement la recherche active de nourriture chez les autres. Les poissons en bancs nagent en files minces, effectuant souvent des montées et des descentes rapides et tournant autour de leur axe, tout en changeant la forme du banc en évitant les collisions les uns avec les autres. De telles manœuvres nécessitent un système de réponse très rapide. Le mode de vie en bancs implique que les poissons disposent de systèmes sensoriels capables de réagir instantanément à de petits changements dans leur position par rapport à leurs voisins.

Pour obtenir une image plus complète, la modélisation mathématique de ce comportement est utilisée. Les modèles mathématiques les plus courants supposent que les animaux individuels d'un banc suivent 3 règles de base :

1. Se déplacer dans la même direction que son voisin
2. Rester proche de ses voisins
3. Éviter les collisions avec les individus voisins

La question de savoir comment les poissons en bancs choisissent la direction dans laquelle ils nagent n'a pas encore été résolue. Lors des migrations, il semble que la plupart des membres du banc savent où aller. Si tous les membres d'un banc sont également conscients de la disponibilité de la nourriture, il y a toujours certains leaders plus audacieux que les autres membres du groupe. Ce comportement en banc a incité de nombreux chercheurs à créer non seulement un modèle mathématique, mais aussi un modèle algorithmique pour résoudre divers problèmes d'optimisation.

2. Description de l'algorithme

La recherche en banc de poissons (FSS) est une sous-famille d'algorithmes d'intelligence en essaim appartenant à la classe des algorithmes méta-heuristiques. Il a été proposé par Bastos Filho et Lima Neto en 2008 et a été publié pour la première fois en 2009. Dans le FSS, les agents simples sont appelés des poissons. Chaque poisson a un poids qui représente le "succès" obtenu au cours de la recherche. Les valeurs et les variations des poids affectent les mouvements individuels et collectifs. Des mécanismes intégrés d'alimentation et d'action coordonnée obligent le banc à se déplacer dans le sens d'un gradient positif pour prendre du poids et trouver les meilleurs endroits au niveau local et mondial. L’algorithme FSS a été développé pour les problèmes d'optimisation continue dans des espaces de recherche multimodaux. Cela a également incité d'autres chercheurs à proposer des options pour résoudre d'autres problèmes, tels que l'optimisation dans les problèmes binaires et l'optimisation multi-objectifs.

Dans l'algorithme FSS, on peut simplifier en imaginant que des poissons nagent dans un aquarium conditionnel dont les parois sont les limites du domaine de la définition de la fonction étudiée. Le poids du poisson est une mesure du succès dans la recherche de nourriture (solutions). Il joue également le rôle de mémoire du poisson. La présence d'un poids est l'idée principale de l'algorithme et la différence avec un essaim de particules. Cette caractéristique de l'algorithme FSS élimine la nécessité de trouver et de fixer les meilleures solutions globales, comme c'est le cas avec un essaim de particules.

Les opérateurs de l'algorithme FSS sont divisés en 2 groupes :
- l'opérateur d'alimentation formalise le succès de l'exploration de la zone
- les opérateurs de natation mettent en œuvre des algorithmes de migration pour les poissons individuels et le banc dans son ensemble

L'opérateur d'alimentation calcule le poids du poisson. L'idée de base est d'amener le poisson à "nager" vers un gradient positif afin de "manger" et de "prendre du poids". Collectivement, les poissons les plus lourds ont un effet plus important sur le processus de recherche global, ce qui fait que le centre de la masse du banc de poissons se déplace vers de meilleurs emplacements dans l'espace de recherche au fil des itérations. L'augmentation du poids à une itération donnée est proportionnelle à la différence normalisée des valeurs de la fonction d'aptitude :

poissons [f].poids = poissons [f].poids + (poissons [f].delta_fitness / max_delta_fitness) ;

avec :

• poids - poids du poisson
• delta_fitness - différence entre les valeurs de la fonction fitness
  
• max_delta_fitness - valeur maximale de la différence entre les fonctions de fitness de tous les poissons

Les opérateurs flottants sont divisés en 3 types selon le type de mouvement :

- individuelle

- instinctif-collectif

- collectif-volontaire

La nage individuelle peut être interprétée comme une recherche locale dans les environs de la position actuelle du poisson. Le vecteur de mouvement de chaque individu est dirigé de manière aléatoire et a une valeur différente.

poissons [f].new_position [d] = poissons [f].current_position [d] + step_ind [d] * r ;

avec :

• new_position - nouvelle position à la coordonnée correspondante
• current_position - position actuelle sur la coordonnée correspondante
• step_ind - pas de déplacement individuel calculé comme suit :

initial_step_ind * (rangeMax[d] - rangeMin[d]);

avec :

• initial_step_ind - paramètre de l'algorithme pour le mouvement individuel
• rangeMax et rangeMin - plages de valeurs optimisées pour les arguments
  
• r - nombre aléatoire [-1,0 ; 1,0]

Le schéma du mouvement individuel est présenté dans la figure 1.

Fig. 1. Mouvement individuel. Le vecteur de mouvement de chaque poisson est orienté dans une direction aléatoire et a une valeur scalaire différente.

Après le mouvement individuel, la fonction d'aptitude est mesurée. Si la position du poisson ne s'est pas améliorée, nous considérons que ce poisson n'a pas bougé et qu'il reste en place. Seuls les poissons qui ont amélioré leurs fonctions d'aptitude se déplacent vers une nouvelle position.

Après l'exécution de la nage individuelle, l'opérateur du mouvement instinctif-collectif est exécuté. Examinons d'abord la figure 2.

Fig. 2. Nage instinctive-collective Le mouvement est caractérisé pour tous les poissons par le même vecteur de direction et de grandeur par rapport au centre de masse G.

Le mouvement collectif instinctif sert à corriger la position générale du banc de poissons en tenant compte de l'évolution de la fonction d'aptitude de chaque poisson à l'itération précédente. Les nouvelles coordonnées sont calculées comme suit :

poissons [f].new_position [d] = poissons [f].current_position [d] + instinct_collectif [d] ;

avec :

• new_position - nouvelle position du poisson à la coordonnée correspondante
• current_position - position actuelle sur la coordonnée correspondante
• instinct_collectif - quantité de mouvement le long de la coordonnée correspondante, calculée comme suit :

instinct_collectif [d] = poissons [f].delta_position [d] * poissons [f].delta_fitness ;

avec :

• delta_position - différence entre les coordonnées de la position actuelle et de la position précédente obtenue au stade de la nage individuelle
• delta_fitness - changement des fonctions de fitness de la position actuelle et de la position précédente pendant la nage individuelle

La nage instinctive-collective formalise le déplacement synchrone d'un banc de poissons vers un nouvel endroit, à la recherche de nouvelles sources de nourriture, et le déplacement individuel permet d'améliorer la situation au niveau local.

Considérons maintenant la natation collective-volontaire. Elle est divisée en 2 types :

- depuis le centre de la masse : si l'amélioration de la position du banc dans son ensemble n'a pas eu lieu par rapport à la position précédente, alors que le poisson s'est répandu sur les côtés, symbolisant une nouvelle recherche de nourriture (figure 3).

- mouvement vers le centre de masse si l'amélioration s'est produite. Les poissons se déplacent ensuite vers le centre de la masse, resserrant l'anneau et symbolisant l'attaque de la proie. D'un point de vue algorithmique, il s'agit d'affiner la solution du problème d'optimisation (figure 4).

Fig. 3 : Nage collective-volontaire. Les vecteurs de direction sont dirigés à partir du centre de masse G

Fig. 4 : Nage collective-volontaire. Les vecteurs de direction sont dirigés vers le centre de masse G

Le concept de centre de masse est introduit pour le calcul de la natation collective-volontaire. À partir de là, l'équation de la natation collective-volontaire se présente comme suit :

poissons [f].new_position [d] = pos + (((pos - barycentre [d]) * step_vol [d] * r) * search_operator) ;

avec :

• pos est la même que current_position
• search_operator : 1 si le coup précédent a permis d'améliorer la position, et -1 si ce n'est pas le cas
  
• 
  
• step_vol [d] - le pas de mouvement collectif, calculé comme suit :

step_vol [d] = initial_step_vol * (rangeMax [d] - rangeMin [d]) ;

avec :

• initial_step_vol - paramètre de l'algorithme pour le mouvement collectif
• 
  
• barycentre [d] - centre de masse calculé comme étant la somme des poids des poissons multipliée par la coordonnée :

barycentre [d] += poissons [f].poids * poissons [f].position_actuelle [d] ;

et divisé par le poids total du banc de poissons :

barycentre [d] /= poids_total_actuel ;

Le pseudo-code de l'algorithme se présente comme suit :

1) initialisation des positions des poissons avec des nombres aléatoires

2) mouvements individuels

3) calcul de la fonction d'aptitude

4) redéfinition des poids pour chaque poisson

5) mouvement instinctif-collectif

6) mouvement collectif-volontaire

7) recalcul du le poids total

8) calcul de la fonction d'aptitude

9) répétition de l'opération à partir de l'étape 2) jusqu'à ce que le critère d'arrêt soit rempli

Fig. 5 : Schéma fonctionnel de l'algorithme FSS

Commençons par décrire le code.

Comme vous pouvez le deviner, l'unité logique la plus simple de l'algorithme est la structure qui décrit le poisson. Comme nous devrons initialiser le poisson plusieurs fois, il est conseillé de "mettre à zéro" cette structure en raison de sa taille relativement importante dans la méthode Init(), ce qui nous permettra d'optimiser légèrement le code. La structure comprend les tableaux de coordonnées de la position actuelle, de la nouvelle position et de la différence de coordonnées depuis le dernier déplacement. Le poids par défaut, égal à 1000 unités standard, peut avoir n'importe quelle valeur. Le poisson est également caractérisé par la valeur de la fonction d'aptitude actuelle, la précédente et leur différence entre elles. Dans la méthode Init(), la fonction d'aptitude est initialisée avec la valeur "double" minimale possible. La différence de fitness est donc nulle, puisque le poisson n'a pas encore bougé.

//——————————————————————————————————————————————————————————————————————————————
struct S_Fish
{
  void Init (int dimensions)
  {
    ArrayResize (current_position, dimensions);
    ArrayResize (new_position,     dimensions);
    ArrayResize (delta_position,   dimensions);
    weight        = 1000.0;
    fitness       = -DBL_MAX;
    delta_fitness = 0.0;
  }

  double current_position [];
  double new_position     [];
  double delta_position   [];
  double weight;
  double fitness;
  double new_fitness;
  double delta_fitness;
};
//——————————————————————————————————————————————————————————————————————————————

Déclarons la classe C_AO_FSS - un banc de poissons représentant mathématiquement le modèle de communauté naturelle. Il n'y a rien d'inhabituel à cela. Il existe également 2 méthodes publiques requises pour l'interaction avec le programme utilisateur : les plages de valeurs de la fonction optimisée nécessaires pour prendre en compte les coordonnées des poissons et l'interaction dans un banc, ainsi que les tableaux.

Dans la méthode publique de la classe d'initialisation Init(), il est nécessaire de remettre les variables à leur valeur d'origine et d'allouer de la mémoire aux tableaux. Accordez une attention particulière aux variables init et swimmingRegime. Selon le pseudo-code que nous avons vu, le calcul de la fonction d'aptitude est effectué 2 fois : la première fois après un mouvement individuel, la deuxième fois après deux types de mouvements collectifs. Ceci est en contradiction avec le schéma de liaison algorithme-application que nous avons adopté, qui stipule que chaque itération présente une séquence : première_méthode -> calcul_fonctions_fitness -> deuxième_méthode. Ces 2 variables sont appliquées afin de résoudre ce problème et de modifier la séquence d'actions dans l'algorithme canonique. La variable init doit être "false" au début de l'algorithme. Il s'agit d'un drapeau indiquant la nécessité d'initialiser le poisson, de calculer la fonction d'aptitude et de refaire le mouvement, puisque toute la logique de l'algorithme utilise la différence entre la valeur actuelle et la valeur précédente des coordonnées, ainsi que la fonction d'aptitude. Sans cela, nous n'aurions pas pu obtenir la différence de valeur. Le deuxième drapeau important est celui de la natation. Il nous permet de redéfinir l'ordre d'appel des méthodes qui décrivent le mouvement des poissons afin qu'il corresponde à notre structure. La valeur 1 correspond à l'appel de la natation "individuelle", sinon nous utilisons la séquence de mouvements de groupe que nous avons considérée plus haut.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Init (const int    dimensionsP,
                     const int    fishSchSizeP,
                     const double initial_step_indP,
                     const double initial_step_volP)
{
  MathSrand (GetTickCount ());
  init = false;
  swimmingRegime = 1;

  dimensions     = dimensionsP;

  ArrayResize (rangeMax,  dimensions);
  ArrayResize (rangeMin,  dimensions);
  ArrayResize (rangeStep, dimensions);

  num_of_individuos = fishSchSizeP;

  ArrayResize (fishes, num_of_individuos);

  for (int i = 0; i < num_of_individuos; i++)
  {
    fishes [i].Init (dimensions);
  }

  global_best = -DBL_MAX;
  ArrayResize (global_best_position, dimensions);

  total_weight     = num_of_individuos;

  initial_step_ind = initial_step_indP;
  ArrayResize (step_ind, dimensions);

  initial_step_vol = initial_step_volP;
  ArrayResize (step_vol, dimensions);

  ArrayResize (collective_instinct, dimensions);
  ArrayResize (barycenter, dimensions);
}
//——————————————————————————————————————————————————————————————————————————————

La première méthode publique appelée dans chaque itération Swimming() détermine la séquence des appels aux mouvements de poissons individuels et collectifs. Si la méthode est appelée pour la première fois, les pas de déplacement individuels et collectifs sont initialisés comme faisant partie de l'intervalle possible le long de la coordonnée correspondante au moyen des deux paramètres d'algorithme initial_step_ind et initial_step_vol. Certains auteurs recommandent de fixer ces valeurs à 0,01 et 0,001 respectivement. Cependant, je n'ai pas obtenu de bons résultats avec ces valeurs. J'utilise donc 0,1 et 0,8. Aussi, lors de la première exécution de l'algorithme, la valeur actuelle des coordonnées de la position du poisson est initialisée avec des nombres aléatoires dans la gamme des paramètres optimisés. Les types de mouvement appropriés seront appelés lors des appels de méthode ultérieurs conformément à l'indicateur swimmingRegime.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Swimming (int i)
{
  //----------------------------------------------------------------------------
  if (!init)
  {
    global_best    = -DBL_MAX;
    swimmingRegime = 1;

    for (int d = 0; d < dimensions; d++)
    {
      step_ind [d] = initial_step_ind * (rangeMax [d] - rangeMin [d]);
      step_vol [d] = initial_step_vol * (rangeMax [d] - rangeMin [d]);
    }

    for (int f = 0; f < num_of_individuos; f++)
    {
      fishes [f].Init (dimensions);

      for (int d = 0; d < dimensions; d++)
      {
        fishes [f].new_position [d] = RNDfromCI (rangeMin [d], rangeMax [d]);
        fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
      }
    }
  }
  //----------------------------------------------------------------------------
  else
  {
    switch (swimmingRegime)
    {
    case 1:
      apply_individual_movement ();            //individual movement
      break;
    default:
      apply_instintive_collective_movement (); //instinctively-collective movement
      apply_collective_volitive_movement ();   //collective-volitional movement
      update_total_weight ();                  //recalculate the total weight
      break;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

La deuxième méthode publique appelée à chaque itération Regrouping() est destinée principalement à déterminer l'ordre d'appel des méthodes de nage - individuelle, collective-instinctive, collective-volontaire. Une fonctionnalité supplémentaire de la méthode permettant de garantir l'ordre des appels est fournie par l'indicateur swimmingRegime, qui prend les valeurs 1 et 2. Il est nécessaire de redéfinir l'ordre d'appel des méthodes de déplacement des poissons dans la version classique pour la structure que j'ai adoptée : first_open_method -> _fitness_function_calculation -> second_open_method. En fonction du drapeau Init, si l'algorithme en est à la première itération, nous stockons la position actuelle des coordonnées et la valeur de la fonction d'aptitude pour le calcul ultérieur de leurs différences, puisqu'il est supposé que la méthode est appelée après le calcul de la fonction d'aptitude. Si le drapeau Init indique que l'algorithme en est à la deuxième itération et aux itérations suivantes, il est nécessaire, après un mouvement individuel, d'obtenir la différence entre la valeur actuelle et la valeur précédente de la fonction d'aptitude, ainsi que la différence entre les coordonnées de la position actuelle et de la position précédente. Les différences sont calculées à condition que la position se soit améliorée. Sinon nous considérons qu'il n'y a pas eu de mouvement. Nous remettons donc les valeurs du poids des poissons à l'état initial, et les différences dans les mouvements et les fonctions d'aptitude sont considérées comme égales à zéro. Nous mettons immédiatement à jour la meilleure solution si elle est atteinte, en appelant la méthode updates_optimal_solution(), et nous appliquons l'alimentation des poissons avec la méthode apply_feeding(). Si l'indicateur swimmingRegime n'est pas égal à 1, des mouvements collectifs-instinctifs et collectifs-volontaires ont été appliqués. Après leur exécution, réglez swimmingRegime sur 1. Un mouvement individuel suivra.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Regrouping ()
{
  //----------------------------------------------------------------------------
  if (swimmingRegime == 1
  {
    if (!init)
    {
      for (int f = 0; f < num_of_individuos; f++)
      {
        ArrayCopy (fishes [f].current_position, fishes [f].new_position, 0, 0, WHOLE_ARRAY);
        ArrayInitialize (fishes [f].delta_position, 0.0);

        fishes [f].fitness = fishes [f].new_fitness;
        fishes [f].delta_fitness = 0.0;
      }

      init = true;
      return;
    }

    for (int f = 0; f < num_of_individuos; f++)
    {
      //remember the best position for the fish
      if (fishes [f].new_fitness > fishes [f].fitness)
      {
        fishes [f].delta_fitness = fishes [f].new_fitness - fishes [f].fitness; //fabs
        fishes [f].fitness = fishes [f].new_fitness;

        for (int d = 0; d < dimensions; d++)
        {
          fishes [f].delta_position [d] = fishes [f].new_position [d] - fishes [f].current_position [d];
        }

        ArrayCopy (fishes [f].current_position, fishes [f].new_position, 0, 0, WHOLE_ARRAY);
      }
      else
      {
        ArrayInitialize (fishes [f].delta_position, 0.0);
        fishes [f].delta_fitness = 0.0;
      }
    }

    swimmingRegime = 2;
    updates_optimal_solution ();
    apply_feeding ();
    return;
  }

  //----------------------------------------------------------------------------
  swimmingRegime = 1;
  updates_optimal_solution ();
}
//——————————————————————————————————————————————————————————————————————————————

La méthode privée simple suivante est utilisée pour mettre à jour les meilleurs résultats de l'algorithme s'ils sont atteints. Pour ce faire, nous comparons simplement les valeurs de la fonction d'aptitude de chaque poisson avec les valeurs globales. S'ils sont meilleurs, il faut les conserver :

//——————————————————————————————————————————————————————————————————————————————
// update the best overall solution
void C_AO_FSS::updates_optimal_solution ()
{
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (fishes [f].fitness > global_best)
    {
      global_best = fishes [f].fitness;
      ArrayCopy (global_best_position, fishes [f].current_position, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Nous avons déjà examiné ci-dessus l'équation de la méthode privée qui fournit une natation individuelle. Tout est donc simple : nous ajoutons un pas individuel multiplié par un nombre aléatoire compris entre -1,0 et 1,0 aux coordonnées actuelles de chaque poisson, ce qui donne un incrément à la fois dans les directions positives et négatives. Si les valeurs des paramètres optimisés dépassent la plage, la valeur limite est fixée pour la coordonnée.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_individual_movement ()
{
  // move the fish to new places-----------------------------------------------
  double r = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      r = RNDfromCI (-1.0, 1.0);

      fishes [f].new_position [d] = fishes [f].current_position [d] + step_ind [d] * r;
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

La méthode d'alimentation ne doit pas entraîner de difficultés de compréhension. Le poids du poisson est en fait déterminé comme le quotient de la différence de la fonction d'aptitude du poisson lui-même et de la valeur maximale de la différence parmi l'ensemble du banc de poissons. Mais il peut arriver que la différence maximale entre tous les poissons soit égale à zéro. La description de la version classique de l'algorithme indique que le poids des poissons doit toujours être positif. En général, seuls les cas où la fonction d'aptitude prend des valeurs positives sont pris en compte, mais je n'ai pas trouvé de sens pratique à cette exigence. J'admets que le poids des poissons peut prendre des valeurs négatives, donc si la différence maximale de la fonction d'aptitude (c'est la valeur à laquelle nous devons normaliser le poids de chaque poisson) est nulle parmi tous les poissons, alors le poids du poisson est considéré comme étant égal à 1.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_feeding ()
{
  double max_delta_fitness = -DBL_MAX;

  //find the maximum weight among fish
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (fishes [f].delta_fitness > max_delta_fitness) max_delta_fitness = fishes [f].delta_fitness;
  }

  //feed the fish
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (max_delta_fitness != 0.0)
    {
      fishes [f].weight = fishes [f].weight + (fishes [f].delta_fitness / max_delta_fitness);
    }
    else fishes [f].weight = 1;
  }
}
//——————————————————————————————————————————————————————————————————————————————

La méthode privée de déplacement instinctif-collectif consiste à modifier les coordonnées de chaque poisson en les incrémentant de la valeur de l'instinct collectif (qui n'est rien d'autre que le produit de la différence des positions sur l'itération en cours et les itérations précédentes par la différence de la fonction d'aptitude obtenue sur les mouvements précédents). Nous attribuons ici les valeurs des limites lorsque nous dépassons les limites des paramètres optimisés :

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_instintive_collective_movement ()
{
  double sum_delta_fitness = 0.0;
  for (int f = 0; f < num_of_individuos; f++)
  {
    sum_delta_fitness += fishes [f].delta_fitness;
  }

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      collective_instinct [d] = fishes [f].delta_position [d] * fishes [f].delta_fitness;

      if (sum_delta_fitness != 0.0)
      {
        collective_instinct [d] /= sum_delta_fitness;
      }

      fishes [f].new_position [d] = fishes [f].current_position [d] + collective_instinct [d];
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

La méthode privée de nage collective-volontaire, dans laquelle le centre de masse d'un banc de poissons, ainsi que le poids total actuel, sont calculés. Si le poids total du banc a augmenté, les poissons commencent à se rapprocher du centre de la masse, sinon ils s'en éloignent. L'équation a été examinée en détail précédemment. Le poids total d'un banc de poissons est mis à jour selon une méthode spéciale décrite ci-dessous :

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_collective_volitive_movement ()
{
  //----------------------------------------------------------------------------
  double current_total_weight = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    current_total_weight += fishes [f].weight;
  }

  ArrayInitialize (barycenter, 0.0);

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      barycenter [d] += fishes [f].weight * fishes [f].current_position [d];
    }
  }

  for (int d = 0; d < dimensions; d++)
  {
    barycenter [d] /= current_total_weight;
  }

  //----------------------------------------------------------------------------
  double search_operator = current_total_weight > total_weight ? 1.0 : -1.0;
  double r   = 0.0;
  double pos = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      r = RNDfromCI (0.0, 1.0);
      pos = fishes [f].current_position [d];

      fishes [f].new_position [d] = pos + (((pos - barycenter [d]) * step_vol [d] * r) * search_operator);
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Il s'agit en fait de la méthode même de mise à jour du poids total des poissons. Tout est simple ici. Nous prenons le poids de chaque poisson et faisons la somme :

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::update_total_weight ()
{
  total_weight = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    total_weight += fishes [f].weight;
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Résultats des tests

Passons maintenant à la dernière partie, la plus intéressante : les résultats. L'algorithme contient des astuces intéressantes, telles que l'absence de nécessité de prendre en compte l'optimum global, l'introduction des concepts de centre de masse et de mouvement instinctif-volontaire, impliquant une convergence ou une dispersion à partir du centre du banc, selon que la position dans son ensemble a été améliorée ou non. Tout ceci laissait espérer un comportement original de l'algorithme sur les fonctions étudiées.

En général, le comportement dans la zone de recherche de l'espace est original, à savoir qu'il y a des dispersions de poissons dans des parties distinctes de l'espace similaires à ce qui a été observé dans l'algorithme de l'abeille, bien qu'un examen détaillé des équations et du principe de fonctionnement du FSS n'implique pas la dispersion du banc en groupes distincts. L'algorithme a donné en général des résultats médiocres, ne dépassant que légèrement l'algorithme PSO en termes de résultat global.

Si l'on considère les tests individuels, le FSS a tout de même réussi à exceller dans certains d'entre eux. En particulier, pour la fonction lisse Skin, l'algorithme FSS s'est avéré meilleur que l'algorithme du loup, montrant de bons résultats (mais pas les meilleurs), ce qui est facile à expliquer. L'algorithme utilise le gradient de la surface de la fonction étudiée, considéré par incréments pour chacune des coordonnées, et la variation de la fonction de fitness à chaque itération. La fonction Skin étant lisse, l'algorithme "s'accroche" bien aux changements de surface.

En ce qui concerne la fonction Forest, l'algorithme a obtenu des résultats inférieurs à la moyenne. Les modifications douces de la fonction de test ont, dans une certaine mesure, aidé l'algorithme à naviguer dans l'espace, mais il n'a pas pu trouver le maximum global. Si l'on considère Megacity, les lacunes du FSS deviennent encore plus évidentes. L'algorithme n'aime vraiment pas lorsque la fonction étudiée ne change pas à proximité de la position actuelle des agents individuels. Et l'algorithme n'est pas en mesure d'effectuer de longs sauts pour identifier de nouveaux endroits potentiellement meilleurs. Par conséquent, il reste bloqué dans tous les extrema locaux qui n'ont pas d'incrément à proximité.

Bien que le test Megacity soit très difficile pour tous les algorithmes d'optimisation et que les autres participants au tableau de comparaison ne soient pas beaucoup plus avancés que FSS en général, il est toujours nécessaire de reconnaître les faibles capacités de l'algorithme sur les problèmes discrets. Dans certains tests, la recherche aléatoire a donné le meilleur résultat. Comme on peut le voir dans l'animation, aucun "regroupement" ne peut être observé dans le fonctionnement de l'algorithme. Vous vous souvenez peut-être de l'algorithme d'optimisation "cristallisation" décrit dans l'article précédent.

Résultats de l'algorithme FSS :

2022.12.08 13:14:06.033 Test_AO_FSS (EURUSD,M1) =============================
2022.12.08 13:14:08.388 Test_AO_FSS (EURUSD,M1) 1 Skin ; Func runs 10000 result : 4,892861444841324
2022.12.08 13:14:08.388 Test_AO_FSS (EURUSD,M1) Score : 0,99391
2022.12.08 13:14:12.557 Test_AO_FSS (EURUSD,M1) 20 Skin ; Func runs 10000 result : 3,11410005347766
2022.12.08 13:14:12.557 Test_AO_FSS (EURUSD,M1) Score : 0,56920
2022.12.08 13:14:47.176 Test_AO_FSS (EURUSD,M1) 500 Skin ; Func runs 10000 result : 1,20519552002827
2022.12.08 13:14:47.176 Test_AO_FSS (EURUSD,M1) Score : 0,11341
2022.12.08 13:14:47.176 Test_AO_FSS (EURUSD,M1) =============================
2022.12.08 13:14:49.498 Test_AO_FSS (EURUSD,M1) 1 Forest ; Func runs 10000 result : 1,5057381856551146
2022.12.08 13:14:49.498 Test_AO_FSS (EURUSD,M1) Score : 0,85172
2022.12.08 13:14:53.825 Test_AO_FSS (EURUSD,M1) 20 Forest ; Func runs 10000 result : 0,21468156279781656
2022.12.08 13:14:53.825 Test_AO_FSS (EURUSD,M1) Score : 0,12143
2022.12.08 13:15:31.235 Test_AO_FSS (EURUSD,M1) 500 Forest ; Func runs 10000 result : 0,056970068652984526
2022.12.08 13:15:31.235 Test_AO_FSS (EURUSD,M1) Score : 0,03223
2022.12.08 13:15:31.235 Test_AO_FSS (EURUSD,M1) =============================
2022.12.08 13:15:34.066 Test_AO_FSS (EURUSD,M1) 1 Megacity ; Func runs 10000 result : 11,0
2022.12.08 13:15:34.066 Test_AO_FSS (EURUSD,M1) Score : 0,91667
2022.12.08 13:15:38.467 Test_AO_FSS (EURUSD,M1) 20 Megacity ; Func runs 10000 result : 1,03
2022.12.08 13:15:38.467 Test_AO_FSS (EURUSD,M1) Score : 0,08583
2022.12.08 13:16:16.589 Test_AO_FSS (EURUSD,M1) 500 Megacity ; Func runs 10000 result : 0,31
2022.12.08 13:16:16.589 Test_AO_FSS (EURUSD,M1) Score : 0,02583
2022.12.08 13:16:16.589 Test_AO_FSS (EURUSD,M1) =============================
2022.12.08 13:16:16.589 Test_AO_FSS (EURUSD,M1) Tous les scores pour C_AO_FSS : 0,4122477188979048

  FSS sur la fonction de test Skin

  FSS sur la fonction de test Forest

  FSS sur la fonction de test Megacity

Voici le tableau final. Il comporte des colonnes supplémentaires pour faciliter l'évaluation des algorithmes pour chaque fonction de test séparément, ce qui nous permet de débattre plus équitablement de l'applicabilité de chaque algorithme à certaines tâches.

AO	Description	Skin			Skin final	Forest			Forest final	Megacity (discrète)			Megacity final	Résultat final
		2 paramètres (1 F)	40 paramètres (20 F)	1.000 paramètres (500 F)		2 paramètres (1 F)	40 paramètres (20 F)	1.000 paramètres (500 F)		2 paramètres (1 F)	40 paramètres (20 F)	1.000 paramètres (500 F)
COAm	algorithme d'optimisation du coucou	1,00000	0,85911	0,14316	0,66742	0,99283	0,28787	0,04551	0,44207	1,00000	0,24917	0,03537	0,42818	0,51255778
ACOm	optimisation par colonies de fourmis	0,98229	0,79108	0,12602	0,63313	1,00000	0,62077	0,11521	0,57866	0,38333	0,44000	0,02377	0,28237	0,49805222
ABCm	colonie d'abeilles artificielle M	1,00000	0,63922	0,08076	0,57333	0,99908	0,20112	0,03785	0,41268	1,00000	0,16333	0,02823	0,39719	0,46106556
ABC	colonie d'abeilles artificielles	0,99339	0,73381	0,11118	0,61279	0,99934	0,21437	0,04215	0,41862	0,85000	0,16833	0,03130	0,34988	0,46043000
GWO	optimiseur du loup gris	0,99900	0,48033	0,18924	0,55619	0,83844	0,08755	0,02555	0,31718	1,00000	0,10000	0,02187	0,37396	0,41577556
FSS	recherche d'un banc de poissons	0,99391	0,5692	0,11341	0,55884	0,85172	0,12143	0,03223	0,33513	0,91667	0,08583	0,02583	0,34278	0,41224778
PSO	optimisation par essaims de particules	0,99627	0,38080	0,05089	0,47599	0,93772	0,14540	0,04856	0,37723	1,00000	0,09333	0,02233	0,37189	0,40836667
RND	aléatoire	0,99932	0,44276	0,06827	0,50345	0,83126	0,11524	0,03048	0,32566	0,83333	0,09000	0,02403	0,31579	0,38163222

Les méthodes heuristiques stochastiques (randomisées) ne garantissent pas une solution précise, mais elles permettent en général de trouver des solutions suffisamment proches pour une utilisation pratique dans un délai acceptable. Toutefois, la pratique montre que certains algorithmes sont capables de démontrer d'excellentes capacités de convergence, ce qui n'est pas le cas du FSS. L'algorithme de recherche d'un banc de poissons est un cas particulier d'algorithmes basés sur un essaim de particules. Il a donc hérité à la fois d'avantages et d'inconvénients. Les caractéristiques uniques de l'algorithme comprennent la division d'un banc de poissons (essaim) en groupes distincts, ce qui n'est pas observé dans l'essaim de particules. L'algorithme s'adapte relativement bien aux fonctions lisses, bien qu'il ne soit pas certain que FSS s'adapte bien aux fonctions à variables multiples.

Avantages :
1. L'algorithme traite assez bien les fonctions lisses.
2. La capacité d'un banc de poissons à être divisé en groupes distincts, qui permet à l'algorithme d'explorer plus avant d'autres extrêmes locaux potentiellement bons.

Inconvénients :
1. Une grande dispersion des résultats dans les tests individuels indique l'instabilité de l'algorithme.
2. Convergence très faible sur les fonctions discrètes et sur les fonctions avec ruptures. Ceci n'est pratiquement pas applicable aux fonctions discrètes.
3. Faible évolutivité.