發行項
08/31/2015

本文章是由機器翻譯。

測試運行

細菌覓食最佳化

細菌覓食優化（BFO）是一種迷人的人工智慧 (AI) 技術，可以用於查找近似極難或不可能的數位最大化或最小化問題的解決方案。我在本文中描述的 BFO 的版本基於 2002年紙，"仿生學的細菌覓食的分散式優化及控制，"由博士。Kevin Passino。（本文可以通過互聯網搜索，找到，但訂閱是必需的）。BFO 是一種概率的技術，模型的常見細菌如 E.尋找食物和生殖行為為了解決數值優化問題的大腸桿菌凡有不確定性的有效途徑。為您的最佳方式，感受 BFO 是什麼，看看這篇文章，我朝就檢查圖 1 和圖 2。

圖 1 Rastrigin 功能問題

圖 2 使用細菌覓食的優化

圖 1 是一個圖形的 Rastrigin 的功能，通常作為標準基準問題使用，測試優化演算法的有效性。目標是找到值的 x 和 y 的最小化功能。你可以看到有很多谷，這是局部極小值的解決方案。然而，有只有一個全球解決方案在 x = 0.0 和 y = 函數的值在哪裡 0.0 0.0。

圖 2 是 BFO 嘗試解決 Rastrigin 功能的截圖。該程式設置幾個參數，包括類比細菌（在此示例中的 100）的數目。每一種細菌的立場，表示可能的解決方案。最初，所有的細菌都設置為隨機的職位。每個位置都具有相關的成本，它表示 Rastrigin 函數的值。執行主處理迴圈，不同的細菌會發現先後有更好的解決方案。在處理結束後，找到最佳的解決方案是 0.0002 當 x =-0.0010 和 y = 0.0005 — — 極其接近但不是完全的最優解。

我在本文的其餘部分中詳細解釋 BFO 演算法和你漫步顯示運行的程式圖 2。我編碼演示計畫在 C# 中，但您應該能夠很容易適應這裡提交給另一種語言如 Visual Basic 代碼。NET 或 Windows PowerShell。完整的原始程式碼的程式是可在 archive.msdn.microsoft.com/mag201203TestRun。本文假定您有中級或高級程式設計技巧與現代的程式語言，但是並不假設你知道任何關於 BFO 或相關的人工智慧技術。

真正的細菌行為

E.如細菌大腸桿菌是這個星球上的最成功的生物之一。細菌有半剛性稱鞭毛的附肢。當所有鞭毛不斷以逆時針方向都旋轉時，螺旋槳影響創建和一種細菌會游更多或少直方向。

細菌往往會游泳時他們正在努力改進在某種意義上，例如，當發現越來越多的養分漸變，例如。當所有的鞭毛旋轉順時針方向時，一種細菌會快速滾落和指向新的方向。細菌容易跌倒時遇到的有毒的物質，或當他們在不提高的漸變。細菌繁殖，約每隔 20 分鐘左右通過無性劃分成完全相同的兩個女兒。更健康的細菌往往更比不太健康的細菌繁殖。

整體的程式結構

整體的程式結構，對於 BFO 演示中列出圖 3。

圖 3 整體 BFO 程式結構

using System;
namespace BacterialForagingOptimization
{
  class BacterialForagingOptimizationProgram
  {
    static Random random = null;
    static void Main(string[] args)
    {
      try
      {
        int dim = 2;
        double minValue = -5.12;
        double maxValue = 5.12;
        int S = 100;
        int Nc = 20;
        int Ns = 5;
        int Nre = 8;
        int Ned = 4;
        double Ped = 0.25;
        double Ci = 0.05;
        random = new Random(0);
        // Initialize bacteria colony
        // Find best initial cost and position
        int t = 0;
        for (int l = 0; l < Ned; ++l) // Eliminate-disperse loop
        {
          for (int k = 0; k < Nre; ++k) // Reproduce-eliminate loop
          {
            for (int j = 0; j < Nc; ++j) // Chemotactic loop
            {
              // Reset the health of each bacterium to 0.0
              for (int i = 0; i < S; ++i)
              {
                // Process each bacterium
              }
              ++t;
             }
            // Reproduce healthiest bacteria, eliminate other half
          }
          // Eliminate-disperse
        }
        Console.WriteLine("\nBest cost found = " + bestCost.ToString("F4"));
        Console.Write("Best position/solution = ");
        ShowVector(bestPosition);
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    } // Main
    static double Cost(double[] position) { ...
}
  }
  public class Colony // Collection of Bacterium
  {
    // ...
public class Bacterium : IComparable<Bacterium>
    {
      // ...
}
  }
} // ns

我用 Visual Studio 創建 C# 主控台應用程式命名為 BacterialForagingOptimization。重命名為 BacterialForagingOptimizationProgram.cs 的 program.cs，然後從該檔，並刪除所有範本生成使用語句除外的 System 命名空間的引用。

我聲明類範圍隨機物件命名隨機； BFO 是一種概率演算法，你很快就會看到。我主要方法內聲明的幾個關鍵變數。 Dim 變數是問題中的維度數。因為在此示例中的目標是找到 x 和 y 的 Rastrigin 函數，設置 2 昏暗。 MinValue 和 maxValue 變數建立任意的 x 和 y 的限制。變數 S 是細菌的數量。我用稍有非描述性的變數名，如 S 和數控因為這些都用在研究文章中，您可以更輕鬆地的名稱使用該文章作為參考。

可變 Nc 是所謂的趨化步驟的數目。你可以把它作為一個計數器，表示每個細菌的壽命。可變 Ns 是一種細菌會游在同一方向的最大次數。可變 Nre 是複製步驟的數目。你能想到的這代的細菌的數量。可變 Ned 是散佈步驟的數目。現在然後 BFO 演算法隨機散至新的位置，類比真實的細菌對外部環境的影響的一些細菌。可變 Ped 是細菌的特定被分散的概率。可變 Ci 是基本游泳長度為每個細菌。時游泳、細菌將 Ci 不超過任何一個步驟。變數 t 是時間計數器跟蹤 BFO 進度。因為 BFO 是相對較新，非常瞭解甚少使用 BFO 參數的值不同的影響。

主要的 BFO 演算法處理包括幾個嵌套迴圈。不像大多數的人工智慧演算法如由單個時間計數器控制的遺傳演算法，BFO 是由多個迴圈計數器控制的。

程式使用靜態的成本函數。這是你想的最小化或最大化的功能。在此示例中成本函數是剛剛的 Rastrigin 函數。輸入是陣列的兩倍，代表一種細菌的位置，它反過來表示可能的解決方案。在此示例中成本函式定義如下：

double result = 0.0;
for (int i = 0; i < position.Length; ++i) {
  double xi = position[i];
  result += (xi * xi) - (10 * Math.Cos(2 * Math.PI * xi)) + 10;
}
return result;

你可以通過互聯網搜索，找到有關 Rastrigin 函數的詳細資訊，但問題是成本函數接受一種細菌的位置，並返回的值，你想最小化或最大化。

細菌和殖民地的類

BFO 程式定義的殖民地類，該類的細菌的集合，使用嵌套的細菌類，定義單個細菌。嵌套的細菌類列在圖 4。

圖 4 細菌類

public class Bacterium : IComparable<Bacterium>
{
  public double[] position;
  public double cost;
  public double prevCost;
  public double health;
  static Random random = new Random(0);
  public Bacterium(int dim, double minValue, double maxValue)
  {
    this.position = new double[dim];
    for (int p = 0; p < dim; ++p) {
      double x = (maxValue - minValue) * random.NextDouble() + minValue;
      this.position[p] = x;
    }
    this.health = 0.0;
  }
  public override string ToString()
  {
    // See code download
  }
  public int CompareTo(Bacterium other)
  {
    if (this.health < other.health)
      return -1;
    else if (this.health > other.health)
      return 1;
    else
      return 0;
  }
}

類細菌源自 IComparable 介面，以便確定哪些細菌會生存的下一代時，可以按他們的健康排序細菌的兩個物件。

位置欄位表示一個解決方案。成本域是與位置相關的成本。欄位的 prevCost 是一種細菌先前的立場；與相關的成本這樣一種細菌，知道如果它提高與否，而且因此是否應游泳或滾落。衛生領域的細菌壽命期間的一種細菌的累積成本的總和。因為目標是儘量減少成本，健康的小值都優於較大的值。

細菌的構造函數初始化一個細菌的物件，以隨機的位置。構造函數不是顯式設置成本域。 CompareTo 方法訂單最大健康的細菌物件從最小的健康。

圖 5 顯示簡單的殖民地類。

圖 5 的殖民地類

public class Colony
{
  public Bacterium[] bacteria;
  public Colony(int S, int dim, double minValue, double maxValue)
  {
    this.bacteria = new Bacterium[S];
    for (int i = 0; i < S; ++i)
      bacteria[i] = new Bacterium(dim, minValue, maxValue);
  }
  public override string ToString() { // See code download }
  public class Bacterium : IComparable<Bacterium>
  {
    // ...
}
}

殖民地類是本質上是細菌的物件的集合。殖民地的構造函數創建的細菌，其中每個細菌分配的隨機位置通過細菌的構造函式呼叫的集合。

該演算法

設置了 S 和數控，BFO 演算法等 BFO 變數初始化後這種細菌菌落像這樣：

Console.WriteLine("\nInitializing bacteria colony");
Colony colony = new Colony(S, dim, minValue, maxValue);
for (int i = 0; i < S; ++i) {
  double cost = Cost(colony.bacteria[i].position);
  colony.bacteria[i].cost = cost;
  colony.bacteria[i].prevCost = cost;
}
...

由於成本函數是外部的殖民地，細菌的每個物件的成本以外使用成本函數的殖民地構造函數設置。

初始化之後，確定在香港最好的細菌，牢記更低的成本比更高的成本最小化的 Rastrigin 功能的情況下：

double bestCost = colony.bacteria[0].cost;
int indexOfBest = 0;
for (int i = 0; i < S; ++i) {
  if (colony.bacteria[i].cost < bestCost) {
    bestCost = colony.bacteria[i].cost;
    indexOfBest = i;
  }
}
double[] bestPosition = new double[dim];
colony.bacteria[indexOfBest].position.CopyTo(bestPosition, 0);
Console.WriteLine("\nBest initial cost = " + bestCost.ToString("F4"));
...

下一步，設置的主要 BFO 處理的多個環：

Console.WriteLine("\nEntering main BFO algorithm loop\n");
int t = 0;
for (int l = 0; l < Ned; ++l)
{
  for (int k = 0; k < Nre; ++k)
  {
    for (int j = 0; j < Nc; ++j)
    {
      for (int i = 0; i < S; ++i) { colony.bacteria[i].health = 0.0; }
      for (int i = 0; i < S; ++i) // Each bacterium
      {
        ...

與索引 l 的外層迴圈處理擴散的步驟。與索引 k 的 next 迴圈處理複製的步驟。與索引 j 第三迴圈處理的趨化的步驟，表示每個細菌的壽命。此趨化迴圈一代新的細菌已只生成，因此每個細菌的健康重置為 0。後重置細菌健康值趨化迴圈，每個細菌內跌倒，確定一個新的方向和新的方向，然後移動如下所示：

double[] tumble = new double[dim];
for (int p = 0; p < dim; ++p) {
  tumble[p] = 2.0 * random.NextDouble() - 1.0;
}
double rootProduct = 0.0;
for (int p = 0; p < dim; ++p) {
  rootProduct += (tumble[p] * tumble[p]);
}
for (int p = 0; p < dim; ++p) {
  colony.bacteria[i].position[p] += (Ci * tumble[p]) / rootProduct;
}
...

第一，每個元件的當前細菌的位置，生成-1.0 和 +1.0 之間的隨機值。然後計算結果向量的根產品。並通過以舊位置和移動有小部分的 Ci 變數的值然後計算細菌的新位置。

後翻筋斗，更新當前細菌和細菌然後檢查以查看是否它找到一個新的全球最佳解決方案：

colony.bacteria[i].prevCost = colony.bacteria[i].cost;
colony.bacteria[i].cost = Cost(colony.bacteria[i].position);
colony.bacteria[i].health += colony.bacteria[i].cost;
if (colony.bacteria[i].cost < bestCost) {
  Console.WriteLine("New best solution found by bacteria " + i.ToString()
    + " at time = " + t);
  bestCost = colony.bacteria[i].cost;
  colony.bacteria[i].position.CopyTo(bestPosition, 0);
}
...

下一步，這種細菌進入游泳迴圈哪裡它會游在同一方向，只要它提高通過找到更好的位置：

int m = 0;
    while (m < Ns && colony.bacteria[i].cost < colony.bacteria[i].prevCost) {
      ++m;
      for (int p = 0; p < dim; ++p) {
        colony.bacteria[i].position[p] += (Ci * tumble[p]) / rootProduct;
      }
      colony.bacteria[i].prevCost = colony.bacteria[i].cost;
      colony.bacteria[i].cost = Cost(colony.bacteria[i].position);
      if (colony.bacteria[i].cost < bestCost) {
        Console.WriteLine("New best solution found by bacteria " +
          i.ToString() + " at time = " + t);
        bestCost = colony.bacteria[i].cost;
        colony.bacteria[i].position.CopyTo(bestPosition, 0);
      }
    } // while improving
  } // i, each bacterium
  ++t;   // increment the time counter
} // j, chemotactic loop
...

可變 m 是游泳計數器限制 Ns 變數中的值相同的方向連續游泳的最大數目。游完泳後, 時間計數器遞增和趨化迴圈終止。

在這一點上，所有的細菌都住了他們的壽命的數控和蟻群的最健康的一半將生活和將死，最不健康的一半：

Array.Sort(colony.bacteria);
  for (int left = 0; left < S / 2; ++left) {
    int right = left + S / 2;
    colony.bacteria[left].position.CopyTo(colony.bacteria[right].position, 0);
    colony.bacteria[right].cost = colony.bacteria[left].cost;
    colony.bacteria[right].prevCost = colony.bacteria[left].prevCost;
    colony.bacteria[right].health = colony.bacteria[left].health;
  }
} // k, reproduction loop
...

因為細菌物件派生自 IComparable，Array.Sort 方法會自動排序，從最小的健康（以較小是更好），所以最好的細菌都是左的 S/2 細胞集落陣列的最大的健康。蟻群的合適的細胞中細菌的弱半有效地被殺的好的一半的細菌陣列的資料複製到較弱的右半部分。請注意，這意味著細菌，S，總人數應被 2 整除的數。

此時的趨化作用和繁殖的環路已完工，所以 BFO 演算法進入分散相：

for (int i = 0; i < S; ++i) {
    double prob = random.NextDouble();
    if (prob < Ped) {
      for (int p = 0; p < dim; ++p) {
        double x = (maxValue - minValue) *
          random.NextDouble() + minValue;
        colony.bacteria[i].position[p] = x;
      }
      double cost = Cost(colony.bacteria[i].position);
      colony.bacteria[i].cost = cost;
      colony.bacteria[i].prevCost = cost;
      colony.bacteria[i].health = 0.0;
      if (colony.bacteria[i].cost < bestCost) {
        Console.WriteLine("New best solution found by bacteria " +
          i.ToString() + " at time = " + t);
        bestCost = colony.bacteria[i].cost;
        colony.bacteria[i].position.CopyTo(bestPosition, 0);
      }
    } // if (prob < Ped)
  } // for
} // l, elimination-dispersal loop
...

檢查每個細菌。一個隨機值生成和可變 Ped 確定如果當前細菌將被移動到任意位置進行比較。如果一種細菌事實上分散的它檢查它是否找到新的全球最佳位置純粹是偶然機會。

此時所有環已被執行都死刑，BFO 演算法顯示使用一個名為 ShowVector 的程式定義的説明器方法找到最佳的解決方案：

Console.WriteLine("\n\nAll BFO processing complete");
    Console.WriteLine("\nBest cost (minimum function value) found = " +
      bestCost.ToString("F4"));
    Console.Write("Best position/solution = ");
    ShowVector(bestPosition);
    Console.WriteLine("\nEnd BFO demo\n");
  }
  catch (Exception ex)
  {
    Console.WriteLine("Fatal: " + ex.Message);
  }
} // Main
...

點是什麼？

BFO 是一種近似解決不能使用傳統的數學技術處理的數值優化問題的相對較新方法。在我看來，BFO 是遺傳演算法與粒子群優化的替代方法。有小研究證據來回答問題的只是如何有效 BFO 是或不是。

BFO 可能會如何使用？有很多可能性相關軟體測試，並優化一般。例如，假設你想預測某事很困難，如一些在紐約證交所的股票價格的短期變化。收集的一些歷史資料，並就一些複雜的數學方程與股票價格有關您的輸入資料，但您需要確定您的方程的參數。您可能有可能使用 BFO 估計您的參數的值成本函數在哪裡你方程所作的不正確預測的百分比。

BFO 是 meta-heuristic，意味著它只是一個概念框架，可以用於設計特定的演算法。我在這裡已經給出了的 BFO 的版本只是許多可能性的一，應考慮實驗，而不是主題最終決定權的起點。事實上，為了使這篇文章的大小易於管理，刪除群集功能所提出的原始 BFO 研究文章的細菌。

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

多虧了以下的技術專家審查這篇文章：Paul Koch， Dan Liebling， Anne Loomis Thompson 和 Shane Williams