人工智能

粒子群优化

James McCaffrey

下载代码示例

粒子蜂群优化 (PSO) 是一种人工智能 (AI) 技术，可用于查找近似极难或不可能的数值最大化和最小化问题的解决方案。PSO 我在本文中介绍的版本是第一次在 1995年研究论文中看到由 J.肯尼迪和键。Eberhart。组行为，例如鸟 flocking 和 schooling 松散效仿 PSO。最好为您 PSO 将体会并查看其中我的标题此处是检查图 1。

图中的第一部分描述虚拟演示 PSO 程序所解决的问题。目的是找到值 x0 和 x1 操作函数 f 的值 = 3 + x 0 ^2 + x ^2 已最小化。我在此处使用表示法 ^2 表示变操作。请注意我特意选择保留 PSO 清晰的思想转变是不现实的简单问题。很明显此问题的解决方案是 0 = 0.0 x 和 x 1 = 0.0，因此使用 PSO 不确实需要产生 3.0 中，一个最小的函数值。我将介绍通过 PSO 可以解决本文中稍后介绍的更具现实意义的问题。在此示例中，要最小化的函数的维度为 2，因为我们需要对其进行求解 2 的数值。一般情况下，PSO 是适合于数值问题为 2 或更大。在大多数情况下，PSO 必须具有某些约束可能 x 值的范围。此处x0 和 x1 限于任意区域设为 100.0 100.0。

图 1粒子蜂群优化演示运行

下一部分的图 1指示 PSO 程序正在使用 10 粒子和程序将循环访问 1000 倍。很快就会看到，为每个粒子所解决的 PSO 问题表示可能的解决方案。PSO 是迭代的一种技术，在大多数情况下不可能知道何时已找到最佳的解决方案。因此，PSO 算法通常必须具有某些限制进行的迭代次数。

下一步的行中图 1指示每个蜂群在 10 个粒子是否已初始化的随机位置。粒子的位置表示优化问题，以解决可能的解决方案。最好的随机生成的初始位置是 0 = 26.53 x 和 x 1 =-6.09 相当于 3 + 26.53 的适用性 （解决方案质量的度量值） ^2 + (-6.09) ^2 = 744.12。PSO 算法然后进入主处理循环每个粒子的位置上循环的每一项传递的更新位置。更新过程是 PSO 的核心，我将在本文后面部分详细介绍它。1000 次迭代后, PSO 算法实际上未找到合适的最佳解决方案的 0 = 0.0 x 和 x 1 = 0.0，但是让我强调，在大多数情况下，您不会知道 PSO 程序是否已找到最佳的解决方案。

在本文中，我将详细介绍 PSO 算法，并引导您逐行显示在运行该程序图 1。我编码演示计划在 C# 中，但您应该能够轻松地适应成其他语言如 Visual Basic 在此处显示的代码。NET 或 Python。本文中介绍的程序的完整源代码位于code.msdn.microsoft.com/mag201108PSO。本文假定您具有与现代过程语言的中间编码技能，但并不假定您了解 PSO 或相关的 AI 技术。

粒子

当使用 PSO，在调查数字优化问题的可能解决方案都用粒子的位置。此外，每个粒子都有当前的速度，它表示一个量值和向新的方向，大概是更好的解决方案/位置。粒子还提供了一种质量的当前位置、 粒子的已知最佳位置 （即原来位置的已知最佳质量） 和质量的已知最佳位置。我编码粒子类，如中所示图 2。

图 2粒子定义

public class Particle
{
  public double[] position;
  public double fitness;
  public double[] velocity;

  public double[] bestPosition;
  public double bestFitness;

  public Particle(double[] position, double fitness,
   double[] velocity, double[] bestPosition, double bestFitness)
  {
    this.position = new double[position.Length];
    position.CopyTo(this.position, 0);
    this.fitness = fitness;
    this.velocity = new double[velocity.Length];
    velocity.CopyTo(this.velocity, 0);
    this.bestPosition = new double[bestPosition.Length];
    bestPosition.CopyTo(this.bestPosition, 0);
    this.bestFitness = bestFitness;
  }

  public override string ToString()
  {
    string s = "";
    s += "==========================\n";
    s += "Position: ";
    for (int i = 0; i < this.position.Length; ++i)
      s += this.position[i].ToString("F2") + " ";
    s += "\n";
    s += "Fitness = " + this.fitness.ToString("F4") + "\n";
    s += "Velocity: ";
    for (int i = 0; i < this.velocity.Length; ++i)
      s += this.velocity[i].ToString("F2") + " ";
    s += "\n";
    s += "Best Position: ";
    for (int i = 0; i < this.bestPosition.Length; ++i)
      s += this.bestPosition[i].ToString("F2") + " ";
    s += "\n";
    s += "Best Fitness = " + this.bestFitness.ToString("F4") + "\n";
    s += "==========================\n";
    return s;
  }
} // class Particle

粒子类有五个公共数据成员： 位置、 适用性、 速度、 bestPosition 和 bestFitness。 为简便起见使用 PSO，我愿意使用公共范围内的字段，但您可能希望使用私有字段，以及获取并而设置的属性。 名为位置的域是一个 double 类型的数组，并在调查的优化问题表示可行的解决方案。 虽然 PSO 可以用于解决非数字的问题，通常是最适合用于解决数字的问题。 一种好的解决方案由位置在字段的适用性。 最小化问题，这是最常见的通过 PSO 来解决的问题，较小的适用性字段值要优于较大的值。 最大化问题，是适用性的更好较大的值。

字段速度为 double 类型的数组，表示更新粒子的当前位置/解决方案所需的信息。 我将稍后解释详细的粒子速度。 粒子类型中的第四个和第五个字段是 bestPosition 和 bestFitness。 这些字段保存最佳位置/解决方案发现粒子对象和相关联的适用性的最佳位置。

粒子类有单个接受对应于每个粒子的五个数据字段的五个参数的构造函数。 构造函数只需将每个参数值复制到其对应的数据字段中。 所有五个粒子字段都具有公共范围内，因为我可能遗漏了构造函数，然后在 PSO 代码中，只需使用字段赋值语句，但我认为该构造函数将导致更整洁的代码。

粒子类定义中包含一个回显五个数据字段的值的 ToString 方法。 为使用构造函数，因为我声明位置、 适用性、 速度，bestPosition 和 bestFitness 字段公共范围内的，我实际上不需要的 ToString 方法来查看某个粒子对象的值，但包括它简化了查看的字段以及它的 WriteLine 式调试在开发过程中非常有用。 中的 ToString 方法以使其更方便地重构非 Microsoft 我的代码使用字符串串联，而不是更有效的 StringBuilder 类。NET 框架的语言如果您愿意的话。

PSO 算法

虽然 thePSO 算法的核心是相当简单，但您需要彻底了解它，以修改以满足自己的需要这篇文章中的代码。 PSO 是一个循环往复的过程。 PSO 主处理循环中的每个迭代，每个粒子的当前速度是第一次更新基于粒子的当前速度、 粒子的本地信息和全局蜂群的信息。 然后，使用新的粒子的速度更新每个粒子的位置。 数学公式中的两个更新公式的条款如下：

v(t+1) = (w * v(t)) + (c1 * r1 * (p(t) – x(t)) + (c2 * r2 * (g(t) – x(t))

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

请与我 ； 位置更新过程会比这些等式建议实际上更简单。 第一个等式更新粒子的速度。 术语v(t + 1) 表示在时间 t + 1 的速度。 请注意 v 是以粗体显示，指示该速度是向量的值，如具有多个组件 {1.55，-0.33}，而不是由单个标量值。 新的速度取决于这三个术语。 第一项是 w *v(t)。 W 型称为惯性重量，只需像 0.73 （详细介绍这很快） ； 常量 v(t) 是次 t 的当前速度。 第二项是 c1 * r1 * (p(t) – x(t)）。 C1 因素就是一个常数，调用的认知 （或个人或本地） 的粗细。 R1 因素就是在范围内随机变量 [0，1)，即大于或等于 0 且严格小于 1。 P(t) 矢量值是到目前为止找到的粒子的最佳位置。 X(t) 矢量值是粒子的当前位置。 速度更新等式中的第三个术语是 (c2 * r2 * (g(t) – x(t)）。 C2 因子是一个常量，称为社会 — 或全局 — 重量。 R2 因素就是一个随机变量在范围 [0, 1) 中。 G (t) 矢量值是已知最好位置找到的任何粒子蜂群中到目前为止。 一次新的速度、 v(t+1)，已经确定，它用于计算新的粒子位置x(t + 1)。

具体的示例将使清除在更新过程。 假设您正在尝试进行减至最少 3 + x 0 ^2 + x ^2 本文简介一节中所述。 图 3 中的绘制该函数。 在包含多维数据集的图 3表示 x0 和 x1 值和垂直轴表示函数的值。 注意： 绘图图面已最小化，f = 3 时 0 = 0 和 1 = 0。

图 3绘图的 f = 3 + x 0 ^2 + x ^2

假设粒子的当前的位置，x(t) 是 {1 x 0} = {3.0、 4.0} 和粒子的当前速度， v(t) 是 {-1.0、-1.5}。 我们还假定该常量 w = 0.7，常量 c1 = 1.4 常量 c2 = 1.4 和随机数字 r1 和 r2 又 0.5 和 0.6 分别。 最后，假设粒子的已知最佳位置将是p(t) = {2.5、 3.6}，通过任何粒子蜂群中的全局已知最佳位置是 g(t) = {2.3、 3.4}。 然后新的速度和位置值是：

v(t + 1) = (0.7 * {-1.0、-1.5}） +

         (1.4 * 0.5 * {2.5, 3.6} - {3.0, 4.0}) +

         (1.4 * 0.6 * {2.3, 3.4} – {3.0, 4.0})

       = {-0.70, -1.05} + {-0.35, -0.28} + {-0.59, -0.50}

       = {-1.64, -1.83}

x(t + 1) = {3.0、 4.0} + {-1.64、-1.83}

       = {1.36, 2.17}

撤回最佳解决方案是 {1 x 0} = (0.0、 0.0}。 观察更新过程改进了从旧位置/解决方案 （3.0、 4.0} 到 {1.36、 2.17}。 如果一位 mull 对更新过程，您将看到新的速度是旧速度 （时间线） 加上系数取决于粒子的已知最佳位置，再加上取决于从所有粒子蜂群中的已知最佳位置的另一个因素。 因此，往往会发展出更多优势，根据粒子的已知最佳位置和所有粒子的已知最佳位置粒子的新位置。 在图表中的图 4的粒子之一移动显示演示 PSO 前八个迭代过程中运行。 从粒子 0 开始的 x = 100.0，1 = 80.4 x 并将移向 0 = 0，1 = 0xx 的最佳解决方案。 螺旋运动是典型的 PSO。

图 4粒子运动实现最佳解决方案

实施 PSO 算法

图 5 显示生成该程序运行中所示的 PSO 程序的总体结构 图 1。 我用来创建一个 C# 控制台应用程序项目名为 ParticleSwarmOptimization 的 Visual Studio。 PSO 代码是非常基本的因此任何版本的。NET 框架 （1.1 至 4） 可能会很好。 删除所有 Visual Studio 生成使用除外的核心系统命名空间的引用的语句。 我声明类范围类型对象的随机生成认知和社会的随机编号，在上一节中所述。 我还用 Random 对象来生成随机初始速度，并为每个粒子对象的位置。 在我换我的所有代码都行在一个高层次的 Main 方法的 try 语句可以捕获任何异常。

图 5PSO 程序结构

using System;
namespace ParticleSwarmOptimization
{
  class Program
  {
    static Random ran = null;
    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin PSO demo\n");
        ran = new Random(0);

        int numberParticles = 10;
        int numberIterations = 1000;
        int iteration = 0;
        int Dim = 2; // dimensions
        double minX = -100.0;
        double maxX = 100.0;

        Particle[] swarm = new Particle[numberParticles];
        double[] bestGlobalPosition = new double[Dim];
        double bestGlobalFitness = double.MaxValue; 

        double minV = -1.0 * maxX;
        double maxV = maxX;

        // Initialize all Particle objects

        double w = 0.729; // inertia weight
        double c1 = 1.49445; // cognitive weight
        double c2 = 1.49445; // social weight
        double r1, r2; // randomizations

        // Main processing loop

        // Display results
        Console.WriteLine("\nEnd PSO demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal error: " + ex.Message);
      }
    } // Main()

    static double ObjectiveFunction(double[] x)
    {
      return 3.0 + (x[0] * x[0]) + (x[1] * x[1]);
    }

  } // class Program

  public class Particle
  {
    // Definition here 
  }

} // ns

初始化完成 Random 对象任意种子值为 0 之后, 我一些关键 PSO 变量进行初始化：

int numberParticles = 10;
int numberIterations = 1000;
int iteration = 0;
int Dim = 2;
double minX = -100.0;
double maxX = 100.0;

我使用 10 个粒子对象。 作为经验法则，更多的粒子对象优于更少，但多极大地降低程序性能。 主处理循环迭代次数设置为 1000。 您可能需要使用的迭代数将取决于您正在尝试进行优化的问题的复杂程度和您的主机的处理能力。 通常情况下，PSO 程序使用 1000 到 100000 之间的值。 名为迭代变量是要跟踪的主循环迭代次数的计数器。 Dim 变量保存解决方案/位置的 x 值的个数。 因为我的示例问题需要查找 x0 和 x1 减至最少 3 + x 0 值 ^2 + x ^2，设置 (in dim) 为 2。 如前所述，在大多数 PSO 情况下您需要限制对某些依赖问题的区域组成的位置/解决方案向量的 x 值。 没有一些限制，要有效地搜索从双精度。MinValue 倍。MaxValue。 这里我随意限制 x0 和 x1 [100.0、 +100.0]。

接下来，我准备粒子蜂群实例化：

Particle[] swarm = new Particle[numberParticles];
double[] bestGlobalPosition = new double[Dim];
double bestGlobalFitness = double.MaxValue; 
double minV = -1.0 * maxX;
double maxV = maxX;

创建数组的对象名为 swarm 的粒子。 此外设置数组来存放由任何粒子的全球已知最佳位置由g(t) 算法中 — 和该位置数组的相应的适用性。 设置新速度的最大和最小值的约束。 这里的想法是由于新速度决定粒子的新位置，所以我不希望任何速度组件以非常大的量。

要初始化蜂群的代码如下所示：

for (int i = 0; i < swarm.Length; ++i)
{ 
  double[] randomPosition = new double[Dim];
  for (int j = 0; j < randomPosition.Length; ++j) {
    double lo = minX;
    double hi = maxX;
    randomPosition[j] = (hi - lo) * ran.NextDouble() + lo; 
  }
...

我循环命名蜂群数组中的每个粒子对象。 我声明数组的大小 (in dim) 以保持当前的粒子的随机位置。 然后为每个 x 值的位置生成 minX （100.0） 和 maxX (+100.0) 之间的随机值。 在很多真实 PSO 问题，每个 x 值的范围将会有所不同，因此您必须添加代码以单独处理每个位置数组中的 x 值。

现在我继续初始化过程：

double fitness = ObjectiveFunction(randomPosition);
double[] randomVelocity = new double[Dim];
for (int j = 0; j < randomVelocity.Length; ++j) {
  double lo = -1.0 * Math.Abs(maxX - minX);
  double hi = Math.Abs(maxX - minX);
  randomVelocity[j] = (hi - lo) * ran.NextDouble() + lo;
}
swarm[i] = new Particle(randomPosition, fitness, randomVelocity,
  randomPosition, fitness);
...

首先，我来将该数组传递给方法 ObjectiveFunction 计算当前的随机位置数组的质量。 如果您回头图 5，您将看到的 ObjectiveFunction 方法只计算值的函数，我要最小化，即 3 + x 0 ^2 + x ^2。 接下来我将计算当前粒子对象的随机速度。 我有一个随机位置、 随机位置和随机速度的适用性之后，我将这些值传递到粒子构造函数。 记得的第四个和第五个参数的粒子的已知最佳位置和其相关联的适用性，因此时初始化粒子随机初始位置和适用性的已知最佳值。

蜂群初始化代码完成有：

...
if (swarm[i].fitness < bestGlobalFitness) {
    bestGlobalFitness = swarm[i].fitness;
    swarm[i].position.CopyTo(bestGlobalPosition, 0);
  }
} // End initialization loop

检查以查看当前粒子的适用性是否最佳 （最小化问题的情况下最小） 到目前为止找到的适用性。 如果是这样，更新阵列 bestGlobalPosition 和相应的变量 bestGlobalFitness。

接下来，我准备进入主 PSO 处理循环：

double w = 0.729; // inertia weight
double c1 = 1.49445; // cognitive weight
double c2 = 1.49445; // social weight
double r1, r2; // randomizers

W，惯性粗细值设置为 0.729。 此值被建议的调查对一组准则最小化问题的各种 PSO 参数值的影响研究论文。 而不是 w 的 w 单个的常量值，另一种方法是 w 的不同值。 例如，如果您 PSO 算法是设置为迭代 10000 次，可以最初设置 w 到 0.90，逐渐减少 0.40 通过减少 w w 0.10 每 2000 次迭代后。 动态 w 的思想是早期算法中您想要浏览位置，较大的更改，但希望以后更小的粒子运动。 我设置 c1 和 c2、 认知和社会重量，值为 1.49445。 同样，此值被推荐一次调查研究。 如果您设置的值大于 c2 的值的 c1，比蜂群的全球已知最佳位置，反之亦然粒子的已知最佳位置上放置更多的重量。 随机变量 r1 和 r2 随机组件添加到 PSO 算法，并帮助防止算法停留在非最佳的本地最小值或最大解决方案。

接下来，我开始主 PSO 处理循环：

for (int i = 0; i < swarm.Length; ++i) 
{
  Particle currP= swarm[i];
            
  for (int j = 0; j < currP.velocity.Length; ++j) 
  {
    r1 = ran.NextDouble();
    r2 = ran.NextDouble();

    newVelocity[j] = (w * currP.velocity[j]) +
      (c1 * r1* (currP.bestPosition[j] - currP.position[j])) +
      (c2 * r2 * (bestGlobalPosition[j] - currP.position[j]));
    ...

我循环使用 i 蜂群数组中的每个粒子对象为索引变量。 创建名为 currP，以简化代码，当前粒子对象的引用，但我无法使用蜂群 [i] 直接。 在上一节中所述，第一步是更新每个粒子的速度向量。 对于当前的粒子对象，我遍历每个对象的速度数组中的值，生成随机变量 r1 和 r2，，然后更新速度的每个组件，如前一节中所述。

我计算新的速度组件当前粒子对象后，检查该组件速度组件的最小值和最大值之间：

if (newVelocity[j] < minV)
    newVelocity[j] = minV;
  else if (newVelocity[j] > maxV)
    newVelocity[j] = maxV;
} // each j
newVelocity.CopyTo(currP.velocity, 0);
...

如果该组件是超出了范围，我将它在回到范围之内。 这里的想法是我不想极值速度组件由于极值可能导致我以旋转超出界限的新位置。 已计算速度的所有组件后，不更新当前粒子对象的速度阵列使用非常方便。NET CopyTo 方法。

一旦确定当前粒子的速度，我可以使用新的速度来计算并更新当前粒子的位置：

for (int j = 0; j < currP.position.Length; ++j)
{
  newPosition[j] = currP.position[j] + newVelocity[j];
  if (newPosition[j] < minX)
    newPosition[j] = minX;
  else if (newPosition[j] > maxX)
    newPosition[j] = maxX;
}
newPosition.CopyTo(currP.position, 0);
...

再次执行范围检查，这一次每个当前粒子的新位置组件上。 在某种意义上，这是一个冗余检查，因为我已经已经约束值的每个速度组件中，但在我看来额外检查属于保修范围此处。

现在，我已经在当前粒子对象的新位置，我计算新的适用性值，并更新该对象的适用性字段：

newFitness = ObjectiveFunction(newPosition);
    currP.fitness = newFitness;

    if (newFitness < currP.bestFitness) {
      newPosition.CopyTo(currP.bestPosition, 0);
      currP.bestFitness = newFitness;
    }
    if (newFitness < bestGlobalFitness) {
      newPosition.CopyTo(bestGlobalPosition, 0);
      bestGlobalFitness = newFitness;
    }

  } // each Particle
} // main PSO loop
...

更新后的当前粒子，检查以查看新的位置是否已知最佳位置的粒子。 我还检查以查看新的位置是否最佳的全局蜂群位置。 请注意逻辑上，可以有一个新的全球最佳位置仅当没有一个最佳的本地位置，因此我可以嵌套全球最佳检查内部检查本地得天独厚的优势。

在此时完成我主 PSO 算法循环，并且我可以显示我的结果：

Console.WriteLine("\nProcessing complete");
    Console.Write("Final best fitness = ");
    Console.WriteLine(bestGlobalFitness.ToString("F4"));
    Console.WriteLine("Best position/solution:");
    for (int i = 0; i < bestGlobalPosition.Length; ++i){
      Console.Write("x" + i + " = " );
      Console.WriteLine(bestGlobalPosition[i].ToString("F4") + " ");
    }
    Console.WriteLine("");
    Console.WriteLine("\nEnd PSO demonstration\n");
  }
  catch (Exception ex)
  {
    Console.WriteLine("Fatal error: " + ex.Message);
  }
} // Main()

扩展和修改

现在，您已经了解如何编写基本 PSO，让我们讨论一下如何扩展和修改我的代码。 我解决的示例问题是人为的意义上则无需使用 PSO 查找近似的解决方案，因为能完全解决问题。 PSO 是很有用的位置是在调查数字问题极难或不可能解决使用标准技术。 请考虑以下问题。 要预测的分数的 (美国) 的足球游戏之间团队 A 和 b。 历史数据包含的 A 以前的结果和对其他团队的 B。 数学模型 X 如果小组赢得游戏，团队的分级的某些固定值 （假设 16 磅） 就会加上另一个值的方式取决于团队的分级 （例如 0.04 时间的差异，如果工作组 X 分级小于获胜的） 之间的差异团队的历史等级。 此外，作为球队; 上的差异的某些功能模型预测的团队的胜利的边距 例如，如果团队 X 等级为 1,720，团队 Y 的评级 1,620 模型预测胜利的边距 3.5 点的 x。 简单地说，您有大量的数据，并需要确定几个数值 （如 16 和 0.04，共需） 最小化您的预测错误的。 此数据驱动的参数估计是问题的右上 PSO 的走廊的类型。

PSO 是基于自然系统的行为的几种 AI 技术之一。 可能是最接近 PSO 算法的技术是遗传算法 (气体)。 这两种技术非常适合于数字难以解决的问题。 天然气被广泛研究数十年。 天然气 Pso 的优点是 PSO 算法实现天然气比简单得多。 它并不清楚这次 Pso 是否比天然气更多或更少有效或大致等于它们。

可以采用多种方式修改的 PSO 了此处提供的版本。 若要使用多个 sub-swarms 粒子，而不是一个全局蜂群一个特别感兴趣的修改。 此类的设计，每个粒子属于 sub-swarm 和新粒子的速度可能取决于四个条款，而不是三个： 旧的速度、 粒子的已知最佳位置、 知名 sub-swarm，在所有粒子的位置和任何粒子的已知最佳位置。 这种 sub-swarm 设计思想是减少 PSO 算法停留在非最佳解决方案的机会。 我的知识的最佳此类设计有不尚未被彻底调查。

Dr. James McCaffrey 适用于伏信息科学 Inc.，他管理着软件工程师使用 Microsoft 雷蒙德，Wash.，在校园内的技术培训。 他参与过多项 Microsoft 产品的研发工作，包括 Internet Explorer 和 MSN Search。 Dr. McCaffrey 是作者"。NET 测试自动化食谱"（Apress，2006年），并可以通过jammc@microsoft.com。

衷心感谢以下 Microsoft 技术专家对本文的审阅：Paul Koch、Dan Liebling、Anne Loomis Thompson 和 Shane Williams