萤火虫算法

维基百科,自由的百科全书
跳转至: 导航搜索

萤火虫算法(Firefly Algorithm)是一种启发式算法,灵感来自于萤火虫闪烁的行为。萤火虫的闪光,其主要目的是作为一个信号系统,以吸引其他的萤火虫。剑桥大学的Xin-She Yang(音译:杨新社)教授提出了萤火虫算法,其假设为[1]

  • 萤火虫不分性别,这样一个萤火虫将会吸引到所有其他的萤火虫;
  • 吸引力与它们的亮度成正比,对于任何两个萤火虫,不那么明亮的萤火虫被吸引,因此移动到更亮的一个,然而,亮度又随着其距离的增加而减少;
  • 如果没有比一个给定的萤火虫更亮的萤火虫,它会随机移动。

亮度应与目标函数联系起来。萤火虫算法是以自然为灵感的启发式优化算法。[2]

算法描述[编辑]

萤火虫算法的伪代码可以概括为:

Begin
1)目标函数 f(\mathbf{x}) \quad \mathbf{x}=(x_1, x_2, ..., x_d)^T 
2)生成一个萤火虫的初始人口 \mathbf{x}_i, \quad (i=1,2,...,n) 
3)制定光照强度I,因此,它与f(\mathbf{x})
   (例如,对于最大化问题I \propto I=f(\mathbf{x});
4)定义吸收系数\gamma 
while(T MaxGeneration)
   for i =1:n(所有n萤火虫)
      for j =1:n(n萤火虫)
         if( I_j > I_i),
            移动萤火虫i向j;
         end if
         吸引力与距离r =\exp[ - \gamma r^2];
         评估新的解决方案和更新的光强度;
      end for j
   end  for i
   排名萤火虫和找到当前最佳;
end while
处理后的结果和可视化;
end

对于任何一两只萤火虫的主要更新公式\mathbf{x}_i and \mathbf{x}_j

\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

其中\alpha_t 是步长参数, e \boldsymbol{\epsilon}_t 是一个矢量(服从高斯或其他的分布)。

可以证明在\gamma \rightarrow 0 的情况,FA可以简化为 准粒子群优化(PSO).事实上,,如果内环(j)条被删除,亮度 I_j替换为当前的全球最佳g^*,FA基本上成为标准PSO。

萤火虫算法的变种[编辑]

离散萤火虫算法(DFA)[编辑]

离散形式的萤火虫算法(Discrete Firefly Algorithm,DFA)[3] DFA优于现有算法如蚁群算法。

对于图像分割,基于FA-方法比Otsu的方法更为有效.[4] 同时, 离散萤火虫算法对QAP问题,Durkota已进很好的实现行[5]

多目标萤火虫算法[编辑]

Apostolopoulos and Vlachos对FA进行了一个重要的多目标研究[6]。同时,Yang提出了多目标萤火虫算法(Multiobjective Firefly Algorithm,MOFA),对连续优化问题有很好的效果[7]

拉格朗日FA[编辑]

拉格朗日萤火虫算法用来解决电力系统优化单元承诺问题[8]

混沌FA[编辑]

混沌萤火虫算法(Chaotic Firefly Algorithm,CFA)也显示了算法的有效性[9]

混合算法[编辑]

萤火虫算法与蚁群优化算法相结合的混合算法,能够解决金融投资组合优化 [10]

基于萤火虫算法的 Memetic 算法[编辑]

一种基于萤火虫算法(FA)的Memetic算法(FA-MA)被用来优化支持向量机(SVR)预测模型的参数。在该FA-MA中,FA用来搜索全局解空间,而模式搜索(pattern Search) 被用来进行个体学习和局部解空间搜索。[11]

实际应用[编辑]

萤火虫算法已被应用到几乎所有领域科学和工程,如数字图像压缩和图像处理[12][13],特征值优化[14],特征提取和故障检测[15][16],天线设计[17][18],工程结构设计[19], 调度和旅行商问题[20][21][22],语义组成[23],化学相平衡[24], 聚类[25],动态问题[26][27], 刚性图像配准问题[28],参数选择[29][30],蛋白质折叠问题[31]等等。

参考文献[编辑]

  1. ^ Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms. Frome: Luniver Press, UK
  2. ^ http://www.mathworks.com/matlabcentral/fileexchange/29693-firefly-algorithm/content/fa_mincon.m
  3. ^ Sayadi, M. K.; Ramezanian, R.; Ghaffari-Nasab, N. A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. Int. J. of Industrial Engineering Computations. 2010, 1: 1–10. 
  4. ^ 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. Conf. on Natural Computation (ICNC), pp. 1817-1821 (2011).
  5. ^ K. Durkota, Implementation of a discrete firefly algorithm for the QAP problem within the sage framework, BSc thesis, Czech Technical University, (2011). http://cyber.felk.cvut.cz/research/theses/papers/189.pdf
  6. ^ Apostolopoulos, T.; Vlachos, A. Application of the Firefly Algorithm for Solving the Economic Emissions Load Dispatch Problem. International Journal of Combinatorics. 2011, 2011: Article ID 523806. 
  7. ^ X. S. Yang, Multiobjective firefly algorithm for continuous optimization, Engineering with Computers, vol. 29, No. 2, pp. 175-184 (2013).
  8. ^ Rampriya B., Mahadevan K. and Kannan S., Unit commitment in deregulated power system using Lagrangian firefly algorithm, Proc. of IEEE Int. Conf. on Communication Control and Computing Technologies (ICCCCT), pp. 389-393 (2010).
  9. ^ 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).
  10. ^ G. Giannakouris, V. Vassiliadis and G. Dounias, Experimental study on a hybrid nature-inspired algorithm for financial portfolio optimization, SETN 2010, LNAI 6040, pp. 101-111 (2010).
  11. ^ 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/
  12. ^ Horng M.-H. and Jiang T. W., The codebook design of image vector quantization based on the firefly algorithm, in: Computational Collective Intelligence, Technologies and Applications, LNCS, Vol. 6423, pp. 438-447 (2010).
  13. ^ M.-H. Horng, vector quantization using the firefly algorithm for image compression, Expert Systems with Applications, Vol. 38, (article in press) 12 Aug. (2011).
  14. ^ R. Dutta, R. Ganguli and V. Mani, Exploring isospectral spring-mass systems with firefly algorithm, Proc. Roy. Soc. A., Vol. 467, (2011)http://rspa.royalsocietypublishing.org/content/early/2011/06/16/rspa.2011.0119.abstract
  15. ^ H. Banati and M. Bajaj, Firefly based feature selection approach, Int. J. Computer Science Issues, vol. 8, No. 2, 473-480 (2011).
  16. ^ R. Falcon, M. Almeida and A. Nayak, Fault identification with binary adaptive fireflies in parallel and distributed systems, IEEE Congress on Evolutionary Computation, (2011).
  17. ^ B. Basu and G. K. Mahanti, Firefly and artificial bees colony algorithm for synthesis of scanned and broadside linear array antenna, Progress in Electromagnetic Research B., Vol. 32, 169-190 (2011).
  18. ^ A. Chatterjee, G. K. Mahanti, and A. Chatterjee, 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, Vol. 36, 113-131(2012)
  19. ^ A. H. Gandomi, X. S. Yang, A. H. Alavi, Mixed variable structural optimization using firefly algorithm, Computers and Structures, Vol. 89, No. 23-24, pp. 2325-2336 (2011). doi:10.1016/j.compstruc.2011.08.002
  20. ^ U. Hönig, A firefly algorithm-based approach for scheduling task graphs in homogenous systems, Proceeding Informatics, doi:10.2316/P.2010.724-033, 724 (2010).
  21. ^ A. Khadwilard, S. Chansombat, T. Thepphakorn, P. Thapatsuwan, W. Chainat, P. Pongcharoen, Application of firefly algorithm and its parameter setting for job shop scheduling, First Symposius on Hands-On Research and Development, (2011).
  22. ^ 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).
  23. ^ 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.
  24. ^ S. E. Fateen, A. Bonilla-Petrociolet, G. P. Rangaiah, 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, May (2012). http://dx.doi.org/10.1016/j.cherd.2012.04.011
  25. ^ 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
  26. ^ S. M. Farahani, B. Nasiri and M. R. Meybodi, A multiswarm based firefly algorithm in dynamic environments, Third Int. Conference on Signal Processing Systems (ICSPS2011), Aug 27-28, Yantai, China, pp. 68-72 (2011)
  27. ^ A. A. Abshouri, M. R. Meybodi and A. Bakhtiary, New firefly algorithm based on multiswarm and learning automata in dynamic environments, Third Int. Conference on Signal Processing Systems (ICSPS2011), Aug 27-28, Yantai, China, pp. 73-77 (2011).
  28. ^ 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).
  29. ^ Tao Xiong, Yukun Bao, Zhongyi Hu: Multiple-output support vector regression with a firefly algorithm for interval-valued stock price index forecasting. Knowl.-Based Syst. 55: 87-100 (2014), http://www.sciencedirect.com/science/article/pii/S0950705113003237
  30. ^ 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/
  31. ^ Yudong Zhang, Lenan Wu, Shuihua Wang. Solving Two-Dimensional HP model by Firefly Algorithm and Simplified Energy Function. Mathematical Problems in Engineering. 2013. doi:10.1155/2013/398141