测试运行

项目
12/08/2016

使用 C# 的变形虫方法优化

数值优化的目标是要解决方程。有许多基于微积分的确定性技术可用；但是，不能轻松地使用古典优化技术解决一些困难的问题，特别是在机器学习和人工智能等领域。在这种情况下，如变形虫方法优化的替代品可以是值。变形虫方法优化，我会在本文中讨论的是在某些方面的粒子群优化，2011 年 8 月的 MSDN 杂志问题所述相似 (msdn.microsoft.com/magazine/hh335067)。

了解哪些变形虫方法优化的最佳方法是和看看我哪里就是检查图1，其中显示演示程序中采取行动。在此程序中的目标是找到的 x 值和 y 被称为罗森布罗克的功能相对较简单的标准基准问题减至最低限度。此函数有已知的解决方案在 x = 1.0 和 y = 1.0 时的函数值为 0。

图 1 变形虫方法优化演示

该演示程序创建虚拟的变形虫，其中包含三个随机的潜在解决方案。最好的这些初步的解决方案不是很好，x =-0.66 和 y = 5.43，高产的 2499.52 函数值。该演示程序调用一个解决方法，和在幕后，它使用的变形虫方法以迭代方式找到更好和更好的解决办法。50 次迭代后, 该算法能够成功地找到最佳的解决方案。

在接下来的部分我提出并解释该演示程序的完整源代码。代码是可在 archive.msdn.microsoft.com/mag201306TestRun。本文假定您有至少中间级与现代程序语言的编程技巧。我编码演示使用 C#，但你不应该重构到另一种语言如 Visual Basic.NET 或 Python 演示太麻烦了。

变形虫方法算法

我在这里介绍的变形虫方法优化算法基于 1965年研究论文，最大限度"A 单纯形方法的功能减少，"由 J.A.单纯和 R.蜂蜜酒。

这种算法的关键部分所示图 2。在任何时间点上，有几个可能的解决办法。在大多数情况下，变形虫优化使用三个解决方案，在图中的红色。每个解决方案有一个相关联的目标函数值，因此，将最坏的解决方案（最高的函数的值因为目标是最大限度地），最好的解决办法（最小的函数值）和其他（s）。

图 2 变形虫优化基元操作

该算法是一个迭代过程。在每个步骤，它将尝试更换的最坏的解决方案与一个新的、更好地从三个候选人中的解决方案：反射的点、扩展的点和承包的点。这些候选人的每个谎言沿着一条线从最糟糕的时候通过质心 — — 一个要点就是在最糟糕的时候除外的所有点。在通常的情况有三种解决办法，质心将谎言中途的最佳点和其他（非最坏）点之间。

如果既不反射的点，扩大的点，也承包的点不是比当前最坏的解决方案更好，变形虫收缩本身通过移动所有点，除了最佳点，中途往最佳点。一些研究论文称这个过程为多个收缩。

当绘制随着时间的推移，如果这三个当前解决方案点相连的一条线 (和中的黑色虚线与图 2）、解决方案构成一个三角形，和他们的运动类似于变形虫爬过它的环境。在数学术语中，一架飞机上的三角形称为单纯，所以此优化算法，除了被称为变形虫方法或单纯 Mead 方法，有时称为单纯形法。

程序的整体结构

我编码作为单一的 C# 控制台应用的变形虫优化演示程序阳离子。我使用 Visual Studio 2010 （任何版本的 Visual Studio 应工作）和创建一个名为变形虫的新项目优化。加载该项目后，在解决方案资源管理器窗口中我重命名文件 program.cs，然后从更具描述性的 AmoebaProgram.cs，其中自动向明确重命名类的程序。已删除所有不需要的模板生成使用除单个语句引用的顶级系统命名空间的语句。

整个程序结构，与一些评论和删除，应使用 WriteLine 语句中列出图 3。

图 3 变形虫优化程序结构

using System; namespace AmoebaOptimization {   class AmoebaProgram   {     static void Main(string[] args)     {       try       {         Console.WriteLine("\nBegin amoeba method optimization demo\n");         int dim = 2;  // problem dimension         int amoebaSize = 3;  // number potential solutions         double minX = -10.0;         double maxX = 10.0;         int maxLoop = 50;         Console.WriteLine("Creating amoeba with size = " + amoebaSize);         Amoeba a = new Amoeba(amoebaSize, dim, minX, maxX, maxLoop);         Console.WriteLine("\nInitial amoeba is: \n");         Console.WriteLine(a.ToString());         Solution sln = a.Solve();         Console.WriteLine("Final amoeba is: \n");         Console.WriteLine(a.ToString());         Console.WriteLine("\nBest solution found: \n");         Console.WriteLine(sln.ToString());         Console.WriteLine("\nEnd amoeba method optimization demo\n");       }       catch (Exception ex)       {         Console.WriteLine(ex.Message);       }     }     public static double ObjectiveFunction(       double[] vector, object dataSource) { .
.
}   }   public class Solution : IComparable<Solution> { .
.
}   public class Amoeba { .
.
} }

目标函数

变形虫方法优化最通常用于解决数值最小化的问题。要最小化的函数通常称为成本函数或目标函数。演示程序中的图 1 解决虚拟数学基准称为罗森布罗克的函数。该函数有两个输入的变量，x 和 y，并被定义为 f(x,y) = 100 * （y-x ^2) ^2 > + (1-x) ^2 >。该函数具有一个解 x = 1.0，y = 1.0，给出的值为 0.0。 图 4 显示三维图形的罗森布罗克的功能。

Graph of the Objective Function
图 4 中的目标函数的关系图

在真实世界的情况下，变形虫优化用于查找基于数据的困难问题的解决。例如，假设你想预测股票市场价格。你可能会跟你相信的因素的列表是预测和一个等式，但您需要确定一组方程的误差最小的一套的已经知道结果的培训数据的数字常量。

演示计划目标函数是作为的主要程序类中定义的：

public static double ObjectiveFunction(   double[] vector, object dataSource) {   double x = vector[0];   double y = vector[1];   return 100.0 * Math.Pow((y - x * x), 2) +      Math.Pow(1 - x, 2); }

我使用名为数据源的虚拟输入的参数来表明在大多数情况下目标函数上取决于一些外部数据源例如，文本文件或 SQL 表。因为使用的公共和静态修饰符声明该函数，该函数是可见的在程序中演示的所有代码。

解决方案类

变形虫优化维护的可能的解决方案，解决方案类中定义的集合：

public class Solution : IComparable<Solution> {   public double[] vector;   public double value;   static Random random = new Random(1);   public Solution(int dim, double minX, double maxX) { .
.
}   public Solution(double[] vector) { .
.
}   public int CompareTo(Solution other) { .
.
}   public override string ToString() { .
.
} }

解决方案对象可以自动进行排序，从 IComparable 接口派生类。一个解决方案对象有只是两个重要领域：其中一个是数组的双重命名向量包含数字值的解决方案，和另一种是在目标函数的值。我使用公共范围内的成员字段，并移除所有错误检查为简单起见。静态随机对象允许用于生成随机解决方案的代码。

第一个解决方案构造函数创建一个随机的解决方案：

public Solution(int dim, double minX, double maxX) {   this.vector = new double[dim];   for (int i = 0; i < dim; ++i)   this.vector[i] = (maxX - minX) * random.NextDouble() + minX;   this.value = AmoebaProgram.ObjectiveFunction(this.vector, null); }

构造函数接受一个问题的层面，并限制每个向量组件。该演示程序的维度是 2，因为罗森布罗克的函数具有两个输入的变量，x 和 y。后为成员字段向量分配空间，构造函数到向量的数组分配荡妇与 maxX 之间的随机值，然后调用全局可访问的目标函数计算的值字段。

第二个解决方案构造函数从指定的数组的双创建一个解决方案：

public Solution(double[] vector) {   this.vector = new double[vector.Length];   Array.Copy(vector, this.vector, vector.Length);   this.value = AmoebaProgram.ObjectiveFunction(this.vector, null); }

因为解决方案类派生自 IComparable 接口，类必须实现一个 CompareTo 方法。 CompareTo 的定义使解决方案对象将自动排序从最好到最坏的（较小）（较大）值的目标函数：

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

可视化和调试目的，解决方案类定义了一种简单的使用字符串串联的 ToString 方法：

public override string ToString() {   string s = "[ ";   for (int i = 0; i < this.vector.Length; ++i) {     if (vector[i] >= 0.0) s += " ";     s += vector[i].ToString("F2") + " ";   }   s += "]  val = " + this.value.ToString("F4");   return s; }

变形虫类

变形虫类是基本上是数组的解决方案对象再加上一个使用的变形虫方法算法的解决方法。变形虫类的结构中列出图 5。

图 5 的变形虫类

public class Amoeba {   public int amoebaSize;  // Number of solutions   public int dim;         // Problem dimension   public Solution[] solutions;  // Potential solutions (vector + value)   public double minX;   public double maxX;   public double alpha;  // Reflection   public double beta;   // Contraction   public double gamma;  // Expansion   public int maxLoop;   // Limits main solving loop   public Amoeba(int amoebaSize, int dim, double minX,     double maxX, int maxLoop) { .
.
}   public Solution Centroid() { .
.
}   public Solution Reflected(Solution centroid) { .
.
}   public Solution Expanded(Solution reflected, Solution centroid) { .
.
}   public Solution Contracted(Solution centroid) { .
.
}   public void Shrink() { .
.
}   public void ReplaceWorst(Solution newSolution) { .
.
}   public bool IsWorseThanAllButWorst(Solution reflected) { .
.
}   public Solution Solve() { .
.
}   public override string ToString() { .
.
} }

我宣布所有字段和方法使用公共范围内，为简单起见，在开发过程中更容易调试。 AmoebaSize 字段指定变形虫对象中的潜在解决方案的数量。到目前为止最常用的值为 3，但是您可能想要尝试与较大的值。 Dim 字段表示必须解决的目标函数中的变量的数目 — — 两个如果罗森布罗克的函数。

阵列的解决方案包含潜在解决方案对象。虽然它不是从宣言》明确，阵列的解决方案必须在所有的时间，从到最坏的解决方案的最佳解决方案（最小值字段）进行排序。字段荡妇和 maxX 约束在解决方案的每个对象的初始数值。这些值将会从问题到问题发生变化。

字段 α、 β 和 γ 是常量所使用的解决方法调用的帮助器方法。字段 maxLoop 限制在解决处理循环的迭代次数。

单个变形虫构造函数创建一个数组，amoebaSize 解决方案对象，每个都有大小 dim 的向量场。所有的工作被执行的方法解决；变形虫类中的所有其他方法是帮助器方法。

变形虫构造函数定义如下：

public Amoeba(int amoebaSize, int dim, double minX, double maxX, int maxLoop) {   this.amoebaSize = amoebaSize;   this.dim = dim;   this.minX = minX; this.maxX = maxX;   this.alpha = 1.0; this.beta = 0.5; this.gamma = 2.0;   this.maxLoop = maxLoop;   this.solutions = new Solution[amoebaSize];   for (int i = 0; i < solutions.Length; ++i)     solutions[i] = new Solution(dim, minX, maxX);   Array.Sort(solutions); }

字段 α、 β 和 γ 控制行为的解决方法，并分别分配，0.5、 1.0、 2.0 中，硬编码值。研究表明这些值一般给出好的结果，但你可能想要尝试。已分配数组的解决方案之后，一个随机的解决方案对象被分配给每个单元格。 Array.Sort 方法进行排序从最佳值到最坏的解决方案。

变形虫类具有可视化和更容易调试简单的 ToString 方法：

public override string ToString() {   string s = "";   for (int i = 0; i < solutions.Length; ++i)     s += "[" + i + "] " + solutions[i].ToString() +       Environment.NewLine;   return s; }

算法基元

变形虫优化算法的一个关键方面是当前最严重的解决方案更换 — — 如果它导致一套更好的解决办法 — — 由所谓的反射点，扩大点或承包点。

变形虫类帮助器方法质心创建一个解决方案对象，在某种意义上是一个中间的解决方案之间，阿米巴虫除了最坏的解决方案中的所有解决方案（最坏的解决方案是解决方案的最大值与一个因为目标是尽量减少了目标函数，它将位于索引 amoebaSize-1）：

public Solution Centroid() {   double[] c = new double[dim];   for (int i = 0; i < amoebaSize - 1; ++i)      for (int j = 0; j < dim; ++j)       c[j] += solutions[i].vector[j];  // Accumulate sum of each component   for (int j = 0; j < dim; ++j)     c[j] = c[j] / (amoebaSize - 1);   Solution s = new Solution(c);   return s; }

帮助器方法反映创建一个解决方案对象，是在更好的解决方案的总方向。常量 alpha，通常设置为 1.0，控制如何远离重心移动产生的反射的解决方案。阿尔法的较大值生成的离质心的反射的点：

public Solution Reflected(Solution centroid) {   double[] r = new double[dim];   double[] worst = this.solutions[amoebaSize - 1].vector;  // Convenience only   for (int j = 0; j < dim; ++j)     r[j] = ((1 + alpha) * centroid.vector[j]) - (alpha * worst[j]);   Solution s = new Solution(r);   return s; }

帮助器方法扩展创建一个解决方案对象，甚至离质心比反映的解决方案。恒定伽玛，通常设置为 2.0，控制从质心有多远的反射的点：

public Solution Expanded(Solution reflected, Solution centroid) {   double[] e = new double[dim];   for (int j = 0; j < dim; ++j)     e[j] = (gamma * reflected.vector[j]) + ((1 - gamma) * centroid.vector[j]);   Solution s = new Solution(e);   return s; }

帮助器方法签约创建一个解决方案对象，大致是最坏的解决方案和质心之间。恒定的 beta 版，通常设置为 0.50，如何关闭控制到承包的点是最坏的解决方案：

public Solution Contracted(Solution centroid) {   double[] v = new double[dim];  // Didn't want to reuse 'c' from centroid routine   double[] worst = this.solutions[amoebaSize - 1].vector;  // Convenience only   for (int j = 0; j < dim; ++j)     v[j] = (beta * worst[j]) + ((1 - beta) * centroid.vector[j]);   Solution s = new Solution(v);   return s; }

帮助器方法 ReplaceWorst 替换当前最糟糕解决方案，位于索引 amoebaSize-1，用不同的解决办法（反映，展开或收缩点）：

public void ReplaceWorst(Solution newSolution) {   for (int j = 0; j < dim; ++j)     solutions[amoebaSize-1].vector[j] = newSolution.vector[j];   solutions[amoebaSize - 1].value = newSolution.value;   Array.Sort(solutions); }

如果既不反映，也不也扩大，不承包的点给出一套更好的解决方案，变形虫算法收缩当前解决方案集。从其当前位置向最佳点中途移动解决方案的每一点，除了位于索引 0 处的最佳点：

public void Shrink() {   for (int i = 1; i < amoebaSize; ++i)  // start at [1]   {     for (int j = 0; j < dim; ++j) {       solutions[i].vector[j] =         (solutions[i].vector[j] + solutions[0].vector[j]) / 2.0;       solutions[i].value = AmoebaProgram.ObjectiveFunction(         solutions[i].vector, null);     }   }   Array.Sort(solutions); }

Solve 方法

变形虫优化解决算法鉴于图 6，在高级别的伪代码。

图 6 变形虫优化解决算法

generate amoebaSize random solutions while not done loop   compute centroid   compute reflected   if reflected is better than best solution then     compute expanded     replace worst solution with better of reflected, expanded   else if reflected is worse than all but worst then     if reflected is better than worst solution then       replace worst solution with reflected     end if     compute contracted     if contracted is worse than worst       shrink the amoeba     else       replace worst solution with contracted     end if   else     replace worst solution with reflected   end if end loop return best solution found

尽管该算法是短的它是有点棘手，比首次出现和你可能必须十分仔细地研究它，如果你想要修改它出于某种原因。帮助器方法 IsWorseThanAllButWorst 使的解决方法很有点整齐。帮助器检查解决方案对象，并仅返回 true 如果解决方案对象（总是在算法中反映解决方案）是更糟（有一个更大的目标函数值）比变形虫，除了可能的最坏的解决方案（位于索引 amoebaSize-1）中的所有其他解决方案：

public bool IsWorseThanAllButWorst(Solution reflected) {   for (int i = 0; i < amoebaSize - 1; ++i) {     if (reflected.value <= solutions[i].value) // Found worse solution       return false;   }   return true; }

与所有的帮助器方法的地方中, 列出的解决方法， 图 7，是相当短。在解决处理循环 maxLoop 次迭代后退出。一般情况下，maxLoop 好值变化从一个问题跳到另一个问题，必须通过试验和错误决定。替代或额外的停车条件是退出处理循环中，阿米巴虫的解决方案的平均误差低于一些依赖问题的值时。

图 7 解决方法

public Solution Solve() {   int t = 0;  // Loop counter   while (t < maxLoop)   {     ++t;     Solution centroid = Centroid();     Solution reflected = Reflected(centroid);     if (reflected.value < solutions[0].value)     {       Solution expanded = Expanded(reflected, centroid);       if (expanded.value < solutions[0].value)         ReplaceWorst(expanded);       else         ReplaceWorst(reflected);       continue;     }     if (IsWorseThanAllButWorst(reflected) == true)     {       if (reflected.value <= solutions[amoebaSize - 1].value)         ReplaceWorst(reflected);       Solution contracted = Contracted(centroid);       if (contracted.value > solutions[amoebaSize - 1].value)         Shrink();       else         ReplaceWorst(contracted);       continue;     }     ReplaceWorst(reflected);   } // loop   return solutions[0];  // Best solution }

自定义代码

代码示例，并在这篇文章中提出的解释应然后您运行如果你想要与实验或变形虫方法优化在软件系统中使用。有可能要考虑的几个修改。在主要算法循环中之前计算的质心和反射的解决办法，, 我经常计算一个纯粹随机解决方案和检查，以查看此随机解决方案是否比当前最坏的解决方案更好。这种方法有助于防止困在当地的最低解决方案中的优化算法。

另一种自定义项可能是计算多个反射的点。而不是位于当前最坏的解决方案与形心之间的界线的单一反射点，您可以计算额外的反射的点，躺在不同的行上。这种方法还有助于避免局部极小值的陷阱。

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

衷心感谢以下技术专家对本文的审阅：达伦 Gehring (Microsoft) 和马克栗子 (Microsoft)
马克栗子为微软在华盛顿州的 Redmond 的研究工作。他在应用数学从加州大学伯克利分校和博士学位文学学士来自新墨西哥大学。他的专长是在程序分析和程序合成，以使用此信息来支持优化和应用程序软件工程为重点的区域中。在他的网站是 https://research.microsoft.com/en-us/um/people/marron/。
达伦 Gehring 是测试经理，在华盛顿州的 Redmond 的微软研究院。之前在微软研究院工作，他在 Microsoft SQL Server 产品组工作 10 多年。达伦的 Web 页是在 https://research.microsoft.com/en-us/people/darrenge/。