2016 年 11 月
第 31 卷,第 11 期
测试运行 - 使用组合进化解决数独问题
组合优化问题旨在按特定顺序来安排一组离散项。数独谜题是组合优化问题的一个示例。在本文中,我将向你介绍如何使用我称为组合进化的技术来编写程序解决困难的数独问题。
此演示将设置一个比较困难的数独问题(我稍后将解释何谓比较困难)。在数独中,有几个约束。9x9 解决方案网格的每行必须包含数字 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 使用组合进化解决数独问题
所有机体得到改善后,选择两个良好的机体解决方案并用于生成新机体,这会替换不良解决方案。因此,机体数量随时间不断增加。如果一段 maxEpochs 时间后仍未找到最佳解决方案,将通过终止所有机体并创建新机体来重启算法。
演示将设置 200 个虚拟机体,时间限制为 5,000 个时期。使用一点反复试验法可找到这些值。组合进化不保证可找到最佳解决方案,因此设置 20 次重启限制以阻止可能出现的无限循环。
演示程序在三次重启后找到最佳解决方案,该程序在我的桌面计算机上约运行了 8 秒。演示运行期间,程序显示了最佳机体的误差测量。在展示相关代码时,我将讲解如何定义和计算误差。但是,请注意算法趋于极快地获得非常好的解决方案(误差 = 2),然后却陷入僵局。重启过程是克服此特性的一个机制,并且是许多优化算法中的常见技术。
演示程序
为了创建演示程序,我启动 Visual Studio,单击“文件 | 新建 | 项目”并选择“C# 控制台应用程序”选项。此项目命名为 SudokuEvo。该演示程序对 .NET 的依赖程度并不明显,因此,任何 Visual Studio 版本都可以正常运行。在“解决方案资源管理器”窗口加载模板代码后,我右键单击了文件 Program.cs 并将其重新命名为 SudokuEvoProgram.cs 且允许 Visual Studio 自动为我重新命名类 Program。
在编辑器窗口的顶部,我使用语句删除了所有不必要的内容,仅留下引用 System 和 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
演示程序并不像第一次出现时那样复杂,因为许多方法是简短的帮助程序方法。演示有两个类。主类将所有代码逻辑实现为静态方法。机体类定义目标数独问题的可能解决方案。
每个机体对象都具有一个类型,“worker”机体可以是 0,或者“explorer”机体可以是 1。名称为矩阵的字段是整数“array-of-arrays-style”矩阵,表示可能的解决方案。每个可能的解决方案有一个误差,其中误差值 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);
方法 Solve 几乎是方法 SolveEvo 周围的包装器,它执行大部分工作。这是组合优化中的一个常见设计模式—一个低级别求解方法尝试查找最佳解决方案,此方法被执行重启的高级别求解方法包装。
组合进化算法不保证可找到最佳解决方案(即,解决方案没有约束误差),因此演示程序会检查以确定找到的最好解决方案是否是最佳的:
int err = Error(soln);
if (err == 0)
Console.WriteLine("Success");
else
Console.WriteLine("Did not find optimal solution");
矩阵初始化和误差
我认为,了解组合进化优化的最好方法是从查看帮助程序方法开始。一旦了解帮助程序,求解方法便相对容易掌握。首先我将介绍方法 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 且没有重复的值。始终正确的情况有时称为不变条件。不变条件会影响算法的所有其他方法。从理论上说,行约束或列约束可用作不变条件,但实际上使用子网格约束会更有效。
从概念上讲,演练 9x9 矩阵中的每个 3x3 子网格并不够深入,但实现却稍微有些棘手。我采用的方法是定义两个帮助程序方法,Block 和 Corner。方法 Block 接受行索引 r 和列索引 c,并返回包含位于 (r, c) 的单元格的块编号 (0-8)。块编号从左到右分配,然后从上到下分配。例如,如果 (r, c) = (3, 8),则方法 Block 返回 5。
方法 Corner 接受块 ID (0-8) 并返回块左上角的索引。例如,如果块 = 8,则方法 Corner 返回 (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;
}
在口头上,可能的解决方案的总误差是行中缺失值的数目与列中缺失值的数目之和。因为算法不变条件的存在,所有 3x3 子网格没有缺失值,因此它们不会造成误差。请注意,计算每行和每列中重复值的数目相当于计算缺失值的数目。
生成相邻矩阵
在组合进化中,有两类机体对象。explorer 类型的机体对象使用方法 RandomMatrix 随机搜索可能的解决方案。worker 类型的机体对象通过检查附近“邻近”可能的解决方案重复尝试查找矩阵字段中存储的更佳解决方案。
因为 3x3 子网格不变条件的存在,邻近解决方案必须限定自身是子网格的排列。更具体地说,要确定相邻矩阵,算法会随机选择一个块,然后在块中选择两个单元格(其中两个单元格均不包含问题定义中的固定值)并交换两个单元格中的值。
将方法 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;
}
演示程序假设存在类作用域的 Random 对象(名称为 rnd)。此设计常见于许多优化算法。可在多个组合优化算法中找到生成相邻解决方案的概念,例如模拟退火优化和模拟蜂群优化。
合并两个矩阵
组合进化优化算法可实现虚拟进化形式,方法是选择两个良好机体对象(即它们有一个具有较小误差的矩阵字段),然后使用这些良好对象来创建新的子对象。新的(很可能非常好)子机体会替换不良机体。
方法 MergeMatrices 从两个机体对象接受两个 9x9 矩阵。此方法从块 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;
}
此进化机制在某种程度上类似于遗传算法中使用的染色体交叉机制。
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 机体对象的数目,因为已使用总数目的 90%。此值通过反复试验法来确定。机体对象存储在名为 hive 的数组。
用于处理 worker 类型机体的伪代码是:
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)会命令机体对象接受比对象的当前解决方案差的相邻解决方案。这是一个常见优化策略,旨在帮助算法摆脱非最佳解决方案。
在迭代循环的每个时期,每个 explorer 类型机体会生成随机解决方案网格。处理每个机体对象后,会创建新的机体。伪代码如下:
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
事实证明,此进化机制对算法的成功至关重要。如果不借助进化,算法有时会失败。但如果借助进化,算法可成功解决我提出的每个困难数独问题,包括一些我在 Internet 上找到的非常困难的问题。但是,组合优化尚未经过研究分析,因此组合进化可解决数独谜题的事实并不保证它可解决任意组合优化问题。
总结
我在本文中介绍的组合进化算法其实并不是一种算法。组合进化是元启发式算法。我的意思是组合进化只是一组常规准则,可用于设计具体算法以解决特定优化问题。
在常规工作环境中你不太可能需要解决数独问题,但组合优化也可用于解决实际问题。组合优化的主要想法是定义可描述目标问题的数据结构;定义何谓随机解决方案;定义何谓相邻解决方案;以及定义误差指标。通过将这些谜题片段整合在一起,可使用组合进化快速高效地解决传统算法无法解决的许多问题。
Dr.James McCaffrey 供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他参与过多个 Microsoft 产品的工作,包括 Internet Explorer 和 Bing。Scripto可通过 jammc@microsoft.com 与 McCaffrey 取得联系。
衷心感谢以下 Microsoft 技术专家对本文的审阅: Chris Lee 和 Kirk Olynyk