螢火蟲算法(Firefly Algorithm)是一種啟發式算法,靈感來自於螢火蟲閃爍的行為。螢火蟲的閃光,其主要目的是作為一個信號系統,以吸引其他的螢火蟲。劍橋大學Xin-She Yang(音譯:楊新社)教授提出了螢火蟲算法,其假設為[1]

  • 螢火蟲不分性別,這樣一個螢火蟲將會吸引到所有其他的螢火蟲;
  • 吸引力與它們的亮度成正比,對於任何兩個螢火蟲,不那麼明亮的螢火蟲被吸引,因此移動到更亮的一個,然而,亮度又隨着其距離的增加而減少;
  • 如果沒有比一個給定的螢火蟲更亮的螢火蟲,它會隨機移動。

亮度應與目標函數聯繫起來。螢火蟲算法是以自然為靈感的啟發式優化算法。[2]

算法描述

編輯

螢火蟲算法的偽代碼可以概括為:

Begin
1)目标函数 
2)生成一个萤火虫的初始人口 
3)制定光照强度 ,因此,它与 
   (例如,对于最大化问题  ;
4)定义吸收系数 
while(T < MaxGeneration)
   for i =1:n(所有n萤火虫)
      for j =1:n(n萤火虫)
         if( ),
            移动萤火虫i向j;
         end if
         吸引力与距离 ;
         评估新的解决方案和更新的光强度;
      end for j
   end  for i
   排名萤火虫和找到当前最佳;
end while
处理后的结果和可视化;
end

對於任何一兩隻螢火蟲的主要更新公式  and  

 

其中 是步長參數, e  是一個向量(服從高斯或其他的分佈)。

可以證明在 的情況,FA可以簡化為 准粒子群優化(PSO).事實上,,如果內環(j)條被刪除,亮度  替換為當前的全球最佳 ,FA基本上成為標準PSO。

螢火蟲算法的變種

編輯

離散螢火蟲算法(DFA)

編輯

離散形式的螢火蟲算法(Discrete Firefly Algorithm,DFA)[3] DFA優於現有算法如蟻群算法。

對於圖像分割,基於FA-方法比Otsu的方法更為有效.[4] 同時, 離散螢火蟲算法對QAP問題,Durkota已進很好的實現行[5]

針對負荷預測中的特徵選擇問題,應用FA實現Wrapper特徵選擇算法. [6]

多目標螢火蟲算法

編輯

Apostolopoulos and Vlachos對FA進行了一個重要的多目標研究[7]。同時,Yang提出了多目標螢火蟲算法(Multiobjective Firefly Algorithm,MOFA),對連續優化問題有很好的效果[8]

拉格朗日FA

編輯

拉格朗日螢火蟲算法用來解決電力系統優化單元承諾問題[9]

混沌FA

編輯

混沌螢火蟲算法(Chaotic Firefly Algorithm,CFA)也顯示了算法的有效性[10]

混合算法

編輯

螢火蟲算法與蟻群優化算法相結合的混合算法,能夠解決金融投資組合優化 [11]

基於螢火蟲算法的 Memetic 算法

編輯

一種基於螢火蟲算法(FA)的Memetic算法(FA-MA)被用來優化支持向量機(SVR)預測模型的參數。在該FA-MA中,FA用來搜索全局解空間,而模式搜索(pattern Search) 被用來進行個體學習和局部解空間搜索。[12]

實際應用

編輯

螢火蟲算法已被應用到幾乎所有領域科學和工程,如數字圖像壓縮和圖像處理[13][14],特徵值優化[15],特徵提取和故障檢測[16][17],天線設計[18][19],工程結構設計[20], 調度和旅行商問題[21][22][23],語義組成[24],化學相平衡[25], 聚類[26],動態問題[27][28], 剛性圖像配准問題[29],參數選擇[30][12],蛋白質摺疊問題[31]等等。

參考文獻

編輯
  1. ^ Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms. Frome: Luniver Press, UK
  2. ^ 存档副本. [2013-05-18]. (原始內容存檔於2013-05-21). 
  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 (PDF). Int. J. of Industrial Engineering Computations. 2010, 1: 1–10 [2013-05-21]. (原始內容存檔 (PDF)於2013-10-13). 
  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). 存档副本 (PDF). [2013-05-21]. (原始內容 (PDF)存檔於2012-04-25). 
  6. ^ 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.
  7. ^ 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. 
  8. ^ X. S. Yang, Multiobjective firefly algorithm for continuous optimization, Engineering with Computers, vol. 29, No. 2, pp. 175-184 (2013).
  9. ^ 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).
  10. ^ 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).
  11. ^ 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).
  12. ^ 12.0 12.1 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/頁面存檔備份,存於互聯網檔案館
  13. ^ 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).
  14. ^ M.-H. Horng, vector quantization using the firefly algorithm for image compression, Expert Systems with Applications, Vol. 38, (article in press) 12 Aug. (2011).
  15. ^ 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頁面存檔備份,存於互聯網檔案館
  16. ^ H. Banati and M. Bajaj, Firefly based feature selection approach, Int. J. Computer Science Issues, vol. 8, No. 2, 473-480 (2011).
  17. ^ R. Falcon, M. Almeida and A. Nayak, Fault identification with binary adaptive fireflies in parallel and distributed systems, IEEE Congress on Evolutionary Computation, (2011).
  18. ^ 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).
  19. ^ 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)
  20. ^ 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
  21. ^ 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).
  22. ^ 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).
  23. ^ 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).
  24. ^ 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.
  25. ^ 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
  26. ^ 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
  27. ^ 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)
  28. ^ 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).
  29. ^ 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).
  30. ^ 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頁面存檔備份,存於互聯網檔案館
  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