• [アーティクル]

February 2016

Volume 31 Number 2

テストの実行 - Roach Infestation Optimization

James McCaffrey

James McCaffrey「Roach Infestation Optimization」とは、ワモンゴキブリなどの一般的なゴキブリの行動に大まかに基づく数値最適化アルゴリズムです。読み間違いではありません。早速、説明しましょう。

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

さまざまな数値最適化アルゴリズムがあります。最も一般的なアルゴリズムは微積分の導関数に基づきますが、自然界の行動に基づくアルゴリズムもあります。このようなアルゴリズムは、生物学を模したアルゴリズムと呼ばれることもあります。今回は Roach Infestation Optimization (RIO) という比較的新しい手法 (2008 年に初めて発表) を取り上げます。RIO 最適化は、ゴキブリの群れの採餌行動と密集行動を大まかにモデル化するものです。

RIO の考え方と今回の目標を理解するには、図 1 のデモ プログラムをご覧いただくのが一番です。デモの目標は、RIO を使用して、8 個の入力変数を指定して Rastrigin 関数の最小値を見つけることです。Rastrigin 関数は、数値最適化アルゴリズムの効果を評価するために使用する標準ベンチマーク関数です。この関数は、値 0 の個数が入力値の個数と等しくなる x = (0, 0, . . 0) の場合に、既知の最小値 0.0 になります。

Roach Infestation Optimization アルゴリズムの動作
図 1. Roach Infestation Optimization アルゴリズムの動作

Rastrigin 関数には局所最小値を生み出す山と谷がたくさんあり、アルゴリズムが抜き差しならない状態になる可能性があるため、大半の最適化アルゴリズムでは、Rastrigin 関数の使用は困難です。8 個の入力値を使用する Rastrigin 関数は簡単には視覚化できません。しかし、入力値が 2 個の場合のグラフを見れば、この関数の特性を把握できます (図 2 参照)。

入力変数が 2 個の Rastrigin 関数
図 2. 入力変数が 2 個の Rastrigin 関数

今回のデモ プログラムでは、ゴキブリの数を 20 匹に設定します。シミュレーションを行うゴキブリにはそれぞれ位置があり、これが最小化問題の解の候補を表します。ゴキブリの数を増やすほど、真の最適解が見つかる可能性が高まりますが、パフォーマンスは低下します。RIO では、通常、10 ～ 100 匹のゴキブリを使用します。

RIO は反復プロセスなので、ループ カウンターの最大値が必要です。今回のデモでは、最大反復回数を 10,000 回に設定します。最大反復回数は問題によって異なりますが、1,000 ～ 100,000 回が一般的です。RIO の要素にはランダム性があり、デモでは、乱数ジェネレーターのシード値を 6 に設定します。シード値に 6 を使用したのは、デモの代表的な出力が得られるためです。

図 1 のデモでは、500 時間単位ごとに、そこまでに見つかったゴキブリの最適位置に関連する最適 (最小) 誤差を表示しています。アルゴリズムが完了すると、すべてのゴキブリに対して見つかる最適位置が x = (0, 0, 0, 0, 0, 0, 0, 0) になっています。実はこれが正解です。しかし、最大反復回数を 10,000 ではなく 5,000 に設定すると、RIO は、全体として 1 つの最小値を見つけられないことがわかります。RIO はほぼすべての数値最適化アルゴリズムと同様、実際のシナリオで最適解が見つかることは保証されません。

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

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

プログラムの全体構造

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

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

using System;
namespace RoachOptimization
{
  class RoachOptimizationProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin roach optimization demo");
      // Code here
      Console.WriteLine("End roach demo");
      Console.ReadLine();
    }
    static double[] SolveRastrigin(int dim, int numRoaches,
      int tMax, int rndSeed) { . . }
    public static double Error(double[] x) { . . }
    static double Distance(double[] pos1,
      double[] pos2) { . . }
    static void Shuffle(int[] indices,
      int seed) { . . }
  } // Program
  public class Roach
  {
    // Defined here
  }
}

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

このデモは、完全なオブジェクト指向プログラミング (OOP) のアプローチではなく、ほぼ静的メソッドのアプローチを使用してコーディングしています。すべての制御ロジックは Main メソッドに配置しています。最初に、アルゴリズムの入力パラメーター値をセットアップします。

Console.WriteLine("Begin roach optimization demo");
int dim = 8;
int numRoaches = 20;
int tMax = 10000;
int rndSeed = 6;

変数 dim は、Rastrigin 関数の入力値の個数を指定します。デモ以外の機械学習シナリオでは、dim が予測モデルの重みの個数を表します。ゴキブリの数は 20 匹に設定します。変数 tMax は最大反復回数です。RIO は、生物学を模した多くのアルゴリズムと同様、確率論です。今回は、ランダム変数のシード値を 6 に設定します。

設定が完了したら、RIO のパラメーターをコンソールにエコー出力します。

Console.WriteLine("Goal is to minimize Rastrigin's " +
  "function in " + dim + " dimensions");
Console.WriteLine("Problem has known min value = 0.0 " +
  "at (0, 0, .. 0) ");
Console.WriteLine("Setting number of roaches = " +
  numRoaches);
Console.WriteLine("Setting maximum iterations = " +
  tMax);
Console.WriteLine("Setting random seed = " + rndSeed);;

最適化のアルゴリズムは次のように呼び出します。

Console.WriteLine("Starting roach optimization ");
double[] answer = SolveRastrigin(dim, numRoaches,
  tMax, rndSeed);
Console.WriteLine("Roach algorithm completed");

最後に Main メソッドは、結果を表示して終了します。

double err = Error(answer);
Console.WriteLine("Best error found = " +
  err.ToString("F6") + " at: ");
for (int i = 0; i < dim; ++i)
  Console.Write(answer[i].ToString("F4") + " ");
Console.WriteLine("");
Console.WriteLine("End roach optimization demo");
Console.ReadLine();

今回の最適化アルゴリズムは、T. Havens、C. Spain、N. Salmon、J. Keller 共著の 2008 年の研究論文「Roach Infestation Optimization」に基づきます。この論文は Web 上の複数の場所から入手できます。

最適化アルゴリズムについて

RIO では、ゴキブリの群れをシュミレーションします。各ゴキブリの位置を n 次元で表現し、その位置が最小化問題の解の候補を表します。ゴキブリの行動シミュレーションは、実際のゴキブリの 3 つの行動パターンに基づきます。まず、傾向として暗い場所に移動します。次に、好んで群れを作ります。最後に、お腹が空くと、食べ物を求めて現在の場所から離れます。このようなゴキブリの行動シミュレーションをモデル化する方法は、コードを見れば一目瞭然です。

この行動アルゴリズムを大まかな擬似コードで表すと、図 4 のようになります。一見すると、アルゴリズムは非常にシンプルですが、擬似コードには示されていない細部はたくさんあります。

図 4. 大まかなゴキブリの行動アルゴリズム

initialize n roaches to random positions
loop tMax times
  compute distances between all roaches
  compute median distance
  for-each roach
    compute number neighbors
    exchange data with neighbors
    if not hungry
      compute new velocity
      compute new position
      check if new best position
    else if hungry
      relocate to new position
    end-if
  end-for
end loop
return best position found

Roach クラス

プログラム定義の Roach クラスは次のコードから始まります。

public class Roach
{
  public int dim;
  public double[] position;
  public double[] velocity;
  public double error;
...

dim フィールドは問題の次元数なので、今回のデモでは 8 です。position フィールドは、ゴキブリの場所を概念的に表す配列で、最小化問題の解の候補になります。velocity フィールドは、次回の時間単位でのゴキブリの移動先を示す値の配列です。たとえば、dim = 2、position = (5.0, 3.0)、および velocity = (1.0, -2.0) の場合、ゴキブリは (6.0, 1.0) に移動します。error フィールドは、現在の場所に関連付けられる誤差です。

さらに、定義は次のように続きます。

public double[] personalBestPos;
public double personalBestErr;
public double[] groupBestPos;
public int hunger;
private Random rnd;

personalBestPos フィールドは、ゴキブリ移動のシミュレーションで見つかった任意の時点での最適位置を保持します。personalBestError は、personalBestPos との誤差です。groupBestPos フィールドは、近くのゴキブリの群れに対して見つかった最適位置を保持します。hunger フィールドは、ゴキブリの空腹度を示す整数値です。rnd という Random オブジェクトは、ゴキブリをランダムな位置に初期化するために使用します。

Roach クラスの定義は、コンストラクターの定義へと続きます。

public Roach(int dim, double minX, double maxX,
  int tHunger, int rndSeed)
{
  this.dim = dim;
  this.position = new double[dim];
  this.velocity = new double[dim];
  this.personalBestPos = new double[dim];
  this.groupBestPos = new double[dim];
...

minX パラメーターと maxX パラメーターは、position ベクトルの成分に制限を設けます。tHunger パラメーターは空腹の最大値です。ゴキブリの空腹が tHunger に達すると、ゴキブリは新しい場所に移動します。コンストラクターでは 4 つの配列フィールド用の領域を確保します。

次に、Random オブジェクトを初期化してから、初期化した Random オブジェクトを使用して、初期 hunger 値にランダム値を設定します。

this.rnd = new Random(rndSeed);
this.hunger = this.rnd.Next(0, tHunger);

続いて、初期位置の配列、速度の配列、個別の最適位置の配列、および群れの最適位置の配列を、minX ～ maxX までのランダムな値に設定します。

for (int i = 0; i < dim; ++i) {
  this.position[i] = (maxX - minX) * rnd.NextDouble() + minX;
  this.velocity[i] = (maxX - minX) * rnd.NextDouble() + minX;
  this.personalBestPos[i] = this.position[i];
  this.groupBestPos[i] = this.position[i];
}

Roach コンストラクターの定義は、次のように締めくくります。

...
    error = RoachOptimizationProgram.Error(this.position);
    personalBestErr = this.error;
  } // ctor
} // Roach

error フィールドは、呼び出し側のクラスで定義されている、外部 Error メソッドを呼び出すことによって設定します。別のアプローチとして、コンストラクターを呼び出す前に error 値を計算して、コンストラクターへのパラメーターとして error 値を渡すこともできます。

最適化アルゴリズムの実装

RIO アルゴリズムは、次の定義で始まる静的メソッド SolveRastrigin に収めています。

static double[] SolveRastrigin(int dim, int numRoaches,
  int tMax, int rndSeed)
{
  double C0 = 0.7;
  double C1 = 1.43;
  double[] A = new double[] { 0.2, 0.3, 0.4 };
...

後ほど説明しますが、定数 C0 と定数 C1 は、ゴキブリの新しい速度を計算する際に使用します。使用する値 0.7 と 1.43 は、粒子群の理論に由来します。他の値も調べてみてください。

互いに近くにいるゴキブリどうしを「隣接ゴキブリ」と呼ぶことにします。隣接ゴキブリは、必ずではありませんが、情報を交換することがあります。配列 A は確率を保持します。最初の値 0.2 は、1 匹の隣接ゴキブリがいるゴキブリが、その隣接ゴキブリと情報を交換する確率です。2 つ目の値 0.3 は、ゴキブリに 2 匹の隣接ゴキブリが存在する場合に、情報を交換する確率です。3 つ目の値 0.4 は、ゴキブリに 3 匹以上の隣接ゴキブリが存在する場合に、情報を交換する確率です。

これらの確率値 (0.2, 0.3, 0.4) は、原典の研究論文で使用されている確率値と異なります。オリジナルの研究論文では、ある生物学的研究論文で示された実際のゴキブリの行動に対応する確率値 (0.49, 0.63, 0.65) が使用されています。実際のゴキブリの行動に対応するこの確率値は、今回のデモで使用する人工的な確率値ほどの効果がないことがわかりました。SolveRastrigin メソッドは次の定義から始まります。

int tHunger = tMax / 10;
double minX = -10.0;
double maxX = 10.0;
int extinction = tMax / 4;
Random rnd = new Random(rndSeed);

ローカル変数 tHunger は、ゴキブリが空腹になって現在の場所と隣接ゴキブリから離れるタイミングを決定します。たとえば、デモのように tMax が 10,000 の場合、ゴキブリの空腹値が tMax / 10 = 1,000 に達すると、ゴキブリは新しい位置に移動します。

変数 minX と変数 maxX は、ゴキブリの position ベクトルに制限を設けます。値 (-10.0, +10.0) は、機械学習の重みとして一般的であり、Rastrigin 関数の通常の制限にも対応します。たとえば、次元 = 3 が設定されている問題の場合、position ベクトルは、-10.0 ～ +10.0 の範囲の値を持つ 3 つのセルの配列になります。

ローカル変数 extinction は、すべてのゴキブリが死に、新しい位置で生き返るタイミングを決定します。これは再起動のメカニズムで、アルゴリズムが最適ではない解にこだわるのを防ぐのに役立ちます。

アルゴリズムでは、rnd というローカル Random オブジェクトを 3 つの目的で使用します。1 つはゴキブリを処理する順番をランダムにするためです。次に、隣接ゴキブリとの情報交換を特定の確率で行うためです。最後に、各ゴキブリの新しい速度にはランダムな成分を持たせるためです。SolveRastrigin メソッドは、次のように続けます。

Roach[] herd = new Roach[numRoaches];
for (int i = 0; i < numRoaches; ++i)
  herd[i] = new Roach(dim, minX, maxX, tHunger, i);

シミュレーションを行うゴキブリの群れは、herd という配列です。クジラの群れやガチョウの群れといった動物の群れには、さまざまな種類の興味深い名前が付けられています。実は、ゴキブリの群れは「侵入者」(Intrusion Of Roaches) と呼ばれます (この情報は飲み会で使える話題となるでしょう)。

ループ インデックス変数 i を、Roach コンストラクターに渡しています。このインデックス変数は、Roach クラス定義に含まれる Random オブジェクトの乱数シード値として機能します。乱数のシード値に使用するためにループ インデックス変数を渡すのは、機械学習では一般的に行われます。メソッド定義は次のように続けます。

int t = 0;  // Loop counter (time)
int[] indices = new int[numRoaches];
for (int i = 0; i < numRoaches; ++i)
  indices[i] = i;
double bestError = double.MaxValue;
double[] bestPosition = new double[numRoaches];
int displayInterval = tMax / 20;

配列 indices は値 (0, 1 2, . . numRoaches-1) を保持します。この配列は、ゴキブリの処理順序が毎回異なるように、メインの処理ループでシャッフルします。ローカル変数 bestPosition と bestError は、任意の時点で任意のゴキブリに対して見つかった最適位置/解と関連誤差を保持します。ローカル変数 displayInterval は、進捗メッセージをコンソールに表示するタイミングを決定します。次に、配列の配列形式の行列のインスタンスを作成し、すべてのゴキブリのペアどうしの距離を保持します。

double[][] distances = new double[numRoaches][];
for (int i = 0; i < numRoaches; ++i)
  distances[i] = new double[numRoaches];

たとえば、distances[0][3] = 7.89 の場合、distances[3][0] も 7.89 になり、roach 0 と roach 3 間の距離が 7.89 であることを示します。多くの場合、膨大な数のゴキブリを扱うことはないため、冗長データはそれほど問題ではありません。続いて、メイン処理ループを次のように始めます。

while (t < tMax)
{
  if (t > 0 && t % displayInterval == 0) {
    Console.Write("time = " + t.ToString().PadLeft(6));
    Console.WriteLine(" best error = " +
      bestError.ToString("F5"));
  }
...

その後、ゴキブリどうしの距離を計算します。

for (int i = 0; i < numRoaches - 1; ++i) {
  for (int j = i + 1; j < numRoaches; ++j) {
    double d = Distance(herd[i].position,
                 herd[j].position);
    distances[i][j] = distances[j][i] = d;
  }
}

距離の値は、ヘルパー メソッド Distance を使用して計算しますが、これについては後ほど説明します。上記の配列のインデックス操作は少し複雑ですが、興味があれば検証してみてください。次に、距離の値を distances 行列から配列にコピーします。これにより、並び替えが可能になり、距離の中央値を決定できるようになります。

double[] sortedDists =
  new double[numRoaches * (numRoaches - 1) / 2];
int k = 0;
for (int i = 0; i < numRoaches - 1; ++i) {
  for (int j = i + 1; j < numRoaches; ++j) {
    sortedDists[k++] = distances[i][j];
  }
}

配列のサイズは、わかりやすいように例を使って説明します。n = 4 匹のゴキブリがいるとします。この場合 distances 行列は、4 行 x 4 列にです。対角線上の値 [0][0]、[1][1]、[2][2]、および [3][3] は 0.0 になるため、含めません。[0][1]、[0][2]、[0][3]、[1][2]、[1][3]、および [2][3] に、6 つの値が残ります。対称の位置となるインデックス [1][0]、[2][0] などに、同じ距離値を設定する必要はありません。そのため、n * (n-1) / 2 個の異なる距離値があります。次に、ゴキブリどうしの距離の中央値を計算し、ゴキブリのインデックスをランダムに変更します。

Array.Sort(sortedDists);
double medianDist = sortedDists[sortedDists.Length / 4];
Shuffle(indices, t); // t is used as a random seed

上記では、4 で割り算しているため、距離は並べ替え済みの距離の配列の先頭から 4 分の 1 です。したがって、実際の結果は中央値ではなく、四分位値になります。オリジナルの研究論では、実際の中央値 (2 で割り算した値) が使用されていますが、中央値よりも四分位値の方が適切に機能することがわかりました。考え方としては、中央値または四分位値は、特定のゴキブリの隣接ゴキブリの数を決めます。この値は、ゴキブリの群れがどの程度密集しているかを示します。四分位値を使用すると、ゴキブリはより距離を保った状態になり、見つかりにくい (ターゲット関数を最小に抑える) 全体的な最小値が見つかるチャンスが高まります。

ゴキブリのインデックスは、ヘルパー メソッド Shuffle を使用してランダムに変更します。詳しくは後ほど説明します。時間のインデックスの変数 t を Shuffle メソッドに渡し、Shuffle 乱数ジェネレーターのシードとして動作させます。続いて、次のように各ゴキブリを処理するループを始めます。

for (int i = 0; i < numRoaches; ++i)  // Each roach
{
  int idx = indices[i]; // Roach index
  Roach curr = herd[idx]; // Ref to current roach
  int numNeighbors = 0;
...

現在のゴキブリへの参照 herd[idx] を作成し、curr と名付けます。これは利便性だけを目的にしています。次に、現在のゴキブリの隣接ゴキブリの数を計算します。

for (int j = 0; j < numRoaches; ++j) {
  if (j == idx) continue;
  double d = distances[idx][j];
  if (d < medianDist) // Is a neighbor
    ++numNeighbors;
}

condition j == idx は、現在のゴキブリ自体が隣接ゴキブリに数えられるのを防ぎます。次に、影響する隣接ゴキブリ数を決定します。

int effectiveNeighbors = numNeighbors;
if (effectiveNeighbors >= 3)
  effectiveNeighbors = 3;

隣接ゴキブリの数を計算する目的は、隣接ゴキブリが情報を交換する確率を決定することでした。ただし、3 匹以上の隣接ゴキブリの場合、情報交換の確率は同じです。ここで、情報交換を行うかどうかを判断します。

for (int j = 0; j < numRoaches; ++j) {
  if (j == idx) continue;
  if (effectiveNeighbors == 0) continue;
  double prob = rnd.NextDouble();
  if (prob > A[effectiveNeighbors - 1]) continue;
...

現在のゴキブリを、他のすべてのゴキブリと比較します。現在のゴキブリに隣接ゴキブリがいなければ、情報は交換しません。隣接ゴキブリが 1 匹以上いる場合、確率の配列 A を使用して、情報を交換するかどうかを判断します。続いて、以下の処理を行います。

double d = distances[idx][j];
if (d < medianDist) { // a neighbor
  if (curr.error < herd[j].error) { // curr better than [j]
    for (int p = 0; p < dim; ++p) {
      herd[j].groupBestPos[p] = curr.personalBestPos[p];
      curr.groupBestPos[p] = curr.personalBestPos[p];
    }
  }
...

隣接ゴキブリと情報を交換することになった場合、隣接する 2 匹のゴキブリのうち群れの最適位置と関連誤差が勝っているゴキブリの情報を、劣っている方のゴキブリにコピーします。情報交換の 2 つ目の分岐のコードは以下のとおりです。

...
    else { // [j] is better than curr
      for (int p = 0; p < dim; ++p) {
        curr.groupBestPos[p] = herd[j].personalBestPos[p];
        herd[j].groupBestPos[p] = herd[j].personalBestPos[p];
      }
    }
  } // If a neighbor
} // j, each neighbor

隣接ゴキブリとの情報交換後、現在のゴキブリは、空腹でなければ移動します。移動プロセスの冒頭部分で、現在のゴキブリの新しい速度を計算します。

if (curr.hunger < tHunger) {
  for (int p = 0; p < dim; ++p)
    curr.velocity[p] = (C0 * curr.velocity[p]) +
     (C1 * rnd.NextDouble() * (curr.personalBestPos[p] -
       curr.position[p])) +
     (C1 * rnd.NextDouble() * (curr.groupBestPos[p] -
       curr.position[p]));

新しい速度には 3 つの成分があります。最初の成分は以前の速度で、粒子群の用語では「慣性」と呼ばれることもあります。慣性は、ゴキブリが同じ方向に移動し続けるように働きます。2 つ目の成分はゴキブリの既知の最適位置で、「認知」と呼ばれることもあります。認知成分は、ゴキブリが今よりも悪い位置に移動するのを防ぎます。3 つ目の成分は、隣接ゴキブリの既知の最適位置です。この成分は、おおよそ RIO ごとに一意になり、標準名はありません。この 3 つ目の成分は、ゴキブリの群れが 1 つにまとまった状態を保つように働きます。

現在のゴキブリの速度を計算したら、ゴキブリを移動します。

for (int p = 0; p < dim; ++p)
  curr.position[p] = curr.position[p] + curr.velocity[p];
double e = Error(curr.position);
curr.error = e;

現在のゴキブリを移動したら、新しい位置をチェックして、そのゴキブリにとって新しい最適位置かどうかを確認します。

if (curr.error < curr.personalBestErr) {
  curr.personalBestErr = curr.error;
  for (int p = 0; p < dim; ++p)
    curr.personalBestPos[p] = curr.position[p];
}

次に、新しい位置をチェックして、全体として新しい最適位置になるかどうかを確認します。その後、空腹カウンターをインクリメントします。

if (curr.error < bestError) {
    bestError = curr.error;
    for (int p = 0; p < dim; ++p)
      bestPosition[p] = curr.position[p];
  }
  ++curr.hunger;
} // If not hungry

各ゴキブリのループの最後に空腹のゴキブリを処理します。

else { // Roach is hungry
  {
    herd[idx] = new Roach(dim, minX, maxX, tHunger, t);
  }
} // j each roach

ゴキブリの空腹カウンターがしきい値 tHunger に達したら、そのゴキブリを新しいランダムな位置に移動します。すべてのゴキブリを処理したら、全体として死滅するタイミングかどうかをチェックし、メイン ループの時間カウンターをインクリメントして、すべてのゴキブリで見つかった最適位置を返せばアルゴリズムは完了です。

if (t > 0 && t % extinction == 0) { // Extinction?
      Console.WriteLine("Mass extinction at t = " +
        t.ToString().PadLeft(6));
      for (int i = 0; i < numRoaches; ++i)
        herd[i] = new Roach(dim, minX, maxX, tHunger, i);
    }
    ++t;
  } // Main while loop
  return bestPosition;
} // Solve

今回のアルゴリズムは、Solve のような一般的な名前ではなく、SolveRastrigin という名前のメソッドに収めました。RIO が規範的なアルゴリズムではなく、メタヒューリスティックなアルゴリズムで、解決を試みる最小化問題に合わせてカスタマイズする必要があるという考えで、この名前にしています。

ヘルパー メソッド

SolveRastrigin メソッドは、ヘルパー メソッドとして Distance、Error、および Shuffle を呼び出しています。ヘルパー メソッド Distance は、ユークリッド距離 (項の差の 2 乗を合計した値の平方根) を返します。

static double Distance(double[] pos1, double[] pos2)
{
  double sum = 0.0;
  for (int i = 0; i < pos1.Length; ++i)
    sum += (pos1[i] - pos2[i]) * (pos1[i] - pos2[i]);
  return Math.Sqrt(sum);
}

ヘルパー メソッド Error は、与えられたゴキブリの位置 x における Rastrigin 関数の計算値と、真の最小値 0 との差の 2 乗を返します。

public static double Error(double[] x)
{
  double trueMin = 0.0; double rastrigin = 0.0;
  for (int i = 0; i < x.Length; ++i) {
    double xi = x[i];
    rastrigin += (xi * xi) - (10 * Math.Cos(2 * Math.PI * xi)) + 10;
  }
  return (rastrigin - trueMin) * (rastrigin - trueMin);
}

Shuffle メソッドは、Fisher-Yates ミニアルゴリズムを使用して、配列内の値の順番をランダムに入れ替えます。

static void Shuffle(int[] indices, int seed)
{
  Random rnd = new Random(seed);
  for (int i = 0; i < indices.Length; ++i) {
    int r = rnd.Next(i, indices.Length);
    int tmp = indices[r]; indices[r] = indices[i];
    indices[i] = tmp;
  }
}

オリジナルの研究論文に記載されている RIO バージョンでは、ゴキブリの処理順序のランダム化を行っていませんが、ほとんどの場合、このアプローチは、生物学を模した最適化アルゴリズムの正確性を向上させます。

コメントをいくつか

では、他の数値最適化手法に比べて、ゴキブリを模したアルゴリズムはどれほど効果的なのでしょう。数回という限られた実験結果に基づくと、RIO は、他のアルゴリズムよりも適切にベンチマークの問題を解決するように見えますが、他の問題ではそれほどではありません。RIO は、新しい優れた汎用最適化アルゴリズムではありませんが、将来性があり、ある特定の最小化問題には適しているというのが結論です。もちろん、Roach Infestation Optimization は、コンピューター サイエンス全体において、最も独特な名前を持つ手法の 1 つです。

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

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