Algoritmos de optimización de la población: Algoritmo de siembra y crecimiento de árboles (Saplings Sowing and Growing up — SSG)

Contenido:

1. Introducción
2. Descripción del algoritmo
3. Resultados de las pruebas

1. Introducción

Todos los organismos vivos en la naturaleza están sujetos a ciertas leyes, y esto ayuda a los representantes de la flora y la fauna a sobrevivir en condiciones ambientales cambiantes. Existen varias opciones en cuanto a la adaptabilidad de las plantas al medio ambiente. Algunas de ellas son capaces de tolerar los cambios estacionales, otras pueden adaptarse a la falta de humedad, las temperaturas altas o bajas y la ausencia de polinizadores. Uno de los organismos más estables entre las plantas son los árboles, algunos de ellos son capaces de vivir más de 50 mil años, formando colonias.

La naturaleza es un campo inagotable de inspiración para muchas ideas efectivas en el desarrollo y la invención de métodos computacionales. De hecho, la computación evolutiva es una proyección de la evolución en modelación por computadora. Existen muchos métodos de optimización inspirados en procesos de la naturaleza, como la computación evolutiva, la inmunología artificial, los métodos de población y otros. El SSG se define básicamente como procesos iterativos de generación y combinación que trabajan con un jardín de soluciones potenciales llamadas plántulas.  El algoritmo de siembra y crecimiento de árboles (SSG) fue propuesto por A. Karci y otros coautores en 2002. El algoritmo se inspira en la evolución de los árboles en crecimiento y modela el crecimiento y la ramificación de los mismos.

2. Descripción del algoritmo

El algoritmo SSG es uno de los pocos que no tiene una descripción clara por parte de los autores (solo se expresan disposiciones e ideas generales). Los operadores del algoritmo presentados por los autores tampoco suponen instrucciones prefabricadas para la implementación algorítmica del programa; no hay instrucciones claras sobre los árboles padre e hijo y su interacción. No existen requisitos para el orden en que se ejecutan los operadores, y cualquier usuario puede cambiar su orden para obtener una mejor semilla.

En un sentido amplio, el SSG no es un algoritmo de optimización, sino un conjunto general de reglas diseñado para complementar otros algoritmos con el objetivo de mejorar la calidad de la optimización, es decir, el SSG es un complemento para cualquier algoritmo de población evolutiva que deja espacio para la imaginación y la oportunidad de experimentar con una implementación específica del algoritmo de optimización. He aplicado algunos de mis propios pensamientos y experiencias durante la escritura de los algoritmos anteriores y los he usado para trabajar con el SSG: los resultados de los experimentos se presentan a continuación para que el lector los analice y reflexione por su cuenta.

Para comenzar a comprender el algoritmo, deberemos pensar en un árbol como un agente de optimización. Un árbol es una solución a un problema de optimización, donde cada rama es un parámetro optimizado del problema. De forma bastante abstracta y, diría, artística, podemos ilustrar el árbol hijo y el árbol padre (el algoritmo opera con estos dos conceptos) en la figura 1. El tronco del árbol es un conjunto de parámetros a optimizar. Cada rama es un parámetro optimizado aparte, donde la longitud de la rama está limitada por el rango permitido de valores del parámetro correspondiente. La dirección de las ramas no importa: solo se representa en la figura para mostrar que son diferentes.

Figura 1. Árbol hijo y árbol padre. La línea punteada indica las ramas secundarias que son reemplazadas por las principales;

así, las ramas de los árboles son las coordenadas de los árboles en el espacio de búsqueda.

El algoritmo SSG consta de operadores de variación que generan nuevas soluciones, los candidatos para el conjunto común de soluciones. Los principales operadores de variación son el cruzamiento, la ramificación y la vacunación. La siembra de plántulas debe realizarse a distancias equidistantes en cada dirección una respecto a otra (oeste, este, norte, sur): esta será la etapa inicial del método. Cuando el número de coordenadas (parámetros optimizados) es muy superior a tres, la plantación "uniforme" supone una distribución aleatoria simple de plántulas en el espacio de búsqueda. Luego, las plántulas crecen, se entrecruzan, se ramifican y se realiza el proceso de vacunación.

Vamos a analizar los pasos y operadores del algoritmo SSG:

1) Plantación de plántulas.

El espacio de búsqueda se puede considerar como un jardín de plántulas y, por consiguiente, todas las plántulas deberán distribuirse uniformemente por todo el jardín. Si un agricultor quiere sembrar plántulas, simplemente las sembrará a la misma distancia entre sí para que las plántulas crezcan más rápido sin interferir mutuamente. Para resolver un problema simulando el cultivo de plántulas, las soluciones aleatorias que se generarán inicialmente deberán distribuirse de forma uniforme en un espacio de búsqueda válido.

Cuando tenemos dos o tres coordenadas, no hay problema para distribuir las plántulas de manera uniforme, pero cuando el número de coordenadas es muy superior a tres, resulta más fácil usar una distribución aleatoria. Sin embargo, en la práctica, con una pequeña cantidad de coordenadas, no es necesario cuidar la distribución uniforme de las plántulas, ya que la tarea no supone un gran problema y sabemos que la solución se obtendrá con gran precisión, por lo tanto, independientemente del número de coordenadas en el algoritmo, usaremos una distribución aleatoria de plántulas en el jardín. 

2) Cultivo de plántulas (árboles), tres operadores ejecutados secuencialmente.

2.1) Cruzamiento.

El propósito del operador "cruzamiento" es crear una nueva plántula a partir de las plántulas existentes intercambiando información entre ellas. El cruzamiento es esencialmente un trasplante de una copia de una rama del árbol padre al hijo (figura 1). Para cada par de plántulas, se usa un coeficiente de cruzamiento diferente, que es la probabilidad de cruzamiento. La probabilidad de cruzamiento depende de la distancia entre las plántulas en un par, cuanto mayor sea la distancia, menor será la probabilidad de cruzamiento. El operador de cruzamiento es un método muy importante del algoritmo que ofrece mecanismos combinatorios; la combinación de información entre agentes puede mejorar significativamente la calidad general del algoritmo de optimización.

2.2) Ramificación.

El operador modela el crecimiento de las ramas, y el crecimiento puede resultar positivo (alargamiento) o negativo (desecación). "Para que crezca una rama en cualquier punto del cuerpo de la plántula, no deberá haber ninguna rama cercana que haya brotado previamente allí": aproximadamente así es la descripción del operador "ramificación" que realizan los autores del algoritmo. De hecho, este proceso es más simple y claro de lo que podría parecer a primera vista, y supone una modificación de las ramas existentes del árbol hijo (no se especifica el método concreto de modificación).

La modificación de cada rama individual resulta más probable cuantas más iteraciones hayan pasado entre la iteración actual y aquella en la que se realizó la última modificación de la rama. Mis experimentos han mostrado la ineficiencia de este operador, además, no existen indicaciones directas del uso del método de modificación; así que he tomado la iniciativa en este asunto y he aplicado el cambio en la longitud de la rama según la ley de distribución del vuelo de Levy. Realizaremos la modificación con la probabilidad e intensidad especificadas como parámetros externos del algoritmo.   

2.3) Vacunación.

El proceso de vacunación se realiza entre dos plántulas diferentes si las plántulas son similares. La similitud de plántulas influye en el éxito del proceso de vacunación y es proporcional a la media aritmética de la distancia ponderada. El operador es similar al operador de cruzamiento y consiste en el intercambio de ramificaciones, dotando al algoritmo de una forma adicional de combinar información entre agentes. El operador se muestra en el artículo, pero este operador se comenta en los códigos fuente y los resultados de las pruebas se presentan sin su participación, ya que la vacunación empeora los resultados.

3) Cálculo de la aptitud de los árboles.

4) Plantación de nuevas plántulas en el jardín.

Las plántulas obtenidas con la ayuda de los operadores de cruzamiento, ramificación y vacunación son soluciones temporales (jardín hijo). En esta etapa, deberemos seleccionar las n mejores plántulas (parámetro externo del algoritmo) y colocarlas en el jardín, reemplazando los n peores árboles del jardín. Cabe señalar que el reemplazo con plántulas sucederá en cualquier caso, incluso si son peores que los peores árboles del jardín.

Este es un buen momento para mirar el código del algoritmo SSG, que nos acercará cada vez más al punto culminante de este estudio: la revisión de los resultados de las pruebas.

Por ello, resulta cómodo representar cada árbol como una estructura Garden que servirá de base para crear un jardín de flores. No hay nada más simple en este algoritmo que la entidad "árbol", que necesita solo dos componentes: las coordenadas con [] y el valor de aptitud f.

//——————————————————————————————————————————————————————————————————————————————
struct S_Garden
{
  double c []; //coordinates
  double f;    //fitness
};
//——————————————————————————————————————————————————————————————————————————————

La clase C_AO_SSG del algoritmo SG no supone nada especial, todo aquí nos es bastante familiar gracias a los algoritmos anteriormente analizados. En la clase, declararemos los miembros y métodos para operar en los jardines padre e hijo, un jardín temporal para que funcione el método de clasificación, pues necesitamos clasificar tanto el jardín padre como el hijo. Luego declararemos un array con las mejores coordenadas de la solución en general y el mejor valor de aptitud, así como variables constantes para almacenar los parámetros externos del algoritmo.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SSG
{
  //============================================================================
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: S_Garden pGarden []; //parent's garden
  public: S_Garden cGarden []; //child's garden
  public: S_Garden gardenT []; //temp garden
  public: double cB        []; //best coordinates
  public: double fB;           //fitness of the best coordinates

  public: void Init (const int    coordinatesP,          //Number of coordinates
                     const int    numberTreesP,          //Number of trees
                     const double seedlingsReplacementP, //Seedlings replacement
                     const double probabMatingOperatorP, //Probability mating operator
                     const double probabBranchOperatorP, //Probability branching operator
                     const double powerBranchOperatorP); //Power branching operator

  public: void Sowing      (int iter);
  public: void Germination ();


  //============================================================================
  private: void   Sorting        (S_Garden &garden []);
  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: double vec [];               //Vector
  private: int    ind [];
  private: double val [];
  private: double r;

  private: bool   sowing;               //Sowing
  private: int    coordinates;          //Coordinates number
  private: int    numberTrees;          //Number of trees
  private: int    seedlingsReplacement; //Seedlings replacement
  private: double probabMatingOperator; //Probability mating operator
  private: double probabBranchOperator; //Probability branching operator
  private: double powerBranchOperator;  //Power branching operator
};
//——————————————————————————————————————————————————————————————————————————————

En el método de inicialización Init (), asignaremos la memoria para los arrays y asignaremos los valores a las constantes - parámetros. Como el parámetro seedlingsReplacementP se establece en fracciones del tamaño del jardín (de 0,0 a 1,0), y es responsable de la cantidad de plántulas secundarias para plantar en el jardín principal, deberá convertirse en una representación entera del tamaño del jardín. Después restableceremos la bandera inicial de siembra del jardín e inicializaremos la variable de decisión global con el valor double más pequeño posible.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SSG::Init (const int    coordinatesP,          //Number of coordinates
                     const int    numberTreesP,          //Number of trees
                     const double seedlingsReplacementP, //Seedlings replacement
                     const double probabMatingOperatorP, //Probability mating operator
                     const double probabBranchOperatorP, //Probability branching operator
                     const double powerBranchOperatorP)  //Power branching operator
{
  MathSrand (GetTickCount ());
  sowing = false;
  fB     = -DBL_MAX;

  coordinates    = coordinatesP;
  numberTrees    = numberTreesP;

  if (seedlingsReplacementP >= 1.0)
  {
    seedlingsReplacement = numberTreesP;
  }
  else
  {
    if (seedlingsReplacementP <= 0.0)
    {
      seedlingsReplacement = 1;
    }
    else seedlingsReplacement = int(numberTreesP * seedlingsReplacementP);
  }

  probabMatingOperator = probabMatingOperatorP;
  probabBranchOperator = probabBranchOperatorP;
  powerBranchOperator  = powerBranchOperatorP;

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


  ArrayResize (pGarden,  numberTrees);
  ArrayResize (cGarden,  numberTrees);
  ArrayResize (gardenT,  numberTrees);
  ArrayResize (ind,      numberTrees);
  ArrayResize (val,      numberTrees);

  for (int i = 0; i < numberTrees; i++)
  {
    ArrayResize (pGarden  [i].c, coordinates);
    ArrayResize (cGarden  [i].c, coordinates);
    ArrayResize (gardenT  [i].c, coordinates);
    cGarden [i].f = -DBL_MAX;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Sowing() es el primer método público llamado necesariamente en cada iteración. En la primera iteración, cuando el algoritmo se esté ejecutando, dispersaremos al azar las plántulas por el jardín (espacio de búsqueda) con una distribución uniforme. Aquí vemos que las coordenadas se generan aleatoriamente en el rango permitido entre el mínimo y el máximo de los parámetros optimizados; luego verificaremos si se da una salida del rango permitido, y convertiremos los valores de las coordenadas según el paso de optimización.

En esta etapa, la adaptabilidad de las plántulas es mínima. Ahora estableceremos el vector vec[], que necesitaremos para escalar los incrementos de las ramas en el operador de ramificación, y también calcularemos la distancia euclidiana máxima posible r en el espacio de búsqueda: nos será útil en el operador de cruzamiento para determinar la probabilidad dependiendo de la distancia entre pares de árboles.

//the first planting of trees-------------------------------------------------
if (!sowing)
{
  fB = -DBL_MAX;
  r = 0.0;

  for (int t = 0; t < numberTrees; t++)
  {
    for (int c = 0; c < coordinates; c++)
    {
      cGarden [t].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      cGarden [t].c [c] = SeInDiSp (cGarden [t].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }

    cGarden [t].f = -DBL_MAX;
  }

  for (int c = 0; c < coordinates; c++)
  {
    vec [c] = rangeMax [c] - rangeMin [c];
    r += vec [c] * vec [c];
  }

  r = sqrt (r);

  return;
}

Además, en el método Sowing (), los operadores de cruzamiento, ramificación y vacunación se ejecutarán en las iteraciones segunda y subsiguientes. Aquí, en este ciclo principal, se ejecutarán secuencialmente las siguientes declaraciones:

//tree growth-----------------------------------------------------------------
int child, parent;
double rnd;
double ed; //euclidean distance
double eM;
double u;
double temp;

for (int t = 0; t < numberTrees; t++)

Al ejecutar los operadores, los conceptos "hijo" y "padre" están muy poco definidos, de hecho, son solo fuentes de información básica para crear una nueva plántula. La nueva plántula copia todas las ramas (y las ramas, como podemos recordar, son los parámetros a optimizar) del árbol hijo y recibe otras nuevas del padre.

Para cada nueva plántula, se seleccionarán individualmente dos árboles del jardín, un hijo y un padre al azar, con la misma probabilidad para todos los árboles del jardín, es decir, todos los árboles pueden participar en la creación de una nueva plántula con la misma probabilidad e independientemente de su aptitud. Por lo tanto, hijo y padre son simplemente los índices de los dos árboles originales en el array del jardín padre.

ed = 0.0;

rnd = RNDfromCI (0.0, numberTrees - 1);
child = (int)MathRound (rnd);
if (child < 0) child = 0;
if (child > numberTrees - 1) child = numberTrees - 1;

rnd = RNDfromCI (0.0, numberTrees - 1);
parent = (int)MathRound (rnd);
if (parent < 0) parent = 0;
if (parent > numberTrees - 1) parent = numberTrees - 1;

if (child == parent) parent++;
if (parent > numberTrees - 1) parent = 0;

ArrayCopy (cGarden [t].c, pGarden [child].c, 0, 0, WHOLE_ARRAY);

El primer operador, el cruzamiento o conjugación (mating). Para ejecutar el operador de cruzamiento en una plántula con índice t, deberemos calcular el espacio euclidiano entre los árboles hijo y padre con los índices child y parent:

//mating operator-----------------------------------------------------------
for (int c = 0; c < coordinates; c++)
{
  temp = pGarden [child].c [c] - pGarden [parent].c [c];
  ed += temp * temp;
}

ed = sqrt (ed);

La distancia euclidiana participa en la fórmula para calcular la probabilidad de cruzamiento mediante la normalización a la máxima distancia euclidiana posible r en el espacio de búsqueda:

eM = 1.0 - (ed / r);

A continuación, generaremos un número aleatorio en el rango [0.0;1.0] y si el número resultante entra en la probabilidad calculada eM, realizaremos el cruzamiento, copiando las ramas del árbol padre con la probabilidad del operador probabMatingOperator para cada rama. Si la probabilidad eM no se cumple, la plántula ejecutará el siguiente operador con todas las ramas originales del árbol hijo.

rnd = RNDfromCI (0.0, 1.0);

if (rnd <= eM)
{
  for (int c = 0; c < coordinates; c++)
  {
    rnd = RNDfromCI (0.0, 1.0);

    if (rnd <= probabMatingOperator) cGarden [t].c [c] = pGarden [parent].c [c];
  }
}

A continuación, se ejecutará el operador de ramificación. La ramificación ofrece una variación de ramas: el alargamiento y el acortamiento; este es el operador principal que crea ramas de una nueva longitud, mientras que los operadores restantes realizan solo un papel combinatorio y no crean nuevas ramas únicas. Para cada rama, generaremos un número aleatorio en el rango [0.0;1.0] y si se cumple la probabilidad probabBranchOperator, entonces ramificaremos: cambiaremos la longitud de la rama según la ley de distribución del vuelo de Levy, analizado aquí.

Como podemos ver, no se cambiarán todas las ramas de la plántula; además, se cambiarán independientemente de si la rama se ha copiado del árbol principal en el operador anterior o de si es la rama secundaria original. Después de modificar la rama, verificaremos si hay valores fuera de rango y la alinearemos con el paso de optimización.

//branching operator--------------------------------------------------------
for (int c = 0; c < coordinates; c++)
{
  rnd = RNDfromCI (0.0, 1.0);

  if (rnd < probabBranchOperator)
  {
    double r1 = RNDfromCI (0.0, 1.0);
    r1 = r1 > 0.5 ? 1.0 : -1.0;
    double r2 = RNDfromCI (1.0, 20.0);

    cGarden [t].c [c] = cGarden [t].c [c] + r1 * vec [c] * powerBranchOperator * pow (r2, -2.0);
    cGarden [t].c [c] = SeInDiSp (cGarden [t].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}

El tercer operador es la vacunación. El operador de vacunación fue concebido por los autores, aparentemente, como un operador combinatorio, y debe ejecutarse para copiar ramas del árbol principal en el caso de que las ramas del árbol secundario y principal se distingan en un valor superior a la diferencia promedio entre todas las ramas del árbol del par. Suena muy complicado, pero este operador no tiene mucha utilidad, por lo que lo comentaremos en los archivos fuente. En este caso, no puedo comportarme como un experto en última instancia, así que admito la posibilidad de haber malentendido este operador.

//vaccinating operator------------------------------------------------------
u = 0.0;
    
for (int c = 0; c < coordinates; c++)
{
  u += fabs (cGarden [t].c [c] - pGarden [parent].c [c]) / vec [c];
}

u /= coordinates;

for (int c = 0; c < coordinates; c++)
{
  if (fabs (cGarden [t].c [c] - pGarden [parent].c [c]) / vec [c] >= u)
  {
    cGarden [t].c [c] = pGarden [parent].c [c];
  }
}

Bien, ya hemos plantado las plántulas, hemos cruzado y ramificado, e incluso a veces hemos vacunado. Ha llegado el momento de la última, pero no menos importante, operación del algoritmo: la germinación, es decir, ejecutaremos el segundo método público Germination (), que es obligatorio para la ejecución en cada iteración.

Si la primera iteración está llegando a su fin (y ciertamente lo reconoceremos por la bandera sowing), esto significará que el jardín principal está vacío, así que plantaremos todas las plántulas del jardín secundario en el jardín principal, simplemente copiando todos los árboles jóvenes uno a uno. Después de ello, clasificaremos el jardín principal según el valor de aptitud utilizando el método Sorting(), y si los árboles están clasificados, el árbol en el índice 0 tendrá la mejor aptitud y podremos actualizar la mejor solución global si aún no es la mejor.

if (!sowing)
{
  for (int t = 0; t < numberTrees; t++) pGarden [t] = cGarden [t];

  Sorting (pGarden);

  if (pGarden [0].f > fB)
  {
    fB = pGarden [0].f;

    ArrayCopy (cB, pGarden [0].c, 0, 0, WHOLE_ARRAY);
  }
  
  sowing = true;
  return;
}

Más adelante en el código, solo llegaremos a la segunda y posteriores iteraciones en el algoritmo, ya que a la bandera sowing le hemos asignado prudentemente el valor true. En la segunda y siguientes iteraciones, el jardín secundario deberá clasificarse antes de que las plántulas se transfieran al jardín principal y se reemplacen los peores árboles. Vamos a comprobar si la solución global ha mejorado y luego copiaremos las mejores n plántulas al final del jardín principal.

Para finalizar, solo quedará clasificar el jardín principal; los nuevos miembros de la sociedad arbórea del jardín podrán reemplazar los árboles de las generaciones anteriores para deleitarnos con los resultados florecientes obtenidos tras solucionar los problemas de optimización.

//planting some part from all child trees-------------------------------------
Sorting (cGarden);

if (cGarden [0].f > fB)
{
  fB = cGarden [0].f;

  ArrayCopy (cB, cGarden [0].c, 0, 0, WHOLE_ARRAY);
}

for (int t = 0; t < seedlingsReplacement; t++) pGarden [numberTrees - seedlingsReplacement + t] = cGarden [t];

Sorting (pGarden);

3. Resultados de las pruebas

Aquí tenemos el resultado del funcionamiento del algoritmo SSG en el banco de pruebas:

2023.03.09 12:50:37.207    Test_AO_SSG (GBPUSD,M1)    C_AO_SSG:50;0.3;0.5;0.4;0.1
2023.03.09 12:50:37.207    Test_AO_SSG (GBPUSD,M1)    =============================
2023.03.09 12:50:45.954    Test_AO_SSG (GBPUSD,M1)    5 Rastrigin's; Func runs 10000 result: 80.7052793572295
2023.03.09 12:50:45.954    Test_AO_SSG (GBPUSD,M1)    Score: 0.99998
2023.03.09 12:50:59.290    Test_AO_SSG (GBPUSD,M1)    25 Rastrigin's; Func runs 10000 result: 77.3972262608643
2023.03.09 12:50:59.290    Test_AO_SSG (GBPUSD,M1)    Score: 0.95900
2023.03.09 12:52:25.368    Test_AO_SSG (GBPUSD,M1)    500 Rastrigin's; Func runs 10000 result: 52.24518909141432
2023.03.09 12:52:25.368    Test_AO_SSG (GBPUSD,M1)    Score: 0.64735
2023.03.09 12:52:25.368    Test_AO_SSG (GBPUSD,M1)    =============================
2023.03.09 12:52:31.419    Test_AO_SSG (GBPUSD,M1)    5 Forest's; Func runs 10000 result: 1.331178589711503
2023.03.09 12:52:31.419    Test_AO_SSG (GBPUSD,M1)    Score: 0.75298
2023.03.09 12:52:42.575    Test_AO_SSG (GBPUSD,M1)    25 Forest's; Func runs 10000 result: 1.019329018074209
2023.03.09 12:52:42.575    Test_AO_SSG (GBPUSD,M1)    Score: 0.57658
2023.03.09 12:53:48.922    Test_AO_SSG (GBPUSD,M1)    500 Forest's; Func runs 10000 result: 0.25410121872226443
2023.03.09 12:53:48.922    Test_AO_SSG (GBPUSD,M1)    Score: 0.14373
2023.03.09 12:53:48.922    Test_AO_SSG (GBPUSD,M1)    =============================
2023.03.09 12:53:57.201    Test_AO_SSG (GBPUSD,M1)    5 Megacity's; Func runs 10000 result: 6.4
2023.03.09 12:53:57.201    Test_AO_SSG (GBPUSD,M1)    Score: 0.53333
2023.03.09 12:54:08.004    Test_AO_SSG (GBPUSD,M1)    25 Megacity's; Func runs 10000 result: 4.504
2023.03.09 12:54:08.004    Test_AO_SSG (GBPUSD,M1)    Score: 0.37533
2023.03.09 12:56:07.061    Test_AO_SSG (GBPUSD,M1)    500 Megacity's; Func runs 10000 result: 1.2336
2023.03.09 12:56:07.061    Test_AO_SSG (GBPUSD,M1)    Score: 0.10280
2023.03.09 12:56:07.061    Test_AO_SSG (GBPUSD,M1)    =============================
2023.03.09 12:56:07.061    Test_AO_SSG (GBPUSD,M1)    All score: 5.09109

Podemos decir que el SSG no tiene demasiados parámetros, aunque esto es consecuencia de mi rendimiento amateur a la hora de escribir el algoritmo (los autores del SSG tienen menos parámetros), pero ellos (los parámetros) merecen una atención excepcional y su significado merece ser discutido. En las pruebas se han utilizado estos parámetros: permítame recordarle que en cada artículo doy los mejores parámetros de los algoritmos en el sentido de que los parámetros deben proporcionar el mayor resultado posible en las pruebas.

C_AO_SSG:50;0.3;0.5;0.4;0.1

input int NumberTrees_P = 50; - número de árboles en el jardín, no he experimentado con este parámetro, y he dejado el valor por defecto (el valor por defecto en mis experimentos); con un valor de 100, el algoritmo produce resultados en conjunto aún mejores, pero la capacidad de escalado disminuye debido a la disminución en el número de iteraciones permitidas en el jardín considerando el tamaño del mismo: un jardín con un gran número de ramas no tiene tiempo para evolucionar.

input double SeedlingsReplacement_P = 0.3; - proporción de plántulas del jardín hijo que se transferirán al jardín padre.
input double ProbabMatingOperator_P = 0.5; - probabilidad de cruzamiento (copiado de ramas del árbol padre) si se cumple la probabilidad, teniendo en cuenta la distancia entre un par de árboles.
input double ProbabBranchOperator_P = 0.4; - probabilidad de ramificación (crecimiento/acortamiento de ramas); es un parámetro importante que afecta significativamente al rendimiento del algoritmo (sin embargo, todos los parámetros son importantes).
input double PowerBranchOperator_P  = 0.1; - fuerza de la ramificación, este es un factor de escalado en la dimensionalidad de los parámetros que se están optimizando; 1.0 o más indicará el crecimiento de las ramas hasta los límites del jardín; 0.0 - sin crecimiento de las ramas, es decir, no surgirán nuevos tamaños de ramas y el algoritmo degenerará en una herramienta combinatoria simple (gran idea para usar el SSG, por cierto, no se ha realizado ninguna investigación en esta dirección).

Si prestamos atención a la animación del algoritmo SSE en las funciones de prueba, notaremos la ausencia de patrones de movimiento de árboles en el jardín, solo se nota algo de "agrupamiento" en los extremos locales. No obstante, la alta calidad de la convergencia se nota de inmediato al compararlo con los algoritmos considerados anteriormente. También es destacable la reproducibilidad estable de los resultados.

  SSG en la función de prueba Rastrigin.

  SSG en la función de prueba Forest.

  SSG en la función de prueba Megacity.

Vamos a discutir los resultados del algoritmo SSG, y definitivamente hay algo de qué hablar. El algoritmo de siembra y crecimiento de árboles se ha colocado triunfalmente en la primera línea de la clasificación, ¡ha convertido a sus rivales en escombros! El algoritmo no usa el conocimiento de la aptitud directamente para modificar los árboles de decisión; la aptitud solo es necesaria para clasificar el jardín hijo y el jardín padre, por lo que resulta aún más sorprendente que el algoritmo haya podido mostrar resultados tan notables en las pruebas.

Esto es como si un equipo de ciegos venciera a un equipo de personas con visión normal en ejercicios de orientación. El algoritmo ha superado a los demás miembros de la tabla en cuatro de las seis pruebas, y se encuentra no muy lejos de ellos en las pruebas en las que no es líder. ¡El SSG ha mostrado la ventaja más impresionante sobre sus rivales en la función discreta Megacity, superando al competidor más cercano, el HS, en casi un 60%! Esto demuestra la excelente escalabilidad del algoritmo. El mejor resultado de escalabilidad se ha dado en la función de prueba Forest "aguda", superando al mejor competidor en esta prueba ACOm en casi un 30%.

AO	Description	Rastrigin			Rastrigin final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result
		10 params (5 F)	50 params (25 F)	1000 params (500 F)		10 params (5 F)	50 params (25 F)	1000 params (500 F)		10 params (5 F)	50 params (25 F)	1000 params (500 F)
SSG	plantones sembrando y creciendo	1,00000	1,00000	0,65914	2,65914	0,70823	0,94522	1,00000	2,65345	0,71532	0,85412	1,00000	2,56944	100,000
HS	harmony search	0,99676	0,95282	0,57048	2,52006	1,00000	0,98931	0,44806	2,43736	1,00000	1,00000	0,41537	2,41537	93,370
ACOm	ant colony optimization M	0,34611	0,17985	0,20182	0,72778	0,85966	1,00000	0,77362	2,63327	1,00000	0,88484	0,05606	1,94090	66,407
IWO	invasive weed optimization	0,95828	0,67083	0,35295	1,98207	0,68718	0,46349	0,31773	1,46840	0,75912	0,39732	0,33289	1,48933	61,691
COAm	cuckoo optimization algorithm M	0,92400	0,46794	0,30792	1,69987	0,55451	0,34034	0,16526	1,06012	0,67153	0,30326	0,17083	1,14561	48,226
FAm	firefly algorithm M	0,59825	0,33980	0,20290	1,14095	0,47632	0,42299	0,49790	1,39721	0,21167	0,25143	0,35258	0,81568	41,042
ABC	artificial bee colony	0,78170	0,32715	0,24656	1,35541	0,50591	0,21455	0,13344	0,85390	0,47444	0,23609	0,13926	0,84979	37,204
BA	bat algorithm	0,40526	0,63761	1,00000	2,04287	0,15275	0,17477	0,25989	0,58741	0,15329	0,06334	0,17371	0,39034	36,703
GSA	gravitational search algorithm	0,70167	0,45217	0,00000	1,15384	0,26854	0,36416	0,33204	0,96475	0,51095	0,32436	0,00000	0,83531	35,834
BFO	bacterial foraging optimization	0,67203	0,30963	0,13988	1,12154	0,35462	0,26623	0,20652	0,82736	0,42336	0,30519	0,18932	0,91786	34,700
MA	monkey algorithm	0,33192	0,33451	0,17340	0,83983	0,03684	0,07891	0,08932	0,20508	0,05838	0,00383	0,10720	0,16941	13,185
FSS	fish school search	0,46812	0,25337	0,13383	0,85532	0,06711	0,05013	0,06516	0,18240	0,00000	0,00959	0,08283	0,09242	12,089
PSO	particle swarm optimisation	0,20449	0,08200	0,08478	0,37127	0,13192	0,10486	0,21738	0,45415	0,08028	0,02110	0,01957	0,12095	9,696
RND	random	0,16826	0,09743	0,09495	0,36065	0,07413	0,04810	0,04715	0,16938	0,00000	0,00000	0,04922	0,04922	4,916
GWO	grey wolf optimizer	0,00000	0,00000	0,02672	0,02672	0,00000	0,00000	0,00000	0,00000	0,18977	0,03645	0,02557	0,25179	1,000

Conclusiones

Características del SSG: no hay requisitos de diferenciabilidad y continuidad de la función optimizada; no hay restricciones en el tipo de representación y codificación utilizado; el algoritmo no usa la información sobre la aptitud de los agentes individuales y la mejor solución en su conjunto. Gracias a estas características, el SSG puede aplicarse fácilmente a varios problemas de optimización, incluidas tareas muy complejas. El SSG se puede recomendar para su uso con confianza en tareas de trading y aprendizaje automático. Al momento de escribir este artículo, el algoritmo de siembra y crecimiento de árboles es el líder indiscutible en cuanto a calidad de convergencia, estabilidad de resultados y escalabilidad.

Encontrará el histograma con los resultados de la prueba del algoritmo en la Figura 2.

Figura 2. Histograma con los resultados finales de los algoritmos de prueba.

Ventajas y desventajas del algoritmo de siembra y crecimiento de árboles (SSG):

Ventajas:
1. Es fácil de aplicar.
2. Excelente convergencia en todo tipo de funciones, sin excepción.
3. Escalabilidad extraordinaria.

Desventajas:
1. Muchas opciones de personalización, aunque estas son intuitivas.

Para cada artículo, adjuntamos un archivo que contiene las versiones actualizadas actuales de los códigos del algoritmo para todos los artículos anteriores. El artículo representa la experiencia acumulada y la opinión personal del autor; las conclusiones y juicios se basan en los experimentos realizados.