Algorithmes d'optimisation de la population : Algorithme d'Optimisation du Coucou - Cuckoo Optimization Algorithm (COA)

Sommaire

1. Introduction
2. Description de l'algorithme, arbre de décision et vol Levy
3. Code COA
4. Résultats des test

1. Introduction

Le coucou est un oiseau fascinant, non seulement à cause de son chant, mais aussi à cause de sa stratégie de reproduction agressive, qui consiste à pondre des œufs dans les nids d'autres oiseaux. L'oiseau transfère ainsi complètement ses responsabilités parentales à d'autres espèces. Chaque espèce de coucou pond des œufs d'une certaine couleur et d’une certaine taille afin de correspondre au mieux aux œufs des divers parents nourriciers. Les poussins de coucou jetés dans les nids d'autres oiseaux sont généralement plus gros et plus forts que les poussins des propriétaires du nid, de sorte que les coucous ont besoin de plus de nourriture. Au cours du développement, les poussins coucous de Hodgson développent un motif spécial sur leurs ailes sous la forme d'un bec ouvert, ce qui leur permet de recevoir plus de nourriture des parents adoptifs. Le coucou n'est pas le seul oiseau présentant ce type de trait. Le parasitisme de nidification a été trouvé chez au moins 80 espèces d'oiseaux. Ce phénomène est répandu chez certaines espèces d'insectes sociaux (bourdons, abeilles et fourmis) dont les femelles pénètrent dans une autre colonie, tuent la reine et pondent leurs œufs. Le parasitisme de nidification existe également chez certains poissons, comme le poisson-chat du lac Tanganyika en Afrique. Ils jettent leurs œufs à d'autres poissons incubant des œufs dans leur bouche.

La recherche de coucou est l'un des derniers algorithmes heuristiques inspirés de la nature développés par Yang et Deb en 2009. Il est basé sur le parasitisme de certaines espèces de coucous. Cet algorithme a été encore amélioré par des vols dits Levy plutôt que par de simples méthodes de marche aléatoire isotrope.

2. Description de l'algorithme

L'Algorithme d'Optimisation du Coucou (COA) est utilisé pour l'optimisation non linéaire continue. Le COA s'inspire du mode de vie de cet oiseau. L'algorithme d'optimisation est basé sur les caractéristiques de ponte et de reproduction de l'espèce. Comme d'autres approches évolutives, le COA commence par une population initiale. La base de l'algorithme est une tentative de survie. Alors qu'ils rivalisent pour survivre, certains oiseaux meurent. Les coucous survivants se déplacent vers de meilleurs endroits et commencent à se reproduire et à pondre des œufs. Les coucous survivants convergent ensuite de telle sorte qu'une société de coucous avec des valeurs de fitness similaires est obtenue.
Le principal avantage de cette méthode est sa simplicité : la recherche du coucou ne nécessite que 4 paramètres compréhensibles, donc le réglage devient une évidence.

Dans l'algorithme de recherche du coucou, les œufs dans le nid sont interprétés comme des solutions possibles au problème d'optimisation, et l'œuf de coucou représente la nouvelle solution. Le but ultime de la méthode est d'utiliser ces nouvelles (et potentiellement meilleures) solutions d'œufs de coucou parasites pour remplacer la solution actuelle d'œufs du nid. Ce remplacement, effectué de manière itérative, conduit finalement à une solution.

Les professeurs Yang et Deb ont proposé les 3 ensembles d'états idéaux suivants pour l'algorithme :
1. Chaque coucou pond un œuf et le laisse tomber dans un nid choisi au hasard.
2. Les meilleurs nids avec des œufs de haute qualité seront transmis aux générations suivantes.
3. Le nombre de nids disponibles est fixe et le nid peut détecter un œuf extraterrestre avec la probabilité ’pa’. Dans ce cas, l'oiseau hôte peut soit jeter l'œuf, soit quitter le nid et l'œuf mourra.

Pour simplifier, la 3ème hypothèse peut être approchée par la fraction pa de n nids. Pour le problème de maximisation, la qualité ou la pertinence de la solution peut simplement être proportionnelle à la fonction objectif. Mais d'autres expressions (plus complexes) de la fonction de fitness peuvent également être définies.

Pour chaque itération g, un œuf de coucou i est sélectionné au hasard. De nouvelles solutions xi (g + 1) sont générées à l'aide du vol Levy, une sorte de marche aléatoire dans laquelle les pas sont déterminés dans des limites de longueurs de pas avec une certaine distribution de probabilité, et les directions des pas sont isotropes et aléatoires. Selon les créateurs originaux de la méthode, la stratégie d'utilisation des vols de Levy est préférable à d'autres marches aléatoires simples car elle se traduit par de meilleures performances globales. L'équation générale du vol de Levy se présente comme suit :

xi(g + 1) = xi(g) + α ⊕ prélèvement(λ),

où g indique le numéro de la génération actuelle, et α > 0 indique la taille du pas, qui doit être liée à l'échelle du problème particulier à l'étude. Le symbole ⊕ est utilisé pour désigner la multiplication élément par élément. Notez qu'il s'agit essentiellement d'une chaîne de Markov, puisque l'emplacement suivant dans la génération g + 1 dépend uniquement de l'emplacement actuel dans la génération g et de la probabilité de transition donnée par les 1er et 2ème termes, respectivement. Cette probabilité de transition est modulée par la distribution de Levy comme : 

levy(λ) ∼ g−λ, (1 < λ ≤ 3),

qui a une variance infinie avec une moyenne infinie. La pratique a montré que les meilleurs résultats sont obtenus avec un degré fixe de 2,0. Ici, les étapes forment essentiellement un processus de marche aléatoire avec une distribution de longueur de pas à queue lourde en loi de puissance. Du point de vue informatique, la génération de nombres aléatoires à l'aide des vols de Levy se compose de 2 étapes : d'abord, une direction aléatoire est choisie selon une distribution uniforme, puis des étapes sont générées selon la distribution de Levy choisie. L'algorithme évalue ensuite l'adéquation de la nouvelle solution et la compare avec la solution actuelle. Dans le cas où la nouvelle solution offre une meilleure adéquation, elle remplace l'actuelle. Certains nids sont également abandonnés (le propriétaire du nid a jeté l'œuf de coucou ou a quitté le nid et l'œuf est mort) afin d'augmenter l'exploration de l'espace de recherche à la recherche de solutions plus prometteuses. Le taux de remplacement est déterminé par la probabilité pa, un paramètre du modèle qui doit être ajusté pour améliorer les performances. L'algorithme est appliqué itérativement jusqu'à ce que le critère d'arrêt soit satisfait. Les critères de fin courants sont qu'une solution qui satisfait un seuil inférieur a été trouvée, qu'un nombre fixe de générations a été atteint ou que les itérations successives ne produisent plus de meilleurs résultats.

Arrêtons-nous plus en détail sur le processus de ponte du coucou. Parmi tous les nids, un nid où l'œuf est censé être pondu sera sélectionné au hasard. Puisque l'œuf est une solution, il peut être représenté par la qualité de l'œuf. Si l'œuf de coucou est de meilleure qualité que l'œuf parent, il sera remplacé. Sinon, l'œuf parent restera dans le nid. En fait, l'évolution ultérieure se poursuivra à partir du poussin survivant. Cela signifie que si le poussin de l'œuf parent a survécu, l'évolution se poursuivra à partir du même endroit. Un développement ultérieur n'est possible que si l'œuf de coucou s'avère plus viable et que la recherche d'une solution au problème se poursuit à partir d'un nouvel endroit. L'arbre de décision est représenté schématiquement à la figure 1.

Fig. 1 : Arbre de décision. Le début correspond au point rouge, le point vert est la décision finale

Le deuxième composant de base de l'algorithme après l'arbre de décision est le vol de Levy. Le vol de Levy est une marche aléatoire (un processus statistique de Markov) dans laquelle la longueur du saut change par étapes, la direction des sauts change de manière aléatoire et la distribution de probabilité, un cas particulier de la distribution de Pareto, se caractérise par des queues lourdes. Il est défini comme un saut dans l'espace, isotrope dans des directions aléatoires. Le vol de Levy est un outil pour décrire les processus stochastiques anormaux. La dispersion est infinie (des sauts de grande longueur sont possibles), les longueurs des sauts sont auto-similaires à tous les niveaux (les sauts courts sont entrecoupés de vols longs). Le terme vol de Levy est parfois étendu pour inclure une marche aléatoire qui se produit sur une grille discrète plutôt que dans un espace continu.

Une application claire du vol de Levy dans l'algorithme du coucou peut être imaginée si l'on considère un problème d'optimisation à 1 paramètre. Prenons une fonction hypothétique (la ligne noire de la figure 2), qui ne change pas sur la majeure partie de son domaine de définition, c'est-à-dire la ligne horizontale (y=x). La fonction change seulement dans une petite zone et elle a un maximum. Si nous commençons la recherche du maximum à partir du point orange de la figure 2, puis en obtenant une valeur aléatoire x avec la distribution de Levy, nous nous éloignerons du point de départ, sans obtenir de changement dans la fonction. Mais avec un fort saut dans la queue de la distribution, nous obtenons un point vert, qui est une meilleure solution que l'orange d'origine. Alors seulement à partir du point vert, nous pouvons améliorer le résultat, tout en approchant le maximum de la fonction. Dans cet exemple, le vol de Levy améliore considérablement la capacité de recherche de l'algorithme.

Fig. 2 : Un exemple de recherche d'une solution à une fonction unidimensionnelle hypothétique à l'aide du vol de Levy

Le concept des vols de Levy est utilisé dans la théorie du chaos, lors de la modélisation de phénomènes naturels aléatoires ou pseudo-aléatoires (par exemple, le vol d'un albatros, combinant des trajectoires longues et courtes). Les exemples incluent l'analyse des données sismiques, les mathématiques financières, la cryptographie, l'analyse des signaux, le mouvement turbulent, ainsi que de nombreuses applications en astronomie, biologie et physique.

Pseudo-code de l'algorithme COA (figure 3) :

1. Initialisation des coucous avec des valeurs aléatoires.
2. Définition de la condition de fitness.
3. Ponte des œufs dans des nids aléatoires.
4. Vidage du nid avec une probabilité donnée.
5. Envoi des coucous de la position actuelle vers une direction aléatoire dans la distance de vol de Levy
6. Définition de la condition de fitness.
7. Ponte des œufs dans des nids aléatoires.
8. Vidage du nid avec une probabilité donnée.
9. Répétition à partir de l’étape 5 jusqu'à ce que le critère d'arrêt soit satisfait.

Fig. 3 : Schéma de l'algorithme COA 

3. Code COA

Commençons par considérer le code de l'algorithme. La solution au problème est le coucou, qui est aussi l'œuf. Il s'agit d'une structure simple qui inclut les coordonnées dans l'espace de recherche et la valeur de la fonction de fitness (qualité des œufs).

//——————————————————————————————————————————————————————————————————————————————
struct S_Cuckoo
{
  double c []; //coordinates (egg parameters)
  double e;    //egg quality 
};
//——————————————————————————————————————————————————————————————————————————————

Décrivons le nid sous la forme d'une structure. Ici, exactement comme dans la structure d'un œuf, il y a des coordonnées dans l'espace et la valeur de la fonction de fitness. "Poser l'œuf dans le nid" signifie essentiellement copier la structure de l'œuf dans la structure du nid. Lors de l'utilisation du paramètre probabiliste pa, l'œuf est éjecté du nid lorsqu'un nombre aléatoire de 0,0 à pa tombe dans la plage [0,0 ; 1,0] et la valeur de e est fixée égale à -DBL_MAX.

//——————————————————————————————————————————————————————————————————————————————
struct S_Nest
{
  void Init (int coordinates)
  {
    ArrayResize (c, coordinates);
    e = -DBL_MAX;
  }
  double c []; //coordinates (egg parameters)
  double e;    //egg quality
};
//——————————————————————————————————————————————————————————————————————————————

Classes de l'algorithme. Les méthodes d'initialisation publiques, les deux principales méthodes d'appel dans le programme, les plages de valeurs des arguments du problème d'optimisation et les méthodes privées supplémentaires qui exécutent des fonctions de service sont déclarées ici.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_COA
{
  //============================================================================
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: S_Cuckoo cuckoos []; //all the cuckoos
  public: double cB        []; //best coordinates (egg parameters)
  public: double eB;           //best eggs quality

  public: void Init (const int    coordinatesP, //number of opt. parameters
                     const int    cuckoosP,     //number of cuckoos
                     const int    nestsP,       //number of cuckoo nests
                     const double koef_paP,     //probability of detection of cuckoo eggs
                     const double koef_alphaP); //step control value

  public: void CuckooFlight ();
  public: void LayEggs      ();


  //============================================================================
  private: double SeInDiSp       (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI      (double Min, double Max);
  private: double Scale          (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool Revers);

  private: S_Nest nests [];      //nests
  private: int    cuckoosNumber; //number of cuckoos
  private: int    nestsNumber;   //number of cuckoo nests
  private: double koef_pa;       //probability of detection of cuckoo eggs
  private: double koef_alpha;    //step control value
  private: double v     [];
  private: int    coordinates;   //coordinates number
  private: bool   clutchEggs;    //clutch of eggs
};
//——————————————————————————————————————————————————————————————————————————————

Méthode publique Init() : dans cette méthode, les valeurs des variables sont réinitialisées et la mémoire est allouée pour les tableaux.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_COA::Init (const int    coordinatesP,  //number of opt. parameters
                     const int    cuckoosP,     //number of cuckoos
                     const int    nestsP,       //number of cuckoo nests
                     const double koef_paP,     //probability of detection of cuckoo eggs
                     const double koef_alphaP)  //step control value
{
  MathSrand (GetTickCount ());
  clutchEggs = false;
  eB         = -DBL_MAX;

  coordinates   = coordinatesP;
  cuckoosNumber = cuckoosP;
  nestsNumber   = nestsP;
  koef_pa       = koef_paP;
  koef_alpha    = koef_alphaP;

  ArrayResize (nests, nestsNumber);
  for (int i = 0; i < nestsNumber; i++)
  {
    nests  [i].Init (coordinates);
  }

  ArrayResize (rangeMax,  coordinates);
  ArrayResize (rangeMin,  coordinates);
  ArrayResize (rangeStep, coordinates);
  ArrayResize (cB,        coordinates);

  ArrayResize (v, coordinates);

  ArrayResize (cuckoos, cuckoosNumber);
  for (int i = 0; i < cuckoosNumber; i++)
  {
    ArrayResize (cuckoos [i].c, coordinates);
  }
}
//——————————————————————————————————————————————————————————————————————————————

La première méthode publique faisait appel à chaque itération du « vol du coucou ». Si le drapeau clutchEggs est désactivé, nous envoyons les coucous dans une direction aléatoire, générant des nombres aléatoires dans la plage de la coordonnée correspondante. Si le drapeau est activé, alors le vol réel du coucou est effectué selon la répartition du vol de Levy dans la plage du vecteur v. Le vecteur v est pré-calculé séparément dans Init() pour chaque coordonnée, puisque chacune peut avoir une plage de valeurs différente.

L’expression coucous [i].c [c] = coucous [i].c [c] + r1 * v [c] * pow (r2, -2.0); signifie que nous ajoutons le décalage r1 * v [c] * pow (r2, -2.0), où r1 est -1 ou 1, et détermine la direction du décalage par rapport à la position d'origine, v est un vecteur de déplacement, r2 est un nombre aléatoire compris entre 0,0 et 20,0 élevé à la puissance -2,0. Élever un nombre aléatoire à une puissance est la fonction du vol de Levy. Son graphique est visible à la figure 2.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_COA::CuckooFlight ()
{
  //----------------------------------------------------------------------------
  if (!clutchEggs)
  {
    for (int i = 0; i < coordinates; i++) v [i] = (rangeMax [i] - rangeMin [i]) * koef_alpha;

    for (int i = 0; i < cuckoosNumber; i++)
    {
      for (int c = 0; c < coordinates; c++)
      {
        cuckoos [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
        cuckoos [i].c [c] = SeInDiSp (cuckoos [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    clutchEggs = true;
  }
  else
  {
    double r1 = 0.0;
    double r2 = 0.0;

    for (int i = 0; i < cuckoosNumber; i++)
    {
      for (int c = 0; c < coordinates; c++)
      {
        r1 = RNDfromCI (0.0, 1.0);
        r1 = r1 > 0.5 ? 1.0 : -1.0;
        r2 = RNDfromCI (1.0, 20.0);

        cuckoos [i].c [c] = cuckoos [i].c [c] + r1 * v [c] * pow (r2, -2.0);
        cuckoos [i].c [c] = SeInDiSp (cuckoos [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

La deuxième méthode publique appelée à chaque itération est la "ponte des œufs". Dans cette méthode, la simulation de la ponte d'un œuf de coucou dans un nid est reproduite de manière algorithmique. Cela se produit en choisissant un nid aléatoire parmi tous ceux existants. Il y a ensuite une comparaison de la qualité de l'œuf de coucou et de celui qui est déjà dans le nid. Si l'œuf de coucou est meilleur, un remplacement a lieu. Une caractéristique intéressante de l'algorithme de cette méthode est que la probabilité de savoir si l'œuf va mourir est effectuée après la ponte même si l'œuf de coucou était en meilleure forme. Cela signifie qu'il y a une possibilité koef_pa que n'importe quel œuf meure, peu importe ce qui s'y trouve, tout comme dans la nature. Si l'œuf est mort ou a été jeté hors du nid, ce qui est en fait la même chose, alors le nid sera libre pour une nouvelle ponte d'œuf de toute aptitude, même inférieure, ce qui signifie algorithmiquement une recherche dans un nouvel endroit.

De cette façon, l'une des méthodes d'évolution naturelle, comme le parasitisme des nids, peut être décrite en quelques lignes de code. De nombreux auteurs recommandent dans leurs publications d'initialiser le nid après avoir retiré l'œuf avec de nouvelles valeurs aléatoires, ce qui signifie recommencer la recherche depuis le tout début. Dans la plupart des cas, cela ne donnera pas le résultat souhaité en termes d'augmentation de la capacité exploratoire de l'algorithme. Mes propres recherches ont montré qu'il est plus opportun de laisser simplement le nid vide et l'un des coucous y pondra un œuf, quelle que soit la qualité de l'œuf. C'est mieux que de simples valeurs aléatoires. La variabilité dans l'étude est fournie par des sauts aléatoires dans des directions aléatoires à partir des coordonnées actuelles. Nous aurons donc besoin de moins d'itérations pour rechercher la meilleure solution, augmentant ainsi le taux de convergence de l'algorithme dans son ensemble.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_COA::LayEggs ()
{
  int ind = 0;

  //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  for (int i = 0; i < cuckoosNumber; i++)
  {
    ind = (int)round (RNDfromCI (0.0, nestsNumber - 1));

    if (cuckoos [i].e > nests [ind].e)
    {
      nests [ind].e = cuckoos [i].e;
      ArrayCopy (nests [ind].c, cuckoos [i].c, 0, 0, WHOLE_ARRAY);

      if (cuckoos [i].e > eB)
      {
        eB = cuckoos [i].e;
        ArrayCopy (cB, cuckoos [i].c, 0, 0, WHOLE_ARRAY);
      }
    }
    else
    {
      ArrayCopy (cuckoos [i].c, nests [ind].c, 0, 0, WHOLE_ARRAY);
    }
  }
  //vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv

  for (int n = 0; n < nestsNumber; n++)
  {
    if (RNDfromCI (0.0, 1.0) < koef_pa)
    {
      nests [ind].e = -DBL_MAX;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

4. Résultats des tests

Voici les résultats des tests :

2022.11.30 11:31:54.490 Test_AO_COA_fast (EURUSD,M1) =============================
2022.11.30 11:31:54.507 Test_AO_COA_fast (EURUSD,M1) 1 Skin ; Func exécute 10000 résultats : 4,918379100238852
2022.11.30 11:31:54.507 Test_AO_COA_fast (EURUSD,M1) 1,00000
2022.11.30 11:31:54.854 Test_AO_COA_fast (EURUSD,M1) 20 Skin ; Func exécute 10000 résultats : 4,257477577760983
2022.11.30 11:31:54.854 Test_AO_COA_fast (EURUSD,M1) 0,84220
2022.11.30 11:32:02.346 Test_AO_COA_fast (EURUSD,M1) 500 Skin ; Func exécute 10000 résultats : 1,3521208312080903
2022.11.30 11:32:02.346 Test_AO_COA_fast (EURUSD,M1) 0,14849
2022.11.30 11:32:02.346 Test_AO_COA_fast (EURUSD,M1) =============================
2022.11.30 11:32:02.368 Test_AO_COA_fast (EURUSD,M1) 1 Forest ; Func exécute 10000 résultats : 1,7600394018343262
2022.11.30 11:32:02.368 Test_AO_COA_fast (EURUSD,M1) 0,99557
2022.11.30 11:32:02.775 Test_AO_COA_fast (EURUSD,M1) 20 Forest ; Func exécute 10000 résultats : 0,4968964923017033
2022.11.30 11:32:02.775 Test_AO_COA_fast (EURUSD,M1) 0,28107
2022.11.30 11:32:13.125 Test_AO_COA_fast (EURUSD,M1) 500 Forest ; Func exécute 10000 résultats : 0,07638950254648778
2022.11.30 11:32:13.125 Test_AO_COA_fast (EURUSD,M1) 0,04321
2022.11.30 11:32:13.125 Test_AO_COA_fast (EURUSD,M1) =============================
2022.11.30 11:32:13.148 Test_AO_COA_fast (EURUSD,M1) 1 Megacity ; Func exécute 10000 résultats : 12,0
2022.11.30 11:32:13.148 Test_AO_COA_fast (EURUSD,M1) 1,00000
2022.11.30 11:32:13.584 Test_AO_COA_fast (EURUSD,M1) 20 Megacity ; Func exécute 10000 résultats : 2,69
2022.11.30 11:32:13.584 Test_AO_COA_fast (EURUSD,M1) 0,22417
2022.11.30 11:32:24.379 Test_AO_COA_fast (EURUSD,M1) 500 Megacity ; Func exécute 10000 résultats : 0,40800000000000003
2022.11.30 11:32:24.379 Test_AO_COA_fast (EURUSD,M1) 0,03400
2022.11.30 11:32:24.379 Test_AO_COA_fast (EURUSD,M1) =============================
2022.11.30 11:32:24.379 Test_AO_COA_fast (EURUSD,M1) Tous les scores pour C_AO_COA : 0,507633670637353

L'algorithme de recherche de coucous à l’aide des vols de Levy a montré des résultats impressionnants. Dans la plupart des tests, il a surpassé les autres algorithmes d'optimisation. L'algorithme a montré en particulier une convergence de 100% sur la fonction Skin lisse à 2 variables et sur la fonction Megacity discrète à 2 variables. Ce qui est encore plus surprenant, il a montré une excellente scalabilité sur une fonction discrète. Dans d'autres tests, il n'est que légèrement inférieur à l'algorithme de colonie de fourmis. À l'heure actuelle, nous avons un leader incontesté dans le tableau des résultats.

Je voudrais préciser que tous les algorithmes ont des paramètres de réglage qui affectent les résultats finaux à un degré ou à un autre. Il est donc tout à fait possible que certains de ces algorithmes aient des paramètres encore plus optimaux et que le tableau des résultats puisse être différent. J'ai juste montré les résultats des tests avec les paramètres que j'ai pu trouver pour assurer le meilleur résultat. Si vous parvenez à trouver des paramètres plus optimaux et à obtenir de meilleurs résultats, je peux corriger le tableau des résultats en fonction de ceux-ci. On suppose que l'algorithme des fourmis peut rivaliser avec succès avec le leader actuel, car dans certains indicateurs, il est en avance sur l'algorithme de recherche de coucous et est légèrement en retard en termes d'indicateurs finaux. GWO est toujours leader sur la fonction Skin avec 1000 variables. Dans tous les cas, ceux qui utiliseront des algorithmes dans leurs projets lors de la résolution de leurs problèmes d'optimisation peuvent naviguer dans le tableau et choisir un algorithme pour leurs besoins spécifiques.

COA sur la fonction de test Skin

  COA sur la fonction de test Forest

  COA sur la fonction de test Megacity

Sur la visualisation du banc d'essai, le comportement de l'algorithme diffère de ceux considérés précédemment. Il existe cependant certaines caractéristiques qui sont caractéristiques des algorithmes qui divisent la tâche en zones d'étude, comme l'algorithme de colonie d'abeilles. Cela caractérise la capacité de l'algorithme à ne pas se concentrer sur un seul extremum, mais à explorer plusieurs domaines potentiellement prometteurs, offrant à l'algorithme une résistance contre le blocage d'extrema locaux. Il serait donc peut-être possible d'améliorer l'algorithme en triant les nids et en choisissant parmi eux proportionnellement à leur qualité. Cela signifierait que le coucou choisirait des nids, au lieu de mettre un œuf dans un nid sélectionné au hasard, comme dans la version canonique de l'algorithme. Mais cela n'a pas amélioré les résultats démontrant le caractère pratique du choix aléatoire des nids. Cela fait peut-être écho à ce qui se passe dans la nature. Remplacer un œuf dans le cas d'hôtes plus intelligents est plus difficile, ce qui le rend aléatoire et statistiquement injustifié.

Une autre caractéristique de l'algorithme est qu'il se comporte comme une marche aléatoire sur des fonctions à plusieurs variables. Visuellement, cela ressemble à un bruit blanc ou à un vieil écran de télévision. Une certaine concentration de coordonnées aux endroits des extrema locaux n'est perceptible qu'à la fin des itérations. Je voudrais fournir une "cristallisation" plus claire des paramètres, comme c'est le cas avec l'algorithme de colonie de fourmis. Nous sommes ainsi arrivés au problème général de tous les algorithmes d'optimisation, qui n'a pas de solution générale. De nombreux auteurs d'algorithmes classiques et relativement nouveaux ont tenté de le résoudre.

L'essence du problème est la suivante : on ne sait pas avec certitude lequel des paramètres optimisés de la fonction étudiée a la priorité ou la force, on ne sait pas dans quelle mesure et comment chacun des paramètres affecte le résultat. Par exemple, il y a plusieurs paramètres et l'algorithme a déjà trouvé le bon, mais lequel d'entre eux exactement est inconnu. L'algorithme continuera d'essayer de tous les changer, bien qu'il suffise de n'en changer que quelques-uns pour atteindre l'extrême global. Le problème est exacerbé lorsqu'il s'agit d'une fonction avec plusieurs dizaines, voire des milliers, de variables. Plus il y a de variables, plus le problème est compliqué. Visuellement, cela ressemble à du bruit blanc sur l'écran. 

J'ai essayé de résoudre ce problème au moins partiellement. Si on ne sait pas a priori lequel des paramètres de la fonction étudiée doit être modifié et lequel doit rester le même, on peut essayer de résoudre cela de manière probabiliste. Nous partons du principe que seule une partie de tous les paramètres doit être modifiée, et non pas tous en même temps. L'algorithme PSO se comporte de manière caractéristique. Avec une augmentation du nombre de paramètres (arguments) de la fonction optimisée, celle-ci se comporte comme un nuage qui n'a pas la capacité de se concentrer. Pour ce faire, j'ai introduit un nouveau paramètre pour l'algorithme, qui définit la probabilité que la coordonnée soit modifiée, sinon la coordonnée restera la même.

Et le résultat est... positif !!! Les résultats des tests se sont améliorés. La "cristallisation" que je voulais réaliser est apparue sur des fonctions à plusieurs variables.

Les résultats du banc d'essai se présentent maintenant comme suit :

2022.12.03 16:01:26.256 Test_AO_COAm (EURUSD,M1) =============================
2022.12.03 16:01:27.511 Test_AO_COAm (EURUSD,M1) 1 Skin ; Func exécute 10000 résultats : 4,918367945334852
2022.12.03 16:01:27.511 Test_AO_COAm (EURUSD,M1) 1,00000
2022.12.03 16:01:30.291 Test_AO_COAm (EURUSD,M1) 20 Skin ; Func exécute 10000 résultats : 4,328327964103814
2022.12.03 16:01:30.291 Test_AO_COAm (EURUSD,M1) 0,85911
2022.12.03 16:01:59.306 Test_AO_COAm (EURUSD,M1) 500 Skin ; Func exécute 10000 résultats : 1,3297901702583084
2022.12.03 16:01:59.306 Test_AO_COAm (EURUSD,M1) 0,14316
2022.12.03 16:01:59.306 Test_AO_COAm (EURUSD,M1) =============================
2022.12.03 16:02:00.511 Test_AO_COAm (EURUSD,M1) 1 Forest ; Func exécute 10000 résultats : 1,755200932219688
2022.12.03 16:02:00.511 Test_AO_COAm (EURUSD,M1) 0,99283
2022.12.03 16:02:03.566 Test_AO_COAm (EURUSD,M1) 20 Forest ; Func exécute 10000 résultats : 0,5089243656052672
2022.12.03 16:02:03.566 Test_AO_COAm (EURUSD,M1) 0,28787
2022.12.03 16:02:35.468 Test_AO_COAm (EURUSD,M1) 500 Forest ; Func exécute 10000 résultats : 0,08044934398920801
2022.12.03 16:02:35.468 Test_AO_COAm (EURUSD,M1) 0,04551
2022.12.03 16:02:35.468 Test_AO_COAm (EURUSD,M1) =============================
2022.12.03 16:02:36.628 Test_AO_COAm (EURUSD,M1) 1 Megacity ; Func exécute 10000 résultats : 12,0
2022.12.03 16:02:36.628 Test_AO_COAm (EURUSD,M1) 1,00000
2022.12.03 16:02:39.628 Test_AO_COAm (EURUSD,M1) 20 Megacity ; Func exécute 10000 résultats : 2,9899999999999998
2022.12.03 16:02:39.628 Test_AO_COAm (EURUSD,M1) 0,24917
2022.12.03 16:03:11.892 Test_AO_COAm (EURUSD,M1) 500 Megacity ; Func exécute 10000 résultats : 0,4244
2022.12.03 16:03:11.892 Test_AO_COAm (EURUSD,M1) 0,03537
2022.12.03 16:03:11.892 Test_AO_COAm (EURUSD,M1) =============================
2022.12.03 16:03:11.892 Test_AO_COAm (EURUSD,M1) Tous les scores pour C_AO_COAm : 0,5125572342985216

On peut clairement voir une "cristallisation" sur la visualisation. L'écran, qui ressemble d'abord à un bruit blanc, s'efface, les coordonnées commencent à se concentrer, les centres de concentration deviennent mobiles :

COAm sur la fonction de test Megacity. L'effet de "cristallisation" est visible.

D'une part, il y a la variabilité, c'est-à-dire la capacité de rechercher dynamiquement de nouvelles zones, et d'autre part, la capacité de clarifier les coordonnées des extrêmes déjà atteints. Ci-dessous, l'animation de l'algorithme de colonie de fourmis avec une "cristallisation" prononcée à titre de comparaison :

  ACOm sur la fonction de test Forest

Résultats des tests

AO	Description	Skin			Forest			Megacity (discrète)			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,99283	0,28787	0,04551	1,00000	0,24917	0,03537	0,51255778
ACOm	optimisation des colonies de fourmis	0,98229	0,79108	0,12602	1,00000	0,62077	0,11521	0,38333	0,44000	0,02377	0,49805222
ABCm	colonie d'abeilles artificielle M	1,00000	0,63922	0,08076	0,99908	0,20112	0,03785	1,00000	0,16333	0,02823	0,46106556
ABC	colonie d'abeilles artificielles	0,99339	0,73381	0,11118	0,99934	0,21437	0,04215	0,85000	0,16833	0,03130	0,46043000
GWO	optimiseur du loup gris	0,99900	0,48033	0,18924	0,83844	0,08755	0,02555	1,00000	0,10000	0,02187	0,41577556
PSO	optimisation des essaims de particules	0,99627	0,38080	0,05089	0,93772	0,14540	0,04856	1,00000	0,09333	0,02233	0,40836667
RND	aléatoire	0,99932	0,44276	0,06827	0,83126	0,11524	0,03048	0,83333	0,09000	0,02403	0,38163222

L'un des avantages de l'algorithme de recherche du coucou est que sa recherche globale utilise des vols ou un processus de Levy plutôt que des marches aléatoires standard. Étant donné que les vols de Levy ont une moyenne et une variance infinies, COA peut explorer l'espace de recherche plus efficacement que les algorithmes de processus gaussiens standard. Vol de Levy : Processus de marche aléatoire caractérisé par une série de sauts instantanés sélectionnés à partir d'une fonction de densité de probabilité qui a une queue de loi de puissance.

À l'heure actuelle, l'algorithme est le leader du tableau, surpassant de manière significative les autres algorithmes dans les tests individuels et ne restant pas loin derrière dans d'autres "disciplines". Il y a d'excellents résultats sur la fonction discrète Megacity avec 1000 arguments faisant de la recherche de coucou un excellent outil pour les tâches des traders (qui sont discrètes dans la plupart des cas). D'excellents (mais pas les meilleurs) résultats pour la fonction Skin avec 1000 arguments permettent d'affirmer que l'algorithme est adapté à l'entraînement des réseaux de neurones en particulier et à l'apprentissage automatique en général.

Avantages :
1. Grande vitesse.
2. Polyvalence. L'algorithme peut être utilisé dans une variété de problèmes d'optimisation.
3. La capacité de ne pas se concentrer uniquement sur les extrema locaux.
4. Convergence élevée pour les fonctions lisses et discrètes.
5. Évolutif.

Inconvénients :
1. Paramètres multiples.