母集団最適化アルゴリズム：ホタルアルゴリズム(FA)

内容

1.はじめに
2.アルゴリズムの説明
3.テスト結果

1.はじめに

自然は常に多くのメタヒューリスティックアルゴリズムにインスピレーションを与えてきました。また、問題解決のために、個々の経験をもとに、指示されることなく解決策を見出すことができました。初期のメタヒューリスティックアルゴリズム創出の主な動機は自然淘汰と適者生存でした。自然界では、動物たちはさまざまな方法でコミュニケーションをとっています。ホタルは点滅する能力を使ってコミュニケーションをとります。ホタルの種類は約2000種あり、それぞれ特殊な発光パターンを持っています。通常、特定のパターンで短く閃光します。光とその強さは、生物発光と呼ばれる生化学的なプロセスの結果となります。このような閃光の主な機能は、交尾のパターンと潜在的な犠牲者を引き寄せることだと考えられています。熱帯地方のホタルの中には、閃光を同期させることができるものがあり、生物の自己組織化の一例を示しています。光の強さは光源からの距離の関数として逆二乗則に従うので、ホタルから出る光が明滅すると、その光が見える範囲で周囲のホタルが反応するのです。

ホタルの行動にヒントを得た集団最適化アルゴリズムには、ホタルアルゴリズムとGSO (Glowworm Swarm Optimization)アルゴリズムという2つのバリエーションがあります。ホタルとGlowworm（ツチボタル）の大きな違いは、後者には翅がないことです。今回は、1つ目のタイプの最適化アルゴリズムについて考えてみます。

2.アルゴリズムの説明

ホタルアルゴリズム(F-algorithm)は、2007年に英国ケンブリッジ大学のX-Sh. Yangによって提案され、すぐに最適化研究者の注目を集めました。ホタルアルゴリズムは、近年、最適化問題の解決に目覚ましい成果を上げている群知能アルゴリズム群の1つです。特にホタルアルゴリズムは、連続離散最適化問題の解法として利用されています。

ホタルアルゴリズムには、実際のホタルの明滅の特徴に基づいた3つのルールがあります。ルールは次のとおりです。

1. すべてのホタルは、より魅力的で明るい相手に向かっていく。
2. ホタルの魅力度は明るさに比例し、他のホタルとの距離が離れると、空気が光を吸収するため、明るさが減少する。そのため、明滅している2つのホタルのうち、明るくないほうが明るいほうに寄っていく。より明るい（より魅力的な）相手がいない場合、ホタルはランダムに移動する。
3. ホタルの明るさや光量は、問題の目的関数の値で決まる。

アルゴリズム開始当初は、すべてのホタルが探索空間全体にランダムに散らばっています。そして、このアルゴリズムは、2つのフェーズに基づいて最適なパーティションを決定します。

1. 光の強さの変化 - 現在位置のホタルの明るさが適応度の値に反映され、魅力的なホタルに向かって移動する。
2. ホタルは、隣のホタルの光量を観察して位置を変える。

ここで、ホタル最適化の複雑な仕組みについて、より詳しく掘り下げてみましょう。そのアルゴリズムのエッセンスを図1にわかりやすく示します。

図1：探索空間におけるホタルの光 - 距離が離れると視認性が低下する

探索原理の主な考え方は、ホタル同士の距離が長くなると視認性が非線形に低下するということです。この非線形関係がなければ、各ホタルは決定論的に明るい光源に向かって移動することになります。ただし、図1にあるように、ホタルの光は環境に吸収されて目立たないため、最も明るい親類を選ぶことはありません。その代わりに、より暗い相手（ただし、その環境では最も明るい相手）を選びます。この特徴は、より小さな群に分割するアルゴリズムの優れた能力を説明するものです。これは、距離による光の吸収の非線形関数によってのみ自然に発生するものです。下の図2には、アルゴリズムのパラメータの1つであるγ（ガンマ）媒体の吸収係数値を変えた場合の、距離に対する視認性の関数が示されています。

図2：距離f(x)からの媒体の透明度を表す関数（γ透明度係数はそれぞれ1.0, 0.2, 0.05, 0.01）

γが無限大に近づくと環境は不透明になります。γがゼロになると環境は完全に透明になり、各ホタルは探索空間内のどの距離でも相手を見ることができるようになります。γ = 0.0の場合はどうなるのでしょうか。すべてのホタルは、ある最適でない地点に収束する最も明るい相対的な場所に飛ぶことになります。そのため、アルゴリズムは極値から抜け出せず、収束しません。環境が完全に不透明な場合はどうなるのでしょうか。ホタルは、自分より魅力的な個体を見ることはありません。このアルゴリズムの作者が提唱した概念によると、自分より優れた個体がいないことで、ホタルはランダムに動くようになります。アルゴリズムはランダム探索に縮退してしまいます。アルゴリズム分類の評価表では、ランダム検索アルゴリズムは最下位になっています。 

さらにアルゴリズムの解析を掘り下げ、ホタルの動きを表す方程式を考えてみましょう。いわゆる魅力度指数の算出には、視認性対距離の関数が用いられます。

ここで
attractiveness - 自明
γ - 環境不透明度係数
distance - ホタル間のユークリッド距離
fireflies [k].f - k番目のホタルの光度

この式から、魅力度関数は問題の次元と距離値の限界に直接依存することが明らかです。アルゴリズムの著者は特定の最適化問題に対して透明度係数を選択することを推奨しています。事前にアルゴリズムの挙動がわからない状態でそれをおこなうのは不便で時間もかかるので、0から20の範囲で距離の値を正規化することが必要だと考えています。そのために、他のアルゴリズムで繰り返し使ってきたScale()関数を適用します。魅力度計算前の「距離」の変換は次のようになります。

ここで

maxDist - すべてのホタルの組の中での最大ユークリッド距離

この場合、ホタルの魅力は問題の次元に依存しないので、特定の最適化問題に対してγ係数を選択する必要はありません。魅力関数とは、各ホタルがどのような仲間を選択するかを決めるものです。この選択は厳しく決められています。ホタル同士の魅力の影響で、アルゴリズムの2つ目のパラメータであるβ（ベータ）係数が決まります。対応する反復ごとにホテルの選択があらかじめ決まっている場合、アルゴリズムの探索能力はどのように確保されるのでしょうか。そのために、ランダムなベクトル成分とアルゴリズムの第3パラメータ(α)を導入しています。ホタルの複雑な行動関係は、こんな感じでしょうか。

ここで
fireflies [i].c [c] - i番目のホタルのc番目の座標
β - ホタル誘引影響係数
α - ホテルを動かすときのランダム要素に影響する係数で、移動目標からのずれを与える
r - 範囲 [-1.0;1.0] の乱数
v[c] - c番目の座標による探索範囲の極限点間の距離を特徴付けるベクトル成分
Хj - 対になったホタルの対応する座標で、移動先となるもの
Xi - 移動が計算されるホタルの対応する座標

さて、いよいよアルゴリズムのコードを記述していきます。比較的シンプルです。もう少し詳しく考えてみましょう。

//——————————————————————————————————————————————————————————————————————————————
struct S_Firefly
{
  double c  []; //coordinates
  double f;     //the value of the fitness function
};
//——————————————————————————————————————————————————————————————————————————————

S_Attractiveness構造体は、魅力度と対応するホタルの数をペアとして格納するためのものです。各ホタルは、最も魅力的なホタルの座標に向かって移動するのではなく、パートナーがすでに移動した座標に向かって移動します。著者が説明したアルゴリズムのバージョンとは若干のズレがありますが、この方がうまくいくのです。

//——————————————————————————————————————————————————————————————————————————————
struct S_Attractiveness
{
  double a; //attractiveness
  int    i; //index of the most attractive firefly
};
//——————————————————————————————————————————————————————————————————————————————

ホタルアルゴリズムについては、C_AO_FAクラスを使用して記述しています。ここには3つのpublicメソッドがあり、1つは初期化用のInit()、2つは反復毎に呼び出す必要のあるFlight()とLuminosity()です。Privateヘルパーメソッドとパラメータ定数を保存するためのメンバーがあります。

//——————————————————————————————————————————————————————————————————————————————
class C_AO_FA
{
  //----------------------------------------------------------------------------
  public: S_Firefly fireflies []; //fireflies
  public: double    rangeMax  []; //maximum search range
  public: double    rangeMin  []; //minimum search range
  public: double    rangeStep []; //step search
  public: double    cB        []; //best coordinates
  public: double    fB;           //FF of the best coordinates

  public: void Init (const int    paramsP,  //number of opt. parameters
                     const int    sizeP,    //swarm size
                     const double alphaP,   //alpha, randomness in motion
                     const double betaP,    //beta, effect of attractiveness
                     const double gammaP);  //gamma, transparency of the environment

  public: void Flight ();
  public: void Luminosity ();

  //----------------------------------------------------------------------------
  private: S_Attractiveness att [];
  private: int    swarmSize;
  private: int    params;
  private: double maxDist;
  private: double v [];

  private: double alpha;      //randomness in motion
  private: double beta;       //effect of attractiveness
  private: double gamma;      //transparency of the environment
  private: bool   luminosity;

  private: double SeInDiSp  (double In, double inMin, double inMax, double step);
  private: double RNDfromCI (double min, double max);
  protected: double Scale   (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers);
};
//——————————————————————————————————————————————————————————————————————————————

Init() publicメソッドは、初期化に使用され、各最適化の開始前に呼び出される必要があります。そのパラメータは、アルゴリズムの上部構造パラメータです。このメソッドは、配列のためのメモリを割り当て、グローバルおよび個々のホタルの光度値をリセットします。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FA::Init (const int    paramsP, //number of opt. parameters
                    const int    sizeP,   //swarm size
                    const double alphaP,  //alpha, randomness in motion
                    const double betaP,   //beta, effect of attractiveness
                    const double gammaP)  //gamma, transparency of the environment
{
  fB = -DBL_MAX;

  params    = paramsP;
  swarmSize = sizeP;
  alpha     = alphaP;
  beta      = betaP;
  gamma     = gammaP;

  ArrayResize (rangeMax,  params);
  ArrayResize (rangeMin,  params);
  ArrayResize (rangeStep, params);
  ArrayResize (v,         params);
  ArrayResize (att,       swarmSize);

  luminosity = false;

  ArrayResize (fireflies, swarmSize);

  for (int i = 0; i < swarmSize; i++)
  {
    ArrayResize (fireflies [i].c,  params);
    fireflies [i].f = -DBL_MAX;
  }

  ArrayResize (cB, params);
}
//——————————————————————————————————————————————————————————————————————————————

各反復で呼び出される最初のpublicメソッド、Flight()を考えてみましょう。アルゴリズムの主要なロジックはこの方式に集約されているので、より詳細に検討する必要があります。luminosity変数は、アルゴリズムが最初の反復で実行されているか、その後の反復で実行されているかを判断するためのフラグとして機能します。フラグが設定されていない場合は、一様分布に従ってホタルを座標空間内にランダムに分布させる必要があります。この動作に伴い、各座標に変位ベクトルを設定し、直ちにホタル間に存在しうる最大ユークリッド距離を計算します（すでに述べたように、これは環境透明度係数の問題次元への依存を避けるために、ホタル間の距離を正規化するために必要なことです）。これらの操作の後、luminosityフラグを有効にします。

if (!luminosity)
{
  fB = -DBL_MAX;

  //--------------------------------------------------------------------------
  double summCoordinates = 0.0;
  for (int c = 0; c < params; c++)
  {
    v [c] = rangeMax [c] - rangeMin [c];
    summCoordinates += pow (v [c], 2.0);
  }
  maxDist = pow (summCoordinates, 0.5);

  //--------------------------------------------------------------------------
  for (int s = 0; s < swarmSize; s++)
  {
    for (int k = 0; k < params; k++)
    {
      fireflies [s].c  [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      fireflies [s].c  [k] = SeInDiSp (fireflies [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    }
  }

  luminosity = true;
}

1回目の反復でランダムに分布したホタルが光り始めた（それに対して適応度関数を計算した）あと、2回目以降の反復から、各ホタルの魅力度を計算することができます。そのためには、考えられるすべてのホタルのペアの間のユークリッド距離を計算する必要があります。これには単に、座標の差の二乗を足して、その和から根を求めます。算出された距離は、魅力度計算式に使用されます。こうして、各ホタルの唯一可能なペアを得ます。すべてのホタルの中で最大輝度を決定します。これは、ペアを見つけることができず、単独で空間を彷徨うことになる最も明るいホタルを決定するために必要なことです。まあ、おそらく、次の反復ではもっと運が良くなるのでしょう。

//measure the distance between all------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  att [i].a = -DBL_MAX;

  for (int k = 0; k < swarmSize; k++)
  {
    if (i == k) continue;

    summCoordinates = 0.0;
    for (int c = 0; c < params; c++) summCoordinates += pow (fireflies [i].c [c] - fireflies [k].c [c], 2.0);

    distance = pow (summCoordinates, 0.5);
    distance = Scale (distance, 0.0, maxDist, 0.0, 20.0, false);
    attractiveness = fireflies [k].f / (1.0 + gamma * distance * distance);

    if (attractiveness > att [i].a)
    {
      att [i].a = attractiveness;
      att [i].i = k;
    }

    if (fireflies [i].f > maxF) maxF = fireflies [i].f;
  }
}

Flight()メソッドのコードのこの部分は、ホタルの飛行を担当します。光度が他よりも大きい不幸なホタルの場合、計算方法が多少異なります。移動ベクトルに乱数[-1.0;1.0]を乗じたα係数を介して現在位置に加算しています。理論的には、アルゴリズムにおいて、これは最適解追加学習として機能して、さらなる改善を期待できますが、後で見るように、このテクニックは役に立たないことが判明します。現段階では、古典版のアルゴリズムを考察します。

それ以外のホタルではすでにペアが見つかっており、ランダムな要素（先ほども書きました）を加えて、該当するペアに移動する計算となります。

//flight--------------------------------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  if (fireflies [i].f >= maxF)
  {
    for (int c = 0; c < params; c++)
    {
      r  = RNDfromCI (-1.0, 1.0);
      fireflies [i].c [c] = fireflies [i].c [c] + alpha * r * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); 
    }
  }
  else
  {
    for (int c = 0; c < params; c++)
    {
      r  = RNDfromCI (-1.0, 1.0);
      Xi = fireflies [i].c [c];
      Xj = fireflies [att [i].i].c [c];
      fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

次は、反復毎に呼び出されるシンプルなpublicメソッドです。ここでは、最適解を更新します。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FA::Luminosity ()
{
  for (int i = 0; i < swarmSize; i++)
  {
    if (fireflies [i].f > fB)
    {
      fB = fireflies [i].f;
      ArrayCopy (cB, fireflies [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

では、テストに移りましょう。テスト関数にアルゴリズムを適用した結果を見てみましょう。

その結果は、控えめに言っても印象が悪いものです。このアルゴリズムは、個々のテストにおいて、PSO、FSS、GWOよりもわずかに優れているに過ぎません。しかし、総合評価指標では、ランダム検索アルゴリズムを差し置いて下から2番目の位置にいます。そこで、テストにおける推定指標の算出方法を見直すという発想が生まれました。次の記事では、より便利な評価計算方式に切り替えます。そして、今回の記事では、最終結果のヒストグラムを追加する予定です。個々のアルゴリズム間の性能比を明確に示すことができるようになります。

古典的なホタルアルゴリズムは簡単に実装できますが、多峰性の問題では収束が遅く、極限の罠に陥りやすいという研究結果が出ています。また、現在の反復処理にパラメータ的に依存する係数を欠いています。そこで、この研究の目的の1つは、標準的なホタルアルゴリズムを改良して、その性能を向上させることでした。

アルゴリズムの考え方そのものが非常に独創的で、すべてをそのままにして、その特性を改善しようとしないのは残念なことです。そこで、ランダムな要素をレヴィ飛行に置き換えて、アルゴリズムの修正を試みました。レヴィ飛行はすべてのアルゴリズムの検索能力を向上させることはできません。カッコー検索アルゴリズムを検討した後、この手法で他のアルゴリズムも改良してみましたが、期待通りの結果は得られませんでした。どうやら、これを補完するアルゴリズム内の内部検索戦略と何らかの形で整合性がとれている必要があるようです。この特定の場合には、「レヴィ飛行」を適用することで、アルゴリズムの能力が飛躍的に向上するという顕著な効果が得られました。これについては、テスト結果に関する部分でお話します。

以下は、その変更をおこなったコードの部分です。まず、古典版では、最も輝度の高いホタルが現在位置からランダムな方向に移動します。そして、最適なホタルが最適な大局的位置から移動し、現在位置ではなく、解全体を改善しようとするのです。最適解の座標に、移動ベクトルを考慮したレヴィ飛行分布（尾が重い分布）の乱数を同じα係数で追加します。これによって、本当に近傍を絞り込むことで全体解の座標を向上させることが可能になったのです。

このように、レヴィ飛行のランダム性を調整したとはいえ、他のホタルの挙動も同じ古典的な法則に従うようになりました。これがアルゴリズムに施された修正のすべてです。

//flight--------------------------------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  if (fireflies [i].f >= maxF)
  {
    for (int c = 0; c < params; c++)
    {
      r1 = RNDfromCI (0.0, 1.0);
      r1 = r1 > 0.5 ? 1.0 : -1.0;
      r2 = RNDfromCI (1.0, 20.0);

      fireflies [i].c [c] = cB [c] + alpha * r1 * pow (r2, -2.0) * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
  else
  {
    for (int c = 0; c < params; c++)
    {
      r1 = RNDfromCI (0.0, 1.0);
      r1 = r1 > 0.5 ? 1.0 : -1.0;
      r2 = RNDfromCI (1.0, 20.0);

      Xi = fireflies [i].c [c];
      Xj = fireflies [att [i].i].c [c];

      fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r1 * pow (r2, -2.0) * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

図3はレヴィ飛行関数図です。関数式の指数はアルゴリズムの動作にどのような影響を与えるのでしょうか。私の研究によると、次数が高くなると、短いジャンプに比べて長い（尾が重い）ジャンプの数が減り、最適解の近傍で座標を絞り込むアルゴリズムの能力が向上します。長いジャンプが少ないため、極値で行き詰まる確率が高くなります。この効果は離散関数を研究するときに顕著になりますが、滑らかな関数の場合はそれほど顕著にはならありません。逆に指数を小さくすると長いジャンプの回数が増えて、アルゴリズムの探索能力は向上するが収束精度は悪化するので、精度と探索の中間が必要です。その上、最適化問題によって異なることもあります。

図3：レヴィ飛行関数、度数0.5...3.0 

それでは、修正版のアルゴリズムをテストスタンドで試した結果に移ります。以下では、古典版と比較して、どれだけ性能が向上したかをご覧いただけます。

ご覧のように、修正したアルゴリズムはより良い結果を示すだけでなく、評価表でトップの座を獲得しています。次節で、その結果を詳しく見ていきましょう。以下は、テストスタンドに設置された修正版アルゴリズムのアニメーションです。

  Skinテスト関数のFAm

  Forestテスト関数のFAm

  Megacityテスト関数のFAm

3.テスト結果

今回から、テスト時に最も良いアルゴリズムが100点、最も悪いアルゴリズムが1点という条件付きのヒストグラムを公開することにしました。評価表でのアルゴリズムの最終結果のスケールが明確に分かるので、視覚的に最も便利な表示方法だと思います。ここで、ランダムアルゴリズムがリーダーにどれだけ遅れをとっているかを見ることができます。

評価alt

図4：テストアルゴリズムの最終結果のヒストグラム

覚えていらっしゃるかもしれませんが、メタヒューリスティックアルゴリズムとは、最適化問題を解くための近似的な手法で、その探索エンジンに合理的な仮定によるランダム性の特性を利用し、ランダムに生成した有効解の集合から反復して解空間を調査し利用することで解の質を向上させようとするものです。これらのアルゴリズムは最適であることを保証するものではありませんが、合理的で受け入れ可能な解を与えることがテストされています。また、問題の挙動に大きく影響されないという利点もあり、多くのタスクで活躍することができます。多くの利用可能なアルゴリズムが存在するため、問題の挙動に応じて適切なものを選択して解くことが可能です。

進化的アルゴリズムの登場以来、ヒューリスティックアルゴリズムに関する研究が盛んにおこなわれています。新しいアルゴリズムの実装は、主要な研究分野の1つです。現在、40以上のメタヒューリスティックアルゴリズムが存在します。その多くは、自然界のシナリオをシミュレートして作られたものです。

「賛成」と「反対」は、ホタルアルゴリズムの修正版(FAm)についてです。

各記事には、過去の記事のアルゴリズムコードを最新版に更新したアーカイブが用意されています。それぞれの新しい記事は、著者の個人的な経験の蓄積であり、結論と判断は、この目的のために開発された特別なテストスタンドでおこなわれた実験に基づいています。