測試運行

發行項
07/23/2015

蟻群最佳化

在本月的專欄中，我介紹 C# 代碼實現螞蟻蟻群優化（ACO）演算法解決旅行商問題 (TSP)。蟻群優化演算法是一種基於資訊素鋪設的螞蟻；行為的人工智慧技術它可以用於尋求通過圖形的最優路徑的極其複雜的問題找到解決辦法。看到我朝哪裡最好是看一看在截圖圖 1。在此情況下，該演示求解 TSP 的實例訪問 60 城市的每一次的最短路徑的目標。演示計畫使用四個螞蟻；每只螞蟻表示可能的解決方案。蟻群演算法需要幾個參數如資訊素影響因數（alpha）和資訊素的蒸發係數（rho），後面會講的規範。四個螞蟻被初始化為隨機徑進行 60 的城市；初始化之後，最佳的螞蟻的最短徑長度為 245.0 單位。蟻群優化的關鍵點是類比資訊素，這吸引到更好的創新，通過該圖形的螞蟻的使用。主要加工迴圈之間交替更新基於資訊素的當前值的螞蟻跟蹤和更新基於 ant 創新的資訊素。最大數目 (1000) 倍通過主要加工迴圈後，程式將顯示找到的最好的線索和其相應的長度（61.0 單位）。

60 城市圖是人工建造這種連接到每個其他城市，每個城市，任何兩個城市之間的距離 1.0 和 8.0 任意單元 (英里、公里等等）之間的隨機值。沒有解決 TSP 的簡便方法。60 城市，假設你可以在任何城市和 go 向前或向後，啟動並連接所有的城市，有共 (60-1）！/ 2 = 69,341,559,272,844,917,868,969,509,860,194,703,172,951,438,386,343,716,270,410,647,470,080,000,000,000,000 可能的解決方案。即使您可以評估每秒 1 億可能的解決辦法，才會約 2.2 ＊ 1063 年檢查它們所有的情況下，這是宇宙的估計年齡比長很多倍。

蟻群優化是 meta-heuristic，這意味著它一個可以用來創建特定的演算法，以解決特定圖形路徑問題的一般框架。雖然蟻群優化 1991年博士論文中提出 M。多裡戈演算法的第一次詳細說明通常被由於 1996 年的後續論文萬。多裡戈 VManiezzo 和 a。科洛爾尼。自那時以來，蟻群優化廣泛研究和修改，但是，有點奇怪的是，很少有的完整和正確實現可連線使用。

此列假定您擁有中級高級程式設計技能。我實現使用 C# 的蟻群優化程式，但你不應該有太多的麻煩，我以不同的語言，例如，JavaScript 代碼重構。我決定，避免所有使用物件導向的程式設計 (OOP) 保持盡可能清晰的演算法的想法。由於空間的限制，我不能提交所示中運行的代碼的所有圖 1。我將會在最棘手的部分，你可以下載完整的代碼從 archive.msdn.microsoft.com/mag201202TestRun。雖然永遠不可能直接使用蟻群優化的代碼，很多技術，例如，輪盤賭輪選擇，可以很有意思，設置你的技術的有益補充。

圖 1 蟻群優化在行動

程式結構

我作為單個 C# 主控台應用程式實現蟻群優化演示計畫。所示的程式中，大多數 WriteLine 語句刪除，整體結構圖 2。雖然某些部分棘手，但該程式並不複雜的圖 2 表明，因為許多方法都是短期的説明器方法。

圖 2 螞蟻蟻群優化程式結構

using System;

namespace AntColony
{
  class AntColonyProgram
  {
    static Random random = new Random(0);
    static int alpha = 3;
    static int beta = 2;
    static double rho = 0.01;
    static double Q = 2.0;

    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin Ant Colony Optimization demo\n");
        int numCities = 60;
        int numAnts = 4;
        int maxTime = 1000;

        int[][] dists = MakeGraphDistances(numCities);
        int[][] ants = InitAnts(numAnts, numCities); 

        int[] bestTrail = BestTrail(ants, dists);
        double bestLength = Length(bestTrail, dists);

        double[][] pheromones = InitPheromones(numCities);

        int time = 0;
        while (time < maxTime)
        {
          UpdateAnts(ants, pheromones, dists);
          UpdatePheromones(pheromones, ants, dists);
           
          int[] currBestTrail = BestTrail(ants, dists);
          double currBestLength = Length(currBestTrail, dists);
          if (currBestLength < bestLength)
          {
            bestLength = currBestLength;
            bestTrail = currBestTrail;
          }
          ++time;
        }

        Console.WriteLine("\nBest trail found:");
        Display(bestTrail);
        Console.WriteLine("\nLength of best trail found: " +
          bestLength.ToString("F1"));

        Console.WriteLine("\nEnd Ant Colony Optimization demo\n");
      }
      catch (Exception ex)
      {
        Console.WriteLine(ex.Message);
      }
    } // Main

    static int[][] InitAnts(int numAnts, int numCities) { .
.
}
    
    static int[] RandomTrail(int start, int numCities) { .
.
}
    
    static int IndexOfTarget(int[] trail, int target) { .
.
}
    
    static double Length(int[] trail, int[][] dists) { .
.
}
    
    static int[] BestTrail(int[][] ants, int[][] dists) { .
.
}
    
    static double[][] InitPheromones(int numCities) { .
.
}
    
    static void UpdateAnts(int[][] ants, double[][] pheromones,
      int[][] dists) { .
.
}
    
    static int[] BuildTrail(int k, int start, double[][] pheromones,
      int[][] dists) { .
.
}
 
    static int NextCity(int k, int cityX, bool[] visited, double[][] pheromones,
      int[][] dists) { .
.
}

    static double[] MoveProbs(int k, int cityX, bool[] visited,
      double[][] pheromones, int[][] dists) { .
.
}
    
    static void UpdatePheromones(double[][] pheromones, int[][] ants,
      int[][] dists) { .
.
}
    
    static bool EdgeInTrail(int nodeX, int nodeY, int[] trail) { .
.
}
    
    static int[][] MakeGraphDistances(int numCities) { .
.
}
    
    static double Distance(int cityX, int cityY, int[][] dists) { .
.
}
    
    static void Display(int[] trail) { .
.
}
    
    static void ShowAnts(int[][] ants, int[][] dists) { .
.
}
    
    static void Display(double[][] pheromones) { .
.
}
  }
}

我使用 Visual Studio 創建名為 AntColony 的主控台應用程式。在解決方案資源管理器視窗中我重命名預設的 program.cs，然後從檔為 AntColonyProgram.cs，其中汽車◆ 重命名專案中的單個類。已刪除所有的範本生成使用除了 System 命名空間的聲明 — — 蟻群演算法通常並不需要太多的庫支援。UpdateAnts 和 UpdatePheromones 兩種主要方法。UpdateAnts 方法調用 BuildTrail，NextCity，其中要求 MoveProbs 要求的傭工。UpdatePheromones 方法調用説明器 EdgeInTrail，其中要求 IndexOfTarget。

我聲明類範圍隨機物件命名隨機。蟻群優化演算法的概率為您很快就會看到。類範圍變數 α、 β、 rho 和 Q 控制蟻群優化演算法的行為。我使用這些變數的名稱，因為它們被用在原始描述的蟻群優化。

設置問題

我使用 MakeGraphDistances 方法人工圖設置：

static int[][] MakeGraphDistances(int numCities)
{
  int[][] dists = new int[numCities][];
  for (int i = 0; i < dists.Length; ++i)
    dists[i] = new int[numCities];
  for (int i = 0; i < numCities; ++i)
    for (int j = i + 1; j < numCities; ++j) {
      int d = random.Next(1, 9); // [1,8]
      dists[i][j] = d; dists[j][i] = d;
    }
  return dists;
}

為真實世界圖的問題，您可能會讀圖-鄰接和距離之間節點的資料，從文字檔，在一定的資料結構。在這裡我通過創建陣列的陣列，其中的行索引，我代表從城市和列索引 j 代表到市類比圖。通知所有城市都相連，距離不對稱，從一個城市到本身的距離為 0。

一旦我有可以為遠端方法的距離資料結構：

static double Distance(int cityX, int cityY, int[][] dists)
{
  return dists[cityX][cityY];
}

為了儘量減少提交的代碼量，省略掉正常的錯誤檢查，例如，確保的 cityX 和 cityY 參數有效。

啟動螞蟻和資訊素

在非 OOP 的實現中，一隻螞蟻是只代表的步道或路徑，從最初的城市，通過所有其他城市的 int 值的陣列。螞蟻的集合是陣列的陣列中的第一個索引指示螞蟻：

static int[][] InitAnts(int numAnts, int numCities)
{
  int[][] ants = new int[numAnts][];
  for (int k = 0; k < numAnts; ++k) {
    int start = random.Next(0, numCities);
    ants[k] = RandomTrail(start, numCities);
  }
  return ants;
}

初始化方法為每只螞蟻的線索分配行、拿一個隨機啟動城市，然後調用 RandomTrail 的説明器方法：

static int[] RandomTrail(int start, int numCities)
{
  int[] trail = new int[numCities];
  for (int i = 0; i < numCities; ++i) { trail[i] = i; }

  for (int i = 0; i < numCities; ++i) {
    int r = random.Next(i, numCities);
    int tmp = trail[r]; trail[r] = trail[i]; trail[i] = tmp;
  }

  int idx = IndexOfTarget(trail, start);
  int temp = trail[0]; trail[0] = trail[idx]; trail[idx] = temp;

  return trail;
}

RandomTrail 説明器分配一個跟蹤，並將它初始化為 0、 1、 2、... numCities-1。下一步，該方法使用費雪耶茨無序播放演算法隨機化的步道城市秩序。指定的起始城市然後找到並換入位置跟蹤 [0]。

資訊素是化學品螞蟻地方對其跟蹤資訊；他們吸引其他螞蟻。更多的螞蟻將較短的路線前往食物來源 — — 和存放更多的資訊素 — — 比上更長時間的跟蹤資訊。隨著時間的推移慢慢蒸發資訊素。這裡是 InitPheromones 的方法：

static double[][] InitPheromones(int numCities)
{
  double[][] pheromones = new double[numCities][];
  for (int i = 0; i < numCities; ++i)
    pheromones[i] = new double[numCities];
  for (int i = 0; i < pheromones.Length; ++i)
    for (int j = 0; j < pheromones[i].Length; ++j)
      pheromones[i][j] = 0.01;
  return pheromones;
}

資訊素的資訊存儲在哪裡行索引一陣列的陣列樣式對稱矩陣是從城市和列索引 j 是到城市。所有值最初都設置為任意的小值 (0.01) 跳開始 UpdateAnts UpdatePheromones 週期。

更新螞蟻

蟻群優化演算法的關鍵是通過構建一個新的更新每個螞蟻和跟蹤的過程 — — 我們希望更好地 — — 基於資訊素和距離資訊的線索。看看圖 3。假設我們有小的圖的只是五個城市。在圖 3 正在建設中的一隻螞蟻的新線索。古道啟動市 1，然後去城市 3，並更新演算法的確定下一個城市。現在假設資訊素和距離資訊是在圖像中所示。在確定下一個城市的第一步構建一個陣列，我打過電話"taueta"（因為原始研究論文用希臘字母頭和 eta)。Taueta 值是 alpha 的冪，時間超過 beta 冪的距離值之一的邊緣資訊素值。阿爾法和貝塔都必須指定的全域常量的召回。在這裡，我會認為 alpha 是 3，測試版是 2。市 1 和 3 市的 taueta 值並不是因為他們已經在當前徑計算的。注意到資訊素較大的值增加 taueta，但更遠的距離減少 taueta。

圖 3 更新的蟻群資訊

計算所有的 taueta 值之後下, 一步是將這些值轉換為概率並將它們放置在陣列中我所稱的 probs。該演算法 taueta 的值，在此示例中，獲取 82.26 求和，然後將每個 taueta 的值除以總和。在這一點上，城市 0 有 0.09 等被選中的概率。接下來，該演算法需要選擇基於計算概率的下一個城市。正如我剛才所說，我這篇文章中提出的蟻群優化演算法使用一種稱為輪盤賭輪選擇整潔技術。我建造一個增強的陣列，稱為 cumul，持有累積概率。增強的陣列的大小是大於 probs 陣列中，並 [0] 細胞播種了 0.0。在 cumul 中的每個儲存格是累積概率的總和。Cumul 陣列已落成後，將生成 0.0 和 1.0 之間的亂數字 p。假設 p = 0.538，如圖所示。那個 p 值介於在值 [2] 和 [3] 在 cumul 陣列中，這意味著，[2]，或城市 2，被選定為下一個城市。

名為 UpdateAnts 的更新頂級的方法：

static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists)
{
  int numCities = pheromones.Length; 
  for (int k = 0; k < ants.Length; ++k) {
    int start = random.Next(0, numCities);
    int[] newTrail = BuildTrail(k, start, pheromones, dists);
    ants[k] = newTrail;
  }
}

請注意每只螞蟻都分配一個新的、隨機的起始城市而不是保留舊啟動城市。如中所示，大部分的實際工作由説明器方法 BuildTrail， 圖 4。

圖 4 BuildTrail 方法

static int[] BuildTrail(int k, int start, double[][] pheromones,
  int[][] dists)
{
  int numCities = pheromones.Length;
  int[] trail = new int[numCities];
  bool[] visited = new bool[numCities];
  trail[0] = start;
  visited[start] = true;
  for (int i = 0; i < numCities - 1; ++i) {
    int cityX = trail[i];
    int next = NextCity(k, cityX, visited, pheromones, dists);
    trail[i + 1] = next;
    visited[next] = true;
  }
  return trail;
}

BuildTrail 維護訪問過的布林值陣列，以便創建的跟蹤並不包含重複的城市。在跟蹤 [0] 價值播種了一個開始的城市，然後每個城市的説明器方法 NextCity，所示添加反過來圖 5。

圖 5 NextCity 方法

static int NextCity(int k, int cityX, bool[] visited,
  double[][] pheromones, int[][] dists)
{
  double[] probs = MoveProbs(k, cityX, visited, pheromones, dists);

  double[] cumul = new double[probs.Length + 1];
  for (int i = 0; i < probs.Length; ++i)
    cumul[i + 1] = cumul[i] + probs[i];

  double p = random.NextDouble();

  for (int i = 0; i < cumul.Length - 1; ++i)
    if (p >= cumul[i] && p < cumul[i + 1])
      return i;
  throw new Exception("Failure to return valid city in NextCity");
}

NextCity 方法實現輪盤賭輪選擇演算法。請注意，該演算法將失敗，如果 cumul 陣列中的最後一個值大於（可能是由於需要舍入錯誤），1.00，所以您可能要添加邏輯以始終設置 cumul [cumul。長度 1] 為 1.00。 NextCity 要求生產的説明器方法 MoveProbs，所示的概率的陣列圖 6。

圖 6 MoveProbs 方法

static double[] MoveProbs(int k, int cityX, bool[] visited,
  double[][] pheromones, int[][] dists)
{
  int numCities = pheromones.Length;
  double[] taueta = new double[numCities];
  double sum = 0.0;
  for (int i = 0; i < taueta.Length; ++i) {
    if (i == cityX)
      taueta[i] = 0.0; // Prob of moving to self is zero
    else if (visited[i] == true)
      taueta[i] = 0.0; // Prob of moving to a visited node is zero
    else {
      taueta[i] = Math.Pow(pheromones[cityX][i], alpha) *
        Math.Pow((1.0 / Distance(cityX, i, dists)), beta);
      if (taueta[i] < 0.0001)
        taueta[i] = 0.0001;
      else if (taueta[i] > (double.MaxValue / (numCities * 100)))
        taueta[i] = double.MaxValue / (numCities * 100);
    }
    sum += taueta[i];
  }

  double[] probs = new double[numCities];
  for (int i = 0; i < probs.Length; ++i)
    probs[i] = taueta[i] / sum;
  return probs;
}

（如果距離值是非常大的），就可以很小的 taueta 值或非常大（如果資訊素值是大），可以產生困難的演算法。為處理這問題，我檢查 taueta 的值，並施加任意的最小和最大值。

更新資訊素

正在更新資訊素的資訊容易得多比更新螞蟻跟蹤資訊。關鍵線路的 UpdatePhermones 方法中是代碼的：

double length = Length(ants[k], dists);
double decrease = (1.0 - rho) * pheromones[i][j];
double increase = 0.0;
if (EdgeInTrail(i, j, ants[k]) == true)
  increase = (Q / length);
pheromones[i][j] = decrease + increase;

資訊素的每個值被下跌，類比蒸發，和增加，類比資訊素的存款古道上的螞蟻。減少影響是通過資訊素的當前值乘以係數小於 1.0，取決於全域參數 rho 產生的。較大的 rho 是，資訊素值越大減少。增加影響是通過添加當前螞蟻總徑長度，所占比例由全域參數 Q 的比例而產生的。Q 的較大的值增加資訊素添加的量。Ant 的當前徑上調用説明器方法 UpdatePheromones EdgeInTrail，它決定了如果兩個城市之間的一段。你可以看看這篇文章的詳細資訊代碼下載 (archive.msdn.microsoft.com/mag201202TestRun)。

接近尾聲了

我要強調有許多不同的蟻群優化；我已經給出了在這裡的版本只是一個許多可能的解決辦法。蟻群優化的宣導者已應用於廣泛的組合優化問題的演算法。其他組合的最適mization 演算法基於自然系統的行為包括類比退火 (SA)，其時我上個月（msdn.microsoft.com/magazine/hh708758)，和類比蜜蜂殖民地 (SBC)，在 2011 年 4 月專欄報導 (msdn.microsoft.com/magazine/gg983491)。每種方法都有優點和弱點。在我看來，最適合於相似貨郎擔問題，雖然 SA 和 SBC 是更好的更一般的組合優化問題，例如調度的問題蟻群優化。

蟻群優化，與自然系統，基於其他元啟發式一樣是相當敏感，您所選擇的自由的全域參數 — — 阿爾法、測試版等等。雖然已經相當多的蟻群演算法參數研究，但普遍的共識是品質的，您必須有點試驗與自由的參數，以獲得最佳的性能和解決方案。

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

多虧了以下 Microsoft 技術專家審查這篇文章： 丹利布林 和 安妮 · 梅斯 · 湯普森

共用方式為