测试运行
蚁群优化
在本月的专栏中，我介绍 C# 代码实现蚂蚁蚁群优化 （ACO） 算法解决旅行商问题 (TSP)。蚁群优化算法是一种基于信息素铺设的蚂蚁 ； 行为的人工智能技术 它可以用于寻求通过图形的最优路径的极其复杂的问题找到解决办法。看到我朝哪里最好是看一看在截图图 1。在此情况下，该演示求解 TSP 的实例访问 60 城市的每一次的最短路径的目标。演示计划使用四个蚂蚁 ； 每只蚂蚁表示可能的解决方案。蚁群算法需要几个参数如信息素影响因子 （alpha） 和信息素的蒸发系数 （rho），后面会讲的规范。四个蚂蚁被初始化为随机径进行 60 的城市 ； 初始化之后，最佳的蚂蚁的最短径长度为 245.0 单位。蚁群优化的关键点是模拟信息素，这吸引到更好的创新，通过该图形的蚂蚁的使用。主要加工循环之间交替更新基于信息素的当前值的蚂蚁跟踪和更新基于 ant 创新的信息素。最大数目 (1000) 倍通过主要加工循环后，程序将显示找到的最好的线索和其相应的长度 （61.0 单位）。
60 城市图是人工建造这种连接到每个其他城市，每个城市，任何两个城市之间的距离 1.0 和 8.0 任意单元 (英里、 公里等等） 之间的随机值。没有解决 TSP 的简便方法。60 城市，假设你可以在任何城市和 go 向前或向后，启动并连接所有的城市，有共 (60-1） ！/ 2 = 69,341,559,272,844,917,868,969,509,860,194,703,172,951,438,386,343,716,270,410,647,470,080,000,000,000,000 可能的解决方案。即使您可以评估每秒 1 亿可能的解决办法，才会约 2.2 ＊ 1063 年检查它们所有的情况下，这是宇宙的估计年龄比长很多倍。
蚁群优化是 meta-heuristic，这意味着它一个可以用来创建特定的算法，以解决特定图形路径问题的一般框架。虽然蚁群优化 1991年博士论文中提出 M。多里戈算法的第一次详细说明通常被由于 1996 年的后续论文万。多里戈 VManiezzo 和 a。科洛尔尼。自那时以来，蚁群优化广泛研究和修改，但是，有点奇怪的是，很少有的完整和正确实现可联机使用。
此列假定您拥有中级高级编程技能。我实现使用 C# 的蚁群优化程序，但你不应该有太多的麻烦，我以不同的语言，例如，JavaScript 代码重构。我决定，避免所有使用面向对象的编程 (OOP) 保持尽可能清晰的算法的想法。由于空间的限制，我不能提交所示中运行的代码的所有图 1。我将会在最棘手的部分，你可以下载完整的代码从 archive.msdn.microsoft.com/mag201202TestRun。虽然永远不可能直接使用蚁群优化的代码，很多技术，例如，轮盘赌轮选择，可以很有意思，设置你的技术的有益补充。
.png)
图 1 蚁群优化在行动
程序结构
我作为单个 C# 控制台应用程序实现蚁群优化演示计划。所示的程序中，大多数 WriteLine 语句删除，整体结构图 2。虽然某些部分棘手，但该程序并不复杂的图 2 表明，因为许多方法都是短期的帮助器方法。
图 2 蚂蚁蚁群优化程序结构
using System;
namespace AntColony
{
class AntColonyProgram
{
static Random random = new Random(0);
static int alpha = 3;
static int beta = 2;
static double rho = 0.01;
static double Q = 2.0;
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin Ant Colony Optimization demo\n");
int numCities = 60;
int numAnts = 4;
int maxTime = 1000;
int[][] dists = MakeGraphDistances(numCities);
int[][] ants = InitAnts(numAnts, numCities);
int[] bestTrail = BestTrail(ants, dists);
double bestLength = Length(bestTrail, dists);
double[][] pheromones = InitPheromones(numCities);
int time = 0;
while (time < maxTime)
{
UpdateAnts(ants, pheromones, dists);
UpdatePheromones(pheromones, ants, dists);
int[] currBestTrail = BestTrail(ants, dists);
double currBestLength = Length(currBestTrail, dists);
if (currBestLength < bestLength)
{
bestLength = currBestLength;
bestTrail = currBestTrail;
}
++time;
}
Console.WriteLine("\nBest trail found:");
Display(bestTrail);
Console.WriteLine("\nLength of best trail found: " +
bestLength.ToString("F1"));
Console.WriteLine("\nEnd Ant Colony Optimization demo\n");
}
catch (Exception ex)
{
Console.WriteLine(ex.Message);
}
} // Main
static int[][] InitAnts(int numAnts, int numCities) { .
.
}
static int[] RandomTrail(int start, int numCities) { .
.
}
static int IndexOfTarget(int[] trail, int target) { .
.
}
static double Length(int[] trail, int[][] dists) { .
.
}
static int[] BestTrail(int[][] ants, int[][] dists) { .
.
}
static double[][] InitPheromones(int numCities) { .
.
}
static void UpdateAnts(int[][] ants, double[][] pheromones,
int[][] dists) { .
.
}
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists) { .
.
}
static int NextCity(int k, int cityX, bool[] visited, double[][] pheromones,
int[][] dists) { .
.
}
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists) { .
.
}
static void UpdatePheromones(double[][] pheromones, int[][] ants,
int[][] dists) { .
.
}
static bool EdgeInTrail(int nodeX, int nodeY, int[] trail) { .
.
}
static int[][] MakeGraphDistances(int numCities) { .
.
}
static double Distance(int cityX, int cityY, int[][] dists) { .
.
}
static void Display(int[] trail) { .
.
}
static void ShowAnts(int[][] ants, int[][] dists) { .
.
}
static void Display(double[][] pheromones) { .
.
}
}
}
我使用 Visual Studio 创建名为 AntColony 的控制台应用程序。 在解决方案资源管理器窗口中我重命名默认的 program.cs，然后从文件为 AntColonyProgram.cs，其中汽车◆ 重命名项目中的单个类。 已删除所有的模板生成使用除了 System 命名空间的声明 — — 蚁群算法通常并不需要太多的库支持。 UpdateAnts 和 UpdatePheromones 两种主要方法。 UpdateAnts 方法调用 BuildTrail，NextCity，其中要求 MoveProbs 要求的佣工。 UpdatePheromones 方法调用帮助器 EdgeInTrail，其中要求 IndexOfTarget。
我声明类范围随机对象命名随机。 蚁群优化算法的概率为您很快就会看到。 类范围变量 α、 β、 rho 和 Q 控制蚁群优化算法的行为。 我使用这些变量的名称，因为它们被用在原始描述的蚁群优化。
设置问题
我使用 MakeGraphDistances 方法人工图设置：
static int[][] MakeGraphDistances(int numCities)
{
int[][] dists = new int[numCities][];
for (int i = 0; i < dists.Length; ++i)
dists[i] = new int[numCities];
for (int i = 0; i < numCities; ++i)
for (int j = i + 1; j < numCities; ++j) {
int d = random.Next(1, 9); // [1,8]
dists[i][j] = d; dists[j][i] = d;
}
return dists;
}
为真实世界图的问题，您可能会读图-邻接和距离之间节点的数据，从文本文件，在一定的数据结构。 在这里我通过创建数组的数组，其中的行索引，我代表从城市和列索引 j 代表到市模拟图。 通知所有城市都相连，距离不对称，从一个城市到本身的距离为 0。
一旦我有可以为远程方法的距离数据结构：
static double Distance(int cityX, int cityY, int[][] dists)
{
return dists[cityX][cityY];
}
为了尽量减少提交的代码量，省略掉正常的错误检查，例如，确保的 cityX 和 cityY 参数有效。
启动蚂蚁和信息素
在非 OOP 的实现中，一只蚂蚁是只代表的步道或路径，从最初的城市，通过所有其他城市的 int 值的数组。 蚂蚁的集合是数组的数组中的第一个索引指示蚂蚁：
static int[][] InitAnts(int numAnts, int numCities)
{
int[][] ants = new int[numAnts][];
for (int k = 0; k < numAnts; ++k) {
int start = random.Next(0, numCities);
ants[k] = RandomTrail(start, numCities);
}
return ants;
}
初始化方法为每只蚂蚁的线索分配行、 拿一个随机启动城市，然后调用 RandomTrail 的帮助器方法：
static int[] RandomTrail(int start, int numCities)
{
int[] trail = new int[numCities];
for (int i = 0; i < numCities; ++i) { trail[i] = i; }
for (int i = 0; i < numCities; ++i) {
int r = random.Next(i, numCities);
int tmp = trail[r]; trail[r] = trail[i]; trail[i] = tmp;
}
int idx = IndexOfTarget(trail, start);
int temp = trail[0]; trail[0] = trail[idx]; trail[idx] = temp;
return trail;
}
RandomTrail 帮助器分配一个跟踪，并将它初始化为 0、 1、 2、... numCities-1。 下一步，该方法使用费雪耶茨无序播放算法随机化的步道城市秩序。 指定的起始城市然后找到并换入位置跟踪 [0]。
信息素是化学品蚂蚁地方对其跟踪信息 ； 他们吸引其他蚂蚁。 更多的蚂蚁将较短的路线前往食物来源 — — 和存放更多的信息素 — — 比上更长时间的跟踪信息。 随着时间的推移慢慢蒸发信息素。 这里是 InitPheromones 的方法：
static double[][] InitPheromones(int numCities)
{
double[][] pheromones = new double[numCities][];
for (int i = 0; i < numCities; ++i)
pheromones[i] = new double[numCities];
for (int i = 0; i < pheromones.Length; ++i)
for (int j = 0; j < pheromones[i].Length; ++j)
pheromones[i][j] = 0.01;
return pheromones;
}
信息素的信息存储在哪里行索引一数组的数组样式对称矩阵是从城市和列索引 j 是到城市。 所有值最初都设置为任意的小值 (0.01) 跳开始 UpdateAnts UpdatePheromones 周期。
更新蚂蚁
蚁群优化算法的关键是通过构建一个新的更新每个蚂蚁和跟踪的过程 — — 我们希望更好地 — — 基于信息素和距离信息的线索。 看看图 3。 假设我们有小的图的只是五个城市。 在图 3 正在建设中的一只蚂蚁的新线索。 古道启动市 1，然后去城市 3，并更新算法的确定下一个城市。 现在假设信息素和距离信息是在图像中所示。 在确定下一个城市的第一步构建一个数组，我打过电话"taueta"（因为原始研究论文用希腊字母头和 eta)。 Taueta 值是 alpha 的幂，时间超过 beta 幂的距离值之一的边缘信息素值。 阿尔法和贝塔都必须指定的全局常量的召回。 在这里，我会认为 alpha 是 3，测试版是 2。 市 1 和 3 市的 taueta 值并不是因为他们已经在当前径计算的。 注意到信息素较大的值增加 taueta，但更远的距离减少 taueta。
.png)
图 3 更新的蚁群信息
计算所有的 taueta 值之后下, 一步是将这些值转换为概率并将它们放置在数组中我所称的 probs。 该算法 taueta 的值，在此示例中，获取 82.26 求和，然后将每个 taueta 的值除以总和。 在这一点上，城市 0 有 0.09 等被选中的概率。 接下来，该算法需要选择基于计算概率的下一个城市。 正如我刚才所说，我这篇文章中提出的蚁群优化算法使用一种称为轮盘赌轮选择整洁技术。 我建造一个增强的数组，称为 cumul，持有累积概率。 增强的数组的大小是大于 probs 数组中，并 [0] 细胞播种了 0.0。 在 cumul 中的每个单元格是累积概率的总和。 Cumul 阵列已落成后，将生成 0.0 和 1.0 之间的随机数字 p。 假设 p = 0.538，如图所示。 那个 p 值介于在值 [2] 和 [3] 在 cumul 数组中，这意味着，[2]，或城市 2，被选定为下一个城市。
名为 UpdateAnts 的更新顶级的方法：
static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
for (int k = 0; k < ants.Length; ++k) {
int start = random.Next(0, numCities);
int[] newTrail = BuildTrail(k, start, pheromones, dists);
ants[k] = newTrail;
}
}
请注意每只蚂蚁都分配一个新的、 随机的起始城市而不是保留旧启动城市。 如中所示，大部分的实际工作由帮助器方法 BuildTrail， 图 4。
图 4 BuildTrail 方法
static int[] BuildTrail(int k, int start, double[][] pheromones,
int[][] dists)
{
int numCities = pheromones.Length;
int[] trail = new int[numCities];
bool[] visited = new bool[numCities];
trail[0] = start;
visited[start] = true;
for (int i = 0; i < numCities - 1; ++i) {
int cityX = trail[i];
int next = NextCity(k, cityX, visited, pheromones, dists);
trail[i + 1] = next;
visited[next] = true;
}
return trail;
}
BuildTrail 维护访问过的布尔值数组，以便创建的跟踪并不包含重复的城市。 在跟踪 [0] 价值播种了一个开始的城市，然后每个城市的帮助器方法 NextCity，所示添加反过来图 5。
图 5 NextCity 方法
static int NextCity(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
double[] probs = MoveProbs(k, cityX, visited, pheromones, dists);
double[] cumul = new double[probs.Length + 1];
for (int i = 0; i < probs.Length; ++i)
cumul[i + 1] = cumul[i] + probs[i];
double p = random.NextDouble();
for (int i = 0; i < cumul.Length - 1; ++i)
if (p >= cumul[i] && p < cumul[i + 1])
return i;
throw new Exception("Failure to return valid city in NextCity");
}
NextCity 方法实现轮盘赌轮选择算法。请注意，该算法将失败，如果 cumul 数组中的最后一个值大于 （可能是由于需要舍入错误），1.00，所以您可能要添加逻辑以始终设置 cumul [cumul。长度 1] 为 1.00。 NextCity 要求生产的帮助器方法 MoveProbs，所示的概率的数组图 6。
图 6 MoveProbs 方法
static double[] MoveProbs(int k, int cityX, bool[] visited,
double[][] pheromones, int[][] dists)
{
int numCities = pheromones.Length;
double[] taueta = new double[numCities];
double sum = 0.0;
for (int i = 0; i < taueta.Length; ++i) {
if (i == cityX)
taueta[i] = 0.0; // Prob of moving to self is zero
else if (visited[i] == true)
taueta[i] = 0.0; // Prob of moving to a visited node is zero
else {
taueta[i] = Math.Pow(pheromones[cityX][i], alpha) *
Math.Pow((1.0 / Distance(cityX, i, dists)), beta);
if (taueta[i] < 0.0001)
taueta[i] = 0.0001;
else if (taueta[i] > (double.MaxValue / (numCities * 100)))
taueta[i] = double.MaxValue / (numCities * 100);
}
sum += taueta[i];
}
double[] probs = new double[numCities];
for (int i = 0; i < probs.Length; ++i)
probs[i] = taueta[i] / sum;
return probs;
}
（如果距离值是非常大的），就可以很小的 taueta 值或非常大 （如果信息素值是大），可以产生困难的算法。 为处理这问题，我检查 taueta 的值，并施加任意的最小和最大值。
更新信息素
正在更新信息素的信息容易得多比更新蚂蚁跟踪信息。 关键线路的 UpdatePhermones 方法中是代码的：
double length = Length(ants[k], dists);
double decrease = (1.0 - rho) * pheromones[i][j];
double increase = 0.0;
if (EdgeInTrail(i, j, ants[k]) == true)
increase = (Q / length);
pheromones[i][j] = decrease + increase;
信息素的每个值被下跌，模拟蒸发，和增加，模拟信息素的存款古道上的蚂蚁。 减少影响是通过信息素的当前值乘以系数小于 1.0，取决于全局参数 rho 产生的。 较大的 rho 是，信息素值越大减少。 增加影响是通过添加当前蚂蚁总径长度，所占比例由全局参数 Q 的比例而产生的。 Q 的较大的值增加信息素添加的量。 Ant 的当前径上调用帮助器方法 UpdatePheromones EdgeInTrail，它决定了如果两个城市之间的一段。 你可以看看这篇文章的详细信息代码下载 (archive.msdn.microsoft.com/mag201202TestRun)。
接近尾声了
我要强调有许多不同的蚁群优化 ； 我已经给出了在这里的版本只是一个许多可能的解决办法。 蚁群优化的倡导者已应用于广泛的组合优化问题的算法。 其他组合的最适mization 算法基于自然系统的行为包括模拟退火 (SA)，其时我上个月 （msdn.microsoft.com/magazine/hh708758)，和模拟蜜蜂殖民地 (SBC)，在 2011 年 4 月专栏报道 (msdn.microsoft.com/magazine/gg983491)。 每种方法都有优点和弱点。 在我看来，最适合于相似货郎担问题，虽然 SA 和 SBC 是更好的更一般的组合优化问题，例如调度的问题蚁群优化。
蚁群优化，与自然系统，基于其他元启发式一样是相当敏感，您所选择的自由的全局参数 — — 阿尔法、 测试版等等。 虽然已经相当多的蚁群算法参数研究，但普遍的共识是质量的，您必须有点试验与自由的参数，以获得最佳的性能和解决方案。
**博士。**詹姆斯 · 麦卡弗里为伏信息科学 Inc.，凡他管理技术培训工作在华盛顿雷德蒙的微软校园软件工程师的工作。他被在几个微软的产品，包括互联网资源管理器和 MSN 搜索。麦卡弗里的作者是"。网络测试自动化食谱"（很，2006年），可以通过在 jmccaffrey@volt.com 或 jammc@microsoft.com。
多亏了以下 Microsoft 技术专家审查这篇文章： 丹利布林 和 安妮 · 梅斯 · 汤普森