Algoritmo firefly

El algoritmo firefly (FA por sus siglas en inglés, "firefly algorithm"; algoritmo luciérnaga en español) es un algoritmo metaheurístico, inspirado en el comportamiento del centelleo de las luciérnagas. El propósito primario de una luciérnaga es generar destellos de luz para actuar como sistema de señal para atraer a otras luciérnagas. Xin-She Yang formuló este algoritmo con las siguientes premisas:^[1]

1. Todas las luciérnagas son "unisexuales", de modo que cualquier luciérnaga individual será atraída por todas las demás;
2. La atracción es proporcional a su brillo, y para cualquier par de luciérnagas, la menos brillante será atraída por (y por lo tanto se desplazará hacia) la más brillante; aun así, la intensidad (el brillo aparente) decrece cuando aumenta la distancia entre ambas;
3. Si no hay luciérnagas más brillantes que una dada, esta se mueve aleatoriamente.

El brillo es asociado con los valores de una función objetivo.

El algoritmo firefly es un procedimiento metaheurístico de optimización inspirado en la naturaleza.

Descripción del algoritmo

El pseudocódigo puede ser resumido como:

Inicio
   1) Función Objetivo: ${\displaystyle f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},...,x_{d})}$;
   2) Generar una población inicial de luciérnagas ${\displaystyle \mathbf {x} _{i}\quad (i=1,2,\dots ,n)}$;.
   3) Formular la intensidad de la luz I de modo que esté asociada con ${\displaystyle f(\mathbf {x} )}$
      (ejemplo, para problemas de maximización, ${\displaystyle I\propto f(\mathbf {x} )}$ or simply ${\displaystyle I=f(\mathbf {x} )}$;)
   4) Definir el coeficiente de absorción γ

   While (t < MaxGeneration)
      for i = 1 : n (all n luciérnagas)
         for j = 1 : n (n luciérnagas)
            if (${\displaystyle I_{j}>I_{i}}$),
               mover luciérnaga i hacia j;
               Variar atracción con la distancia r vía ${\displaystyle \exp(-\gamma \;r)}$;
               Evaluar las nuevas soluciones y actualizar la intensidad de la luz;
            end if 
         end for j
      end for i
      Ordenar las luciérnagas y buscar la más luminosa;
   end while

   Post-proceso de los resultados y visualización;

final

La fórmula de actualización principal para cualquier par de dos luciérnagas ${\displaystyle \mathbf {x} _{i}}$ y ${\displaystyle \mathbf {x} _{j}}$ es

${\displaystyle \mathbf {x} _{i}^{t+1}=\mathbf {x} _{i}^{t}+\beta \exp[-\gamma r_{ij}^{2}](\mathbf {x} _{j}^{t}-\mathbf {x} _{i}^{t})+\alpha _{t}{\boldsymbol {\epsilon }}_{t}}$

donde ${\displaystyle \alpha _{t}}$ es un parámetro que controla la medida del paso, mientras que ${\displaystyle {\boldsymbol {\epsilon }}_{t}}$ es un vector extraído de una distribución Gaussiana u otra distribución.

Puede demostrarse que el caso limitativo ${\displaystyle \gamma \rightarrow 0}$ corresponde a la optimización por enjambre de partículas estándar (PSO). De hecho, si el bucle interior (for j) es eliminado y el brillo ${\displaystyle I_{j}}$ es reemplazado por el mejor actual global ${\displaystyle g^{*}}$, entonces FA esencialmente se convierte en el estándar PSO.

Guías de implementación

${\displaystyle \gamma }$ tiene que ser relacionado con la escala de variables de diseño. Idealmente, el término ${\displaystyle \beta }$ tendría que ser de orden uno, lo que requiere que ${\displaystyle \gamma }$ tendría que ser enlazado con las escalas. Por ejemplo, una posible elección es utilizar ${\displaystyle \gamma =1/{\sqrt {L}}}$ , donde ${\displaystyle L}$ es la escala media del problema. En el caso de que las escalas varíen significativamente, ${\displaystyle \gamma }$ puede ser considerado como un vector para adoptar escalas diferentes en dimensiones diferentes. De modo parecido, ${\displaystyle \alpha _{t}}$ también tendría que ser enlazada con las escalas. Por ejemplo, ${\displaystyle \alpha _{t}\leftarrow 0.01L\alpha _{t}}$. Se puede señalar que la descripción anterior no incluye la reducción aleatoria. De hecho, en su implementación real por diversos investigadores, el movimiento de las luciérnagas es gradualmente reducido por una especie de suavizamiento aleatorio como ${\displaystyle \alpha =\alpha _{0}\delta ^{t}}$ donde${\displaystyle 0<\delta <1(e.g.,\delta =0.97)}$, aunque este valor puede depender del número de iteraciones.^[2] En algún problema difícil, pueda ser útil aumentar ${\displaystyle \alpha _{t}}$ en algunas etapas, y reducirlo cuando sea necesario. Esta variación no-monótona de ${\displaystyle \alpha _{t}}$ capacita al algoritmo para salir de cualquier óptimo local como en el caso improbable de que pudiera bloquearse si el término aleatorio es reducido demasiado deprisa.

Estudios paramétricos muestran que n (el número de luciérnagas) tendría que ser aproximadamente entre 15 y 40 para la mayoría de problemas.^[3] Hay una versión disponible del algoritmo programada en python, aunque con funcionalidades limitadas.^[4]

Estudios recientes muestran que el algoritmo firefly es muy eficaz, y puede superar a otros algorítmicos metaheurísticos que incluyen optimización por enjambre de partículas.^[5][6] Otros algoritmos metaheurísticos pueden tener dificultad en tratar funciones de prueba estocástica, y parece que el algoritmo firefly puede tratar la prueba estocástica de forma muy eficientemente.^[7] Además, también es mejor en el tratamiento de problemas de optimización de ruido, con una notable facilidad de implementación.^[8][9]

Chatterjee y otros^[10] han demostrado que el algoritmo firefly puede ser superior a la optimización por enjambre de partículas en sus aplicaciones. Además, puede solucionar eficientemente problemas no convexos con condiciones de contorno complejas no lineales.^[11][12] Se han hecho mejoras posteriores en el rendimiento con resultados prometedores.^[13][14]

Análisis teórico

A pesar de que se han hecho muchos progresos en algorítmos basados en el FA desde 2008, todavía se necesitan esfuerzos significativos para mejorar su rendimiento:^[15]

• Análisis teórico para convergencia de trajectorias;
• Deducción de las condiciones suficientes y necesarias para la selección de los coeficientes de control;
• Mecanismos o estrategias eficaces para la selección de los parámetros de control;
• Reglas no-homogéneas de actualización para realzar la capacidad de búsqueda.^[16]

Las variantes clásicas del algoritmo tienen encuadres de parámetros inesperados y leyes de actualización limitada, notablemente la regla homogénea necesita ser mejorada para hacer más búsquedas en escenarios de formas físicas diferentes. Se ha efectuado el análisis de la trayectoria de una sola luciérnaga en el algoritmo tradicional y en una variante adaptativa, respectivamente. Estos análisis llevan a un modelo general de los algoritmos que incluyen un conjunto de las condiciones de frontera para los parámetros que garantizan las tendencias de convergencia de los dos algoritmos.^[15]

Variantes del algoritmo firefly

Una revisión recopilatoria reciente ha mostrado que el algoritmo firefly y sus variantes han sido utilizados en casi todas las áreas de la ciencia:^[17]

• Adaptive Firefly Algorithm (AdaFa)^[18][16]
• Discrete Firefly Algorithm (DFA)^[19][20][21]
• Multiobjective FA^[22]
• Lagrangian FA^[23]
• Chaotic FA^[24]
• Algoritmos híbridos^[25]
• Firefly Algorithm Based Memetic Algorithm^[26]
• Parallel Firefly Algorithm with Predation (pFAP)^[27]
• Modified Firefly Algorithm^[28]

Aplicaciones

• Compresión de imagen digital y procesamiento de imagen^{[29][30][31][32]}
• Optimización de autovalores^[33]
• Sistemas nanoelectronicos y Diseño de circuitos integrados^[34]
• Selección de características y detección de fallos^[35][36][37]
• Diseño de antenas^[38][10][39]
• Diseño estructural^[40]
• Planificación y TSP (Problema del viajante)^{[41][42][43][44]}
• Servicios web semánticos^[45]
• Equilibrio de fase químico^[46]
• Agrupamientos^[47]
• Problemas dinámicos^[48][49]
• Problemas de procesados de imagen rígidos^[50]
• Predicción de la estructura de proteínas^[51][52]
• Optimización de parámetros de máquinas de vectores de soporte (Comportamiento de la bolsa y predicciones meteorológicas)^[53][26]
• IK-FA (Solución de problemas cinemáticos inversos)^[54]

Véase también

• Evolutivo multi-optimización modal
• Glowworm Optimización de enjambre (GSO)
• Metaheuristic
• Inteligencia de enjambre

Enlaces externos

• Optimización de algoritmo Firefly (James McCaffrey) Microsoft Magazine. Junio de 2015. Interesante enlace en español, con código VB de ejemplo para descargar.
• Firefly Algorithm implemented in Python
• Firefly Algorithm in C/C++
• Firefly Algorithm in Matlab or Octave