發行項
02/02/2017

2016 年 11 月

第 31 卷，第 11 期

本文章是由機器翻譯。

測試回合 - 使用組合演化解出數獨

James McCaffrey 針對最佳化問題是其中一個目標是一組特定的項目放入特定的順序。數獨謎題是針對最佳化問題的範例。本文中，我告訴您如何撰寫程式來解決艱難的數獨問題，我呼叫組合的發展一種技術。

示範設定非簡單的數獨問題（我會說明我的意思由非簡單短時間內）。在數獨，有數個條件約束。9 x 9 方案方格的每個資料列必須包含 1 到 9 的數字，而且沒有重複。每個資料行必須包含 1 到 9 的數字。每一個 3x3 子方格必須包含 1 到 9 的數字。而且方案方格無法變更任何問題方格中的起始值。

示範問題示 [圖 1。使用您用來檢查方格，看看哪些值可以合法放在這裡的檢查資料列、資料行和子資料格的條件約束中每個空白資料格的暴力密碼破解演算法可以解決一些數獨問題。如果只有一個值是可行的這個值會置於空資料格。處理序會繼續，直到已指派給所有的空資料格。這些非簡單類型的數獨問題是通常報紙與雜誌中找到。

非簡單的數獨問題
[圖 1] 非簡單數獨問題

示範問題是非簡單，因為暴力演算法無法運作。假設您掃描問題方格從左到右，然後再往前。在空白的儲存格（0，0）可以是其中一個（1、 3、 5、 9）。在空白的儲存格（0，1）可以是其中一個（1、 3、 9）。在下一個空白儲存格（0，4）只能是 3，因此您可以將 3 該處並繼續。不過，使用這種方式，在將放九個值之後，您會取得卡所有剩下的儲存格可能是兩個或多個值。

若要了解的是何種組合的演化最佳化，看看螢幕擷取畫面中 [圖 2。針對演化最佳化會使用數種簡歷啟發演算法的想法。此演算法會維護虛擬生態的集合。每個生物表示問題可能的解決方案。組合的發展是一種反覆的程序。每個反覆項目會呼叫的期間。在每個期間，每個生物會嘗試尋找更好的解決方案，藉由檢查新的可能解決方案。

[圖 2 獨使用組合的發展

所有生態都有機會來改善之後，會選取兩個不錯的生物解決方案，而且用來提供 birth 至新的生物，取代不佳的解決方案。讓長時間的發展生態的母體擴展。如果找不到某些 maxEpochs 時間之後的最佳解決方案，此演算法會重新啟動終止所有生態並建立新的擴展。

示範設定 200 虛擬生態和 5000 epoch 時間限制。透過反覆嘗試一些找不到這些值。針對發展並不保證會找出最佳化的解決方案，以便限制為 20 的重新啟動已設定，以防止可能的無限迴圈。

示範程式需要在我的桌上型電腦上執行的大約 8 秒的三個重新啟動後找到最好的解決方案。示範執行時，程式會顯示錯誤的最佳生物的量值。我將說明如何定義及計算當我提出的相關程式碼錯誤。但請注意，此演算法通常取得很好的解決方案 (錯誤 = 2) 非常快速，但然後卡住。重新啟動程序是一項機制來對抗這項特性，常用的技巧，在許多最佳化演算法。

示範程式

若要建立示範程式，我啟動 Visual Studio 中，按一下 [檔案 |新 |專案，然後選取 [C# 主控台應用程式] 選項。我命名為 SudokuEvo 的專案。示範程式有沒有顯著的.NET 相依性，因此任何版本的 Visual Studio 將運作。在 [方案總管] 視窗中，範本程式碼載入之後我以滑鼠右鍵按一下檔案 Program.cs 和重新命名了 SudokuEvoProgram.cs，允許 Visual Studio 會自動重新命名為我的類別程式。

在編輯器視窗的頂端，我刪除所有不必要 using 陳述式，讓系統和 Collections.Generic 命名空間的只是參考。少數的次要編輯程式的整體結構所示 [圖 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

示範程式並不那麼複雜，因為它可能會先出現，因為許多方法都是簡短的 helper 方法。示範具有兩個類別。主要的類別已實作做為靜態方法中的程式碼邏輯。生物類別定義的目標數獨問題可能的解決方案。

每個生物物件具有類型，可為「總管」生物的「背景工作」生物，0 或 1。名為矩陣的欄位是整數陣列的陣列樣式矩陣，表示可能的解決方案。每個可能的解決方案有錯誤，其中 0 表示沒有條件約束會違反了，因此，[矩陣] 欄位的錯誤值保存最好的解決方案。每個生物物件有時間欄位，來控制是否生物無作用中每個事件。

示範程式設定，並顯示使用這些陳述式的數獨問題︰

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);

解決方法是工作的大部分的包裝函式方法 SolveEvo，完成大部分。這是常見的設計模式中針對最佳化 — 一種低階的求解器方法會嘗試尋找最佳的解決方案，並執行重新啟動的高階規劃求解方法包裝該方法。

針對發展演算法並不一定能夠找出最好的解決方案（也就是解決方案，沒有任何條件約束錯誤），因此示範程式會檢查以判斷是否找到的最佳解決方案是最佳作法︰

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

矩陣初始化和錯誤

在我看來，了解針對演化最佳化的最佳方式是先檢查的 helper 方法。一旦了解協助程式，解決方法是相當容易理解。讓我開始說明方法 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，而且沒有重複的值。一定是 true 的條件通常稱為非變異值。此恆定性影響演算法的所有其他方法。理論上，資料列的條件約束或資料行條件約束可能已經已做為非變異值，但實際上使用的子格線條件約束會更有效率。

就概念而言，每個 3x3 的逐步解說 9 x 9 矩陣中的子格線不深入，但實作稍微難處理。我的方法是定義兩個 helper 方法，區塊和角。方法區塊接受以 r 的資料列索引和資料行索引 c，並傳回保存 (r、 c) 處的儲存格的區塊數字 (0-8)。左到右，然後上到下，會指派區塊數字。例如，如果 (r、 c) = 3 (8）則區塊方法會傳回 5。

角方法接受的區塊識別碼 (0-8)，並傳回區塊上限左上角的索引。例如，如果區塊 = 8，方法角傳回（6，6）。

一旦知道每九個 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;
}

中的字，可能的解決方案的錯誤總數是資料列中的遺漏值的數目再加上資料行中的遺漏值的數目總和。演算法而異，因為所有的 3 x 3 子方格有沒有遺漏值，因此它們不造成錯誤。請注意，計算的次數重複在每個資料列和資料行的值相當於計算遺漏值的數目。

產生一個芳鄰矩陣

在組合的發展，有兩種生物物件。項目類型可能的解決方案總管] 中搜尋隨機，使用 RandomMatrix 方法。生物的物件類型的背景工作重複試著找出更好的解決方案，藉由檢查 [關閉]，儲存在其 [矩陣] 欄位中，「介面上的「可行的解決方案。

3 x 3 子格線恆定性，因為芳鄰方案必須限制本身成為子方格的排列。更具體而言，將決定芳鄰矩陣中，演算法選取區塊，隨機]，然後在區塊中（未儲存格包含從問題定義為固定的值），選取兩個儲存格和交換兩個儲存格的值。

定義方法 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 物件存在這項設計是通常在許多最佳化演算法。在數種組合最佳化演算法，例如，模擬鍛鍊最佳化和模擬的蜂群蟻群最佳化中找到產生芳鄰方案的概念。

合併兩個矩陣

針對發展最佳化演算法實作一種虛擬的發展選取兩個很好生物物件（亦即它們有小錯誤的矩陣欄位），然後使用這些良好的物件建立新的子物件。新的大概是很理想，子生物取代不佳的生物。

MergeMatrices 方法接受兩個 9 x 9 的矩陣，從兩個生物物件。方法會掃描透過區塊 0 到 8。每個區塊，會產生介於 0.0 到 1.0 之間的隨機值。如果隨機值低於 0.50 (亦即，大約一半的時間)，然後交換兩個區塊中的值。程式碼是︰

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;
}

此進化的機制是有點類似基因演算法所用的 chromosome 交叉機制。

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;
}

這個方法一開始藉由判斷使用的總次數的 90%的背景工作生物物件數目。透過反覆嘗試偵測到此值。生物物件會儲存在名為 hive 的陣列。

處理背景工作類型生物的虛擬程式碼是︰

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.001) 會接受物件的目前方案最糟的鄰居解決方案生物物件的指示。這是常見的最佳化策略，旨在協助遇從非最佳方案的演算法。

在反覆項目迴圈中每個期間，每個檔案總管類型生物會產生隨機方案方格。每個生物物件經過處理之後，會建立新的生物。虛擬程式碼︰

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 適用於在美國華盛頓州 Redmond 的 Microsoft Research 他曾在數個 Microsoft 產品，包括 Internet Explorer 和 Bing。Dr。可以連線到 McCaffrey jammc@microsoft.com。

感謝下列 Microsoft 技術專家檢閱這份文件︰ Chris Lee 和 Kirk Olynyk