测试运行

项目
07/13/2015

模拟退火算法和测试

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。

**博士。**James McCaffrey适合伏信息科学 Inc.，他在管理技术培训为软件工程师工作在微软雷德蒙德，华盛顿，校园。他被在几个 Microsoft 产品，包括互联网资源管理器和 MSN 搜索。博士。麦卡弗里是作者"。网络测试自动化食谱"（很，2006年），可以在达到 jammc@microsoft.com。

多亏了以下技术专家，检讨这篇文章： Paul Koch， Dan Liebling， Ann Loomis Thompson 和 Shane Williams