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

Referencias

1. Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms. Frome: Luniver Press. ISBN 1-905986-10-6.
2. «http://www.mathworks.com/matlabcentral/fileexchange/29693-firefly-algorithm/content/fa_mincon.m».
3. A simple demo Matlab code is available
4. «https://code.google.com/p/csc6810project/».
5. Yang, X. S. (2009). «Firefly algorithms for multimodal optimization». Stochastic Algorithms: Foundations and Applications, SAGA 2009. Lecture Notes in Computer Sciences 5792. pp. 169-178. arXiv:1003.1466.
6. Lukasik, S.; Zak, S. (2009). «Firefly algorithm for continuous constrained optimization task». ICCCI 2009, Lecture Notes in Artificial Intelligence (Eds. N. T. Ngugen, R. Kowalczyk, S. M. Chen) 5796. pp. 97-100.
7. Yang, X.-S. (2010). «Firefly algorithm, stochastic test functions and design optimisation». Int. J. Bio-inspired Computation 2 (2): 78-84. arXiv:1003.1409. doi:10.1504/ijbic.2010.032124.
8. Chai-ead, N.; Aungkulanon, P.; Luangpaiboon, P. (2011). «Bees and firefly algorithms for noisy non-linear optimisation problems». Prof. Int. Multiconference of Engineers and Computer Scientists 2011 2: 1449-1454.
9. Aungkulanon, P.; Chai-ead, N.; Luangpaiboon, P. (2011). «Simulated manufacturing process improvement via particle swarm optimisation and firefly algorithms». Prof. Int. Multiconference of Engineers and Computer Scientists 2011 2: 1123-1128.
10. Chatterjee, A.; Mahanti, G. K.; Chatterjee, A. (2012). «Design of a fully digital controlled reconfigurable switched beam conconcentric ring array antenna using firefly and particle swarm optimization algorithm». Progress in Elelectromagnetic Research B 36: 113-131. doi:10.2528/pierb11083005.
11. Yang, X. S.; Hosseini, S. S.; Gandomi, A. H. «Firefly algorithm for solving non-convex economic dispatch problems with valve loading effect». Applied Soft Computing 12 (3): 1180-1186. doi:10.1016/j.asoc.2011.09.017.
12. Abdullah, A.; Deris, S.; Mohamad, M. S.; Hashim, S. Z. M. (2012). «A new hybrid firefly algorithm for complex and nonlinear problem, in: Distributed Computing and Artificial Intelligence». Advances in Intelligent and Soft Computing 151: 673-680. doi:10.1007/978-3-642-28765-7_81.
13. Farahani, S. M.; Abshouri, A. A.; Nasiri, B.; Meybodi, M. R. (2012). «Some hybrid models to improve firefly algorithm performance». Int. J. Artificial Intelligence 8 (S12): 97-117.
14. Nasiri, B.; Meybodi, M. R. (2012). «Speciation-based firefly algorithm for optimization in dynamic environments». Int. J. Artificial Intelligence 8 (S12): 118-132.
15. Cheung, Ngaam J.; Ding, X.-M.; Shen, H.-B. (2016). «A Non-Homogeneous Firefly Algorithm and Its Convergence Analysis». Journal of Optimization Theory and Applications. doi:10.1007/s10957-016-0875-4. Archivado desde el original el 5 de marzo de 2016. Consultado el 26 de febrero de 2016.
16. Cheung, Ngaam J.; Ding, X.-M.; Shen, H.-B. (2014). «Adaptive Firefly Algorithm: Parameter Analysis and its Application». PLOS ONE 9 (11): e112634. doi:10.1371/journal.pone.0112634.
17. Fister, I.; Fister, Jr.; Yang, X. S.; Brest, J. (2013). «A comprehensive review of firefly algorithms». Swarm and Evolutionary Computation 13 (1): 34-46. doi:10.1016/j.swevo.2013.06.001.
18. «http://godzilla.uchicago.edu/pages/ngaam/AdaFa/index.html». Archivado desde el original el 4 de marzo de 2016. Consultado el 26 de febrero de 2016.
19. Sayadi, M. K.; Ramezanian, R.; Ghaffari-Nasab, N. (2010). «A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems». Int. J. of Industrial Engineering Computations 1: 1-10. doi:10.5267/j.ijiec.2010.01.001.
20. 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.
21. K. Durkota, Implementation of a discrete firefly algorithm for the QAP problem within the sage framework, BSc thesis, Czech Technical University, (2011). «Copia archivada». Archivado desde el original el 25 de abril de 2012. Consultado el 21 de mayo de 2013.
22. Apostolopoulos, T.; Vlachos, A. (2011). «Application of the Firefly Algorithm for Solving the Economic Emissions Load Dispatch Problem». International Journal of Combinatorics 2011: Article ID 523806.
23. Rampriya B., Mahadevan K. and Kannan S., Unit commitment in deregulated power system using Lagrangian firefly algorithm, Proc. of IEEE Int.
24. L. 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).
25. Giannakouris, G.; Vassiliadis, V.; Dounias, G. (2010). «Experimental study on a hybrid nature-inspired algorithm for financial portfolio optimization». SETN 6040: 101-111. doi:10.1007/978-3-642-12842-4_14.
26. Zhongyi 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/
27. 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).
28. Tilahun, S. L.; Ong, H. C. «Modified Firefly Algorithm». Journal of Applied Mathematics 2012: 467631.
29. Horng, M.-H.; Jiang, T. W. (2010). «The codebook design of image vector quantization based on the firefly algorithm». Computational Collective Intelligence, Technologies and Applications, LNCS 6423: 438-447. doi:10.1007/978-3-642-16696-9_47.
30. Horng, M.-H. (2011). «vector quantization using the firefly algorithm for image compression». Expert Systems with Applications 38.
31. Horng, M.-H.; Liou, R.-J (2011). «Multilevel minimum cross entropy threshold selection based on the firefly algorithm». Expert Systems with Applications 38 (12): 14805-14811. doi:10.1016/j.eswa.2011.05.069.
32. M. 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).
33. Dutta, R.; Ganguli, R.; Mani, V. (2011). «Exploring isospectral spring-mass systems with firefly algorithm». Proc. Roy. Soc. A. 467.
34. G. Zheng, S. P. Mohanty, E. Kougianos, and O. Okobiah, "iVAMS: Intelligent Metamodel-Integrated Verilog-AMS for Circuit-Accurate System-Level Mixed-Signal Design Exploration Archivado el 4 de marzo de 2016 en Wayback Machine.", in Proceedings of the 24th IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP), 2013, pp. 75--78.
35. Banati, H.; Bajaj, M. (2011). «Firefly based feature selection approach». Int. J. Computer Science Issues 8 (2): 473-480.
36. R. Falcon, M. Almeida and A. Nayak, Fault identification with binary adaptive fireflies in parallel and distributed systems, IEEE Congress on Evolutionary Computation, (2011).
37. Hu, Z.; Bao, Y.; Xiong, T.; Chiong, R. (2015). «Hybrid filter–wrapper feature selection for short-term load forecasting». Engineering Applications of Artificial Intelligence 40: 17-27. doi:10.1016/j.engappai.2014.12.014.
38. Basu, B.; Mahanti, G. K. (2011). «Firefly and artificial bees colony algorithm for synthesis of scanned and broadside linear array antenna». Progress in Electromagnetic Research B. 32: 169-190. doi:10.2528/pierb11053108.
39. Chatterjee, Anirban; Kumar Mahanti, Gautam; Ghatak, Gourab (2014). «Synthesis of satellite footprint patterns from rectangular planar array antenna by using swarm-based optimization algorithms». Int. J. Satell. Commun. Network 32: 25-47. doi:10.1002/sat.1055.
40. Gandomi, A. H.; Yang, X. S.; Alavi, A. H. (2011). «Mixed variable structural optimization using firefly algorithm». Computers and Structures 89 (23-24): 2325-2336. doi:10.1016/j.compstruc.2011.08.002.
41. U. Hönig, A firefly algorithm-based approach for scheduling task graphs in homogeneous systems, Proceeding Informatics, doi 10.2316/P.2010.724-033, 724 (2010).
42. A. Khadwilard, S. Chansombat, T. Thepphakorn, P. Thapatsuwan, W. Chainat, P. Pongcharoen,
43. 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).
44. S. Palit, S. Sinha, M. Molla, A. Khanra, M. Kule, A cryptanalytic attack on the knapsack cryptosystem using binary Firefly algorithm, in: 2nd Int.
45. C. 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.
46. Fateen, S. E.; Bonilla-Petrociolet, A.; Rangaiah, G. P. (2012). «Evaluation of covariance matrix adaptation evolution strategy, shuffled complex evolution and firefly algorithms for phase stability, phase equilibrium and chemical equilibrium problems». Chemical Engineering Research and Design 90: 2051-2071. doi:10.1016/j.cherd.2012.04.011.
47. J. Senthilnath, S. N. Omkar and V. Mani, Clustering using firefly algorithm: Performance study, Swarm and Evolutionary Computation, June (2011). doi 10.1016/j.swevo.2011.06.003
48. S. M. Farahani, B. Nasiri and M. R. Meybodi, A multiswarm based firefly algorithm in dynamic environments, Third Int.
49. A. A. Abshouri, M. R. Meybodi and A. Bakhtiary, New firefly algorithm based on multiswarm and learning automata in dynamic environments, Third Int.
50. Yudong 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).
51. Maher, B.; Albrecht, A.; Loomes, M.; Yang, X. S.; Steinhofel, K. (2014). «A firefly-inspired method for protein structure prediction in lattice models». Biomolucules 4 (1): 56-75. doi:10.3390/biom4010056.
52. Yudong, Zhang; Lenan, Wu; Shuihua, Wang (2013). «Solving Two-Dimensional HP model by Firefly Algorithm and Simplified Energy Function». Mathematical Problems in Engineering 2013: 1-9. doi:10.1155/2013/398141.
53. Xiong, Tao; Bao, Yukun; Hu, Zhongyi (2014). «Multiple-output support vector regression with a firefly algorithm for interval-valued stock price index forecasting». Knowl.-Based Syst. 55: 87-100. doi:10.1016/j.knosys.2013.10.012.
54. Rokbani, Nizar, et al.

• Datos: Q48784144