2016 年 2 月
第 31 卷，第 2 期
此文章由机器翻译。
测试运行 - 蟑螂侵害优化
.jpg "James 麦卡弗里")
Roach 感染优化是严格基于常见蟑螂如 Periplaneta americana 的行为的数字优化算法。是，您的正确读取。我来做个解释。
在机器学习，数字优化算法经常用于查找尽量减少一定程度的错误的变量 (通常称为权重) 的一组值。例如，逻辑回归分类可以使用数学等式。在该等式中，如果有 n 个预测变量，则有 n+1 个必须确定的权重值。确定权重值的过程被称为定型模型。其原理是，使用含有已知正确输入值的定型数据的集合。数字优化算法用于查找最小化之间计算得出的输出值和已知的正确输出值的误差的权重的值。
有许多不同的数字优化算法。最常见基于微积分衍生产品，但也有基于自然系统的行为的算法。这有时称为个人简历极具创意的算法。此文章介绍了一种相对新 (2008 年第一次发布) 名为 roach 感染优化 (RIO) 技术。RIO 优化轻松地模仿一套 roaches 的觅食和聚合行为。
若要了解什么是 RIO 并查看本文所述观点的好方法是看一看中的演示程序 图 1。该演示旨在使用 RIO 查找具有八个输入变量的 Rastrigin 函数的最小值。Rastrigin 函数是标准的基准测试函数用于评估数字优化算法的有效性。该函数具有已知的最小值 0.0 位于 x = (0，0，...0) 的 0 值的数量等于输入的值的数目。
.png "Roach 感染优化算法正在运行")
图 1 Roach 感染优化算法正在运行
Rastrigin 函数很难对于大多数优化算法，因为它具有许多峰值和低谷创建本地最小值可以捕获这些算法。不能轻松地看到含有 8 个输入值 Rastrigin 函数，但可以通过检查关系图中所示的两个输入的值的函数来获取该函数的特点一个好主意 图 2。
.png "具有两个输入变量的 Rastrigin 函数")
图 2 具有两个输入变量的 Rastrigin 函数
该演示程序将 roaches 数设置为 20。每个模拟的 roach 有一个表示最小化问题的可能的解决方案的位置。更多 roaches 查找真正的最佳解决方案，这会降低性能的可能性就越大。RIO 通常使用 10 至 100 个 roaches。
RIO 是一个迭代过程，需要最大循环计数器值。该演示将最大值设置为 10000 的迭代。最大迭代数而异问题到问题，但常见介于 1000 和 100000 之间的值。RIO 具有随机性的元素，并演示设置种子值的随机数生成器为 6，因为 6 提供代表性演示输出。
在演示中所示 图 1, ，截至目前已找到的最佳 roach 位置相关联的最佳 (最小) 错误显示每个 500 时间单位。该算法完成发现的任何 roach 的最佳位置后，x = (0、 0，0，0，0，0，0，0)，即，事实上，正确答案。但请注意是否最大迭代数必须已设置为 5000，而不是 10000，RIO 将均未注意到一个全局最小值。RIO，几乎所有的数字优化算法，如不保证在实际方案中查找最佳的解决方案。
本文假定您至少具有中级编程技能，但并不假定您知道有关数字优化的任何信息或 roach 感染优化算法。该演示程序使用 C# 中，进行编码，但您应能够将代码重构到另一种语言，如 Visual Basic 或 JavaScript 太困难。
本文显示了完整的演示代码以及少量小幅改动，以节省空间。还可以在本文随附的代码下载中获取该演示。该演示代码含有已删除的所有常规错误检查，以使主要概念清晰明了并减少代码的大小。
程序的整体结构
图 3 中显示了总体程序结构。若要创建此演示，我启动了 Visual Studio 并创建一个新 C# 控制台应用程序名为 RoachOptimization。演示对并没有明显的 Microsoft.NET Framework 依赖性，因此任何最新版本的 Visual Studio 将起作用。
图 3 Roach 优化演示程序结构
using System;
namespace RoachOptimization
{
class RoachOptimizationProgram
{
static void Main(string[] args)
{
Console.WriteLine("Begin roach optimization demo");
// Code here
Console.WriteLine("End roach demo");
Console.ReadLine();
}
static double[] SolveRastrigin(int dim, int numRoaches,
int tMax, int rndSeed) { . . }
public static double Error(double[] x) { . . }
static double Distance(double[] pos1,
double[] pos2) { . . }
static void Shuffle(int[] indices,
int seed) { . . }
} // Program
public class Roach
{
// Defined here
}
}
模板代码加载到 Visual Studio 编辑器之后，在解决方案资源管理器窗口文件 Program.cs 重命名为更具描述性的 RoachOptimizationProgram.cs 和 Visual Studio 会自动重命名 Program 类，为我。在对源代码的顶部，我删除了所有不必要的 using 语句，对系统的单一引用。
我使用主要静态方法的方法，而不是完整的面向对象编程 (OOP) 方法该演示进行编码。该演示具有 Main 方法中的所有控制逻辑。它首先会通过设置算法的输入的参数值:
Console.WriteLine("Begin roach optimization demo");
int dim = 8;
int numRoaches = 20;
int tMax = 10000;
int rndSeed = 6;
Dim 变量指定为 Rastrigin 的函数的输入值的数目。在非演示机器学习方案中，维度表示预测模型中的权重数。Roaches 数设置为 20。变量 tMax 是最大迭代数。RIO，像大多数个人简历极具创意的算法，是概率性。在这里，随机变量种子值设置为 6。
接下来，RIO 参数将回显到控制台:
Console.WriteLine("Goal is to minimize Rastrigin's " +
"function in " + dim + " dimensions");
Console.WriteLine("Problem has known min value = 0.0 " +
"at (0, 0, .. 0) ");
Console.WriteLine("Setting number of roaches = " +
numRoaches);
Console.WriteLine("Setting maximum iterations = " +
tMax);
Console.WriteLine("Setting random seed = " + rndSeed);;
调用 roach 优化算法如下所示:
Console.WriteLine("Starting roach optimization ");
double[] answer = SolveRastrigin(dim, numRoaches,
tMax, rndSeed);
Console.WriteLine("Roach algorithm completed");
Main 方法最后会显示结果:
double err = Error(answer);
Console.WriteLine("Best error found = " +
err.ToString("F6") + " at: ");
for (int i = 0; i < dim; ++i)
Console.Write(answer[i].ToString("F4") + " ");
Console.WriteLine("");
Console.WriteLine("End roach optimization demo");
Console.ReadLine();
在本文中介绍的 roach 优化算法基于 2008年研究论文，"Roach 感染优化"T.Havens、 C.西班牙、 N.橙红色和 J.Keller。可以在 Web 上找到多个位置找到此白皮书。
了解 Roach 优化算法
RIO，在没有模拟 roaches 的集合。每个 roach 有 n 维度表示最小化问题的可能的解决方案的一个位置。模拟的 roach 行为取决于实际 roaches 的三个行为。首先，roaches 往往要移至暗区。其次，roaches 喜欢组合在一起。第三，当 roaches 获得过大，它们将保留其当前位置食物搜索。如何精确地模拟的 roaches 模型这些行为将变得清晰时显示的代码。
表示非常高级别的伪代码中，roach 优化算法所示 图 4。从表面看，该算法看起来非常简单;但是，有大量不明显的伪代码的详细信息。
图 4 较高层面的 Roach 算法
initialize n roaches to random positions
loop tMax times
compute distances between all roaches
compute median distance
for-each roach
compute number neighbors
exchange data with neighbors
if not hungry
compute new velocity
compute new position
check if new best position
else if hungry
relocate to new position
end-if
end-for
end loop
return best position found
Roach 类
程序定义的类 Roach 的定义开头如下:
public class Roach
{
public int dim;
public double[] position;
public double[] velocity;
public double error;
...
Dim 字段是问题维度，即如果使用演示用 8。位置字段是一个数组，从概念上讲表示 roach 的位置，并还表示为最小化问题的可能的解决方案。速度字段是决定在下一步的时间单位将移动 roach 将其中的值的数组。例如，如果 dim = 2 和位置 = (5.0，3.0) 和速度 = (1.0，-2.0) roach 将移到 (6.0，1.0)。错误字段是与当前的位置相关联的错误。
定义将继续:
public double[] personalBestPos;
public double personalBestErr;
public double[] groupBestPos;
public int hunger;
private Random rnd;
PersonalBestPos 字段保存在其移动过程中，任何时候模拟 roach 所发现的最佳位置。PersonalBestError 包含对应于 personalBestPos 的错误。GroupBestPos 字段可容纳任何邻居 roaches 一组发现的最佳位置。肚子字段是表示如何 ¶ roach 是一个整数值。Random 对象 rnd 用于初始化 roach 到随机位置。
Roach 类定义将继续通过定义一个构造函数:
public Roach(int dim, double minX, double maxX,
int tHunger, int rndSeed)
{
this.dim = dim;
this.position = new double[dim];
this.velocity = new double[dim];
this.personalBestPos = new double[dim];
this.groupBestPos = new double[dim];
...
MinX 和 maxX 参数用于设置位置矢量的组件的限制。参数 tHunger 是最大肚子值。当 roach 肚子达到 tHunger 时，roach 将移动到新位置。构造函数为四个数组字段分配的空间。
接下来，构造函数初始化的 Random 对象，并使用它来将初始肚子值设置为一个随机值:
this.rnd = new Random(rndSeed);
this.hunger = this.rnd.Next(0, tHunger);
接下来，构造函数将初始位置、 速度、 个人的最佳位置和组最佳位置数组设置为 minX 和 maxX 之间的随机值:
for (int i = 0; i < dim; ++i) {
this.position[i] = (maxX - minX) * rnd.NextDouble() + minX;
this.velocity[i] = (maxX - minX) * rnd.NextDouble() + minX;
this.personalBestPos[i] = this.position[i];
this.groupBestPos[i] = this.position[i];
}
Roach 构造函数定义完成如下所示:
...
error = RoachOptimizationProgram.Error(this.position);
personalBestErr = this.error;
} // ctor
} // Roach
错误字段是通过调用外部方法错误，调用程序类中定义的设置。一种替代方法是在调用构造函数中，然后传递错误中的值以参数形式向该构造函数之前计算错误值。
实现 Roach 算法
RIO 算法都包含在静态方法 SolveRastrigin，其定义开头如下:
static double[] SolveRastrigin(int dim, int numRoaches,
int tMax, int rndSeed)
{
double C0 = 0.7;
double C1 = 1.43;
double[] A = new double[] { 0.2, 0.3, 0.4 };
...
时计算 roach 新速度，当您不久就会看到使用常量 C0 和 C1。使用的值，0.7 和 1.43，来自粒子群理论。您可能需要调查其他值。
彼此邻近的 roaches 被称作邻居。邻居将有时，但不是总是交换信息。该数组名为保存概率。第一个值，0.2，为与一个邻居 roach 将交换信息与该邻居的概率。第二个值，0.3，是如果有两个邻居，roach 将交换信息的可能性。第三个值，0.4，是指如果 roach 具有三个或多个邻居交换信息的概率。
这些概率值，(0.2、 0.3，0.4)，不是那些源研究论文中使用了。原始的研究使用概率值为 (0.49、 0.63、 0.65)，它们分别对应于实际 roach 行为生物学研究论文中所述。我发现与实际 roach 行为相匹配的概率不是有效演示中使用的人工概率值。SolveRastrigin 方法的定义将继续执行:
int tHunger = tMax / 10;
double minX = -10.0;
double maxX = 10.0;
int extinction = tMax / 4;
Random rnd = new Random(rndSeed);
本地变量 tHunger 确定何时 roach 将变得过大，将保留其当前所在的位置和邻居。例如，如果 tMax 10000 如下所示演示程序中，然后，当 roach 肚子值达到 tMax / 10 = 1000，roach 会将移动到新位置。
变量 minX 和 maxX roach 位置向量设置限制。(-10.0，+ 10.0) 的值是正常的机器学习权重，还对应于常用限制 Rastrigin 函数。例如，对于与维度的问题 = 3，位置矢量是三个单元格，都将有-10.0 和 + 10.0 之间的值的数组。
本地变量废弃确定当所有 roaches 将随时终止及能 reborn 新位置。此机制是重启，可帮助防止该算法滞留在非最佳解决方案。
本地 Random 对象 rnd 算法所使用的有三种目的。在其中处理 roaches 的顺序是随机选择;邻居 roaches 之间的信息的交换出现某些概率;并且没有要为其每个 roach 新速度随机组件。方法 SolveRastrigin 继续:
Roach[] herd = new Roach[numRoaches];
for (int i = 0; i < numRoaches; ++i)
herd[i] = new Roach(dim, minX, maxX, tHunger, i);
模拟 roaches 集合是名为人群的数组。有各种各样的有意义的名称为动物，如 whales pod 和 geese 匆忙的集合。实际上，蟑螂集合被称为 roaches 入侵。(此信息可以使有用栏匹配为您。)
请注意循环索引变量，i，传递给 Roach 构造函数。索引变量充当是 Roach 类定义的一部分的 Random 对象的随机种子。将传递一个循环索引变量，以用作随机种子值是一种机器学习中的常用技术。方法定义将继续执行:
int t = 0; // Loop counter (time)
int[] indices = new int[numRoaches];
for (int i = 0; i < numRoaches; ++i)
indices[i] = i;
double bestError = double.MaxValue;
double[] bestPosition = new double[numRoaches];
int displayInterval = tMax / 20;
该数组名为索引保留值 (0、 1 2...numRoaches-1)。将在主处理循环中随机排布数组，以便在其中处理 roaches 的顺序是每次不同。本地变量 bestPosition 和 bestError 保持最佳位置/解决方案并在任何时候通过任何 roach 找到相关联的错误。本地变量 displayInterval 确定何时将向控制台显示进度消息。接下来，数组的数组样式矩阵是实例化，以容纳所有的 roaches 对之间的距离:
double[][] distances = new double[numRoaches][];
for (int i = 0; i < numRoaches; ++i)
distances[i] = new double[numRoaches];
例如，如果距离 [0] [3] = 7.89 则距离 [3] [0] 也是 7.89 并且 7.89 roach 0 和 roach 3 之间的距离。请注意冗余数据不严重，因为在大多数情况下不会有大量的 roaches。接下来，主处理循环开始:
while (t < tMax)
{
if (t > 0 && t % displayInterval == 0) {
Console.Write("time = " + t.ToString().PadLeft(6));
Console.WriteLine(" best error = " +
bestError.ToString("F5"));
}
...
然后计算 roaches 之间的距离:
for (int i = 0; i < numRoaches - 1; ++i) {
for (int j = i + 1; j < numRoaches; ++j) {
double d = Distance(herd[i].position,
herd[j].position);
distances[i][j] = distances[j][i] = d;
}
}
使用 helper 方法 Distance，将立即看到计算距离值。此处索引的数组是变得有点棘手，但我会将它留给您要验证您感兴趣。接下来，距离值将复制从距离矩阵转换为数组以便可以进行排序，然后可以确定中间距离:
double[] sortedDists =
new double[numRoaches * (numRoaches - 1) / 2];
int k = 0;
for (int i = 0; i < numRoaches - 1; ++i) {
for (int j = i + 1; j < numRoaches; ++j) {
sortedDists[k++] = distances[i][j];
}
}
更好地示例说明数组的大小。假设有 n = 4 roaches。然后距离矩阵将具有大小 4 x 4。值的对角线上，[0] [0]，[1] [1]，[2] [2] 和 [3] [3] 将是 0.0，不应是包括在内。如此便还剩下 6 的值在 [0] [1]，[0] [2]，[0] [3]，[1] [2]，[1] [3] 和 [2] [3]。您不需要对称索引 [1] [0]，[2] [0] 处的相同的距离值，等等。因此，有 n * (n-1) / 2 不同距离值。接下来，计算的中间值 roaches 距离和随机化 roach 索引:
Array.Sort(sortedDists);
double medianDist = sortedDists[sortedDists.Length / 4];
Shuffle(indices, t); // t is used as a random seed
在这里，我将除以 4，因为之间的距离是四分之一从排序的距离数组的开头，因此结果实际上不是一个折衷的办法，正是四分位数。原始的研究论文使用实际的中值 (除以 2)，但是我发现四分位数，2 更好地工作。其理念是，四分位数的值决定了多少个近邻 roach 有，这反过来会影响 roaches 紧密程度进行分组。通过使用四分位数可阻止 roaches 分开，从而更好的机会来查找目标函数最大限度地棘手的全局最小值。
使用 helper 方法随机排布，将很快提供随机化 roach 索引。请注意时间索引变量，t，传递给无序播放方法，并且可作为无序播放随机数生成器的种子。接下来，循环来处理每个 roach 开始:
for (int i = 0; i < numRoaches; ++i) // Each roach
{
int idx = indices[i]; // Roach index
Roach curr = herd[idx]; // Ref to current roach
int numNeighbors = 0;
...
创建并命名为当前范围对当前 roach，人群 [idx] 的引用。这只是为了方便起见。接下来，计算的当前 roach 近邻域数量:
for (int j = 0; j < numRoaches; ++j) {
if (j == idx) continue;
double d = distances[idx][j];
if (d < medianDist) // Is a neighbor
++numNeighbors;
}
条件 j = = idx 用来防止当前 roach 计为自身的邻居。接下来，确定有效近邻域数量:
int effectiveNeighbors = numNeighbors;
if (effectiveNeighbors >= 3)
effectiveNeighbors = 3;
回想一下，计算近邻域数量的用途是确定的邻居将交换信息的概率。但信息交换的概率是相同的 3 个或多个相邻元素。接下来，算法会确定是否交换信息:
for (int j = 0; j < numRoaches; ++j) {
if (j == idx) continue;
if (effectiveNeighbors == 0) continue;
double prob = rnd.NextDouble();
if (prob > A[effectiveNeighbors - 1]) continue;
...
与所有其他 roaches，当前 roach 进行比较。如果当前 roach 没有相邻节点则没有信息交换。如果当前 roach 具有一个或多个邻居，概率的一个数组用于决定是否如果交换信息。接下来：
double d = distances[idx][j];
if (d < medianDist) { // a neighbor
if (curr.error < herd[j].error) { // curr better than [j]
for (int p = 0; p < dim; ++p) {
herd[j].groupBestPos[p] = curr.personalBestPos[p];
curr.groupBestPos[p] = curr.personalBestPos[p];
}
}
...
邻居 roaches 之间进行信息交换时，组最佳位置和关联的两个 roaches 更好的错误复制到更糟 roach。第二个分支的信息交换代码是:
...
else { // [j] is better than curr
for (int p = 0; p < dim; ++p) {
curr.groupBestPos[p] = herd[j].personalBestPos[p];
herd[j].groupBestPos[p] = herd[j].personalBestPos[p];
}
}
} // If a neighbor
} // j, each neighbor
邻居 roaches 之间进行信息交换已经处理完毕后，将移动当前 roach，如果不需要能够。在移动过程的第一部分是计算当前 roach 新速度:
if (curr.hunger < tHunger) {
for (int p = 0; p < dim; ++p)
curr.velocity[p] = (C0 * curr.velocity[p]) +
(C1 * rnd.NextDouble() * (curr.personalBestPos[p] -
curr.position[p])) +
(C1 * rnd.NextDouble() * (curr.groupBestPos[p] -
curr.position[p]));
新的速度有三个组件。第一个组件是在粒子群术语有时称为延时的旧速度。延时的作用要保留 roach 沿相同方向移动。第二个组件是 roach 最佳已知位置，有时称为认知术语。认知组件可防止 roach 移动到错误的位置。第三个组件是 roach 的邻居的已知最佳位置。此组件是更多或更少特有 RIO 且不具有标准名称。此第三个术语的作用将 roaches 组放在一起。
在计算的当前 roach 速度之后，移动 roach:
for (int p = 0; p < dim; ++p)
curr.position[p] = curr.position[p] + curr.velocity[p];
double e = Error(curr.position);
curr.error = e;
当前 roach 移动后，将检查其新位置，以查看它是否是新的最佳的 roach:
if (curr.error < curr.personalBestErr) {
curr.personalBestErr = curr.error;
for (int p = 0; p < dim; ++p)
curr.personalBestPos[p] = curr.position[p];
}
接下来，新位置进行检查，以查看是否是新的全局最佳，以及肚子计数器就会增加:
if (curr.error < bestError) {
bestError = curr.error;
for (int p = 0; p < dim; ++p)
bestPosition[p] = curr.position[p];
}
++curr.hunger;
} // If not hungry
每个 roach 循环完成时处理大量 roaches:
else { // Roach is hungry
{
herd[idx] = new Roach(dim, minX, maxX, tHunger, t);
}
} // j each roach
如果 roach 肚子计数器达到 tHunger 阈值，roach 移动到新的、 随机的位置。在处理完所有 roaches 后，该算法完成时通过检查它是否为全局废弃的时间、 递增的主循环 time 计数器并返回任何 roach 所找到的最佳位置:
if (t > 0 && t % extinction == 0) { // Extinction?
Console.WriteLine("Mass extinction at t = " +
t.ToString().PadLeft(6));
for (int i = 0; i < numRoaches; ++i)
herd[i] = new Roach(dim, minX, maxX, tHunger, i);
}
++t;
} // Main while loop
return bestPosition;
} // Solve
请注意，该算法包含在名为 SolveRastrigin 而不是一个更一般的名称，例如求解的方法。这里的思路是，RIO 真正元启发式算法，而不规定性算法，并需要进行自定义任何求最小值问题所尝试解决。
帮助程序方法
方法 SolveRastrigin 调用 helper 方法 Distance、 错误和无序播放。帮助程序方法 Distance 返回欧几里得距离 (平方的术语之间的差异之和的平方根):
static double Distance(double[] pos1, double[] pos2)
{
double sum = 0.0;
for (int i = 0; i < pos1.Length; ++i)
sum += (pos1[i] - pos2[i]) * (pos1[i] - pos2[i]);
return Math.Sqrt(sum);
}
帮助程序方法 Error 返回位于给定 roach Rastrigin 的函数的计算值的平方的差 x 位置和为零，则返回 true 的最小值:
public static double Error(double[] x)
{
double trueMin = 0.0; double rastrigin = 0.0;
for (int i = 0; i < x.Length; ++i) {
double xi = x[i];
rastrigin += (xi * xi) - (10 * Math.Cos(2 * Math.PI * xi)) + 10;
}
return (rastrigin - trueMin) * (rastrigin - trueMin);
}
方法无序播放随机排列的顺序使用 Fisher-yates 最小化算法数组中的值:
static void Shuffle(int[] indices, int seed)
{
Random rnd = new Random(seed);
for (int i = 0; i < indices.Length; ++i) {
int r = rnd.Next(i, indices.Length);
int tmp = indices[r]; indices[r] = indices[i];
indices[i] = tmp;
}
}
RIO 信息检索原版不随机化 roach 处理顺序，但我发现这种方法几乎总是提高了个人简历极具创意的优化算法的准确性。
几点注释
那么，是多么有效是与其他数字优化技术进行比较的 roach 启发优化? 根据我执行了几个限制试验，RIO 看起来解决一些比其他算法更好的基准测试问题，但效果弱于其他问题。我结束时，RIO 不是出色的新通用优化算法，它没有承诺，可能适用于某些特定求最小值问题。和 roach 感染优化确实，在所有计算机科学中都有一个最异常的名称。
Dr. James McCaffrey供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他参与过多个 Microsoft 产品的工作，包括 Internet Explorer 和 Bing。Scripto可通过 jammc@microsoft.com 与 McCaffrey 取得联系。
感谢以下的微软技术专家对本文的审阅: Todd Bello、Marciano Moreno Diaz Covarrubias 和 Alisson Sol