本文章是由機器翻譯。

測試回合

螢火蟲演算法優化

James McCaffrey

下載代碼示例(VB)

在機器學習中數值優化演算法通常用於查找一組值變數 — — 通常被稱為權重 — —，儘量減少一些誤差的測量。例如，分類 logistic 迴歸分析使用數學方程在哪裡，如果 n 預測變數，但也有必須確定的 n + 1 的權重值。確定的權重值的過程被稱為培養模式。這個想法是使用具有已知正確的輸出值的培訓資料的集合。一種優化演算法用於查找的值的誤差，計算出的輸出值和正確的輸出值之間的區別是最小的權重。

有很多不同的優化演算法。這篇文章解釋了一個相對較新 (2009 年第一次出版） 稱為螢火蟲演算法 （FA） 優化技術。FA 優化鬆散建模的螢火蟲群的行為。

一個好的方法，以及得到的什麼法優化是一個想法，看看這篇文章將走向何方是來看一看該演示程式中圖 1。該演示程式的目標是使用 FA 優化來查找具有五個輸入變數的 Michalewicz 函數的最小值。Michalewicz 函數是標準基準函數用於計算數值優化演算法的有效性。有五個輸入值，函數具有 z 最小值 =-4.6877 位於 x = (2.2029 1.5707，1.2850，1.9231，1.7205）。

圖 1 中行動的螢火蟲演算法優化

Michalewicz 函數是大多數的優化演算法很難的因為它有幾個局部極小值和幾個平坦區域 （所有 z 值都是幾乎相等）。它是不可能輕鬆地視覺化 Michalewicz 函數與五個輸入值，但是你可以通過考試理念的功能特點­入會須知圖中所示的兩個輸入值的函數圖 2。函數的定義中使用數學術語是顯示在圖的底部。

圖 2 Michalewicz Function 的兩個變數

該演示程式將螢火蟲的數量設置為 40。 每個螢火蟲有一個虛擬的位置表示最小化問題的一個可能的解決方案。更多的螢火蟲增加找到真正的最優解，這會降低性能的機會。FA 優化通常使用 15 到 40 螢火蟲。

該演示將問題維度設置為 5，因為有五個輸入的值。足總杯是一個反覆運算的過程，需要最大的迴圈計數器值。在機器學習優化的迴圈計數器變數往往是命名的時代，將最大值為 1,000 反覆運算演示設置。最大反覆運算次數將會發生變化的問題，但 1000 是一個合理的起始值。英足總有一個隨機性的元素和演示設置為任意值 0 的亂數字產生器的種子值。

在這個演示中運行圖 1，到目前為止發現的最好的位置相關聯的最好 （最小） 錯誤顯示每 100 的時代。該演算法完成發現任何螢火蟲為的最佳位置後，x = (2.2033、 1.5711、 1.2793、 1.1134、 2.2216)。此解決方案是接近，但並不完全等於 x = 2.2029 1.5707、 1.2850、 1.9231 1.7205） 的最優解。由發找到解決方案 Michalewicz 函數的值是-4.69 的-4.45，而是-4.69 的在真實的最小值附近。FA 解決方案的錯誤是 0.0561。

這篇文章假設你有至少中級程式設計技能，但不是承擔你知道任何關於數值優化或螢火蟲演算法。該演示程式使用 C# 編寫，但你不應該有太大的困難，到另一種語言如 JavaScript 或 Python 代碼進行重構。

在這篇文章中，提出了一種完整的演示代碼中，與一些少量的編輯，以節省空間。演示也是本文附帶的代碼下載中提供的。演示代碼具有所有正常的錯誤檢查已刪除，以保持較小的代碼的大小並盡可能清楚的主要思想。

程式的整體結構

程式的整體結構提出了圖 3。若要創建演示，我推出Visual Studio，並創建一個新 C# 主控台應用程式命名為 FireflyAlgorithm。演示有沒有重大的 Microsoft.NET 框架依賴關係，因此，任何新版本的Visual Studio將工作。

圖 3 螢火蟲演示程式結構

using System;
namespace FireflyAlgorithm
{
  class FireflyProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin firefly demo");
      // Code here
      Console.WriteLine("End firefly demo");
      Console.ReadLine();
    }
    static void ShowVector(double[] v, int dec, bool nl)
    {
      for (int i = 0; i < v.Length; ++i)
        Console.Write(v[i].ToString("F" + dec) + " ");
      if (nl == true)
        Console.WriteLine("");
    }
    static double[] Solve(int numFireflies, int dim,
      int seed, int maxEpochs) { . . }
    static double Distance(double[] posA,
      double[] posB) { . . }
    static double Michalewicz(double[] xValues) { . . }
    static double Error(double[] xValues) { . . }
  } // Program
  public class Firefly : IComparable<Firefly>
  {
    // Defined here
  }
}

範本代碼載入到Visual Studio編輯器之後，在解決方案資源管理器視窗我重命名為更具描述性的 FireflyProgram.cs 和Visual Studio自動 Program.cs 檔重命名類程式對我來說。 頂部的原始程式碼，我刪掉所有不必要使用語句，離開只是參考系統。

我編碼演示使用一種常用的靜態方法技術，而不是完全面向物件的程式設計方法。演示中主要有所有的控制邏輯。Main 方法開始通過顯示演示的目的：

Console.WriteLine("Goal is to solve the Michalewicz benchmark function");
Console.WriteLine("The function has a known minimum value of -4.687658");
Console.WriteLine("x = 2.2029 1.5707 1.2850 1.9231 1.7205");

接下來，FA 所需的參數設置：

int numFireflies = 40;
int dim = 5;
int maxEpochs = 1000;
int seed = 0;

對這些陳述顯示參數值：

Console.WriteLine("Setting numFireflies = " + numFireflies);
Console.WriteLine("Setting problem dim = " + dim);
Console.WriteLine("Setting maxEpochs = " + maxEpochs);
Console.WriteLine("Setting initialization seed = " + seed);

螢火蟲演算法調用如下所示：

Console.WriteLine("Starting firefly algorithm");
double[] bestPosition = Solve(numFireflies, dim, seed, maxEpochs);
Console.WriteLine("Finished");

Main 方法通過顯示 FA 結果得出結論：

Console.WriteLine("Best solution found: ");
Console.Write("x = ");
ShowVector(bestPosition, 4, true);
double z = Michalewicz(bestPosition);
Console.Write("Value of function at best position = ");
Console.WriteLine(z.ToString("F6"));
double error = Error(bestPosition);
Console.Write("Error at best position = ");
Console.WriteLine(error.ToString("F4"));

螢火蟲演算法是元啟發式真的比一個說明性的演算法。我的意思是 FA 是一套可以適用于許多不同類型的優化問題的設計準則。

理解螢火蟲演算法

在這篇文章提出的螢火蟲演算法基於 2009年研究論文，為"螢火蟲優化多式聯運演算法，"新村 — — 她楊。螢火蟲演算法的過程如圖中所示圖 4。下圖表示了簡化虛擬極小化問題，有的只是兩個輸入的值，X 和 Y，和全域最小值是在 X = 0 和 Y = 0。 有三個螢火蟲。螢火蟲 [0] 是在 （2，1），所以是最接近正確的解決方案。螢火蟲 [1] 是在-4-4）。螢火蟲 [2] 是在 8-8），最遠的距離是從解決方案。

圖 4 螢火蟲演算法

真正的螢火蟲飛行昆蟲使用發光，大概為了吸引異性的輝光。每個螢火蟲可以閃耀著不同的強度。在足總杯，螢火蟲更好，意思一個小的錯誤，有較高的強度。在圖 4、 然後，螢火蟲 [0] 具有最高的強度、 螢火蟲 [1] 具有中間強度和螢火蟲 [2] 具有弱變強。

法的基本思想是一隻螢火蟲將被吸引到具有高的強度，任何其他螢火蟲和吸引力 （距離移動朝更加激烈的螢火蟲） 是更強的如果兩只螢火蟲之間的距離小於。所以，在圖 4，螢火蟲 [0] 具有高強度及將不會移動。螢火蟲 [1] 和 [2] 螢火蟲會都被吸引到和走向螢火蟲 [0]。因為螢火蟲 [1] [2] 螢火蟲比接近螢火蟲 [0]，螢火蟲 [1] 將移動更遠的距離比螢火蟲 [2]。

展示層次非常高的偽代碼中，提出了螢火蟲演算法在圖 5。乍一看，該演算法似乎很簡單 ； 然而，它是非常微妙，你會看到當給出了代碼實現。

第一個主要問題是定義一隻螢火蟲的強度。因為足總杯是元啟發式的你是自由定義強度，但是你喜歡，只要較高的強度是與每個處於更好的解決方案。下一個主要問題是定義的吸引力，以便接近螢火蟲將走向一個更強烈的目標多遙遠螢火蟲會移動。

Figure 5 Firefly Algorithm

initialize n fireflies to random positions
loop maxEpochs times
  for i := 0 to n-1
    for j := 0 to n-1
      if intensity(i) < intensity(j)
        compute attractiveness
        move firefly(i) toward firefly(j)
        update firefly(i) intensity
      end for
    end for
  sort fireflies
end loop
return best position found

螢火蟲演算法實現

方法求解的定義開始：

static double[] Solve(int numFireflies, int dim, int seed, int maxEpochs)
{
  Random rnd = new Random(seed);
  double minX = 0.0;
  double maxX = 3.2;
  double B0 = 1.0;
  double g = 1.0;
  double a = 0.20;
  int displayInterval = maxEpochs / 10;
...

本地變數這個混蛋和 maxX 建立每個螢火蟲位置的界限。在這裡使用的值，0.0 和 3.2 (大約 Pi) 是特定于 Michalewicz 功能。對於機器學習優化與歸一化的資料，值-10.0 和 + 10.0 比較常見。

本地變數 B0 （基地測試版），g (伽瑪) 和 （阿爾法） 控制到另一隻螢火蟲的吸引力。使用的值 （1.0，1.0 和 0.20） 被建議的來源研究論文。本地變數 displayInterval 控制通常如何顯示進度消息。

接下來，創建了空的螢火蟲群：

double bestError = double.MaxValue;
double[] bestPosition = new double[dim]; // Best ever
Firefly[] swarm = new Firefly[numFireflies]; // All null

螢火蟲物件是程式定義，並且封裝位置、 關聯的錯誤和相應的強度。最初，所有的螢火蟲是 null 的物件。螢火蟲類定義將在這篇文章的下一節仲介紹。接下來，一群具現化，並且隨意放置的位置。為每一隻螢火蟲，螢火蟲建構函式調用：

for (int i = 0; i < numFireflies; ++i)
{
  swarm[i] = new Firefly(dim);
  for (int k = 0; k < dim; ++k) // Random position
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
...

該建構函式隱式設置到 （0.0，0.0，0.0，0.0，0.0） 的位置與關聯的錯誤及強度為假值為 0.0。然後每個元件的位置陣列設置為這個混蛋和 maxX （0.0 和 3.2） 之間的隨機值。下一步，當前螢火蟲錯誤及強度計算：

swarm[i].error = Error(swarm[i].position);
  swarm[i].intensity = 1 / (swarm[i].error + 1);
...

誤差函數將在短期內提交。在這裡，螢火蟲的強度被定義為這樣小的誤差值將具有高強度和較大的誤差值將具有低強度的逆誤差。分母中的 1 零，從而防止司，當誤差為零。初始化的結論通過檢查新創建的螢火蟲，看它是否有發現的最好的位置是：

...
  if (swarm[i].error < bestError)
  {
    bestError = swarm[i].error;
    for (int k = 0; k < dim; ++k)
      bestPosition[k] = swarm[i].position[k];
  }
} // For each firefly

主處理迴圈始于這些語句：

int epoch = 0;
while (epoch < maxEpochs)
{
  if (epoch % displayInterval == 0 && epoch < maxEpochs)
  {
    string sEpoch = epoch.ToString().PadLeft(6);
    Console.Write("epoch = " + sEpoch);
    Console.WriteLine(" error = " + bestError.ToString("F14"));
  }
...

固定的反覆運算次數的替代方法是在 bestError 的值下降到低於一些較小的閾值值時中斷 （0.00001 很常見）。每個螢火蟲相比其他所有的螢火蟲使用嵌套的 for 迴圈：

for (int i = 0; i < numFireflies; ++i) // Each firefly
{
  for (int j = 0; j < numFireflies; ++j) // Others
  {
    if (swarm[i].intensity < swarm[j].intensity)
    {
      // Move firefly(i) toward firefly(j)
...

請注意，因為每個循環索引從 0 開始，每一對螢火蟲比較兩次在每次反覆運算中 while 迴圈。要移動向另一個螢火蟲一隻螢火蟲具有較高的強度，必須首先計算吸引力：

double r = Distance(swarm[i].position, swarm[j].position);
double beta = B0 * Math.Exp(-g * r * r);
...

可變 Beta 定義吸引力並將一會兒用來移動螢火蟲 [i]。它的價值取決於螢火蟲 [i] 和 [j] 之間距離的平方而使用 helper 方法距離計算。方法距離返回兩個位置之間的歐氏距離。例如，如果只螢火蟲 [i] 在兩個維度是在 3.0 4.0） 和螢火蟲 [j] 是在 9.0 5.0），它們之間的距離是 sqrt ((5-3) ^2 + (9-4） ^2) = sqrt (4 + 25) = sqrt(29) = 5.4。請注意該 Beta 版使用距離平方，是逆的平方根操作，因此可以簡化計算的 Beta 版，犧牲靈活性，如果你決定使用不同的度量的距離。

實際運動完成這些語句所示：

for (int k = 0; k < dim; ++k)
{
  swarm[i].position[k] += beta *
    (swarm[j].position[k] - swarm[i].position[k]);
  swarm[i].position[k] += a * (rnd.NextDouble() - 0.5);
  if (swarm[i].position[k] < minX)
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
  if (swarm[i].position[k] > maxX)
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
}
...

螢火蟲 [i] 的位置在泰熙元件移動 β-­分數的螢火蟲 [i] 和 [j] 螢火蟲向螢火蟲 [j] 之間的距離。然後一個小的隨機術語添加到泰熙位置的每個元件。這有助於防止演算法陷入非最優解。每個位置元件檢查，看看是否它出去範圍，並且如果是這樣，分配一個隨機值，在範圍。

通過更新錯誤和強度的只是移動的螢火蟲執行完嵌套的迴圈運動代碼之後：

swarm[i].error = Error(swarm[i].position);
      swarm[i].intensity = 1 / (swarm[i].error + 1);
    } // If firefly(i) < firefly(j)
  } // j
} // i each firefly
...

方法解決最後這些語句：

...
   Array.Sort(swarm); // low error to high
    if (swarm[0].error < bestError)
    {
      bestError = swarm[0].error;
      for (int k = 0; k < dim; ++k)
        bestPosition[k] = swarm[0].position[k];
    }
    ++epoch;
  } // While
  return bestPosition;
} // Solve

比較了每個對螢火蟲並沒那麼強烈的螢火蟲有走向更加激烈的螢火蟲，螢火蟲物件的陣列排序從低誤差高錯誤是最好的一個後在群 [0]。檢查此物件，以查看是否已找到一個新的最佳解決方案。排序的螢火蟲物件的陣列也具有重要作用的改變他們的陣列中的位置，以便處理的物件是以不同的順序每次 while 迴圈。

説明器方法

方法解決調用協助程式方法距離和錯誤，反過來調用説明器方法 Michalewicz。説明器方法的距離定義如下：

static double Distance(double[] posA, double[] posB)
{
  double ssd = 0.0; // sum squared diffrences
  for (int i = 0; i < posA.Length; ++i)
    ssd += (posA[i] - posB[i]) * (posA[i] - posB[i]);
  return Math.Sqrt(ssd);
}

説明器方法 Michalewicz 定義如下：

static double Michalewicz(double[] xValues)
{
  double result = 0.0;
  for (int i = 0; i < xValues.Length; ++i) {
    double a = Math.Sin(xValues[i]);
    double b = Math.Sin(((i+1) * xValues[i] * xValues[i]) / Math.PI);
    double c = Math.Pow(b, 20);
    result += a * c;
  }
  return -1.0 * result;
}

如果你是指底部的 Michalewicz 函數的數學定義圖 2，您將看到該函數具有指數 2 米。然而，通常將 m 的值設置為 10，所以在代碼中，使用恒定值 20。説明器方法錯誤定義如下：

static double Error(double[] xValues)
{
  int dim = xValues.Length;
  double trueMin = 0.0;
  if (dim == 2)
    trueMin = -1.8013; // Approx.
  else if (dim == 5)
    trueMin = -4.687658; // Approx.
  double calculated = Michalewicz(xValues);
  return (trueMin - calculated) * (trueMin - calculated);
}

錯誤方法只是返回的 Michalewicz 函數，已知的最小值與理論計算的值的平方差的產品。此虛擬錯誤函數可以計算速度非常快，但在大多數機器學習方案中，誤差函數可以是非常耗費時間。

螢火蟲類

螢火蟲類定義的開頭：

public class Firefly : IComparable<Firefly>
{
  public double[] position;
  public double error;
  public double intensity;
...

類繼承 IComparable 介面，以便可以自動排序陣列和包含的物件的清單。使用公共的範圍內，為簡單起見定義的資料欄位。因為錯誤和強度之間的一對一映射，或者這兩個領域可能會被放棄。類的建構函式是：

public Firefly(int dim)
{
  this.position = new double[dim];
  this.error = 0.0;
  this.intensity = 0.0;
}

有很多設計替代品，你可以考慮。在這裡，該建構函式只為位置陣列分配空間。公共的方法就只是和：

public int CompareTo(Firefly other)
  {
    if (this.error < other.error) return -1;
    else if (this.error > other.error) return +1;
    else return 0;
  }
} // Class Firefly

螢火蟲物件從低錯誤到高訂單和方法。等效替代是順序從高到低的強度。

幾個評論

在這篇文章提出了一種螢火蟲演算法的實現基於種子 2009年紙。原演算法催生了幾種變體。研究提出了一些資料表明 FA 是優於粒子群優化演算法，至少對一些虛擬基準優化問題。我有點懷疑。然而，在我看來，足總杯是非常有用的方案是當最小化目標函數具有多個解。它雖不是顯而易見的事實證明，FA 自動自組織成子蜂擁而至，同時可以找到多個解決方案。

Dr. James McCaffrey 適合在雷德蒙的微軟研究院  他曾在幾個 Microsoft 產品包括 Internet Explorer 和冰。 博士。 麥卡弗裡也可以撥打 jammc@microsoft.com。

感謝以下的微軟技術專家對本文的審閱：陶德 · 貝洛、 馬西亞諾 Moreno 迪亞茲維亞和愛麗森溶膠