Algoritmo de búsqueda con retroceso — Backtracking Search Algorithm (BSA)
50
0
Contenido
Introducción
En el laberinto infinito de posibilidades, donde cada giro puede llevar tanto al triunfo como a un callejón sin salida, el viajero sabio deja tras de sí huellas invisibles: algo efímero, pero al mismo tiempo más fiable, el recuerdo de los caminos recorridos. Esta sabiduría ancestral —la de mirar hacia atrás para ver el futuro— constituye la base del algoritmo de optimización. Cada paso hacia lo desconocido se da con la mirada puesta en la experiencia del pasado, donde la historia se convierte en una brújula y los recuerdos en un mapa.
En este artículo, analizaremos un algoritmo que me ha parecido muy interesante debido a su idea de búsqueda. El Backtracking Search Algorithm (algoritmo de búsqueda por retroceso, BSA) es un nuevo algoritmo evolutivo (EA) para resolver problemas de optimización numérica de valores reales, propuesto por Pinar Civicioglu en 2013, y es un método para encontrar la mejor solución que permite "aprender de la experiencia pasada".
Implementación del algoritmo
El BSA funciona según el principio de los algoritmos evolutivos, pero tiene características únicas, ya que utiliza dos poblaciones:- la población actual (P) es una población en constante evolución.
- la población histórica (oldP): una población seleccionada aleatoriamente de generaciones pasadas.
El BSA utiliza una estrategia de mutación aleatoria que produce una única solución direccional para cada individuo objetivo. Fórmula de mutación:
Mutant = P + F × (oldP - P)
donde F es el factor de amplitud que controla el tamaño del paso de búsqueda.
El proceso de cruce de BSA incluye dos pasos. La primera estrategia utiliza "mixrate". La segunda estrategia permite que solo un individuo seleccionado al azar mute en cada muestra. Imagine que usted y sus amigos (esa es nuestra población) están buscando la mejor pizzería de la ciudad.
Situación inicial:
- tiene 10 amigos (tamaño de la población),
- todos comienzan a buscar en un área aleatoria de la ciudad,
- cada uno tiene un teléfono inteligente con el mapa de los viajes pasados (memoria histórica).
Día 1: todos se dispersan por la ciudad. El primer amigo encuentra una pizzería con una calificación de 7/10, el segundo amigo, una pizzería con una calificación de 5/10, y el tercero, una pizzería con una calificación de 8/10... y así sucesivamente.
Día 2: ponemos en práctica la experiencia acumulada.
Paso 1: "recordamos el pasado" (Selection-I). Algoritmo: "¡Lancemos una moneda!" Si sale cara, entonces "Recordamos dónde estaba cada uno ayer" (actualizamos la historia); si sale cruz, "Usamos los recuerdos antiguos" (no actualizamos); entonces "Mezclamos los recuerdos" (como una baraja de cartas).
Segundo paso: "Seguimos las huellas" (Mutation). Todos los amigos piensan: "¿Dónde estoy ahora? (posición actual), ¿y dónde estaba antes?" (posición histórica). Entonces la fórmula del movimiento será: Nueva ubicación = Ubicación actual + Paso aleatorio × (Ubicación anterior - Ubicación actual). Por ejemplo: el primer amigo está ahora en la calle A, 10, su "fantasma del pasado" estaba en la calle B, 20, paso aleatorio = 2. Nueva ubicación = A.10 + 2 × (B.20 - A.10) = movimiento hacia la calle B, ¡pero 2 veces más lejos!
"Corregimos la ruta" (Crossover). El algoritmo lanza una moneda y elige una estrategia. Estrategia A: "Cambio parcial". El primer amigo planeaba ir a una dirección determinada, pero el algoritmo dice: "Simplemente cambia de calle, deja la casa como estaba". Resultado: de acuerdo, cambiamos la calle, pero mantenemos la casa. Estrategia B: "Cambio mínimo." El primer amigo planeaba ir a una dirección determinada, pero el algoritmo dice: "Quédate en el mismo sitio, pero cambia solo el número de la casa". Resultado: de acuerdo, cambiamos el número de la casa.
"Comprobamos el resultado general" (Selection II). El amigo 1 llega a un lugar nuevo:
- Si la nueva pizzería es mejor (puntuación 9/10): "¡Genial, me quedaré aquí!"
- Si es peor (calificación 4/10): "¡No, voy a volver!"
Veamos la ilustración del funcionamiento del algoritmo en la siguiente figura.
Figura 1. Ilustración del funcionamiento de las fases del algoritmo BSA.
Esta ilustración muestra cómo el algoritmo BSA busca una solución óptima en un espacio bidimensional. Imagine que está mirando un mapa topográfico desde arriba, donde el objetivo es encontrar el punto más alto (centro rojo).
La ilustración está dividida en tres paneles que muestran la evolución de la búsqueda: Iteration 1 — Random Initialization. Un campo de búsqueda cuadrado con líneas de contorno (como en un mapa topográfico), el punto rojo en el centro es el óptimo global (mejor solución), los 4 puntos azules (P1, P2, P3, P4) son las posiciones aleatorias iniciales de los "exploradores". El algoritmo coloca aleatoriamente 4 agentes en el espacio de búsqueda; en esta etapa, oldP = P (la población histórica copia a la actual) y este es el punto de partida de la búsqueda.
Iteration 2 - Mutation Step. Los puntos azules representan las posiciones actuales de los agentes, los puntos verdes translúcidos representan las posiciones obtenidas de la memoria histórica (mixtas) y las flechas rojas indican las direcciones de movimiento durante la mutación.
Elementos clave: las flechas rojas muestran la fórmula de mutación en acción: M = P + F × (oldP - P). Cada agente se mueve en relación con su "par histórico". Algunas flechas apuntan hacia posiciones históricas, otras se alejan de ellas (dependiendo del signo F). Fórmula en el recuadro rojo: F = 3 × randn(); M = P + F × (oldP - P). Esta es la fórmula clave para la mutación BSA.
Iteration 3 - After Crossover & Selection. Los puntos violeta representan las nuevas posiciones después del cruce (población de prueba), los puntos azules translúcidos representan las posiciones anteriores (para comparación) y las flechas verdes muestran solo las mejoras (donde la nueva posición es mejor que la anterior). Cruce: el algoritmo ha combinado información de las poblaciones mutantes y actuales. La selección voraz ha conservado solo aquellos movimientos que han mejorado la solución. La población se ha acercado al óptimo (centro rojo).
BSA Process Summary, el ciclo completo del algoritmo como una secuencia de círculos de colores:- Init (azul) — inicio aleatorio
- Select-I (verde) — actualización de memoria con una probabilidad del 50%.
- Mutate (rojo) — aplicación de la fórmula de mutación
- Crossover (violeta) — combinación de soluciones
- Evaluate (naranja) — cálculo de calidad
- Select-II (turquesa) — selección codiciosa de las mejores
La flecha punteada indica que el proceso se repite hasta la convergencia. Esta ilustración demuestra claramente por qué el BSA es eficaz: "recuerda" dónde ha estado antes y utiliza esa información para buscar de forma más inteligente que un simple paseo aleatorio.
Pasemos ahora a escribir el pseudocódigo para el algoritmo BSA.
Preparación para el trabajo
Parámetros iniciales:
- Establecemos el tamaño de la población
- Establecemos el parámetro de cruce mixrate
- Creamos contenedores vacíos para:
- la población actual
- la población histórica
- la población mutante
- la población de prueba
- los mapas de cruce para cada individuo
Inicialización:
- Colocamos aleatoriamente a todos los individuos de la población histórica en el espacio de búsqueda.
- Tendremos en cuenta, además, la discretización si se da el paso
- Establecemos el indicador "selección requerida" en "no".
Ciclo principal del algoritmo
PASO 1: Primer inicio
Si esta es la primera iteración:
- Colocamos la población actual al azar
- Aplicamos la discretización a las coordenadas
- Marcamos que la inicialización ha finalizado
- Salimos y esperamos a que se calcule la aptitud
PASO 2: Selección codiciosa (si es necesaria)
Si se activa la bandera "selección requerida":
- Para cada individuo, comparamos:
- Si la nueva solución es peor que la guardada, se retornan las coordenadas antiguas y la aptitud.
- si es mejor → conservamos la nueva
- Restablecemos la bandera de selección
PASO 3: Guardado del estado actual
Para cada individuo:
- Recordamos la aptitud actual
- Guardamos una copia de las coordenadas actuales.
PASO 4: Actualización de la memoria histórica (Selection-I)
- Lanzamos una moneda (50% de probabilidad)
- Si la moneda cae en cara:
- copiamos a toda la población actual en la memoria histórica
- preservamos su aptitud
- barajamos la población histórica como si fuera una baraja de cartas:
- vamos desde el último individuo hasta el primero
- para cada uno, seleccionamos una posición aleatoria para el intercambio
- intercambio de lugares
PASO 5: Mutación
- Generación de un factor de movimiento F a partir de una distribución normal.
- promedio = 0, rango de -3 a +3
- es como una tirada de dados, pero con una distribución en forma de campana.
- Para cada individuo y cada coordenada:
- Nueva posición = Actual + F × (Histórica - Actual)
- Si F es positivo → movimiento a la posición histórica
- Si F es negativo → movimiento desde la posición histórica
PASO 6: Cruce
- Copiamos la población mutante en la población de prueba.
- Lanza una moneda ponderada (40% / 60%)
Si obtenemos un 40% (Estrategia 1):
Para cada individuo:
- determinamos cuántas coordenadas cambiar (de 0 a todas, usando mixrate)
- seleccionamos aleatoriamente qué coordenadas
- para las coordenadas seleccionadas, tomamos valores de la población actual.
- dejamos el resto de la mutante
Si obtenemos un 60% (Estrategia 2):
Para cada individuo:
- elegimos solo una coordenada aleatoria
- la reemplazamos con un valor de la población actual
- dejamos todo lo demás de la mutante
PASO 7: Control de límites
Para cada individuo de la población de prueba:
- Comprobamos cada coordenada
- Si ha traspasado los límites:
- lanzamos una moneda (50/50)
- Si sale "cara" → generamos un nuevo valor aleatorio dentro de los límites
- Si sale "cruz" → colocamos en el borde más cercano
- Aplicamos discretización si se especifica un paso
PASO 8: Preparación para la evaluación
- Copiamos la población de prueba a la población principal para su evaluación
- Establecemos el indicador "selección requerida" en "sí".
- Transferimos el control para el cálculo de aptitud
Después de calcular la aptitud
- Encontramos al individuo con la mejor aptitud
- Si encontramos alguna mejor que el récord global:
- actualizamos el registro global
- guardamos las coordenadas de la mejor solución
Repetición
Volvemos al PASO 2 y continuamos hasta que:
- No se haya logrado la convergencia.
- o no se haya agotado el límite de iteraciones
Ahora que entendemos los puntos principales, comenzaremos a escribir el código del algoritmo. La clase "C_AO_BSA_Backtracking" será una implementación del algoritmo de retroceso BSA para la resolución de problemas de optimización. Heredará la clase básica "C_AO", que define una interfaz común para algoritmos de optimización.
Características principales y finalidad:
Parámetros de optimización:- popSize — tamaño de la población, el número de "agentes" o "soluciones" que el algoritmo considera simultáneamente.
- mixrate — parámetro de cruce que controla el grado de "mezcla" de información entre los agentes al crear nuevas soluciones.
- El constructor de la clase inicializa los parámetros básicos y agrega "popSize" y "mixrate" al array "params", que se utiliza para controlar los parámetros del algoritmo.
- El método "SetParams" permite actualizar los parámetros internos del algoritmo según los valores obtenidos del array "params". También incluye comprobaciones básicas de validez del valor.
- Init — para la configuración inicial del algoritmo, incluyendo la definición de los rangos de cambio de las variables (valores mínimos y máximos, y pasos) y el número de épocas de optimización.
- Moving — describe la iteración principal del algoritmo, responsable de generar nuevos "candidatos" o soluciones "en movimiento" según la población actual.
- Revision — evalúa las soluciones generadas y actualiza la población según su calidad.
- oldP — array que representa la población "histórica" o anterior de agentes.
- M — array para la población resultante de la mutación.
- T — array para la población de "prueba", que se utiliza para compararla con la población actual antes de tomar decisiones.
- F — factor de amplitud para la mutación, que influye en la magnitud del cambio tras la mutación.
- needSelection — bandera que señala la necesidad de realizar la segunda etapa de selección.
- prevFitness — array para almacenar los valores de aptitud de los agentes de la iteración anterior.
- S_Map — estructura auxiliar que contiene un mapa binario, utilizado durante el proceso de cruce para determinar qué variables de agente se "mezclarán" a partir de diferentes padres.
- map — array de estos mapas binarios, uno para cada agente.
- Selectionl — primera etapa del proceso de selección, encargada de elegir a los agentes que crearán nuevas soluciones.
- Mutation — aplica la operación de mutación a los agentes seleccionados.
- Crossover — realiza una operación de cruce (mezcla) entre agentes para crear nuevas soluciones de "prueba".
- BoundaryControl — comprueba que los valores de los parámetros del agente se mantengan dentro de los límites especificados (mínimo y máximo).
- ShufflePopulation — método para mezclar aleatoriamente una población.
De este modo, la clase "C_AO_BSA_Backtracking" implementa un algoritmo de optimización evolutiva que usa los conceptos de población, mutación y cruce, así como mecanismos específicos del BSA, como el retroceso, para resolver problemas de optimización.
//———————————————————————————————————————————————————————————————————— class C_AO_BSA_Backtracking : public C_AO { public: //---------------------------------------------------------- ~C_AO_BSA_Backtracking () { } C_AO_BSA_Backtracking () { ao_name = "BSA"; ao_desc = "Backtracking Search Algorithm"; ao_link = "https://www.mql5.com/ru/articles/18568"; popSize = 10; // размер популяции mixrate = 1.0; // параметр кроссовера ArrayResize (params, 2); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "mixrate"; params [1].val = mixrate; } void SetParams () { popSize = (int)params [0].val; mixrate = params [1].val; // Проверка корректности параметров //if (popSize < 2) popSize = 2; if (mixrate < 0.0) mixrate = 0.0; if (mixrate > 1.0) mixrate = 1.0; } bool Init (const double &rangeMinP [], // минимальные значения const double &rangeMaxP [], // максимальные значения const double &rangeStepP [], // шаг изменения const int epochsP = 0); // количество эпох void Moving (); void Revision (); //------------------------------------------------------------------ double mixrate; // параметр кроссовера private: //--------------------------------------------------------- S_AO_Agent oldP []; // историческая популяция S_AO_Agent M []; // мутантная популяция (Mutant) S_AO_Agent T []; // пробная популяция (Trial) double F; // фактор амплитуды для мутации bool needSelection; // флаг необходимости выполнения Selection-II double prevFitness []; // массив для хранения предыдущих fitness // Вспомогательные структуры для кроссовера struct S_Map { int val []; // бинарная карта для кроссовера void Init (int size) { ArrayResize (val, size); ArrayInitialize (val, 0); } }; S_Map map []; // массив бинарных карт для каждого агента // Методы алгоритма void SelectionI (); void Mutation (); void Crossover (); void BoundaryControl (S_AO_Agent &agent); void ShufflePopulation (S_AO_Agent &pop []); }; //————————————————————————————————————————————————————————————————————
El método "Init" se encarga de preparar el algoritmo para su funcionamiento antes de comenzar la optimización. En primer lugar, se llama a la función de inicialización básica, que establece los parámetros básicos relacionados con los rangos de valores de las variables (valores mínimos, máximos y paso de cambio). Si este paso básico falla, el método se interrumpe y retorna un error.
A continuación, se asignan y preparan las estructuras de datos internas concretas del algoritmo BSA. En concreto, se crean arrays de población y se ajustan al tamaño necesario: la población histórica "oldP", la población mutante "M", la población de prueba "T", así como un array de mapas binarios para el cruce "map" y un array para almacenar los valores de aptitud anteriores de cada agente "prevFitness". El indicador que señala la necesidad de una selección adicional está configurado inicialmente en false.
Posteriormente, se llaman métodos de inicialización para cada agente de la población; estos preparan las estructuras internas de cada agente de acuerdo con el número de parámetros de la tarea.
Luego, la población histórica se completa con valores iniciales. Para cada agente y cada parámetro de su conjunto, se genera un valor aleatorio dentro de un rango determinado, tras lo cual este valor se ajusta según un paso de cambio dado. Si todos estos pasos se completan con éxito, el método retorna un valor que indica que el objeto del algoritmo se ha inicializado correctamente y está listo para una mayor optimización.
//———————————————————————————————————————————————————————————————————— //--- Инициализация bool C_AO_BSA_Backtracking::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Инициализация дополнительных структур BSA ArrayResize (oldP, popSize); ArrayResize (M, popSize); ArrayResize (T, popSize); ArrayResize (map, popSize); ArrayResize (prevFitness, popSize); needSelection = false; for (int i = 0; i < popSize; i++) { oldP [i].Init (coords); M [i].Init (coords); T [i].Init (coords); map [i].Init (coords); } // Инициализация исторической популяции oldP for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { oldP [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); oldP [p].c [c] = u.SeInDiSp (oldP [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } return true; } //————————————————————————————————————————————————————————————————————
El método "Moving" describe el paso principal del algoritmo de optimización BSA y es el responsable de generar nuevos candidatos a soluciones en la población. En la primera llamada al método, cuando el indicador "revisión" es false, la población activa "a" se inicializa. Para cada agente de la población y para cada uno de sus parámetros, se genera un valor aleatorio dentro de un rango determinado (mínimo y máximo). Este valor aleatorio se ajusta posteriormente según el paso de cambio de parámetro especificado. Tras la inicialización, el indicador "revision" se establece en true (para que este bloque no se ejecute en llamadas posteriores) y el indicador "needSelection" se desactiva. El método finaliza.
Ejecución de selección codiciosa (Selection-II) (se realiza si es necesario) : si la bandera "needSelection" es true, significa que se ha generado una nueva población en el paso anterior y ahora su aptitud debe compararse con la aptitud de las soluciones anteriores. La iteración se produce para cada agente de la población. El valor de aptitud actual del agente "a[i].f" (que se ha calculado para la solución de "prueba") se compara con su aptitud en el paso anterior, almacenada en "prevFitness[i]". Si la solución de "prueba" "a [i]" ha resultado peor que la anterior, entonces los valores de coordenadas del agente actual "a [i].c" se restauran a partir de "a [i].cP" (las coordenadas del agente en el paso anterior), y su aptitud "a [i].f" también se restaura a "prevFitness [i]". Esto garantiza que la población no se deteriore. Una vez completada la selección, se restablece el indicador "needSelection".
Los pasos principales del algoritmo BSA (después de la inicialización o selección) son: antes de generar nuevas soluciones, los valores de aptitud actuales de todos los agentes de "a" se guardan en "prevFitness" para su uso posterior en "Selection-II" y las coordenadas actuales de los agentes de "a[i].c" se copian a "a[i].cP" para poder revertirse si las nuevas soluciones resultan ser peores.
Llamamos al método interno "SelectionI". Este paso se encarga de seleccionar o preparar la población de "archivo" "oldP" que se usará para la mutación. Llamamos al método interno "Mutation". En este paso, se genera una población "mutante" "M" basada en las poblaciones activas y/o archivadas. Llamamos al método interno "Crossover". En este paso, la población mutante "M" se mezcla con la población activa actual "a", lo que da como resultado la formación de una población de "prueba" "T".
Las coordenadas de los agentes de la población de prueba generada "T" se copian en la población activa "a". Ahora "a" contiene nuevas soluciones de "prueba" cuya aptitud debe calcularse. El indicador "needSelection" está configurado como "true". Esto indica que en la siguiente llamada "Moving" (después de que se haya calculado la aptitud de las nuevas soluciones en "a"), se debe realizar una selección codiciosa (Selection-II).
De este modo, el método "Moving" engloba una iteración completa o "época" del algoritmo BSA, incluyendo la inicialización, la selección, la mutación, el cruce y la preparación para la comparación de resultados.
//———————————————————————————————————————————————————————————————————— //--- Основной шаг алгоритма void C_AO_BSA_Backtracking::Moving () { // Начальная инициализация популяции if (!revision) { for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { a [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; needSelection = false; return; } // Если нужно выполнить жадный отбор после вычисления fitness if (needSelection) { // Selection-II: Жадный отбор for (int i = 0; i < popSize; i++) { // Если текущее решение (из T) хуже предыдущего, возвращаем предыдущее if (a [i].f < prevFitness [i]) { ArrayCopy (a [i].c, a [i].cP, 0, 0, WHOLE_ARRAY); a [i].f = prevFitness [i]; } } needSelection = false; } //--- Основные шаги BSA: // Сохраняем текущие fitness перед генерацией новой популяции for (int i = 0; i < popSize; i++) { prevFitness [i] = a [i].f; ArrayCopy (a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY); } // 1. Selection-I SelectionI (); // 2. Mutation Mutation (); // 3. Crossover Crossover (); // 4. Копируем пробную популяцию T в основную популяцию a для вычисления fitness for (int i = 0; i < popSize; i++) { ArrayCopy (a [i].c, T [i].c, 0, 0, WHOLE_ARRAY); } // Устанавливаем флаг для выполнения Selection-II после вычисления fitness needSelection = true; } //————————————————————————————————————————————————————————————————————
El método "SelectionI" implementa la primera etapa de selección en el algoritmo BSA y se encarga de elegir la población histórica que posteriormente se utiliza para la mutación.
Actualización probabilística de la población histórica: con una probabilidad del 50% (o, más simplemente, con igual probabilidad), la población histórica "oldP" se actualiza con la población actual "a". Si se genera un número aleatorio menor que un umbral determinado (0,5), entonces el contenido ("c", coordenadas) de cada agente de la población actual "a" se copia al agente correspondiente en la población histórica "oldP", y la aptitud "f" del agente también se copia.
Mezcla de la población histórica: independientemente de si la población histórica se ha actualizado en el paso anterior o no, llamamos al método "ShufflePopulation(oldP)" para mezclar los agentes en la población histórica. Esto se hace para introducir aleatoriedad en el proceso de mutación. El proceso de reordenamiento garantiza que los agentes de la población histórica se seleccionen en un orden aleatorio, en lugar de en el orden en que se han ubicado originalmente.
De este modo, "SelectionI" actualiza la población histórica con las soluciones candidatas actuales o mantiene su estado anterior, y luego, en ambos casos, reorganiza los agentes en la población histórica, lo cual permite la diversificación de la búsqueda durante la mutación posterior.
//———————————————————————————————————————————————————————————————————— //--- Selection-I: выбор исторической популяции void C_AO_BSA_Backtracking::SelectionI () { // С вероятностью 50% обновляем историческую популяцию if (u.RNDprobab () < 0.5) // эквивалент if (a < b) где a,b ~ U(0,1) { // Копируем текущую популяцию в историческую for (int i = 0; i < popSize; i++) { ArrayCopy (oldP [i].c, a [i].c, 0, 0, WHOLE_ARRAY); oldP [i].f = a [i].f; } } // Перемешиваем историческую популяцию ShufflePopulation (oldP); } //————————————————————————————————————————————————————————————————————
El método "ShufflePopulation" está diseñado para mezclar aleatoriamente elementos en una población determinada de agentes (representada por la estructura "S_AO_Agent"). Este recibe como entrada un array de agentes "pop[]" y realiza una reorganización in situ, es decir, cambia el orden de los elementos directamente en el array pasado.
Algoritmo de barajado: el método utiliza el algoritmo de barajado de Fisher-Yates para barajar aleatoriamente los elementos de la población; el algoritmo garantiza que cada permutación (orden) de los elementos tenga la misma probabilidad.
El ciclo "for" comienza en el último elemento del array (popSize - 1) y va en orden inverso hasta el segundo elemento (índice 1). El primer elemento (índice 0) no necesita ser barajado, ya que para entonces ya habrá sido "movido" durante el algoritmo. Para cada elemento con índice "i", se selecciona un índice aleatorio "j" en el rango de "0" a "i" inclusive. Esto se hace usando la función "u.RNDminusOne(i+1)", que devuelve un número entero aleatorio dentro del rango especificado (incluyendo "0" y excluyendo "i+1").
Los elementos con índices "i" y "j" se intercambian. Para ello, se usa una variable temporal "temp" del tipo "S_AO_Agent". Como "S_AO_Agent" contiene el array "c" (coordenadas), esta array se copia. El valor de aptitud "f" también se copia. Las coordenadas y los valores de aptitud del elemento "pop[i]" se almacenan en la variable temporal "temp", mientras que las coordenadas y los valores de aptitud del elemento "pop[j]" se copian a "pop[i]". Los valores guardados de "temp" (el valor original de "pop[i]") se copian a "pop[j]". Como resultado, una vez completado el ciclo, el orden de los elementos en el array "pop[]" será aleatorio.
//———————————————————————————————————————————————————————————————————— //--- Перемешивание популяции void C_AO_BSA_Backtracking::ShufflePopulation (S_AO_Agent &pop []) { for (int i = popSize - 1; i > 0; i--) { int j = u.RNDminusOne (i + 1); // Обмен местами элементов i и j S_AO_Agent temp; temp.Init (coords); ArrayCopy (temp.c, pop [i].c, 0, 0, WHOLE_ARRAY); temp.f = pop [i].f; ArrayCopy (pop [i].c, pop [j].c, 0, 0, WHOLE_ARRAY); pop [i].f = pop [j].f; ArrayCopy (pop [j].c, temp.c, 0, 0, WHOLE_ARRAY); pop [j].f = temp.f; } } //————————————————————————————————————————————————————————————————————
El método "Mutation" es el responsable de generar la población mutante, lo cual es un paso clave en el algoritmo BSA. Se basa en la diferencia entre la población actual y la población histórica.
En primer lugar, se genera un factor de amplitud aleatorio "F", que determina la magnitud del impacto de la población histórica sobre la actual. Luego, para cada agente de la población y para cada coordenada dentro de ese agente, se calcula un nuevo valor para la coordenada en la población mutante. Esto se logra sumando a la coordenada actual el producto del factor de amplitud "F" y la diferencia entre la coordenada correspondiente en la población histórica y la coordenada actual. De este modo, se crea una población mutante desplazando la población actual en la dirección determinada por la población histórica, con una amplitud que depende del factor "F".
//———————————————————————————————————————————————————————————————————— //--- Mutation: генерация мутантной популяции void C_AO_BSA_Backtracking::Mutation () { // Генерируем фактор амплитуды F = u.GaussDistribution (0.0, -3.0, 3.0, 2); // Применяем мутацию: M = P + F * (oldP - P) for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { M [i].c [j] = a [i].c [j] + F * (oldP [i].c [j] - a [i].c [j]); } } } //————————————————————————————————————————————————————————————————————
El método de "cruce" consiste en formar una población de prueba basada en la población mutante actual usando la estrategia de cruce seleccionada. Este proceso tiene como objetivo combinar las características de las soluciones heredadas para encontrar opciones más óptimas.
Inicialmente, se copia una población de prueba a partir de la población mutante para ofrecer una base para modificaciones posteriores. A continuación, se debe seleccionar una estrategia de cruce: con una probabilidad del 40% se utiliza la primera estrategia, y en caso contrario, la segunda.
Si elegimos la primera opción, se implementa una estrategia denominada "mixrate". En este caso, para cada agente, se determina el número de elementos (dentro de las coordenadas) que se tomarán del agente actual, considerando el coeficiente de "mixrate" especificado. Estos elementos se seleccionan al azar, sin repetición. Después de esto, las coordenadas correspondientes de la solución actual se copian desde los índices seleccionados al agente de la población de prueba.
Si elegimos la segunda estrategia, entonces para cada agente se selecciona un elemento aleatorio (coordenada), y en la población de prueba en la posición correspondiente este elemento se reemplaza por su valor de la solución actual.
Una vez completado el cruce, se realiza una comprobación de los límites para cada agente en la población de prueba para garantizar que todas las decisiones sean válidas y cumplan con los requisitos de rango.
//———————————————————————————————————————————————————————————————————— //--- Crossover: генерация пробной популяции void C_AO_BSA_Backtracking::Crossover () { // Инициализируем пробную популяцию как копию мутантной for (int i = 0; i < popSize; i++) { ArrayCopy (T [i].c, M [i].c, 0, 0, WHOLE_ARRAY); } // Выбираем стратегию кроссовера if (u.RNDprobab () < 0.4) { //--- СТРАТЕГИЯ 1: Использование mixrate for (int i = 0; i < popSize; i++) { // Сброс карты ArrayInitialize (map [i].val, 0); // Определяем количество элементов для кроссовера int numElements = (int)MathCeil (mixrate * u.RNDprobab () * coords); // Генерируем уникальные индексы для кроссовера for (int n = 0; n < numElements; n++) { int idx; do { idx = u.RNDminusOne (coords); } while (map [i].val [idx] == 1); // пока не найдем неиспользованный индекс map [i].val [idx] = 1; } // Применяем кроссовер for (int j = 0; j < coords; j++) { if (map [i].val [j] == 1) { T [i].c [j] = a [i].c [j]; } } } } else { //--- СТРАТЕГИЯ 2: Мутация только одного элемента for (int i = 0; i < popSize; i++) { // Выбираем один случайный элемент int randomIndex = u.RNDminusOne (coords); T [i].c [randomIndex] = a [i].c [randomIndex]; } } // Контроль границ для всех агентов пробной популяции for (int i = 0; i < popSize; i++) { BoundaryControl (T [i]); } } //————————————————————————————————————————————————————————————————————
El método "BoundaryControl" está diseñado para comprobar y ajustar los valores de decisión del agente para garantizar que se mantengan dentro de los límites aceptables, así como para convertir las decisiones al formato discreto deseado.
Para cada elemento de las coordenadas del agente, se realiza una comprobación: si el valor supera los límites mínimos o máximos establecidos, entonces este resultado se procesa según la estrategia seleccionada. Si la probabilidad seleccionada aleatoriamente es inferior al 50%, se produce una regeneración aleatoria de un valor dentro del rango aceptable. En caso contrario, el valor se establece en el límite más cercano, ya sea el mínimo o el máximo.
Tras ello, cada valor de coordenada se discretiza, es decir, se convierte en el valor aceptable más cercano que corresponda al rango y al paso de discretización especificados. Esto garantiza que la solución cumpla con los requisitos de tipo y rango de datos.
//———————————————————————————————————————————————————————————————————— //--- Контроль границ void C_AO_BSA_Backtracking::BoundaryControl (S_AO_Agent &agent) { for (int j = 0; j < coords; j++) { if (agent.c [j] < rangeMin [j] || agent.c [j] > rangeMax [j]) { // Выбор стратегии обработки границ if (u.RNDprobab () < 0.5) { // Случайная регенерация agent.c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]); } else { // Установка на границу if (agent.c [j] < rangeMin [j]) agent.c [j] = rangeMin [j]; else agent.c [j] = rangeMax [j]; } } // Дискретизация agent.c [j] = u.SeInDiSp (agent.c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } //————————————————————————————————————————————————————————————————————
El método de "Revision" se encarga de seleccionar y actualizar la mejor solución encontrada en la población actual. Una vez analizadas todas las soluciones, busca aquella con el valor máximo de la función de evaluación (aptitud). Si se encuentra dicha solución, se almacena como el mejor resultado actual y sus coordenadas se copian en un array aparte diseñado para almacenar la mejor solución en ese momento. Este método permite, por lo tanto, el seguimiento y la actualización continuos de la solución óptima encontrada durante las iteraciones del algoritmo.
//———————————————————————————————————————————————————————————————————— //--- Selection-II и обновление лучшего решения void C_AO_BSA_Backtracking::Revision () { int bestIND = -1; for (int i = 0; i < popSize; i++) { // Обновляем глобальное лучшее решение if (a [i].f > fB) { fB = a [i].f; bestIND = i; } } // Копируем координаты лучшего решения if (bestIND != -1) { ArrayCopy (cB, a [bestIND].c, 0, 0, WHOLE_ARRAY); } } //————————————————————————————————————————————————————————————————————
El método "GaussDistribution" genera un número aleatorio con una distribución gaussiana (normal) centrada en torno a un valor de entrada dado y delimitada por un cierto rango, usando el método de Box-Muller para producir variables aleatorias con distribución normal.
En primer lugar, genera dos variables aleatorias con distribución uniforme. Luego, basándose en estos valores, se calcula una variable aleatoria con distribución normal estándar, que puede usarse para obtener una distribución gaussiana.
A continuación, el método comprueba si el valor generado se encuentra dentro del rango de desviación especificado y definido por el parámetro sigma. Si el valor generado se encuentra fuera de estos límites, se vuelve a llamar al método de forma recursiva para generar un nuevo valor hasta que se encuentre dentro del rango permitido.
Finalmente, la varianza generada con distribución normal se escala para ajustarse al rango de salida dado (desde "outMin" hasta "outMax") en relación con el valor de entrada "In". Esto permite modificar y escalar la distribución para que se ajuste a los parámetros deseados. El resultado es un número con distribución gaussiana centrado en "In", pero sujeto a restricciones en el valor mínimo y máximo de salida.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_Utilities :: GaussDistribution (const double In, const double outMin, const double outMax, const double sigma) { double logN = 0.0; double u1 = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0); double u2 = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0); logN = u1 <= 0.0 ? 0.000000000000001 : u1; double z0 = sqrt (-2 * log (logN)) * cos (2 * M_PI * u2); double sigmaN = sigma > 8.583864105157389 ? 8.583864105157389 : sigma; // Если z0 выходит за пределы [-sigmaN, sigmaN], генерируем заново if (z0 >= sigmaN || z0 <= -sigmaN) { return GaussDistribution(In, outMin, outMax, sigma); // Рекурсивный вызов } if (z0 >= 0.0) z0 = Scale (z0, 0.0, sigmaN, 0.0, outMax - In, false); else z0 = -Scale (fabs (z0), 0.0, sigmaN, 0.0, In - outMin, false); return In + z0; } //——————————————————————————————————————————————————————————————————————————————
Resultados de las pruebas
Los resultados del algoritmo BSA son muy buenos.
=============================
5 Hilly's; Func runs: 10000; result: 0,9730917210619289
25 Hilly's; Func runs: 10000; result: 0,5453406317593932
500 Hilly's; Func runs: 10000; result: 0,2909827609772065
=============================
5 Forest's; Func runs: 10000; result: 0,9999986842258451
25 Forest's; Func runs: 10000; result: 0,5854340780208712
500 Forest's; Func runs: 10000; result: 0,21747482800959225
=============================
5 Megacity's; Func runs: 10000; result: 0,8476923076923077
25 Megacity's; Func runs: 10000; result: 0,3695384615384615
500 Megacity's; Func runs: 10000; result: 0,12978461538461658
=============================
All score: 4.95934 (55.10%)
En la visualización del algoritmo BSA, podemos observar la dispersión de valores en los resultados para funciones de dimensionalidades pequeñas y medianas; sin embargo, con un aumento en los parámetros del tamaño de la población, la dispersión disminuye, pero para una mejor convergencia, es necesario aumentar el número de iteraciones.
BSA en la función de prueba Hilly
BSA en la función de prueba Forest
BSA en la función de prueba Megacity
El algoritmo BSA ocupa el puesto número 20 en la tabla de clasificación de algoritmos de optimización basados en poblaciones.
| № | 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 | 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 |
| 2 | 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 |
| 3 | 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 |
| 4 | (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 |
| 5 | 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 |
| 6 | 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 |
| 7 | 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 |
| 8 | 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 |
| 9 | 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 |
| 10 | 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 |
| 11 | 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 |
| 12 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | AOSm | búsqueda de orbitales atómicos 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | (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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | SOA | simple optimization algorithm | 0,91520 | 0,46976 | 0,27089 | 1,65585 | 0,89675 | 0,37401 | 0,16984 | 1,44060 | 0,69538 | 0,28031 | 0,10852 | 1,08422 | 4.181 | 46,45 |
| 43 | ABHA | artificial bee hive algorithm | 0,84131 | 0,54227 | 0,26304 | 1,64663 | 0,87858 | 0,47779 | 0,17181 | 1,52818 | 0,50923 | 0,33877 | 0,10397 | 0,95197 | 4.127 | 45,85 |
| 44 | ACMO | atmospheric cloud model optimization | 0,90321 | 0,48546 | 0,30403 | 1,69270 | 0,80268 | 0,37857 | 0,19178 | 1,37303 | 0,62308 | 0,24400 | 0,10795 | 0,97503 | 4,041 | 44,90 |
| 45 | ADAMm | adaptive moment estimation M | 0,88635 | 0,44766 | 0,26613 | 1.60014 | 0,84497 | 0,38493 | 0,16889 | 1,39880 | 0,66154 | 0,27046 | 0,10594 | 1,03794 | 4.037 | 44.85 |
| 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
El BSA representa un compromiso entre la facilidad de implementación y la eficiencia de búsqueda, ocupando una posición estable en la parte media de la tabla de clasificación de algoritmos de optimización basados en poblaciones. Su principal ventaja reside en el interesante concepto de memoria histórica, que permite al algoritmo evitar la convergencia prematura sin complicar el esquema computacional. A diferencia de muchas metaheurísticas modernas, que están sobrecargadas de parámetros y operadores complejos, el BSA solo requiere un conjunto mínimo de configuraciones, lo que lo convierte en una opción atractiva para los profesionales que no desean dedicar tiempo a ajustar parámetros externos.
El único parámetro significativo, "mixrate", es intuitivo y no requiere una comprensión profunda de la mecánica interna del algoritmo. Al mismo tiempo, el BSA demuestra un rendimiento estable en una amplia gama de problemas, desde funciones unimodales simples hasta complejos escenarios multiextremos con múltiples óptimos locales. El algoritmo no pretende ser un campeón en términos de velocidad de convergencia o precisión de la solución, pero su fiabilidad y previsibilidad lo convierten en una herramienta práctica y fiable. Especialmente valioso resulta que, a medida que crece la población, el BSA es poco susceptible al estancamiento: el mecanismo de renovación aleatoria de la población histórica garantiza una afluencia constante de diversidad incluso en las últimas etapas de la búsqueda.
Su posición en la mitad de la clasificación no es un signo de mediocridad, sino más bien una prueba de su versatilidad y practicidad, ya que resolver problemas del mundo real no siempre requiere la herramienta más compleja y moderna. En ocasiones, basta con un algoritmo robusto con una lógica de funcionamiento clara que produzca buenos resultados sin necesidad de ajustes por parte de expertos, y el BSA cumple con éxito esta función.
Figura 2. Clasificación por colores de los algoritmos según las pruebas respectivas
Figura 3. Histograma de los resultados de las pruebas de algoritmos (en una escala de 0 a 100, cuanto más mejor, donde 100 es el máximo resultado teórico posible, el script para calcular la tabla de puntuación está en el archivo)
Ventajas y desventajas del algoritmo BSA:
Ventajas:
- Buena convergencia en las funciones.
- Además del tamaño de la población, solo existe un parámetro externo adicional.
Desventajas:
- Existe cierta tendencia a quedarse estancado en problemas de baja dimensionalidad con poblaciones pequeñas.
Adjuntamos al artículo un archivo con las versiones actuales de los códigos de los algoritmos. El autor de este artículo no se responsabiliza de la exactitud absoluta de la descripción de los algoritmos canónicos, muchos de ellos han sido modificados para mejorar las capacidades de búsqueda. Las conclusiones y juicios presentados en los artículos se basan en los resultados de los experimentos realizados.
Programas usados en el artículo
| # | Nombre | Tipo | Descripción |
|---|---|---|---|
| 1 | #C_AO.mqh | Archivo de inclusión | Clase padre de algoritmos de optimización basados en la población |
| 2 | #C_AO_enum.mqh | Archivo de inclusión | Enumeración de los algoritmos de optimización basados en la población |
| 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 en una tabla comparativa |
| 7 | Testing AOs.mq5 | Script | Banco de pruebas único para todos los algoritmos de optimización basados en la población |
| 8 | Simple use of population optimization algorithms.mq5 | Script | Ejemplo sencillo de utilización de algoritmos de optimización basados en la población sin visualización |
| 9 | Test_AO_BSA.mq5 | Script | Banco de pruebas para BSA |
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/18568
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.
Utilizando redes neuronales en MetaTrader
Guía de aprendizaje automático para MetaTrader 5 (Parte 1): Correcciones relacionadas con la fuga de datos y las marcas de tiempo
Particularidades del trabajo con números del tipo double en MQL4
Redes neuronales en el trading: Segmentación periódica adaptativa (LightGTS)
- Aplicaciones de trading gratuitas
- 8 000+ señales para copiar
- Noticias económicas para analizar los mercados financieros
Usted acepta la política del sitio web y las condiciones de uso