本文章是由機器翻譯。

測試回合

革命性最佳化演算法

James McCaffrey

下載代碼示例

一種進化優化演算法是執行 meta-heuristic 仿照生物進化的行為。這些演算法可針對困難或極度困難的數字最小化問題組合尋求適當的解決方案。有三個原因，您可能有興趣進化優化演算法。首先，瞭解如何編寫代碼這些演算法可以實際加到您的開發人員、 經理和測試技能集。第二，一些使用，如錦標賽選擇的技術可以在其他演算法和編碼方案中重用。第三，許多工程師的結果只是發現這些演算法的有趣在他們自己的權利。

一種進化優化演算法是本質上是一種遺傳演算法的虛擬的染色體進行的實際值而不是某種形式的位表示形式。您可以看到我駛向哪裡的最佳方式是看看圖 1 和圖 2。

施韋費爾圖 1 的功能

圖 2 進化優化演示

中的圖圖 1 顯示施韋費爾的功能，標準基準數值最小化問題。施韋費爾的函式定義如下：

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

函數具有最小值為-837.9658 時 x = y = 420.9687。 在圖 1 此最小值是遠左角的圖形。 該函數故意旨在優化演算法，著手解決眾多虛假本地最小值，很難。

中的截圖圖 2 顯示從一個 C# 主控台應用程式的輸出。 後顯示一些資訊性消息，該程式設置八個參數，然後使用一種進化演算法尋找最佳的解決方案。 在此示例中，該演算法發現的最佳解決方案 （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 來創建一個新 C# 主控台應用程式專案命名為 EvolutionaryOptimization。 在解決方案資源管理器視窗中，我重 program.cs，然後從命名為 EvolutionaryOptimizationProgram.cs，其中自動重命名類程式。 我也將刪除所有不需要的範本生成使用語句。

圖 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 包含大部分演算法邏輯。 類個人模型最小化問題的可能解決方案。 類問題定義的功能，可最小化，施韋費爾的功能在這種情況下。 一種替代設計結構就是將 Evolver 類內部單獨的類。

單獨的類

個人類的定義開始：

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 介面，以便按其健身可以自動排序的單個物件的陣列。 類有八個資料成員。 染色體陣列表示對目標問題的一個可能的解決方案。 請注意該染色體是陣列的兩倍，而不是某種形式的通常由遺傳演算法使用的位表示形式的陣列。 進化優化演算法有時也稱為實數型遺傳演算法。

健身欄位是多麼好的染色體解決方案的一項措施。 最小化的問題，對於較小的值的健身都優於較大的值。 為簡單起見，染色體和健身聲明與公眾範圍以便它們可見於在 Evolver 類中的邏輯。 基因是染色體陣列中的一個值，此 numGenes 欄位保存實際值的數目可能的解決方案中。 施韋費爾的函數，此值將設置為 2。 有很多數位優化問題，可以指定每個基因的最小和最大值，這些值存儲在 minGene 和 maxGene。 如果不知道這些值，可以設置 minGene 和 maxGene 雙。MinValue 和雙。MaxValue。 當我使用他們的代碼，我來解釋 mutateRate 和精密欄位。

個別類定義將繼續與類的建構函式：

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

建構函式為染色體陣列分配記憶體，並將 maxGene minGene） 範圍內的隨機值分配給每個基因細胞。 請注意，通過調用的外部定義的健身方法用於設置健身欄位的值。 或者，您可以傳遞到建構函式引用的健身方法通過委託。 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;
  }
}

走過的染色體陣列，更改為隨機值範圍中的隨機選定的基因的突變操作 （羅喜)。 要分配的值的範圍是由精度和 maxGene 成員值決定的。 在示例中圖 2、 精度設置為 0.0001 和 maxGene 設置為 500。 一種基因突變可能的最高值是 0.0001 ＊ 500 = 0.05，這就意味著如果一種基因的突變，其新值將舊值加上或減去-0.05 和 +0.05 之間的隨機值。 通知的精度值對應于解決方案 ； 中的小數位數 這是合理的啟發式演算法用於精度值。 突變率值控制多少基因在染色體中的將被修改。 一個啟發式演算法 mutateRate 欄位的值是使用 1.0/numGenes，所以，平均一個基因在染色體中的會突變，每次調用 Mutate 時。

個別類定義使用 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 方法定義了預設排序次序為單個物件，在這種情況下從最小的健身 （最佳） 到最大健身。

問題類別

問題類封裝的進化演算法的目標問題：

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

由於一個染色體陣列，表示可能的解決方案，它被通過作為輸入參數的健身方法。 任意最小化的問題，要最小化的目標函數通常稱為成本函數。 在進化和遺傳演算法的方面，但是，通常叫做健身函數。 通知術語是有點尷尬，因為身體素質較低的值均優於較高的值。 在此示例中，健身功能是完全獨立的。 在很多優化問題，健身功能需要額外的輸入的參數，如資料或對外部資料檔的引用的矩陣。

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 成員持有的人數在人口中。 PopSize 的較大值往往提高速度而該演算法的準確性。 一般情況下，進化演算法是比普通的遺傳演算法快得多，因為進化演算法實際值的工作並不導致轉換和操縱位申述的開銷。 Evolver 類的心是一個名為人口的單個物件的陣列。 沙頭角和索引成員用作所選擇的方法，你很快就會看到。

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

建構函式為人口陣列分配記憶體，然後使用單獨的建構函式用來填充該陣列具有基因隨機值的個人。 通過選擇的方法，拿兩個父母使用命名索引的陣列。 稍後，我會解釋索引，但通知該建構函式分配每個個體的一個儲存格，並按順序分配整數從 0 到 popSize-1。

中列出的演變方法， 圖 5，是相當之短。

圖 5 進化方法

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

演變方法返回找到一個類型的陣列作為雙的最佳解決方案。 作為替代方法，您可以返回單個物件染色體凡持有找到最佳的解決方案。 演變方法開始通過初始化的最佳健身和向後的第一個在人口中的最佳染色體。 方法逐一查看準確時間、 使用代 (代) 作為迴圈計數器的 maxGenerations。 幾個備選方案之一是要停止時沒有改善已發生後一些的反覆運算次數。 Select 方法返回從人口的很好，但不是一定是最好的兩個人。 這兩個家長將傳遞給重現，其中創建並返回兩個孩子。 接受方法放入的人口，取代兩個現有個體的兩個孩子。 外來移民方法將生成一個新的隨機個人，並將其放置到人口。 新的人口然後掃描，看看是否在人口中的三個新個人的任何新的最佳解決方案。

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

該方法接受良好的個人選擇的數目，並將它們返回陣列中的類型個人。 為了儘量減少的代碼量，我省略掉正常的錯誤檢查，如驗證請求的個人的數目小於人口規模。 Select 方法使用一種稱為錦標賽選擇技術。 生成隨機候選個人的一個子集，並且返回最佳的前 n 個他們的。 入變數 tournSize，這是一些分數，馬頭，總人口大小的計算是候選人的人數。 沙頭角的較大值增加的最好的兩個人會被選中的概率。

記得 Evolver 類具有命名具有值 0 的索引成員陣列 ... ... popSize 1。 ShuffleIndexes 説明器方法重新排列為順序是隨機的陣列索引中的值。 前 n 個隨機的索引用於人口從挑選候選人。 Array.Sort 方法然後排序的候選人個人從最小 (最佳) 健身到最大。 返回在頂部 n 個人的排序的候選人。 有許多不同的進化選擇演算法。 錦標賽選擇相比，大多數其他技術的一個優點是可以通過修改頭參數進行調整選擇壓力。

ShuffleIndexes 説明器方法使用標準的費雪耶茨洗牌演算法：

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。 此方法首先通過生成隨機的交叉點。 索引是有點棘手，但 child1 創建從左邊的部分的 parent1 和 parent2 的右側部分。 Child2 是從左邊的部分的 parent2 和 parent1 的右側部分創建的。 這個想法所示圖 7，其中有五個基因與兩個父母，交叉點是 2。 常見的設計替代方法是使用多個交叉點。 他們突變後創建的物件的個別兒童和其新健身計算。

圖 6 的複製方法

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 交叉的機制

接受方法放入人口由重現創建的兩個孩子個人：

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

人口陣列按健身，其中的兩個最差個人置於陣列，哪裡然後替換它們的孩子們最後兩個儲存格進行排序。 有很多途徑選擇哪兩個人死。 一種可能是使用一種稱為輪盤賭輪選擇技術近親選擇兩個人要更換，更糟糕的個人有較高概率的被取代的地方。

外來移民方法生成一個新的隨機個人並將其放置到的人口正上方的兩個孩子只是生成的位置 （人民入境事務處説明，防止進化演算法陷入局部極小值的解決辦法 ； 設計方案包括創建多個移民和移民放置在人口中的隨機位置）：

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

實驗的切入點

在這篇文章，進化優化用於估計一個數學方程的最小值。雖然進化優化演算法可以用這種方式，更經常他們用來尋找一套更大的優化問題，是沒有有效的確定性演算法中的數值參數的值。例如，當使用一種神經網路對現有資料進行分類來進行預測未來的資料，面臨的主要挑戰是確定一組神經元權重和偏見。使用一種進化優化演算法是一種估計的最佳權重和偏差值的方法。在大多數情況下，不適合使用旅行推銷員問題，目標是要找到相結合的最短路徑總長度的城市非數值組合優化問題的進化優化演算法。

進化演算法，純粹的遺傳演算法，像是元-啟發式演算法。這意味著他們的總體框架和一套概念的指引，可用於創建特定的演算法，以解決特定的問題。所以本文仲介紹的示例可以查看更多作為起始點的實驗和創建進化優化代碼，而不是一個固定的、 靜態的代碼基。

Dr. James McCaffrey 為伏資訊科學 Inc.，凡他管理技術培訓工作在華盛頓雷德蒙的微軟校園軟體工程師的工作。他曾對幾個微軟的產品，包括互聯網資源管理器和 MSN 搜索。他是作者的".NET 測試自動化食譜"（很，2006年），並可以在達到jammc@microsoft.com。

感謝以下 Microsoft 技術專家，檢討這篇文章：Anne Loomis Thompson