项目
03/10/2015

此文章由机器翻译。

测试运行

焰火算法优化

James McCaffrey 很多机器学习软件系统使用数值优化。例如，在 logistic 回归分析分类训练分类器是寻找关联的输入变量，以便收集的训练数据，计算出的输出值密切匹配已知的输出变量的值的权重的一组值的过程。换句话说，目标是优化（最小化）计算和期望输出值之间的误差。

有很多不同的数值优化算法。反向传播基于经典演算技术并常常用神经网络。粒子群优化算法模仿等植绒鸟类群体行为。遗传算法优化的一种形式的进化算法优化模型染色体复制的生物学过程。

这篇文章描述一个相对较新的（第一次在 2010 年出版）一种叫做烟花算法优化（粮农组织）的优化技术。这项技术并不显式模型或模仿行为的烟花炮竹，但当可以直观地显示该算法，由此产生的图像像放烟花的几何。

看到这篇文章将走向何方是，得到一个想法的粮农组织是什么，最好的方法是看一看该演示程序中图 1。该演示程序的目标是使用粮农组织找到艾克的 10 变量函数的最小值。艾克的函数是一个标准基准评价数值优化算法的有效性。演示版本具有最小值为 0.0 位于 (0、 0、 0、 0、 0、 0、 0、 0、 0，0)。艾克利的功能是棘手的因为它有很多地方的最低解决方案可以找到一个全局最小值之前捕获的搜索算法。艾克利的两个变量的函数图所示图 2。

图 1 烟花算法优化在行动

图 2 艾克利两个变量的函数

该演示程序将烟花数目设置为 5。更多的烟花增加的机会找到一个真正的最优解，这会降低性能。粮农组织通常能够处理 3 到 10 烟花。粮农组织是一个迭代的过程，需要最大的循环计数器值。在机器学习优化的循环计数器变量往往是命名的"时代"，演示设置最大值为 1,000 迭代。这是有点小，用于演示目的，并在现实场景中，从 10000 到 100000 的值是典型。

在这个演示中运行图 1，到目前为止发现的最好的位置相关联的最好（最小）错误显示每 100 的时代。注意到粮农组织开始收敛速度非常快。在 1,000 时代之后发现的最佳位置是（0.034 0.098 0.003 0.132-0.054 0.181-0.018 为 0.051 0.004-0.023）和关联的错误是 0.41。如果时代的最大数目增加至一万个，粮农组织将事实上找到了问题的最优解。粮农组织，像大多数的数值优化算法，并不保证在现实情况下的最优解还不知道在哪里找到最优的解决方案。

这篇文章假设你有至少中级编程技能，但不会假设你知道任何有关数值优化或粮农组织。该演示程序编码使用 C# 中，但你不应该有太大的困难，到另一种语言如 JavaScript 或 Python 代码进行重构。

演示代码有点太长，无法显示其全部内容，但完整的源代码是本文附带的代码下载中提供。演示代码具有最正常的错误检查已删除，以保持较小的代码的大小并尽可能清楚的主要思想。

程序的整体结构

程序的整体结构，与一些少量的编辑，以节省空间，提出了图 3。若要创建演示，我启动 Visual Studio，创造了一个新 C# 控制台应用程序命名为烟花爆竹算法。演示有没有重大的.NET 依赖关系，因此，任何新版本的 Visual Studio 会工作。

图 3 程序的整体结构

using System;
using System.Collections.Generic;
namespace FireworksAlgorithm
{
  class FireworksProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin fireworks algorithm demo\n");
      Console.WriteLine("Goal is to solve Ackley's function");
      Console.WriteLine("Function has min value = 0.0 at (0, .. ))");
      int dim = 10;
      int n = 5;    // Number of fireworks
      int maxEpochs = 10000;
      Console.WriteLine("\nSetting Ackley's dimension to " + dim);
      Console.WriteLine("Setting number fireworks to " + n);
      Console.WriteLine("Setting maxEpochs to " + maxEpochs);
      Console.WriteLine("\nBegin algorithm\n");
      double[] bestPosition = Solve(dim, n, maxEpochs);
      Console.WriteLine("\nAlgorithm complete");
      Console.WriteLine("\nBest solution found: ");
      for (int i = 0; i < dim; ++i)
        Console.Write(bestPosition[i].ToString("F3") + " ");
      Console.WriteLine();
      double error = Error(bestPosition);
      Console.WriteLine("\nError of best solution found = " +
        error.ToString("F5"));
      Console.WriteLine("\nEnd fireworks algorithm demo\n");
      Console.ReadLine();
    } // Main
    public static double Error(double[] position) { . . }
    public static double[] Solve(int dim, int n, int maxEpochs) { . . }
    private static int[] PickDimensions(int dim, int z, int seed) { . . }
    private static double YMax(Info[] fireworks) { . . }
    private static double YMin(Info[] fireworks) { . . }
    private static int[] NumberSparks(Info[] fireworks, int m,
      double a, double b) { . . }
    private static double[] Amplitudes(Info[] fireworks, int A,
      int epoch, int maxEpochs, double minX, double maxX) { . . }
    private static double MinAmplitude(int epoch, int maxEpochs,
      double minX, double maxX) { . . }
    private static void AddGaussianSparks(Info[] fireworks,
      List<Info>[] sparksList, int dim, int mHat, int epoch, double minX,
      double maxX, double[] bestPosition, ref double bestError, Random rnd)
  }
  public class Info
  {
    public double[] position;
    public double error;
  }
} // ns

模板代码加载到 Visual Studio 编辑器后，在解决方案资源管理器窗口中我将 Program.cs 文件重命名为更具描述性的 FireworksProgram.cs，Visual Studio 将自动重命名类程序对我来说。顶部的源代码中，删除所有使用指向不需要命名空间的语句，留下只是系统和 Collections.Generic 的引用。

我编码演示使用静态方法，而不是面向对象编程（OOP）方法。演示了所有的控制逻辑，在 Main 方法中，调用两个公共方法，求解和误差。基本的调用语句是：

int dim = 10;
int n = 5;
int maxEpochs = 1000;
double[] bestPosition = Solve(dim, n, maxEpochs)
double error = Error(bestPosition);

变量的 dim 认为问题的维数。在机器学习训练，这通常会模型权重确定的数量。变量 n 是烟花数目。我尽可能多使用相当简洁的变量名，如 n，所以你可以更容易地使用这些文件作为一种资源在粮农组织的研究论文中使用。粮农组织技术载有方法解决。方法错误接受一个位置（数组 10 个值），计算这些值的艾克的函数的值和返回的总和的计算的输出和 0.0 的已知的最低差值的平方的平均值。

该演示程序有一个名为信息那封闭的实用程序类sulates 的位置和它关联的错误。课堂上有没有相关联的方法，如显式的构造函数，以方便您对面向对象的有限支持的语言的演示代码进行重构。

理解算法

在图中说明的烟花算法过程图 4。图像表示简化虚拟最小化的问题，不该演示程序的艾克的功能。虚拟问题的目标是尽量减少一些任意的函数具有两个输入的变量，X 和 Y，该函数有一个最小值为 0.0 位于 X = 0 和 Y = 0。

图 4 烟花算法

在图像图 4 使用三个烟花。每个烟花有所谓的火花。有两种火花，定期和高斯。图 5 显示烟花算法层次非常高的伪代码中。

图 5 中高层的伪代码的烟花算法

initialize 3 fireworks to random positions
loop until done
  for each firework
    calculate the amplitude of the firework
    calculate the number of regular sparks
    generate the regular sparks
  end for
  generate special Gaussian sparks
  evaluate each spark
  from the list of sparks,
    select 3 to act as positions of new fireworks
  create 3 new fireworks
end loop
return the position of the best spark found

中的图像图 4，由彩色圆点标记在表示三个烟花的立场 2-6），（3，4）和 3-3）。注意到第一的烟花是最坏的打算，因为它是最远距离的目标位置 (0，0) 和第三的烟花是最好的因为它是最接近。振幅由每个烟花的虚线圆圈表示。好烟花有较小的振幅和坏烟花有较大的振幅。

每个烟花将产生不同数量的常规（非高斯）火花。坏的烟花将产生比好烟花少火花。在图 4、烟花 [0] 生成三个火花、烟花 [1] 生成四个火花和烟花 [2] 生成五个火花。每个常规的火花会位于其父烟花振幅。因为好的烟花有小振幅和相对较多的火花，算法搜索将集中附近好烟花。坏的烟花不应完全忽视，因为它们可能导致位于当前烟花爆竹的范围外的最优解。在这种情况下他们倾向于位于烟花和搜索过程中遇到任何火花的著名位置之间生成高斯的火花。

所有的经常预算和高斯火花产生后，每个进行了评价。从当前的火花中选择新烟花爆炸的下一轮。最好的星火的位置保留作为一个新的烟花爆竹，加紧搜索地点好。最糟糕的火花的位置保留保持搜索多样性并防止该算法快速折叠上可能不是最佳的解决方案。其余的烟花炮竹，在简单的示例中只是一个烟花阵地图 4，随机抽取的当前的火花。

烟花，然后火花的生成过程被迭代直到满足一些停止条件。停止条件是在该演示程序的情况下只是一个最大的循环计数器值。当粮农组织用机器学习的训练，停止条件可能还会包括错误阈值，以便当误差下降到低于一些小的指定值，取决于特定的解决，处理循环终止。

烟花算法实现

方法求解的定义开始：

public static double[] Solve(int dim, int n, int maxEpochs)
{
  int m = n * 10;
  int mHat = 5;
  double a = 0.04;
  double b = 0.8;
  int A = 40;
  double minX = -10.0;
  double maxX = 10.0;
...

变量 m 是定期的火花，将分配给 n 烟花的总数。变量 mHat （这样命名是因为研究论文使用小写 m 与克拉遍）是特别高斯数目火花产生。变量和 b 控制为任何特定的烟火火花的最小值和最大数量。变量 A 是最大振幅为任何烟花。变量这个混蛋和 maxX 举行信息对象位置数组中的任何单个值的最小和最大值。

方法解决创建 n 初始的烟火，就像这样：

Random rnd = new Random(3);
Info[] fireworks = new Info[n];
for (int i = 0; i < n; ++i)
{
  fireworks[i] = new Info();
  fireworks[i].position = new double[dim];
  for (int j = 0; j < dim; ++j)
    fireworks[i].position[j] = (maxX - minX) 
      * rnd.NextDouble() + minX;
  fireworks[i].error = Error(fireworks[i].position);
}

随机对象 rnd 最初使用 3 一个种子值，只是因为该值给代表演示运行。每一个 n 烟花被存储为数组中的信息对象。初始化代码拿这个混蛋和 maxX 位置数组的每个单元格之间的随机值。对于一些特定的机器学习培训场景，较为可取来初始化初始的烟花，所以他们相距很远。

方法解决继续通过建立变量以保存的任何类型的火花，发现的最佳位置，该位置相关联的错误。像烟花，有一个固定的数字，每烟火火花数目会有所不同主要处理循环中，每个迭代中所以火花都存储在列表集合，而不是数组中：

double[] bestPosition = new double[dim];
for (int k = 0; k < dim; ++k)
  bestPosition[k] = fireworks[0].position[k];
double bestError = fireworks[0].error; // arbitrary
List<Info>[] sparksList = new List<Info>[n];
for (int i = 0; i < n; ++i)
  sparksList[i] = new List<Info>();

主处理循环的开始：

int epoch = 0;
while (epoch < maxEpochs)
{
  if (epoch % 100 == 0) // Show progress every 100 iterations
  {
    Console.Write("epoch = " + epoch);
    Console.WriteLine(" error at best known position = " +
      bestError.ToString("F4"));
  }
...

在这里，进度显示每 100 的时代。你可能想要考虑通过一个名为"进步"来控制是否显示进度消息的布尔型标志变量：

int[] numberSparks = NumberSparks(fireworks, m, a, b);
double[] amplitudes = 
  Amplitudes(fireworks, A, epoch, maxEpochs, minX, maxX);
for (int i = 0; i < n; ++i)
  sparksList[i].Clear(); // Number of sparks changed

接下来，数目为每个烟花和每个烟花最大振幅的火花，计算使用 NumberSparks 和振幅的帮助器方法。为一场烟火火花数目是正比的烟花错误这样好烟花接收 m 总经常火花占较大比重。同样，每个幅度是成正比的错误，这样好烟花有较小幅度。

接下来，每一颗火星进行实例化：

for (int i = 0; i < n; ++i)
{
  double amp = amplitudes[i]; // Amplitude for curr firework
  int ns = numberSparks[i];   // Number of sparks for curr firework
  for (int j = 0; j < ns; ++j) // Each spark for curr firework
  {
    Info spark = new Info(); // A spark has a position and error
    spark.position = new double[dim]; // Allocate space (ctor doesn't)
    for (int k = 0; k < dim; ++k) // Spark position based on its parent firework
      spark.position[k] = fireworks[i].position[k];

火花位置基于其父烟花位置。接下来，几个 (z) 的位置数组的维数随机选择，并随机位移添加到位置数组：

int z = (int)Math.Round(dim * rnd.NextDouble());
int[] dimensions = PickDimensions(dim, z, epoch);
for (int ii = 0; ii < dimensions.Length; ++ii)
{
  double h = amp * 2 * rnd.NextDouble() - 1;
  int k = dimensions[ii]; // convenience
    spark.position[k] += h; // displace from parent
  if (spark.position[k] < minX || spark.position[k] > maxX)
    spark.position[k] = (maxX - minX) * rnd.NextDouble() + minX;
}
spark.error = Error(spar.position);
sparksList[i].Add(spark);

生成一个火花之后, 方法解决检查，看看是否新火花有最好的位置发现到目前为止：

if (spark.error < bestError)
    {
      bestError = spark.error;
      for (int k = 0; k < dim; ++k)
        bestPosition[k] = spark.position[k];
    }
  } // Each new regular spark
} // Each firework

其次，特殊的高斯火花生成：

AddGaussianSparks(fireworks, sparksList, dim, mHat,
  epoch, minX, maxX, bestPosition, ref bestError, rnd);

帮助器方法 AddGaussianSparks 生成特殊的火花，以便其立场趋于随机选定的烟花和最著名的位置之间。方法解决最后的最佳和最差的火花产生的发现和使用它们的立场为两个新的烟火为下一次迭代。其余的 n 2 烟花是使用随机选定的火花创建的：

...
    // Find best, worst spark
    // Create 2 new fireworks
    // Create remaining n-2 fireworks
    ++epoch;
  } // main loop
  return bestPosition;
} // Solve

请参阅代码下载实现细节。

几个评论

烟花算法的原纸是"烟花算法的优化，"由 Y。谭和 Y。朱（2010 年）。该文件载有几个错误，使得该算法不切实际的真实生活优化的因素。其他研究人员迅速指出这些缺陷。我的文章基于主要 2013年论文，"增强烟花算法"，由美国 A.郑亚内切克和 Y。谭。您可以在 Internet 上的几个位置找到这两篇论文。我取得了相当多的简化和对在这两个研究论文中提出的算法的轻微修改。在我看来，没有足够的研究证据尚未回答烟花优化是否比其他优化算法比好或差的问题。但它确实很有趣。

James McCaffrey 博士 任职于华盛顿州雷德蒙德市的 Microsoft 研究中心。他长期从事多个 Microsoft 产品（包括 Internet Explorer 和 Bing）的研发工作。可以在 jammc@microsoft.com 上联系 McCaffrey 博士。

衷心感谢以下 Microsoft 技术专家对本文的审阅：托德 · 贝洛、 Kenneth 格里芬、 Yong 刘、布莱恩 · 琳、叶辛萨卡