Algoritmo de estructura cristalina — Crystal Structure Algorithm (CryStAl)
Índice
Introducción
No hace mucho, tuve la oportunidad de estudiar un algoritmo de optimización, y el trabajo con él puso de manifiesto los «escollos» que entraña la puesta en práctica de una idea prometedora. Hoy presentamos el Crystal Structure Algorithm (CryStAl), un algoritmo metaheurístico de optimización inspirado en el proceso físico de formación de estructuras cristalinas. Fue propuesto en 2021 por un grupo de investigadores formado por A. Kaveha y M. Kooshkebaghi, y publicado en un artículo de Siamak Talatahari. CryStAl simula el proceso de formación de cristales, en el que las soluciones son átomos y la búsqueda del óptimo consiste en ordenar dichos átomos en una estructura estable. El algoritmo utiliza una base y una retícula como representación de la distribución espacial de las soluciones, la simetría y la regularidad para formar una población equilibrada, y criterios energéticos para descartar las soluciones inestables.
Implementación del algoritmo
Analizaremos el funcionamiento del algoritmo CryStAl usando un pseudocódigo detallado de todas sus etapas:
Parámetros de entrada del algoritmo
Tamaño de la población de cristales: cuántos cristales habrá en la población (normalmente 30)
Número de cristales aleatorios: cuántos cristales aleatorios se deben utilizar para calcular el valor medio Fc (normalmente 3)
Dimensionalidad del problema: número de variables que se optimizan
Número máximo de iteraciones: número de veces que el algoritmo repetirá el ciclo de optimización
Límites de búsqueda: valores mínimos y máximos para cada variable
ETAPA 1: INICIALIZACIÓN DE LA POBLACIÓN
Creación de cristales iniciales
Para cada cristal de la población y para cada coordenada (variable) de dicho cristal:
- Fórmula 3 — Inicialización aleatoria: Nueva coordenada = Límite mínimo + Número aleatorio × (Límite máximo - Límite mínimo), donde el número aleatorio se distribuye uniformemente entre 0 y 1
Calcular el valor de la función de aptitud para este cristal y anotar los récords personales del cristal
Inicialización de récords globales
Encontrar el cristal con el valor máximo de la función de aptitud
Encontrar el cristal con el valor mínimo de la función de aptitud
ETAPA 2: CICLO PRINCIPAL DE OPTIMIZACIÓN
Repetir los siguientes pasos desde la primera iteración hasta la máxima:
PASO 1: Cálculo de la posición media de todos los cristales (Cr_main)
Para cada coordenada: poner a cero la suma correspondiente a esa coordenada
Para cada cristal de la población: añadir a la suma el valor de esa coordenada correspondiente a ese cristal
Dividir la suma entre el número de cristales para obtener el valor medio
Resultado: hemos obtenido el vector de valores medios en todas las coordenadas
PASO 2: Determinación del mejor cristal (Cr_b)
Asignar al índice del mejor cristal el valor del índice del primer cristal
Para cada uno de los cristales siguientes, desde el segundo hasta el último:
Si la aptitud de este cristal es mayor que la del mejor cristal actual: actualizar el índice del mejor cristal con el índice de este cristal
Resultado: se averigua el índice del cristal con el mejor valor de la función de aptitud
PASO 3: Actualización de las posiciones de todos los cristales
Para cada cristal de la población:
Etapa 3.1: Conservación del estado actual
Guardar la posición actual del cristal como posición anterior
Etapa 3.2: Elección de la estrategia de actualización
Seleccionar al azar una de las cuatro estrategias de actualización:
- Estrategia 0: Actualización cúbica simple
- Estrategia 1: Actualización cúbica con el mejor cristal
- Estrategia 2: Actualización cúbica con el valor medio de los cristales seleccionados al azar
- Estrategia 3: Actualización combinada con el mejor cristal y el valor medio
Etapa 3.3: Aplicación de la estrategia elegida
SI se ha seleccionado la ESTRATEGIA 0 — Actualización cúbica simple:
Para cada coordenada del cristal: generar un número aleatorio r entre 0 y 1
- Fórmula 4 — Nueva coordenada = Coordenada anterior + r × Coordenada media de todos los cristales
DE LO CONTRARIO, SI se ha elegido la ESTRATEGIA 1 — Con el mejor cristal:
Para cada coordenada del cristal: generar dos números aleatorios r1 y r2 comprendidos entre 0 y 1
- Fórmula 5 — Nueva coordenada = Coordenada anterior + r1 × Coordenada media de todos los cristales + r2 × Coordenada del mejor cristal
EN CASO CONTRARIO, SI se ha seleccionado la ESTRATEGIA 2 — Con la media de cristales aleatorios:
Subetapa 2.1: Cálculo de la media de los cristales aleatorios (Fc)
Para cada coordenada: poner a cero la suma correspondiente a esa coordenada
Repetir el número de veces indicado (normalmente 3 veces): seleccionar un cristal al azar de la población (excluyendo el que se está procesando actualmente)
Para cada coordenada: acumular en la suma el valor de esa coordenada del cristal seleccionado al azar
Para cada coordenada: dividir la suma entre el número de cristales aleatorios seleccionados
Resultado: se obtuvo el valor medio de varios cristales seleccionados al azar
Subetapa 2.2: Actualización de la posición
Para cada coordenada del cristal: generar dos números aleatorios r1 y r2 comprendidos entre 0 y 1
- Fórmula 6 — Nueva coordenada = Antigua coordenada + r1 × Coordenada media de todos los cristales + r2 × Coordenada media de los cristales aleatorios
SI NO, se ha seleccionado la ESTRATEGIA 3 — Combinada:
Subetapa 3.1: Cálculo de la media de los cristales aleatorios (Fc)
(Se lleva a cabo exactamente igual que en la estrategia 2)
Subetapa 3.2: Actualización de la posición
- Para cada coordenada del cristal: generar tres números aleatorios r1, r2 y r3 comprendidos entre 0 y 1
- Fórmula 7 — Nueva coordenada = Antigua coordenada + r1 × Coordenada media de todos los cristales + r2 × Coordenada del mejor cristal + r3 × Coordenada media de los cristales aleatorios
Etapa 3.4: Tratamiento de posiciones fuera de los límites (Boundary Handling)
Para cada coordenada de la nueva posición del cristal: si la coordenada es inferior al límite mínimo O superior al límite máximo, el cristal ha salido de los límites permitidos y es necesario realizar una corrección.
- Generar un número aleatorio entre 0 y 1
- Recalcular la coordenada dentro de los límites permitidos: Coordenada = Límite mínimo + Número aleatorio × (Límite máximo - Límite mínimo)
Actualizar la posición del cristal a la nueva posición calculada
PASO 4: Evaluación de las nuevas posiciones y actualización de los mejores y peores valores históricos
Para cada cristal de la población:
Etapa 4.1: Cálculo de la aptitud
Calcular el valor de la función de aptitud para la nueva posición del cristal
Etapa 4.2: Actualización de los mejores y peores valores personales del cristal
Si el nuevo valor de aptitud es mejor que el mejor valor personal: Actualizar el mejor valor personal de aptitud con el valor actual. Guardar la posición actual como la mejor posición personal.
Si el nuevo valor de aptitud es peor que el peor valor personal: Actualizar el peor valor personal de aptitud con el actual. Guardar la posición actual como la peor posición personal.
Etapa 4.3: Actualización de los mejores y peores valores globales
Si el valor de aptitud de este cristal es mejor que el mejor valor global: Actualizar el mejor valor global con el valor de aptitud de este cristal. Guardar la posición de este cristal como la mejor posición global.
Si el valor de aptitud de este cristal es peor que el peor valor global: Actualizar el peor valor global con el valor de aptitud de este cristal. Guardar la posición de este cristal como la peor posición global.
PASO 5: Pasar a la siguiente iteración
Pasar a la siguiente iteración del ciclo principal de optimización
Fin del ciclo principal de optimización
ETAPA 3: FINALIZACIÓN DEL FUNCIONAMIENTO DEL ALGORITMO
Una vez realizadas todas las iteraciones, devolver el resultado:
- La mejor posición global (solución del problema de optimización)
- El mejor valor global de la función de aptitud
El diagrama de la siguiente figura muestra el esquema del ciclo principal, una representación de las cuatro estrategias y un ejemplo del espacio de búsqueda con cristales.

Figura 1. Diagrama de flujo del algoritmo CryStAl
El algoritmo CryStAl trata de mantener un equilibrio entre dos aspectos importantes de la optimización:
Exploración (exploration) — estudio de nuevas áreas del espacio de búsqueda: se garantiza mediante la estrategia 0 con el desplazamiento hacia la posición media, se refuerza mediante la estrategia 2 con información procedente de cristales aleatorios y ayuda a evitar el estancamiento en óptimos locales.
Explotación (exploitation) — búsqueda en profundidad en torno a buenas soluciones: se lleva a cabo mediante la estrategia 1, avanzando hacia el mejor cristal; acelera la convergencia hacia el óptimo y permite utilizar de forma eficaz la información obtenida.
Enfoque combinado:
- La estrategia 3 aúna los tres componentes
- La selección aleatoria de estrategias en cada iteración garantiza la adaptabilidad
- Cada estrategia tiene una probabilidad de ser elegida del 25 %
Función de los componentes clave:
Posición media (Cr_main) — representa el centro de masa de la población, orienta la búsqueda hacia las zonas centrales del espacio explorado y se actualiza en cada iteración a partir de las posiciones actuales de todos los cristales.
Mejor cristal (Cr_b) — contiene la mejor solución encontrada hasta el momento, atrae a otros cristales hacia una zona prometedora y potencia la explotación de las buenas soluciones encontradas.
Media de los cristales aleatorios (Fc) — representa la información local de los vecinos, aporta estocasticidad y diversidad a la búsqueda y ayuda a evitar la convergencia prematura.
Ahora que hemos analizado con detalle los principios de funcionamiento del algoritmo, pasemos a su implementación en código. Escribiremos la clase «C_AO_CryStAl», que heredará de la clase «C_AO» y estará destinada a implementar el algoritmo «Crystal Structure Algorithm».
Constructor:- Se inicializan dos parámetros: «popSize» (tamaño de la población de cristales, por defecto 30) y «numRandomCrystals» (número de cristales aleatorios utilizados para uno de los cálculos de «Fc», por defecto 3).
- Estos parámetros se añaden a la estructura que proporciona información sobre los parámetros del algoritmo.
- Este método permite actualizar los valores de los parámetros «popSize» y «numRandomCrystals» utilizando datos de una estructura de parámetros externa.
- Luego se comprueba que «numRandomCrystals» sea siempre mayor o igual que 1 y menor o igual que «popSize» menos 1, para evitar cálculos incorrectos.
- Init () — método para inicializar el algoritmo, que requiere información sobre los intervalos y los incrementos de las variables de entrada, así como sobre el número de épocas;
- Moving () — método que implementa el paso de desplazamiento de los cristales en el algoritmo;
- Revision () — método encargado de revisar o actualizar el estado de la población.
- numRandomCrystals — número de cristales aleatorios que se utiliza para calcular «Fc».
- meanPosition — array que almacena el valor medio de las posiciones de todos los cristales de la población;
- bestCrystalIdx — índice del mejor cristal de la población actual;
- isFirstIteration — indicador booleano que indica si la iteración actual es la primera tras la inicialización;
- CalculateMeanPosition () — método para calcular la posición media de los cristales;
- CalculateFc () — método para calcular el valor «Fc», que es un criterio que depende de los cristales seleccionados;
- SelectRandomCrystal () — método para seleccionar un cristal aleatorio de la población, con la posibilidad de excluir el cristal especificado.
En general, la clase «C_AO_CryStAl» modela un algoritmo de optimización basado en el comportamiento de los cristales. Trabaja con una población de «cristales», cada uno de los cuales tiene su propia posición. El algoritmo incluye pasos para mover los cristales, calcular sus características cualitativas y determinar la mejor solución.
//———————————————————————————————————————————————————————————————————— class C_AO_CryStAl : public C_AO { public: //---------------------------------------------------------- ~C_AO_CryStAl () { } C_AO_CryStAl () { ao_name = "CryStAl"; ao_desc = "Crystal Structure Algorithm"; ao_link = "https://www.mql5.com/ru/articles/19899"; popSize = 30; // tamaño de la población de cristales numRandomCrystals = 3; // número de cristales aleatorios para Fc ArrayResize (params, 2); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "numRandomCrystals"; params [1].val = numRandomCrystals; } void SetParams () { popSize = (int)params [0].val; numRandomCrystals = (int)params [1].val; if (numRandomCrystals < 1) numRandomCrystals = 1; if (numRandomCrystals > popSize - 1) numRandomCrystals = popSize - 1; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP); void Moving (); void Revision (); //------------------------------------------------------------------ int numRandomCrystals; // número de cristales aleatorios para calcular Fc private: //--------------------------------------------------------- double meanPosition []; // posición media de todos los cristales (Cr_main) int bestCrystalIdx; // índice del mejor cristal bool isFirstIteration; // indicador de la primera iteración tras la inicialización void CalculateMeanPosition (); void CalculateFc (int currentCrystal, double &fcArray []); int SelectRandomCrystal (int excludeCrystal); }; //————————————————————————————————————————————————————————————————————
El método «Init» está destinado a inicializar el algoritmo «Crystal Structure Algorithm» antes de que comience a funcionar.
En primer lugar, se invoca el método «StandardInit», que lleva a cabo las acciones preparatorias básicas, comunes a todos los algoritmos heredados de «C_AO». Si esta etapa básica falla, el método «Init» también falla. Se crea el array «meanPosition» (posición media). El tamaño de este array viene determinado por la variable «coords», que almacena el número de dimensiones. Todos los elementos de este array se inicializan con el valor cero. Esto significa que, al inicio del algoritmo, se considera que la posición media de todos los cristales es igual a cero.
Configuración de los valores iniciales de los indicadores:- El valor de bestCrystalIdx (índice del mejor cristal) se establece en 0. Esto supone que, al inicio, el primer cristal de la población se considera el mejor.
- isFirstIteration (indicador de primera iteración) se establece en «true». Esto indica que la siguiente iteración que se ejecutará será la primera tras la inicialización completa.
//———————————————————————————————————————————————————————————————————— //--- Inicialización bool C_AO_CryStAl::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Inicialización de arrays ArrayResize (meanPosition, coords); ArrayInitialize (meanPosition, 0.0); bestCrystalIdx = 0; isFirstIteration = true; return true; } //————————————————————————————————————————————————————————————————————
El método «CalculateMeanPosition» sirve para calcular la posición media de todos los «cristales» de la población. En primer lugar, se reinician todos los elementos del array «meanPosition» (que almacena la media de cada coordenada). Esto se hace para que, antes de empezar a sumar las posiciones actuales de los cristales, partamos de cero.
A continuación, el método recorre cada cristal de la población. Para cada cristal, también recorre todas sus coordenadas (determinadas por «coords»). El valor de cada coordenada del cristal actual se suma al elemento correspondiente del array «meanPosition». De este modo, «meanPosition» va acumulando progresivamente la suma de los valores de cada coordenada en todos los cristales.
Una vez finalizada la suma, el método vuelve a recorrer todas las coordenadas. Cada valor acumulado en «meanPosition» se divide entre el número total de cristales, «popSize». Esta transformación convierte la suma de las coordenadas en su valor medio. Como resultado de la ejecución de este método, el array «meanPosition» contendrá el valor medio de cada coordenada para todos los cristales de la población.
//———————————————————————————————————————————————————————————————————— //--- Cálculo de la posición media de todos los cristales (Cr_main) void C_AO_CryStAl::CalculateMeanPosition () { // Ponemos a cero los valores medios ArrayInitialize (meanPosition, 0.0); // Sumamos las posiciones actuales de todos los cristales for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { meanPosition [c] += a [i].c [c]; } } // Dividimos entre el número de cristales para obtener la media for (int c = 0; c < coords; c++) { meanPosition [c] /= (double)popSize; } } //————————————————————————————————————————————————————————————————————
El método «CalculateFc» está diseñado para calcular el denominado «valor medio de los cristales seleccionados al azar». Este acepta como argumentos el índice del cristal actual «currentCrystal» y el array «fcArray», en el que se guardará el resultado.
Al principio, todos los elementos del array «fcArray» se ponen a cero. Esto garantiza que empecemos la suma desde cero para cada nueva posición «Fc». A continuación, el método entra en un bucle que se repite «numRandomCrystals» veces. En cada iteración de este ciclo:
- Luego se selecciona al azar el índice de un cristal, «randomCrystal». Es importante señalar que esta selección se realiza de tal forma que se excluya el propio «currentCrystal» (es decir, el cristal para el que estamos calculando ahora «Fc»);
- La posición (coordenadas) de este cristal elegido al azar se añade a los elementos correspondientes del array «fcArray». De este modo, este array acumula la suma de las coordenadas de todos los cristales seleccionados al azar.
En definitiva, el array «fcArray» contendrá las coordenadas del cristal «medio», obtenido mediante el promedio de las posiciones de varios cristales seleccionados al azar de la población (excluyendo el actual).
//———————————————————————————————————————————————————————————————————— //--- Cálculo de Fc (valor medio de cristales seleccionados al azar) void C_AO_CryStAl::CalculateFc (int currentCrystal, double &fcArray []) { // Inicializamos el array con ceros ArrayInitialize (fcArray, 0.0); // Seleccionamos numRandomCrystals cristales aleatorios (excluyendo el actual) for (int i = 0; i < numRandomCrystals; i++) { int randomCrystal = SelectRandomCrystal (currentCrystal); // Sumamos las posiciones de los cristales seleccionados for (int c = 0; c < coords; c++) { fcArray [c] += a [randomCrystal].c [c]; } } // Calculamos el valor medio for (int c = 0; c < coords; c++) { fcArray [c] /= (double)numRandomCrystals; } } //————————————————————————————————————————————————————————————————————
El método «SelectRandomCrystal» está diseñado para seleccionar un «cristal» aleatorio de toda la población, pero con una condición importante: no debe seleccionar el cristal que se haya indicado como «excludeCrystal».
El método inicia un bucle infinito que continuará hasta que se cumpla la condición de salida. Dentro del ciclo se genera un índice numérico aleatorio, que se selecciona de un rango que abarca todos los «cristales» posibles de la población (de 0 a «popSize» menos 1).
Tras generar un índice aleatorio, se lleva a cabo una comprobación:
- si el índice generado «selected» es igual al índice del cristal que queremos excluir, «excludeCrystal», el bucle continúa ejecutándose y se genera un nuevo índice aleatorio;
- si el índice generado no es igual a «excludeCrystal», entonces se cumple la condición para salir del bucle.
//———————————————————————————————————————————————————————————————————— //--- Selección de un cristal al azar (excluyendo el indicado) int C_AO_CryStAl::SelectRandomCrystal (int excludeCrystal) { int selected; do selected = u.RNDminusOne (popSize); while (selected == excludeCrystal); return selected; } //————————————————————————————————————————————————————————————————————
El método «Moving» es el ciclo de trabajo principal del algoritmo, encargado de la evolución de la población de «cristales» en cada iteración. Si el algoritmo se ejecuta por primera vez («revision» es igual a «false»), se inicializan las posiciones de todos los cristales de la población. Para cada cristal y cada una de sus coordenadas se genera un valor aleatorio comprendido entre 0 y 1. Este valor aleatorio se escala posteriormente al rango de trabajo especificado (rangeMin - rangeMax) para esa coordenada. Después se aplica una discretización para ajustar la posición al paso admisible «rangeStep». Tras la inicialización, se establece el indicador «revision» en «true» para que las llamadas posteriores al método realicen una actualización en lugar de una inicialización.
Tras la primera iteración, se calcula en primer lugar la posición media de todos los cristales de la población. El algoritmo encuentra el cristal con el mejor valor de la función de aptitud «f» en la iteración actual y memoriza su índice.
Para cada cristal de la población (recorriendo los índices de 0 a «popSize»):
- La posición actual del cristal se copia en una memoria temporal, que se utilizará como «posición anterior» (Cr_old) para los cálculos;
- Luego se selecciona al azar una de las varias estrategias disponibles para actualizar la posición (hay cuatro en total, numeradas del 0 al 3);
- para dos de las cuatro estrategias (las estrategias 2 y 3) se calcula el «valor medio de los cristales seleccionados al azar» (Fc), que también se utilizará en la actualización;
- En función de la estrategia elegida, la nueva posición del cristal «Cr_new» se calcula a partir de su posición anterior, la posición media de la población, la posición del mejor cristal y «Fc». Cada estrategia utiliza su propia combinación de estos factores y de números aleatorios (r, r1, r2, r3) para introducir cambios;
- Una vez calculada la nueva posición, se comprueba que se ajuste a los rangos de trabajo establecidos (rangeMin - rangeMax) para cada coordenada. Si la nueva posición se sale de los límites permitidos, se corrige generando una nueva posición aleatoria dentro de dichos límites;
- A continuación, se vuelve a aplicar el procedimiento de discretización a la posición mediante la función u.SeInDiSp().
El método «Moving» desplaza de forma iterativa los «cristales» en el espacio de búsqueda, utilizando diversas estrategias basadas en la información actual sobre la población (posición media, mejor cristal) y en factores aleatorios.
//———————————————————————————————————————————————————————————————————— //--- Paso principal del algoritmo void C_AO_CryStAl::Moving () { // Inicialización de la población (fórmula 3) if (!revision) { // Inicialización aleatoria de la población de cristales for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { double xi = u.RNDfromCI (0.0, 1.0); a [i].c [j] = rangeMin [j] + xi * (rangeMax [j] - rangeMin [j]); a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } revision = true; return; } // CRÍTICO: Calculamos la posición media y encontramos el mejor cristal ANTES de la actualización CalculateMeanPosition (); // Encontramos el mejor cristal para la iteración actual bestCrystalIdx = 0; for (int i = 1; i < popSize; i++) { if (a [i].f > a [bestCrystalIdx].f) { bestCrystalIdx = i; } } // Ciclo principal de actualización de posiciones (fórmulas 4-7) for (int i = 0; i < popSize; i++) { // Guardamos la posición actual como posición anterior (Cr_old) ArrayCopy (a [i].cP, a [i].c, 0, 0, coords); // Elegimos una estrategia aleatoria (0-3) int strategy = u.RNDminusOne (5); // Preparamos el array para Fc (solo para las estrategias 2 y 3) double fc []; ArrayResize (fc, coords); if (strategy == 2 || strategy == 3) { CalculateFc (i, fc); } // Aplicamos la estrategia seleccionada para actualizar la posición switch (strategy) { case 0: // Estrategia 1: Actualización cúbica simple (fórmula 4) // Cr_new = Cr_old + r * Cr_main for (int c = 0; c < coords; c++) { double r = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].cP [c] + r * meanPosition [c]; } break; case 1: // Estrategia 2: Actualización cúbica con el mejor cristal (fórmula 5) // Cr_new = Cr_old + r1 * Cr_main + r2 * Cr_b for (int c = 0; c < coords; c++) { double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].cP [c] + r1 * meanPosition [c] + r2 * a [bestCrystalIdx].c [c]; } break; case 2: // Estrategia 3: Actualización cúbica con la posición media de los cristales seleccionados al azar (fórmula 6) // Cr_new = Cr_old + r1 * Cr_main + r2 * Fc for (int c = 0; c < coords; c++) { double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].cP [c] + r1 * meanPosition [c] + r2 * fc [c]; } break; case 3: // Estrategia 4: Actualización cúbica con el mejor cristal y la posición media de los cristales seleccionado al azar(fórmula 7) // Cr_new = Cr_old + r1 * Cr_main + r2 * Cr_b + r3 * Fc for (int c = 0; c < coords; c++) { double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); double r3 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].cP [c] + r1 * meanPosition [c] + r2 * a [bestCrystalIdx].c [c] + r3 * fc [c]; } break; } // Comprobación y corrección de los límites para la nueva posición for (int c = 0; c < coords; c++) { // Si se han sobrepasado los límites, aplicamos el tratamiento de límites if (a [i].c [c] < rangeMin [c] || a [i].c [c] > rangeMax [c]) { // Generamos una nueva posición aleatoria dentro del rango permitido double xi = u.RNDfromCI (0.0, 1.0); a [i].c [c] = rangeMin [c] + xi * (rangeMax [c] - rangeMin [c]); } // Aplicamos la discretización a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //————————————————————————————————————————————————————————————————————
El método «Revision» se encarga de actualizar y guardar las mejores soluciones encontradas, tanto a nivel de cada «cristal» individual (la mejor solución personal) como a nivel de toda la población (la mejor solución global).
El método recorre cada «cristal» de la población para evaluar su estado actual. Para cada cristal, se compara su valor actual de aptitud «f» con su mejor valor histórico «fB». Si el valor actual de aptitud es mejor que el mejor valor anterior, se actualiza el mejor valor personal «fB» con el valor actual y se copia la posición del cristal correspondiente a este nuevo mejor valor en su mejor solución personal «cB».
Al mismo tiempo que actualiza las mejores soluciones personales, el algoritmo realiza un seguimiento de la mejor solución encontrada por toda la población hasta ese momento. También se compara el valor actual de aptitud «f» del cristal con el mejor valor global de la población «fB». Si el valor actual de aptitud del cristal es mejor que el mejor valor global actual, se actualiza el mejor valor global «fB» con el valor actual y se copia la posición del cristal correspondiente a este nuevo mejor valor global en la mejor solución global «cB».
Una vez finalizada la ejecución del método «Revision», las variables «fB» y «cB» almacenan los valores más altos de la función de aptitud y las coordenadas correspondientes, encontrados durante toda la ejecución del algoritmo. A cada cristal se le asigna también su propia mejor solución encontrada.
//———————————————————————————————————————————————————————————————————— //--- Actualización y verificación de los resultados void C_AO_CryStAl::Revision () { // Actualizamos las mejores y peores soluciones para cada cristal for (int i = 0; i < popSize; i++) { // Actualizamos la mejor solución personal if (a [i].f > a [i].fB) { a [i].fB = a [i].f; ArrayCopy (a [i].cB, a [i].c, 0, 0, coords); } // Actualizamos la mejor solución global if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, coords); } } } //————————————————————————————————————————————————————————————————————
Resultados de las pruebas
En las pruebas, el algoritmo obtiene unos resultados muy modestos. Llama la atención el resultado en sí, un 26,33 %, que se sitúa en el nivel de la búsqueda aleatoria (random walk) en nuestra tabla de clasificación. Entonces, ¿qué significa esto? Ya volveremos sobre este tema.
CryStAl|Crystal Structure Algorithm|30.0|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.49130791883895686
25 Hilly's; Func runs: 10000; result: 0.3254668138312991
500 Hilly's; Func runs: 10000; result: 0.25762861219210875
=============================
5 Forest's; Func runs: 10000; result: 0.3770837459944563
25 Forest's; Func runs: 10000; result: 0.21650897859329796
500 Forest's; Func runs: 10000; result: 0.158890697466887
=============================
5 Megacity's; Func runs: 10000; result: 0.2938461538461538
25 Megacity's; Func runs: 10000; result: 0.1498461538461539
500 Megacity's; Func runs: 10000; result: 0.09889230769230854
=============================
All score: 2.36947 (26.33%)
Estos resultados no me dejaron indiferente, así que decidí introducir algunas modificaciones para mejorar la convergencia del algoritmo. Su lógica de interacción, que resultó no ser del todo eficaz, me permitió revisar algunos métodos ilógicos sin perder la idea general. Veamos qué resultado ha dado finalmente la versión modificada.
Formulación de la actualización de posiciones (estrategias 0-3): la versión modificada utiliza otro estilo de actualización, que consiste en añadir un desplazamiento a la posición actual a [i].c [c]. Las fórmulas tienen un aspecto diferente, aunque en la estrategia se utilizan los mismos conceptos. Añadir una determinada proporción de la diferencia entre la posición actual y la posición media supone un cambio significativo en la implementación matemática.
Perturbación aleatoria adicional: se introduce una condición adicional «if (u.RNDprobab () < 0.1)». Si esta condición se cumple con una probabilidad del 10 %, la posición del cristal se actualiza mediante a[i].c[c] = u.PowerDistribution (cB[c], rangeMin[c], rangeMax[c], 20), lo que reduce la probabilidad de que el algoritmo se quede atascado. El resto de estrategias se aplican con una probabilidad del 90 %.
Almacenamiento de la posición anterior: la versión original guarda la posición en “a[i].cP” antes de calcular la nueva. En la versión modificada, esta copia no se guarda ni se utiliza; la actualización se realiza directamente desde la posición actual «a [i].c [c]».
Tratamiento de límites: en la versión original, tras aplicar la estrategia de actualización, el método recorre todas las coordenadas y, si la nueva posición se sale de los límites, se genera una posición aleatoria completamente nueva dentro del rango válido; en «C_AO_CryStAlm» primero se aplica la estrategia de actualización y, a continuación, únicamente se realiza la discretización mediante el método «u.SeInDiSp».
//———————————————————————————————————————————————————————————————————— //--- Paso principal del algoritmo void C_AO_CryStAlm::Moving () { // Inicialización de la población (fórmula 3) if (!revision) { // Inicialización aleatoria de la población de cristales for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { double xi = u.RNDfromCI (0.0, 1.0); a [i].c [j] = rangeMin [j] + xi * (rangeMax [j] - rangeMin [j]); a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } revision = true; return; } // CRÍTICO: Calculamos la posición media y encontramos el mejor cristal ANTES de la actualización CalculateMeanPosition (); // Ciclo principal de actualización de posiciones (fórmulas 4-7) for (int i = 0; i < popSize; i++) { // Elegimos una estrategia aleatoria (0-3) int strategy = u.RNDminusOne (5); // Preparamos el array para Fc (solo para las estrategias 2 y 3) double fc []; ArrayResize (fc, coords); if (strategy == 2 || strategy == 3) { CalculateFc (i, fc); } for (int c = 0; c < coords; c++) { if (u.RNDprobab () < 0.1) { a [i].c [c] = u.PowerDistribution (cB [c], rangeMin [c], rangeMax [c], 20); } else { // Aplicamos la estrategia seleccionada para actualizar la posición switch (strategy) { case 0: // Estrategia 1: Actualización cúbica simple (fórmula 4) { // Cr_new = Cr_old + r * Cr_main double r = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].c [c] + r * (meanPosition [c] - a [i].c [c]); } break; case 1: // Estrategia 2: Actualización cúbica con el mejor cristal (fórmula 5) { // Cr_new = Cr_old + r1 * Cr_main + r2 * Cr_b double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].c [c] + r1 * (meanPosition [c] - a [i].c [c]) + r2 * (cB [c] - a [i].c [c]); } break; case 2: // Estrategia 3: Actualización cúbica con la posicion media de los cristales seleccionados al azar (fórmula 6) { // Cr_new = Cr_old + r1 * Cr_main + r2 * Fc double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].c [c] - r1 * (meanPosition [c] - a [i].c [c]) + r2 * (fc [c] - a [i].c [c]); } break; case 3: // Estrategia 4: Actualización cúbica con el mejor cristal y la posición media de los cristales seleccionados al azar (fórmula 7) { // Cr_new = Cr_old + r1 * Cr_main + r2 * Cr_b + r3 * Fc double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); double r3 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].c [c] + r1 * (meanPosition [c] - a [i].c [c]) + r2 * (cB [c] - a [i].c [c]) + r3 * (fc [c] - a [i].c [c]); } break; } } // Aplicamos la discretización a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //————————————————————————————————————————————————————————————————————
La inicialización no ha cambiado en nuestro caso. En el caso del método «CalculateMeanPosition», no hay diferencias entre las versiones para «C_AO_CryStAl» y «C_AO_CryStAlm», ni tampoco en los métodos «CalculateFc» y «SelectRandomCrystal». El método «Revision» se ha implementado de forma totalmente idéntica en ambas versiones, C_AO_CryStAl y C_AO_CryStAlm.
Veamos los nuevos resultados que se muestran a continuación: confirman la validez de mis supuestos teóricos. Ahora vamos a averiguar las razones por las que la versión original convierte una búsqueda dirigida en un paseo aleatorio con deriva.
CryStAlm|Crystal Structure Algorithm M|30.0|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.8065665859751701
25 Hilly's; Func runs: 10000; result: 0.5614723387106613
500 Hilly's; Func runs: 10000; result: 0.2909726108642525
=============================
5 Forest's; Func runs: 10000; result: 0.7522883470073202
25 Forest's; Func runs: 10000; result: 0.48674341114821484
500 Forest's; Func runs: 10000; result: 0.2101468006131327
=============================
5 Megacity's; Func runs: 10000; result: 0.48461538461538467
25 Megacity's; Func runs: 10000; result: 0.2701538461538461
500 Megacity's; Func runs: 10000; result: 0.11110769230769342
=============================
All score: 3,97407 (44.16%)
Al comparar las dos versiones del algoritmo Crystal Structure Algorithm, a primera vista puede parecer que los cambios son mínimos. Ambos métodos inicializan la población de la misma manera, ambos calculan la posición media y ambos utilizan cuatro estrategias de actualización. Sin embargo, tras esta similitud aparente se esconden diferencias fundamentales que dan lugar a una diferencia de casi el doble en el rendimiento. Analicemos cada cambio para comprender por qué la versión modificada es mucho más eficaz.
Error fundamental: suma de coordenadas absolutas en lugar de movimiento dirigido. Para comprender el problema clave del algoritmo original, imaginemos una optimización unidimensional: buscamos el máximo de una función en el intervalo de 0 a 100. La posición media de la población (el lugar hacia el que se atraen los cristales) se encuentra en el punto 60. Tenemos tres cristales en diferentes posiciones: el primero en el punto 10, el segundo en el punto 60 y el tercero en el punto 90. El coeficiente aleatorio r es el mismo para todos: 0,5.Fórmula original: x_new = x_old + r × mean
- Cristal 1: 10 + 0,5 × 60 = 10 + 30 = 40 (desplazamiento de +30)
- Cristal 2: 60 + 0,5 × 60 = 60 + 30 = 90 (desplazamiento de +30)
- Cristal 3: 90 + 0,5 × 60 = 90 + 30 = 120 (desplazamiento de +30, ¡FUERA DE LÍMITES!)
¿Ha detectado el problema? ¡LOS TRES CRISTALES SE HAN DESPLAZADO +30, independientemente de dónde estuvieran! El primer cristal estaba muy a la izquierda del objetivo y se desplazó hacia la derecha, lo cual es normal. El segundo ya ESTABA en el objetivo y lo empujaron hacia la derecha: un absurdo. El tercero estaba a la derecha del objetivo, lo empujaron aún más hacia la derecha y salió disparado fuera de los límites: un desastre.
Esto no es «moverse hacia el objetivo». Es un empujón idéntico para todos en la misma dirección, como si soplara un fuerte viento y los desplazara a todos la misma distancia. Además, la dirección y la intensidad de este «viento» vienen determinadas por los valores absolutos de la coordenada del objetivo, y no por la posición relativa de los cristales.
Fórmula modificada: x_new = x_old + r × (mean - x_old)
- Cristal 1: 10 + 0,5 × (60 - 10) = 10 + 25 = 35 (ha recorrido el 50 % del camino hacia el objetivo)
- Cristal 2: 60 + 0,5 × (60 - 60) = 60 + 0 = 60 (ya ha alcanzado el objetivo, se ha quedado en el mismo sitio)
- Cristal 3: 90 + 0,5 × (60 - 90) = 90 - 15 = 75 (ha recorrido el 50 % del camino de VUELTA hacia el objetivo)
¿Se aprecia la diferencia? Cada cristal se mueve HACIA su objetivo, de forma proporcional a la distancia que lo separa de él. El que está lejos da un paso grande. El que está cerca da un paso pequeño. El que ya está en el objetivo permanece inmóvil. El que ha sobrepasado el objetivo retrocede. Eso es justo lo que hace falta para optimizar.
Problema 1: Explosión con valores elevados de las coordenadas. Si las variables que se van a optimizar tienen un rango, digamos, de 0 a 1000, y la posición media de la población se sitúa en torno a 600-700, entonces a CADA cristal se le añade un número del orden de 600-700 (multiplicado por un coeficiente aleatorio comprendido entre 0 y 1). Incluso el cristal que se encuentra en la posición 650 (¡casi exactamente en el objetivo!) sufrirá un desplazamiento de +300...+600 y saldrá disparado hacia el límite de 1000 o más allá. El algoritmo se convierte en un generador de números aleatorios en los límites del espacio.
Problema 2: Dependencia de la escala de las coordenadas. Si se tiene un problema con variables de diferente escala (por ejemplo, x de 0 a 10, y de 0 a 1000), los desplazamientos en la variable y serán 100 veces mayores que en la variable x, ¡simplemente por la diferencia de escala! Esto no tiene nada que ver con lo lejos que se encuentre el cristal del valor óptimo en cada coordenada.
Problema 3: Todos los cristales se mueven en la misma dirección. Cuando se suma un vector idéntico a todos los cristales (aunque sea con coeficientes aleatorios diferentes), toda la población se desplaza como un todo en una misma dirección. No se trata de una «búsqueda del óptimo», sino de una «deriva poblacional». Podemos imaginar una bandada de pájaros que debería buscar alimento, pero cuyos integrantes, en lugar de hacerlo, vuelan todos al noreste de forma sincronizada, con pequeñas desviaciones aleatorias. Esto no es una búsqueda, es una migración.
Problema 4: Reinicializaciones constantes. Debido a los enormes desplazamientos, los cristales salen constantemente fuera de los límites. El algoritmo tiene que reinicializarlos en posiciones aleatorias. Esto significa que **se pierde toda la información acumulada sobre la dirección del movimiento**. El cristal se dirigía hacia una zona prometedora, salió disparado y fue teletransportado a un lugar aleatorio: todo el historial de su movimiento quedó borrado. En esencia, el algoritmo vuelve a la búsqueda aleatoria cada pocas iteraciones.
Memoria de la mejor solución: local frente a global. El segundo cambio importante tiene que ver con qué «mejor solución» se utiliza en las fórmulas. La versión modificada lleva un registro global de los mejores resultados. Cuando alguien alcanza los 3.000 metros de altitud, eso queda registrado y nunca se olvida. Aunque todos los investigadores hayan bajado después, el algoritmo recuerda: «El mejor lugar que hemos encontrado hasta ahora estaba allí, a 3.000 metros de altitud». Y es precisamente hacia este punto hacia donde son atraídos los demás investigadores. Esto es especialmente importante en los problemas de optimización, en los que la población puede deteriorarse temporalmente. Por ejemplo, se ha aplicado una mutación y todas las soluciones han empeorado. En el original, el algoritmo empezará a seguir las peores soluciones. En la versión modificada, el algoritmo seguirá dirigiéndose hacia la mejor solución realmente encontrada durante toda su ejecución.
Incorporación de una explotación local intensiva. El tercer cambio clave se refiere a un nuevo mecanismo que no aparece en la versión original. En la versión modificada, con una probabilidad del 10 %, cada coordenada del cristal se genera de forma específica en torno a la mejor solución global mediante la función «PowerDistribution» con el parámetro 20. El algoritmo original funciona como una metaheurística pura: los cristales se mueven por todo el espacio siguiendo sus propias estrategias. La versión modificada incorpora un elemento de búsqueda local: cada décima coordenada salta a las proximidades de la mejor solución encontrada. El parámetro 20 en PowerDistribution indica una concentración muy elevada, más o menos como si se buscaran las llaves en un radio de medio metro alrededor del lugar donde se recuerda haberlas visto por última vez. No se trata de un punto elegido al azar en esta zona, sino de uno con una probabilidad muy alta de encontrarse muy cerca del centro.
Simplificación del tratamiento de límites. La cuarta modificación se refiere a lo que ocurre cuando el cristal intenta salir de los límites permitidos del espacio de búsqueda. En la versión modificada, la coordenada simplemente se pasa a la función «u.SeInDiSp», que recorta el valor según los límites y aplica la discretización. ¿Por qué ha sido posible este cambio? Porque, gracias a las fórmulas de movimiento adecuadas, los cristales de la versión modificada rara vez traspasan los límites
En la versión original, debido a la suma directa de los vectores de posición, los cristales se salen constantemente de los límites, por lo que es necesario reinicializarlos. Pero esta reinicialización tiene un alto coste: en primer lugar, requiere la generación de números aleatorios y cálculos adicionales; en segundo lugar, convierte el movimiento dirigido en un desplazamiento aleatorio. El cristal podía estar moviéndose en una dirección prometedora, pero sobrepasó el límite y acabó en un lugar completamente aleatorio, perdiendo toda su trayectoria de movimiento.
Optimización del uso de la memoria. La quinta modificación parece insignificante desde el punto de vista técnico, pero demuestra que se ha comprendido lo que realmente necesita el algoritmo para funcionar. En la versión original, antes de actualizar la posición del cristal, su posición actual se copia en un array especial cP (posición anterior) y, a continuación, se utiliza esa copia en las fórmulas. Por ejemplo, la nueva coordenada se calcula sumando algo más a la coordenada anterior almacenada en el array cP. En la versión modificada, no se realiza esta copia. La fórmula simplemente toma el valor actual de la coordenada, calcula la variación y vuelve a asignar el resultado a la misma variable.
¿Por qué la versión original necesitaba una copia? Porque la fórmula tenía el siguiente formato: «x_new = x_old + algo». Para calcular el lado derecho, era necesario fijar x_old antes de que se produjeran los cambios. En la versión modificada, la fórmula se ha reestructurado de tal forma que se puede trabajar directamente con el valor actual: «x = x + variación». Para una población de 30 cristales en un espacio de 10 dimensiones, esto supone un ahorro de 300 operaciones de copia de datos en cada iteración. Puede parecer un detalle menor, pero cuando el algoritmo realiza miles de iteraciones, estos pequeños ahorros se acumulan.
En la visualización podemos observar cómo la versión modificada genera «formas cristalinas» durante su funcionamiento; también se aprecia la dispersión de los valores en las funciones de baja y media dimensión.

CryStAlm en la función de prueba Hilly

CryStAlm en la función de prueba Forest

CryStAlm en la función de prueba Forest

CryStAlm en la función de prueba estándar de Ackley
En la tabla de clasificación, el algoritmo CryStAlm aparece a título informativo; le faltó muy poco para que se le asignara una posición.
| N.º | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of 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 | DOAdingom | dingo_optimization_algorithm_M | 0,47968 | 0,45367 | 0,46369 | 1,39704 | 0,94145 | 0,87909 | 0,91454 | 2,73508 | 0,78615 | 0,86061 | 0,84805 | 2,49481 | 6,627 | 73,63 |
| 2 | ANS | across neighbourhood search | 0,94948 | 0,84776 | 0,43857 | 2,23581 | 1,00000 | 0,92334 | 0,39988 | 2,32323 | 0,70923 | 0,63477 | 0,23091 | 1,57491 | 6,134 | 68,15 |
| 3 | CLA | code lock algorithm (joo) | 0,95345 | 0,87107 | 0,37590 | 2,20042 | 0,98942 | 0,91709 | 0,31642 | 2,22294 | 0,79692 | 0,69385 | 0,19303 | 1,68380 | 6,107 | 67,86 |
| 4 | AMOm | animal migration optimization M | 0,90358 | 0,84317 | 0,46284 | 2,20959 | 0,99001 | 0,92436 | 0,46598 | 2,38034 | 0,56769 | 0,59132 | 0,23773 | 1,39675 | 5,987 | 66,52 |
| 5 | (P+O)ES | (P+O) evolution strategies | 0,92256 | 0,88101 | 0,40021 | 2,20379 | 0,97750 | 0,87490 | 0,31945 | 2,17185 | 0,67385 | 0,62985 | 0,18634 | 1,49003 | 5,866 | 65,17 |
| 6 | CTA | comet tail algorithm (joo) | 0,95346 | 0,86319 | 0,27770 | 2,09435 | 0,99794 | 0,85740 | 0,33949 | 2,19484 | 0,88769 | 0,56431 | 0,10512 | 1,55712 | 5,846 | 64,96 |
| 7 | TETA | time evolution travel algorithm (joo) | 0,91362 | 0,82349 | 0,31990 | 2,05701 | 0,97096 | 0,89532 | 0,29324 | 2,15952 | 0,73462 | 0,68569 | 0,16021 | 1,58052 | 5,797 | 64,41 |
| 8 | 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 |
| 9 | BOAm | billiards optimization algorithm M | 0,95757 | 0,82599 | 0,25235 | 2,03590 | 1,00000 | 0,90036 | 0,30502 | 2,20538 | 0,73538 | 0,52523 | 0,09563 | 1,35625 | 5,598 | 62,19 |
| 10 | AAm | archery algorithm M | 0,91744 | 0,70876 | 0,42160 | 2,04780 | 0,92527 | 0,75802 | 0,35328 | 2,03657 | 0,67385 | 0,55200 | 0,23738 | 1,46323 | 5,548 | 61,64 |
| 11 | ESG | evolution of social groups (joo) | 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 |
| 12 | SIA | simulated isotropic annealing (joo) | 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 |
| 13 | EOm | extremal_optimization_M | 0,76166 | 0,77242 | 0,31747 | 1,85155 | 0,99999 | 0,76751 | 0,23527 | 2,00277 | 0,74769 | 0,53969 | 0,14249 | 1,42987 | 5,284 | 58,71 |
| 14 | BBO | biogeography based optimization | 0,94912 | 0,69456 | 0,35031 | 1,99399 | 0,93820 | 0,67365 | 0,25682 | 1,86867 | 0,74615 | 0,48277 | 0,17369 | 1,40261 | 5,265 | 58,50 |
| 15 | ACS | artificial cooperative search | 0,75547 | 0,74744 | 0,30407 | 1,80698 | 1,00000 | 0,88861 | 0,22413 | 2,11274 | 0,69077 | 0,48185 | 0,13322 | 1,30583 | 5,226 | 58,06 |
| 16 | DA | dialectical algorithm | 0,86183 | 0,70033 | 0,33724 | 1,89940 | 0,98163 | 0,72772 | 0,28718 | 1,99653 | 0,70308 | 0,45292 | 0,16367 | 1,31967 | 5,216 | 57,95 |
| 17 | BHAm | black hole algorithm M | 0,75236 | 0,76675 | 0,34583 | 1,86493 | 0,93593 | 0,80152 | 0,27177 | 2,00923 | 0,65077 | 0,51646 | 0,15472 | 1,32195 | 5,196 | 57,73 |
| 18 | ASO | anarchy society optimization | 0,84872 | 0,74646 | 0,31465 | 1,90983 | 0,96148 | 0,79150 | 0,23803 | 1,99101 | 0,57077 | 0,54062 | 0,16614 | 1,27752 | 5,178 | 57,54 |
| 19 | RFO | royal flush optimization (joo) | 0,83361 | 0,73742 | 0,34629 | 1,91733 | 0,89424 | 0,73824 | 0,24098 | 1,87346 | 0,63154 | 0,50292 | 0,16421 | 1,29867 | 5,089 | 56,55 |
| 20 | AOSm | atomic orbital search M | 0,80232 | 0,70449 | 0,31021 | 1,81702 | 0,85660 | 0,69451 | 0,21996 | 1,77107 | 0,74615 | 0,52862 | 0,14358 | 1,41835 | 5,006 | 55,63 |
| 21 | TSEA | turtle shell evolution algorithm (joo) | 0,96798 | 0,64480 | 0,29672 | 1,90949 | 0,99449 | 0,61981 | 0,22708 | 1,84139 | 0,69077 | 0,42646 | 0,13598 | 1,25322 | 5,004 | 55,60 |
| 22 | BSA | backtracking_search_algorithm | 0,97309 | 0,54534 | 0,29098 | 1,80941 | 0,99999 | 0,58543 | 0,21747 | 1,80289 | 0,84769 | 0,36953 | 0,12978 | 1,34700 | 4,959 | 55,10 |
| 23 | 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 |
| 24 | SRA | successful restaurateur algorithm (joo) | 0,96883 | 0,63455 | 0,29217 | 1,89555 | 0,94637 | 0,55506 | 0,19124 | 1,69267 | 0,74923 | 0,44031 | 0,12526 | 1,31480 | 4,903 | 54,48 |
| 25 | CRO | chemical reaction optimisation | 0,94629 | 0,66112 | 0,29853 | 1,90593 | 0,87906 | 0,58422 | 0,21146 | 1,67473 | 0,75846 | 0,42646 | 0,12686 | 1,31178 | 4,892 | 54,36 |
| 26 | BIO | blood inheritance optimization (joo) | 0,81568 | 0,65336 | 0,30877 | 1,77781 | 0,89937 | 0,65319 | 0,21760 | 1,77016 | 0,67846 | 0,47631 | 0,13902 | 1,29378 | 4,842 | 53,80 |
| 27 | DOA | dream_optimization_algorithm | 0,85556 | 0,70085 | 0,37280 | 1,92921 | 0,73421 | 0,48905 | 0,24147 | 1,46473 | 0,77231 | 0,47354 | 0,18561 | 1,43146 | 4,825 | 53,62 |
| 28 | BSA | bird swarm algorithm | 0,89306 | 0,64900 | 0,26250 | 1,80455 | 0,92420 | 0,71121 | 0,24939 | 1,88479 | 0,69385 | 0,32615 | 0,10012 | 1,12012 | 4,809 | 53,44 |
| 29 | DEA | dolphin_echolocation_algorithm | 0,75995 | 0,67572 | 0,34171 | 1,77738 | 0,89582 | 0,64223 | 0,23941 | 1,77746 | 0,61538 | 0,44031 | 0,15115 | 1,20684 | 4,762 | 52,91 |
| 30 | 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 |
| 31 | 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 |
| 32 | BCOm | bacterial chemotaxis optimization M | 0,75953 | 0,62268 | 0,31483 | 1,69704 | 0,89378 | 0,61339 | 0,22542 | 1,73259 | 0,65385 | 0,42092 | 0,14435 | 1,21912 | 4,649 | 51,65 |
| 33 | ABO | african buffalo optimization | 0,83337 | 0,62247 | 0,29964 | 1,75548 | 0,92170 | 0,58618 | 0,19723 | 1,70511 | 0,61000 | 0,43154 | 0,13225 | 1,17378 | 4,634 | 51,49 |
| 34 | (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 |
| 35 | FBA | fractal-based Algorithm | 0,79000 | 0,65134 | 0,28965 | 1,73099 | 0,87158 | 0,56823 | 0,18877 | 1,62858 | 0,61077 | 0,46062 | 0,12398 | 1,19537 | 4,555 | 50,61 |
| 36 | TSm | tabu search M | 0,87795 | 0,61431 | 0,29104 | 1,78330 | 0,92885 | 0,51844 | 0,19054 | 1,63783 | 0,61077 | 0,38215 | 0,12157 | 1,11449 | 4,536 | 50,40 |
| 37 | BSO | brain storm optimization | 0,93736 | 0,57616 | 0,29688 | 1,81041 | 0,93131 | 0,55866 | 0,23537 | 1,72534 | 0,55231 | 0,29077 | 0,11914 | 0,96222 | 4,498 | 49,98 |
| 38 | WOAm | wale optimization algorithm M | 0,84521 | 0,56298 | 0,26263 | 1,67081 | 0,93100 | 0,52278 | 0,16365 | 1,61743 | 0,66308 | 0,41138 | 0,11357 | 1,18803 | 4,476 | 49,74 |
| 39 | AEFA | artificial electric field algorithm | 0,87700 | 0,61753 | 0,25235 | 1,74688 | 0,92729 | 0,72698 | 0,18064 | 1,83490 | 0,66615 | 0,11631 | 0,09508 | 0,87754 | 4,459 | 49,55 |
| 40 | AEO | artificial ecosystem-based optimization algorithm | 0,91380 | 0,46713 | 0,26470 | 1,64563 | 0,90223 | 0,43705 | 0,21400 | 1,55327 | 0,66154 | 0,30800 | 0,28563 | 1,25517 | 4,454 | 49,49 |
| 41 | CAm | camel algorithm M | 0,78684 | 0,56042 | 0,35133 | 1,69859 | 0,82772 | 0,56041 | 0,24336 | 1,63149 | 0,64846 | 0,33092 | 0,13418 | 1,11356 | 4,444 | 49,37 |
| 42 | 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 |
| 43 | CMAES | covariance_matrix_adaptation_evolution_strategy | 0,76258 | 0,72089 | 0,00000 | 1,48347 | 0,82056 | 0,79616 | 0,00000 | 1,61672 | 0,75846 | 0,49077 | 0,00000 | 1,24923 | 4,349 | 48,33 |
| 44 | DA_duelist | duelist_algorithm | 0,92782 | 0,53778 | 0,27792 | 1,74352 | 0,86957 | 0,47536 | 0,18193 | 1,52686 | 0,62153 | 0,33569 | 0,11715 | 1,07437 | 4,345 | 48,28 |
| 45 | 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 |
| CryStAlm | crystal_structure_algorithm_M | 0,80656 | 0,56147 | 0,29097 | 1,65900 | 0,75228 | 0,48674 | 0,21014 | 1,44916 | 0,48461 | 0,27015 | 0,11111 | 0,86587 | 3.974 | 44,16 | |
| RW | random walk | 0,48754 | 0,32159 | 0,25781 | 1,06694 | 0,37554 | 0,21944 | 0,15877 | 0,75375 | 0,27969 | 0,14917 | 0,09847 | 0,52734 | 2,348 | 26,09 | |
Conclusiones
Nos encontramos ante una idea atractiva, arruinada por su implementación. El algoritmo Crystal Structure Algorithm apareció en 2021 con un concepto atractivo: utilizar los principios de formación de estructuras cristalinas para la optimización global. Los autores han propuesto un algoritmo poblacional en el que los «cristales» se mueven bajo la influencia de la posición media de la población, la mejor solución encontrada y los vecinos seleccionados al azar. Cuatro estrategias de movimiento, un elegante modelo matemático. Sobre el papel, todo parecía convincente.
El problema es que entre la idea conceptual y una implementación que funcione hay una etapa crucial: la traducción de la metáfora física en operaciones matemáticas concretas. Y es precisamente aquí donde el CryStAl original fracasa. Las fórmulas que parecen razonables en el artículo convierten, en la práctica, la búsqueda dirigida en un paseo caótico. No se trata simplemente de una historia del tipo «encontramos un error y lo corregimos», sino de una lección fundamental sobre cómo, en el desarrollo de metaheurísticas, el concepto y la implementación matemática deben estar en consonancia; de lo contrario, el algoritmo no funciona como se pretendía o no funciona en absoluto.
La brecha entre la idea y la ejecución. Veamos qué QUERÍAN implementar los autores en el CryStAl original. La idea es clara: los cristales deben ser atraídos hacia tres puntos clave: la posición media de toda la población (centro de masas, información global), el mejor cristal encontrado (explotación) y la posición media de los vecinos seleccionados al azar (información local, diversidad). Las cuatro estrategias combinan estas fuerzas de atracción de diferentes maneras. En teoría, esto crea un equilibrio entre la exploración de nuevas zonas del espacio de búsqueda y la intensificación de la búsqueda en regiones prometedoras. La analogía física es muy bonita: los átomos interactúan con sus vecinos y tienden a alcanzar una configuración de equilibrio. Los autores QUERÍAN implementar la «atracción hacia el objetivo», pero ESCRIBIERON una «suma de un vector». ¡Son operaciones diferentes!
Un error sistémico de razonamiento: fórmulas en lugar de geometría. La raíz del problema va más allá de una sola fórmula errónea. Se trata de un error de razonamiento al diseñar el algoritmo: centrarse en las fórmulas en lugar de comprender qué efectos tienen en la geometría del espacio de búsqueda. Los autores del CryStAl original escribieron: «El cristal se desplaza hacia la posición media, según la fórmula: x + r × mean». Se centraron en la expresión algebraica, sin imaginar qué ocurriría con los cristales en diferentes partes del espacio. Para adoptar el enfoque adecuado, hay que plantearse las siguientes preguntas:
- ¿Qué debe ocurrir con el cristal que ya se encuentra en el punto objetivo? Respuesta: debe permanecer allí o dar un paso muy pequeño. La fórmula original lo aleja de ese punto. La fórmula modificada lo mantiene en su posición (cuando x_old = mean, obtenemos x + 0 × (mean - x) = x).
- ¿Qué debe ocurrir con el cristal que se encuentra más allá del objetivo? Respuesta: debe retroceder hacia el objetivo. La fórmula original lo empuja aún más en esa misma dirección. La fórmula modificada invierte su dirección (una diferencia negativa provoca un movimiento hacia atrás).
- ¿Debe depender el tamaño del paso de los valores absolutos de las coordenadas? Respuesta: no, debe depender de la distancia al objetivo. El original depende de valores absolutos. La modificación depende de las distancias.
- ¿Qué ocurre cuando las variables tienen escalas diferentes? Original: los desplazamientos en las distintas coordenadas no son proporcionales a sus distancias relativas respecto al objetivo. Modificación: los desplazamientos se ajustan automáticamente en función de las distancias relativas.
Las respuestas a estas preguntas ponen de manifiesto de inmediato que la fórmula x + r × target es geométricamente incorrecta para modelar la atracción. En cambio, la fórmula x + r × (target - x) es geométricamente correcta: se trata de una interpolación, un desplazamiento que recorre una fracción r del trayecto hacia el objetivo, con una desaceleración natural al acercarse a él.
Muchas fórmulas no subsanan una base incorrecta. Puede dar la impresión de que las cuatro estrategias de CryStAl compensan mutuamente sus deficiencias. La estrategia 0, con un solo punto objetivo, funciona mal, pero ¿no debería funcionar mejor la estrategia 3, con tres puntos objetivo? En la práctica ocurre justo lo contrario: la multiplicación de operaciones incorrectas agrava el problema.
Fórmula de la estrategia 3: x_new = x_old + r1 × mean + r2 × best + r3 × fc, donde fc es la media de los cristales seleccionados al azar. Ahora sumamos TRES números grandes (las coordenadas absolutas de los tres puntos objetivo). Consideremos un ejemplo: variables de 0 a 1000, un cristal en [640, 430, 770], mean = [650, 420, 780], best = [645, 425, 775], fc = [655, 415, 785], coeficientes r1 = r2 = r3 = 0.4.
Primera coordenada: 640 + 0.4 × 650 + 0.4 × 645 + 0.4 × 655 = 640 + 260 + 258 + 262 = 1420: ¡aún más allá del límite!
La estrategia 3 debía ser la más compleja y eficaz (equilibra la información global, la información local y la explotación), pero en la práctica genera los desplazamientos más extremos, ya que suma aún más valores absolutos. El problema no radica en el número de componentes, sino en que la operación básica —sumar directamente las coordenadas absolutas en lugar de utilizar desplazamientos relativos— es fundamentalmente errónea.
De la búsqueda aleatoria a la optimización dirigida. ¿Qué hace realmente el CryStAl original en la práctica? Tras varias iteraciones, se establece el siguiente modo de funcionamiento: en cada paso, la población sufre desplazamientos enormes, la mayoría de los cristales salen fuera de los límites y sus coordenadas se reinician de forma aleatoria. De hecho, cada 2 o 3 iteraciones, el algoritmo genera una nueva población casi aleatoria, conservando solo una pequeña parte de las coordenadas de la generación anterior.
CryStAlm, la versión modificada, funciona de forma radicalmente distinta. Los cristales se desplazan realmente hacia los puntos de destino, en lugar de moverse de forma caótica. Las trayectorias son suaves y controladas. Las salidas fuera de los límites son poco frecuentes. La población converge de forma metódica hacia las áreas prometedoras, al tiempo que conserva su diversidad gracias a estrategias aleatorias y al mecanismo de repulsión. Cada iteración acumula información sobre el paisaje de la función y la utiliza para los pasos siguientes, sin borrar el estado anterior mediante regeneraciones aleatorias.
Lección metodológica para investigadores. La historia de CryStAl no solo supone un ejemplo de implementación fallida. Se trata de un problema sistémico en el desarrollo de algoritmos metaheurísticos.
Un contexto más amplio: la epidemia de algoritmos deficientes. CryStAl no es un caso único. En la bibliografía sobre metaheurística de los últimos 15 años hay cientos de algoritmos «nuevos», inspirados en diversas metáforas, y muchos de ellos adolecen del mismo problema: una idea atractiva, una implementación poco rigurosa, pruebas realizadas en un conjunto limitado de problemas y una publicación en la que se proclama su competitividad. Después, otros investigadores toman estos algoritmos como referencia para comparar sus propios algoritmos, creando así una cadena de comparaciones con fundamentos esencialmente débiles.
La transformación de CryStAl en CryStAlm permite realizar un análisis en profundidad. Cambios mínimos en el código (reescribir las fórmulas de movimiento, añadir PowerDistribution, utilizar cB en lugar de bestCrystalIdx), pero cambios fundamentales en el comportamiento.
La comparación entre CryStAl y CryStAlm ofrece varias lecciones fundamentales para la comunidad de investigadores en el ámbito de la optimización metaheurística:
Lección 1: El concepto no equivale a la implementación. Una idea elegante para un algoritmo es solo el principio. La traducción de una idea en operaciones matemáticas requiere una comprensión profunda de la geometría del espacio de búsqueda. Las fórmulas deben hacer lo que se pretende, y no solo parecer verosímiles sobre el papel. Es necesario comprobar no solo «qué calcula la fórmula», sino también «qué hace con los agentes en diferentes situaciones».
Lección 2: La abstracción oculta los errores. Cuando se escribe «el cristal es atraído hacia la posición media», es fácil pasar por alto que la fórmula no implementa una atracción, sino un desplazamiento paralelo. El pensamiento abstracto («avanzar hacia el objetivo») debe ir acompañado de una verificación concreta («cómo cambiarán exactamente las coordenadas»). Es necesario comprobar siempre las fórmulas con ejemplos numéricos concretos.
Lección 3: Las pruebas estándar no son suficientes. Las pruebas con el banco de pruebas CEC y variables normalizadas pueden ocultar problemas críticos que se manifiestan a escalas realistas o con intervalos heterogéneos. Conviene añadir pruebas con condiciones «difíciles»: rangos muy amplios, distintas escalas de las variables y óptimos estrechos. Es necesario visualizar el comportamiento del algoritmo, no solo los resultados.
Lección 4: Por muchos mecanismos que se utilicen, no se compensa una base incorrecta. Si la operación básica (por ejemplo, una fórmula de movimiento) es incorrecta, añadir complementos complejos no servirá de nada. Primero hay que asegurarse de que la base funciona y, después, introducir mejoras. Un mecanismo adecuado es mejor que diez inadecuados.
Lección 5: Las comparaciones requieren verificar el algoritmo de referencia. Si el nuevo algoritmo supera al existente, cabe preguntarse: ¿funciona siquiera ese algoritmo de referencia? Comprobación rápida: comparar el algoritmo de referencia con la búsqueda aleatoria. Si la diferencia es pequeña, la comparación se está haciendo con un algoritmo sin valor y el resultado obtenido no significa nada.
Lección 6: Los detalles de la implementación son fundamentales. La diferencia entre una fórmula «casi correcta» y una «correcta» puede ser enorme en cuanto al rendimiento. x + r × mean y x + r × (mean - x) difieren en unos pocos caracteres en el código, pero la calidad de sus resultados difiere en un factor de dos. Los detalles importan. No deben pasarse por alto como si fueran «detalles técnicos sin importancia».
CryStAl demuestra que la metaheurística no es una simple recopilación de metáforas y fórmulas. Es una disciplina de ingeniería en la que comprender cómo las operaciones influyen en la dinámica de la búsqueda en el espacio de soluciones es tan importante como el concepto inicial. Una idea elegante, implementada sin el debido cuidado, da como resultado un algoritmo que funciona como una búsqueda aleatoria. Esa misma idea, aplicada con un buen conocimiento de la geometría y la dinámica, da como resultado una herramienta eficaz.
Para que este campo avance, no basta con crear nuevas metáforas. Hay que crear algoritmos que realmente hagan lo que prometen: explorar el espacio de forma dirigida, acumular información y converger hacia los puntos óptimos. Y esto no solo requiere escribir fórmulas, sino analizar en profundidad si dichas fórmulas plasman correctamente la idea original.

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

Figura 3. 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 CryStAlm:
Ventajas:
- Una implementación relativamente sencilla.
- Es rápido.
- Resultados estables de nivel medio (color amarillo, sin caídas importantes en pruebas concretas).
Inconvenientes:
- Dispersión de valores en funciones de dimensionalidad baja y media.
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.
Programas utilizados en el artículo
| # | Nombre | Tipo | Descripción |
|---|---|---|---|
| 1 | #C_AO.mqh | Archivo de inclusión | Clase padre de los algoritmos de optimización poblacional |
| 2 | #C_AO_enum.mqh | Archivo de inclusión | Enumeración de algoritmos de optimización poblacional |
| 3 | TestFunctions.mqh | Archivo de inclusión | Biblioteca de funciones de prueba |
| 4 | TestStandFunctions.mqh | Archivo de inclusión | Biblioteca de funciones del banco de pruebas |
| 5 | Utilities.mqh | Archivo de inclusión | Biblioteca de funciones auxiliares |
| 6 | CalculationTestResults.mqh | Archivo de inclusión | Script para calcular los resultados destinados a la tabla comparativa |
| 7 | Testing AOs.mq5 | Script | Banco de pruebas unificado para todos los algoritmos de optimización poblacional |
| 8 | Simple use of population optimization algorithms.mq5 | Script | Ejemplo sencillo de uso de algoritmos de optimización poblacional sin visualización |
| 9 | Test_AO_CryStAlm.mq5 | Script | Banco de pruebas para CryStAlm |
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/19899
Advertencia: todos los derechos de estos materiales pertenecen a MetaQuotes Ltd. Queda totalmente prohibido el copiado total o parcial.
Este artículo ha sido escrito por un usuario del sitio web y refleja su punto de vista personal. MetaQuotes Ltd. no se responsabiliza de la exactitud de la información ofrecida, ni de las posibles consecuencias del uso de las soluciones, estrategias o recomendaciones descritas.