• 發行項

本文章是由機器翻譯。

測試運行

模擬鍛鍊與測試

James McCaffrey

在本月的專欄中，我介紹 C# 代碼實現類比退火 (SA) 演算法解決調度問題的。SA 演算法是一種基於行為的冷卻金屬的人工智慧技術。它可用於查找困難或不可能的組合優化問題的解決辦法。

看到我駛向哪裡的最佳方法是看看圖 1 和圖 2。表中的圖 1 調度問題描述：五名工人和六個任務。每個表中的條目表示多長時間完成任務的一名工人。例如，工人 w2 需要完成任務 t3 5.5 小時。在一行中的空項指示對應的工人不能執行某項任務。問題是要將每個六個任務分配給一個工人才能完成所有任務的總時間最小化的一種。此外，我們假定每次工作執行緒將切換到新的任務，有 3.5 小時 retooling 懲罰。

圖 1 為完成任務的工作的時間

  t0 t1 t2 t3 t4 t5
w0 7.5 3.5 2.5      
w1   1.5 4.5 3.5    
w2     3.5 5.5 3.5  
w3       6.5 1.5 4.5
先行 2.5       2.5 2.5

SimulatedAnnealing in Action
圖 2 SimulatedAnnealing 在行動**

圖 2 演示程式，它使用 SA 演算法來查找一個調度問題的解決方案。程式開始通過生成一個隨機的解決方案。在 SA 術語中，一個可能的解決方案稱為系統的狀態。初始狀態是 [4 0 0 2 2 3]，這意味著任務 0 已分配給任務 1 4，工人已分配給工人 0，2 任務已分配給工人 0、 3 任務已分配給工人 2、 4 任務已分配給工人 2 和 5 任務已分配給工人 3。隨機的初始狀態的總時間是 2.5 + 3.5 + 2.5 + 5.5 + 3.5 + 4.5 = 22 小時加上工人 0 retooling 罰款 3.5 小時和 3.5 小時工 2，共有 29 個小時的罰則。在 SA 術語中，你想最小化 （或少最大化） 的數量稱為能量的狀態。

該程式進入迴圈。在每次迴圈反覆運算，SA 演算法生成一個相鄰的國家，並評估該相鄰狀態以查看它是否比的當前狀態。在幕後，SA 演算法使用溫度變數，慢慢的下降，我稍後會解釋。SA 迴圈結束時溫度冷卻足夠接近于零。該程式最後顯示找到最佳的解決方案。

這個例子是人工簡單六任務執行每個任務的地方由三名工人之一，僅有 36 可能的組合，因為這等於 729，所以你可能只是評估每一個人。但是，假設您有 20 個任務的問題，可以由 12 名工人之一執行每個任務。會有 1220年組合，這等於高達 3,833,759,992,447,475,122,176。即使您可以評估每秒 1 萬可能的解決方案，您需要約 121 億年評估所有的可能性。

SA 是元啟發 — — 就是一個總概念框架，可用於創建特定的演算法，以解決特定的問題。它最適合用組合優化問題有沒有實際的確定性演算法的地方。S.1983年檔在首次描述C.柯克派翠克蓋拉特和 M。Vecchi、 SA 是嚴格基於退火冷卻金屬的行為。當某些金屬被加熱到高溫時，原子和分子打破他們的債券。當慢慢冷卻金屬時，原子和分子改革能量系統的最小化的一種債券。

此列假定您擁有中級的程式設計技巧。我實現 SA 程式使用的 C# 中，但你不應該有太多的麻煩，我以一種不同的語言如 Visual Basic 或 Python 代碼重構。在下麵幾節，我陪你走的生成程式通過圖 2。所有的代碼是可從下載 archive.msdn.microsoft.com/mag201201TestRun。我想你會發現能夠理解和使用 SA 有趣且可能有用的附加到您個人的技能集。

程式結構

我作為一個 C# 主控台應用程式實現 SA 演示計畫。整體結構化程式所示圖 3。

圖 3 SimulatedAnnealing 程式結構

using System;
namespace SimulatedAnnealing
{
  class SimulatedAnnealingProgram
  {
    static Random random;
    static void Main(string[] args)
    {
      try
      {
        // Set up problem data.
// Create random state.
// Set up SA variables for temperature and cooling rate.
while (iteration < maxIteration && currTemp > 0.0001)
        {
          // Create adjacent state.
// Compute energy of adjacent state.
// Check if adjacent state is new best.
// If adjacent state better, accept state with varying probability.
// Decrease temperature and increase iteration counter.
}
        // Display best state found.
}
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
        Console.ReadLine();
      }
    } // Main
    static double[][] MakeProblemData(int numWorkers, int numTasks) { ...
}
    static int[] RandomState(double[][] problemData) { ...
}
    static int[] AdjacentState(int[] currState,
      double[][] problemData) { ...
}
    static double Energy(int[] state, double[][] problemData) { ...
}
    static double AcceptanceProb(double energy, double adjEnergy,
      double currTemp) { ...
}
    static void Display(double[][] matrix) { ...
}
    static void Display(int[] vector) { ...
}
    static void Interpret(int[] state, double[][] problemData) { ...
}
  } // Program
} // ns

我用 Visual Studio 創建一個名為 SimulatedAnnealing 的主控台應用程式。 在解決方案資源管理器視窗中，我命名為 SimulatedAnnealingProgram.cs，其中自動重命名專案中的單個類的預設的 program.cs，然後從檔。 已刪除所有範本生成使用除外的 System 命名空間的聲明 — — SA 非常簡單，通常不需要多庫支援。 我聲明一個類範圍隨機物件命名隨機。 SA 演算法是概率，你很快就會看到。

SA 演算法處理的核心是一段時間迴圈。 名為"反覆運算"迴圈計數器變數，變數，它表示系統的溫度控制迴圈。 在實踐中，溫度變數幾乎總是達到接近于零，並終止迴圈之前迴圈計數器達到其最大值和終止迴圈。

SA 演算法必須有三個特定問題的方法，所建議的圖3。 SA 演算法必須在初始的 （通常是隨機的） 狀態/解決方案生成的一種方法。 SA 演算法必須生成給定狀態相對於鄰近國家的一種方法。 SA 演算法必須有一種方法，計算能耗的狀態 — — 你想最小化或最大化的價值。 在圖 3 這些都是鄰近的方法 RandomState，­狀態和能量，分別。 AcceptanceProb 方法生成一個值，用於確定是否系統的當前狀態轉換到相鄰國家即使相鄰國家比的當前狀態。 方法 MakeProblemData 是一名傭工和創建一個資料結構矩陣與對應的圖 1。 要顯示的資訊只是傭工重載的顯示方法和解釋方法。

程式初始化

Main 方法開始像這樣：

try
{
  Console.WriteLine("\nBegin Simulated Annealing demo\n");
  Console.WriteLine("Worker 0 can do Task 0 (7.5) Task 1 (3.5) Task 2 (2.5)");
  Console.WriteLine("Worker 1 can do Task 1 (1.5) Task 2 (4.5) Task 3 (3.5)");
  Console.WriteLine("Worker 2 can do Task 2 (3.5) Task 3 (5.5) Task 4 (3.5)");
  Console.WriteLine("Worker 3 can do Task 3 (6.5) Task 4 (1.5) Task 5 (4.5)");
  Console.WriteLine("Worker 4 can do Task 0 (2.5) Task 4 (2.5) Task 5 (2.5)");
 ...

在單一的、 高層次的 try catch 塊中換行 SA 的所有代碼，並顯示的虛擬的問題，我打算成立。在這裡，我使用人工簡單的例子 — — 只有一種適合的解決方案的 SA 演算法的組合問題的代表。接下來是：

random = new Random(0);
int numWorkers = 5;
int numTasks = 6;
double[][] problemData = MakeProblemData(numWorkers, numTasks);

使用任意的種子值為 0 的隨機物件初始化。 然後我請説明器方法來構造中顯示的資料結構的 MakeProblemData 圖 1。 完呈現在 Main 方法中的所有代碼，我會提出 MakeProblemData 和其他説明器方法。 接下來是：

int[] state = RandomState(problemData);
double energy = Energy(state, problemData);
int[] bestState = state;
double bestEnergy = energy;
int[] adjState;
double adjEnergy;

我請説明器方法來生成一個隨機的國家 RandomState /­解決問題。 作為一個 int 陣列的陣列索引代表一項任務，該索引處的陣列中的值表示分配給該任務的工人代表國家。 説明器方法能量計算其狀態參數，考慮到 3.5 小時的罰則更換設備每次的工人不會額外任務所需的總時間。 我會跟蹤找到最佳狀態和其相應的能源，所以我聲明變數 bestState 和 bestEngery。 變數 adjState 和 adjEnergy 用於保存的國家是相鄰的當前狀態，並相應的能源。 接下來是：

int iteration = 0;
int maxIteration = 1000000;
double currTemp = 10000.0;
double alpha = 0.995;

SA 處理回路終止對兩個條件之一：當計數器超過最大值或溫度變數減少到一個值接近為零。 我叫迴圈計數器"反覆運算"，但我可以叫它"計數器"或"時間"或"刻度"或類似的東西。 我的名字溫度變 currTemp 而不是臨時的所以不太可能有人檢查代碼可能解釋它作為一個臨時變數。 變數的 alpha 代表冷卻速度，或一個因素，以確定如何降低溫度的變數或冷卻，每次處理迴圈。 接下來是：

Console.WriteLine("\nInitial state:");
Display(state);
Console.WriteLine("Initial energy: " + energy.ToString("F2"));
Console.WriteLine("\nEntering main Simulated Annealing loop");
Console.WriteLine("Initial temperature = " + currTemp.ToString("F1") + "\n");

進入主處理迴圈之前, 顯示初始狀態、 能量和溫度的一些資訊性的消息。 您可能希望顯示附加資訊如冷卻速度。 這裡是迴圈：

while (iteration < maxIteration && currTemp > 0.0001)
{
  adjState = AdjacentState(state, problemData);
  adjEnergy = Energy(adjState, problemData);
  if (adjEnergy < bestEnergy)
  {
    bestState = adjState;
    bestEnergy = adjEnergy;
    Console.WriteLine("New best state found:");
    Display(bestState);
    Console.WriteLine("Energy = " + bestEnergy.ToString("F2") + "\n");
  }
...

請注意閉環控制退出時的溫度變數滴眼液 0.0001 下麵而不是當它為 0.0。 您可能要參數化的最低溫度值。 創建相鄰的狀態，並計算其能量之後, 我檢查，看看這個相鄰的國家就是一個新的全球最佳解決方案，如果我這樣保存該資訊。 我可以通過引用複製最佳狀態，因為方法 AdjacentState 分配一個新的陣列，但可能已經作出明確的副本。 每當發現一種新的全球最佳狀態，顯示它和它的能量。 主要加工迴圈結束，像這樣：

double p = random.NextDouble();
  if (AcceptanceProb(energy, adjEnergy, currTemp) > p)
  {
    state = adjState;
    energy = adjEnergy;
  }
  currTemp = currTemp * alpha;
  ++iteration;
} // While

迴圈完成首次生成隨機值大於或等於 0.0 和嚴格小於 1.0 p 並將針對從 AcceptanceProb 的説明器方法返回的值進行比較。 如果接受概率超過隨機值，當前狀態轉換為相鄰狀態。 接下來，當前溫度輕微下跌，乘以的冷卻的因素，並迴圈計數器變數遞增的。 接下來是：

Console.Write("Temperature has cooled to (almost) zero ");
Console.WriteLine("at iteration " + iteration);
Console.WriteLine("Simulated Annealing loop complete");
Console.WriteLine("\nBest state found:");
Display(bestState);
Console.WriteLine("Best energy = " + bestEnergy.ToString("F2") + "\n");
Interpret(bestState, problemData);
Console.WriteLine("\nEnd Simulated Annealing demo\n");
Console.ReadLine();

主要的 SA 處理迴圈完成後，顯示找到最佳狀態 (解決方案) 和其相應的能源 （小時）。 Main 方法結束，像這樣：

...
} // Try
  catch (Exception ex)
  {
    Console.WriteLine(ex.Message);
    Console.ReadLine();
  }
} // Main

該方法包通過簡單地通過顯示異常消息處理的任何異常。

説明器方法

MakeProblemData 的説明器方法的代碼是：

static double[][] MakeProblemData(int numWorkers, int numTasks)
{
  double[][] result = new double[numWorkers][];
  for (int w = 0; w < result.Length; ++w)
    result[w] = new double[numTasks];
  result[0][0] = 7.5; result[0][1] = 3.5; result[0][2] = 2.5;
  result[1][1] = 1.5; result[1][2] = 4.5; result[1][3] = 3.5;
  result[2][2] = 3.5; result[2][3] = 5.5; result[2][4] = 3.5;
  result[3][3] = 6.5; result[3][4] = 1.5; result[3][5] = 4.5;
  result[4][0] = 2.5; result[4][4] = 2.5; result[4][5] = 2.5;
  return result;
}

我決定使用類型雙 [] [] — — 就是陣列的陣列 — — 持有我調度問題的定義。 與許多 C 家庭語言，不同的 C# 語言，並支援一個內置的二維陣列，所以可能已經使用類型雙 [，]，但如果您想要重新編碼我的示例中，一種語言，不支援二維陣列，陣列的陣列很容易重構。 在本例中，我隨便把工人指數第一次和任務索引二 (所以 [1] [3] 的結果是由工人 1 執行任務 3 所需的時間），但可能已經顛倒順序。 請注意 C# 自動初始化類型雙陣列儲存格為 0.0，因此我不必顯式地這樣做。 我可以使用一些其他的值，如-1.0 表示一名工人不能執行特定的任務。

説明器方法 RandomState 是：

static int[] RandomState(double[][] problemData)
{
  int numWorkers = problemData.Length;
  int numTasks = problemData[0].Length;
  int[] state = new int[numTasks];
  for (int t = 0; t < numTasks; ++t) {
    int w = random.Next(0, numWorkers);
    while (problemData[w][t] == 0.0) {
      ++w; if (w > numWorkers - 1) w = 0;
    }
    state[t] = w;
  }
  return state;
}

記得一國代表的解決方案和狀態是一個 int 陣列索引是任務，值是工人。 為每個狀態中的儲存格，生成隨機工人 w。 但那工人可能無法執行該任務，以便檢查，看看問題資料矩陣中的相應值是 0.0 （也就是說工人不能執行的任務），如果這樣我嘗試下一個工人，小心換回來到工人 0，如果超過去年工人的索引。

説明器方法 AdjacentState 是：

static int[] AdjacentState(int[] currState, double[][] problemData)
{
  int numWorkers = problemData.Length;
  int numTasks = problemData[0].Length;
  int[] state = new int[numTasks];
  int task = random.Next(0, numTasks);
  int worker = random.Next(0, numWorkers);
  while (problemData[worker][task] == 0.0) {
    ++worker; if (worker > numWorkers - 1) worker = 0;
  }
  currState.CopyTo(state, 0);
  state[task] = worker;
  return state;
}

方法 AdjacentState 始于一個給定的狀態，然後選擇一個隨機的任務，然後選擇一個隨機的工人，能做到任務。 請注意這是很粗的辦法 ； 它不會檢查是否隨機生成新來的工人是相同，當前的工人，所以返回狀態可能是相同的當前狀態。 取決於正在有針對性的 SA 演算法問題的性質，您可能要插入代碼的邏輯，以確保相鄰的國家是不同的當前狀態。

能量法所示圖 4。

圖 4 的能量法

static double Energy(int[] state, double[][] problemData)
{
  double result = 0.0;
  for (int t = 0; t < state.Length; ++t) {
    int worker = state[t];
    double time = problemData[worker][t];
    result += time;
  }
  int numWorkers = problemData.Length;
  int[] numJobs = new int[numWorkers];
  for (int t = 0; t < state.Length; ++t) {
    int worker = state[t];
    ++numJobs[worker];
    if (numJobs[worker] > 1) result += 3.50;
  }
  return result;
}

能量法首先走過狀態陣列中的每個任務、 抓工作價值、 查找問題資料矩陣，在所需的時間和積累的結果。 接下來，該方法計數工人不會多個任務，並添加 3.5 小時 retooling 刑罰，為每個額外任務的次數。 在此示例中，計算能量的一種狀態是快速 ； 不過，在最現實的 SA 演算法，能量法主導執行時間，所以你要確保該方法是盡可能高效。

説明器方法 AcceptanceProb 是：

static double AcceptanceProb(double energy, double adjEnergy,
  double currTemp)
{
  if (adjEnergy < energy)
    return 1.0;
  else
    return Math.Exp((energy - adjEnergy) / currTemp);
}

如果相鄰國家的能量是少於 （或更多，在最大化問題的情況下） 能量的當前狀態，該方法返回 1.0，所以當前狀態過渡到新的、 更好地相鄰的狀態，總是會。 但是，如果相鄰國家的能量是一樣，甚至更差的當前狀態，該方法返回的值應小於 1.0，這取決於當前溫度。 早在演算法中溫度的高值，返回值是靠近 1.0，所以當前狀態將經常轉換到新的、 更糟糕的是相鄰的狀態。 但作為溫度冷卻，則返回的值，從 AcceptanceProb 變得更小，規模較小，所以有少機會的過渡到一個糟糕的狀態。

這裡的想法是，有時你 — — 尤其是早期演算法中 — — 想要去一個糟糕的狀態，所以你不會收斂非最佳本地解決方案。 有時去糟，你能逃避非最佳沒有前途的國家。 請注意因為該函數執行算術司的當前溫度值，不能達到 0 允許溫度。 接受函數用在這裡是最常見的功能，並且基於一些基本的數學假設，但您不能使用其他接受函數沒有理由。

顯示和解釋的説明器方法是非常簡單，如圖所示，在圖 5。

圖 5 顯示並解釋的説明器方法

static void Display(double[][] matrix)
{
  for (int i = 0; i < matrix.Length; ++i) {
    for (int j = 0; j < matrix[i].Length; ++j)
      Console.Write(matrix[i][j].ToString("F2") + " ");
    Console.WriteLine("");
  }
}
static void Display(int[] vector)
{
  for (int i = 0; i < vector.Length; ++i)
    Console.Write(vector[i] + " ");
  Console.WriteLine("");
}
static void Interpret(int[] state, double[][] problemData)
{
  for (int t = 0; t < state.Length; ++t) { // task
    int w = state[t]; // worker
    Console.Write("Task [" + t + "] assigned to worker ");
    Console.WriteLine(w + ", " + problemData[w][t].ToString("F2"));
  }
}

一些弱點

SA 演算法很容易實現，可以是功能強大的工具，但是他們有弱點。因為凡有沒有好的確定性求解演算法，一般是你不知道什麼時候，或即使這些演算法最經常使用的情況下，你打了最佳的解決方案。例如，在圖 1，找到最佳的解決方案有能量的 20.5 小時，但通過運行長一點的演算法，您可以找到的國家有 19.5 小時的能源。因此，當使用 SAs，你必須願意接受良好，但不是一定是最佳的解決方案。SA 演算法和其他演算法基於行為的自然系統相關的缺點是它們需要自由參數如初始溫度和冷卻速度的規範。有效性和性能的這些演算法，包括 SAs，往往很敏感，你選擇的自由參數的值。

SA 演算法與類比蜜蜂殖民地 (SBC) 的演算法，我描述了在 2011 年 4 月一期密切相關 (msdn.microsoft.com/magazine/gg983491)。這兩種技術都很好地適合組合、 非數值優化問題求解。一般情況下，SAs 速度更快，比 SBCs，但 SBCs 往往產生更好的解決方案，在性能為代價。

人工智慧技術在軟體測試中的使用是一個區域，幾乎是完全發掘。凡可能用於 SAs 軟體測試的一個例子是作為驗證演算法。假設您有一些組合的問題，可實際上解決使用確定性演算法。圖的最短路徑問題，可以由幾個有效但相對複雜的演算法，如舉世聞名的演算法解決的就是一個例子。如果您已經編碼的最短路徑演算法，您可以測試，通過快速編碼，一種簡單的 SA 演算法和比較的結果。SA 結果是比的確定性演算法，如果你知道你在你的確定性演算法的 bug。

Dr. James McCaffrey* 適合伏資訊科學 Inc.，他在管理技術培訓為軟體工程師工作在微軟雷德蒙德，華盛頓，校園。他被在幾個 Microsoft 產品，包括互聯網資源管理器和 MSN 搜索。 博士。 麥卡弗裡是作者"。網路測試自動化食譜"（很，2006年），可以在達到 jammc@microsoft.com。*

多虧了以下技術專家，檢討這篇文章： Paul Koch， Dan Liebling， Ann Loomis Thompson 和 Shane Williams