Optimización basada en biogeografía — Biogeography-Based Optimization (BBO)
25
0
Contenido
Introducción
Mientras revisaba algunos algoritmos de optimización, me interesé en el algoritmo de Optimización Biogeográfica (BBO), desarrollado por el profesor Dan Simon en 2008. El BBO se inspira en la biogeografía, la ciencia de la distribución geográfica de los organismos biológicos. Los modelos matemáticos que describen la distribución de las especies se desarrollaron por primera vez en la década de 1960. Así como los algoritmos genéticos se inspiraron en la genética biológica y las redes neuronales en las neuronas biológicas, BBO usa los principios matemáticos de la biogeografía para resolver problemas de optimización.
En la naturaleza, las islas de un archipiélago con condiciones favorables (alto Índice de Adecuación del Hábitat - HSI) tienen una gran cantidad de especies y una alta emigración, mientras que las islas con malas condiciones tienen pocas especies y una alta inmigración. Precisamente esta dinámica natural de migración de especies entre islas formó la base del mecanismo de optimización BBO. El algoritmo usa el concepto de migración de especies para intercambiar características entre soluciones; la probabilidad de mutación se basa en un modelo de distribución de especies teóricamente sólido y las buenas soluciones comparten activamente sus características pero siguen siendo resistentes al cambio. Este punto destacado es la característica principal del algoritmo.
En este artículo, analizaremos un concepto de algoritmo elegante que supone un método simple y efectivo para resolver problemas de optimización, lo implementaremos en código y examinaremos y evaluaremos los resultados del algoritmo BBO.
Implementación del algoritmo
Imagínese archipiélagos de islas, donde cada isla alberga distintas especies de animales.
1. Hábitat = Isla = Solución de un problema. Cada isla en nuestro algoritmo representa una posible solución. Si tenemos 50 islas, entonces tenemos 50 soluciones diferentes.
2. HSI (Índice de idoneidad del hábitat) = Idoneidad de la isla para vivir = Calidad de la solución. Isla rica con agua dulce, frutas y buen clima = Buena solución (HSI alto). Isla desierta sin agua = Mala solución (HSI bajo)
3. Especies = Características de la solución. La rica isla es el hogar de muchas especies de animales. La isla pobre tiene pocas especies porque no es diversa.
¿Cómo funciona la migración? Ejemplo de la vida: Hawaii (isla rica), muchas especies → los animales a menudo nadan o vuelan hacia otras islas (alta emigración), pero pocos llegan a ella (baja inmigración, la isla ya está superpoblada). Isla deshabitada: pocas especies → los animales rara vez se van (baja emigración), pero a menudo llegan nuevos (alta inmigración, mucho espacio libre).
En el algoritmo: Mala solución (pocas especies) → Alta inmigración → adquiere características de buenas soluciones. Buena solución (muchas especies) → Alta emigración → comparte características con otros.
Otro ejemplo de la vida: digamos que estamos buscando la mejor ubicación para una tienda en la ciudad. Cada "isla" es una variante de ubicación. Así, creamos 50 ubicaciones aleatorias (islas), de las cuales:
Isla 1: mal Lugar - afueras
Isla 2: excelente ubicación - centro
Isla 50: lugar promedio bueno
Calificamos cada ubicación (HSI): Isla 2 (centro): HSI = 95 (muchos compradores, buena accesibilidad), Isla 1 (afueras): HSI = 20 (pocos compradores), entonces la Isla 1 (mala) tiene alta inmigración y “adopta” algunas características de la Isla 2 (buena). Por ejemplo, si la Isla 2 está ubicada "cerca del metro", entonces la Isla 1 también intentará encontrar un lugar cerca del metro. A veces pueden ocurrir "desastres" (terremotos, tsunamis) cuando la solución cambia por accidente: la tienda "salta" a una ubicación completamente nueva y dicho movimiento ayuda a encontrar soluciones inesperadamente buenas.
¿Por qué las soluciones promedio mutan con menos frecuencia? En la naturaleza, las islas muy ricas (como por ejemplo las Galápagos) son raras e inestables, mientras que las islas muy pobres también son raras e inestables, y las islas promedio son las más comunes y estables. En el algoritmo esto implica:
Soluciones muy buenas (HSI = 95): alta probabilidad de mutación
Soluciones muy malas (HSI = 5): alta probabilidad de mutación
Soluciones promedio (HSI = 50): baja probabilidad de mutación
Las 2 primeras mejores islas (soluciones) están protegidas contra los cambios: estas son nuestras "reservas". ¡No queremos perder las mejores soluciones encontradas! Luego, el proceso de optimización final será: creamos 50 soluciones aleatorias (islas), las clasificamos por calidad (de mejor a peor), luego las malas soluciones aprenden de las buenas y algunas soluciones se modifican aleatoriamente. De esta forma, BBO simula el proceso natural de distribución de especies entre islas para encontrar una solución óptima. A continuación mostramos una ilustración de cómo funciona el algoritmo.
Figura 1. Ilustración del algoritmo BBO en funcionamiento
El esquema de la figura 1 muestra visualmente:
- Tres tipos de islas (rica, media, pobre) con diferente número de especies
- El proceso de migración: las flechas muestran cómo se desplazan las especies entre islas.
- El proceso de optimización paso a paso: desde la inicialización hasta la iteración
- Los conceptos clave: leyenda y principios básicos del algoritmo
La ilustración demuestra claramente cómo las islas ricas (buenas soluciones) tienen una alta emigración, las islas pobres (malas soluciones) tienen una alta inmigración; hay un intercambio de características entre soluciones y funciona todo el ciclo de optimización. Tras realizar un análisis detallado del algoritmo, podemos escribir el pseudocódigo.
1. INICIALIZACIÓN:
- Establecemos los parámetros:
* tamaño de la población (número de hábitats) = 50
* tasa máxima de inmigración I = 1,0
* tasa máxima de emigración E = 1,0
* probabilidad de mutación = 0,01
* número de soluciones de élite = 2
* número máximo de especies = 50
* número de iteraciones
- Creamos una población de N hábitats aleatorios (soluciones)
- Calculamos el HSI (idoneidad) para cada hábitat
- Calculamos las probabilidades de existencia para diferentes números de especies.
2. CICLO PRINCIPAL (repetimos un número específico de iteraciones):
2.1. EVALUACIÓN Y CLASIFICACIÓN:
- Calculamos el HSI para cada hábitat
- Clasificamos los hábitats por HSI descendente
- Guardamos la mejor solución
2.2. CÁLCULO DE PARÁMETROS DE MIGRACIÓN:
Para cada hábitat i:
- Determinamos el número de especies: Si = Smax × (N - rang_i) / N
- Calculamos la tasa de inmigración: λi = I × (1 - Si/Smax)
- Calculamos la tasa de emigración: μi = E × (Si/Smax)
- Determinamos la probabilidad de existencia en función de Si
2.3. MIGRACIÓN (intercambio de características):
Para cada hábitat Hi (excepto élite):
SI número_aleatorio < λi (tasa de inmigración) ENTONCES:
Para cada variable de decisión (SIV) j:
SI número_aleatorio < λi ENTONCES:
- Seleccionamos un hábitat donante:
* calculamos la suma de todas las tasas de emigración (excepto Hi)
* utilizamos la selección de ruleta basada en μ
* seleccionamos el hábitat Hk con probabilidad μk/Σμ
- Copiamos la variable j-ésima de Hk a Hi
FINAL SI
FIN del ciclo de variables
FINAL SI
Se da el FINAL del ciclo sobre hábitats
2.4. MUTACIÓN (investigación de nuevas soluciones):
Para cada hábitat Hi (excepto élite):
- Calculamos la tasa de mutación: m_rate = m × (1 - probabilidad_de_existencia_i)
SI número_aleatorio < tasa_m ENTONCES:
- Seleccionamos una variable aleatoria j
- La remplazamos con un valor aleatorio del rango aceptable
FINAL SI
FIN del ciclo sobre hábitats
2.5. REEMPLAZO Y ACTUALIZACIÓN:
- Calculamos nuevos valores de HSI
- Actualizamos la mejor solución encontrada
- Guardamos los valores de aptitud actuales para la siguiente iteración
3. DEVOLUCIÓN de la mejor solución encontrada
Ahora queda muy poco por hacer. Vamos a escribir la clase "C_AO_BBO", que será sucesora de la clase "C_AO" y estará diseñada para implementar el algoritmo BBO. La herencia implica que "C_AO_BBO" usa la funcionalidad de optimización base proporcionada por la clase básica.
La clase contiene el conjunto de parámetros, el tamaño de población y los valores específicos de BBO, como: tasa máxima de inmigración/emigración (immigrationMax, emigrationMax), probabilidad de mutación (mutationProb), número de soluciones de élite que se mantienen sin cambios (elitismCount) y número máximo de especies (speciesMax). El constructor de clase inicializa los parámetros BBO con los valores por defecto, asigna un nombre, una descripción y un enlace a un artículo sobre el algoritmo. El método "SetParams()" permite cambiar los valores de los parámetros utilizando datos del array "params".
Métodos principales:- Init() — inicializa el algoritmo, incluida la creación e inicialización de la población, la especificación de los rangos de valores, el paso y el número de épocas y la inicialización de los arrays para almacenar los datos del hábitat.
- Moving() — implementa la lógica básica de desplazamiento (migración) de las soluciones entre hábitats de acuerdo con los principios BBO.
- Revision() — incluye la lógica para revisar y ajustar soluciones (hábitats).
- S_HabitatData — estructura interna que contiene información sobre cada hábitat (solución), incluido el número de especies (speciesCount), la tasa de inmigración/emigración (immigration, emigration) y la probabilidad de existencia (probability).
- habitatData — array de estructuras "S_HabitatData" que almacena datos para cada hábitat de la población.
- probabilities — conjunto de probabilidades utilizadas para la mutación.
Los métodos privados contienen la implementación de los pasos principales del algoritmo BBO, como la inicialización de la población, el cálculo de la tasa de migración y la mutación.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_BBO : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_BBO () { } C_AO_BBO () { ao_name = "BBO"; ao_desc = "Biogeography-Based Optimization"; ao_link = "https://www.mql5.com/ru/articles/18354"; popSize = 50; // размер популяции (количество хабитатов) immigrationMax = 1.0; // максимальная скорость иммиграции emigrationMax = 1.0; // максимальная скорость эмиграции mutationProb = 0.5; // вероятность мутации elitismCount = 2; // количество элитных решений speciesMax = 50; // максимальное количество видов ArrayResize (params, 6); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "immigrationMax"; params [1].val = immigrationMax; params [2].name = "emigrationMax"; params [2].val = emigrationMax; params [3].name = "mutationProb"; params [3].val = mutationProb; params [4].name = "elitismCount"; params [4].val = elitismCount; params [5].name = "speciesMax"; params [5].val = speciesMax; } void SetParams () { popSize = (int)params [0].val; immigrationMax = params [1].val; emigrationMax = params [2].val; mutationProb = params [3].val; elitismCount = (int)params [4].val; speciesMax = (int)params [5].val; } bool Init (const double &rangeMinP [], // минимальные значения const double &rangeMaxP [], // максимальные значения const double &rangeStepP [], // шаг изменения const int epochsP = 0); // количество эпох void Moving (); void Revision (); //---------------------------------------------------------------------------- double immigrationMax; // максимальная скорость иммиграции double emigrationMax; // максимальная скорость эмиграции double mutationProb; // вероятность мутации int elitismCount; // количество элитных решений int speciesMax; // максимальное количество видов private: //------------------------------------------------------------------- struct S_HabitatData { int speciesCount; // количество видов в хабитате double immigration; // скорость иммиграции double emigration; // скорость эмиграции double probability; // вероятность существования }; S_HabitatData habitatData []; // данные для каждого хабитата double probabilities []; // вероятности для подсчета мутаций // Вспомогательные методы void InitializePopulation (); void CalculateRates (); void Migration (); void Mutation (); double CalculateProbability (int speciesCount); }; //——————————————————————————————————————————————————————————————————————————————
El método "Init" configura el algoritmo BBO antes de que comience a funcionar. Realiza la inicialización básica (comprobaciones y configuraciones), asigna memoria para almacenar datos sobre "hábitats" y probabilidades de migración. Luego calcula y normaliza las probabilidades de migración según el número de especies en cada hábitat. Retorna "true" en caso de éxito.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_BBO::Init (const double &rangeMinP [], // минимальные значения const double &rangeMaxP [], // максимальные значения const double &rangeStepP [], // шаг изменения const int epochsP = 0) // количество эпох { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Инициализация массивов для каждого хабитата ArrayResize (habitatData, popSize); ArrayResize (probabilities, speciesMax + 1); // Расчет вероятностей для различного количества видов double sum = 0.0; for (int i = 0; i <= speciesMax; i++) { probabilities [i] = CalculateProbability (i); sum += probabilities [i]; } // Нормализация вероятностей if (sum > 0) { for (int i = 0; i <= speciesMax; i++) { probabilities [i] /= sum; } } return true; } //——————————————————————————————————————————————————————————————————————————————
El método "Moving" implementa el ciclo de optimización principal del algoritmo BBO. La primera vez que se llama al método, se comprueba el indicador "revision". Si se establece en un valor que indica que la población aún no se ha creado, se inicializará, y esto implica generar soluciones aleatorias, evaluar su idoneidad y establecer parámetros iniciales. Después de esto, la bandera se reinicia.
Una vez completada la inicialización, se realizan una serie de pasos característicos de un ciclo algorítmico: se clasifica la población de soluciones según su valor de idoneidad para identificar los mejores y peores agentes. Esto ayuda a gestionar las migraciones y mutaciones. En esta etapa se calculan las probabilidades y velocidades de intercambio de especies entre hábitats según su estado actual y la calidad de sus soluciones. Estos parámetros controlan cómo las especies “migran” de un hábitat a otro. En este paso se produce el intercambio de “SIV” entre hábitats.
Como resultado, los hábitats con poca diversidad reciben nuevas especies de opciones más ricas, lo cual facilita la exploración del espacio de soluciones. Después de la migración, se producen cambios aleatorios en las soluciones (mutación) para mantener la diversidad genética. Las probabilidades de mutación pueden depender del estado actual de la solución y de los parámetros del algoritmo. Al final del ciclo, se guardan los valores actuales de la función de idoneidad de la solución para que puedan usarse para la clasificación y el análisis en la siguiente iteración del algoritmo.
//+----------------------------------------------------------------------------+ //| Основной метод оптимизации | //+----------------------------------------------------------------------------+ void C_AO_BBO::Moving () { // Первая итерация - инициализация начальной популяции if (!revision) { InitializePopulation (); revision = true; return; } // Основной процесс оптимизации // 1. Сортировка популяции по HSI (fitness) static S_AO_Agent aTemp []; ArrayResize (aTemp, popSize); u.Sorting (a, aTemp, popSize); // 2. Расчет скоростей иммиграции и эмиграции CalculateRates (); // 3. Миграция (обмен SIV между хабитатами) Migration (); // 4. Мутация на основе вероятностей Mutation (); // 5. Сохранение состояния для следующей итерации for (int i = 0; i < popSize; i++) { a [i].fP = a [i].f; } } //——————————————————————————————————————————————————————————————————————————————
El método "Revision" está diseñado para actualizar la mejor solución actual en la población. Itera por todos los agentes (soluciones) de la población actual y compara su valor de función de aptitud con el almacenado en la variable "fB", que guarda el mejor resultado en el momento.
Si algún agente tiene un valor de función de aptitud mejor que el mejor actual, lo reemplaza y los parámetros de solución correspondientes se copian en la variable que guarda la mejor solución. Como resultado, tras ejecutar el método, la variable siempre contiene la mejor solución encontrada.
//+----------------------------------------------------------------------------+ //| Обновление лучшего решения | //+----------------------------------------------------------------------------+ void C_AO_BBO::Revision () { // Поиск лучшего решения в текущей популяции for (int i = 0; i < popSize; i++) { // Обновление лучшего решения if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY); } } } //——————————————————————————————————————————————————————————————————————————————
El método "InitializePopulation" es responsable de crear la población inicial de soluciones para el algoritmo BBO. Crea un "popSize" (tamaño de la población) de individuos (hábitats) distribuidos uniformemente por todo el espacio de búsqueda.
Para cada individuo, el método genera coordenadas aleatorias (valores de los parámetros de la solución) dentro de los límites especificados por las arrays "rangeMin" (límites mínimos) y "rangeMax" (límites máximos) para cada coordenada "coords". La función "u.RNDfromCI" se usa para generar un número aleatorio en un rango determinado.
A continuación, el método redondea las coordenadas generadas al paso válido más cercano definido por el array "rangeStep". Esto garantiza que las soluciones estén en un espacio de búsqueda discreto factible. Para ello se usa la función "SeInDiSp". Tras inicializar las coordenadas, el método inicializa la estructura de datos "habitatData" para cada individuo, estableciendo los valores "speciesCount", "immigration", "emigration" y "probability" en cero. Estos valores se usarán en el proceso de optimización para calcular las tasas de inmigración, emigración y probabilidades de mutación.
//+----------------------------------------------------------------------------+ //| Инициализация начальной популяции | //+----------------------------------------------------------------------------+ void C_AO_BBO::InitializePopulation () { // Инициализация начальной популяции равномерно по всему пространству for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { // Генерация случайных координат в допустимых пределах a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); // Округление до ближайшего допустимого шага a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } // Инициализация данных хабитата habitatData [i].speciesCount = 0; habitatData [i].immigration = 0.0; habitatData [i].emigration = 0.0; habitatData [i].probability = 0.0; } } //——————————————————————————————————————————————————————————————————————————————
El método CalculateRates está diseñado para calcular las tasas de migración (inmigración y emigración) y la probabilidad de existencia de cada hábitat en la población.
Para ello, se utiliza un modelo lineal en el que el número de especies asociadas a cada solución es proporcional a su rango, siendo las mejores soluciones las que tienen más especies. La tasa de inmigración disminuye a medida que aumenta el número de especies: cuantas más especies tenga una solución, menor será su probabilidad de aceptar nuevos individuos. La tasa de emigración aumenta con el número de especies: cuantas más especies tenga una solución, mayor será la probabilidad de abandonarla.
La probabilidad de existencia de hábitat se establece según las probabilidades predeterminadas para cada número de especies. Si el número de especies excede el máximo permitido, la probabilidad se establece en cero.
//+----------------------------------------------------------------------------+ //| Расчет скоростей иммиграции и эмиграции | //+----------------------------------------------------------------------------+ void C_AO_BBO::CalculateRates () { // Для линейной модели миграции for (int i = 0; i < popSize; i++) { // Количество видов обратно пропорционально рангу (лучшие решения имеют больше видов) habitatData [i].speciesCount = speciesMax - (i * speciesMax / popSize); // Скорость иммиграции уменьшается с увеличением количества видов habitatData [i].immigration = immigrationMax * (1.0 - (double)habitatData [i].speciesCount / speciesMax); // Скорость эмиграции увеличивается с увеличением количества видов habitatData [i].emigration = emigrationMax * (double)habitatData [i].speciesCount / speciesMax; // Вероятность существования хабитата if (habitatData [i].speciesCount <= speciesMax) { habitatData [i].probability = probabilities [habitatData [i].speciesCount]; } else { habitatData [i].probability = 0.0; } } } //——————————————————————————————————————————————————————————————————————————————
El método "Migration" implementa el proceso de migración (intercambio de variables del índice de idoneidad del hábitat (SIV, es decir, valores de coordenadas) entre hábitats de una población. La idea detrás del método es que los hábitats con altas tasas de inmigración (aquellos con pocas especies) pueden "aceptar" SIV de otros hábitats con altas tasas de emigración (aquellos con muchas especies).
El ciclo itera a través de todos los hábitats de la población, pero omite los primeros hábitats "elitismCount", que se consideran "élite" y no están sujetos a migración. Para cada hábitat (excepto los de élite), se determina aleatoriamente si se modificará en la iteración actual. La probabilidad de modificación viene determinada por el valor de "habitatData[i].immigration" (la tasa de inmigración del hábitat actual). Si se selecciona un hábitat para la migración, comenzará una iteración de todas sus coordenadas (SIV). Para cada coordenada, se determina nuevamente de forma aleatoria si será modificada. La probabilidad de modificación también está determinada por el valor "habitatData[i].immigration".
Si se selecciona una coordenada para modificarla, se determina el hábitat del que se "tomará prestado" el valor de esta coordenada. Esta selección se basa en una selección de ruleta proporcional a los valores "habitatData[j].emigration" (tasas de emigración de otros hábitats). Es decir, los hábitats con mayores tasas de emigración tienen mayores posibilidades de convertirse en fuente de migración. Al calcular las probabilidades se considera que el hábitat actual no se elige como fuente por sí mismo. Si se selecciona una fuente de migración, el valor de la coordenada correspondiente (SIV) se copiará del hábitat de origen al hábitat actual.
En última instancia, el método realiza un proceso de intercambio de información regulado (SIV) entre hábitats, donde los hábitats con baja abundancia de especies (alta inmigración) obtienen información de los hábitats con alta abundancia de especies (alta emigración). Esto permite que las buenas soluciones (SIV) se distribuyan entre la población, manteniendo inalteradas las mejores soluciones.
//+----------------------------------------------------------------------------+ //| Миграция (обмен SIV между хабитатами) | //+----------------------------------------------------------------------------+ void C_AO_BBO::Migration () { for (int i = 0; i < popSize; i++) { // Пропускаем элитные решения if (i < elitismCount) continue; // Определяем, будет ли хабитат модифицирован if (u.RNDprobab () < habitatData [i].immigration) { // Для каждой координаты (SIV) for (int c = 0; c < coords; c++) { // Определяем, будет ли эта координата модифицирована if (u.RNDprobab () < habitatData [i].immigration) { // Выбор источника миграции на основе скоростей эмиграции double sumEmigration = 0.0; for (int j = 0; j < popSize; j++) { if (j != i) sumEmigration += habitatData [j].emigration; } if (sumEmigration > 0) { // Рулеточная селекция источника double roulette = u.RNDprobab () * sumEmigration; double cumSum = 0.0; for (int j = 0; j < popSize; j++) { if (j != i) { cumSum += habitatData [j].emigration; if (roulette <= cumSum) { // Копирование SIV из хабитата j в хабитат i a [i].c [c] = a [j].c [c]; break; } } } } } } } } } //——————————————————————————————————————————————————————————————————————————————
El método "Mutation" muta los hábitats de una población. El objetivo de la mutación es introducir cambios aleatorios en las soluciones para evitar que estas se estanquen en óptimos locales y explorar nuevos espacios de búsqueda.
Al igual que en el método de migración, las soluciones de élite (los primeros hábitats "elitismCount") se omiten y no se mutan. Esto es necesario para guardar las mejores soluciones encontradas. Para cada hábitat restante, se calcula la probabilidad de mutación. Es importante que la probabilidad de mutación sea inversamente proporcional a la probabilidad de existencia del hábitat (habitatData [i].probability). Esto significa que los hábitats con baja probabilidad de existencia (no las mejores soluciones) mutarán con mayor frecuencia para facilitar la exploración de nuevas áreas.
Si el número aleatorio generado es menor que la "mutationRate" calculada, entonces se producirá una mutación. Luego se selecciona aleatoriamente una coordenada "mutateCoord" (SIV) para la mutación entre todas las "coords". Y se genera un nuevo valor aleatorio dentro del rango especificado para la coordenada seleccionada. A continuación, se aplica la función "SeInDiSp" al nuevo valor, limitando el valor a los límites especificados.
De este modo, el método “Mutation” introduce un elemento de aleatoriedad en el proceso de búsqueda, permitiendo al algoritmo encontrar soluciones nuevas, potencialmente mejores, especialmente en áreas que aún no han sido suficientemente exploradas. La tasa de mutación se ajusta según la probabilidad del hábitat para equilibrar la exploración frente a la explotación.
//+----------------------------------------------------------------------------+ //| Мутация на основе вероятностей | //+----------------------------------------------------------------------------+ void C_AO_BBO::Mutation () { for (int i = 0; i < popSize; i++) { // Пропускаем элитные решения if (i < elitismCount) continue; // Скорость мутации обратно пропорциональна вероятности существования double mutationRate = mutationProb * (1.0 - habitatData [i].probability); if (u.RNDprobab () < mutationRate) { // Выбираем случайную координату для мутации int mutateCoord = MathRand () % coords; // Генерируем новое значение для выбранной координаты a [i].c [mutateCoord] = u.RNDfromCI (rangeMin [mutateCoord], rangeMax [mutateCoord]); a [i].c [mutateCoord] = u.SeInDiSp (a [i].c [mutateCoord], rangeMin [mutateCoord], rangeMax [mutateCoord], rangeStep [mutateCoord]); } } } //——————————————————————————————————————————————————————————————————————————————
El método CalculateProbability calcula la probabilidad de que exista un hábitat dado el número de especies. El método usa un modelo simplificado: la probabilidad máxima se alcanza cerca del valor de equilibrio de la especie (en la mitad del rango), y al desviarse de este, la probabilidad disminuye rápidamente a lo largo de una curva gaussiana. Cuanto más lejos esté "speciesCount" de "speciesMax/2", menor será la probabilidad.
En general, el método produce un modelo en el que los hábitats con números de especies cercanos al valor de equilibrio tienen una mayor probabilidad de existir que los hábitats con números de especies que se desvían en gran medida del valor de equilibrio. Esto supone un modelo simplificado pero efectivo de “idoneidad” del hábitat basado en su diversidad biológica.
//+----------------------------------------------------------------------------+ //| Расчет вероятности для заданного количества видов | //+----------------------------------------------------------------------------+ double C_AO_BBO::CalculateProbability (int speciesCount) { // Упрощенная модель вероятности // Максимальная вероятность в середине диапазона (равновесие) int equilibrium = speciesMax / 2; double distance = MathAbs (speciesCount - equilibrium); double probability = MathExp (-distance * distance / (2.0 * equilibrium * equilibrium)); return probability; } //——————————————————————————————————————————————————————————————————————————————
Resultados de las pruebas
Tras experimentar un poco con los parámetros, hemos descubierto excelentes resultados del algoritmo BBO.
BBO|Biogeography-Based Optimization|50.0|1.0|1.0|0.5|2.0|50.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.9491244808033844
25 Hilly's; Func runs: 10000; result: 0.6945610309062928
500 Hilly's; Func runs: 10000; result: 0.35031241665471596
=============================
5 Forest's; Func runs: 10000; result: 0.9381951766964413
25 Forest's; Func runs: 10000; result: 0.6736501622157315
500 Forest's; Func runs: 10000; result: 0,2568167323109364
=============================
5 Megacity's; Func runs: 10000; result: 0,7461538461538464
25 Megacity's; Func runs: 10000; result: 0.4827692307692309
500 Megacity's; Func runs: 10000; result: 0,17369230769230892
=============================
All score: 5.26528 (58.50%)
La visualización muestra cómo de bien funciona el algoritmo BBO. En la función discreta más difícil, Megacity, el algoritmo muestra resultados excelentes.
BBO en la función de prueba de Hilly
BBO en la función de prueba Forest
BBO en la función de prueba Megacity
Según los resultados de las pruebas, el elegante algoritmo BBO ocupa el 12.º puesto en la parte alta de la clasificació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 | 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 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | (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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | CGO | chaos game optimization | 0,57256 | 0,37158 | 0,32018 | 1,26432 | 0,61176 | 0,61931 | 0,62161 | 1,85267 | 0,37538 | 0,21923 | 0,19028 | 0,78490 | 3,902 | 43,35 |
| 44 | CROm | coral reefs optimization M | 0,78512 | 0,46032 | 0,25958 | 1,50502 | 0,86688 | 0,35297 | 0,16267 | 1,38252 | 0,63231 | 0,26738 | 0,10734 | 1,00703 | 3,895 | 43,27 |
| 45 | ATAm | artificial tribe algorithm M | 0.71771 | 0.55304 | 0,25235 | 1,52310 | 0.82491 | 0.55904 | 0,20473 | 1,58867 | 0,44000 | 0,18615 | 0.09411 | 0.72026 | 3.832 | 42.58 |
| RW | neuroboids optimization algorithm 2(joo) | 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 algoritmo de Optimización Biogeográfica (BBO) ha demostrado resultados impresionantes en las pruebas realizadas, ocupando el puesto 12 entre los 45 mejores algoritmos de optimización basados en la población con un puntaje de rendimiento general del 58,5%. Se trata de un resultado excepcional para un algoritmo basado en una metáfora natural tan elegante e intuitiva.
Resulta particularmente destacable la capacidad de BBO para manejar problemas de dimensionalidades medias y altas de manera eficiente, lo que demuestra su escalabilidad y resistencia a la "maldición de la dimensionalidad", un problema al que se enfrentan muchos algoritmos de optimización.
La base conceptual de BBO —la migración de especies entre islas— ha resultado no solo una hermosa metáfora, sino también un mecanismo muy eficaz para equilibrar la exploración del espacio de búsqueda y la explotación de las soluciones encontradas. Un modelo de migración lineal, donde los hábitats ricos comparten activamente sus características y los hábitats pobres las adoptan activamente, crea un gradiente natural de flujo de información desde las mejores soluciones a las peores.
Especial atención merece el operador de mutación BBO, ya que es fundamentalmente diferente de los enfoques clásicos. En lugar de una probabilidad fija o aleatoria de mutación, BBO usa un modelo basado en la teoría donde la probabilidad de mutación es inversamente proporcional a la probabilidad de existencia del hábitat. Esto significa que las soluciones más "naturales" y estables (con un número promedio de especies) mutan raramente, mientras que las soluciones extremas, tanto muy buenas como muy malas, sufren cambios más frecuentes. Este enfoque crea un mecanismo adaptativo que regula automáticamente el equilibrio entre la estabilidad y la variabilidad de la población.
El algoritmo demuestra una excelente estabilidad en distintos tipos de paisajes: tiene un color verde uniforme en todas las pruebas y no muestra una caída sustancial en los resultados en comparación con otros algoritmos de optimización.
Una ventaja importante de BBO es su simplicidad conceptual combinada con una alta eficiencia. A diferencia de algunas metaheurísticas modernas que requieren muchos parámetros y operadores complejos, el BBO opera con conceptos intuitivos: migración, número de especies, idoneidad del hábitat.
Los resultados de las pruebas confirman que el BBO no es simplemente "otro" algoritmo bioinspirado, sino un método de optimización completo y competitivo, capaz de competir con líderes reconocidos en el campo. La combinación de solidez teórica, eficiencia computacional y aplicabilidad práctica hace del BBO una valiosa adición al arsenal de métodos modernos de optimización global.
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 BBO:
Ventajas:
- Es rápido.
- Implementación sencilla.
- Buenos resultados en una amplia gama de dimensionalidades de problemas.
Desventajas:
- Un gran número de parámetros.
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_BBO.mq5 | Script | Banco de pruebas BBO |
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/18354
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.
Características del Wizard MQL5 que debe conocer (Parte 62): Uso de patrones del ADX y el CCI con aprendizaje por refuerzo TRPO
Del básico al intermedio: Puntero a función
Descarga de datos del Fondo Monetario Internacional en Python
Red neuronal en la práctica La práctica lleva a la perfección
- 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