[アーティクル]
12/19/2016

April 2011

Volume 26 Number 04

自然なアルゴリズム - 蜂コロニーのアルゴリズムを使用して困難な問題を解決する

James McCaffrey | April 2011

image: James McCaffrey 蜂コロニーのシミュレーション (SBC: Simulated Bee Colony) アルゴリズムは、ミツバチの行動をモデル化するアルゴリズムで、解くのが困難または不可能に思える組み合わせ問題を解決できます。今回の記事では、SBC アルゴリズムとは何かを解説し、SBC アルゴリズムを使用して解決できる問題の種類について説明します。また、巡回セールスマン問題 (TSP: Traveling Salesman Problem) を解くために SBC アルゴリズムを使用する完全なエンドツーエンドの例を示します。

SBC アルゴリズムの感触を掴み、この記事の目的を理解するには、図 1 で実行されているデモプログラムを参照してください。このデモプログラムでは、SBC アルゴリズムを使用して、(A ～ T のラベルを付けた) 20 都市について分析し、すべての都市を確実に 1 回訪れる最短経路を見つけます。都市のデータは、都市 A から都市 T までをアルファベット順に訪問すると経路の長さが 19 単位になり、これが最短経路となるよう人工的に作成しています。

図 1 蜂コロニーのシミュレーションのデモ

図 1 蜂コロニーのシミュレーションのデモ

SBC アルゴリズムの内部では、それぞれランダムで潜在的な解法を持つ 100 匹のミツバチのシミュレーションを行い、そのミツバチの巣のインスタンスを 1 つ作成します。ランダムな解法が求めた最初の最短経路の長さは、95.5 単位です。SBC アルゴリズムは、食料を探し回るミツバチの行動のシミュレーションを行う処理ループに入ります。この処理ループでの動きは、テキストベースの進行状況バーによって示します。SBC の処理ループの最後には、20 個のうち 16 個の都市が適切な位置に変わり、最短経路の長さは正解にほぼ近い 26.5 単位になります。

SBC アルゴリズムは、細かい解法の処方箋を提供するのではなく、問題の解法を作成するための全般的フレームワークと一連のガイドラインを提供するため、しばしば "メタヒューリスティック" といわれます。ここでは、SBC を使用して具体的な問題を解決する例を示します。SBC を使用してどのように問題を解決できるかを理解できれば、ここで紹介している SBC アルゴリズムを自身の問題解決に適用できるようになります。この後、例を挙げて説明しますが、SBC アルゴリズムは、実用的な決定性の解法がない、複雑な組み合わせ問題にとって最適なアルゴリズムです。

今回は、C# の中級レベルのプログラミングスキルが前提です。ここで紹介する例は、C# を使用してコーディングしていますが、すべてのコードは別のプログラミング言語に簡単にリファクタリングできるように記述しています。きっと興味深くお読みいただけると思います。そして、SBC アルゴリズムを使いこなす能力を自分のスキルに追加すれば便利なことがおわかりいただけるとさいわいです。

ミツバチについて

セイヨウミツバチなどの一般的なミツバチは、自身のコロニーの中で徐々に異なる役割を担うようになります。代表的な巣には、5,000 ～ 20,000 匹のミツバチがいます。成熟したミツバチ (20 ～ 40 日) は、普通、食料を探す役割を果たすようになります。ミツバチは通常、能動的な食料探索担当、食料源の偵察担当、および受動的な食料探索担当の 3 つの役割に分かれます。

能動的探索担当は、食料源に向かい、近くの食料源を調べ、食料を集めて巣に戻ります。

食料源偵察担当は、巣を取り囲む領域 (多くの場合、最大 50 平方マイル) を調査し、魅力的な新しい食料源を探します。巣の中の探索担当の約 10% が、この偵察者としての役割を担います。

探索担当の一部は、一定期間受動的探索担当になります。このような受動的探索担当は、巣の入り口あたりで待機します。能動的探索担当と、食料源偵察担当が巣に戻ると、つい先ほど訪れた食料源の質に応じて、待機していた受動的ミツバチに向かって尻振りダンスを踊ります。この尻振りダンスは、食料源の場所と質についての情報を受動的探索担当に伝える強力な証拠になります。受動的探索担当は、この尻振りダンスから食料源についての情報を受け取り、能動的探索担当になります。

通常、能動的探索担当は食料源が尽きるまで、特定の食料源から食料を収集し続けます。食料源が尽きると、受動的探索担当になります。

巡回セールスマン問題

巡回セールスマン問題 (TSP: Traveling Salesman Problem) は、コンピューターサイエンスの調査において、最も広く研究されている問題の 1 つです。TSP にはさまざまなバリエーションがありますが、平たく言えば、この問題は、特定の複数の都市を必ず 1 回訪れる最短経路を見つけるものです。

図 1 を見ると、SBC デモプログラムでは、ランダムに A ～ T のラベルを付けた 20 個の都市を使用しているのがわかります。有効な経路は、各都市が必ず 1 回登場し、それが順番に並べられた 20 個の都市名から構成されます。したがって、全部で 20! = 2,432,902,008,176,640,000 とおりの経路が存在します。

内部では、各都市のペアに距離値を関連付けています。ここではわかりやすくするために、アルファベット順で都市 c1 < 都市 c2 の場合、c1 から c2 に向かう距離は、2 つの都市間に関連付けた距離のちょうど 1.0 倍とします。アルファベット順で都市 c1 > 都市 c2 の場合、c1 から c2 に向かう距離は、c1 と c2 のペアに関連付けた距離の 1.5 倍とします。たとえば、A から B に向かう距離は 1.0 単位 (単位は何でもかまいません) で、B から A に向かう距離は 1.5 単位です。A から C に向かう距離は 2.0 単位というように考えていきます。したがって、すべての都市を必ず 1 回訪れる最短経路は A -> B-> C -> ... -> T になり、経路の長さは (20-1) * 1.0 = 19.0 になります。

ほとんど TSP シナリオでは、都市間の距離が人為的に計算されることはありません。距離は、ある種の照合を行えるデータ構造に格納します。TSP の中には、どの都市も他のすべての都市とつながっていると仮定するものや、すべての都市どうしがつながっているわけではないと仮定するものもあります。さらに、都市 c1 から都市 c2 へ向かっても、都市 c2 から c1 に向かっても距離は同じであると仮定するものや、このような双方向性の仮定を行わないものもあります。

細かい状況を除けば、最短経路を見つけるのに強引な手法はふさわしくありません。たとえば、20 個の都市があり、1 秒間に 100 万個の経路を評価できるとしても、20! 個すべての有り得る経路を調べるには、77,000 年以上かかります。このような、きわめて難しい組み合わせの最適化問題に、SBC アルゴリズムが適しています。

このダミーの TSP の問題は、図 2 の CitiesData というクラスに実装しています。この SBC のデモプログラムは、 code.msdn.microsoft.com/mag201104BeeColony (英語) からダウンロードできます。

図 2 CitiesData クラス定義

class CitiesData {
  public char[] cities;

  public CitiesData(int numberCities) {
    this.cities = new char[numberCities];
    this.cities[0] = 'A';
    for (int i = 1; i < this.cities.Length; ++i)
      this.cities[i] = (char)(this.cities[i - 1] + 1);
  }

  public double Distance(char firstCity, char secondCity) {
    if (firstCity < secondCity)
      return 1.0 * ((int)secondCity - (int)firstCity);
    else
      return 1.5 * ((int)firstCity - (int)secondCity);
  }

  public double ShortestPathLength() {
    return 1.0 * (this.cities.Length - 1);
  }

  public long NumberOfPossiblePaths() {
    long n = this.cities.Length;
    long answer = 1;
    for (int i = 1; i <= n; ++i)
      checked { answer *= i; }
    return answer;
  }

  public override string ToString() {
    string s = "";
    s += "Cities: ";
    for (int i = 0; i < this.cities.Length; ++i)
      s += this.cities[i] + " ";
    return s;
  }
}

それぞれの問題を表すクラスやデータ構造の定義は、ここで示しているものとは異なるでしょう。ただし、一般に、SBC アルゴリズムを使用した解法に適した問題は、数値以外の配列、数値以外の行列、または数値以外のジャグ配列として表すことができます。

CitiesData コンストラクターは、都市数を受け取り、最初の都市に A、2 つ目の都市に B という具合にラベルを付けます。

Distance メソッドは、先ほど説明した単方向方式で定義し、すべての都市が他のすべての都市につながっていると仮定します。

ShortestPathLength メソッドは、Distance 定義を踏まえ、最短経路の長さを返します。SBC の大半のケースでは、最適な解法を返すメソッドを実装するのに必要な情報はわかりません。

NumberOfPossiblePaths メソッドは、単に n! を計算します。n は都市数です。TSP では、有り得る経路の数が n-1! (開始する都市がどこでも良い) のシナリオもあれば、有り得る経路の数が n/2! (経路の方向を問わない) のシナリオもあります。

ToString メソッドは、説明的なデータを含む文字列を組み立てるために、効率の良い StringBuilder クラスではなく、文字列の連結を使用します。文字列の連結は、別のプログラミング言語へのリファクタリングを簡単にするために使用しています。

ここでは、コードを比較的短く、わかりやすくするために、エラーチェックをほとんど取り除くなど、運用コードでは使用しない近道をしました。たとえば NumberOfPossiblePaths メソッドは、結果が long.MaxValue よりも大きくても、数値のオーバーフローに対処しません。

SBC プログラムの構造

図 1 の SBC アルゴリズムは、C# コンソールアプリケーションとして実装しています。プログラムの全体構造を図 3 に示します。SBC プログラム構造は、かなりシンプルで、基本の System 名前空間のみを使用しています。クラスには、Main メソッドを 1 つ含む Program クラス、SBC アルゴリズムのロジックをすべて含む Hive クラス、および今説明した CitiesData クラスの 3 つのクラスがあります。SBC アルゴリズムの実装は、解決の対象として設計した特定の問題に大きく依存しますが、Hive クラスは、TravelingSalesmanHive などの具体的な名前ではなく、総称的に Hive と名付けています。

図 3 プログラムの全体構造

using System;
namespace SimulatedBeeColony {
  class Program {
    static void Main(string[] args) {
      Console.WriteLine("\nBegin Simulated Bee Colony algorithm demo\n");
      . . . 
      Console.WriteLine("End Simulated Bee Colony demo");
    } 
  } 

  class Hive {
    public class Bee {
      . . . 
    }

    // Hive data fields here

    public override string ToString() { . . . }
    
    public Hive(int totalNumberBees, int numberInactive,
      int numberActive, int numberScout, int maxNumberVisits,
      int maxNumberCycles, CitiesData citiesData) {
      . . .      
    } 

    public char[] GenerateRandomMemoryMatrix() { . . . }
    
    public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) { . . . }
    
    public double MeasureOfQuality(char[] memoryMatrix) { . . . }
    
    public void Solve() { . . . }

    private void ProcessActiveBee(int i) { . . . }

    private void ProcessScoutBee(int i) { . . . }

    private void ProcessInactiveBee(int i) { . . . }

    private void DoWaggleDance(int i) { . . . }
  } 

  class CitiesData {
    . . .
  }

} // ns

Main メソッドはかなりシンプルです。次のように、開始メッセージを表示後、CitiesData オブジェクトのインスタンスを作成します。

Console.WriteLine(
  "Loading cities data for SBC Traveling Salesman Problem analysis");
CitiesData citiesData = new CitiesData(20);
Console.WriteLine(citiesData.ToString());
Console.WriteLine("Number of cities = " + citiesData.cities.Length);
Console.WriteLine("Number of possible paths = " + 
  citiesData.NumberOfPossiblePaths().ToString("#,###"));
Console.WriteLine("Best possible solution (shortest path) length = " + 
  citiesData.ShortestPathLength().ToString("F4"));

多くの SBC シナリオでは、問題のデータは、テキストファイルや SQL データベースなどの外部のストレージに存在するため、myProblemData.Load(dataFile) 行のところで、なんらかの読み込みコンストラクターか読み込みメソッドを通じてデータを読み込みます。

次に、Hive コンストラクターを準備して、呼び出します。

int totalNumberBees = 100;
int numberInactive = 20;
int numberActive = 50;
int numberScout = 30;
int maxNumberVisits = 100; 
int maxNumberCycles = 3460;
       
Hive hive = new TravelingSalesmanHive(totalNumberBees,
  numberInactive, numberActive, numberScout, maxNumberVisits,
  maxNumberCycles, citiesData);

この後詳しく説明しますが、SBC アルゴリズムは、能動的ミツバチ、受動的ミツバチ、偵察ミツバチの 3 種類のミツバチを使用します。これらの各種のミツバチの数はハードコーティングできますが、多くのシナリオでは、このような数は Hive コンストラクターへのパラメーターとして渡すことをお勧めします。そうすれば、パフォーマンスに合わせてアルゴリズムを簡単にチューニングできます。

totalNumberBees 変数の値は、別の 3 つの変数から導き出すことができますが、ここではコードの読みやすさを考え、このような余分な変数も用意しています。ミツバチの総数は、どのような問題を扱うかによって異なります。ミツバチの数が多い方が適切な回答を導き出せますが、実行速度が遅くなるというデメリットがあります。比率から言うと、能動的ミツバチ、受動的ミツバチ、偵察ミツバチの最適な割合は、だいたい 75%、10%、15% になることが多いという調査結果があります。

maxNumberVisits 変数に使用している 100 という値は、この後簡単に説明しますが、特定の解法に関連している、存在する近傍解の数に関連しています。

maxNumberCycles 変数は、Solve ルーチンが何回反復処理を行うかを制御するのに使用します。SBC アルゴリズムのシナリオでは、通常、最適解にたどり着くタイミングがわからないため、これは重要です (最適解がわかっていれば、もともと何の問題もありません)。今回の例では、SBC アルゴリズムが完全な結果を生成しないように、maxNumberCycles の値を 3,460 に制限しました。ここでのポイントは、SBC アルゴリズムは最適結果を生成するにもかかわらず、基本的に生成したかどうかはわからないため、単なる "良い" 結果しか得られないことを受け入れなければなりません。

コンストラクターが実行されると、それぞれランダムな解法を持つミツバチのコレクションが作成されます。Hive オブジェクトは、巣のミツバチによって見つけられた全体的に最適な (最短の) 経路と、最適解に関連する経路の長さを検出します。

Hive コンストラクターを呼び出した後、Main メソッドは、ToString メソッドを使用してランダムに生成された最初の Hive 値を表示します。次に、テキストベースの進行状況バーを出力すべきかどうかを指定するパラメーターを受け取る Solve メソッドを呼び出し、見つかった最短経路とその長さを表示して、完了します。

...
  Console.WriteLine("\nInitial random hive");
  Console.WriteLine(hive);

  bool doProgressBar = true;
  hive.Solve(doProgressBar);

  Console.WriteLine("\nFinal hive");
  Console.WriteLine(hive);
  Console.WriteLine("End Simulated Bee Colony demo");
}

Bee クラス

図 3 に示したように、Hive クラスには、Bee クラスを入れ子にして定義しています。この Bee クラス定義の詳細を図 4 に示します。

図 4 Bee クラス定義

public class Bee {
  public int status;
  public char[] memoryMatrix;
  public double measureOfQuality; 
  public int numberOfVisits;

  public Bee(int status, char[] memoryMatrix, 
    double measureOfQuality, int numberOfVisits) {
    this.status = status;
    this.memoryMatrix = new char[memoryMatrix.Length];
    Array.Copy(memoryMatrix, this.memoryMatrix, memoryMatrix.Length);
    this.measureOfQuality = measureOfQuality;
    this.numberOfVisits = numberOfVisits;
  }

  public override string ToString() {
    string s = "";
    s += "Status = " + this.status + "\n";
    s += " Memory = " + "\n";
    for (int i = 0; i < this.memoryMatrix.Length-1; ++i)
      s += this.memoryMatrix[i] + "->";
    s += this.memoryMatrix[this.memoryMatrix.Length-1] + "\n";
    s += " Quality = " + this.measureOfQuality.ToString("F4");
    s += " Number visits = " + this.numberOfVisits;
    return s;
  }
}

Bee クラスには、すべての SBC 実装に共通の 3 つのデータフィールドと、今回の問題固有の 1 つのデータフィールドがあります。問題固有のフィールドは memoryMatrix です。すべての SBC 実装には、解法を表すなんらかの方法が必要です。今回の TSP の場合、解法は char 型の配列によって表すことができます。解法を表すオブジェクトは、問題に強く依存していて、すべての問題は、意味のある解法の表現を生成するために個別に分析する必要があることを強調しておきます。

status というフィールドは、Bee オブジェクトの種類を表す int 値を保持します。0 が受動的ミツバチ、1 が能動的ミツバチ、2 が偵察ミツバチです。列挙型をサポートする言語でコーディングを行う場合は、status フィールドを列挙体としてリファクタリングすることをお勧めします。

measureOfQuality フィールドは、Bee オブジェクトの memoryMatrix の適性を表す double 値を保持します。TSP の場合、解法の適性の自然な測定値は、memoryMatrix オブジェクトによって表される経路の長さです。この状況では、短い経路は長い経路よりも優れているため、measureOfQuality フィールドの値が大きいよりも小さい方が、適切な解法を表していることになります。すべての SBC 実装には、解法の適性の測定を計算するなんらかの方法が必要です。多くの場合、この測定は、double 型の値で表すのが最適です。

Bee クラスの 3 つ目の共通のデータフィールドは numberOfVisits です。このフィールドは、Bee オブジェクトが、適切な近傍解は見つけていない状態で特定の食料源/問題の解法を訪れた数を表す int 値を保持し、食料源が尽きるまでその食料源を訪れるミツバチのシミュレーションを行うのに使用します。能動的ミツバチに関して言うと、numberOfVisits フィールドの値がしきい値を超えると、シミュレーションを行うミツバチが食料源を仮想的に使い果たし、受動的状態に移行します (そして、1 匹の受動的ミツバチが能動的状態に移行します)。

Bee コンストラクターは、status、memoryMatrix、measureOfQuality、および numberOfVisits の 4 つのデータフィールドの値を受け取ります。Bee コンストラクターは、measureOfQuality の値を memoryMatrix フィールドから直接計算できないため、measureOfQuality の値を受け取る必要があることに注意してください。適性の測定は、問題固有の CitiesData オブジェクトに格納されている情報に依存します。

Bee クラス定義には、4 つのデータフィールドの値を公開する ToString メソッドがあります。Bee.ToString メソッドは絶対に必要なわけではありませんが、SBC の開発中、WriteLine ステートメントを使用してバグを検出するのに非常に役立ちます。

Hive データフィールド

図 5 に Hive クラスコードを示します。ここには 14 個の Hive データフィールドがあります。具体的な SBC アルゴリズムの実装方法を理解するうえでは、各フィールドの目的を理解することが重要です。

図 5 14 個の Hive データフィールド

static Random random = null;

public CitiesData citiesData;

public int totalNumberBees; 
public int numberInactive; 
public int numberActive;
public int numberScout;

public int maxNumberCycles;
public int maxNumberVisits; 

public double probPersuasion = 0.90;
public double probMistake = 0.01; 

public Bee[] bees;
public char[] bestMemoryMatrix;
public double bestMeasureOfQuality;
public int[] indexesOfInactiveBees;

簡潔にするため、そして WriteLine ステートメントでのデバッグを容易にするため、14 個のデータフィールドをすべてパブリックスコープで定義しています。クラス定義の外部でアクセスする必要のあるフィールドは、フィールドをプライベートスコープに制限して、プロパティを作成します。

最初のフィールドは random で、Random 型の変数です。SBC アルゴリズムは確率的アルゴリズムなので、ランダムオブジェクトを使用して、複数の目的に擬似乱数を生成します。このランダムオブジェクトは、Hive コンストラクターでインスタンスを作成します。

2 つ目のデータフィールドは、CitiesData 型のオブジェクトです。SBC 実装は、解決対象の問題の詳細を把握する必要があります。多くの場合、このデータフィールドのように、問題のデータはオブジェクトとして表現します。CitiesData には都市ラベルの一覧と、2 つの都市間の距離を返すメソッドがあったことを思い出してください。

3 つ目～ 6 つ目のデータフィールドは、ミツバチの総数、受動的ミツバチの数、能動的ミツバチの数、および偵察ミツバチの数を保持する int 型の変数です。先ほど説明したように、各ミツバチは潜在的な解法を表すため、巣にミツバチが多いほど優れています。しかし、ミツバチの数が多いと、プログラムのパフォーマンスが低下します。

7 つ目のデータフィールドの maxNumberCycles は、Solve メソッドを実行する長さを制限するのに使用するしきい値です。1 サイクルは、巣の各ミツバチの処理を表します。

8 つ目のデータフィールドの maxNumberVisits は、ミツバチが特定の解法に長くとどまらないようにするために使用するしきい値です。Solve メソッドにおけるメイン処理ループのすべての反復処理では、ミツバチが近くにある食料源の品質を良いと判断しなかった場合、そのミツバチの numberOfVisits カウンターを増加します。Bee オブジェクト内の numberOfVisits のカウンターが maxNumberVisits しきい値を超えると、ミツバチは受動的状態に変化します。

9 つ目のデータフィールドの probPersuasion は、より適切な解法を巣に持ち帰ったミツバチの尻振りダンスを観察する受動的ミツバチに、メモリをその適切な解法で更新するかどうかを決定するのに使用する確率的しきい値です。

probPersuasion の値は 0.90 にハードコーディングしています。これは、受動的ミツバチに、活動時間の 90% は適切な解法を受け入れさせるということを表します。probPersuasion の 0.90 という値は、調査結果に基づくものですが、別の値でも試してみることをお勧めします。値が大きいと、より迅速に 1 つの解法に収束する SBC アルゴリズムが生成されますが、最適ではない解法に収束する可能性も高まります。

10 個目のデータフィールドの probMistake は、能動的ミツバチが間違いを犯す (つまり、ミツバチの現在の解法よりも適切である近傍解を誤って拒否したり、ミツバチの現在の解法よりも劣っている近傍解を誤って受け入れたりする) かどうかを判断するのに使用する確率的しきい値です。probMistake の値は 0.01 にハードコーディングしています。これは、能動的ミツバチが、活動時間の 1% は近傍解の評価に失敗することを表します。

11 個目のデータフィールドの bees は、Bee オブジェクトの配列です。ミツバチには、それぞれ、状態 (active、inactive、scout)、解法 (memoryMatrix)、解法の品質の測定 (measureOfQuality)、近くにある良い食料源を見つけていない状態で特定の仮想食料源に訪れた回数のカウンター (numberOfVisits) があることを思い出してください。Bee をクラスとして定義しているため、bees 配列の各エントリは Bee オブジェクトへの参照です。

12 個目のデータフィールドの bestMemoryMatrix は char型の配列で、bees 配列内の最適解法を表します。SBC アルゴリズムは、メタヒューリスティックの特殊な実装になるため、問題解決の表現は問題ごとに異なります。解法の種類の定義をハードコーディングする設計アプローチをとる場合は、このデータフィールドをジェネリック型としてパラメーター化します。SBC アルゴリズムを使用するときは、通常、特定の問題の解決を試みるため、それぞれの新しい SBC 実装を最初からコーディングし直すことをお勧めします。

13 個目のデータフィールドの bestMeasureOfQuality は、bestMemoryMatrix 解法に対応する品質の測定です。

最後の Hive データフィールドの indexesOfInactiveBees は、int 型の配列です。この配列は、現在受動的ミツバチの巣の中でのインデックスを保持します。能動的ミツバチは受動的状態に移行でき、受動的ミツバチは能動的状態に移行できます。SBC アルゴリズムの実装では、能動的ミツバチが仮想的な尻振りダンスを踊るときに、どのミツバチが現在受動的かを判断する必要があることがほとんどで、受動的ミツバチのインデックスを格納する方法は、bees 配列全体を反復処理して各ミツバチの status データフィールドを確認する方法よりもパフォーマンスが高くなります。

図 6 は、Hive オブジェクトとして可能性のある状態を仮想的に表現したものです。表示している巣には、10 匹のミツバチがいます。5 匹が能動的ミツバチ、2 匹が偵察ミツバチ、3 匹が受動的ミツバチです。現在の受動的ミツバチは、bees 配列の 2、7、4 です。CitiesData オブジェクトには 5 つの都市があります。現在の最適な解法は、次のとおりです。

A->B->E->C-D

この解法の経路は、次の距離になります。

1.0 + (3 * 1.0) + (2 * 1.5) + 1.0 = 8.0

citiesData フィールドは、Hive オブジェクトの外部で定義された CitiesData オブジェクトへの参照であることに注意してください。

巣の表現

図 6 巣の表現

Hive コンストラクター

図 7 に、Hive コンストラクターのコードを示します。Hive コンストラクターは、7 つの入力パラメーターを受け取ります。パラメーターのうち 6 つはスカラー値で、1 つはオブジェクト (citiesData) です。totalNumberBees パラメーターは、numberInactive、numberActive、および numberScout から定義できるという意味では冗長ですが、コードが読みやすくなるのであれば、余分なコードを追加する価値はあると考えます。

図 7 Hive コンストラクター

public Hive(int totalNumberBees, int numberInactive,
  int numberActive, int numberScout, int maxNumberVisits,
  int maxNumberCycles, CitiesData citiesData) {

  random = new Random(0);
      
  this.totalNumberBees = totalNumberBees;
  this.numberInactive = numberInactive;
  this.numberActive = numberActive;
  this.numberScout = numberScout;
  this.maxNumberVisits = maxNumberVisits;
  this.maxNumberCycles = maxNumberCycles;

  this.citiesData = citiesData;

  this.bees = new Bee[totalNumberBees];
  this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
  this.bestMeasureOfQuality = 
    MeasureOfQuality(this.bestMemoryMatrix);

  this.indexesOfInactiveBees = new int[numberInactive]; 

  for (int i = 0; i < totalNumberBees; ++i) {
    int currStatus; 
    if (i < numberInactive) {
      currStatus = 0; // inactive
      indexesOfInactiveBees[i] = i; 
    }
    else if (i < numberInactive + numberScout)
      currStatus = 2; // scout
    else
      currStatus = 1; // active
    
    char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
    double mq = MeasureOfQuality(randomMemoryMatrix);
    int numberOfVisits = 0;

    bees[i] = new Bee(currStatus, 
      randomMemoryMatrix, mq, numberOfVisits); 
        
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix, 
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    }
  } 
}

クラススコープのランダムオブジェクトは、シード値に 0 を指定してインスタンスを作成します。シード値を指定すると、同じ結果を再生成することができます。次に、スカラーデータフィールドの 6 つの入力パラメーターの値を、Hive データフィールドにコピーします。Hive オブジェクトには、総計 14 個のデータフィールドを用意し、しきい値の probPersuasion と probMistake はハードコーディングしています。

Hive コンストラクターは、citiesData 入力パラメーターを受け取り、citiesData フィールドを参照としてパラメーターに代入します。この参照によるアプローチを使用しない場合は、次のように、問題データのコピーを新しく作成するのも 1 つの方法です。

int n = citiesData.cities.Length;
this.citiesData = new CitiesData(n);

このアプローチは、より多くのメモリを使用しますが、副作用として起こり得るエラーを回避できます。こちらのアプローチでは、ここで表しているコードを、ポインターや参照をサポートしないプログラミング言語にリファクタリングする際に使用できます。

この時点の Hive コンストラクターでは、bees 配列のすべてのエントリが null です。次に、コンストラクターでは、グローバルな最適解法 (つまり、巣のすべてのミツバチの間で最適な解法) と、それに対応する解法の品質を初期化します。

this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
this.bestMeasureOfQuality = 
  MeasureOfQuality(this.bestMemoryMatrix);

GenerateRandomMemoryMatrix ヘルパーメソッドは、ランダムな解法を生成します。MeasureOfQuality ヘルパーメソッドは、ランダムに生成された解法を受け取って、その品質を計算します。これらの 2 つのヘルパーメソッドのコードは、この後説明します。

グローバルな最適解法とその対応する品質を初期化した後、Hive コンストラクターは、numberInactive フィールドの値を使用して、bees 配列の indexesOfInactiveBees を確保します。この時点では、このインデックス配列内のすべての値は 0 です。

コンストラクターコードの次の部分では、bees 配列内の各 Bee オブジェクトを反復処理し、Bee コンストラクターを使用して各オブジェクトのインスタンスを作成します。このループ内のロジックは、bees 配列内最初の numberInactive セルが受動的ミツバチ、次の numberScout セルが偵察ミツバチ、それ以外のセルが能動的ミツバチであると仮定しています。

たとえば、5 匹の能動的ミツバチ、2 匹の受動的ミツバチ、3 匹の偵察ミツバチがいるとすると、コンストラクターは bees 配列をサイズが 10 で初期化して、セル 0 と 1 を受動的ミツバチとして、セル 2 ～ 4 を偵察ミツバチとして、5 ～ 9 を能動的ミツバチとしてインスタンスを作成します。さらに、indexesOfInactiveBees 配列はサイズ 2 で、最初に 0 と 1 の値を保持します。

ミツバチの現在状態をループのインデックス変数に基づいて決定した後は、次のように、ランダム生成される解法の作成と、その対応する品質の計算を行います。訪問回数のカウンターを明示的に 0 に設定し、Bee コンストラクターを呼び出します。

char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
double mq = MeasureOfQuality(randomMemoryMatrix);
int numberOfVisits = 0;
bees[i] = new Bee(currStatus, randomMemoryMatrix, 
  mq, numberOfVisits);

各ミツバチのインスタンスを作成したら、各ミツバチのランダム生成した解法の品質が、グローバルな最適解法よりも優れているかどうかを確認します。現在のミツバチの解法の方が優れていたら、その解法と対応する品質を bestMemoryMatrix と bestMeasureOfQuality フィールドにコピーします。グローバルな最適解法の品質確認では、値が小さい方を優れているものとします。品質値は経路の長さで、TSP は経路の長さを最小限にすることが目的のためです。

ミツバチのメモリを bestMemoryMatrix 配列に明示的にコピーする方法以外に、参照によって代入を行うアプローチもあります。このアプローチによってパフォーマンスは向上しますが、複雑さも増します。

3 つの不可欠な SBC メソッド

すべての SBC アルゴリズムの実装には、問題固有の 3 つのメソッドが必要です。つまり、ランダムに解法を生成するメソッド、特定の解法に関連する近傍解を生成するメソッド、特定の解法の品質を計算するメソッドです。この TSP の例では、各メソッドが、完全に問題に依存するカスタム実装です。

インターフェイスを定義して、それらのインターフェイスを実装するという設計方法もあります。インターフェイスを通じてのプログラミングには、インターフェイス以外のアプローチと比べるとメリットとデメリットがありますが、ほとんどは個人の好みの問題だと考えます。次に、ランダムに解法を生成するメソッドの GenerateRandomMemoryMatrix を示します。

public char[] GenerateRandomMemoryMatrix() {
  char[] result = new char[this.citiesData.cities.Length];
  Array.Copy(this.citiesData.cities, result,
    this.citiesData.cities.Length);      
  for (int i = 0; i < result.Length; i++) {
    int r = random.Next(i, result.Length);
    char temp = result[r];
    result[r] = result[i];
    result[i] = temp;
  }
  return result;
}

TSP 問題の解法は、各 char が都市のラベルを表す char 型の配列なので、GenerateRandomMemoryMatrix メソッドは char の配列を返します。ローカルの結果配列のサイズは、Hive の CitiesData オブジェクトに基づいて確保し、Hive の CitiesData オブジェクトへの参照に格納される都市 ID を結果配列にコピーします。次に、クラススコープのランダムオブジェクトと、Fisher-Yates シャッフルアルゴリズム (Knuth のシャッフルと呼ばれることもあります) を使用して、結果配列での値の順番をランダムに決定します。

当初、GenerateRandomMemoryMatrix メソッドは概念的に Bee オブジェクトに属するように思えましたが、ランダム解法生成は、部分的に問題固有のデータ (ここでは CitiesData) に依存するため、ランダム解法生成メソッドを Hive 定義全体に配置する方が適切な設計です。

図 8 は、近傍解を生成するメソッドの GenerateNeighborMemoryMatrix です。

図 8 近傍解の生成

public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) {
  char[] result = new char[memoryMatrix.Length];
  Array.Copy(memoryMatrix, result, memoryMatrix.Length);

  int ranIndex = random.Next(0, result.Length);
  int adjIndex;
  if (ranIndex == result.Length - 1)
    adjIndex = 0;
  else
    adjIndex = ranIndex + 1;

  char tmp = result[ranIndex];
  result[ranIndex] = result[adjIndex];
  result[adjIndex] = tmp;  return result;
}

SBC アルゴリズムの重要な考え方は、仮想食料源がある種の近傍解を表すことです。近傍という概念がないと、ミツバチの行動に基づいたアルゴリズムの考え全体が崩れます。経路を表す都市 ID の配列で解法を表現できる TSP の場合、現在解法に関連する自然の近傍解は、隣接する 2 つの都市を交換した現在解法の順列になります。

たとえば、TSP の現在解法が A、B、C、D、E の場合、適切な近傍解は A、C、B、D、E です。隣接する 2 つの都市を交換するのではなく、任意の 2 つ都市を交換する順列が、適切な近傍解を表すかどうかはあまり明確ではありません。この例では、A、D、C、B、E は適切な近傍解なのでしょうか。SBC アルゴリズムの近傍解の定義は、問題に依存していて、通常、主観的基準が関与します。

また、近傍解の考え方は、数値でない組み合わせ問題が SBC アルゴリズムによる解法に特に適している理由を表しています。問題が本質的に数値の場合、近傍という考えは、十分に定義することが困難なのがほとんどです。問題が本質的に組み合わせの問題なら、近傍解の考えは、多くの場合において、なんらかの数学的な順列や組み合わせの形で適切に定義できます。

GenerateNeighborMemoryMatrix メソッドは、ミツバチの現在解法の memoryMatrix 表現を入力パラメーターとして受け取って、それを結果配列にコピーします。メソッドは、クラススコープのランダムオブジェクトを使用して、現在の結果配列に、1 つのランダムインデックスを選択します。ランダムインデックスが最後のセルを指す場合は、最初と最後の都市 ID を交換します。ランダムインデックスが最後以外のセルを指す場合、ランダムインデックスが指定する ID と、次のインデックスを交換します。

近傍解の考え方は、maxNumberVisits 値に関連しています。maxNumberVisits の適切な値は、あらゆる解法に有り得る近傍解の数の約 5 倍になるという調査結果があります。たとえば、3 つの都市 (A、B、C) がある場合、近傍解をあらゆる隣接する都市のペアの交換だと定義すると、有り得る近傍解が 3 つあることになります (A と B の交換、B と C の交換、A と C の交換)。このため、都市が 20 個ある場合、適切な maxNumberVisits の値は、約 20 * 5 = 100 です。

ミツバチの解法の品質を評価するメソッドの MeasureOfQuality を次に示します。

public double MeasureOfQuality(char[] memoryMatrix) {
  double answer = 0.0;
  for (int i = 0; i < memoryMatrix.Length - 1; ++i) {
    char c1 = memoryMatrix[i];
    char c2 = memoryMatrix[i + 1];
    double d = this.citiesData.Distance(c1, c2);
    answer += d;
  }
  return answer;
}

SBC アルゴリズムを使用して問題を解決するには、解決する問題の重要な特質として、解法品質の測定を生成するためにすべての解法を評価できなくてはなりません。概念的観点から言うと、実世界の組み合わせ最適化問題には、ほぼ確実に、なんらかの常識的な品質の測定が元から備わっています。ただし、実際的観点から言うと、解法の品質の測定を計算することは難しく、手間がかかります。

この例での MeasureOfQuality メソッドは、memoryMatrix パラメーターによって表される解法で、連続する都市 ID のすべてのペアを単に反復処理して、CitiesData オブジェクトの Distance メソッドを使用して各ペア間の距離を決定し、全距離を累積します。ここでは、2 つの都市 ID 間の普通の距離を使用するだけで、2 つの都市の距離をすばやく簡単に計算できるように、都市のデータを人口的に構築しています。しかし、実際的な問題として、2 つの都市間の距離は、ある種のデータ構造を照合する必要があることがほとんどです。SBC 実装での MeasureOfQuality メソッドは、プログラムの実行時間に影響を及ぼすルーチンになることがほとんどです。そのため、このメソッドのパフォーマンスが最適化されていること、そしてメソッドがホストシステムのリソースから考えて実行可能かどうかを確認することは、一般的に意味があります。

Solve メソッド

Solve メソッドは、問題解決のために探索ミツバチの行動のシミュレーションを行うすべてのロジックを保持します。Solve メソッドは適度に複雑で、ProcessActiveBee、ProcessScoutBee、および ProcessInactiveBee の 3 つのヘルパーメソッドを使用します。ProcessActiveBee メソッドと ProcessScoutBee メソッドは、DoWaggleDance ヘルパーメソッドを使用します。Solve メソッドを 図 9 に示します。

図 9 Solve メソッド

public void Solve(bool doProgressBar) {
  bool pb = doProgressBar;
  int numberOfSymbolsToPrint = 10; 
  int increment = this.maxNumberCycles / numberOfSymbolsToPrint;
  if (pb) Console.WriteLine("\nEntering SBC Traveling Salesman Problem algorithm main processing loop\n");
  if (pb) Console.WriteLine("Progress: |==========|");
  if (pb) Console.Write("           ");
  int cycle = 0;
      
  while (cycle < this.maxNumberCycles) {
    for (int i = 0; i < totalNumberBees; ++i) {
      if (this.bees[i].status == 1)
        ProcessActiveBee(i);
      else if (this.bees[i].status == 2)
        ProcessScoutBee(i);
      else if (this.bees[i].status == 0)
        ProcessInactiveBee(i);
    } 
    ++cycle;

    if (pb && cycle % increment == 0)
      Console.Write("^");
  } 

  if (pb) Console.WriteLine("");
}

実際の作業のほとんどは、ProcessActiveBee、ProcessScoutBee、および ProcessInactiveBee ヘルパーメソッドが担当します。ブール型の入力パラメーターは、初歩的なテキストベースの進行状況バーを出力するかどうかを示すために Solve メソッドに渡します。これは、実装の速度を監視してパフォーマンスボトルネックを明らかにする SBC アルゴリズムを開発するときに便利です。今回のアプローチは、Solve メソッドがコンソールアプリケーションの一部であると想定しています。

ブール型のパラメーター値は、pb というローカルブール型変数に転送します。この変数は、操作のために短い名前にしているだけです。状態バーにおける各増分値が、進行全体の 10% を表すように、numberOfSymbolsToPrint を 10 に設定します。各増分値は、maxNumberCycles 値から決定します (増分変数を使用して、10% の進捗とは何サイクルを表すか決定します)。

ループ制御変数の後、cycle を 0 に初期化します。これは、巣の各ミツバチを処理するのにループを使用する期間です。for ループは、簡単に使用できます。各サイクルでは、for ループを使用して bees 配列を反復処理し、各 Bee オブジェクトを適切なヘルパーメソッドによって処理します。各ミツバチを処理したら、ブール型の doProgressBar パラメーターが true の場合、剰余演算子 % を使用して、^ 文字を使用して進行状況バーに更新を出力するタイミングかどうかをチェックします。

ProcessActiveBee メソッド

ProcessActiveBee メソッドは、SBC アルゴリズムの心臓部で、コードのサイズと分岐の数の観点から言うと最も複雑なメソッドです。ProcessActiveBee メソッドを図 10 に示します。

図 10 ProcessActiveBee メソッド

private void ProcessActiveBee(int i) {
  char[] neighbor = GenerateNeighborMemoryMatrix(bees[i].memoryMatrix);
  double neighborQuality = MeasureOfQuality(neighbor); 
  double prob = random.NextDouble();
  bool memoryWasUpdated = false;
  bool numberOfVisitsOverLimit = false; 

  if (neighborQuality < bees[i].measureOfQuality) { // better
    if (prob < probMistake) { // mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
    else { // No mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0; 
      memoryWasUpdated = true; 
    }
  }
  else { // Did not find better neighbor
    if (prob < probMistake) { // Mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0;
      memoryWasUpdated = true; 
    }
    else { // No mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
  }

  if (numberOfVisitsOverLimit == true) {
    bees[i].status = 0; 
    bees[i].numberOfVisits = 0;
    int x = random.Next(numberInactive); 
    bees[indexesOfInactiveBees[x]].status = 1; 
    indexesOfInactiveBees[x] = i; 
  }
  else if (memoryWasUpdated == true) {
    if (bees[i].measureOfQuality < this.bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length); 
      this.bestMeasureOfQuality = bees[i].measureOfQuality
    }
    DoWaggleDance(i);
  }
  else {
    return;
  }
}

ProcessActiveBee メソッドは、bees 配列のミツバチのインデックス i を 1 つの入力パラメーターとして受け取ります。能動的ミツバチは、まず memoryMatrix に保存されている現在解法に関連する近傍解を取得して、その近傍解の品質を判断します。

char[] neighbor =
  GenerateNeighborMemoryMatrix(bees[i].memoryMatrix); 
double neighborQuality = MeasureOfQuality(neighbor);

次に、後から使用するローカルの変数を 3 つ設定します。

double prob = random.NextDouble();)
bool memoryWasUpdated = false; 
bool numberOfVisitsOverLimit = false;

prob 変数は 0.0 ～ 1.0 の値で、ミツバチが近傍解を誤って評価している (適切な近傍解を拒否しているか、品質の低い近傍解を受け取っている) かどうかを判断するために probMistake フィールド値と比較します。

ブール型の memoryWasUpdated 値は、能動的ミツバチが受動的ミツバチに尻振りダンスを踊るべきか (true) そうでないか (false) を判断するのに使用します。ブール型の numberOfVisitsOverLimit は、ミツバチが、適切な近傍解を見つけていないまま、特定の食料源を使い果たしてしまったかどうかを判断するために、maxNumberVisits フィールドと比べます。使い果たしてしまっている場合は、能動的状態から受動的状態に変換する必要があります。

現在のミツバチが適切な近傍解を見つけた場合、ミツバチが誤って適切な近傍解を拒否したか、適切な近傍解を受け入れたかどうかを判断します。同様に、現在のミツバチが適切な近傍解を見つけなかった場合、ミツバチが誤って不適切な近傍解を受け取ったか、その近傍解を適切に拒否したかどうかを判断します。

このように間違いには 2 とおりの種類がありますが、どちらの間違いにも同じ可能性があります (probMistake = 0.01)。2 種類の間違いに 2 種類の可能性を使用しても、SBC アルゴリズムの効率は良くならないという調査結果がありますが、2 つのしきい値を使用して試してみることをお勧めします。

現在のミツバチが近傍解を受け取ったか拒否した後、訪問回数カウンターが maxNumberVisits しきい値を超えたかどうかを確認します。超えている場合は、現在のミツバチの状態を inactive に変換し、ランダムに選択した受動的ミツバチを能動的状態に変換して、indexesOfInactiveBees 配列を更新します。次に、ミツバチのメモリを更新したかどうかを確認します。その場合、新しい解法が、新しいグローバルな最適解法であるかどうかをチェックし、巣に帰還して受動的ミツバチに新しい食料源についての情報を知らせるミツバチのシミュレーションを行うために、プライベートヘルパーメソッドの DoWaggleDance を呼び出します。

DoWaggleDance メソッド

DoWaggleDance ヘルパーメソッドは、巣に帰還して、食料源の場所と質についての情報を知らせるために受動的ミツバチに尻振りダンスを踊る能動的ミツバチまたは偵察ミツバチのシミュレーションを行います。次に DoWaggleDance メソッドを示します。

private void DoWaggleDance(int i) {
  for (int ii = 0; ii < numberInactive; ++ii) {
    int b = indexesOfInactiveBees[ii]; 
    if (bees[i].measureOfQuality < bees[b].measureOfQuality) {
      double p = random.NextDouble(); 
      if (this.probPersuasion > p) {
        Array.Copy(bees[i].memoryMatrix, bees[b].memoryMatrix,
          bees[i].memoryMatrix.Length);
        bees[b].measureOfQuality = bees[i].measureOfQuality;
      } 
    } 
  } 
}

入力パラメーター i は、仮想の尻振りダンスを踊る現在のミツバチのインデックスです。現在のミツバチの解法の質の測定を、受動的ミツバチの質の測定値と比較します。現在のミツバチの解法の方が優れていて、現在の受動的ミツバチのメモリを置き換える必要がある (可能性は probPersuasion = 0.90) 場合、現在のミツバチのメモリを受動的ミツバチのメモリにコピーします。

ここで紹介しているコードにエラーチェックを挿入する場所はたくさんあります。たとえば、DoWaggleDance の for ループ内では、現在の受動的ミツバチの状態をチェックできます。

if (bees[b].status != 0) throw new Exception(. . .);

また、受動的ミツバチの訪問回数カウンターをチェックすることもできます。

if (bees[b].numberOfVisits != 0) throw new Exception(. . .);

ProcessScoutBee と ProcessInactiveBee

Solve メソッドで使用する ProcessScoutBee ヘルパーメソッドは、魅力的な食料源をランダムに探す偵察ミツバチの行動のシミュレーションを行います。ProcessScoutBee メソッドを図 11 に示します。

図 11 ProcessScoutBee メソッド

private void ProcessScoutBee(int i) {
  char[] randomFoodSource = GenerateRandomMemoryMatrix();
  double randomFoodSourceQuality = 
    MeasureOfQuality(randomFoodSource);
  if (randomFoodSourceQuality < bees[i].measureOfQuality {
    Array.Copy(randomFoodSource, bees[i].memoryMatrix,
      randomFoodSource.Length);
    bees[i].measureOfQuality = randomFoodSourceQuality;
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    } 
    DoWaggleDance(i);
  }
}

入力パラメーター i は、bees 配列内の偵察ミツバチのインデックスを表します。偵察ミツバチは、解法をランダムに生成して、生成した解法がメモリ内の現在の解法よりも優れているかをチェックし、優れていた場合は生成した解法をメモリにコピーします。品質の値は、小さい方が優れています。偵察ミツバチが優れた解法を見つけた場合、新しい解法がグローバルな最適解法かどうかをチェックします。

能動的ミツバチとは異なり、この SBC 実装の偵察ミツバチは、食料源の質を評価するのに決して間違いは起こしません。偵察ミツバチの失敗の影響に関する調査は、現時点では存在しません。

ProcessInactiveBee メソッドを次に示します。

`private void ProcessInactiveBee(int i) {
  return;
}
private void ProcessInactiveBee(int i) {
  return;
}

この SBC 実装では、受動的ミツバチはまさに受動的なので、ProcessInactiveBee メソッドは、ある種の問題依存のロジックを受動的ミツバチに実装する場合の単なるプレースホルダーです。可能な変更の 1 つとして、受動的ミツバチのメモリを非常に低い可能性でランダムに変化させることなどが挙げられます。

まとめ

SBC アルゴリズムの実装のプロセス全体は、問題の特定から始まります。多くの場合、実用的な決定性解法がない、数値以外の複雑な組み合わせ最適化問題の解決には SBC が適しています。対象となる問題には、解法を表す方法 (多くの場合、配列か行列) が必要で、各解法には、ある種の近傍解と、解法の質の測定を含める必要があります。

たとえば、グラフを 2 つに分割する問題について考えてみます。分割の条件として、分割する 2 つの部分のそれぞれに含まれる接続の数を最大にし、2 つの各部分を相互につなぐ接続の数を最小限に抑えます。このようなグラフ分割の問題は、組み合わせの問題で、最適解法を迅速に見つけるアルゴリズムはありません (ただし、最適に近い解法を見つけることができる、決定性アルゴリズムはあります)。SBC を使用して取り組むことができる NP 完全問題および NP 困難問題は他にもたくさんあります。

SBC アルゴリズムは、自然体系の行動に基づいています。自然淘汰と進化に基づいた遺伝アルゴリズム (GA) や、蟻の行動に基づいた蟻コロニー最適化 (ACO)、および金属冷却の物理的性質に基づいた焼きなまし法 (SA) など、このようなアルゴリズムは他にもあります。

自然体系に基づくアルゴリズムは、決定性アプローチと比較して、多くの場合、実装が容易です。ただし、自然体系に基づくアルゴリズムは、通常、解法収束の速度と解法の精度に影響を及ぼしやすい、いくつかのパラメーター値を指定することが必要になります。SBC の場合、各種ミツバチの数、食料源が尽きるまでの最大訪問回数、受動的ミツバチが適切な解法でメモリを更新する必要がある可能性のしきい値、および能動的ミツバチが失敗する可能性が、各問題に対して適切に調整すべき、影響を及ぼしやすいパラメーターです。

SBC アルゴリズムはすべての問題に適用できるわけではありませんが、いくつかのシナリオにおいては、きわめて強力なツールになります。

Dr. James McCaffrey は Volt Information Sciences Inc. に勤務し、ワシントン州レドモンドにあるマイクロソフト本社で働くソフトウェアエンジニアの技術トレーニングを管理しています。これまでに、Internet Explorer、MSN サーチなどの複数のマイクロソフト製品にも携わってきました。また、『.NET Test Automation Recipes: A Problem-Solution Approach』(Apress、2006 年) の著者でもあります。連絡先は jammc@microsoft.com (英語のみ) です。

この記事のレビューに協力してくれた、Microsoft Research の技術スタッフの Dan Liebling と Anne Loomis Thompson に心より感謝いたします。

次の方法で共有

自然なアルゴリズム - 蜂コロニーのアルゴリズムを使用して困難な問題を解決する

ミツバチについて

巡回セールスマン問題

SBC プログラムの構造

Bee クラス

Hive データフィールド

Hive コンストラクター

3 つの不可欠な SBC メソッド

Solve メソッド

ProcessActiveBee メソッド

DoWaggleDance メソッド

ProcessScoutBee と ProcessInactiveBee

まとめ

その他のリソース

次の方法で共有

自然なアルゴリズム - 蜂コロニーのアルゴリズムを使用して困難な問題を解決する

ミツバチについて

巡回セールスマン問題

SBC プログラムの構造

Bee クラス

Hive データ フィールド

Hive コンストラクター

3 つの不可欠な SBC メソッド

Solve メソッド

ProcessActiveBee メソッド

DoWaggleDance メソッド

ProcessScoutBee と ProcessInactiveBee

まとめ

その他のリソース

Hive データフィールド