利用者:Mklab/ホタルアルゴリズム

数学的最適化において、 ホタルアルゴリズムとは、Xin-She Yangによって提案された、 ホタルの発光現象をもとにしたメタヒューリスティクスのひとつである。

概要

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

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

ホタルの明るさは目的関数と関連する。

アルゴリズム

ホタルアルゴリズムは疑似コードを用いて次のように記述される。

Begin
   1) 目的関数: $f(\mathbf {x} ),\quad \mathbf {x} =(x_{1},x_{2},...,x_{d})$;
   2) ホタル $\mathbf {x} _{i}\quad (i=1,2,\dots ,n)$の初期状態を生成;
   3) 光の強さ I を $f(\mathbf {x} )$と関連するように定義
      (例えば, 最大化問題では, $I\propto f(\mathbf {x} )$ または単に $I=f(\mathbf {x} )$;)
   4) 吸収係数 γ を定義
 
   While (t < 世代数)
      for i = 1 : n (すべての n 匹のホタル)
         for j = 1 : i (n 匹のホタル)
            if ($I_{j}>I_{i}$),
               $\exp(-\gamma \;r)$によって距離 r で 魅力度 を変化
               ホタルi を ホタルj に移動;                
               新たな解を評価し、光の強さ I を更新;
            end if 
         end for j
      end for i
      ホタルを順位付けし、現在の最良のホタルを見つける
   end while

   結果や視覚化の後処理

end

ループあたりの目的関数評価の数は、上記の擬似コードがn * nであることを示唆していても、ホタルごとに1つの評価である。 （YangのMATLABコードに基づく。） したがって、目的関数評価の総数は（世代数）*（ホタルの数）となる。

2つのホタル$\mathbf {x} _{i}$と$\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}$はステップ数を制御するパラメータで、${\boldsymbol {\epsilon }}_{t}$はガウス分布などの分布から描かれたベクトルである。

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

問題点

一般的に、自然に触発されたメタヒューリスティクスは、精巧なメタファーの背後にある目新しさのなさを隠しているとして、研究界で批判を集めている。 ホタルアルゴリズムは、定着している粒子群最適化とほとんど同じであると批判されている。

関連項目

• 群知能

外部リンク

• [1]本に含まれているMatlabプログラムのファイル：Xin-She Yang、Nature-Inspired Metaheuristic Algorithms、Second Edition、Luniver Press、（2010）。

[[Category:メタヒューリスティクス]] [[Category:郡知能]] [[Category:アルゴリズム]] [[Category:未査読の翻訳があるページ]]