Algoritmos de optimización de la población: Evolución de grupos sociales (Evolution of Social Groups, ESG)

Contenido:

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

1. Introducción

En el campo de la optimización, existe una amplia gama de algoritmos poblacionales diseñados para encontrar soluciones óptimas a diversos problemas. No obstante, a pesar de su importancia, los algoritmos multipoblacionales y de enjambre múltiple no han sido suficientemente tratados hasta ahora en nuestros artículos e investigaciones. En consecuencia, he llegado a la conclusión de que debemos profundizar en este tema tan fascinante y prometedor.

Los algoritmos multipoblacionales se basan en la idea de usar múltiples poblaciones independientes para resolver problemas de optimización. Las poblaciones funcionan lógicamente en paralelo y pueden intercambiar información sobre las soluciones óptimas, lo cual permite explorar simultáneamente distintas regiones del espacio de parámetros y encontrar diferentes óptimos. Por otra parte, los algoritmos de enjambre múltiple utilizan grupos sociales (enjambres) de muchas partículas interactuantes que pueden cooperar entre sí de forma similar e intercambiar información para alcanzar soluciones óptimas.

En el presente artículo, llenaremos ese vacío y analizaremos como ejemplo un algoritmo ESG multipoblacional que hemos creado específicamente para esta ocasión. Asimismo, repasaremos los principios básicos de estos algoritmos, y revisaremos los resultados de los estudios comparativos para evaluar el rendimiento de dichos algoritmos en comparación con los métodos de optimización monopoblacionales.

2. Descripción del algoritmo

Los algoritmos multipoblacionales pueden basarse en los siguientes principios en diversas variantes y combinaciones:

1. Grupos sociales. El algoritmo no opera sobre partículas individuales, sino sobre grupos sociales unidos por la cooperación y la experiencia compartida. Cada grupo posee su propio centro de decisión y un conjunto de partículas como agentes de optimización. Los grupos interactúan, comparten experiencias y utilizan la información sobre las mejores soluciones para mejorar su rendimiento.

2. Movimiento colectivo. Las partículas de los grupos sociales interactúan y se mueven de forma conjunta en el espacio de parámetros. Esto permite a los grupos explorar distintas regiones del espacio de parámetros y compartir información sobre las mejores soluciones halladas.

3. Experiencia local y global. Cada grupo social almacena información sobre la mejor solución dentro de él (experiencia local). También hay un mejor resultado general entre todos los grupos (experiencia global). Los grupos retienen las mejores soluciones, comparten las experiencias y las utilizan para mejorar los resultados.

4. Evolución e intercambio de experiencias. El algoritmo pasa por iteraciones en las que los grupos sociales se actualizan y comparten experiencias. Así, se da una mejora iterativa de las soluciones y una búsqueda del resultado óptimo.

5. Adaptabilidad y diversidad. Al interactuar y compartir experiencias, los grupos pueden adaptarse a condiciones cambiantes y encontrar una variedad de soluciones óptimas. El algoritmo tiene la propiedad de la adaptabilidad, que le permite responder de manera eficaz a las condiciones y requisitos cambiantes del problema de optimización. Los grupos pueden adaptarse a las nuevas condiciones, cambiar su estrategia para moverse por el espacio de parámetros y actualizar sus soluciones basándose en las experiencias aprendidas. Esto permite al algoritmo buscar soluciones óptimas de manera eficaz, especialmente cuando las condiciones del problema cambian con el tiempo.

Más arriba hemos hablado de los principios básicos de los algoritmos multipoblacionales. Veamos ahora los detalles de la estrategia de búsqueda ESG.

Supongamos que tenemos una sociedad de partículas, a la que llamaremos "grupo social". En este grupo prevalece un determinado patrón de comportamiento, el "centro", y las partículas del grupo siguen este patrón con cierta desviación, que puede describirse usando una determinada ley de distribución. La mayoría de las partículas difieren ligeramente del centro, pero algunas se desvían fuertemente dentro de la zona de influencia del grupo, cuyos límites son definidos por la distribución. Cuando surge un modelo de comportamiento más adaptable entre las partículas, este se convierte en el nuevo centro del grupo. Así, el grupo se desplazará en busca del modelo de comportamiento de partículas más estable.

Puede haber varios grupos de este tipo y ser independientes, por lo que podemos denominar algoritmo multipoblacional aquel que imita el comportamiento de los miembros individuales en grupos sociales a bajo nivel y el comportamiento general de los grupos a alto nivel.

Dado tal concepto, es posible que algunos grupos individuales o incluso todos los grupos se detengan simultáneamente en su desarrollo y se queden atascados en extremos locales. Para evitarlo, introduciremos la noción de "ampliación de la esfera de influencia de un grupo social". Si no se avanza en cada iteración, ampliaremos los límites del grupo, lo cual permitirá abrir nuevas áreas de búsqueda y diversificar la población de grupos. Si el grupo encuentra una solución superior a la anterior, el radio de los límites del grupo se reducirá de nuevo al valor mínimo por defecto. Esto ayudará al algoritmo a evitar quedarse atascado en trampas localizadas y potenciará la exploración de nuevas zonas cuando sea necesario. El aumento del radio también favorecerá la diversidad de grupos sociales. Diferentes grupos explorarán distintas regiones del espacio de parámetros.

Este concepto de algoritmo multipoblacional para la evolución de los grupos sociales parece prometedor. Sin embargo, no todo resulta tan sencillo como puede parecer a primera vista. La posición actual del centro del grupo puede hallarse en una posición desafortunada en las coordenadas relevantes, e incluso ampliar la zona de influencia podría no resultar efectivo. En estos casos, podemos decir que existe una "expansión diagonal" (como en el algoritmo ACO, en el que las hormigas recorren solo sus caminos sin desviarse lateralmente), cuando lo que realmente se requiere es una "expansión perpendicular", o también es posible lo contrario.

Para superar el problema mencionado, es importante garantizar la transferencia de experiencias positivas entre grupos. Para ello, podemos permitir que algunas partículas tomen prestadas ideas de los centros de grupos "ajenos". Así, un modelo central de comportamiento influirá en las partículas individuales de otros grupos. El impacto, por cierto, no puede ser ni será necesariamente positivo. De forma esquemática, el modelo de comportamiento de los grupos sociales se presenta en la figura 1.

Figura 1. Esquema de funcionamiento del algoritmo. Separar los grupos, ampliar si no hay progreso, reducir si la solución mejora,

préstamo de "mejores ideas" (coordenadas) de grupos vecinos "Bt" (best of team) por partículas "p0" (partícula sobre el índice condicional 0 del grupo).

El pseudocódigo del algoritmo ESG puede representarse de la forma que sigue:

1. Colocamos aleatoriamente los centros de los grupos en el espacio de búsqueda.
2. Ubicamos las partículas de los grupos alrededor de los centros correspondientes con la distribución dada*.
3. Calculamos los valores de aptitud de las partículas.
4. Actualizamos la solución global.
5. Actualizamos el centro de cada grupo.
6. Ampliamos los límites del grupo si no mejora la posición del centro y los reducimos si ha mejorado.
7. Colocamos las partículas de los grupos alrededor de los centros correspondientes con la distribución dada.
8. Añadimos información de los centros de los "grupos ajenos" a una partícula de cada grupo (la partícula recibe un conjunto de coordenadas de los grupos ajenos elegidas al azar).
9. Calculamos los valores de aptitud de las partículas.
   
10. Repetimos desde el paso 4 hasta que se cumpla el criterio de parada.

* - En ESG he utilizado la distribución de ley de potencia para repartir las partículas del grupo con respecto al centro, pero en principio se pueden utilizar otras leyes de distribución, incluso combinaciones de ellas para partes individuales de la lógica de la estrategia. El campo está abierto a la experimentación.

Veamos ahora el código. Para describir un grupo social, escribiremos la estructura "S_Group", que contiene algunas variables de miembro:

• "cB" - array de valores para almacenar las coordenadas del "centro".
• "fB" - valor de la función de aptitud central, inicializada con el valor "-DBL_MAX".
• "sSize" - tamaño del grupo.
• "sRadius" - radio del grupo.
  

El método "Init" en la estructura toma dos argumentos: "coords", el número de coordenadas y "groupSize", el tamaño del grupo.

//——————————————————————————————————————————————————————————————————————————————
struct S_Group
{
  void Init (int coords, int groupSize)
  {
    ArrayResize (cB, coords);
    fB          = -DBL_MAX;
    sSize       = groupSize;
  }

  double cB [];
  double fB;
  int    sSize;
  double sRadius;
};
//——————————————————————————————————————————————————————————————————————————————

Para la lógica del algoritmo ESG, bastará con una estructura simple que describa un agente de búsqueda. Hemos decidido no incluir la estructura partícula-agente en los campos de descripción de los grupos; cada grupo tendrá acceso a sus partículas como parte de la población global, lo que mantendrá el ya conocido acceso a los agentes desde fuera del algoritmo a la vez que se evita el copiado innecesario de partículas de grupo en los agentes.

La definición de la estructura "S_Agent" contiene dos variables:

• "c" - array de valores de coordenadas del agente.
• "f" - valor de aptitud del agente, inicializado con el valor "-DBL_MAX".
  

El método "Init" toma el argumento "coords" para redimensionar el array "c".

//——————————————————————————————————————————————————————————————————————————————
struct S_Agent
{
  void Init (const int coords)
  {
    ArrayResize (c, coords);
    f = -DBL_MAX;
  }

  double c []; //coordinates
  double f;    //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Ahora definiremos la clase "C_AO_ESG", que contiene varios campos y métodos:

1. Campos públicos:

• "cB" - array de valores de las mejores coordenadas de la solución global.
• "fB" - valor de aptitud de las mejores coordenadas.
• "a" - array de objetos de tipo "S_Agent" que representan agentes.
• "rangeMax" - array de valores máximos del rango de búsqueda.
• "rangeMin" - array de valores mínimos del rango de búsqueda.
•  "rangeStep" - array de valores de pasos de búsqueda.

2. Métodos:

• "Init" - función utilizada para inicializar las variables de miembro de una clase. Toma los argumentos: número de coordenadas, tamaño de la población, número de grupos, radio inicial del grupo, factor de expansión del grupo y grado de distribución.
  
• "Moving" - método que desplaza los agentes.
• "Revision" - método que revisa los agentes.
• "SeInDiSp" - método que calcula los valores en un rango con un paso especificado.
• "RNDfromCI" - método que genera números aleatorios en un intervalo dado.
• "Scale" - método que escala valores de un rango a otro.
• "PowerDistribution" - método que genera valores según una distribución de potencia.

3. Campos privados:

• "coords" - número de coordenadas.
• "popSize" - tamaño de la población.
• "gr" - array de objetos de tipo "S_Group" que representan los grupos.
• "groups" - número de grupos.
• "groupRadius" - radio del grupo.
• "expansionRatio" - ratio de expansión.
• "poder" - grado.
•  "revision" - bandera que indica la necesidad de una revisión.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ESG
{
  //----------------------------------------------------------------------------
  public: double  cB [];       //best coordinates
  public: double  fB;          //FF of the best coordinates
  public: S_Agent a  [];       //agents

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search

  public: void Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    groupsP,              //number of groups
                     const double groupRadiusP,         //group radius
                     const double expansionRatioP,      //expansion ratio
                     const double powerP);              //power

  public: void Moving   ();
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: int     coords;
  private: int     popSize;          //population size
  private: S_Group gr [];            //group

  private: int    groups;            //number of groups
  private: double groupRadius;       //group radius
  private: double expansionRatio;    //expansion ratio
  private: double power;             //power

  private: bool   revision;

  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 PowerDistribution (const double In, const double outMin, const double outMax, const double power);
};
//——————————————————————————————————————————————————————————————————————————————

El método "Init" de la clase se utiliza para inicializar las variables de la clase según los parámetros introducidos. Además de la inicialización primaria de las variables y del establecimiento de los tamaños de los arrays, el método realiza el cálculo del número de partículas de cada grupo en caso de que el número de grupos no sea múltiplo del tamaño de la población.

El array "partInSwarms" cambia de tamaño a "groups", donde "groups" es el número de grupos. A continuación, se asigna a la variable "particles" el resultado de la división de "popSize" entre "groups", donde "popSize" será el tamaño de la población. Los valores del array "partInSwarms" se rellenan con el valor "particles", es decir, la cantidad sin resto. A continuación, se calcula el número de elementos perdidos ("lost") restando el producto de "particles" y "groups" a "popSize". Si hay elementos perdidos ("lost > 0"), se agrupan uniformemente en el ciclo while.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ESG::Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    groupsP,              //number of groups
                     const double groupRadiusP,         //group radius
                     const double expansionRatioP,      //expansion ratio
                     const double powerP)
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords         = coordinatesNumberP;
  popSize        = populationSizeP;
  groups         = groupsP;
  groupRadius    = groupRadiusP;
  expansionRatio = expansionRatioP;
  power          = powerP;

  //----------------------------------------------------------------------------
  int partInSwarms [];
  ArrayResize (partInSwarms, groups);

  int particles = popSize / groups;
  ArrayInitialize (partInSwarms, particles);

  int lost = popSize - particles * groups;

  if (lost > 0)
  {
    int pos = 0;

    while (true)
    {
      partInSwarms [pos]++;
      lost--;
      pos++;
      if (pos >= groups) pos = 0;
      if (lost == 0) break;
    }
  }

  //----------------------------------------------------------------------------
  ArrayResize (rangeMax,  coords);
  ArrayResize (rangeMin,  coords);
  ArrayResize (rangeStep, coords);
  ArrayResize (cB,        coords);

  ArrayResize (gr,        groups);
  for (int s = 0; s < groups; s++) gr [s].Init (coords, partInSwarms [s]);

  ArrayResize (a, popSize);
  for (int i = 0; i < popSize; i++) a [i].Init (coords);
}
//——————————————————————————————————————————————————————————————————————————————

El método Moving se usa para generar los centros y los individuos de los grupos al principio de la optimización. El método efectúa las siguientes acciones:

• Generación de los centros para cada grupo "s" en el ciclo exterior "for". Para ello, un ciclo "for" anidado genera un valor "coordinate" aleatorio dentro de un rango determinado para cada coordenada "c". A continuación, el valor de "coordinate" se convierte al rango deseado y se almacena en el array "gr[s].cB[c]".

• Generación de individuos para cada grupo "s" y cada individuo "p" en un ciclo externo "for". Los ciclos "for" anidados calculan el valor "radius" según los parámetros especificados y el estado actual del grupo. A continuación, se calculan los valores "min" y "max" ajustando "radius" en relación con los límites del intervalo. Después se genera un valor "coordinate" aleatorio dentro del intervalo especificado utilizando la función "PowerDistribution". El valor de "coordinate" resultante se convierte y se almacena en el array "a[cnt].c[c]".

• Luego establecemos la bandera "revision" en "true" para indicar que se están generando centros e individuos.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ESG::Moving ()
{
  if (!revision)
  {
    int    cnt        = 0;
    double coordinate = 0.0;
    double radius     = 0.0;
    double min        = 0.0;
    double max        = 0.0;

    //generate centers----------------------------------------------------------
    for (int s = 0; s < groups; s++)
    {
      gr [s].sRadius = groupRadius;

      for (int c = 0; c < coords; c++)
      {
        coordinate    = RNDfromCI (rangeMin [c], rangeMax [c]);
        gr [s].cB [c] = SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    //generate individuals of groups--------------------------------------------
    for (int s = 0; s < groups; s++)
    {
      for (int p = 0; p < gr [s].sSize; p++)
      {
        for (int c = 0; c < coords; c++)
        {
          radius = (rangeMax [c] - rangeMin [c]) * gr [s].sRadius;
          min    = gr [s].cB [c] - radius;
          max    = gr [s].cB [c] + radius;

          if (min < rangeMin [c]) min = rangeMin [c];
          if (max > rangeMax [c]) max = rangeMax [c];

          coordinate    = PowerDistribution (gr [s].cB [c], min, max, power);
          a [cnt].c [c] = SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
        }

        cnt++;
      }
    }

    revision = true;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Las principales acciones para generar nuevas partículas tienen lugar en el método "Revision", que realiza la actualización de la mejor solución global, la generación de los nuevos individuos del grupo y el intercambio de experiencias entre grupos mediante la transferencia de información de los centros de los grupos "ajenos" a una única partícula. Así, solo una partícula de un grupo puede tomar prestadas experiencias de otros grupos. El método efectúa las siguientes acciones:

• Actualización de la mejor solución global. En un ciclo "for" se iteran todos los individuos y se comprueba si el valor de la función de aptitud del individuo actual es mayor que el mejor valor actual de la función de aptitud, entonces se actualiza el mejor valor y el array de coordenadas del individuo actual se copia en el array de coordenadas de la mejor solución.

• Generación de nuevos individuos o grupos. En un ciclo for iteramos todos los grupos y sus individuos. Los ciclos anidados calculan los valores del radio, la coordenada mínima y la coordenada máxima de cada grupo. A continuación, se generan valores de coordenadas aleatorios usando la función "PowerDistribution" y el resultado se almacena en un array de coordenadas de los individuos.

• Intercambio de experiencias entre grupos. En un ciclo for iteramos todos los grupos. El ciclo "for" anidado genera un valor aleatorio que determina con qué grupo se compartirá la experiencia. A continuación, los valores de las coordenadas de los individuos del grupo actual se actualizan con los valores de las coordenadas del grupo elegido.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ESG::Revision ()
{
  //----------------------------------------------------------------------------
  //update the best global solution
  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB)
    {
      fB = a [i].f;
      ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  int cnt = 0;
  bool impr = false;

  for (int s = 0; s < groups; s++)
  {
    impr = false;

    for (int p = 0; p < gr [s].sSize; p++)
    {
      if (a [cnt].f > gr [s].fB)
      {
        gr [s].fB = a [cnt].f;
        ArrayCopy (gr [s].cB, a [cnt].c, 0, 0, WHOLE_ARRAY);
        impr = true;
      }

      cnt++;
    }

    if (!impr) gr [s].sRadius *= expansionRatio;
    else       gr [s].sRadius  = groupRadius;

    if (gr [s].sRadius > 0.5) gr [s].sRadius = 0.5;
  }

  //generate individuals of groups----------------------------------------------
  double coordinate = 0.0;
  double radius     = 0.0;
  double min        = 0.0;
  double max        = 0.0;
  cnt = 0;

  for (int s = 0; s < groups; s++)
  {
    for (int p = 0; p < gr [s].sSize; p++)
    {
      for (int c = 0; c < coords; c++)
      {
        if (RNDfromCI (0.0, 1.0) < 1.0)
        {
        radius = (rangeMax [c] - rangeMin [c]) * gr [s].sRadius;
        min    = gr [s].cB [c] - radius;
        max    = gr [s].cB [c] + radius;

        if (min < rangeMin [c]) min = rangeMin [c];
        if (max > rangeMax [c]) max = rangeMax [c];

        coordinate    = PowerDistribution (gr [s].cB [c], min, max, power);
        a [cnt].c [c] = SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
        }
      }

      cnt++;
    }
  }

  //exchange of experience----------------------------------------------------------------
  cnt = 0;

  for (int s = 0; s < groups; s++)
  {
    for (int c = 0; c < coords; c++)
    {
      int posSw = (int)RNDfromCI (0, groups);
      if (posSw >= groups) posSw = groups - 1;

      //if (sw [posSw].fB > sw [s].fB)
      {
        a [cnt].c [c] = gr [posSw].cB [c];
      }
    }

    cnt += gr [s].sSize;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Tras escribir el algoritmo ESG básico, cuyo código se presenta más arriba, surgió la idea de introducir cambios y permitir que partículas de distintos grupos intercambiaran información para aumentar las cualidades combinatorias del algoritmo. Para ello, modificaremos la estructura del agente. Necesitaremos los campos adicionales "cMain" (coordenadas principales) y "fMain" (experiencia principal).

//——————————————————————————————————————————————————————————————————————————————
struct S_Agent
{
  void Init (const int coords)
  {
    ArrayResize (c,     coords);
    ArrayResize (cMain, coords);
    f     = -DBL_MAX;
    fMain = -DBL_MAX;
  }

  double c     []; //coordinates
  double cMain []; //coordinates
  double f;        //fitness
  double fMain;    //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Además, la diferencia entre las dos variantes radica en los cambios introducidos en el método "Revision":

1. En la versión principal, el intercambio de experiencias entre agentes se realizará a nivel de grupo. En el ciclo "for" interno, se seleccionará un grupo al azar y el valor de las coordenadas del agente actual se sustituirá por el valor de las coordenadas del centro del grupo seleccionado. De esta forma, los grupos compartirán experiencias usando la transferencia de experiencias a una sola partícula del grupo respectivo.

2. En la segunda variante, el intercambio de experiencia entre agentes tendrá lugar al nivel de toda la población, es decir, entre partículas de grupos en caso de que la partícula seleccionada para el intercambio tenga una aptitud superior. De este modo, la experiencia solo podrá transmitirse de las mejores a las peores partículas entre grupos, quedando la mejor experiencia a disposición de la partícula. En el ciclo interno "for", se seleccionará un agente al azar, y con cierta probabilidad (determinada por el valor "copyProb") el valor de coordenadas del agente actual se sustituirá por el valor de coordenadas del agente seleccionado en la población.

Además, la segunda variante tiene un bloque extra de código que actualiza los agentes. Si el valor de la función de aptitud del agente actual supera su mejor valor anterior (f > fMain), los valores de las coordenadas del agente actual se actualizarán con los valores de su mejor solución actual (cMain). Esto permite a los agentes conservar y usar sus mejores soluciones en el futuro.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ESG::Revision ()
{
  //----------------------------------------------------------------------------
  //Update the best global solution
  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB)
    {
      fB = a [i].f;
      ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  //update agents
  for (int p = 0; p < popSize; p++)
  {
    if (a [p].f > a [p].fMain)
    {
      a [p].fMain = a [p].f;
      ArrayCopy (a [p].cMain, a [p].c, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  int cnt = 0;
  bool impr = false;

  for (int s = 0; s < groups; s++)
  {
    impr = false;

    for (int p = 0; p < gr [s].sSize; p++)
    {
      if (a [cnt].f > gr [s].fB)
      {
        gr [s].fB = a [cnt].f;
        ArrayCopy (gr [s].cB, a [cnt].c, 0, 0, WHOLE_ARRAY);
        impr = true;
      }

      cnt++;
    }

    if (!impr) gr [s].sRadius *= expansionRatio;
    else       gr [s].sRadius  = groupRadius;

    if (gr [s].sRadius > 0.5) gr [s].sRadius = 0.5;
  }

  //generate individuals of groups----------------------------------------------
  double coordinate = 0.0;
  double radius     = 0.0;
  double min        = 0.0;
  double max        = 0.0;
  cnt = 0;

  for (int s = 0; s < groups; s++)
  {
    for (int p = 0; p < gr [s].sSize; p++)
    {
      for (int c = 0; c < coords; c++)
      {
        if (RNDfromCI (0.0, 1.0) < 0.6)
        {
        radius        = (rangeMax [c] - rangeMin [c]) * gr [s].sRadius;
        min           = gr [s].cB [c] - radius;
        max           = gr [s].cB [c] + radius;

        if (min < rangeMin [c]) min = rangeMin [c];
        if (max > rangeMax [c]) max = rangeMax [c];

        coordinate    = PowerDistribution (gr [s].cB [c], min, max, power);
        a [cnt].c [c] = SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]);
        }
      }

      cnt++;
    }
  }

  //exchange of experience----------------------------------------------------------------
  cnt = 0;

  for (int p = 0; p < popSize; p++)
  {
    for (int c = 0; c < coords; c++)
    {
      int pos = (int)RNDfromCI (0, popSize);
      if (pos >= popSize) pos = popSize - 1;

      if (RNDfromCI(0.0, 1.0) < copyProb)
      {
        if (a [pos].fMain > a [p].fMain)
        {
          a [p].c [c] = a [pos].cMain [c];
        }
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Tras experimentar y probar la segunda versión del algoritmo, el resultado global no ha progresado como se esperaba, empeorando ligeramente. Esto puede explicarse por el hecho de que resulta importante mantener la experiencia de las partículas exactamente dentro de los límites de sus propios grupos y evitar una mezcla completa de ideas entre grupos. Hay que preservar la experiencia única de cada grupo y garantizar que solo se comparta de forma parcial.

Debemos señalar que un resultado fallido del experimento no es definitivo y no significa que sea imposible mejorar el algoritmo. Esto no es más que un intento que nos permite hacernos una idea de los aspectos que debemos considerar y las estrategias que es mejor aplicar. Con más investigación y desarrollo, podremos utilizar estos conocimientos para crear nuevas variantes del algoritmo que pueden dar lugar a mejoras significativas en las capacidades de búsqueda. Es importante seguir siendo optimista y perseverante en la consecución de nuestros objetivos. A continuación le resumimos los resultados de las pruebas.

3. Resultados de las pruebas

Impresión del funcionamiento de la variante principal del algoritmo de evolución de grupos sociales ESG en el banco de pruebas:

C_AO_ESG|200|100|0.1|2.0|10.0
=============================
5 Hilly's; Func runs: 10000; result: 0.9990564816911227
25 Hilly's; Func runs: 10000; result: 0.7965424362150277
500 Hilly's; Func runs: 10000; result: 0.35055904999599663
=============================
5 Forest's; Func runs: 10000; result: 1.0
25 Forest's; Func runs: 10000; result: 0.8286255415345216
500 Forest's; Func runs: 10000; result: 0.13102081222227177
=============================
5 Megacity's; Func runs: 10000; result: 0.8233333333333333
25 Megacity's; Func runs: 10000; result: 0.5529999999999999
500 Megacity's; Func runs: 10000; result: 0.04724999999999998
=============================
All score: 5.52939 (61.44%)

Impresión del funcionamiento de una variante del algoritmo de evolución de grupos sociales ESG con una ligera modificación en el banco de pruebas:

C_AO_MPSO|200|100|0.1|1.1|10.0|1.0
=============================
5 Hilly's; Func runs: 10000; result: 0.9986983861349696
25 Hilly's; Func runs: 10000; result: 0.7971379560351051
500 Hilly's; Func runs: 10000; result: 0.3351159723676586
=============================
5 Forest's; Func runs: 10000; result: 1.0
25 Forest's; Func runs: 10000; result: 0.8288612676775615
500 Forest's; Func runs: 10000; result: 0.11374411604788078
=============================
5 Megacity's; Func runs: 10000; result: 0.8333333333333333
25 Megacity's; Func runs: 10000; result: 0.5116666666666667
500 Megacity's; Func runs: 10000; result: 0.049316666666666654
=============================
All score: 5.46787 (60.75%)

En la visualización del funcionamiento del banco de pruebas, observamos una buena convergencia de la versión principal del algoritmo. En las funciones de prueba "Hilly" y "Forest", se aprecia una ligera dispersión de las trayectorias en el gráfico de convergencia. Sin embargo, en la función "Megacity" esta dispersión resulta bastante grande, aunque la mayoría de los algoritmos en esta función de prueba también muestran una amplia dispersión de la convergencia. El algoritmo "prefiere", a diferencia de la mayoría de los presentados anteriormente, un tamaño de población mucho mayor: 200 (normalmente se usa 50), a pesar de que el número de épocas se reduce proporcionalmente. El ESG es bueno en la elaboración de extremos locales; esta propiedad está influenciada por la "naturaleza" multipoblacional del algoritmo.

  ESG en la función de prueba Hilly.

  ESG en la función de prueba Forest.

  ESG en la función de prueba Megacity.

El algoritmo ESG ha mostrado unos resultados decentes, situándose entre los líderes de la tabla de clasificación. Podemos observar una convergencia del 100% en la función Forest con 10 parámetros y una convergencia casi completa, del 99,9%, en la función Hilly con 10 parámetros. La tabla incluye los resultados de la versión principal del algoritmo, mientras que la versión experimental se encuentra en la carpeta "variant2".

№	AO	Description	Hilly			Hilly final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result	% de MAX
			10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)
1	BGA	binary genetic algorithm	0,99992	0,99484	0,50483	2,49959	1,00000	0,99975	0,32054	2,32029	0,90667	0,96400	0,23035	2,10102	6,921	76,90
2	(P+O)ES	(P+O) evolution strategies	0,99934	0,91895	0,56297	2,48127	1,00000	0,93522	0,39179	2,32701	0,83167	0,64433	0,21155	1,68755	6,496	72,18
3	SDSm	stochastic diffusion search M	0,93066	0,85445	0,39476	2,17988	0,99983	0,89244	0,19619	2,08846	0,72333	0,61100	0,10670	1,44103	5,709	63,44
4	ESG	evolution of social groups	0,99906	0,79654	0,35056	2,14616	1,00000	0,82863	0,13102	1,95965	0,82333	0,55300	0,04725	1,42358	5,529	61,44
5	SIA	simulated isotropic annealing	0,95784	0,84264	0,41465	2,21513	0,98239	0,79586	0,20507	1,98332	0,68667	0,49300	0,09053	1,27020	5,469	60,76
6	DE	differential evolution	0,95044	0,61674	0,30308	1,87026	0,95317	0,78896	0,16652	1,90865	0,78667	0,36033	0,02953	1,17653	4,955	55,06
7	HS	harmony search	0,86509	0,68782	0,32527	1,87818	0,99999	0,68002	0,09590	1,77592	0,62000	0,42267	0,05458	1,09725	4,751	52,79
8	SSG	saplings sowing and growing	0,77839	0,64925	0,39543	1,82308	0,85973	0,62467	0,17429	1,65869	0,64667	0,44133	0,10598	1,19398	4,676	51,95
9	(PO)ES	(PO) evolution strategies	0,79025	0,62647	0,42935	1,84606	0,87616	0,60943	0,19591	1,68151	0,59000	0,37933	0,11322	1,08255	4,610	51,22
10	ACOm	ant colony optimization M	0,88190	0,66127	0,30377	1,84693	0,85873	0,58680	0,15051	1,59604	0,59667	0,37333	0,02472	0,99472	4,438	49,31
11	BFO-GA	bacterial foraging optimization - ga	0,89150	0,55111	0,31529	1,75790	0,96982	0,39612	0,06305	1,42899	0,72667	0,27500	0,03525	1,03692	4,224	46,93
12	MEC	mind evolutionary computation	0,69533	0,53376	0,32661	1,55569	0,72464	0,33036	0,07198	1,12698	0,52500	0,22000	0,04198	0,78698	3,470	38,55
13	IWO	invasive weed optimization	0,72679	0,52256	0,33123	1,58058	0,70756	0,33955	0,07484	1,12196	0,42333	0,23067	0,04617	0,70017	3,403	37,81
14	Micro-AIS	micro artificial immune system	0,79547	0,51922	0,30861	1,62330	0,72956	0,36879	0,09398	1,19233	0,37667	0,15867	0,02802	0,56335	3,379	37,54
15	COAm	cuckoo optimization algorithm M	0,75820	0,48652	0,31369	1,55841	0,74054	0,28051	0,05599	1,07704	0,50500	0,17467	0,03380	0,71347	3,349	37,21
16	SDOm	spiral dynamics optimization M	0,74601	0,44623	0,29687	1,48912	0,70204	0,34678	0,10944	1,15826	0,42833	0,16767	0,03663	0,63263	3,280	36,44
17	NMm	Nelder-Mead method M	0,73807	0,50598	0,31342	1,55747	0,63674	0,28302	0,08221	1,00197	0,44667	0,18667	0,04028	0,67362	3,233	35,92
18	FAm	firefly algorithm M	0,58634	0,47228	0,32276	1,38138	0,68467	0,37439	0,10908	1,16814	0,28667	0,16467	0,04722	0,49855	3,048	33,87
19	GSA	gravitational search algorithm	0,64757	0,49197	0,30062	1,44016	0,53962	0,36353	0,09945	1,00260	0,32667	0,12200	0,01917	0,46783	2,911	32,34
20	BFO	bacterial foraging optimization	0,61171	0,43270	0,31318	1,35759	0,54410	0,21511	0,05676	0,81597	0,42167	0,13800	0,03195	0,59162	2,765	30,72
21	ABC	artificial bee colony	0,63377	0,42402	0,30892	1,36671	0,55103	0,21874	0,05623	0,82600	0,34000	0,14200	0,03102	0,51302	2,706	30,06
22	BA	bat algorithm	0,59761	0,45911	0,35242	1,40915	0,40321	0,19313	0,07175	0,66810	0,21000	0,10100	0,03517	0,34617	2,423	26,93
23	SA	simulated annealing	0,55787	0,42177	0,31549	1,29513	0,34998	0,15259	0,05023	0,55280	0,31167	0,10033	0,02883	0,44083	2,289	25,43
24	IWDm	intelligent water drops M	0,54501	0,37897	0,30124	1,22522	0,46104	0,14704	0,04369	0,65177	0,25833	0,09700	0,02308	0,37842	2,255	25,06
25	PSO	particle swarm optimisation	0,59726	0,36923	0,29928	1,26577	0,37237	0,16324	0,07010	0,60572	0,25667	0,08000	0,02157	0,35823	2,230	24,77
26	MA	monkey algorithm	0,59107	0,42681	0,31816	1,33604	0,31138	0,14069	0,06612	0,51819	0,22833	0,08567	0,02790	0,34190	2,196	24,40
27	SFL	shuffled frog-leaping	0,53925	0,35816	0,29809	1,19551	0,37141	0,11427	0,04051	0,52618	0,27167	0,08667	0,02402	0,38235	2,104	23,38
28	FSS	fish school search	0,55669	0,39992	0,31172	1,26833	0,31009	0,11889	0,04569	0,47467	0,21167	0,07633	0,02488	0,31288	2,056	22,84
29	RND	random	0,52033	0,36068	0,30133	1,18234	0,31335	0,11787	0,04354	0,47476	0,25333	0,07933	0,02382	0,35648	2,014	22,37
30	GWO	grey wolf optimizer	0,59169	0,36561	0,29595	1,25326	0,24499	0,09047	0,03612	0,37158	0,27667	0,08567	0,02170	0,38403	2,009	22,32
31	CSS	charged system search	0,44252	0,35454	0,35201	1,14907	0,24140	0,11345	0,06814	0,42299	0,18333	0,06300	0,02322	0,26955	1,842	20,46
32	EM	electroMagnetism-like algorithm	0,46250	0,34594	0,32285	1,13129	0,21245	0,09783	0,10057	0,41085	0,15667	0,06033	0,02712	0,24412	1,786	19,85

Conclusiones

En conclusión, el algoritmo de evolución de grupos sociales es un método de optimización eficaz basado en la cooperación y el intercambio de experiencias entre grupos. Posee las propiedades de adaptabilidad y diversidad, y es capaz de encontrar soluciones óptimas en diversos problemas de optimización.

Puedo recomendar el algoritmo ESG para aplicaciones en diversos campos en los que se requiera la optimización de parámetros. Por ejemplo, puede usarse para ajustar hiperparámetros en el aprendizaje automático, optimizar funciones en problemas de control óptimo, resolver problemas de optimización combinatoria y otros problemas en los que sea necesario encontrar los valores óptimos de los parámetros.

El algoritmo presentado puede considerarse una especie de plantilla, que puede complementarse con las diversas técnicas y estrategias de búsqueda individuales descritas en artículos anteriores. Además, cada grupo puede usar algoritmos de optimización distintos, como PSO, ABC, ACO, etc. Así, la arquitectura del algoritmo ESG garantiza que estos métodos de optimización puedan aplicarse y usarse juntos con facilidad, combinando las ventajas de cada algoritmo por separado.

Debemos destacar que el ESG es una solución autónoma con buenos resultados y supone un planteamiento extremadamente flexible para resolver problemas complejos. Todo su potencial puede realizarse usando la experimentación y el desarrollo de la idea básica: las oportunidades para ello están abiertas a todos los interesados.

Figura 2. Gradación por colores de los algoritmos según sus respectivas pruebas. Los resultados superiores o iguales a 0,99 aparecen resaltados en blanco.

Figura 3. Histograma con los resultados de las pruebas de los algoritmos (en una escala de 0 a 100, cuanto mayor, mejor),

donde 100 es el máximo resultado teórico posible; hay un script para calcular la tabla de puntuación en el archivo).

Ventajas y desventajas del algoritmo de evolución de grupos sociales (ESG):

Ventajas:

1. Arquitectura sencilla.
   
2. Alta convergencia.
3. No resulta exigente desde el punto de vista computacional.

Desventajas:

1. Bajos resultados en funciones con un gran número de parámetros.
   

Adjuntamos al artículo un archivo con las versiones reales actualizadas de los códigos de los algoritmos descritos en los artículos anteriores. El autor de este artículo no se responsabiliza de la exactitud absoluta de la descripción de los algoritmos canónicos, muchos de ellos han sido modificados para mejorar las capacidades de búsqueda. Las conclusiones y juicios presentados en los artículos se basan en los resultados de los experimentos realizados.