Optimización basada en biogeografía

La optimización basada en biogeografía ( BBO ) es un algoritmo evolutivo (EA) que optimiza una función mejorando de forma estocástica e iterativa las soluciones candidatas con respecto a una medida dada de calidad, o función de aptitud . BBO pertenece a la clase de metaheurísticas ya que incluye muchas variaciones y no hace ninguna suposición sobre el problema y, por lo tanto, se puede aplicar a una amplia clase de problemas.

BBO se utiliza normalmente para optimizar funciones multidimensionales de valor real, pero no utiliza el gradiente de la función, lo que significa que no requiere que la función sea diferenciable como lo requieren los métodos de optimización clásicos, como el descenso de gradiente y los métodos cuasi-newton . Por lo tanto, BBO se puede utilizar en funciones discontinuas .

BBO optimiza un problema manteniendo una población de soluciones candidatas y creando nuevas soluciones candidatas combinando las existentes según una fórmula simple. De esta manera, la función objetivo se trata como una caja negra que simplemente proporciona una medida de calidad dada una solución candidata, y el gradiente de la función no es necesario.

Al igual que muchas EA, la BBO estuvo motivada por un proceso natural; en particular, la BBO estuvo motivada por la biogeografía , que es el estudio de la distribución de especies biológicas a través del tiempo y el espacio. ^[1] La BBO fue introducida originalmente por Dan Simon en 2008. ^[2]

Los modelos matemáticos de biogeografía describen la especiación (la evolución de nuevas especies ), la migración de especies (animales, peces, aves o insectos) entre islas y la extinción de especies. ^[3] Se dice que las islas que son amigables para la vida tienen un alto índice de idoneidad del hábitat (HSI). ^[4] Las características que se correlacionan con el HSI incluyen las precipitaciones, la diversidad vegetal, la diversidad topográfica, la superficie terrestre, la temperatura y otras. Las características que determinan se denominan variables del índice de idoneidad (SIV). En términos de habitabilidad, las SIV son las variables independientes y el HSI es la variable dependiente.

Las islas con un HSI alto pueden albergar muchas especies, y las islas con un HSI bajo pueden albergar solo unas pocas especies. Las islas con un HSI alto tienen muchas especies que emigran a hábitats cercanos debido a las grandes poblaciones y la gran cantidad de especies que albergan. Tenga en cuenta que la emigración de una isla con un HSI alto no ocurre porque las especies quieran abandonar su hogar; después de todo, su isla de origen es un lugar atractivo para vivir. La emigración ocurre debido a la acumulación de efectos aleatorios en una gran cantidad de especies con grandes poblaciones. La emigración ocurre cuando los animales viajan en restos flotantes , nadan, vuelan o viajan en el viento hacia islas vecinas. Cuando una especie emigra de una isla, no significa que la especie desaparezca por completo de su isla original; solo emigran unos pocos representantes, por lo que una especie que emigra permanece presente en su isla original mientras migra a una isla vecina. Sin embargo, en BBO se supone que la emigración de una isla da como resultado la extinción de esa isla. Esta suposición es necesaria en BBO porque las especies representan las variables independientes de una función y cada isla representa una solución candidata a un problema de optimización de funciones.

Las islas con un alto índice de saturación de hábitat no solo tienen una alta tasa de emigración, sino también una baja tasa de inmigración porque ya albergan a muchas especies. Las especies que migran a esas islas tienden a morir a pesar del alto índice de saturación de hábitat de la isla, porque existe demasiada competencia por los recursos con otras especies.

Las islas con un HSI bajo tienen una alta tasa de inmigración debido a sus bajas poblaciones. Una vez más, esto no se debe a que las especies quieran emigrar a esas islas; después de todo, estas islas son lugares indeseables para vivir. La razón por la que se produce la inmigración a estas islas es porque hay mucho espacio para especies adicionales. Si la especie inmigrante puede sobrevivir en su nuevo hogar y durante cuánto tiempo es otra cuestión. Sin embargo, la diversidad de especies está correlacionada con el HSI, por lo que cuando más especies llegan a una isla con un HSI bajo, el HSI de la isla tenderá a aumentar. ^[4]

La figura de la derecha ilustra un modelo de migración de islas. ^[3] La tasa de inmigración y la tasa de emigración son funciones del número de especies en la isla. La tasa de inmigración máxima posible ocurre cuando hay cero especies en la isla. A medida que aumenta el número de especies, la isla se vuelve más poblada, menos especies pueden sobrevivir a la inmigración y la tasa de inmigración disminuye. El mayor número posible de especies que el hábitat puede soportar es , momento en el que la tasa de inmigración es cero. Si no hay especies en la isla, entonces la tasa de emigración es cero. A medida que aumenta el número de especies en la isla, se vuelve más poblada, más representantes de especies pueden abandonar la isla y la tasa de emigración aumenta. Cuando la isla contiene el mayor número posible de especies , la tasa de emigración alcanza su valor máximo posible . ${\estilo de visualización \lambda}$${\estilo de visualización \mu}$${\displaystyle I}$${\displaystyle S_{\max}}$${\displaystyle S_{\max}}$${\estilo de visualización E}$

En BBO, es la probabilidad de que una variable independiente dada en la solución candidata -ésima sea reemplazada; es decir, es la probabilidad de inmigración de . Si se debe reemplazar una variable independiente, entonces la solución candidata que emigra se elige con una probabilidad que es proporcional a la probabilidad de emigración . Esto generalmente se realiza utilizando la selección de la ruleta . ${\displaystyle \lambda _{k}}$${\estilo de visualización k}$${\displaystyle \lambda _{k}}$$Estilo de visualización x_{k}}$${\displaystyle \mu_{k}}$

${\displaystyle {\text{Prob}}(x_{j}){\text{ se selecciona para la emigración}}={\frac {\mu _{j}}{\sum _{i=1}^{N}\mu _{i}}}}$

para , donde es el número de soluciones candidatas en la población. ${\displaystyle j=1,\cpuntos ,N}$${\estilo de visualización N}$

Al igual que la mayoría de los demás EA, BBO incluye mutación . Un algoritmo BBO básico con un tamaño de población de para optimizar una función dimensional se puede describir de la siguiente manera. ${\estilo de visualización N}$${\estilo de visualización n}$

Inicializar una población de soluciones candidatas Mientras no (criterio de terminación)
     Para cada , establecer la aptitud de la probabilidad de emigración de , hacer 
        con Para cada , establecer la probabilidad de inmigración hacer Para cada individuo hacer Para cada índice de variable independiente hacer 
            Usar para decidir probabilísticamente si inmigrar a Si inmigra entonces 
                Usar para seleccionar probabilísticamente al individuo que emigra Fin si 
        Siguiente índice de variable independiente: 
        Mutar probabilísticamente 
    Siguiente individuo:${\estilo de visualización N}$$Estilo de visualización: x_k$ 
 $Estilo de visualización x_{k}}$${\displaystyle \mu _{k}\propto }$$Estilo de visualización x_{k}}$${\displaystyle \mu _{k}\in [0,1]}$
     ${\displaystyle x_{k}}$${\displaystyle \lambda _{k}=1-\mu _{k}}$ 
    ${\displaystyle \{z_{k}\}\leftarrow \{x_{k}\}}$
    ${\displaystyle z_{k}(k=1,\cdots ,N)}$ 
        ${\displaystyle s\in [1,n]}$ ${\displaystyle \lambda _{k}}$${\displaystyle z_{k}}$
            ${\displaystyle \{\mu _{i}\}}$${\displaystyle x_{j}}$
                ${\displaystyle z_{k}(s)\leftarrow x_{j}(s)}$
            ${\displaystyle s\leftarrow s+1}$${\displaystyle z_{k}}$${\displaystyle k\leftarrow k+1}$
    ${\displaystyle \{x_{k}\}\leftarrow \{z_{k}\}}$
Próxima generación

• El tamaño de la población es un parámetro de ajuste. Si es demasiado pequeño o demasiado grande, el rendimiento de optimización de BBO se verá afectado. Las implementaciones típicas de BBO utilizan un valor de entre 20 y 200.${\displaystyle N}$${\displaystyle N}$${\displaystyle N}$
• La población inicial de soluciones candidatas suele generarse de forma aleatoria. Sin embargo, podría generarse de forma dependiente del problema en función de algunas suposiciones razonables o soluciones buenas conocidas previamente para el problema de optimización.${\displaystyle \{x_{k}\}_{k=1}^{N}}$
• El criterio de terminación depende del problema, como en cualquier otro EA. En la mayoría de las aplicaciones, el criterio de terminación es un límite de conteo de generación o un límite de evaluación de función (es decir, la frecuencia con la que se evalúa la función objetivo).
• ${\displaystyle \{z_{k}\}}$es una población temporal de modo que todas las variables emigrantes pueden originarse de la población que se encuentra al comienzo de la generación, que es .${\displaystyle \{x_{k}\}}$

Se han propuesto muchas variaciones del algoritmo BBO básico, entre las que se encuentran las siguientes.

• El elitismo se implementa en la mayoría de los EA para asegurarse de que la mejor solución candidata no se pierda de una generación a la siguiente. Esto se puede implementar de varias maneras, pero una forma común es guardar las mejores soluciones candidatas al comienzo de cada generación en un conjunto ; luego reemplazar las peores soluciones candidatas con al final de la generación, después de que se hayan completado la migración y la mutación. El tamaño de es un parámetro de ajuste, pero generalmente incluye los dos mejores individuos. El elitismo fue propuesto originalmente para algoritmos genéticos por DeJong. ^[5] El elitismo puede marcar una diferencia significativa en el rendimiento de BBO y es muy recomendable.${\displaystyle \mathbb {E} }$${\displaystyle \mathbb {E} }$${\displaystyle \mathbb {E} }$${\displaystyle \mathbb {E} }$
• El reemplazo de duplicados se implementa a menudo en BBO. Se trata de un procedimiento que se realiza al final de cada generación y que reemplaza a los individuos duplicados en la población. La búsqueda de duplicados puede requerir un gran esfuerzo computacional porque es una operación, por lo que a menudo se realiza solo cada pocas generaciones, en lugar de cada generación.${\displaystyle O(N^{2})}$
• La combinación se puede implementar en BBO. Con la combinación, en lugar de reemplazar una solución candidata inmigrante con una solución candidata inmigrante, se establece como igual a una combinación lineal de su valor original y :${\displaystyle z_{k}(s)}$${\displaystyle x_{j}(s)}$${\displaystyle z_{k}(s)}$${\displaystyle x_{j}(s)}$

${\displaystyle z_{k}(s)\leftarrow \alpha z_{k}(s)+(1-\alpha )x_{j}(s)}$

donde , y corresponde a la migración estándar como se muestra en el algoritmo anterior. El BBO combinado se basa en el cruce combinado en algoritmos genéticos, ^[6] y se ha demostrado que supera al BBO estándar. ^[7]${\displaystyle \alpha \in [0,1]}$${\displaystyle \alpha =0}$

• El algoritmo BBO presentado anteriormente se denomina BBO basado en inmigración parcial porque la solución candidata de inmigración se selecciona antes de que se seleccione la solución candidata de emigración, y la migración para cada variable independiente en la solución candidata de inmigración se realiza independientemente de todas las demás variables independientes. También se han propuesto otros enfoques para seleccionar las soluciones candidatas de inmigración y emigración. ^{[8] [9]}
• Las curvas de migración en la figura anterior son lineales, pero las curvas de migración no lineales a menudo brindan un mejor rendimiento. ^[10]

• BBO se ha hibridado con varios otros EA, incluyendo optimización de enjambre de partículas , ^{[9] [11]} evolución diferencial , ^[12] estrategia de evolución , ^[13] computación basada en oposición, ^[14] razonamiento basado en casos , ^[15] algoritmo de colonia de abejas artificiales , ^{[ cita requerida ]} optimización de búsqueda de alimento bacteriano, ^[16] búsqueda de armonía , ^[17] y el algoritmo simplex . ^[18]
• BBO se puede combinar con la búsqueda local para crear un algoritmo memético que funciona mucho mejor que BBO solo. ^[19]

• El siguiente código MATLAB ofrece una implementación de BBO para minimizar la función Rosenbrock de 20 dimensiones . Tenga en cuenta que el siguiente código es muy básico, aunque incluye elitismo. Una implementación de BBO seria debería incluir algunas de las variaciones analizadas anteriormente, como reemplazo de duplicados, combinación, migración no lineal y optimización local.

Función BBO % Optimización basada en biogeografía (BBO) para minimizar una función continua % Este programa fue probado con MATLAB R2012b 



GenerationLimit = 50 ; % límite de recuento de generaciones PopulationSize = 50 ; % tamaño de la población ProblemDimension = 20 ; % número de variables en cada solución (es decir, dimensión del problema) MutationProbability = 0.04 ; % probabilidad de mutación por solución por variable independiente NumberOfElites = 2 ; % cuántas de las mejores soluciones se deben conservar de una generación a la siguiente MinDomain = - 2.048 ; % límite inferior de cada elemento del dominio de la función MaxDomain = + 2.048 ; % límite superior de cada elemento del dominio de la función   
   
   
   
   
   
   

% Inicializar la población 
rng ( round ( sum ( 100 * clock ))); % inicializar el generador de números aleatorios x = zeros ( PopulationSize , ProblemDimension ); % asignar memoria para la población para index = 1 : PopulationSize % inicializar aleatoriamente la población x ( index , :) = MinDomain + ( MaxDomain - MinDomain ) * rand ( 1 , ProblemDimension ); end Cost = RosenbrockCost ( x ); % calcular el costo de cada individuo   [ x , Cost ] = PopulationSort ( x , Cost ); % ordenar la población de mejor a peor MinimumCost = zeros ( GenerationLimit , 1 ); % asignar memoria MinimumCost ( 1 ) = Cost ( 1 ); % guardar el mejor costo en cada generación en la matriz MinimumCost disp ([ 'Generation 0 min cost = ' , num2str ( MinimumCost ( 1 ))]); z = zeros ( PopulationSize , ProblemDimension ); % asignar memoria para la población temporal 
    
      
              

   
     
    
   
 
    

% Calcular las tasas de migración, asumiendo que la población está ordenada de más adecuada a menos adecuada 
mu = ( PopulationSize + 1 - ( 1 : PopulationSize )) / ( PopulationSize + 1 ); % tasa de emigración lambda = 1 - mu ; % tasa de inmigración           
     

para Generación = 1 : GenerationLimit % Guarde las mejores soluciones y costos en las matrices de élite EliteSolutions = x ( 1 : NumberOfElites , :); EliteCosts = Cost ( 1 : NumberOfElites );     
    
         
        

    % Utilice las tasas de migración para decidir cuánta información compartir entre soluciones 
para k = 1 : PopulationSize % Migración probabilística a la k-ésima solución para j = 1 : ProblemDimension         
        
             

            si rand < lambda ( k ) % ¿Deberíamos inmigrar? % Sí - Elija una solución desde la cual emigrar (selección de ruleta) RandomNum = rand * sum ( mu ); Select = mu ( 1 ); SelectIndex = 1 ; mientras ( RandomNum > Select ) && ( SelectIndex < PopulationSize ) SelectIndex = SelectIndex + 1 ; Select = Select + mu ( SelectIndex ); fin z ( k , j ) = x ( SelectIndex , j ); % este es el paso de migración de lo contrario z ( k , j ) = x ( k , j ); % no hay migración para esta variable independiente fin    
                
                    
                  
                  
                       
                        
                        
                
                     
            
                     
            

        
fin fin    

    % de mutación 
para k = 1 : Tamaño de población para ParameterIndex = 1 : ProblemDimension if rand < MutationProbability z ( k , ParameterIndex ) = MinDomain + ( MaxDomain - MinDomain ) * rand ; fin fin fin         
             
               
                         
            
        
    

    x = z ; % reemplaza las soluciones con sus nuevas versiones migradas y mutadas Cost = RosenbrockCost ( x ); % calcula el costo [ x , Cost ] = PopulationSort ( x , Cost ); % ordena la población y los costos de mejor a peor   
       
         

    para k = 1 : NumberOfElites % reemplaza a los peores individuos con las élites de la generación anterior x ( PopulationSize - k + 1 , :) = EliteSolutions ( k , :); Cost ( PopulationSize - k + 1 ) = EliteCosts ( k ); fin      
            
          
    

    [ x , Cost ] = PopulationSort ( x , Cost ); % ordena la población y los costos de mejor a peor MinimumCost ( Generation + 1 ) = Cost ( 1 ); disp ([ 'Generation ' , num2str ( Generation ), ' min cost = ' , num2str ( MinimumCost ( Generation + 1 ))]) end     
      
       


% Termine mostrando la mejor solución y graficando los resultados 
disp ([ 'Mejor solución encontrada = ' , num2str ( x ( 1 , :))]) close all plot ( 0 : GenerationLimit , MinimumCost ); xlabel ( 'Generation' ) ylabel ( 'Minimum Cost' ) return  
 
 




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
function [x, Cost] = PopulationSort ( x, Cost ) % Ordena la población y los costos de mejor a peor [ Cost , indices ] = sort ( Cost , 'ascend' ); x = x ( indices , :); return 

    
   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
function  [Cost] = RosenbrockCost ( x ) % Calcula el valor de la función Rosenbrock de cada elemento en x NumberOfDimensions = size ( x , 2 ); Cost = zeros ( size ( x , 1 ), 1 ); % asigna memoria para la matriz Cost para PopulationIndex = 1 : length ( x ) Cost ( PopulationIndex ) = 0 ; para i = 1 : NumberOfDimensions - 1 Temp1 = x ( PopulationIndex , i ); Temp2 = x ( PopulationIndex , i + 1 ); Costo ( Índice de población ) = Costo ( Índice de población ) + 100 * ( Temp2 - Temp1 ^ 2 ) ^ 2 + ( Temp1 - 1 ) ^ 2 ; fin fin retorno  

   
     
     
      
         
           
           
                    
    

• "bbo: Biogeography-Based Optimization" es un paquete R para BBO continuo. ^[20]

BBO se ha extendido a funciones ruidosas (es decir, funciones cuya evaluación de aptitud está corrompida por el ruido); ^[21] funciones restringidas; ^[22] funciones combinatorias; ^[23] y funciones multiobjetivo. ^{[24] [25]} Además, se implementó un algoritmo de optimización multiobjetivo inspirado en la microbiogeografía (μBiMO): es adecuado para resolver optimizaciones multiobjetivo en el campo del diseño industrial porque se basa en un pequeño número de islas (de ahí el nombre μBiMO), es decir, se requieren pocas llamadas a funciones objetivo. ^[26]

El BBO se ha analizado matemáticamente utilizando modelos de Markov ^[27] y modelos de sistemas dinámicos. ^[28]

Los investigadores han aplicado BBO en diversas aplicaciones académicas e industriales y han descubierto que funciona mejor que los métodos de optimización global más modernos.

Por ejemplo, Wang et al. demostraron que BBO tenía el mismo rendimiento que FSCABC pero con códigos más simples. ^[29]

Yang et al. demostraron que BBO era superior a GA, PSO y ABC. ^[30]

• Página de inicio de BBO