人工知能

  • [アーティクル]

粒子群最適化

James McCaffrey

コード サンプルのダウンロード

James McCaffrey粒子群最適化 (PSO: Particle Swarm Optimization) は人工知能 (AI) の技術で、解決が極めて困難または不可能に思える、数値の最大化および最小化問題の近似解法を見つけるために使用します。今回の記事で説明する PSO のバージョンは、J. Kennedy 氏と R. Eberhart 氏が 1995 年に発表した研究論文で初めて紹介されました。PSO は、鳥の群れや魚の群雄などのグループ行動に基づいて大まかにモデル化されます。PSO の感触をつかみ、この記事の目的を理解するため、まず図 1 をご覧ください。

この図の最初の部分は、PSO デモ プログラムで解決するダミーの問題です。f = 3 + x0^2 + x1^2 関数の値が最小になるような x0 と x1 の値を見つけることが目的です。ここで ^2 は、2 乗演算を表しています。PSO の概念をわかりやすくするために、あえて非現実的と思えるほど単純な問題を選びました。この問題の解は、関数の最小値 3.0 を返す、x0 = 0.0 と x1 = 0.0 であることは明らかなので、必ずしも PSO を使用する必要はありません。PSO で解決する、より現実的な問題については後ほど説明します。この例では、2 つの数値の解を求める必要があるため、最小値を求める関数は 2 次元です。一般に、PSO は多次元の数値に関する問題に適しています。ほとんどの場合、PSO では、x 値の可能性のある範囲についていくつか制約を設けます。ここでは、x0 と x1 の範囲を -100.0 ～ 100.0 に制限します。

Particle Swarm Optimization Demo Run

図 1 粒子群最適化のデモの実行

図 1 の次の部分は、PSO プログラムで 10 個の粒子を使用すること、およびプログラムを 1,000 回反復処理することを示しています。後ほど説明しますが、各粒子は、解決しようとしている PSO 問題の可能性のある解を表します。PSO は反復技法で、ほとんどの場合、どの時点で最適解が見つかるかはわかりません。そのため、通常、PSO アルゴリズムでは、実行する反復処理の回数に制限を設けます。

図 1 の次の行は、群れの中の 10 個の粒子をそれぞれランダムな位置に初期化することを示しています。粒子の位置は、解決する最適化問題の可能性のある解を表します。ランダムに生成する最初の最適位置は x0 = 26.53 と x1 = -6.09 です。この位置は、3 + 26.53^2 + (-6.09)^2 = 744.12 という適合度 (解精度の尺度) に対応しています。その後、PSO アルゴリズムはメインの処理ループに入り、ループを繰り返すたびに各粒子の位置を更新します。更新プロシージャは PSO の中核となるため、後ほど詳しく説明します。この PSO アルゴリズムでは、反復処理を 1,000 回実行した後、x0 = 0.0 と x1 = 0.0 という最適解を得ましたが、ほとんどの状況では、PSO プログラムで最適解が見つかったかどうかはわからないことを強調しておきます。

この記事では、PSO アルゴリズムについて詳しく説明し、図 1 に示している実行中のプログラムについて 1 行ずつ説明します。デモ プログラムのコードは C# で記述しましたが、ここで紹介するコードは Visual Basic、.NET、Python などの別の言語に簡単に適合させることができます。この記事で紹介するプログラムの全ソース コードは、code.msdn.microsoft.com/mag201108PSO (英語) からダウンロードできます。今回は、新しい手続き型言語の中級レベルのコーディング スキルが前提ですが、PSO や関連 AI 技術についての知識は必要ありません。

粒子

PSO を使用する場合、調査中の数値最適化問題の可能性のある解は粒子の位置で表されます。また、各粒子は現在の速度を保持します。この速度は、大きさと、より良いと思われる解または位置の方向を表します。さらに、粒子は現在位置の適合度の尺度、粒子の既知の最適位置 (つまり、既知の最適適合度を保持する前回の位置)、および既知の最適位置の適合度も保持します。Particle クラスのコードを図 2 に示します。

図 2 粒子の定義

public class Particle
{
  public double[] position;
  public double fitness;
  public double[] velocity;

  public double[] bestPosition;
  public double bestFitness;

  public Particle(double[] position, double fitness,
   double[] velocity, double[] bestPosition, double bestFitness)
  {
    this.position = new double[position.Length];
    position.CopyTo(this.position, 0);
    this.fitness = fitness;
    this.velocity = new double[velocity.Length];
    velocity.CopyTo(this.velocity, 0);
    this.bestPosition = new double[bestPosition.Length];
    bestPosition.CopyTo(this.bestPosition, 0);
    this.bestFitness = bestFitness;
  }

  public override string ToString()
  {
    string s = "";
    s += "==========================\n";
    s += "Position: ";
    for (int i = 0; i < this.position.Length; ++i)
      s += this.position[i].ToString("F2") + " ";
    s += "\n";
    s += "Fitness = " + this.fitness.ToString("F4") + "\n";
    s += "Velocity: ";
    for (int i = 0; i < this.velocity.Length; ++i)
      s += this.velocity[i].ToString("F2") + " ";
    s += "\n";
    s += "Best Position: ";
    for (int i = 0; i < this.bestPosition.Length; ++i)
      s += this.bestPosition[i].ToString("F2") + " ";
    s += "\n";
    s += "Best Fitness = " + this.bestFitness.ToString("F4") + "\n";
    s += "==========================\n";
    return s;
  }
} // class Particle

Particle クラスには、position、fitness、velocity、bestPosition、および bestFitness という 5 つのパブリック データ メンバーがあります。PSO を使用する場合、ここではわかりやすくするためにパブリック スコープのフィールドを使用していますが、get プロパティや set プロパティを備えたプライベート フィールドを使用してもかまいません。position フィールドは倍精度浮動小数点型の配列で、調査中の最適化問題の可能性のある解を表します。PSO を使用して数値以外の問題も解決できますが、一般に、PSO は数値問題を解決するのに最適です。fitness フィールドは、位置で表される解がどの程度最適解に近いかを示す尺度です。PSO で解決する最も一般的な種類の問題は最小化問題ですが、この問題の場合は fitness フィールドの値は小さい方がよく、最大化問題の場合は大きい方がよいことになります。

velocity フィールドは、倍精度浮動小数点型の配列で、粒子の現在位置 (解) を更新するために必要な情報を表します。粒子の速度については、後ほど詳しく説明します。Particle クラスの 4 つ目のフィールドは bestPosition で、5 つ目のフィールドは bestFitness です。これらのフィールドは、Particle オブジェクトで検出された最適位置 (解)、および最適位置に関連する尺度を保持します。

Particle クラスには、Particle クラスの 5 つのデータ フィールドに対応する 5 つのパラメーターを受け取る 1 つのコンストラクターがあります。このコンストラクターは、各パラメーター値を対応するデータ フィールドにコピーするだけです。Particle クラスの 5 つのフィールドはすべてパブリック スコープのため、PSO コードのコンストラクターを省略して、フィールド代入ステートメントを使用することもできましたが、コンストラクターを使用すると、コードが簡潔になります。

Particle クラス定義には、5 つのデータ フィールドの値をエコー出力する ToString メソッドがあります。コンストラクターと同様に、パブリック スコープの position、fitness、velocity、bestPosition、bestFitness という各フィールドを宣言したので、Particle オブジェクトの値を表示するために必ずしも ToString メソッドを使用する必要はありませんが、ToString メソッドを使用すると、フィールドの表示が簡単になり、開発中に WriteLine 形式のデバッグを行うのに役立ちます。必要に応じて、Microsoft .NET Framework ベースの言語以外の言語にコードをリファクタリングしやすいように、ToString メソッドでは、効率の高い StringBuilder クラスではなく、文字列の連結を使用しています。

PSO アルゴリズム

PSO アルゴリズムの本質はかなりシンプルですが、ここで紹介しているコードを自身のニーズに合わせて変更する場合は、PSO アルゴリズムについて完全に理解しておく必要があります。PSO は反復プロセスです。PSO メインの処理ループ内で反復処理を行うたびに、まず、粒子の現在速度、粒子のローカル情報、およびグローバルな群れの情報に基づいて、各粒子の現在速度を更新します。その後、粒子の新しい速度を使用して、各粒子の位置を更新します。数学表現では、これらの 2 つの更新方程式は次のようになります。

v(t+1) = (w * v(t)) + (c1 * r1 * (p(t) – x(t)) + (c2 * r2 * (g(t) – x(t))

x(t+1) = x(t) + v(t+1)

少し我慢してお付き合いください。位置の更新プロセスは、実際には上記の方程式よりはるかに単純です。1 つ目の方程式は、粒子の速度を更新します。項 v(t+1) は、時間 t+1 における速度を意味します。v を太字にしているのは、速度がベクトル値で、単一のスカラー値ではなく、{1.55, -0.33} といった複数の構成要素を保持することを示しています。新しい速度は、3 つの項によって決まります。第 1 項は w * v(t) です。w 因数は慣性質量と呼ばれ、0.73 のような単なる定数です (詳細については、後ほど説明します)。v(t) は時間 t における現在速度を意味します。第 2 項は c1 * r1 * (p(t) – x(t)) です。c1 因数は認識 (個人的またはローカル) 質量と呼ばれる定数です。r1 因数は [0, 1) 範囲内の確率変数で、0 以上かつ厳密に 1 未満になります。p(t) ベクトル値は、これまで検出した中で最適な粒子の位置を意味し、x(t) ベクトル値は、粒子の現在位置を意味します。速度更新方程式の第 3 項は、(c2 * r2 * (g(t) – x(t)) です。c2 因数は、社会的 (またはグローバル) 質量と呼ばれる定数です。r2 因数は、[0, 1) 範囲内の確率変数です。g(t) ベクトル値は、これまでに群れの中の粒子によって検出された位置の中で最適な位置を意味します。新しい速度 v(t+1) を特定すると、その値を使用して粒子の新しい位置 x(t+1) を計算します。

更新プロセスをわかりやすく示すために、具体的な例を紹介します。今回の冒頭で説明したように、3 + x0^2 + x1^2 を最小化するとします。図 3 は、この関数を座標で表したものです。外側の立方体の底部は値 x0 と x1 を表し、縦軸は関数値を表します。プロットの面は、x0 = 0 かつ x1 = 0 のときに f = 3 で最小になります。

Plot of f = 3 + x0^2 + x1^2

図 3 f = 3 + x0^2 + x1^2 のプロット

たとえば、粒子の現在位置 x(t) が {x0, x1} = {3.0, 4.0} で、粒子の現在速度 v(t) が {-1.0, -1.5} だとします。また、定数 w = 0.7、定数 c1 = 1.4、定数 c2 = 1.4 、乱数 r1 = 0.5、r2 = 0.6 とします。さらに、粒子の既知の最適位置は p(t) = {2.5, 3.6} で、群れの中の粒子が検出したグローバルな最適位置は g(t) = {2.3, 3.4} だとします。この場合、新しい速度と位置の値は次のようになります。

v(t+1) = (0.7 * {-1.0,-1.5}) +

         (1.4 * 0.5 * {2.5, 3.6} - {3.0, 4.0}) +

         (1.4 * 0.6 * {2.3, 3.4} – {3.0, 4.0})

       = {-0.70, -1.05} + {-0.35, -0.28} + {-0.59, -0.50}

       = {-1.64, -1.83}

x(t+1) = {3.0, 4.0} + {-1.64, -1.83}

       = {1.36, 2.17}

最適解は {x0, x1} = (0.0, 0.0} であることを思い出してください。更新プロセスによって、古い位置 (解) が (3.0, 4.0} から {1.36, 2.17} に改善されました。更新プロセスについて少し考えてみると、新しい速度は、古い速度 (*質量) に、粒子の既知の最適位置によって決まる関数、および群れの中のすべての粒子の既知の最適位置によって決まる別の関数を加算したものであることがわかります。そのため、粒子の新しい位置は、粒子の既知の最適位置およびすべての粒子の既知の最適位置に基づいて、より良い位置に移動する傾向があります。図 4 のグラフは、デモ PSO 実行の 1 回目から 8 回目までの反復処理における 1 つの粒子の移動を示しています。粒子は x0 = 100.0、x1 = 80.4 から、x0 = 0、x1 = 0 という最適解に向かって移動する傾向があります。このらせん状の動きは PSO の特色をよく示しています。

Particle Motion Toward Optimal Solution

図 4 最適解に向かう粒子の動き

PSO アルゴリズムの実装

図 5 は、プログラムの実行結果 (図 1 参照) を生み出した PSO プログラムの全体構造を示しています。Visual Studio を使用して、ParticleSwarmOptimization という名前の C# コンソール アプリケーション プロジェクトを作成しました。PSO コードはごく基本的なので、どのバージョンの .NET Framework (1.1 ～ 4) でもうまく機能します。中核となる System 名前空間への参照を除いて、Visual Studio が生成するすべての using ステートメントを削除します。Random 型のクラス スコープ オブジェクトを宣言して、前述の認識乱数と社会的乱数を生成します。また、Random オブジェクトを使用して、ランダムな初期速度と各 Particle オブジェクトの位置を生成します。例外をキャッチするため、Main メソッド内の高いレベルの 1 つの try ステートメントにすべてのコードをラップします。

図 5 PSO プログラムの構造

using System;
namespace ParticleSwarmOptimization
{
  class Program
  {
    static Random ran = null;
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin PSO demo\n");
        ran = new Random(0);

        int numberParticles = 10;
        int numberIterations = 1000;
        int iteration = 0;
        int Dim = 2; // dimensions
        double minX = -100.0;
        double maxX = 100.0;

        Particle[] swarm = new Particle[numberParticles];
        double[] bestGlobalPosition = new double[Dim];
        double bestGlobalFitness = double.MaxValue; 

        double minV = -1.0 * maxX;
        double maxV = maxX;

        // Initialize all Particle objects

        double w = 0.729; // inertia weight
        double c1 = 1.49445; // cognitive weight
        double c2 = 1.49445; // social weight
        double r1, r2; // randomizations

        // Main processing loop

        // Display results
        Console.WriteLine("\nEnd PSO demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal error: " + ex.Message);
      }
    } // Main()

    static double ObjectiveFunction(double[] x)
    {
      return 3.0 + (x[0] * x[0]) + (x[1] * x[1]);
    }

  } // class Program

  public class Particle
  {
    // Definition here 
  }

} // ns

0 という任意のシード値を使用して Random オブジェクトのインスタンスを作成後、次のように、いくつかの重要な PSO 値を初期化します。

int numberParticles = 10;
int numberIterations = 1000;
int iteration = 0;
int Dim = 2;
double minX = -100.0;
double maxX = 100.0;

10 個の Particle オブジェクトを使用します。経験から言って、Particle オブジェクトは少ないより多い方が適切な解を得られますが、数が増えるほどプログラムのパフォーマンスが大きく低下する可能性があります。メインの処理ループの反復処理回数を 1,000 に設定します。使用する反復処理回数は、最適化する問題の複雑さと、ホスト コンピューターの処理能力によって異なります。通常、PSO プログラムでは 1,000 ～ 100,000 の値を使用します。iteration という変数は、メイン ループの反復処理回数を追跡するカウンター変数です。Dim 変数には、位置 (解) の x 値の数を格納します。サンプル問題では、3 + x0^2 + x1^2 を最小化する x0 と x1 を見つける必要があるため、Dim を 2 に設定しました。前述のとおり、PSO のほとんどの状況では、位置 (解) ベクトルを構成する x 値を、問題によって決まる範囲に制限することをお勧めします。制限を設けないと、事実上、double.MinValue から double.MaxValue までを検索することになります。ここでは、x0 と x1 を [-100.0, +100.0] に制限しています。

次に、粒子群のインスタンスを作成する準備をします。

Particle[] swarm = new Particle[numberParticles];
double[] bestGlobalPosition = new double[Dim];
double bestGlobalFitness = double.MaxValue; 
double minV = -1.0 * maxX;
double maxV = maxX;

swarm という名前で Particle オブジェクトの配列を作成します。また、Particle オブジェクトによって特定される、グローバルな既知の最適位置 (アルゴリズム内では g(t) で示します)、およびその位置配列の対応する適合度を保持する配列の設定も行います。さらに、新しい速度の最大値および最小値の定数を設定します。ここで紹介する考え方では、新しい速度によって粒子の新しい位置が特定されるため、速度コンポーネントの大きさは大きくなりすぎないようにします。

群れを初期化するコードは、次のとおりです。

for (int i = 0; i < swarm.Length; ++i)
{ 
  double[] randomPosition = new double[Dim];
  for (int j = 0; j < randomPosition.Length; ++j) {
    double lo = minX;
    double hi = maxX;
    randomPosition[j] = (hi - lo) * ran.NextDouble() + lo; 
  }
...

swarm 配列内の各 Particle オブジェクトを反復処理します。現在の Particle オブジェクトのランダムな位置を保持する、サイズ Dim の配列を宣言します。その後、位置の x 値ごとに、minX (-100.0) ～ maxX (+100.0) のランダム値を生成します。多くの現実的な PSO 問題では、各 x 値の範囲が異なるため、位置配列内の各 x 値を個別に処理するコードを追加する必要があります。

では、初期化プロセスを続行します。

double fitness = ObjectiveFunction(randomPosition);
double[] randomVelocity = new double[Dim];
for (int j = 0; j < randomVelocity.Length; ++j) {
  double lo = -1.0 * Math.Abs(maxX - minX);
  double hi = Math.Abs(maxX - minX);
  randomVelocity[j] = (hi - lo) * ran.NextDouble() + lo;
}
swarm[i] = new Particle(randomPosition, fitness, randomVelocity,
  randomPosition, fitness);
...

まず、ObjectiveFunction メソッドに現在のランダムな位置配列を渡して、その配列の精度を計算します。図 5 を見直してみると、ObjectiveFunction メソッドは、最小化を試みている関数の値 (つまり、3 + x0^2 + x1^2) を計算するだけであることがわかります。次に、現在の Particle オブジェクトのランダムな速度を計算します。ランダムな位置、およびランダムな位置とランダムな速度の適合度がわかったら、それらの値を Particle コンストラクターに渡します。4 つ目のパラメーターは粒子の既知の最適位置で、5 つ目のパラメーターはそれに関連する適合度なので、Particle オブジェクトを初期化する場合、初期のランダム位置と適合度は既知の最適値になります。

群れの初期化コードの最後は、次のようになります。

...
  if (swarm[i].fitness < bestGlobalFitness) {
    bestGlobalFitness = swarm[i].fitness;
    swarm[i].position.CopyTo(bestGlobalPosition, 0);
  }
} // End initialization loop

現在の Particle オブジェクトの適合度が、これまで検出した中で最適な適合度 (最小化問題の場合は、最小の適合度) かどうかを確認します。最適な適合度であれば、bestGlobalPosition 配列、および対応する bestGlobalPosition 変数を更新します。

次に、メインの PSO 処理ループに入る準備をします。

double w = 0.729; // inertia weight
double c1 = 1.49445; // cognitive weight
double c2 = 1.49445; // social weight
double r1, r2; // randomizers

w の値 (慣性質量) を 0.729 に設定します。この値は、一連のベンチマーク最小化問題に対するさまざまな PSO パラメーター値の効果を調査した研究論文で推奨された値です。他には、w の値を 1 つの定数値にするのではなく、変化させる方法もあります。たとえば、PSO アルゴリズムが反復処理を 10,000 回実行するように設定されている場合、最初に w を 0.90 に設定し、反復処理を 2,000 回実行するごとに w の値を 0.10 ずつ減らして、段階的に 0.40 まで減らすことができます。動的な w の考え方は、アルゴリズムの最初のうちは、位置のより大きな変化を調べますが、後になるにつれて粒子の移動は小さい方が好ましくなるというものです。c1 と c2 両方の値 (認識質量と社会的質量) を 1.49445 に設定します。繰り返しになりますが、この値も研究論文での推奨値です。c1 の値を c2 の値より大きい値に設定する場合は、群れのグローバルな既知の最適位置よりも粒子の既知の最適位置に重き置きます。その逆も同様です。確率変数 r1 および r2 は、PSO アルゴリズムにランダムなコンポーネントを追加し、アルゴリズムがローカルの最適ではない最小解または最大解にとどまらないようにすることができます。

次に、メインの PSO 処理ループを開始します。

for (int i = 0; i < swarm.Length; ++i) 
{
  Particle currP= swarm[i];
            
  for (int j = 0; j < currP.velocity.Length; ++j) 
  {
    r1 = ran.NextDouble();
    r2 = ran.NextDouble();

    newVelocity[j] = (w * currP.velocity[j]) +
      (c1 * r1* (currP.bestPosition[j] - currP.position[j])) +
      (c2 * r2 * (bestGlobalPosition[j] - currP.position[j]));
    ...

インデックス変数 i を使用して、swarm 配列内の各 swarm オブジェクトを反復処理します。コードを簡潔にするために、currP という現在の Particle オブジェクトへの参照を作成しますが、直接 swarm[i] を使用することもできます。前述のように、まず、各粒子の速度ベクトルを更新します。現在の Particle オブジェクトについては、オブジェクトの速度配列内の値をそれぞれ見ていき、確率変数 r1 および r2 を生成して、各速度コンポーネントを更新します。

現在の Particle オブジェクトの新しい速度コンポーネントを計算後、次のように、そのコンポーネントが速度コンポーネントの最小値と最大値の間にあるかどうかを確認します。

if (newVelocity[j] < minV)
    newVelocity[j] = minV;
  else if (newVelocity[j] > maxV)
    newVelocity[j] = maxV;
} // each j
newVelocity.CopyTo(currP.velocity, 0);
...

コンポーネントが範囲外になったら、範囲内に戻します。ここでの考え方では、速度コンポーネントが最大値を超える値だと新しい位置が範囲外になる可能性があるため、最大値を超える値は避けます。すべての速度コンポーネントを計算後、手軽な .NET CopyTo メソッドを使用して、現在の Particle オブジェクトの速度配列を更新します。

現在の Particle オブジェクトの速度を特定したら、次のように、新しい速度を使用して現在の Particle オブジェクトの位置を計算および更新します。

for (int j = 0; j < currP.position.Length; ++j)
{
  newPosition[j] = currP.position[j] + newVelocity[j];
  if (newPosition[j] < minX)
    newPosition[j] = minX;
  else if (newPosition[j] > maxX)
    newPosition[j] = maxX;
}
newPosition.CopyTo(currP.position, 0);
...

再び範囲チェックを実行します。今回は、現在の粒子の新しい位置コンポーネントそれｘぞれに対して実行します。各速度コンポーネントの値に既に制約を加えているため、これはある意味、冗長なチェックになりますが、ここでは追加チェックを行うに値する、というのが個人的な意見です。

これで、現在の Particle オブジェクトの新しい位置がわかったので、次のように、新しい適合度値を計算し、オブジェクトの適合度フィールドを更新します。

newFitness = ObjectiveFunction(newPosition);
    currP.fitness = newFitness;

    if (newFitness < currP.bestFitness) {
      newPosition.CopyTo(currP.bestPosition, 0);
      currP.bestFitness = newFitness;
    }
    if (newFitness < bestGlobalFitness) {
      newPosition.CopyTo(bestGlobalPosition, 0);
      bestGlobalFitness = newFitness;
    }

  } // each Particle
} // main PSO loop
...

現在の粒子を更新後、新しい位置がその粒子の既知の最適位置かどうかを確認します。また、新しい位置が群れのグローバルな最適位置かどうかも確認します。論理的には、ローカルの最適位置がある場合にのみ、グローバルな新しい最適位置が存在できるため、ローカルの最適位置チェック内部にグローバルな最適位置チェックを入れ子にすることができます。

ここで、次のように、メインの PSO アルゴリズム ループが終了し、結果を表示できます。

Console.WriteLine("\nProcessing complete");
    Console.Write("Final best fitness = ");
    Console.WriteLine(bestGlobalFitness.ToString("F4"));
    Console.WriteLine("Best position/solution:");
    for (int i = 0; i < bestGlobalPosition.Length; ++i){
      Console.Write("x" + i + " = " );
      Console.WriteLine(bestGlobalPosition[i].ToString("F4") + " ");
    }
    Console.WriteLine("");
    Console.WriteLine("\nEnd PSO demonstration\n");
  }
  catch (Exception ex)
  {
    Console.WriteLine("Fatal error: " + ex.Message);
  }
} // Main()

拡張と変更

ここまでは、基本の PSO を記述する方法を見てきました。ここからは、紹介したコードを拡張および変更する方法について説明しましょう。ここで解決したサンプル問題は、問題を正確に解決できるため、近似解法を見つけるために PSO を使用する必要はないという意味で人工的と言えます。PSO が真に役立つのは、調査中の数値に関する問題を標準の技法を使用して解くことが極めて困難または不可能な場合です。次の問題について考えてみましょう。チーム A 対 B のアメリカン フットボール試合の得点を予想するとします。チーム A と B が以前に他のチームと対戦した結果を示す履歴データがあるとします。チーム X の履歴評点を数学的にモデル化します。その方法は、チーム X が勝利したら、チームの評点をある固定値 (たとえば、16 点) だけ上げ、対戦チームとの評点の違いに応じて別の値を加算する (たとえば、チーム X の評点が対戦チームより低い場合は 0.04 倍にする) という方法です。さらに、チームが何点差で勝利するかを予想し、チームの評点の違いの関数としてモデル化します。たとえば、チーム X の評点が 1,720 で、チーム Y の評点が 1,620 の場合、X が勝利する場合の対戦チームとの評点の差は 3.5 点であると予想されます。つまり、大量のデータがあるため、予想エラーを最小化する数値 (16 や 0.04 など) をいくつか指定する必要があります。このデータ主導のパラメーター推定は、PSO が適している種類の問題です。

PSO は、自然体系の行動に基づくいくつかの AI 技術の 1 つにすぎません。おそらく、PSO アルゴリズムに最も近い技術は遺伝アルゴリズム (GA) でしょう。どちらの技術も、解決が困難な数値問題に適しています。GA は、数十年に渡って幅広く研究されています。PSO が GA よりも優れている点は、PSO アルゴリズムの方が GA よりも大幅に簡単に実装できることです。PSO が GA より多少優れているか、ほぼ同じであるかは、今のところはっきりとしていません。

ここで紹介したバージョンの PSO は、さまざまな方法で変更できます。特に興味深い変更として、グローバルな群れではなく、粒子のいくつか部分的な群れを使用することが挙げられます。そのように設計すると、各粒子が部分的な群れに属し、粒子の新しい速度は 3 つではなく 4 つの項によって決まります。4 つの項とは、古い速度、粒子の既知の最適位置、部分的な群れの中の任意の粒子の既知の最適位置、および任意の粒子の既知の最適位置です。この部分的な群れの設計という考え方を利用すると、PSO アルゴリズムが最適ではない解に陥る可能性が減少します。私が知っている限り、このような設計はまだ研究の余地があります。

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

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