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: Todas las luciérnagas son "unisexuales", de modo que cualquier luciérnaga individual será atraída por todas las demás; 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; 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: 2) Generar una población inicial de luciérnagas 3) Formular la intensidad de la luz de modo que esté asociada con (ejemplo, para problemas de maximización, 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)
mover luciérnaga i hacia j; Variar atracción con la distancia r vía 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 y es
donde es un parámetro que controla la medida del paso, mientras que es un vector extraído de una distribución Gaussiana u otra distribución.
Puede demostrarse que el caso limitativo 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 es reemplazado por el mejor actual global , entonces FA esencialmente se convierte en el estándar PSO.
Guías de implementación tiene que ser relacionado con la escala de variables de diseño. Idealmente, el término tendría que ser de orden uno, lo que requiere que tendría que ser enlazado con las escalas. Por ejemplo, una posible elección es utilizar , donde es la escala media del problema. En el caso de que las escalas varíen significativamente, puede ser considerado como un vector para adoptar escalas diferentes en dimensiones diferentes. De modo parecido, también tendría que ser enlazada con las escalas. Por ejemplo, . 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 donde, aunque este valor puede depender del número de iteraciones. En algún problema difícil, pueda ser útil aumentar en algunas etapas, y reducirlo cuando sea necesario. Esta variación no-monótona de 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.A simple demo Matlab code is available Hay una versión disponible del algoritmo programada en python, aunque con funcionalidades limitadas.
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. 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. Además, también es mejor en el tratamiento de problemas de optimización de ruido, con una notable facilidad de implementación.
Chatterjee y otros 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. Se han hecho mejoras posteriores en el rendimiento con resultados prometedores.
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: 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. 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.
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: Adaptive Firefly Algorithm (AdaFa) Discrete Firefly Algorithm (DFA)T. Hassanzadeh, H. Vojodi and A. M. E. Moghadam, An image segmentation approach based on maximum variance intra-cluster method and firefly algorithm, in: Proc. of 7th Int.K. Durkota, Implementation of a discrete firefly algorithm for the QAP problem within the sage framework, BSc thesis, Czech Technical University, (2011). Multiobjective FA Lagrangian FARampriya B., Mahadevan K. and Kannan S., Unit commitment in deregulated power system using Lagrangian firefly algorithm, Proc. of IEEE Int. Chaotic FAL. dos Santos Coelho, D. L. de Andrade Bernert, V. C. Mariani, a chaotic firefly algorithm applied to reliability-redundancy optimization, in: 2011 IEEE Congress on Evolutionary Computation (CEC'11), pp. 517-521 (2011). Algoritmos híbridos Firefly Algorithm Based Memetic AlgorithmZhongyi Hu, Yukun Bao, and Tao Xiong, Electricity Load Forecasting using Support Vector Regression with Memetic Algorithms, The Scientific World Journal, 2014, http://www.hindawi.com/journals/tswj/aip/292575/ Parallel Firefly Algorithm with Predation (pFAP)E. F. P. Luz, H. F. Campos Velho, J. C. Becceneri, Firefly Algorithm with Predation: A parallel implementation applied to inverse heat conduction problem, in: Proc. of 10th World Congress on Computational Mechanics (WCCM 2012), (2012). Modified Firefly Algorithm
Aplicaciones Compresión de imagen digital y procesamiento de imagenM. H. M. Noor, A. R. Ahmad, Z. Hussain, K. A. Ahmad, A. R. Ainihayati, Multilevel thresholding of gel electrophoresis images using firefly algorithm, in: Proceedings of Control System, Computing and Engineering (ICCSCE2011), pp. 18-21 (2011). Optimización de autovalores Sistemas nanoelectronicos y Diseño de circuitos integradosG. Zheng, S. P. Mohanty, E. Kougianos, and O. Okobiah, "iVAMS: Intelligent Metamodel-Integrated Verilog-AMS for Circuit-Accurate System-Level Mixed-Signal Design Exploration ", in Proceedings of the 24th IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP), 2013, pp. 75--78. Selección de características y detección de fallosR. Falcon, M. Almeida and A. Nayak, Fault identification with binary adaptive fireflies in parallel and distributed systems, IEEE Congress on Evolutionary Computation, (2011). Diseño de antenas Diseño estructural Planificación y TSP (Problema del viajante)U. Hönig, A firefly algorithm-based approach for scheduling task graphs in homogeneous systems, Proceeding Informatics, , 724 (2010).A. Khadwilard, S. Chansombat, T. Thepphakorn, P. Thapatsuwan, W. Chainat, P. Pongcharoen,G. K. Jati and S. Suyanto, Evolutionary discrete firefly algorithm for travelling salesman problem, ICAIS2011, Lecture Notes in Artificial Intelligence (LNAI 6943), pp.393-403 (2011).S. Palit, S. Sinha, M. Molla, A. Khanra, M. Kule, A cryptanalytic attack on the knapsack cryptosystem using binary Firefly algorithm, in: 2nd Int. Servicios web semánticosC. B. Pop, V. R. Chifu, I. Salomie,R. B. Baico, M. Dinsoreanu, G. Copil, A hybrid firefly-inspired approach for optimal semantic web service composition, in: Proc. of 2nd Workshop on Software Services: Cloud Computing and Applications, June, 2011. Equilibrio de fase químico AgrupamientosJ. Senthilnath, S. N. Omkar and V. Mani, Clustering using firefly algorithm: Performance study, Swarm and Evolutionary Computation, June (2011). Problemas dinámicosS. M. Farahani, B. Nasiri and M. R. Meybodi, A multiswarm based firefly algorithm in dynamic environments, Third Int. A. A. Abshouri, M. R. Meybodi and A. Bakhtiary, New firefly algorithm based on multiswarm and learning automata in dynamic environments, Third Int. Problemas de procesados de imagen rígidosYudong Zhang and Lenan Wu, A Novel Method for Rigid Image Registration based on Firefly Algorithm, International Journal of Research and Reviews in Soft and Intelligent Computing, vol.2, no.2, pp. 141-146 (2012). Predicción de la estructura de proteínas Optimización de parámetros de máquinas de vectores de soporte (Comportamiento de la bolsa y predicciones meteorológicas) IK-FA (Solución de problemas cinemáticos inversos)Rokbani, Nizar, et al.
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
Referencias
Firefly Categoría:Heurística Categoría:Procesamiento digital de imágenes