测试运行

2015-07-13

多粒子群优化

多群优化 (MSO) 是一种技术估计很难或不可能的数值问题的解决。它是一种变异的粒子群优化算法（见我的文章在主题上 msdn.microsoft.com/magazine/hh335067)。定期的粒子群优化模型植绒的行为，例如，在群体的鸟类和鱼类的学校中看到。MSO 延伸通过使用几个群的模拟粒子，而不单一的群粒子群优化算法。

MSO 可以应用于几个机器学习方案，例如，估计的权重和偏置值的人工神经网络或估算弱学习者合奏分类和预测中的权重。MSO 是元启发式，这意味着，技术真的一套设计原则和准则，可以用于构造特定的算法来解决特定的优化问题。

了解多群优化的好方法是，审查中的演示程序图 1 和中的图图 2。该演示程序估算称为 Rastrigin 的函数的标准基准数值优化问题的解决办法。目标是要找到 x 0 和最小化该函数的 x 1 的值：

图 1 多群优化演示

图 2 Rastrigin 函数

该函数有已知的解决方案的 f = 0.0 时 x 0 = 0.0 和 x 1 = 0.0，因此 MSO 的使用并不是真的有必要在这种情况。中的图图 2 显示 Rastrigin 的功能。虽然该函数具有许多不同的山峰和山谷代表错误的解决办法，目前只有一个全球最低，图像的中心。Rastrigin 的函数的多个关闭-但是-不-相当解决方案是在蓄意和旨在优化算法的麻烦。

演示程序中的图 1 开始通过设置一些 MSO 算法的输入参数。有三个群，每个群有四个粒子。在大多数的数值优化问题，以某种方式限制可能值的范围。在这里，搜索空间是最初只限于 x-100.0 和 +100.0 之间的值。

该演示程序初始化每个粒子的 12 到随机 (x 0，x 1) 的值。每一对值表示粒子的位置，也可以被解释为可能的解决办法。Rastrigin 的函数在每个位置的值被调用的位置，建议的目标是尽量减少功能的成本。初始化后，最佳的粒子 (一个最小成本）是群 2 中的粒子从零开始的索引 0。该粒子具有位置 [-40.57，28.54] 和相关的成本 2498.93。

多群优化是一个迭代过程。演示计划设置的任意环路最大值为 150。MSO 算法然后搜索更好的解决方案，跟踪的由任何 12 粒子发现的最佳解决方案。在结束了 150 迭代，找到最佳的解决方案是 f = 0.000043 在 x 0 =-0.0003，x 1 = 0.0004，是非常接近但不是太实际的解决方案。演示计划其实可以找到实际解决方案通过将 maxLoop 变量设置为 500，但很重要的是要记住在最现实的问题情况下你不会知道是否 MSO 已找到最佳解决方案。

本文假定您有至少中间级的编程技能，但不会假设你知道多群优化的事。该演示程序编码在 C# 中，但你不应该有太多的麻烦重构到另一种语言。为了保持小代码的大小和主要思想清晰，我已删除大部分正常的错误检查从演示的代码。演示是太长，目前其整体在这篇文章，但整个源代码，该代码是可在 archive.msdn.microsoft.com/mag201309TestRun。

程序的整体结构

演示程序，与一些轻微的编辑和删除，应使用 WriteLine 语句的大部分结构提出的图 3。

图 3 多群演示的程序结构

using System;
namespace MultiSwarm
{
  class MultiSwarmProgram
  {
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine(
          "\nBegin Multiple Particle Swarm optimization demo\n");
        int dim = 2;
        double minX = -100.0;
        double maxX = 100.0;
        int numParticles = 4; // Particles in each swarm
        int numSwarms = 3; // Swarms in multi-swarm
        Multiswarm ms = new Multiswarm(numSwarms, numParticles, 
          dim, minX, maxX);
        Console.WriteLine("\nInitial multiswarm:");
        Console.WriteLine(ms.ToString());
        int maxLoop = 150;
        ms.Solve(maxLoop);
        Console.WriteLine("\nFinal multiswarm:");
        Console.WriteLine(ms.ToString());
        Console.WriteLine("\nBest solution found = " +
          ms.bestMultiCost.ToString("F6"));
        Console.Write("at x0 = " + ms.bestMultiPos[0].ToString("F4"));
        Console.WriteLine(", x1 = " 
          + ms.bestMultiPos[1].ToString("F4"));
        Console.WriteLine("\nEnd demo\n");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
        Console.ReadLine();
      }
    }
    public static double Cost(double[] position) { . . }
  } // Program
  public class Particle { . . }
  public class Swarm { . . }
  public class Multiswarm { . . }
} // ns

要创建该演示程序我使用 Visual Studio 2012。演示了没有显著的相关性，和任何版本的 Visual Studio 应工作。我选的 C# 控制台应用程序模板，名为 MultiSwarm 的项目。 Visual Studio 加载的代码模板后，在解决方案资源管理器窗口改名 Program.cs 文件到 MultiSwarmProgram.cs 和 Visual Studio 自动改名程序类为我。在顶部的源代码已删除所有不需要的离开只是对 System 命名空间的引用的命名空间引用。

演示计划定义了一个公共范围成本方法，这是 Rastrigin 的功能：

public static double Cost(double[] position)
{
  double result = 0.0;
  for (int i = 0; i < position.Length; ++i) {
    double xi = position[i];
    result += (xi * xi) - (10 * Math.Cos(2 * Math.PI * xi)) + 10;
  }
  return result;
}

成本方法接受单个数组参数，表示一个粒子的位置，是一个可能的解决方案。在最机器学习方案中，你想尽量减少的成本函数表示某种形式的错误，并将需要额外的参数，如培训的数据源。成本函数通常是 MSO 的性能瓶颈，所以你应该代码要尽可能高效。

Multiswarm 类封装的 MSO 算法。类粒子和群是 Multiswarm 类的帮助器类。在支持嵌套的类定义语言中替代设计是定义在 Multiswarm 类的内部的类粒子和群。

该演示程序开始通过设置五个输入参数：

int dim = 2;
double minX = -100.0;
double maxX = 100.0;
int numParticles = 4;
int numSwarms = 3;

变量 dim 表示要解决的问题中的维度数。因为 Rastrigin 的函数接受 x 0 和 x 1，dim 的值设置为 2。多群优化算法非常适合与任何数目的尺寸的问题。变量荡妇和 maxX 限制搜索范围有限的值。荡妇和马科斯的值将会从问题到问题发生变化。变量 numParticles 定义在每个群的粒子的数量。变量 numSwarms 定义蝗群的总数。一般情况下，numParticles 和 numSwarms 的值越大，生成更准确的解决方案，这会降低性能。

下一步，主多群对象实例化，并且求解算法的 MSO 称为：

Multiswarm ms = new Multiswarm(numSwarms, numParticles, 
  dim, minX, maxX);
Console.WriteLine("\nInitial multiswarm:");
Console.WriteLine(ms.ToString());
int maxLoop = 150;
ms.Solve(maxLoop);

演示调用的"群"，粒子的集合和集合的蝗群"多群"。而不是此命名方案，一些研究文学调用的粒子"小组群"的集合和集合的群"群"。Multiswarm 对象进行实例化使用先前定义的输入的参数。变量 maxLoop 持有主要解决算法循环将循环访问的最大次数。一般情况下，maxLoop 的较大的值将产生更准确的解决方案，这会降低性能。

解决方法反复搜索 Rastrigin 的功能的最佳解决方案。注意成本函数从外部定义的 Multiswarm 对象。在大多数情况下，MSO 代码是集成到一个软件系统而非作为一个类库 DLL 中，这就需要你（通过一个委托，为示例）到 Multiswarm 对象传递成本函数或使用界面设计方法来定义一个编程的合同执行。

解决方法完成执行后，Multiswarm 对象的最终状态显示，并在多群在任何群中发现的任何粒子的最佳解决方案显式显示：

Console.WriteLine("\nFinal multiswarm:");
Console.WriteLine(ms.ToString());
Console.WriteLine("\nBest solution found = " +
 ms.bestMultiCost.ToString("F6"));
Console.Write("at x0 = " + ms.bestMultiPos[0].ToString("F4"));
Console.WriteLine(", x1 = " + ms.bestMultiPos[1].ToString("F4"));

粒子

粒子类有六名成员：

static Random ran = new Random(0);
public double[] position;
public double[] velocity;
public double cost;
public double[] bestPartPos;
public double bestPartCost;

我更愿意使用公共范围为简单起见，但你可能想要使用私人范围以及获取和设置属性的方法。随机对象由构造函数用于初始化的随机位置的粒子对象。命名位置的数组代表一个粒子的位置。阵列速度表示的速度和方向的粒子。例如，假设一个粒子的位置 [12.0，24.0] 是和速度是 [5.0，0.0]。这可以解释为在下一次的时间增量期间粒子将移动沿 x 0 5.0 单位维度和沿 x 1 0.0 单位维度。微粒移动后，将其新位置 [17.0，24.0]。

可变成本持有成本函数的值在当前的位置。变量 bestPartCost 着粒子遇到过的最好（最小）成本值和变量 bestPartPos 是最有名的成本，在发现了的位置。

粒子构造函数定义在图 4。

图 4 的粒子构造函数

public Particle(int dim, double minX, double maxX)
{
  position = new double[dim];
  velocity = new double[dim];
  bestPartPos = new double[dim];
  for (int i = 0; i < dim; ++i) {
    position[i] = (maxX - minX) * ran.NextDouble() + minX;
    velocity[i] = (maxX - minX) * ran.NextDouble() + minX;
  }
  cost = MultiSwarmProgram.Cost(position);
  bestPartCost = cost;
  Array.Copy(position, bestPartPos, dim);
}

构造函数为基于问题的维数的位置、速度和 bestPartPos 数组分配空间。每个位置和速度单元格分配荡妇与 maxX 之间的随机值。计算成本的初始位置。粒子的最著名的位置和成本被设置为的初始位置和成本。

一重大的替代方法是将分配给每个粒子的非随机的初始位置。一些 MSO 研究文献表明向不同区域的搜索空间分配在不同群粒子是优于随机分配的办法。例如，如果你有两个群 10 粒子中的每个，在第一群 10 粒子能被分配职位与-100.0 和 0.0 和 10 粒子之间的 x 值在 0.0 和 +100.0 之间的位置的 x 值与第二次群。然而，我不完全相信，这些研究结果，简单的随机粒子的位置分配曾对我在实践中。

蝗群

一大群是粒子的集合。群类有三个成员:

public Particle[] particles;
public double[] bestSwarmPos;
public double bestSwarmCost;

命名可以与 MSO 有点棘手。我的名字作为"粒子，"群类粒子对象的数组，但可能要改为使用名称"群"。成员变量 bestSwarmCost 持有由任何粒子的发现在群算法执行过程中的最佳（最小）成本。数组 bestSwarmPos 的立场这最好的群成员成本被发现的地方。

群构造函数所示图 5。

图 5 群构造函数

public Swarm(int numParticles, int dim, double minX, double maxX)
{
  bestSwarmCost = double.MaxValue;
  bestSwarmPos = new double[dim];
  particles = new Particle[numParticles];
  for (int i = 0; i < particles.Length; ++i) {
    particles[i] = new Particle(dim, minX, maxX);
    if (particles[i].cost < bestSwarmCost) {
      bestSwarmCost = particles[i].cost;
      Array.Copy(particles[i].position, bestSwarmPos, dim);
    }
  }
}

群构造函数分配空间，然后调用粒子构造函数 numParticles 次，产生随机位置粒子。创建的每个粒子时，它检查，看看是否它有任何的颗粒的最佳成本在群。

Multiswarm 类

多群是一个集合的蝗群。顶级的 Multiswarm 类有七个成员：

public Swarm[] swarms;
public double[] bestMultiPos;
public double bestMultiCost;
public int dim;
public double minX;
public double maxX;
static Random ran = new Random(0);

阵列群保存每个群对象，每个粒子对象的集合。所以群 [2] [3].particles.position [0] 表示粒子 3 群 2 中的 x 0-值。

成员变量 bestMultiCost 持有任何粒子在发现任何群算法执行过程中的最佳成本。数组 bestMultiPos 的立场关联最好的全球成本被发现的地方。成员变量变暗，荡妇和 maxX 存储为方便所以它们的值可以使用的类方法没有被作为参数传递。

召回类粒子具有随机对象命名为跑了，用来生成最初的随机位置。类 Multiswarm 有一个不同的随机对象，MSO 算法用于求解过程中插入伪随机的行为。

Multiswarm 构造函数列在图 6。

图 6 Multiswarm 构造函数

public Multiswarm(int numSwarms, int numParticles, int dim,
  double minX, double maxX)
{
  swarms = new Swarm[numSwarms];
  bestMultiPos = new double[dim];
  bestMultiCost = double.MaxValue;
  this.dim = dim;
  this.minX = minX;
  this.maxX = maxX;
  for (int i = 0; i < numSwarms; ++i)
  {
    swarms[i] = new Swarm(numParticles, dim, minX, maxX);
    if (swarms[i].bestSwarmCost < bestMultiCost)
    {
      bestMultiCost = swarms[i].bestSwarmCost;
      Array.Copy(swarms[i].bestSwarmPos, bestMultiPos, dim);
    }
  }
}

后分配数组并保存输入的参数值，Multiswarm 的构造函数调用群构造函数 numSwarms 次。创建每个群时，在那群内任何粒子的最佳成本检查以查看它是否全球最佳成本。如果是这样，那成本和其相关联的位置存储到 bestMultiCost 和 bestMultiPos，分别。

MSO 算法

在非常高级别伪代码中，基本的 MSO 算法是：

loop maxLoop times
  for each swarm
    for each particle
      compute new velocity
      use velocity to update position
      check if a new best cost has been found
    end for
  end for
end loop

在 MSO 的密钥操作计算粒子的新速度。对于一个给定的粒子的新速度受影响的当前速度、当前的位置、粒子的最著名的位置、在同一群作为粒子的任何粒子最有名位置和任何群中最著名的任何粒子位置。在数学术语中，新的速度是：

v(t+1) = w * v(t) +
         (c1 * r1) * (p(t) - x(t)) +
         (c2 * r2) * (s(t) - x(t)) +
         (c3 * r3) * (m(t) - x(t))

新的速度已计算后，粒子的新的位置是：

x(t+1) = x(t) + v(t+1)

和我一起承担了一会儿。计算简单很多比它第一次出现。词 v(t+1) 意味着速度在时间 t + 1，换句话说，新的速度。词 v(t) 是的当前速度。词 x (t) 是当前的位置。注意那 x 和 v 是在粗体，这表明他们是向量如 [12.0，25.0] 而不是单个值。

词 p(t) 是一个粒子最著名的立场。 S (t) 一词是任何粒子的粒子群中的最佳位置。期限估算是任何粒子在任何群中的最佳位置。

词 w 是一个常数，称为惯性因素。条款 c1、 c2 和 c3 是建立的每个组件的新速度的最大变化的常数。条款 r1、 r2 和 r3 是介于 0 和 1 之间的随机值，提供给每个速度更新随机效果。

新的流速计算是可能最好的示例解释。假设一个粒子是目前在 [12.0，24.0] 和其当前的速度是 [-1.0，-3.0]。也最著名的粒子位置 [8.0，10.0] 任何粒子在群最著名的立场是 [7.0、 9.0]，和任何粒子在任何群中最著名的立场是 [5.0、 6.0]。并假设常数 w 已值 0.7、常数 c1 和 c2 是两个 1.4，恒定 c3 为 0.4。最后，假定随机值 r1，r2 和 r3 是所有 0.2。

新粒子的速度所示图 7。

图 7 计算的新粒子的速度

v(t+1) = 0.7         * [-1.0, -3.0] +
         (1.4 * 0.2) * [8.0, 10.0] - [12.0, 24.0] +
         (1.4 * 0.2) * [7.0, 9.0] - [12.0, 24.0] +
         (0.4 * 0.2) * [5.0, 6.0] - [12.0, 24.0]
       = 0.7 * [-1.0, -3.0] +
         0.3 * [-4.0, -14.0] +
         0.3 * [-5.0, -15.0] +
         0.1 * [-7.0, -18.0]
       = [-0.7, -2.1] +
         [-1.2, -4.2] +
         [-1.5, -4.5] +
         [-0.7, -1.8]
       = [-4.1, -12.6]

因此，根据图 7，粒子的新的位置是：

x(t+1) = [12.0, 24.0] + [-4.1, -12.6]
       = [7.9, 11.4]

假设最优的解决方案就是 [0.0，0.0]，正如 Rastrigin 的函数的情况，注意到粒子已从其原始位置移动到新的位置，则更接近于最佳的解决方案。

在 v(t+1) 中的惯性词鼓励一个粒子继续在其当前的方向移动。 P(t) 一词鼓励一个粒子走向及其历史最著名的地位。 S (t) 一词鼓励一个粒子走向的粒子群伴侣的任何发现的最著名的位置。估算一词鼓励任何群中发现的任何粒子的最著名位置走向一个粒子。

常数 c1、 c2 和 c3 有时也称为认知、社会和全球重量。这些常量，以及随机值 r1、 r2 和 r3 和惯性权重 w，确定多少每个术语影响粒子的运动。定期粒子群优化中的一些研究表明合理值为 w，c1 和 c2 分别是 0.729，1.49445 和 1.49445。有小小的研究对 c3 常数在 MSO，但我通常使用 0.3645 （惯性重量的一半），这曾对我在实践中。

死亡和入境事务处

有几个令人着迷的方法修改基本的 MSO 算法。一种可能性是本质上时不时，杀了一个随机选择的粒子，然后生出一个新的粒子。该演示程序使用此死亡出生修改。解决方法的前几行所示图 8。

图 8 的第一个行的解决方法

public void Solve(int maxLoop)
{
  // Assign values to ct, w, c1, c2, c3
  double death = 0.005; ; // Prob of death
  while (ct < maxLoop)
  {
    ++ct;
    for (int i = 0; i < swarms.Length; ++i) {
      for (int j = 0; j < swarms[i].particles.Length; ++j) {
        double p = ran.NextDouble();
        if (p < death)
          swarms[i].particles[j] = new Particle(dim, minX, maxX);
        for (int k = 0; k < dim; ++k) {
...

该方法生成一个介于 0 和 1 之间的随机值，并将它存储到 p。如果随机值小于 0.005，当前粒子重新通过实例化并调用的粒子构造函数、有效地杀害当前粒子和生育新粒子在随机位置。

MSO 的另一个选项是向入境事务处模型通过定期考虑两个粒子在不同群和他们交流。一个粒子有效移民入当前群和另一个粒子身故出群。演示计划包含此选项。关键方法是：

private void Immigration(int i, int j)
{
  // Swap particle j in swarm i
  // with a random particle in a random swarm
  int otheri = ran.Next(0, swarms.Length);
  int otherj = ran.Next(0, swarms[0].particles.Length);
  Particle tmp = swarms[i].particles[j];
  swarms[i].particles[j] = swarms[otheri].particles[otherj];
  swarms[otheri].particles[otherj] = tmp;
}

方法很简单，并允许一个粒子可能与本身进行交换的不良可能性。入境事务处功能称为方法解决内部就像这样：

double immigrate = 0.005;
...
double q = ran.NextDouble();
if (q < immigrate)
  Immigration(i, j);

总结

在这篇文章和附带的代码下载中提出的解释应该给你坚实的试验与多群优化效率。相比定期粒子群优化算法，多群优化只是稍微复杂，往往会产生更高质量的结果，虽然它是速度较慢。我与 MSO 的经验表明它往往要处理很难优化问题 — — 那些与许多局部极小值 — — 比常规粒子群优化算法。

MSO 是一种通用的数值优化元启发式，为了找到一组权数最大限度减少某种错误函数通常用于作为一个较大的机器学习方案的一部分。例如，可以使用 MSO 来寻找一种神经网络通过最小化分类错误的训练数据集上的最好的一套权重和偏置值。有很多替代 MSO，包括进化优化算法（也称为实数型遗传算法）、细菌觅食优化和变形虫方法优化。

相比大多数替代通用数值优化方法，在我看来 MSO 是实施更简单、更容易地进行自定义。相比一些替代品的 MSO 的缺点是一般有几个准则选择 MSO 免费的参数包括惯性重量常量和认知、社会和全球体重常数的值。这说，不过，我的 MSO 粉丝和它曾演出非常好，我当我需要我的软件系统中解决数值优化问题的场合。

Dr。James McCaffrey 在华盛顿州雷德蒙德，校园为微软工作。他已为多种 Microsoft 产品效过力，包括 Internet Explorer 和 MSN Search。他是《.NET Test Automation Recipes》(Apress, 2006) 的作者，您可以通过以下电子邮箱地址与他联系：jammc@microsoft.com。

衷心感谢以下技术专家对本文的审阅：柯克 Olynyk (Microsoft)

通过