• 發行項

本文章是由機器翻譯。

測試回合

使用 C# 的變形蟲方法優化

James McCaffrey

下載代碼示例

數值優化的目標是要解決方程。有許多基於微積分的確定性技術可用 ； 但是，不能輕鬆地使用古典優化技術解決一些困難的問題，特別是在機器學習和人工智慧等領域。在這種情況下，如變形蟲方法優化的替代品可以是值。變形蟲方法優化，我會在本文中討論的是在某些方面的粒子群優化，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 Studio2010年 （任何版本的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 顯示三維圖形的羅森布羅克的功能。


圖 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);
}

解決方法

變形蟲優化解決演算法鑒於圖 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 測試自動化食譜"（Apress，2006 年），並可以在達成 jammc@microsoft.com。

衷心感謝以下技術專家對本文的審閱：DarrenGehring (Microsoft) 和Mark栗子 (Microsoft)
Mark栗子為微軟在華盛頓州的 Redmond 的研究工作。他在應用數學從加州大學伯克利分校和博士學位文學學士來自新墨西哥大學。他的專長是在程式分析和程式合成，以使用此資訊來支援優化和應用程式軟體工程為重點的區域中。在他的網站是 HTTP://research.microsoft.com/en-us/um/people/marron/。
DarrenGehring 是測試經理，在華盛頓州的 Redmond 的微軟研究院。之前在微軟研究院工作，他在工作Microsoft SQL Server產品組 10 年。DarrenWeb 頁是在HTTP://research.microsoft.com/en-us/people/darrenge/。