测试运行

进化优化算法

James McCaffrey

下载代码示例

进化优化算法是一种仿照生物进化行为的元启发式算法实现。这些算法可用于查找艰深或无解的求最小值问题的近似解。您对进化优化算法感兴趣可能有三个原因。第一，了解如何编写这些算法的代码可能会为开发人员、管理人员和测试人员提供实用的技能集补充。第二，使用的某些技术（如竞赛选择）可以在其他算法和编码应用场景中重复使用。第三，很多工程师只是由于自身的原因发现这些算法非常有趣。

进化优化算法实质上是一种遗传算法，即，虚拟染色体由实值组成，而不是采用某种位表示形式。要了解我讲述的内容，最好是看一下图 1 和图 2。

图 1 Schwefel 函数

图 2 进化优化演示

图 1 中的图形显示了 Schwefel 函数，这是一个标准基准测试求最小值问题。Schwefel 函数定义如下：

f(x,y) = (-x * sin(sqrt(abs(x)))) + (-y * sin(sqrt(abs(y))))

当 x = y = 420.9687 时，函数具有最小值 -837.9658。 在图 1 中，此最小值位于图表的最左侧的角上。 该函数经过故意设计以使优化算法很难解决该问题，因为它具有很多虚假的局部最低值。

图 2 中的屏幕快照显示了来自 C# 控制台应用程序的输出。 在显示一些信息性消息后，该程序设置 8 个参数，然后使用进化算法查找最优解。 在此示例中，该算法找到一个最佳解 (420.9688, 420.9687)，它非常接近于最优解 (420.9687, 420.9687)，但并不完全等于最优解。

进化优化算法将解作为个体中的染色体进行模拟。 在高级伪代码中，图 2 中实现的算法是：

initialize a population of random solutions
determine best solution in population
loop
  select two parents from population
  make two children from the parents
  place children into population
  make and place an immigrant into population
  check if a new best solution exists
end loop
return best solution found

在下面几节中，我将介绍生成图 2 中的屏幕快照的所有代码。 您可以从 archive.msdn.microsoft.com/mag201206TestRun 中访问该代码。 本文假定您具有中级或高级编程技能，并至少对遗传算法有一个基本的了解。 我使用 C# 编写演示程序代码，但您应该能够轻松将该代码重构为其他语言（如 Visual Basic .NET 或 IronPython）。

程序结构

图 3 中显示了总体程序结构。 我使用 Visual Studio 2010 创建一个名为 EvolutionaryOptimization 的新 C# 控制台应用程序项目。 在解决方案资源管理器窗口中，我将 Program.cs 重命名为 EvolutionaryOptimizationProgram.cs，后者自动重命名 Program 类。 我还删除了所有不需要的模板生成的 using 语句。

图 3 EvolutionaryOptimization 程序的整体结构

using System;
namespace EvolutionaryOptimization
{
  class EvolutionaryOptimizationProgram
  {
    static void Main(string[] args)
    {
      try
      {
        int popSize = 100;
        int numGenes = 2;
        double minGene = -500.0; double maxGene = 500.0;
        double mutateRate = 1.0 / numGenes;
        double precision = 0.0001;
        double tau = 0.40;
        int maxGeneration = 8000;
        Evolver ev = new Evolver(popSize, numGenes, 
          minGene, maxGene, mutateRate,
          precision, tau, maxGeneration);
        double[] best = ev.Evolve();
        Console.WriteLine("\nBest solution found:");
        for (int i = 0; i < best.Length; ++i)
          Console.Write(best[i].ToString("F4") + " ");
        double fitness = Problem.Fitness(best);
        Console.WriteLine("\nFitness of best solution = " 
          + fitness.ToString("F4"));
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    }
  }
  public class Evolver
  {
    // Member fields
    public Evolver(int popSize, int numGenes, 
      double minGene, double maxGene,
      double mutateRate, double precision, 
      double tau, int maxGeneration) { ...
}
    public double[] Evolve() { ...
}
    private Individual[] Select(int n) { ...
}
    private void ShuffleIndexes() { ...
}
    private Individual[] Reproduce(Individual parent1, 
      Individual parent2) { ...
}
    private void Accept(Individual child1, 
      Individual child2) { ...
}
    private void Immigrate() { ...
}
  }
  public class Individual : IComparable<Individual>
  {
    // Member fields
    public Individual(int numGenes, 
      double minGene, double maxGene,
      double mutateRate, double precision) { ...
}
    public void Mutate() { ...
}
    public int CompareTo(Individual other) { ...
}
  }
  public class Problem
  {
    public static double Fitness(double[] chromosome) { ...
}
  }
} // NS

除了主程序类以外，EvolutionaryOptimization 演示还具有三个程序定义的类。 Evolver 类包含大部分的算法逻辑。 Individual 类模拟求最小值问题的可能解。 Problem 类定义了要求最小值的函数，此处为 Schwefel 函数。 另一种设计结构是将 Individual 类放在 Evolver 类内。

Individual 类

Individual 类定义开始：

public class Individual : IComparable<Individual>
{
  public double[] chromosome;
  public double fitness;
  private int numGenes;
  private double minGene;
  private double maxGene;
  private double mutateRate;
  private double precision;
  static Random rnd = new Random(0);
...

该类从 IComparable 接口继承，以便按适合度对 Individual 对象数组自动进行排序。 该类具有 8 个数据成员。 chromosome（染色体）数组表示目标问题的可能解。 请注意，chromosome 是一个双精度型数组，而不是遗传算法通常使用的某种位表示形式的数组。 进化优化算法有时也称为实值遗传算法。

fitness（适合度）字段是衡量 chromosome 解好坏程度的指标。 对于求最小值问题，较小的适合度比较大的值好。 为简单起见，将使用公共作用域声明 chromosome 和 fitness，以使其对 Evolver 类中的逻辑可见。 基因是 chromosome 数组中的一个值，numGenes 字段保存可能解中的实值数。 对于 Schwefel 函数，该值将设置为 2。 对于很多数值优化问题，可以指定每个基因的最小和最大值并将这些值存储在 minGene 和 maxGene 中。 如果不知道这些值，则可以将 minGene 和 maxGene 设置为 double.MinValue 和 double.MaxValue。 在介绍使用 mutateRate 和 precision 字段的代码时，我将说明这些字段。

Individual 类定义将继续定义类构造函数：

public Individual(int numGenes, double minGene, double maxGene,
  double mutateRate, double precision)
{
  this.
numGenes = numGenes;
  this.minGene = minGene;
  this.maxGene = maxGene;
  this.mutateRate = mutateRate;
  this.precision = precision;
  this.chromosome = new double[numGenes];
  for (int i = 0; i < this.chromosome.Length; ++i)
    this.chromosome[i] = (maxGene - minGene) 
    * rnd.NextDouble() + minGene;
  this.fitness = Problem.Fitness(chromosome);
}

该构造函数为 chromosome 数组分配内存，并为每个基因单元分配范围 (minGene, maxGene) 内的随机值。 请注意，fitness 字段值是通过调用外部定义的 Fitness 方法设置的。 或者，您也可以通过 Delegate 将对 Fitness 方法的引用传递到构造函数。 Mutate 方法定义如下：

public void Mutate()
{
  double hi = precision * maxGene;
  double lo = -hi;
  for (int i = 0; i < chromosome.Length; ++i) {
    if (rnd.NextDouble() < mutateRate)
      chromosome[i] += (hi - lo) * rnd.NextDouble() + lo;
  }
}

调换操作遍历 chromosome 数组，以将随机选择的基因更改为 (lo, hi) 范围内的随机值。 要分配的值范围是由 precision 和 maxGene 成员值确定的。 在图 2 的示例中，precision 设置为 0.0001，maxGene 设置为 500。 基因调换的最高可能值为 0.0001 * 500 = 0.05，这意味着，如果调换基因，则它的新值等于旧值加上或减去 -0.05 和 +0.05 之间的随机值。 请注意，precision 值对应于解中的小数位数；这是 precision 值使用的合理启发式算法。 调换率值控制将修改 chromosome 中的基因数。 mutateRate 字段值的一种启发式算法是使用 1.0 / numGenes，以便在每次调用 Mutate 时平均改变 chromosome 中的一个基因。

Individual 类定义以 CompareTo 方法结束：

...
public int CompareTo(Individual other)
  {
    if (this.fitness < other.fitness) return -1;
    else if (this.fitness > other.fitness) return 1;
    else return 0;
  }
}

CompareTo 方法为 Individual 对象定义了默认排序顺序，此处为从最小适合度（最佳）到最大适合度。

Problem 类

Problem 类封装进化算法的目标问题：

public class Problem
{
  public static double Fitness(double[] chromosome)
  {
    double result = 0.0;
    for (int i = 0; i < chromosome.Length; ++i)
      result += (-1.0 * chromosome[i]) *
        Math.Sin(Math.Sqrt(Math.Abs(chromosome[i])));
    return result;
  }
}

由于 chromosome 数组表示一个可能解，因此，它将作为输入参数传递到 Fitness 方法。 对于任意求最小值问题，要求最小值的目标函数通常称为成本函数。 但在进化和遗传算法上下文中，该函数通常称为适合度函数。 请注意，此术语有点别扭，因为较低的适合度值比较高的值好。 在此示例中，适合度函数是完全独立的。 在很多优化问题中，适合度函数需要额外的输入参数，如数据矩阵或外部数据文件引用。

Evolver 类

Evolver 类定义开始：

public class Evolver
{
  private int popSize;
  private Individual[] population;
  private int numGenes;
  private double minGene;
  private double maxGene;
  private double mutateRate;
  private double precision;
  private double tau;
  private int[] indexes;
  private int maxGeneration;
  private static Random rnd = null;
...

popSize 成员保存 population 中的个体数。 较大的 popSize 值往往以牺牲速度为代价来提高算法的准确性。 一般来说，进化算法比普通遗传算法快得多，因为进化算法处理的是实值，而不会产生转换和处理位表示形式的开销。 Evolver 类的核心是一个名为 population 的 Individual 对象数组。 正如您很快会看到的一样，Selection 方法使用 tau 和 indexes 成员。

Evolver 类定义继续定义图 4 中显示的构造函数。

图 4 Evolver 类构造函数

public Evolver(int popSize, int numGenes, double minGene, double maxGene,
  double mutateRate, double precision, double tau, int maxGeneration)
{
  this.popSize = popSize;
  this.population = new Individual[popSize];
  for (int i = 0; i < population.Length; ++i)
    population[i] = new Individual(numGenes, minGene, maxGene,
      mutateRate, precision);
  this.
numGenes = numGenes;
  this.minGene = minGene;
  this.maxGene = maxGene;
  this.mutateRate = mutateRate;
  this.precision = precision;
  this.tau = tau;
  this.indexes = new int[popSize];
  for (int i = 0; i < indexes.Length; ++i)
    this.indexes[i] = i;
  this.maxGeneration = maxGeneration;
  rnd = new Random(0);
}

该构造函数为 population 数组分配内存，然后使用 Individual 构造函数在该数组中填充具有随机基因值的个体。 Select 方法使用名为 indexes 的数组，此方法挑选两个父代。 我稍后将介绍 indexes，但要注意，构造函数为每个个体分配一个单元，并按顺序分配 0 到 popSize-1 之间的整数。

图 5 中列出的 Evolve 方法非常短。

图 5 Evolve 方法

public double[] Evolve()
{
  double bestFitness = this.population[0].fitness;
  double[] bestChomosome = new double[numGenes];
  population[0].chromosome.CopyTo(bestChomosome, 0);
  int gen = 0;
  while (gen < maxGeneration)  {
    Individual[] parents = Select(2);
    Individual[] children = Reproduce(parents[0], parents[1]);
    Accept(children[0], children[1]);
    Immigrate();
    for (int i = popSize - 3; i < popSize; ++i)  {
      if (population[i].fitness < bestFitness)  {
        bestFitness = population[i].fitness;
        population[i].chromosome.CopyTo(bestChomosome, 0);
      }
    }
    ++gen;
  }
  return bestChomosome;
}

Evolve 方法将找到的最佳解作为双精度类型的数组返回。 作为替代方法，您可以返回一个 Individual 对象，chromosome 将保存找到的最佳解。 Evolve 方法首先将最佳适合度和最佳染色体初始化为 population 中的第一个个体。 该方法将 gen（代）作为循环计数器以精确执行 maxGenerations 次迭代。 有几种替代方法，其中之一是在执行若干次迭代后没有得到改善时停止。 Select 方法从 population 中返回两个较好的个体（但不一定是最好的）。 这两个父代将传递到 Reproduce，后者创建并返回两个子代。 Accept 方法将两个子代放在 population 中以替换两个现有的个体。 Immigrate 方法生成新的随机个体并将其放到 population 中。 然后，扫描新 population 以查看 population 中的三个新个体是否为新的最佳解。

Select 方法定义如下：

private Individual[] Select(int n)
{
  int tournSize = (int)(tau * popSize);
  if (tournSize < n) tournSize = n;
  Individual[] candidates = new Individual[tournSize];
  ShuffleIndexes();
  for (int i = 0; i < tournSize; ++i)
    candidates[i] = population[indexes[i]];
  Array.Sort(candidates);
  Individual[] results = new Individual[n];
  for (int i = 0; i < n; ++i)
    results[i] = candidates[i];
  return results;
}

该方法接受要选择的较好个体数，并在 Individual 类型的数组中返回这些个体。 为了最大限度减少代码数量，我省略了正常错误检查，例如，验证请求的个体数是否少于 population 大小。 Select 方法使用称为“竞赛选择”的技术。 将生成随机候选个体的子集，并返回其中最好的 n 个个体。 候选个体数将计入 tournSize 变量中，它是总 population 大小的一部分 (tau)。 tau 值越大，选择两个最好的个体的概率就会越大。

回想一下，Evolver 类具有一个名为 indexes 且值为 0..popSize-1 的成员数组。 ShuffleIndexes 帮助程序方法按随机顺序重新排列 indexes 数组中的值。 这些随机索引中的前 n 个索引用于从 population 中挑选候选个体。 然后，Array.Sort 方法按从最小（最好）到最大的顺序对候选个体进行排序。 将返回排序的前 n 个候选个体。 可以使用许多不同的进化选择算法。 与大多数其他技术相比，竞赛选择的优势是，可以修改 tau 参数以优化选择压力。

ShuffleIndexes 帮助程序方法使用标准 Fisher-Yates 混排算法：

private void ShuffleIndexes()
{
  for (int i = 0; i < this.indexes.Length; ++i) {
    int r = rnd.Next(i, indexes.Length);
    int tmp = indexes[r];
    indexes[r] = indexes[i];
    indexes[i] = tmp;
  }
}

图 6 列出了 Reproduce 方法。 该方法首先生成一个随机交叉点。 编制索引有一点麻烦，而 child1 是通过 parent1 的左侧部分和 parent2 的右侧部分创建的。 child2 是通过 parent2 的左侧部分和 parent1 的右侧部分创建的。 图 7 说明了该想法，其中包含两个具有 5 个基因的父代，交叉点为 2。 一个常见的设计替代方法是使用多个交叉点。 在创建 Individual 子代对象后，将调换它们的位置并计算新的适合度。

图 6 Reproduce 方法

private Individual[] Reproduce(Individual parent1, Individual parent2)
{
  int cross = rnd.Next(0, numGenes - 1);
  Individual child1 = new Individual(numGenes, minGene, maxGene,
    mutateRate, precision);
  Individual child2 = new Individual(numGenes, minGene, maxGene,
     mutateRate, precision);
  for (int i = 0; i <= cross; ++i)
    child1.chromosome[i] = parent1.chromosome[i];
  for (int i = cross + 1; i < numGenes; ++i)
    child2.chromosome[i] = parent1.chromosome[i];
  for (int i = 0; i <= cross; ++i)
    child2.chromosome[i] = parent2.chromosome[i];
  for (int i = cross + 1; i < numGenes; ++i)
    child1.chromosome[i] = parent2.chromosome[i];
  child1.Mutate(); child2.Mutate();
  child1.fitness = Problem.Fitness(child1.chromosome);
  child2.fitness = Problem.Fitness(child2.chromosome);
  Individual[] result = new Individual[2];
  result[0] = child1; result[1] = child2;
  return result;
}

图 7 交叉机制

Accept 方法将 Reproduce 创建的两个子代个体放入 population 中：

private void Accept(Individual child1, Individual child2)
{
  Array.Sort(this.population);
  population[popSize - 1] = child1;
  population[popSize - 2] = child2;
}

population 数组是按适合度排序的，这会将两个最差的个体放在数组的最后两个单元中，然后将它们替换为子代。 可以使用很多替代方法来选择两个要替换的个体。 一种可能性是使用一种称为“轮盘赌选择”的技术，从概率上选择两个要替换的个体，将替换具有较大概率的最差个体。

Immigrate 方法生成一个新的随机个体并将其放在 population 中，正好位于刚创建的两个子代的正上方（迁入有助于防止进化算法卡在局部最小解中；设计替代方法包括创建多个迁入个体，并将其放在 population 中的随机位置）：

private void Immigrate()
{
  Individual immigrant =
    new Individual(numGenes, minGene, maxGene, mutateRate, precision);
  population[popSize - 3] = immigrant;
}

实验的起点

在本文中，使用了进化优化来估计数学方程的最小值。 虽然可以按此方式使用进化优化算法，但它们更多的时候用于在没有有效确定性算法的较大优化问题中查找一组数值参数的值。 例如，在使用神经网络对现有数据进行分类以预测未来数据时，主要的难题是确定一组神经元权重和偏差。 使用进化优化算法是估计最佳权重和偏差值的方法之一。 大多数情况下，进化优化算法不能很好地适用于非数值组合优化问题，例如，旅行推销员问题，其目标是查找具有最短总路线长度的城市组合。

进化算法（如纯遗传算法）是元启发式算法。 这意味着，它们是一个通用框架和一组概念准则，可用于创建特定的算法以解决特定的问题。 因此，本文中介绍的示例可以看作是实验和创建进化优化代码的起点，而不是固定的静态代码库。

James McCaffrey博士 供职于 Volt Information Sciences, Inc.，在该公司他负责管理对华盛顿州雷蒙德市沃什湾 Microsoft 总部园区的软件工程师进行的技术培训。 他参与过多项 Microsoft 产品的研发工作，其中包括 Internet Explorer 和 MSN Search。 他是《.NET Test Automation Recipes》(Apress, 2006) 的作者，您可以通过以下电子邮箱地址与他联系：jammc@microsoft.com。

衷心感谢以下 Microsoft 技术专家对本文的审阅： Anne Loomis Thompson