Algoritmo de circulación coronaria artificial — Artificial Coronary Circulation System (ACCS)

Índice

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

Introducción

El algoritmo Artificial Coronary Circulation System (ACCS) es un método de optimización metaheurístico inspirado en la biología. El ACCS imita el crecimiento de las arterias coronarias en el corazón humano. La idea es que cada arteria o capilar constituye una solución candidata, y que todo el proceso de crecimiento del sistema vascular es análogo a la búsqueda de la solución óptima en un espacio complejo de soluciones. El algoritmo fue propuesto por A. Kaveh y M. Kooshkbaghi en 2019, en el artículo «Artificial coronary circulation system: A new bio-inspired metaheuristic algorithm».

Implementación del algoritmo

Imagine que su corazón no es solo una bomba, sino un sabio arquitecto que construye caminos perfectos para la sangre. Cada segundo resuelve un problema de lo más complejo: cómo suministrar la máxima cantidad de oxígeno consumiendo la mínima cantidad de energía. Los científicos se inspiraron en esta estrategia genial y decidieron crear, partiendo de ella, el algoritmo ACCS.

Al principio, el caos. Al igual que en la naturaleza, cuando los capilares empiezan a formarse, ACCS genera una población aleatoria de soluciones. El líder capilar (CL), que comienza a buscar el camino hacia la solución óptima, se evalúa en función del factor de crecimiento coronario (CGF); se trata de una especie de nivel de energía que indica en qué medida está llevando a cabo la tarea con éxito. Cada capilar elige cómo crecer: búsqueda —se extiende hacia delante, como una raíz, con la esperanza de encontrar un suelo fértil—; ramificación —si las condiciones son buenas, crea nuevas ramas, como un árbol que echa brotes—; y poda —si el crecimiento es inútil, se detiene para no malgastar recursos—.

La memoria del corazón. Para no olvidar cuáles fueron las ramas más fuertes, ACCS utiliza Heart Memory (HM), un diario en el que se anotan las mejores soluciones. Estos registros sirven de guía para el crecimiento y ayudan a que los nuevos capilares crezcan en la dirección correcta.

Autoaprendizaje y adaptación. Si el capilar crece en la dirección equivocada, el algoritmo activa la búsqueda local: empieza a excavar a su alrededor, como una raíz que busca agua. Si, de repente, el capilar resulta ser el mejor, se pone en marcha una búsqueda global, como si el árbol hubiera decidido crecer en una nueva dirección.

El ACCS no es mera matemática, sino el arte de aprender de la naturaleza. Su corazón lleva toda la vida resolviendo problemas de optimización de lo más complejos, y ahora los algoritmos pueden aprovechar esa misma sabiduría: explore de forma variada (como las arterias coronarias), recuerde lo mejor (como la memoria del corazón), deje atrás los fracasos (como la poda de los vasos sanguíneos) y mantenga el equilibrio entre la búsqueda global y el ajuste local.

Este algoritmo nos recuerda que, con frecuencia, las mejores soluciones ya se encuentran en la naturaleza. Solo hay que saber detectarlas y aprender de la sabiduría que late en el pecho de cada uno de nosotros. Podemos ver cómo se representa en la ilustración.

Figura 1. Sistema coronario

En la imagen se muestran los elementos principales: una representación esquemática del corazón con las arterias coronarias. La arteria coronaria izquierda (LCA) con sus ramas, la descendente anterior izquierda (LAD) y la circunfleja; la arteria coronaria derecha (RCA); pequeños capilares para ilustrar la búsqueda local; y un patrón de bifurcación (ramificación) en la parte superior derecha.

Conceptos del algoritmo. En la parte inferior se muestra cómo los elementos biológicos se corresponden con los componentes del algoritmo:

Arterias principales → Búsqueda global
Bifurcación → Factor de ramificación
Capilares → Búsqueda local
Flujo sanguíneo → CGF (factor de crecimiento)

Esta representación visual ayuda a comprender cómo el sistema natural de irrigación sanguínea del corazón ha servido de inspiración para crear un algoritmo de optimización, en el que las «arterias» exploran el espacio de soluciones y los «capilares» realizan el ajuste preciso de las soluciones encontradas. Vamos a escribir el pseudocódigo del algoritmo.

Veamos el esquema de funcionamiento del algoritmo.

Figura 2. Diagrama de flujo del algoritmo ACCS

Pasos del algoritmo representados en el diagrama de flujo:

• inicialización de la población de capilares (posiciones aleatorias),
• cálculo de la función de fitness para cada capilar,
• cálculo del factor de crecimiento coronario (CGF),
• búsqueda global (movimiento hacia el centro o alejándose de él),
• búsqueda local (movimiento hacia el mejor agente y alejándose del peor),
• poda (si la nueva posición es peor, volvemos atrás),
• actualización de la memoria del corazón,
• comprobación del criterio de parada.

Ahora ya tenemos más o menos claro cómo debe funcionar todo, así que vamos a ponernos a escribir el código del algoritmo. Tenemos ante nosotros dos estructuras de datos relacionadas, diseñadas para la optimización y el almacenamiento de información sobre las soluciones.

La primera estructura, denominada «Memoria del corazón» (Heart Memory), está destinada al almacenamiento temporal y la evaluación de las mejores soluciones encontradas, y contiene:

• Una posición es un conjunto de valores numéricos que definen una solución concreta, representada por un punto en el espacio de búsqueda. Estos valores pueden considerarse como las coordenadas de esta solución.
• Fitness: valor numérico que indica la «calidad» de la posición correspondiente. Cuanto mayor sea el fitness, mejor será la solución.
• Inicialización: este componente de la estructura permite especificar el tamaño (número de dimensiones) de la posición y establecer el valor inicial del fitness en un nivel extremadamente bajo, de modo que cualquier solución encontrada se considere mejor.

La segunda estructura, denominada «Posición temporal» (TempPosition), se utiliza para almacenar de forma provisional las nuevas soluciones, recién generadas o calculadas, antes de que sean evaluadas y guardadas en la «memoria del corazón»; incluye:

• Las coordenadas —al igual que la «posición» en la primera estructura— son un conjunto de valores numéricos que determinan una solución concreta.
• Fitness: valor numérico que se asignará a esta solución tras su evaluación.
• Inicialización: al igual que en la primera estructura, este componente permite definir el tamaño (número de dimensiones) de las coordenadas y establecer el valor inicial del fitness en un nivel extremadamente bajo hasta que la solución se haya procesado por completo.

//————————————————————————————————————————————————————————————————————
// Estructura para almacenar la memoria del corazón (Heart Memory)
struct S_HeartMemory
{
    double position [];  // posición en la memoria
    double fitness;      // fitness de la posición

    void Init (int dimensions)
    {
      ArrayResize (position, dimensions);
      fitness = -DBL_MAX;
    }
};

// Estructura para el almacenamiento temporal de nuevas posiciones
struct S_TempPosition
{
    double coords [];   // coordenadas
    double fitness;     // fitness
    
    void Init (int dimensions)
    {
      ArrayResize (coords, dimensions);
      fitness = -DBL_MAX;
    }
};
//————————————————————————————————————————————————————————————————————

La clase «C_AO_ACCS» implementa un algoritmo de optimización denominado «Sistema artificial de circulación coronaria» (Artificial Coronary Circulation System, ACCS). Esta clase hereda de la clase base «AO».

Campos públicos (public) de la clase:

• El destructor es una función especial que se ejecuta al destruir un objeto de esta clase, lo que garantiza la liberación de los recursos.
• El constructor es una función que se invoca al crear un nuevo objeto e inicializa los parámetros principales del algoritmo:
  • Establece el tamaño predeterminado de la población (número de «capilares»): 25.
  • Establece el coeficiente de bifurcación por defecto en 0,5.
  • Crea una estructura para almacenar los parámetros modificables y guarda en ella los valores iniciales de «popSize» y «bifurcationRate».
• SetParams () — función para establecer o actualizar los parámetros del algoritmo. Lee los valores actuales de los parámetros enumerados y, además, establece el tamaño de la «memoria del corazón» en el 25 % del tamaño de la población, con un mínimo de 1.
• Init () — función destinada a la inicialización del algoritmo. Recibe información sobre los intervalos de búsqueda, los incrementos y el número de épocas (iteraciones).
• Moving () — función encargada de desplazar o actualizar los agentes (capilares) en el espacio de búsqueda.
• Revision () — función encargada de revisar y corregir las soluciones basándose en la lógica del algoritmo.
• bifurcationRate — coeficiente de bifurcación, que influye en el proceso de generación de nuevas soluciones y en la ramificación de la búsqueda.

Campos privados (private) de la clase:

• CalculateCGF () — función interna para calcular el indicador denominado «CGF» para cada agente.
• CalculateCenterPosition () — función interna para determinar la posición central de la población.
• GlobalSearch () — función interna encargada de la búsqueda global, es decir, de la exploración de una amplia región del espacio de soluciones.
• LocalSearch () — función interna encargada de la búsqueda local, es decir, una exploración más detallada de la zona que rodea las soluciones actuales.
• SelectionPhase () — función interna que implementa la fase de selección, es decir, la elección de las mejores soluciones para su desarrollo posterior.
• UpdateHeartMemory () — función interna para actualizar la «memoria del corazón» con las mejores soluciones encontradas.
• heartMemorySize — número que determina el número máximo de soluciones que se pueden guardar en la «memoria del corazón».
• heartMemory — array de objetos que representan la «memoria del corazón», donde se almacenan las mejores soluciones encontradas.
• tempPos — array de objetos temporales que se utilizan para almacenar nuevas posiciones aún no evaluadas, principalmente para la búsqueda global.
• cgf — array que almacena los valores «CGF» de cada agente de la población.
• cgfCenter — valor escalar que representa el «CGF» del centro de la población.
• centerCoords — array que almacena las coordenadas del centro de la población.
• centerFitness — valor numérico que representa la calidad (fitness) de la posición central.
• alpha — variable que representa un coeficiente relacionado con el proceso de «angiogénesis» (crecimiento y desarrollo).
• currentIteration — variable que registra el número de la iteración (paso) actual del algoritmo.
• maxIterations — variable que establece el número máximo de iteraciones que puede realizar el algoritmo.
• firstIteration — indicador lógico que señala si la iteración actual es la primera.

//————————————————————————————————————————————————————————————————————
class C_AO_ACCS : public C_AO
{
  public: //----------------------------------------------------------
  ~C_AO_ACCS () { }
  C_AO_ACCS ()
  {
    ao_name = "ACCS";
    ao_desc = "Artificial Coronary Circulation System";
    ao_link = "https://www.mql5.com/ru/articles/19861";

    popSize         = 50;    // tamaño de la población (número de capilares)
    bifurcationRate = 0.5;   // coeficiente de bifurcación

    ArrayResize (params, 2);

    params [0].name = "popSize";         params [0].val = popSize;
    params [1].name = "bifurcationRate"; params [1].val = bifurcationRate;
  }

  void SetParams ()
  {
    popSize         = (int)params [0].val;
    bifurcationRate = params      [1].val;
    
    // Tamaño de la memoria del corazón: 25 % de la población
    heartMemorySize = MathMax (1, (int)(popSize * 0.25));
  }

  bool Init (const double &rangeMinP  [],
             const double &rangeMaxP  [],
             const double &rangeStepP [],
             const int     epochsP);

  void Moving   ();
  void Revision ();

  private:
  void CalculateCGF ();
  void CalculateCenterPosition ();
  void GlobalSearch ();
  void LocalSearch ();
  void SelectionPhase ();
  void UpdateHeartMemory ();
  
  //------------------------------------------------------------------
  public:
  double bifurcationRate;   // coeficiente de bifurcación

  private: //---------------------------------------------------------
  int    heartMemorySize;       // tamaño de la memoria del corazón
  S_HeartMemory heartMemory []; // memoria del corazón
  S_TempPosition tempPos [];    // posiciones provisionales para la búsqueda global
  double cgf [];                // array CGF para cada agente
  double cgfCenter;             // CGF del centro
  double centerCoords [];       // coordenadas del centro de la población
  double centerFitness;         // fitness del centro
  double alpha;                 // factor actual de angiogénesis
  int    currentIteration;      // iteración actual
  int    maxIterations;         // número máximo de iteraciones
  bool   firstIteration;        // indicador de la primera iteración
};
//————————————————————————————————————————————————————————————————————

El método de inicialización «Init» de la clase «C_AO_ACCS» está destinado a preparar los parámetros y las estructuras de datos antes de ejecutar el algoritmo de optimización. Acepta los rangos de búsqueda de las variables, los pasos de variación y el número de épocas (iteraciones). El proceso comienza con la llamada a una función de inicialización estándar, que comprueba que los intervalos y los pasos especificados sean correctos. Si esta comprobación falla, la inicialización finaliza con un error.

A continuación, se establece el tamaño de la «memoria del corazón» en el 25 % del tamaño de la población, con un mínimo de un elemento. A partir de este tamaño, se crea un array de estructuras «memoria del corazón» y a cada elemento se le asignan parámetros iniciales en forma de «coordenadas» (identificadas como coords). Luego se crea un array de posiciones temporales, de un tamaño igual al de la población, para almacenar las nuevas soluciones que se generarán en la siguiente fase. A cada elemento de este array se le asignan también unos parámetros iniciales.

Asimismo, se inicializan los arrays para almacenar los valores de CGF de cada agente y las coordenadas del centro de la población. La secuencia finaliza estableciendo la iteración actual en cero, fijando el número máximo de iteraciones según los parámetros de entrada, estableciendo el indicador de la primera iteración en «verdadero» y asignando el valor inicial al factor de angiogénesis («alpha»). En definitiva, tras ejecutar este método, el algoritmo dispone de todas las estructuras y los parámetros necesarios para iniciar la optimización.

//————————————————————————————————————————————————————————————————————
//--- Inicialización
bool C_AO_ACCS::Init (const double &rangeMinP  [],
                      const double &rangeMaxP  [],
                      const double &rangeStepP [],
                      const int     epochsP)
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //------------------------------------------------------------------
  // Tamaño de la memoria del corazón: 25 % de la población
  heartMemorySize = MathMax (1, (int)(popSize * 0.25));
  
  // Inicialización de la memoria del corazón
  ArrayResize (heartMemory, heartMemorySize);
  for (int i = 0; i < heartMemorySize; i++)
  {
    heartMemory [i].Init (coords);
  }

  // Inicialización de posiciones temporales
  ArrayResize (tempPos, popSize);
  for (int i = 0; i < popSize; i++)
  {
    tempPos [i].Init (coords);
  }

  // Inicialización de arrays
  ArrayResize (cgf, popSize);
  ArrayResize (centerCoords, coords);
  
  currentIteration = 0;
  maxIterations = epochsP;
  firstIteration = true;
  alpha = 0.625;

  return true;
}
//————————————————————————————————————————————————————————————————————

El método «CalculateCGF» está diseñado para calcular los coeficientes de crecimiento (CGF) de cada agente de la población, con el fin de evaluar su contribución al desarrollo del sistema.

El proceso comienza con la determinación de los valores mínimo y máximo de fitness entre todas las soluciones. Si todos los valores de fitness son iguales, a cada agente se le asigna el mismo CGF, igual a 1 dividido entre el número total de agentes, para garantizar un trato igualitario. Si, por el contrario, los valores de fitness son distintos, el fitness de cada agente se normaliza teniendo en cuenta los valores mínimo y máximo, y se añade un pequeño desplazamiento al resultado para estabilizar los cálculos. A continuación, se calcula la suma de todos los valores de fitness normalizados. A cada agente se le asigna un CGF proporcional a su fitness ajustado con respecto a la suma. De forma análoga, se calcula el CGF para el centro de la población.

Este método garantiza una distribución ponderada de la influencia de cada solución en las etapas posteriores del algoritmo en función de su calidad.

//————————————————————————————————————————————————————————————————————
//--- Cálculo del CGF (factor de crecimiento coronario) según la Ley 2
void C_AO_ACCS::CalculateCGF ()
{
  // Para maximizar: CGFi = fiti / Σfiti
  
  double minFit = DBL_MAX;
  double maxFit = -DBL_MAX;
  
  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f < minFit) minFit = a [i].f;
    if (a [i].f > maxFit) maxFit = a [i].f;
  }
  
  double sumFitness = 0.0;
  
  // Si todos los valores de fitness son iguales
  if (MathAbs (maxFit - minFit) < 1e-10)
  {
    for (int i = 0; i < popSize; i++)
    {
      cgf [i] = 1.0 / popSize;
    }
    cgfCenter = 1.0 / popSize;
    return;
  }
  
  // Normalizamos los valores de fitness y calculamos la suma
  for (int i = 0; i < popSize; i++)
  {
    double normalizedFit = (a [i].f - minFit) / (maxFit - minFit) + 0.1;
    sumFitness += normalizedFit;
  }
  
  // Calculamos el CGF para cada capilar
  for (int i = 0; i < popSize; i++)
  {
    double normalizedFit = (a [i].f - minFit) / (maxFit - minFit) + 0.1;
    cgf [i] = normalizedFit / sumFitness;
  }
  
  // CGF para el centro
  double normalizedCenterFit = (centerFitness - minFit) / (maxFit - minFit) + 0.1;
  cgfCenter = normalizedCenterFit / sumFitness;
}
//————————————————————————————————————————————————————————————————————

El método «CalculateCenterPosition» sirve para calcular el centro de la población a partir de las coordenadas y el valor de fitness. Comienza poniendo a cero el array de coordenadas del centro y la variable para acumular el fitness. A continuación, en un bucle que abarca toda la población, se suman las coordenadas de cada solución para cada variable, así como sus valores de fitness. Luego se dividen las sumas acumuladas entre el tamaño de la población para obtener los valores medios de las coordenadas, que constituyen las coordenadas del centro. Del mismo modo, se determina el nivel medio de fitness, lo que permite evaluar la calidad de este centro.

Este método permite determinar el punto central de toda la población, lo cual es importante para los cálculos posteriores y la elaboración de nuevas soluciones.

//————————————————————————————————————————————————————————————————————
//--- Cálculo de la posición central (Ley 3)
void C_AO_ACCS::CalculateCenterPosition ()
{
  // Xc = mean(X), fitc = mean(fit)
  ArrayInitialize (centerCoords, 0.0);
  centerFitness = 0.0;
  
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      centerCoords [j] += a [i].c [j];
    }
    centerFitness += a [i].f;
  }
  
  for (int j = 0; j < coords; j++)
  {
    centerCoords [j] /= popSize;
  }
  centerFitness /= popSize;
}
//————————————————————————————————————————————————————————————————————

El método «GlobalSearch» lleva a cabo una búsqueda global de nuevas posiciones para las soluciones con el objetivo de desarrollar las arterias principales de la población, basándose en la ley 4.

Comienza con una pasada por toda la población; para cada solución se elige un agente al azar (excepto el actual). A continuación, se calcula el factor de bifurcación, proporcional a su «CGF», que influye en la magnitud del cambio. La dirección de la búsqueda se determina comparando el «CGF» del agente actual con el centro de la población: si el «CGF» del agente actual es mayor que el del centro, se elige una dirección; en caso contrario, se elige la dirección opuesta. Para cada parámetro de coordenadas se calcula un nuevo valor mediante una fórmula que depende de la dirección elegida, del factor de bifurcación y de un número aleatorio, lo que aporta un elemento de aleatoriedad y variedad. Después se comprueba el nuevo valor de la coordenada mediante el método «u.SeInDiSp» y, si es necesario, se corrige para mantenerlo dentro de los rangos permitidos.

Este método permite que la solución «crezca» y se desplace por el espacio de búsqueda, lo que fomenta la exploración de nuevas áreas.

//————————————————————————————————————————————————————————————————————
//--- Búsqueda global: crecimiento de las arterias principales (Ley 4)
void C_AO_ACCS::GlobalSearch ()
{
  for (int i = 0; i < popSize; i++)
  {
    // Elegimos un capilar aleatorio r (que no sea el actual)
    int r = i;
    while (r == i && popSize > 1)
    {
      r = (int)MathFloor (u.RNDfromCI (0.0, popSize - 0.001));
      if (r >= popSize) r = popSize - 1;
      if (r < 0) r = 0;
    }
    
    // Factor de bifurcación Bf = CGFi
    double Bf = cgf [i] * bifurcationRate;
    
    // Determinamos la dirección basándonos en la comparación de los valores de CGF
    double dir;
    if (cgfCenter < cgf [i])  // Según el documento
    {
      dir = -1.0;
    }
    else
    {
      dir = 1.0;
    }
    
    // Aplicamos la fórmula de la Ley 4
    for (int j = 0; j < coords; j++)
    {
      double rand_val = u.RNDfromCI (0.0, 1.0);
      
      // X^(t+1)_i,j = X^t_r,j + dir × Bf × (X^t_c,j - rand × X^t_r,j)
      tempPos [i].coords [j] = a [r].c [j] + dir * Bf * (centerCoords [j] - rand_val * a [r].c [j]);
      
      // Comprobación de límites
      tempPos [i].coords [j] = u.SeInDiSp (tempPos [i].coords [j], rangeMin [j], rangeMax [j], rangeStep [j]);
    }
  }
}
//————————————————————————————————————————————————————————————————————

El método «LocalSearsh» lleva a cabo una búsqueda local destinada a desarrollar capilares dentro del algoritmo. Comienza con la actualización del factor de crecimiento de los capilares, que depende de la iteración actual y del número máximo de iteraciones: cuantas más iteraciones hayan transcurrido, mayor será el valor del factor. A continuación, se determinan la solución más adecuada y la menos adecuada de la población actual, con el fin de realizar un ajuste local basándose en ellas.

Para cada solución y para cada coordenada se calcula sucesivamente una nueva posición, que se desplaza en la dirección de la diferencia entre las coordenadas de la mejor y la peor solución, teniendo en cuenta el peso aleatorio y el factor de crecimiento. Tras el cálculo, el nuevo valor se comprueba y se corrige mediante el método «u.SeInDiSp» para que permanezca dentro del rango admisible. Este procedimiento contribuye a mejorar las soluciones en la región local de búsqueda, aumentando su calidad y acercándolas al óptimo.

//————————————————————————————————————————————————————————————————————
//--- Búsqueda local: crecimiento de capilares (Ley 6)
void C_AO_ACCS::LocalSearch ()
{
  // Actualizamos el factor de angiogénesis: α = 0,625 × √(itr/itrmax)
  if (maxIterations > 0 && currentIteration > 0)
  {
    alpha = 0.625 * MathSqrt ((double)currentIteration / (double)maxIterations);
  }
  else
  {
    alpha = 0.625;
  }
  
  // Encontramos la mejor y la peor posición en la población actual
  int bestIdx = 0, worstIdx = 0;
  
  for (int i = 1; i < popSize; i++)
  {
    if (a [i].f > a [bestIdx].f) bestIdx = i;
    if (a [i].f < a [worstIdx].f) worstIdx = i;
  }
  
  // Aplicamos la búsqueda local (Ley 6)
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      double rand_val = u.RNDfromCI (0.0, 1.0);
      
      // X^(t+1)_i,j = X^t_i,j + α × rand × (X^t_b,j - X^t_w,j)
      a [i].c [j] = a [i].c [j] + alpha * rand_val * (a [bestIdx].c [j] - a [worstIdx].c [j]);
      
      // Comprobación de límites
      a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
    }
  }
}
//————————————————————————————————————————————————————————————————————

El método «SelectionPhase» implementa la fase de selección, en la que se actualizan las soluciones actuales basándose en los resultados de la búsqueda global. Para cada elemento de la población, sus coordenadas actuales se sustituyen por las nuevas, obtenidas previamente durante el proceso de búsqueda global. Esto se hace copiando las nuevas posiciones de los arrays temporales a los arrays principales de soluciones. De esta forma, la fase de selección da paso a nuevas soluciones potencialmente más eficaces, que sirven de preparación para la siguiente etapa del algoritmo.

//————————————————————————————————————————————————————————————————————
//--- Fase de selección (Ley 5)
void C_AO_ACCS::SelectionPhase ()
{
  // Aplicamos las nuevas posiciones obtenidas en la búsqueda global
  for (int i = 0; i < popSize; i++)
  {
    // Copiamos la nueva posición
    ArrayCopy (a [i].c, tempPos [i].coords, 0, 0, coords);
  }
}
//————————————————————————————————————————————————————————————————————

El método «UpdateHeartMemory» se encarga de actualizar la memoria del corazón en el algoritmo, lo que sirve como mecanismo para recordar las mejores soluciones encontradas. Para ello, todas las soluciones actuales se ordenan según el valor de su función de fitness, en orden descendente, de modo que las mejores aparecen al principio. Tras la ordenación, se selecciona el número especificado de mejores soluciones y sus coordenadas, junto con los valores de fitness correspondientes, se guardan en una memoria específica.

Este proceso ayuda a conservar las mejores soluciones y a utilizarlas posteriormente para orientar la búsqueda, manteniendo un equilibrio entre la exploración y la explotación del espacio de soluciones.

//————————————————————————————————————————————————————————————————————
//--- Actualización de la memoria del corazón (Ley 7)
void C_AO_ACCS::UpdateHeartMemory ()
{
  // Creamos un array temporal para ordenar
  struct S_IndexedAgent
  {
    int index;
    double fitness;
  };
  
  S_IndexedAgent indexed [];
  ArrayResize (indexed, popSize);
  
  for (int i = 0; i < popSize; i++)
  {
    indexed [i].index = i;
    indexed [i].fitness = a [i].f;
  }
  
  // Ordenación por burbuja en orden descendente de fitness
  for (int i = 0; i < popSize - 1; i++)
  {
    for (int j = i + 1; j < popSize; j++)
    {
      if (indexed [j].fitness > indexed [i].fitness)
      {
        S_IndexedAgent temp = indexed [i];
        indexed [i] = indexed [j];
        indexed [j] = temp;
      }
    }
  }
  
  // Guardamos las mejores soluciones en la memoria del corazón
  for (int i = 0; i < heartMemorySize; i++)
  {
    int idx = indexed [i].index;
    ArrayCopy (heartMemory [i].position, a [idx].c, 0, 0, coords);
    heartMemory [i].fitness = a [idx].f;
  }
}
//————————————————————————————————————————————————————————————————————

El paso principal del método «Moving» del algoritmo consiste en la ejecución secuencial de varias etapas clave. En la fase inicial tiene lugar la inicialización de la población: la generación aleatoria de soluciones iniciales dentro de los rangos admisibles, teniendo en cuenta los pasos establecidos, lo cual se lleva a cabo únicamente una vez antes de iniciar las iteraciones posteriores. Tras la inicialización, se actualiza el contador interno de iteraciones.

A continuación, el algoritmo pasa a calcular la posición central, que sirve de punto de referencia para la búsqueda. Luego se calcula el factor de crecimiento coronario (CGF), que ayuda a determinar la importancia y la contribución de cada elemento. Después se lleva a cabo una búsqueda global de nuevas soluciones a partir de los datos obtenidos, lo que amplía el espacio explorado. Al final de cada ciclo tiene lugar un proceso de selección, durante el cual las soluciones actuales se sustituyen por otras nuevas obtenidas durante la búsqueda. Este ciclo se repite para ir mejorando progresivamente las soluciones.

//————————————————————————————————————————————————————————————————————
//--- Paso principal del algoritmo
void C_AO_ACCS::Moving ()
{
  // Inicialización de la población (Ley 1)
  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int j = 0; j < coords; j++)
      {
        a [i].c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]);
        a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
      }
    }
    
    revision = true;
    firstIteration = true;
    currentIteration = 0;
    return;
  }
  
  currentIteration++;
  
  // Calculamos la posición central (Ley 3)
  CalculateCenterPosition ();
  
  // Calculamos el CGF para todos los capilares (Ley 2)
  CalculateCGF ();
  
  // Realizamos una búsqueda global (Ley 4)
  GlobalSearch ();
  
  // Aplicamos la selección (Ley 5)
  SelectionPhase ();
}
//————————————————————————————————————————————————————————————————————

El método «Revision» se encarga de comprobar las soluciones actuales y actualizar sus datos para su posterior uso en el algoritmo.

En primer lugar, en la primera iteración se inicializan las mejores posiciones individuales de cada agente y se memoriza la mejor solución de toda la población, lo que contribuye a conservar las soluciones más exitosas. A continuación, para cada individuo se guardan su posición actual y el valor de la función de evaluación como valores anteriores. Luego se comparan las nuevas soluciones con las mejores soluciones personales: si la nueva posición es peor, existe la posibilidad de que se revierta a la mejor posición personal (poda), lo que ayuda a evitar un empeoramiento de los resultados. Si la solución ha mejorado, se convierte en la nueva mejor solución personal.

Acto seguido, se realiza una búsqueda local para optimizar las soluciones, se actualiza la memoria del corazón mediante el método correspondiente y, por último, se comprueba y actualiza la mejor solución global de toda la población.

//————————————————————————————————————————————————————————————————————
//--- Comprobación y actualización de los resultados
void C_AO_ACCS::Revision ()
{
  if (firstIteration)
  {
    firstIteration = false;
    // Inicializamos las mejores posiciones personales
    for (int i = 0; i < popSize; i++)
    {
      a [i].fB = a [i].f;
      ArrayCopy (a [i].cB, a [i].c, 0, 0, coords);
    }
    // Inicializamos la memoria del corazón
    UpdateHeartMemory ();
  }
  
  // Guardamos las posiciones y los valores de fitness anteriores
  for (int i = 0; i < popSize; i++)
  {
    ArrayCopy (a [i].cP, a [i].c, 0, 0, coords);
    a [i].fP = a [i].f;
  }
  
  // Tras evaluar el fitness de las nuevas posiciones obtenidas mediante la búsqueda global,
  // comprobamos si hay una mejora (Ley 5: selección y poda)
  for (int i = 0; i < popSize; i++)
  {
    // Si la nueva posición es peor que la mejor posición anterior de este agente
    if (a [i].f < a [i].fB)
    {
      // Probabilidad de poda (pruning)
      double pruningProb = 0.2;
      if (u.RNDfromCI (0.0, 1.0) < pruningProb)
      {
        // Poda: volver a la mejor posición personal
        ArrayCopy (a [i].c, a [i].cB, 0, 0, coords);
        a [i].f = a [i].fB;
      }
    }
    else
    {
      // Actualizamos la mejor solución personal del agente
      a [i].fB = a [i].f;
      ArrayCopy (a [i].cB, a [i].c, 0, 0, coords);
    }
  }
  
  // Realizamos una búsqueda local (Ley 6)
  LocalSearch ();
  
  // Actualizamos la memoria del corazón (Ley 7)
  UpdateHeartMemory ();
  
  // Actualizamos la mejor solución global
  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);
    }
  }
}
//————————————————————————————————————————————————————————————————————

Resultados de las pruebas

Los resultados de las pruebas son, por decirlo suavemente, mediocres. Pero hay un gran «PERO», y de eso hablaré más adelante.

Ejecutemos ahora el script de prueba con el algoritmo. Lo primero que llama la atención es que la forma en que se mueven los agentes en el espacio de búsqueda varía considerablemente en función de las características de la superficie de la función estudiada, lo que, de hecho, constituye una característica distintiva de los algoritmos de optimización que merecen especial atención.

ACCS en la función de prueba Hilly

ACCS en la función de prueba Forest

ACCS en la función de prueba Megacity

El mecanismo de búsqueda global mediante el movimiento respecto al centro de la población, teniendo en cuenta la dirección, resulta bastante eficaz para determinados tipos de problemas en los que los extremos se encuentran exactamente en el centro de la función. El algoritmo los resuelve fácilmente, ya que la estrategia de búsqueda se basa en el promedio; una simple coincidencia ya supone una ventaja en la búsqueda. Por tanto, para evaluar el algoritmo de forma “justa”, se necesitan funciones de prueba que planteen problemas de optimización no triviales.

En todos estos tipos de funciones estándar, el algoritmo «funciona» de maravilla; sin embargo, ocurre todo lo contrario con paisajes más complejos, como los de nuestras funciones de prueba (véase más arriba). Existe otra hipótesis (que requiere verificación): la excelente convergencia en estas funciones con un extremo en el centro podría deberse a que son simétricas simultáneamente en dos planos.

ACCS en la función de prueba estándar «Paraboloid»

ACCS en la función de prueba estándar de Ackley

ACCS en la función de prueba estándar de Rastrigin

En la tabla de clasificación, el algoritmo ACCS se presenta a título informativo.

Conclusiones

El algoritmo ACCS constituye un interesante intento de trasladar el modelo biológico del crecimiento de las arterias coronarias a los problemas de optimización; sin embargo, su aplicación práctica ha puesto de manifiesto importantes limitaciones. Un resultado del 30 % del máximo posible pone de manifiesto problemas fundamentales en la mecánica del algoritmo, que le impiden competir con los mejores métodos de optimización. La principal debilidad radica en la excesiva dependencia de la distribución actual de la población a través del mecanismo «CGF», lo que da lugar a una convergencia prematura y a una exploración insuficiente del espacio de búsqueda.

El mecanismo de búsqueda global mediante el movimiento respecto al centro de la población, teniendo en cuenta la dirección determinada por la comparación de los valores de CGF, resulta poco eficaz para salir de los óptimos locales, especialmente en paisajes multimodales complejos. La búsqueda local, basada en el movimiento entre la mejor y la peor solución con un factor de angiogénesis decreciente, quizá esté demasiado simplificada y no tenga en cuenta la topología del espacio de búsqueda.

La memoria del corazón, que almacena el 25 % de las mejores soluciones, reproduce de hecho la funcionalidad del elitismo, pero no se utiliza de forma activa para orientar la búsqueda, lo que la convierte más bien en un archivo pasivo que en un componente activo del algoritmo. La metáfora biológica, aunque conceptualmente atractiva, no se traduce en mecanismos computacionales eficaces: los procesos de crecimiento de las arterias, bifurcación y poda en un sistema biológico real están regulados por complejos gradientes químicos y tensiones mecánicas, que resultan difíciles de modelar adecuadamente mediante fórmulas matemáticas sencillas.

El intento de combinar la búsqueda global y la local mediante la aplicación sucesiva de dos estrategias de movimiento diferentes da lugar a un conflicto entre la exploración y la explotación, en lugar de a una sinergia entre ambas. He probado a crear varias versiones del algoritmo con pequeños cambios en el orden de las estrategias de búsqueda y modificaciones de estas, sin apartarme de la idea original, pero no he conseguido una mejora significativa, así que lo dejo todo tal y como está. Para quienes disfrutan experimentando: tienen a su disposición todas las posibilidades y herramientas necesarias para mejorar los resultados. Además, en el marco de este artículo sigue sin resolverse la cuestión relativa a la naturaleza de la elevada eficacia en determinadas tareas.

Figura 3. Escala de colores de los algoritmos según las pruebas correspondientes

Figura 4. Histograma de los resultados de las pruebas de los algoritmos (en una escala de 0 a 100; cuanto mayor sea el valor, mejor, donde 100 es el resultado teórico máximo posible; en el archivo se incluye el script para calcular la tabla de clasificación)

Ventajas e inconvenientes del algoritmo ACCS:

Ventajas:

1. Hay pocos parámetros externos.
2. Es extremadamente eficaz en determinados tipos de problemas (incluso de alta dimensión).

Desventajas:

1. Convergencia deficiente en paisajes complejos.

Adjuntamos al artículo un archivo comprimido con las versiones actualizadas de los códigos de los algoritmos. El autor del artículo no se hace responsable de la exactitud absoluta en la descripción de los algoritmos canónicos, ya que en muchos de ellos se han introducido modificaciones para mejorar las capacidades de búsqueda. Las conclusiones y consideraciones que figuran en los artículos se basan en los resultados de los experimentos realizados.

• GitHub: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5

Programas utilizados en el artículo