[アーティクル]
08/26/2015

June 2015

Volume 30 Number 6

テストの実行 - Firefly Algorithm 最適化

James McCaffrey 機械学習では、多くの場合、数値最適化アルゴリズムを使用して、計測誤差を最小限に抑える変数の値の組み合わせを見つけます。この変数を通常重みと呼びます。たとえば、ロジスティック回帰分類では、n 個の予測変数がある場合に、n+1 個の重みの値を決定しなければならない数学方程式を使用します。この重み値を決定するプロセスをモデルのトレーニングと呼びます。考え方としては、正しいことがわかっている出力値を持つトレーニングデータのコレクションを使用します。誤差 (計算出力値と正しい出力値の差) を最小限に抑える重み値を見つけるために使用するのが最適化アルゴリズムです。

最適化には多種多様なアルゴリズムがありますが、今回は Firefly Algorithm (FA) 最適化という比較的新しい手法 (2009 年に初めて発表) を取り上げます。FA 最適化とは、ホタルの群れの動きを大まかにモデル化するものです。

FA 最適化の考え方と今回の目標を理解するには、図 1 のデモプログラムをご覧いただくのが一番です。このデモプログラムの目標は、FA 最適化を使用して、5 個の入力値から Michalewicz 関数の最小値を見つけることです。Michalewicz 関数とは、数値最適化アルゴリズムの効果を評価するために使用する標準ベンチマークです。5 個の入力値を使うこの関数は、x = (2.2029 1.5707, 1.2850, 1.9231, 1.7205) の場合に最小値 z = -4.6877 になります。

図 1. 実行中の FA 最適化

Michalewicz 関数は、複数の局所最小値と複数の扁平領域 (すべての z 値がほぼ等しくなる領域) があるため、ほとんどの最適化アルゴリズムにとって難しい関数です。5 個の入力値を使用する Michalewicz 関数を視覚化するのは簡単ではありませんが、2 個の入力値を使用した場合のグラフを調べると、この関数の特性を把握できます (図 2 参照)。グラフの下に、この関数の数式を示しています。

図 2. 2 つの変数を用いる Michalewicz 関数

デモプログラムでは、ホタルの数を 40 匹に設定します。各ホタルは、最小化問題の解の候補を表す仮想的な位置を持ちます。ホタルの数を増やすほど、真の最適解が見つかる可能性が高まりますが、パフォーマンスは低下します。FA 最適化では、15 ～ 40 匹のホタルを使用するのが一般的です。

デモでは、5 個の入力値があるため、問題の次元数を 5 に設定します。FA は反復プロセスなので、ループカウンターの最大値が必要です。機械学習での最適化のループカウンター変数は、多くの場合、エポック (epoch) と呼ばれます。今回のデモでは最大反復回数を 1,000 回に設定しています。最大反復回数は問題によって異なりますが、1,000 は開始値として妥当です。FA には確率的要素があり、デモでは、乱数ジェネレーターのシード値を任意値の 0 に設定しています。

図 1 の実行中のデモでは、100 エポックごとに、そこまでに見つかった最適位置に関連付けられる最適 (最小) 誤差を表示しています。アルゴリズムの完了後、すべてのホタルで見つかった最適位置は x = (2.2033, 1.5711, 1.2793, 1.1134, 2.2216) です。この解は、x = (2.2029 1.5707, 1.2850, 1.9231, 1.7205) の最適解に近い値になりましたが、正確に一致していません。FA によって見つけられた解における Michalewicz 関数の値は -4.45 であり、真の最小値 -4.69 に近い値です。この FA 解の誤差は 0.0561 です。

今回は、少なくとも中級レベルのプログラミングスキルがあることを前提としますが、数値最適化または Firefly Algorithm の知識は問いません。デモプログラムは C# を使用してコーディングしていますが、コードを JavaScript や Python などの別の言語にリファクタリングしても大きな問題は起きません。

スペースを節約するために少し編集した完全なデモコードを、このコラムに示しています。デモコードは、本稿付随のコードダウンロードから入手することもできます。また、コードを小さく抑え、中心となる考え方を可能な限り明瞭にするため、通常のエラーチェックはすべて削除しています。

プログラムの全体構造

プログラムの全体構造を図 3 に示します。今回のデモを作成するには、Visual Studio を起動して、FireflyAlgorithm という名前で新しい C# コンソールアプリケーションを作成します。デモは、Microsoft .NET Framework との大きな依存関係はないので、新しいバージョンの Visual Studio であれば動作します。

図 3. Firefly デモプログラムの構造

using System;
namespace FireflyAlgorithm
{
  class FireflyProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin firefly demo");
      // Code here
      Console.WriteLine("End firefly demo");
      Console.ReadLine();
    }
    static void ShowVector(double[] v, int dec, bool nl)
    {
      for (int i = 0; i < v.Length; ++i)
        Console.Write(v[i].ToString("F" + dec) + " ");
      if (nl == true)
        Console.WriteLine("");
    }
    static double[] Solve(int numFireflies, int dim,
      int seed, int maxEpochs) { . . }
    static double Distance(double[] posA,
      double[] posB) { . . }
    static double Michalewicz(double[] xValues) { . . }
    static double Error(double[] xValues) { . . }
  } // Program
  public class Firefly : IComparable<Firefly>
  {
    // Defined here
  }
}

テンプレートコードが Visual Studio エディターに読み込まれたら、内容がよくわかるようにソリューションエクスプローラーウィンドウで Program.cs の名前を「FireflyProgram.cs」に変更します。これにより、Visual Studio が自動的に Program クラスの名前を変更します。ソースコードの先頭で、不要な using ステートメントをすべて削除し、System への参照のみを残します。

このデモは、完全なオブジェクト指向プログラミングのアプローチではなく、主に静的メソッドの手法を使用してコーディングしています。デモでは、すべての制御ロジックを Main メソッドに配置しています。Main メソッドでは、まず、デモの目的を表示します。

Console.WriteLine("Goal is to solve the Michalewicz benchmark function");
Console.WriteLine("The function has a known minimum value of -4.687658");
Console.WriteLine("x = 2.2029 1.5707 1.2850 1.9231 1.7205");

次に、FA に必要なパラメーターを設定します。

int numFireflies = 40;
int dim = 5;
int maxEpochs = 1000;
int seed = 0;

このパラメーターの値を、以下のステートメントで表示します。

Console.WriteLine("Setting numFireflies = " + numFireflies);
Console.WriteLine("Setting problem dim = " + dim);
Console.WriteLine("Setting maxEpochs = " + maxEpochs);
Console.WriteLine("Setting initialization seed = " + seed);

そして、FA を、以下のように呼び出します。

Console.WriteLine("Starting firefly algorithm");
double[] bestPosition = Solve(numFireflies, dim, seed, maxEpochs);
Console.WriteLine("Finished");

Main メソッドは、FA の結果を表示して終了します。

Console.WriteLine("Best solution found: ");
Console.Write("x = ");
ShowVector(bestPosition, 4, true);
double z = Michalewicz(bestPosition);
Console.Write("Value of function at best position = ");
Console.WriteLine(z.ToString("F6"));
double error = Error(bestPosition);
Console.Write("Error at best position = ");
Console.WriteLine(error.ToString("F4"));

FA は、規範的なアルゴリズムというよりも、メタヒューリスティックなアルゴリズムです。つまり、FA とは、多くのさまざまな種類の最適化問題に適応できる一連の設計ガイドラインです。

FA について

今回紹介する FA は、Xin-She Yang による 2009 年の研究論文「Firefly Algorithms for Multimodal Optimization」(マルチモーダル最適化のための Firefly Algorithms、英語) に基づきます。この FA のプロセスを、図 4 のグラフで示します。このグラフは簡略したダミーの最小化問題を表し、入力値は X と Y の 2 つだけです。グローバルな最小値は X = 0 かつ Y = 0 の位置です。ここには 3 匹のホタルがいます。firefly[0] は点 (2, 1) にいるため、正解の最も近くにいます。firefly[1] は点 (-4, -4) にいます。firefly[2] は点 (-8, 8) にいて、正解から最も遠くにいます。

図 4. Firefly Algorithm

実際のホタルは、おそらくメスを引き付けるために生物発光を利用して発光する虫で、空中を飛び回ります。それぞれのホタルが発光する明るさは異なります。FA では、正解に近いホタルは、誤差が小さいことから、より明るく発光します。図 4 では、firefly[0] が最も明るく、firefly[1] は中程度、firefly[2] は最も暗い光を放ちます。

FA の基本的な考え方は、ホタルは自分よりも明るい別のホタルに引き寄せられます。引き寄せられる力 (自分よりも明るいホタルへの移動距離) は、2 匹のホタルが近くにいるほど強くなります。図 4 では、firefly[0] は自分が最も明るいため移動しません。firefly[1] と firefly[2] はどちらも firefly[0] に引き寄せられ、そちらの方向へ移動します。firefly[1] は firefly[2] よりも firefly[0] に近いため、firefly[1] は firefly[2] よりも長い距離を移動します。

FA を非常に大まかな擬似コードで表すと、図 5 に示すようになります。一見、アルゴリズムはかなり簡単そうに思えますが、コードの実装を見ると分かるようにかなり複雑です。

最初の大きな問題は、ホタルの明るさの定義です。FA はメタヒューリスティックなアルゴリズムなので、正解に近いほど明るくなるようにすれば自由に定義してかまいません。次に大きな問題は、引き寄せる力の定義です。自分よりも明るいホタルへの移動距離は、近いホタルほど大きくなるようにします。

図 5 Firefly Algorithm

initialize n fireflies to random positions
loop maxEpochs times
  for i := 0 to n-1
    for j := 0 to n-1
      if intensity(i) < intensity(j)
        compute attractiveness
        move firefly(i) toward firefly(j)
        update firefly(i) intensity
      end for
    end for
  sort fireflies
end loop
return best position found

FA の実装

Solve メソッドの定義は以下のように始めます。

static double[] Solve(int numFireflies, int dim, int seed, int maxEpochs)
{
  Random rnd = new Random(seed);
  double minX = 0.0;
  double maxX = 3.2;
  double B0 = 1.0;
  double g = 1.0;
  double a = 0.20;
  int displayInterval = maxEpochs / 10;
...

ローカル変数 minX と maxX は、各ホタルの位置の境界を確立します。ここで使用する値 0.0 と 3.2 (円周率の近似値) は、Michalewicz 関数固有の値です。正規化したデータを使用する機械学習の最適化では、値 -10.0 と +10.0 が一般的な境界です。

ローカル変数 B0 (基本ベータ)、g (ガンマ)、および a (アルファ) は、あるホタルが別のホタルを引き寄せる力を制御します。使用する値 (1.0、1.0、0.20) は、引用した研究論文の推奨値です。ローカル変数 displayInterval は、進捗メッセージを表示する頻度を制御します。

次に、空のホタルの群れを作成します。

double bestError = double.MaxValue;
double[] bestPosition = new double[dim]; // Best ever
Firefly[] swarm = new Firefly[numFireflies]; // All null

Firefly オブジェクトはプログラムで定義したオブジェクトで、ホタルの位置、関連誤差、および明るさをカプセル化します。最初、すべてのホタルは null オブジェクトです。Firefly クラスの定義は、後ほど示します。次に、swarm のインスタンスを作成し、ランダムな位置に配置します。ホタルごとに、Firefly コンストラクターを呼び出します。

for (int i = 0; i < numFireflies; ++i)
{
  swarm[i] = new Firefly(dim);
  for (int k = 0; k < dim; ++k) // Random position
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
...

コンストラクターは、暗黙のうちに位置を (0.0, 0.0, 0.0, 0.0, 0.0) に設定し、関連誤差と明るさをダミー値の 0.0 に設定します。position 配列の各コンポーネントは、minX と maxX (0.0 と 3.2) 間のランダムな値に設定します。次に、現在のホタルの誤差と明るさを計算します。

swarm[i].error = Error(swarm[i].position);
  swarm[i].intensity = 1 / (swarm[i].error + 1);
...

Error 関数についてはこの後示します。ここでは、ホタルの明るさを誤差の逆数になるように定義します。そのため、誤差の小さなホタルほど明るくなり、誤差の大きいホタルほど明るさが抑えられます。分母に 1 を加えているのは、誤差が 0 の場合の 0 除算を避けるためです。初期化の最後に、新しく作成したホタルをチェックして最適な位置をかどうかを確認します。

...
  if (swarm[i].error < bestError)
  {
    bestError = swarm[i].error;
    for (int k = 0; k < dim; ++k)
      bestPosition[k] = swarm[i].position[k];
  }
} // For each firefly

メイン処理のループは、以下のステートメントから始まります。

int epoch = 0;
while (epoch < maxEpochs)
{
  if (epoch % displayInterval == 0 && epoch < maxEpochs)
  {
    string sEpoch = epoch.ToString().PadLeft(6);
    Console.Write("epoch = " + sEpoch);
    Console.WriteLine(" error = " + bestError.ToString("F14"));
  }
...

反復回数を固定する代わりに、bestError 値が小さなしきい値 (一般的には 0.00001) を下回った場合に反復を中断してもかまいません。各ホタルを、入れ子にした for ループを使用して別のホタルと比較します。

for (int i = 0; i < numFireflies; ++i) // Each firefly
{
  for (int j = 0; j < numFireflies; ++j) // Others
  {
    if (swarm[i].intensity < swarm[j].intensity)
    {
      // Move firefly(i) toward firefly(j)
...

各 for ループのインデックスは 0 から始まるため、ホタルの各ペアは while ループの各反復で 2 回比較されます。自分よりも明るい別のホタル方向に移動するには、まず、引き寄せる力を計算する必要があります。

double r = Distance(swarm[i].position, swarm[j].position);
double beta = B0 * Math.Exp(-g * r * r);
...

変数 beta は引き寄せる力を定義し、この後 firefly[i] を移動するために使用します。その値は、fireflies [i] と [j] 間の距離の 2 乗になります。この距離は、ヘルパーメソッド Distance を使用して計算します。メソッド Distance は、2 つの位置の間のユークリッド距離を返します。たとえば、firefly[i] が 2 次元空間の点 (3.0, 4.0) にあり、firefly[j] が点 (5.0, 9.0) にあるとすると、2 点間の距離は sqrt((5 - 3)^2 + (9 - 4)^2) = sqrt(4 + 25) = sqrt(29) = 5.4 です。beta は距離の 2 乗値を使用します。これは平方根演算の逆数になります。そのため、別の距離尺度を使用することにした場合、beta の計算は簡潔になりますが、柔軟性は損なわれます。

実際の動きは、以下のステートメントを使用して実現します。

for (int k = 0; k < dim; ++k)
{
  swarm[i].position[k] += beta *
    (swarm[j].position[k] - swarm[i].position[k]);
  swarm[i].position[k] += a * (rnd.NextDouble() - 0.5);
  if (swarm[i].position[k] < minX)
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
  if (swarm[i].position[k] > maxX)
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
}
...

firefly[i] の位置の k 番目のコンポーネントは、firefly[j] への firefly[i] と firefly[j] 間の距離のベータ分だけ移動されます。小さなランダムな項を、各 k 番目の位置コンポーネントに加算します。これは、アルゴリズムが最適化されていない解にとどまることを防ぐことの役立ちます。各位置コンポーネントをチェックして範囲外にあるかどうかを確認し、範囲外にある場合は、範囲内に収まるランダムな値を代入します。

入れ子になったループの移動コードは、移動したばかりのホタルの誤差と明るさを更新して終了します。

swarm[i].error = Error(swarm[i].position);
      swarm[i].intensity = 1 / (swarm[i].error + 1);
    } // If firefly(i) < firefly(j)
  } // j
} // i each firefly
...

Solve メソッドは、以下のステートメントで終了します。

...
   Array.Sort(swarm); // low error to high
    if (swarm[0].error < bestError)
    {
      bestError = swarm[0].error;
      for (int k = 0; k < dim; ++k)
        bestPosition[k] = swarm[0].position[k];
    }
    ++epoch;
  } // While
  return bestPosition;
} // Solve

各ホタルのペアを比較し、明るさの低いホタルをより明るいホタルの方向に移動した後、一番小さな誤差のホタルが swarm[0] になるように、Firefly オブジェクトの配列を誤差低から高へと並べ替えます。このオブジェクトをチェックして新しい最適解が見つかるかどうかを確認します。Firefly オブジェクトの並べ替えには、while ループを経由するたびにオブジェクトが異なる順序で処理されるように、配列内のオブジェクトの位置を変更するという重要な効果もあります。

ヘルパーメソッド

メソッド Solve は、ヘルパーメソッド Distance と Error を呼び出します。これらのヘルパーメソッドが続いて Michalewicz を呼び出します。ヘルパーメソッド Distance は次のように定義します。

static double Distance(double[] posA, double[] posB)
{
  double ssd = 0.0; // sum squared diffrences
  for (int i = 0; i < posA.Length; ++i)
    ssd += (posA[i] - posB[i]) * (posA[i] - posB[i]);
  return Math.Sqrt(ssd);
}

ヘルパーメソッド Michalewicz は次のように定義します。

static double Michalewicz(double[] xValues)
{
  double result = 0.0;
  for (int i = 0; i < xValues.Length; ++i) {
    double a = Math.Sin(xValues[i]);
    double b = Math.Sin(((i+1) * xValues[i] * xValues[i]) / Math.PI);
    double c = Math.Pow(b, 20);
    result += a * c;
  }
  return -1.0 * result;
}

図 2 下部の Michalewicz 関数の方程式をみると、Michalewicz 関数は 2m 乗を計算しています。ただし、通常 m の値は 10 に設定されるため、コードでは定数値 20 を使用します。ヘルパーメソッド Error は次のように定義します。

static double Error(double[] xValues)
{
  int dim = xValues.Length;
  double trueMin = 0.0;
  if (dim == 2)
    trueMin = -1.8013; // Approx.
  else if (dim == 5)
    trueMin = -4.687658; // Approx.
  double calculated = Michalewicz(xValues);
  return (trueMin - calculated) * (trueMin - calculated);
}

Error メソッドは、Michalewicz 関数の既知の最小値と計算した値の差の 2 乗を返すだけです。このダミーの誤差関数は非常に高速計算されますが、多くの学習シナリオでは誤差関数の計算に長い時間がかかります。

Firefly クラス

Firefly クラスの定義は、次のコードで始まります。

public class Firefly : IComparable<Firefly>
{
  public double[] position;
  public double error;
  public double intensity;
...

Firefly クラスは IComparable インターフェイスを継承するため、オブジェクトを含む配列やリストは自動的に並べ替えられます。データフィールドは、簡潔にするためにパブリックスコープを使用して定義します。error フィールドと intensity フィールドの間には 1 対 1 マッピングがあるため、この 2 つのフィールドのうち一方を削除してもかまいません。クラスコンストラクターを以下に示します。

public Firefly(int dim)
{
  this.position = new double[dim];
  this.error = 0.0;
  this.intensity = 0.0;
}

他にもさまざまな設計が考えられます。ここでは、コンストラクターは単純に position 配列用に領域を確保します。他に必要な最後のパブリックメソッドは CompareTo です。

public int CompareTo(Firefly other)
  {
    if (this.error < other.error) return -1;
    else if (this.error > other.error) return +1;
    else return 0;
  }
} // Class Firefly

CompareTo メソッドでは、誤差の小さいホタルから大きいホタルへと Firefly オブジェクトを並べ替えます。つまり、明るいものから暗いものへと並べ替えます。

コメントをいくつか

今回示した FA の実装は、2009 年の研究論文を基盤にしています。元のアルゴリズムには、複数のバリエーションがあります。この研究論文では、少なくとも一部のダミーベンチマーク最適化問題において、FA が粒子群最適化よりも優れていることを示唆するデータが示されました。少し懐疑的ですが、個人的見解としては、FA が非常に便利であるシナリオは最小化される目的関数が複数の解を持つ場合です。完全に明白というわけではありませんが、結局のところ、FA は複数の解を同時に見つけられる部分的な群れを自動的に自己編成します。

Dr. James McCaffrey* は、ワシントン州レドモンドにある Microsoft Research に勤務しています。これまでに、Internet Explorer、Bing などの複数のマイクロソフト製品にも携わってきました。McCaffrey 博士の連絡先は、jammc@microsoft.com (英語のみ) です。*

この記事のレビューに協力してくれたマイクロソフト技術スタッフの Todd Bello、Marciano Moreno Diaz Covarrubias、および Alisson Sol に心より感謝いたします。

次の方法で共有

テストの実行 - Firefly Algorithm 最適化

プログラムの全体構造

FA について

FA の実装

ヘルパーメソッド

Firefly クラス

コメントをいくつか

その他のリソース

次の方法で共有

テストの実行 - Firefly Algorithm 最適化

プログラムの全体構造

FA について

FA の実装

ヘルパー メソッド

Firefly クラス

コメントをいくつか

その他のリソース

ヘルパーメソッド