Algoritmos de optimización de la población: Algoritmos de estrategias evolutivas (Evolution Strategies, (μ,λ)-ES y (μ+λ)-ES)

Contenido:

1. Introducción
2. Descripción del algoritmo
3. Sustitución de la función de prueba
4. Resultados de la prueba
5. Conclusiones

1. Introducción

Los algoritmos de estrategias evolutivas (Evolution Strategies) son métodos de optimización basados en principios observados en la naturaleza. Estos imitan el proceso de selección natural, en el que las mejores soluciones sobreviven y transmiten sus características a la siguiente generación. Estos algoritmos se utilizan ampliamente en problemas de optimización, sobre todo en los campos del aprendizaje automático y la inteligencia artificial, y fueron desarrollados en la década de 1960 por el profesor Ingo Rechenberg y sus colegas en Alemania para resolver problemas de optimización en la industria y la ingeniería.

La idea básica de las estrategias evolutivas es crear una población de soluciones y luego mejorarlas usando operadores de mutación y selección similares a los utilizados en la evolución natural. Las estrategias evolutivas utilizan vectores reales para representar las decisiones. Esto permite realizar una descripción más flexible y precisa del espacio de soluciones y la búsqueda de valores óptimos, a diferencia del algoritmo genético clásico, que opera con cadenas binarias.

Existen diversas variantes de estrategias evolutivas, que difieren en la forma de generar y procesar la población, así como en los operadores de mutación y selección usados. Algunas de las opciones más comunes son:

1. (1+1)-ES: En esta variante, solo se crea un descendiente para cada progenitor, y la mejor solución de las dos se convierte en el progenitor de la siguiente generación. Este método sencillo y rápido puede resultar eficaz para algunas tareas, pero menos efectivo a la hora de optimizar problemas complejos. El algoritmo (1+1)-ES se creó en los años 60 y es uno de los métodos más simples para optimizar usando estrategias evolutivas. Consiste en generar un vector aleatorio que luego se modifica utilizando un paso aleatorio. Si el vector modificado resulta mejor, sustituirá al vector original; de lo contrario, el vector original permanecerá inalterado. Este proceso se repetirá hasta alcanzar un nivel óptimo.

1. (μ,λ)-ES: En este algoritmo, se crea una población de padres de tamaño μ, que generan λ descendientes, y los mejores descendientes sustituirán a los padres. Puede resultar eficaz en diversos problemas de optimización. El algoritmo (μ,λ)-ES fue creado por Reinhard Spiegelmann en 1965. Tras evaluar a los descendientes, solo quedan las mejores μ soluciones para convertirse en padres de la siguiente generación, por lo que los padres son sustituidos completamente por descendientes en cada época.

1. (μ+λ)-ES: En esta variante, se crean λ descendientes y los mejores de ellos participan con sus padres en la creación de la siguiente generación. En este método, padres e hijos compiten entre sí, lo cual supone una diferencia importante respecto a (μ,λ)-ES. El algoritmo (μ+λ)-ES fue creado en los años 70 por Johannes Reichenbächer y Hans-Paul Schwefel y es un método de optimización mediante estrategias evolutivas. Este método permite una exploración más completa del espacio de soluciones y puede resultar más eficaz para problemas complejos.

Existen otras variantes de estrategias evolutivas, pero en este artículo solo consideraremos (μ,λ)-ES y (μ+λ)-ES. La variante (1+1)-ES es simple y no resulta adecuada para resolver problemas multivariantes. Debido a las dificultades para usar letras griegas y caracteres especiales en los nombres de archivos y variables del código, en adelante utilizaremos la grafía PO y P_O respectivamente, donde P significa padres y O hijos.

Las estrategias evolutivas en informática permiten modelar procesos de evolución y selección natural para resolver problemas complejos de optimización. Usan principios similares a la selección natural para buscar soluciones óptimas en el espacio de parámetros.

Estos algoritmos pueden resultar especialmente útiles en problemas en los que no existe una solución analítica explícita o cuando el espacio de búsqueda es muy grande. Pueden buscar soluciones óptimas de forma eficaz aplicando operaciones de inspiración evolutiva como el cruce, las mutaciones y la selección.

Debemos señalar que el nombre "estrategias evolutivas" puede inducir a error al dar a entender que se trata de un nombre genérico para una clase de algoritmos evolutivos, sin embargo, este no es el caso. De hecho, se trata de un grupo particular de algoritmos que usan las ideas de la evolución para resolver problemas de optimización.

2. Descripción del algoritmo

(μ,λ)-ES significa que en cada iteración del algoritmo se seleccionan μ padres y se generan λ descendientes. Luego se seleccionan los mejores μ de λ descendientes, que se convertirán en los padres de la siguiente iteración. Así, en (μ,λ)-ES, los nuevos descendientes sustituirán completamente a los padres y participarán en la siguiente generación.

(μ+λ)-ES funciona de forma similar, pero en lugar de seleccionar los mejores descendientes de λ, se combinarán con sus progenitores para formar una nueva población de tamaño μ+λ. Los mejores μ individuos se seleccionarán de esta población combinada para convertirse en padres en la siguiente iteración. Así, en (μ+λ)-ES, los nuevos descendientes colaborarán con sus progenitores para formar la siguiente población y competirán entre sí.

La principal diferencia entre (μ,λ)-ES y (μ+λ)-ES reside en cómo compiten los nuevos descendientes con sus padres por un puesto en la siguiente población. En (μ,λ)-ES, los nuevos descendientes compiten con sus padres por un número limitado de plazas, lo cual puede llevar a una convergencia prematura a un óptimo local. En (μ+λ)-ES, los nuevos descendientes trabajan junto con los padres, lo cual lleva a una exploración más amplia del espacio de soluciones.

Ambos algoritmos de estrategia evolutiva se basan en una combinación de operadores genéticos: la mutación y la selección. En cada iteración del algoritmo, se selecciona un individuo de la población actual y se le aplica un operador de mutación, tras lo cual se calcularán las adaptaciones para el individuo resultante y el individuo mejor adaptado se colocará en la siguiente población. Para generar la población inicial, se especificará un intervalo para cada componente del vector de parámetros variables y se supondrá que los valores iniciales de los componentes se distribuyen uniformemente en el intervalo especificado. El algoritmo puede usar diferentes condiciones de parada, como alcanzar un número determinado de generaciones, un determinado estado de la población o un determinado nivel de convergencia. En el caso del algoritmo (μ+λ), todos los individuos se incluirán en la población, mientras que en el caso del algoritmo (μ,λ), solo se incluirán los descendientes. Para el algoritmo (μ+λ) se demuestra la convergencia en probabilidad, mientras que para el algoritmo (μ,λ) la cuestión de la convergencia sigue abierta.

Una comparación entre el algoritmo (μ+λ) y el algoritmo (μ,λ) muestra que el algoritmo (μ+λ) resulta más económico a la hora de utilizar individuos muy aptos, dejándolos competir con la descendencia. Esto aumenta la intensidad de la búsqueda, pero puede provocar una convergencia prematura a un extremo local. El operador de mutación en el algoritmo de estrategia evolutiva canónica es el único operador evolutivo y usa el algoritmo de mutación gaussiano.

El algoritmo clásico (μ,λ)-ES puede describirse usando el pseudocódigo que vemos a continuación:

1. Inicializar la población inicial con individuos aleatorios.
2. Repetir hasta alcanzar el criterio de parada:
2.1. Cada uno de los μ padres genera λ descendientes en la población actual utilizando el operador de mutación.
2.2. Seleccionar los mejores μ descendientes para formar la siguiente población.
3. Traer de vuelta al mejor individuo de la última población.

El algoritmo clásico (μ+λ)-ES puede describirse usando el siguiente pseudocódigo:

1. Inicializar la población inicial con individuos aleatorios.
2. Repetir hasta alcanzar el criterio de parada:
2.1. Cada uno de los μ padres genera λ descendientes en la población actual utilizando el operador de mutación.
2.2. Combinar progenitores y descendientes para obtener una población combinada de tamaño μ+λ.
2.3. Seleccionar los mejores μ individuos de la población combinada para formar la siguiente población.
3. Traer de vuelta al mejor individuo de la última población.

Antes hemos considerado las variantes clásicas de los dos principales algoritmos de "estrategias evolutivas". En ambos casos, los padres producen λ descendientes usando únicamente su información genética. Esto provoca la ramificación en estrella, en la que cada descendiente se desarrolla independientemente de los demás. Tampoco existe intercambio de información entre los progenitores, lo cual elimina la posibilidad de combinar sus rasgos genéticos. Como resultado, las cualidades combinatorias están completamente ausentes.

Los resultados de las pruebas han mostrado que ambas variantes de ES tienen una eficiencia baja, para mejorarla hemos intentado utilizar la recombinación.

La recombinación permite combinar material genético de distintos individuos para crear nuevas combinaciones que pueden tener mejores propiedades o rasgos, y este proceso fomenta la diversidad de la población.

La recombinación (o cruce) es el proceso de combinar el material genético de los individuos parentales para crear descendencia. El presente proceso imita el mestizaje natural en la evolución biológica. Durante la recombinación, los genes de los padres se combinan para crear nuevo material genético para sus descendientes. La recombinación suele producirse a nivel de genes o rasgos genéticos. Los genes son fragmentos de información en el genoma que codifican propiedades o características concretas de un organismo.

Tras la recombinación, los genes de la descendencia se alterarán usando un operador de mutación, que realizará cambios aleatorios en los genes. Esto ayudará a introducir nuevas variantes de estudio en la población y fomentará la diversidad del material genético.

Por consiguiente, para cada gen descendiente utilizaremos los genes de progenitores elegidos al azar, donde los genes serán las coordenadas correspondientes del progenitor. De este modo, la descendencia heredará los rasgos de todos los progenitores de la población.

Algoritmo (μ,λ)-ES.

Vamos ahora a revisar el código: empezaremos con el algoritmo más sencillo (μ,λ)-ES modificado añadiendo la recombinación (herencia de genes de múltiples progenitores).

Para un padre y un descendiente que actúan como agente, la estructura S_Agent, que contiene un array de coordenadas "c" y una variable "f", el valor de adaptabilidad, será un buen ajuste. La función "Init" inicializa el agente cambiando el tamaño del array "c" y estableciendo el valor de "f" en "-DBL_MAX" (el peor valor de aptitud posible).

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

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

Para describir el algoritmo (μ,λ)-ES, declararemos la clase C_AO_POES,

La clase contiene los siguientes elementos:

• Las variables públicas "cB", "fB", "a", "rangeMax", "rangeMin", "rangeStep": estas variables se utilizan para almacenar la mejor coordenada, el valor correspondiente de la función de aptitud, los agentes, los valores máximo y mínimo de búsqueda y el paso de búsqueda, respectivamente.
• "Init()" pública: esta función inicializa el algoritmo de optimización. Toma varios argumentos, como el número de coordenadas, el tamaño de la población, el número de agentes padres, la fuerza de mutación y el valor sigma. Dentro de la función, se inicializan las variables y arrays usados en el algoritmo.
• Las funciones públicas "Moving()" y "Revision()": estas funciones se utilizan para realizar el movimiento de agentes y la revisión de la población respectivamente.
• Las variables privadas "coords", "popSize", "parentsNumb", "mutationPower", "sigmaM", "revision": estas variables se utilizan para almacenar el número de coordenadas, el tamaño de la población, el número de agentes padres, el poder de mutación, el valor sigma y la bandera de revisión respectivamente.
• Los arrays privados "parents", "ind", "val", "pTemp": estos arrays se utilizan para almacenar información de los agentes padre, índices, valores y variables temporales respectivamente.
• Las funciones privadas GaussDistribution(), SeInDiSp(), RNDfromCI(), Scale(), Sorting(): estas funciones se utilizan para generar números aleatorios, escalar valores y ordenar arrays.

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

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

  public: void Init (const int    coordsP,          //coordinates number
                     const int    popSizeP,         //population size
                     const int    parentsP,         //number of parents, < Population size
                     const double mutationPowerP,   //mutation power
                     const double sigmaP);          //sigma

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

  //----------------------------------------------------------------------------
  private: int    coords;        //coordinates number
  private: int    popSize;       //population size
  private: int    parentsNumb;   //number of parents
  private: double mutationPower; //mutation power
  private: double sigmaM;
  private: bool   revision;

  private: S_Agent parents [];  //parents
  private: int     ind     [];
  private: double  val     [];
  private: S_Agent pTemp   [];

  private: double GaussDistribution   (const double In, const double outMin, const double outMax, const double sigma);
  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: void   Sorting   (S_Agent &p [], int size);
};
//——————————————————————————————————————————————————————————————————————————————

La función "Init" de la clase C_AO_POES se usa para inicializar el algoritmo de optimización. La función toma varios argumentos: número de coordenadas, tamaño de la población, número de agentes padres, fuerzas de mutación y valor sigma.

Dentro de la función, se inicializan las variables y arrays usados en el algoritmo. La función realiza las acciones siguientes:

• reinicia el generador de números aleatorios y establece el valor de la variable "fB" en "-DBL_MAX". 
• establece los valores de las variables "coords", "popSize", "parentsNumb", "mutationPower" y "sigmaM". 
• cambia el tamaño de las arrays "ind", "val", "pTemp", "a", "parents", "rangeMax", "rangeMin", "rangeStep" y "cB" usando la función "ArrayResize". 
• Los arrays "a" y "parents" se inicializan usando la función "Init" de la clase "S_Agent", que inicializa las coordenadas del agente y establece el valor de la variable "f" en "-DBL_MAX".

//——————————————————————————————————————————————————————————————————————————————
void C_AO_POES::Init (const int    coordsP,          //coordinates number
                      const int    popSizeP,         //population size
                      const int    parentsP,         //number of parents, < Population size
                      const double mutationPowerP,   //mutation power
                      const double sigmaP)           //sigma
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords        = coordsP;
  popSize       = popSizeP;
  parentsNumb   = parentsP;
  mutationPower = mutationPowerP;
  sigmaM        = sigmaP;

  ArrayResize (ind,   popSize);
  ArrayResize (val,   popSize);
  ArrayResize (pTemp, popSize);
  ArrayResize (a,     popSize);
  for (int i = 0; i < popSize; i++) a [i].Init (coords);

  ArrayResize (parents, parentsNumb);
  for (int i = 0; i < parentsNumb; i++) parents [i].Init (coords);

  ArrayResize (rangeMax,  coords);
  ArrayResize (rangeMin,  coords);
  ArrayResize (rangeStep, coords);
  ArrayResize (cB,        coords);
}
//——————————————————————————————————————————————————————————————————————————————

El método "Moving" está pensado para mover agentes en el espacio de búsqueda.

La función contiene dos bloques de código separados por la condición "if (!revision)".

1. El primer bloque genera coordenadas aleatorias para cada agente en caso de que la bandera de revisión "revision" sea igual a "false". Para cada coordenada, se genera un número aleatorio con una distribución uniforme entre "rangeMin" y "rangeMax". A continuación, dicho número se normaliza usando la función "SeInDiSp", que establece el valor de la coordenada en el valor más cercano que sea múltiplo de "rangeStep".
2. El segundo bloque ejecuta el movimiento del agente si la bandera de revisión "revision" es "true". Para cada agente, se selecciona un agente padre aleatorio del array "parents". A continuación, para cada coordenada de agente, se calcula el valor de mutación "dist", que dependerá de la potencia de mutación "mutationPower" y del rango de búsqueda "rangeMin" y "rangeMax". El valor de coordenadas del agente se modifica usando la función "GaussDistribution", que genera un número aleatorio con una distribución normal alrededor del valor de coordenadas padre utilizando el valor sigma "sigmaM". A continuación, el valor de las coordenadas se normaliza usando la función "SeInDiSp".
   

//——————————————————————————————————————————————————————————————————————————————
void C_AO_POES::Moving ()
{
  //----------------------------------------------------------------------------
  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  int    indx = 0;
  double min  = 0.0;
  double max  = 0.0;
  double dist = 0.0;

  for (int i = 0; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      indx = (int)RNDfromCI (0, parentsNumb);
      if (indx >= parentsNumb) indx = parentsNumb - 1;

      a [i].c [c] = parents [indx].c [c];

      dist = (rangeMax [c] - rangeMin [c]) * mutationPower;

      min = a [i].c [c] - dist; if (min < rangeMin [c]) min = rangeMin [c];
      max = a [i].c [c] + dist; if (max > rangeMax [c]) max = rangeMax [c];

      a [i].c [c] = GaussDistribution (a [i].c [c], min, max, sigmaM);
      a [i].c [c] = SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

La revisión de la población se realiza usando el método "Revision", que se utiliza para revisar el estado actual de los agentes en el algoritmo de optimización.

La función contiene dos bloques de código.

1. El primer bloque busca el mejor agente en el array "a" usando un ciclo "for". Si encontramos un agente con un valor de aptitud mayor que el mejor agente actual "fB", el índice de este agente se almacenará en la variable "indx". A continuación, el valor de "fB" y las coordenadas de "cB" del mejor agente actual se actualizarán en función del nuevo mejor agente.
2. El segundo bloque clasifica el array "a" en orden descendente de adaptabilidad utilizando la función "Sorting", y luego copia los "parentsNumb" de los mejores agentes del array "a" al array "parents".

Así, la función "Revision" permite actualizar el estado actual de los agentes y almacenar los mejores agentes en el array "parents", donde los mejores descendientes sustituyen completamente a todos los padres.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_POES::Revision ()
{
  //----------------------------------------------------------------------------
  int indx = -1;

  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB) indx = i;
  }

  if (indx != -1)
  {
    fB = a [indx].f;
    ArrayCopy (cB, a [indx].c, 0, 0, WHOLE_ARRAY);
  }

  //----------------------------------------------------------------------------
  Sorting (a, popSize);
  for (int i = 0; i < parentsNumb; i++)
  {
    parents [i] = a [i];
  }
}
//——————————————————————————————————————————————————————————————————————————————

Algoritmo (μ+λ)-ES.

Los cambios empiezan por añadir la esperanza de vida del individuo como parámetro "yearsNumber". Esto permitirá controlar la edad máxima de la población y evitar que se "atasque" con individuos muy viejos, lo cual puede impedir explorar nuevos horizontes del espacio vital infinito y hacer nuevos descubrimientos. Esperamos que esto resulte útil en este algoritmo.

Por qué no está este contador en el algoritmo "(μ,λ)-ES?" - Porque así se diseñó: para sustituir completamente a los padres por descendientes. También tiene sentido, como ocurre con los semélparos en el reino animal, donde algunas especies solo se reproducen una vez en su vida. Ejemplos de estas especies son los peces salmónidos, los agaves, el bambú, los cangrejos cocoteros y las cigarras. No obstante, en nuestro algoritmo, daremos a los individuos la capacidad de reproducirse varias veces, vivir indefinidamente o morir como un orgulloso bambú. La duración de vida puede ser un parámetro externo ajustable, y nuestras pruebas ha constatado experimentalmente una duración óptima de 10 años.

Además, un contador de vidas puede ayudar a evitar el "sobreentrenamiento" del modelo, en el que la población empieza a "memorizar" y acumular soluciones específicas en lugar de encontrar nuevas soluciones satisfactorias en otros lugares del espacio de búsqueda. Limitar la esperanza de vida de los individuos preserva la diversidad de la población y nos permite seguir buscando mejores soluciones.

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

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

En el método Init aumentaremos el tamaño de la población de padres por el número de descendientes, esto permitirá ordenar conjuntamente padres y descendientes, aunque al igual que en el algoritmo (μ,λ)-ES, solo se usará la parte μ - de la población conjunta para generar posteriormente nuevos descendientes. Si en el algoritmo anterior el número de padres tenía que ser menor o igual que la población de descendientes, en este algoritmo no importará y se podrá establecer cualquier tamaño de la población de padres, incluso uno muy elevado: esto no afectará al número de épocas. Hemos comprobado experimentalmente que para un tamaño de población de 100 crías, será óptimo tener (no se permiten más, el número de épocas disminuye) una población de padres de 150. Aumentar aún más la población de progenitores provocará demasiada diversidad en el acervo genético y el algoritmo empezará a converger peor (esto es interesante en sí mismo).

ArrayResize (ind,   popSize + parentsNumb);
ArrayResize (val,   popSize + parentsNumb);
ArrayResize (pTemp, popSize + parentsNumb);
ArrayResize (a,     popSize);
for (int i = 0; i < popSize; i++) a [i].Init (coords);

ArrayResize (parents, popSize + parentsNumb);
for (int i = 0; i < popSize + parentsNumb; i++) parents [i].Init (coords);

En el método "moving", al crear nuevos descendientes, pondremos el contador de años del individuo a 1.

a [i].yearsNumber = 1;

También hemos realizado cambios en el método "Revision", donde dados los cambios, el código hace lo siguiente:

• Aumenta en 1 el valor de "yearsNumber" de cada padre.
• Si el valor de "yearsNumber" supera el límite especificado (vida útil), establecerá el valor de aptitud "f" para el progenitor correspondiente en "-DBL_MAX", lo cual significa que el individuo se eliminará de la población.
  
• Copia los nuevos descendientes del array "a" al array de padres "parents".
• Clasifica el array "parents" según el valor de aptitud "f".

//----------------------------------------------------------------------------
for (int i = 0; i < parentsNumb; i++)
{
  parents [i].yearsNumber++;

  if (parents [i].yearsNumber > lifespan)
  {
    parents [i].f = - DBL_MAX;
  }
}

for (int i = parentsNumb; i < parentsNumb + popSize; i++)
{
  parents [i] = a [i - parentsNumb];
}

Sorting (parents, parentsNumb + popSize);

3. Sustitución de la función de prueba

Antes hemos utilizado la función Rastrigin como función de prueba para evaluar algoritmos de optimización. Sin embargo, la función Rastrigin no supone una opción ideal para tales fines. Tiene una periodicidad estricta y unos mínimos y máximos equilibrados que algunos algoritmos pueden detectar con relativa facilidad. Así, la función Rastrigin presenta patrones que pueden influir en la capacidad del algoritmo de identificar los extremos de la función.

Para que las pruebas de los algoritmos de optimización resulten más fiables y objetivas, le recomendamos utilizar funciones con propiedades diversas e impredecibles. Estas funciones no suelen presentar patrones evidentes ni un equilibrio entre mínimos y máximos. Ejemplos de este tipo de funciones son, por ejemplo, las funciones de ruido, las funciones con dependencias no lineales o las funciones con un gran número de extremos locales. Esta elección de características permitirá una evaluación más precisa de la capacidad de los algoritmos para detectar y converger a óptimos globales en distintas condiciones.

Convencionalmente, todas las funciones pueden dividirse en "simples" y "complejas". Las funciones simples son las que tienen la mayor parte de su superficie por encima de la línea media entre el máximo y el mínimo, y cuanto más superficie se halle cerca del máximo, más simple será para los algoritmos de optimización. Así, si simplemente colocamos puntos al azar por toda la superficie en el dominio de la definición de la función, obtendremos una falsa impresión de resultados de optimización "elevados", pues los resultados estarán próximos al máximo global absoluto. Un ejemplo de este tipo de función simple es el dibujo esquemático de la función hipotética de la figura 1.

Figura 1. Ejemplo de función "simple" para algoritmos de optimización.

En vista de lo anterior, la función "Rastrigin" puede clasificarse como una función simple que puede hacer que algunos algoritmos de optimización sobrestimen los resultados. Esto se debe a las peculiaridades de la estrategia de búsqueda de estos algoritmos, que pueden ubicar sus agentes dispersos por toda la superficie de la función.

El efecto se hace especialmente notable en las funciones "Rastrigin" con un gran número de variables, por ejemplo 1 000. Mientras que algunos algoritmos intentan "honestamente" encontrar un extremo global, otros pueden limitarse a colocar los agentes de manera uniforme a lo largo de la superficie de la función. Este planteamiento no habla de la capacidad del algoritmo de optimización para buscar con precisión, sino que solo ofrece la ilusión de poder hacerlo.

Hemos modificado la función "Rastrigin" considerablemente para crear un entorno más complejo y desafiante para los algoritmos de optimización. La nueva versión de la función ha añadido algunas "colinas" y "valles", manteniendo la periodicidad en la parte de la superficie que no ayuda en la búsqueda de un extremo global. Dichos cambios crean obstáculos adicionales, distraen a los agentes y actúan como "trampas".

Ahora no se pueden saltar escalones con periodicidad para llegar a un extremo global, como se podía hacer en la versión clásica de Rastrigin. Además, el óptimo global se ha alejado del borde, lo cual dificulta su localización cuando hay artefactos en los algoritmos, que suelen concentrarse en los límites de la definición de la función.

El nuevo rasgo ha recibido el nombre de "Hilly" (Fig. 2) y, al igual que Forest y Megacity, se refiere a funciones de prueba complejas. Para estas tres funciones, la superficie situada por encima del 50% de la altura máxima será aproximadamente la misma y representa alrededor del 20% de la superficie total de la función.

Las características Hilly, Forest y Megacity presentan escenarios de optimización desafiantes y realistas que pueden ayudar a estimar el rendimiento de los algoritmos en entornos complejos y diversos. Cuando estas funciones se usan como prueba exhaustiva de los algoritmos de optimización, se hace posible comprender mejor su capacidad para encontrar óptimos globales y superar trampas locales.

Además, hemos introducido cambios en la metodología de las pruebas. Ahora se realizan 10 pruebas en lugar de 5 (el número de veces que se repite el proceso de optimización), para reducir los "valores atípicos" aleatorios presentes en los resultados.

Figura 2. Función de prueba "Hilly" (colina).

4. Resultados de la prueba

Impresión del rendimiento del algoritmo (μ,λ)-ES en un banco de pruebas:

C_AO_(PO)ES:100:10:0.025:8.0
=============================
5 Hilly's; Func runs: 10000; result: 0.7902459324049909
25 Hilly's; Func runs: 10000; result: 0.6264667539839893
500 Hilly's; Func runs: 10000; result: 0.42934981087827656
=============================
5 Forest's; Func runs: 10000; result: 0.8761631782479373
25 Forest's; Func runs: 10000; result: 0.6094343681829253
500 Forest's; Func runs: 10000; result: 0.19591138782930953
=============================
5 Megacity's; Func runs: 10000; result: 0.5900000000000001
25 Megacity's; Func runs: 10000; result: 0.37933333333333336
500 Megacity's; Func runs: 10000; result: 0.11321666666666666
=============================
All score: 4.61012

Impresión del rendimiento del algoritmo (μ+λ)-ES en el banco de pruebas:

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
5 Hilly's; Func runs: 10000; result: 0.9993447297882565
25 Hilly's; Func runs: 10000; result: 0.9189524317647721
500 Hilly's; Func runs: 10000; result: 0.562968579605404
=============================
5 Forest's; Func runs: 10000; result: 1.0
25 Forest's; Func runs: 10000; result: 0.9352215748931851
500 Forest's; Func runs: 10000; result: 0.3917923122543615
=============================
5 Megacity's; Func runs: 10000; result: 0.8316666666666664
25 Megacity's; Func runs: 10000; result: 0.6443333333333332
500 Megacity's; Func runs: 10000; result: 0.21155000000000007
=============================
All score: 6.49583

La siguiente visualización corresponde al algoritmo (μ+λ)-ES, que muestra una excelente exploración del espacio de búsqueda sin dejar de lado áreas potencialmente prometedoras.

(μ+λ)-ES en la función de prueba de Hilly.

  (μ+λ)-ES en la función de prueba Forest.

  (μ+λ)-ES en la función de prueba Megacity.

Hemos decidido volver a los valores absolutos en los resultados de las pruebas y abandonar los valores relativos. Para ello, hemos modificado las funciones de prueba para que retornen valores comprendidos entre 0,0 y 1,0. Ahora bien, si el resultado es 1,0, significará un 100% de convergencia, mientras que, por ejemplo, un resultado de 0,32527 significará un 32,5% del máximo global de la función de prueba. Así, como el número total de pruebas es 9, teóricamente los algoritmos podrán mostrar un resultado agregado máximo posible sobre todas las pruebas no superior a 9,0 en el caso de una convergencia del 100% del algoritmo en cada prueba en la columna "Final result" de la tabla. Además, hemos añadido la columna "% of MAX" para mostrar el porcentaje del resultado máximo posible.

Ahora las cifras de resultados no cambiarán al añadir nuevos algoritmos a la tabla, ya que se presentan en valores absolutos.

Así pues, vamos a pasar a los resultados de los algoritmos considerados, en primer lugar (μ+λ)-ES. Este algoritmo me ha impresionado por sus fenomenales resultados: ha obtenido un total del 72,18% del resultado teóricamente posible. Para verificar tan impresionantes resultados, hemos realizado una prueba de 20 veces específicamente para este algoritmo, y cada una de las 20 ejecuciones ha mostrado una convergencia del 100% en la función compleja Forest: ¡es tremendo! Además, los resultados en el resto de las características también han sido fabulosos.

Ahora algunas palabras agradables sobre (μ,λ)-ES. Este algoritmo ha mostrado resultados positivos y estables. En la tabla de colores se muestra como uniformemente "verde", sin cambios bruscos de color.

№	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	(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
2	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
3	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
4	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
5	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
6	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
7	(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
8	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
9	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
10	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
11	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
12	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
13	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
14	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
15	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
16	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
17	BFO	bacterial foraging optimization	0,54626	0,43533	0,31907	1,30066	0,41626	0,23156	0,06266	0,71048	0,35500	0,15233	0,03627	0,54360	2,555	28,39
18	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
19	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
20	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
21	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
22	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
23	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
24	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
25	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
26	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
27	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
28	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

Figura 3. Gradación por colores de los algoritmos según sus respectivas pruebas.

Figura 4. 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).

5. Conclusiones

El uso de estrategias evolutivas abre nuevas oportunidades en diversos campos, como la optimización de parámetros en el aprendizaje automático, el diseño de robots y el control de sistemas complejos. Las estrategias evolutivas permiten obtener mejores soluciones basadas en los principios biológicos de la evolución.

En estos momentos tenemos un nuevo líder indiscutible en la tabla, que supera a su competidor más cercano, SDSm, en casi un 10%.

Ventajas y desventajas del algoritmo de estrategia evolutiva (μ,λ)-ES:

Ventajas:

1. Número reducido de parámetros externos.
2. Alta eficiencia en una gran variedad de tareas.
3. Facilidad de aplicación del algoritmo.
4. Resistencia a atascarse.
5. Buenos resultados en funciones discretas tanto suaves como complejas.
6. Alta convergencia.

Desventajas:

1. Gran variación de resultados sobre funciones discretas.
   

Ventajas y desventajas del algoritmo de estrategia evolutiva (μ+λ)-ES:

Ventajas:

1. Número reducido de parámetros externos.
2. Alta eficiencia en una gran variedad de tareas.
3. Facilidad de aplicación del algoritmo.
4. Resistencia a atascarse.
5. Buenos resultados en funciones discretas tanto suaves como complejas.
6. Alta convergencia.

Desventajas:

1. Gran variación de resultados en funciones discretas (aunque este sea el mejor resultado hasta ahora).

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.