ホタルアルゴリズムのソースを表示

'''ホタルアルゴリズム'''（[[英語|英]]: Firefly Algorithm）とは、[[数理最適化]]において Xin-She Yang によって提案された、 [[ホタル]]の発光現象をもとにした[[メタヒューリスティクス]]のひとつである<ref>{{Cite book|first=X. S.|last=Yang|title=Nature-Inspired Metaheuristic Algorithms|publisher=[[Luniver Press]]|year=2008|isbn=978-1-905986-10-1}}</ref>。

== 概要 ==
ホタルの発光は、他のホタルを引き付ける信号システムとして機能している。Xin-She Yangは、このホタルアルゴリズムを次のように仮定した: 

# すべてのホタルは性別を持たず、個々のホタルは他のすべてのホタルに引き付けられる。
# 魅力はそれらの明るさに比例し、どの2つのホタルにとっても、明るくない方はより明るい方に引き付けられ、移動する。ただし、強度（見かけ上の明るさ）は、互いの距離が大きくなるにつれて減少する。
# 与えられたホタルより明るいホタルがいなければ、そのホタルはランダムに動く。

ホタルの明るさは目的関数と関連付けられる。 

== アルゴリズム ==
ホタルアルゴリズムは[[擬似コード|疑似コード]]を用いて次のように記述される。 
 '''Begin'''
    1) 目的関数: {{nowrap|<math>f(\mathbf{x}), \quad \mathbf{x}=(x_1,x_2,...,x_d) </math>;}}
    2) ホタル {{nowrap|<math> \mathbf{x}_i \quad (i=1,2,\dots,n)</math>}}の初期状態を生成;
    3) 光の強さ ''{{mvar|I}}'' を {{nowrap|<math>f(\mathbf{x})</math>}}と関連付けられるように定義
       (例えば, 最大化問題では, {{nowrap|<math>I \propto f(\mathbf{x})</math> または単に <math>I=f(\mathbf{x})</math>;)}}
    4) 吸収係数 ''{{mvar|&gamma;}}'' を定義
  
    '''While''' (t < 世代数)
       '''for''' i = 1 : n (すべての n 匹のホタル)
          '''for''' j = 1 : i (n 匹のホタル)
             {{nowrap|'''if''' (<math>I_j>I_i </math>),}}
                {{nowrap|<math> \exp(-\gamma \; r) </math>}}によって距離 r で 魅力度 を変化
                ホタルi を ホタルj に移動;                
                新たな解を評価し、光の強さ ''{{mvar|I}}'' を更新;
             '''end if''' 
          '''end for''' j
       '''end for''' i
       ホタルを順位付けし、現在の最良のホタルを見つける
    '''end while'''
 
    結果や視覚化の後処理
 
 '''end'''
ループあたりの目的関数評価の数は、上記の擬似コードがn * nであることを示唆していても、ホタルごとに1つの評価である（Yangの[[MATLAB]]コードに基づく）。 したがって、目的関数評価の総数は（世代数）*（ホタルの数）となる。 

2つのホタル <math>\mathbf{x}_i</math>と <math>\mathbf{x}_j</math>の任意のペアの主となる更新式は、以下のように表される: 

   <math>\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 </math> 

ここで、<math>\alpha_t</math>はステップ数を制御するパラメータで、<math>\boldsymbol{\epsilon}_t</math>はガウス分布などの分布から描かれたベクトルである。 

<math>\gamma \rightarrow 0</math>である特殊なケースでは、標準的な[[粒子群最適化]]と同じである。 実際、内側のループ（jのループ）を消去し、明るさ <math>I_j</math>を現在の最適解 <math>g^*</math>に置き換えると、標準的な粒子群最適化と同じになる。 

== 問題点 ==
一般的に、自然に触発された[[メタヒューリスティクス]]は、精巧なメタファーの背後にある目新しさのなさを隠しているとして、研究界で批判を集めている。 ホタルアルゴリズムは、定着している[[粒子群最適化]]とほとんど同じであると批判されている<ref>{{Cite journal|last=Almasi|first=Omid N.|last2=Rouhani|first2=Modjtaba|year=2016|title=A new fuzzy membership assignment and model selection approach based on dynamic class centers for fuzzy SVM family using the firefly algorithm|journal=Turkish Journal of Electrical Engineering & Computer Sciences|volume=4|pages=1–19|doi=10.3906/elk-1310-253}}</ref><ref>{{Cite journal|last=Lones|first=Michael A.|year=2014|title=Metaheuristics in Nature-Inspired Algorithms|url=http://www.macs.hw.ac.uk/~ml355/common/papers/lones-gecco2014-metaheuristics.pdf|journal=[[Genetic and Evolutionary Computation Conference|GECCO '14]]|pages=1419–1422|doi=10.1145/2598394.2609841|isbn=9781450328814}}</ref><ref>{{Cite journal|last=Weyland|first=Dennis|year=2015|title=A critical analysis of the harmony search algorithm—How not to solve sudoku|journal=Operations Research Perspectives|volume=2|pages=97–105|doi=10.1016/j.orp.2015.04.001}}</ref>。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* [[群知能]]

== 外部リンク ==
* [https://www.mathworks.com/matlabcentral/fileexchange/29693-firefly-algorithm]本に含まれているMatlabプログラムファイル: Xin-She Yang, Nature-Inspired Metaheuristic Algorithms, Second Edition, Luniver Press（2010）

{{デフォルトソート:ほたるあるこりすむ}}
[[Category:自然から着想したメタヒューリスティクス]]
[[Category:郡知能]]
[[Category:アルゴリズム]]