2016-11-17

November 2016

Volume 31 Number 11

テストの実行 - 組み合わせ進化によって数独を解く

James McCaffrey 組み合わせ最適化問題は、一連の不連続の項目を特定の順番に並び変えることを目的とするものです。数独パズルは、組み合わせ最適化問題の一例です。この記事では、組み合わせ進化という手法を使用して、難しい数独の問題を解くプログラムの作成方法について説明します。

今回のデモでは、簡単でない数独の問題を取り上げます ("簡単でない" の意味については、この後説明します)。数独には、いくつかの制約があります。9x9 の解答グリッドの各行には、1 ～ 9 の数字を重複せずに含める必要があります。また、各列にも 1 ～ 9 の数字を含める必要があります。さらに、3x3 の小グリッドにも 1 ～ 9 の数字を含める必要があります。解答グリッドでは、問題グリッド内の初期値を変更できません。

デモの問題を、図 1 に示します。一部の数独の問題は、空のセルをそれぞれ調べ、行、列、および小グリッドの制約を確かめて、適切に配置できる値を探すという総当たりアルゴリズムで解くことができます。配置できる値が 1 つしか考えられない場合のみ、その値を空のセルに配置します。このプロセスを、すべての空のセルが埋まるまで続けます。"簡単でない" タイプの数独の問題というのは、新聞や雑誌でよく見られる問題です。

図 1 簡単でない数独の問題

デモの問題は、総当たりアルゴリズムが通用しないため、簡単ではありません。問題グリッドを左から右、上から下に見てみましょう。(0, 0) の空のセルには、1、3、5、7、9 のいずれかが入ります。(0, 1) の空のセルには、1、3、9 のいずれかが入ります。次の空のセルは (0, 4) にあり、ここには 3 しか配置できないため、3 を入れて続けます。しかし、このアプローチでは、9 個の値を入れると、残りセルにはどれも 2 つ以上の値が入りうるため、手詰まりになってしまいます。

組み合わせ進化による最適化について理解するために、図 2 のスクリーンショットをご覧ください。組み合わせ進化による最適化では、生物学に影響を受けた複数のアルゴリズムから得た考え方を使用します。このアルゴリズムは、仮想生物の個体の集合を保持します。各個体は、考えられる問題の解を示します。組み合わせ進化は反復的なプロセスです。それぞれの反復を、"エポック" と呼びます。各エポックでは、すべての個体が、可能な新しい解を調査して、より優れた解を得ようと試みます。

図 2 組み合わせ進化によって数独を解く

すべての個体により優れた解を得る機会が与えられた後、2 つの優れた個体の解が選択され、新しい個体を誕生させるのに使用されます。新しい個体は、劣る解に取って代わります。こうして、個体の集団は時間とともに進化します。最適解が一定の maxEpochs 時間後に見つからなければ、アルゴリズムがすべての個体を破棄し、新しい集団を作成して再開します。

デモでは 200 体の仮想個体および 5,000 エポックの時間制限が設定されています。これらの値は、多少の試行錯誤を行って決定されました。組み合わせ進化で最適解が見つかる保証はありません。そのため、無限ループが生じないよう、再開回数が 20 回に制限されています。

デモプログラムでは 3 回目の再開後に最適解が見つかりました。筆者のデスクトップ PC では、これに約 8 秒かかりました。デモの実行中、プログラムは最も優れた個体のエラー数を表示します。エラーが定義されて計算される仕組みについては、関連コードを示す際に説明します。ただし、アルゴリズムでとても優れた解 (エラー = 2) を非常に早く見つけても、その後は手詰まりになる傾向がある点には注意が必要です。再開プロセスはこの特性に対処するためのメカニズムの 1 つで、多くの最適化アルゴリズムでよく使われる手法です。

デモプログラム

デモプログラムを作成するには、Visual Studio を起動し、[ファイル] メニューの [新規作成] をポイントし、[プロジェクト] をクリックして、C# コンソールアプリケーションオプションを選択します。プロジェクトには SudokuEvo という名前を付けます。このデモプログラムは .NET との大きな依存関係がないため、どのバージョンの Visual Studio でも機能します。テンプレートコードを読み込んだ後、ソリューションエクスプローラーウィンドウで Program.cs ファイルを右クリックして、名前を SudokuEvoProgram.c に変更します。また、Program クラスの名前が Visual Studio によて自動で変更されることを許可します。

エディターウィンドウの上部で、不要な using ステートメントをすべて削除し、System 名前空間および Collections.Generic 名前空間を参照する using ステートメントだけを残します。少し編集したプログラムの全体構造を図 3 に示します。デモプログラムは長すぎてここにすべて掲載することはできませんが、完全なデモのソースコードはこの記事付属のダウンロードから入手できます。

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

using System;
using System.Collections.Generic;
namespace SudokuEvo
{
  class SudokuEvoProgram
  {
    static Random rnd = new Random(0);
    static void Main(string[] args)
    {
      Console.WriteLine("Begin solving Sudoku");
      Console.WriteLine("The problem is: ");
      int[][] problem = new int[9][];
      problem[0] = new int[] { 0, 0, 6, 2, 0, 0, 0, 8, 0 };
      problem[1] = new int[] { 0, 0, 8, 9, 7, 0, 0, 0, 0 };
      problem[2] = new int[] { 0, 0, 4, 8, 1, 0, 5, 0, 0 };
      problem[3] = new int[] { 0, 0, 0, 0, 6, 0, 0, 0, 2 };
      problem[4] = new int[] { 0, 7, 0, 0, 0, 0, 0, 3, 0 };
      problem[5] = new int[] { 6, 0, 0, 0, 5, 0, 0, 0, 0 };
      problem[6] = new int[] { 0, 0, 2, 0, 4, 7, 1, 0, 0 };
      problem[7] = new int[] { 0, 0, 3, 0, 2, 8, 4, 0, 0 };
      problem[8] = new int[] { 0, 5, 0, 0, 0, 1, 2, 0, 0 };
      DisplayMatrix(problem);
      int numOrganisms = 200;
      int maxEpochs = 5000;
      int maxRestarts = 20;
      int[][] soln = Solve(problem, numOrganisms,
        maxEpochs, maxRestarts);
      Console.WriteLine("Best solution found: ");
      DisplayMatrix(soln);
      int err = Error(soln);
      if (err == 0)
        Console.WriteLine("Success \n");
      else
        Console.WriteLine("Did not find optimal solution \n");
      Console.WriteLine("End Sudoku demo");
      Console.ReadLine();
    } // Main()
    public static int[][] Solve(int[][] problem,
      int numOrganisms, int maxEpochs, int maxRestarts) { . . }
    public static void DisplayMatrix(int[][] matrix) { . . }
    public static int[][] SolveEvo(int[][] problem,
      int numOrganisms, int maxEpochs) { . . }
    public static int[][] RandomMatrix(int[][] problem) { . . }
    public static int[] Corner(int block) { . . }
    public static int Block(int r, int c) { . . }
    public static int[][] NeighborMatrix(int[][] problem,
      int[][] matrix)
    public static int[][] MergeMatrices(int[][] m1,
      int[][] m2) { . . }
    public static int Error(int[][] matrix) { . . }
    public static int[][] DuplicateMatrix(int[][] matrix) { . . }
    public static int[][] CreateMatrix(int n) { . . }
  } // Program
  public class Organism
  {
    public int type;  // 0 = worker, 1 = explorer
    public int[][] matrix;
    public int error;
    public int age;
    public Organism(int type, int[][] m, int error, int age)
    {
      this.type = type;
      this.matrix = SudokuEvoProgram.DuplicateMatrix(m);
      this.error = error;
      this.age = age;
    }
  }
} // ns

メソッドの多くは短いヘルパーメソッドのため、デモプログラムは一見して感じるほど複雑ではありません。デモには 2 つのクラスがあります。メインクラスには、静的メソッドとして実装されるコードロジックがすべて含まれます。Organism クラスは、対象の数独問題に対して考えられる解を定義します。

それぞれの Organism オブジェクトは、"worker (労働担当)" 個体は 0、"explorer (探索担当)" 個体は 1 で表わされる型を持ちます。matrix という名前のフィールドは、考えられる解を表す配列の配列形式の整数の行列です。考えられる解にはそれぞれエラーがあり、エラーの値が 0 の場合は制約違反がないことを意味するため、matrix フィールドは最適解を保持します。各 Organism オブジェクトには、個体がエポックごとに死ぬかどうかを制御する age フィールドがあります。

デモプログラムは、以下のステートメントを使用して数独問題を設定および表示します。

int[][] problem = new int[9][];
problem[0] = new int[] { 0, 0, 6, 2, 0, 0, 0, 8, 0 };
...
problem[8] = new int[] { 0, 5, 0, 0, 0, 1, 2, 0, 0 };
DisplayMatrix(problem);

値 0 で空のセルを示している点に注意してください。この手動のハードコーディングされたアプローチは非常に退屈です。最も現実的な組み合わせ最適化問題では、テキストファイルから問題のデータを読み取ります。

数独問題は、以下のステートメントを使用して取り組みます。

int numOrganisms = 200;
int maxEpochs = 5000;
int maxRestarts = 20;
int[][] soln = Solve(problem, numOrganisms, maxEpochs, maxRestarts);
Console.WriteLine("Best solution found: ");
DisplayMatrix(soln);

Solve メソッドは主として、ほとんどの作業を行う SolveEvo メソッドのラッパーです。これは組み合わせ最適化における一般的な設計パターンです。ある低レベルのソルバーメソッドが最適解の特定を試み、そのメソッドは再開を実行するより高レベルなソルバーメソッドによってラップされます。

組み合わせ進化アルゴリズムでは最適解 (制約のエラーのない解) が見つかる保証がないため、デモプログラムでは見つかった最も優れた解が最適かどうかをチェックして判別します。

int err = Error(soln);
if (err == 0)
  Console.WriteLine("Success");
else
  Console.WriteLine("Did not find optimal solution");

行列の初期化とエラー

個人的な意見では、組み合わせ進化による最適化を理解する近道は、最初にヘルパーメソッドを調べることです。ヘルパーがわかると、解法は比較的簡単です。最初に、Organism オブジェクトの matrix フィールドをランダムな解候補に初期化する RandomMatrix メソッドについて説明します。少し驚くかもしれませんが、RandomMatrix メソッドは、アルゴリズム全体の中で最も複雑な部分です。

図 4 に、RandomMatrix メソッドの定義を示します。

図 4 RandomMatrix メソッドの定義

public static int[][] RandomMatrix(int[][] problem)
{
  int[][] result = DuplicateMatrix(problem);
  for (int block = 0; block < 9; ++block) {
    // Create a List with values 1-9
    // Shuffle the values in List
    // Walk through each cell in current block
    // If a cell is occupied, remove that value from List
    // Walk through each cell in current block
    // If cell is empty, add value from List
  }
  return result;
}

このアルゴリズムは、あらゆる時点で、3x3 の小グリッドのセルに 1 ～ 9 の数字がそれぞれ含まれており、値の重複がないという意味で 9 個の小グリッドがどれも問題ないように設計されています。常に真である条件は、不変条件と呼ばれることがあります。この不変条件は、アルゴリズムのその他すべてのメソッドに影響します。理論上、行の制約または列の制約を不変条件として使用することができますが、実際には小グリッドの制約を使用するのがより有効です。

概念的には、9x9 の行列内の各 3x3 の小グリッドを処理することは難しくありませんが、実装はやや複雑です。この記事では、Block と Corner という 2 つのヘルパーメソッドを定義します。Block メソッドは行のインデックス r と列のインデックス c を受け取り、(r, c) のセルを保持するブロック番号 (0 ～ 8) を返します。ブロック番号は左から右方向に、上の行から下の行の順に割り当てられます。たとえば、(r, c) が (3, 8) の場合、Block メソッドは 5 を返します。

Corner メソッドはブロックの ID (0 ～ 8) を受け取り、ブロックの左上の角のインデックスを返します。たとえば、ブロックが 8 の場合、Corner メソッドは (6, 6) を返します。

行列の9 個の 3x3 小グリッドそれぞれに問題がないことがわかれば、エラーを定義する比較的シンプルなメソッドを定義できます。

public static int Error(int[][] matrix)
{
  int err = 0;
  for (int i = 0; i < 9; ++i) {  // Each row
    // Determine missing values in row
    // Add 1 to err for each missing value
  }
  for (int j = 0; j < 9; ++j) {  // each column
    // Determine missing values in column
    // Add 1 to err for each missing value
  }
  return err;
}

つまり、考えられる解の総エラー数は、行に不足している値の数と列に不足している値の数の合計です。アルゴリズムの不変条件から、すべての 3x3 小グリッドに不足している値は存在しないため、グリッドはエラーの原因にはなりません。各行および列で重複している値の数をカウントするのは、不足している値の数をカウントするのと同じです。

近隣行列を生成する

組み合わせ進化には、2 種類の Organism オブジェクトがあります。explorer 型の Organism オブジェクトは、RandomMatrix メソッドを使用して考えられる解をランダムに検索します。worker 型の Organism オブジェクトは、近い "近傍" 解を調べることで、matrix フィールドに格納されている解よりも優れた解を得ようと繰り返し試行します。

3x3 の小グリッドの不変条件により、近傍解は、小グリッドの順列に限定されなければなりません。より具体的に言うと、アルゴリズムは近傍行列を特定するために、ランダムにブロックを選択した後、そのブロック内の 2 つのセル (どちらのセルも問題の定義時の固定値を含まない) を選択し、その 2 セルの値を交換します。

NeighborMatrix メソッドは次のように定義されます。

public static int[][] NeighborMatrix(int[][] problem, int[][] matrix)
{
  int[][] result = DuplicateMatrix(matrix);
  int block = rnd.Next(0, 9);  // pick a random block
  // Determine which cells have values that can be swapped
  // Pick two of those cells: (r1,c1) and (r2,c2)
  int tmp = result[r1][c1];
  result[r1][c1] = result[r2][c2];
  result[r2][c2] = tmp;
  return result;
}

今回のデモプログラムでは、rnd という名前のクラススコープの Random オブジェクトが存在することを前提としています。この設計は、多くの最適化アルゴリズムでよく用いられます。近傍解の生成という考え方は、焼きなまし法最適化や疑似ハチコロニー最適化など、複数の組み合わせ最適化アルゴリズムで見られます。

2 つの行列をマージする

組み合わせ進化による最適化アルゴリズムは、2 つの優れた (matrix フィールドのエラーが少ない) Organism オブジェクトを選ぶことで仮想個体の形を実装した後、そのオブジェクトを使用して新しい子オブジェクトを作成します。非常に優れていると考えられる新しい子 Organism は、劣った Organism に取って代わります。

MergeMatrices は、2 つの 9x9 の行列を 2 つの Organism オブジェクトから受け取ります。このメソッドはブロック 0 ～ 8 をスキャンします。各ブロックに対して、0.0 ～ 1.0 のランダム値が生成されます。ランダム値が 0.50 より低い場合 (つまり、ほぼ 2 回に 1 回) は、2 つのブロックの値が入れ替えられます。コードは次のようになります。

public static int[][] MergeMatrices(int[][] m1, int[][] m2)
{
  int[][] result = DuplicateMatrix(m1);
  for (int block = 0; block < 9; ++block) {
    double pr = rnd.NextDouble();
    if (pr < 0.50) {
      // Replace values in block of m1 with those in m2    
    }
  }
  return result;
}

この進化的メカニズムは、遺伝的アルゴリズムで使用される交差メカニズムに少し似ています。

SolveEvo メソッド

最も優先されるアルゴリズムは、SolveEvo メソッドに実装されています。このメソッドは、コードとおおまかな疑似コードの組み合わせて説明するのが最もわかりやすいでしょう (図 5 参照)。

図 5 SolveEvo メソッドに実装された主要なアルゴリズム

public static int[][] SolveEvo(int[][] problem,
  int numOrganisms, int maxEpochs)
{
  int numWorker = (int)(numOrganisms * 0.90);
  int numExplorer = numOrganisms - numWorker;
  Organism[] hive = new Organism[numOrganisms];
  // Initialize each Organism
  int epoch = 0;
  while (epoch < maxEpochs) {
    for (int i = 0; i < numOrganisms; ++i) {
      // Process each Organism
    }
    // Merge best worker with best explorer, increment epoch
  }
  return bestMatrix;
}

このメソッドではまず、worker Organism オブジェクトの数を使用されるオブジェクト総数の 90% として決定します。この値は、試行錯誤の結果決めたものです。Organism オブジェクトは、hive という名前の配列に格納されます。

worker 型の Organism オブジェクトを処理する疑似コードは、以下のようになります。

generate a neighbor matrix
if neighbor is better (or Organism makes mistake)
  update matrix with neighbor
  reset age to 0
else
  don't update matrix
  increment age
end-if

このアルゴリズムでは、0.1% の確率で、Organism オブジェクトに対して、オブジェクトの現在の解よりも悪い近傍解を受け取るよう指示します。これは、アルゴリズムが非最適解から抜け出しやすくなることを目的とした、一般的な最適化手法です。

反復ループにおける各エポックでは、explorer 型の各 Organism が、ランダムな解答グリッドを生成します。Organism オブジェクトがそれぞれ処理を完了した後、新しい Organism が作成されます。疑似コードは次のとおりです。

determine index of best worker Organism
determine index of best explorer Organism
create new Organism using best worker and best explorer
determine index of worst worker Organism
replace worst worker with new child Organism

結局のところ、この進化的メカニズムは、アルゴリズムが成功するためには欠かせません。進化がなければ、アルゴリズムが失敗することがありますが、進化があれば、インターネットで見つかる超難問を含む難しい数独問題を、この記事で紹介したようにすべて正しく解くことができます。ただし、組み合わせ最適化は研究解析されたことがないため、組み合わせ進化で数独問題を解けることは、組み合わせ進化で任意の組み合わせ最適化問題を解けることの保証にはなりません。

まとめ

この記事で説明した組み合わせ進化アルゴリズムは、実際にはアルゴリズムではありません。組み合わせ進化はメタヒューリスティックです。つまり、組み合わせ進化は、特定の最適化問題を解決するための具体的なアルゴリズムの設計に使用できる一連の一般的なガイドラインです。

通常の作業環境で数独問題を解く必要に迫られることはないでしょうが、組み合わせ最適化は、実世界の問題解決にも使用できます。組み合わせ進化で重要な考え方は、目標となる問題を示すデータ構造を定義すること、ランダム解の意味を定義すること、近傍解を定義すること、およびエラーのメトリックを定義することです。これらのパズルのピースを正しい場所にはめれば、従来のアルゴリズムでは解けない多くの問題を、組み合わせ進化を使用してすばやく効率的に解くことができます。

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

この記事のレビューに協力してくれたマイクロソフト技術スタッフの Chris Lee および Kirk Olynyk に心より感謝いたします。