[Term Project]螞蟻演算法

"一、何謂螞蟻演算法?
  螞蟻演算法Ant Colony Optimization,ACO(也有人稱Ant Colony System,ACS;或者再更簡稱AC),是一種用來在圖中尋找優化路徑的機率型技術。在1992年Dorigo等人利用了螞蟻群體合作尋找食物的行為,設計出一個用於處理最佳化問題的螞蟻演算法。1996年Dorigo 將ACS演算法與GA、SA等啟發式演算法以TSPLIB國際列題進行比較,其結果皆優於其他的演算法,其結果與最佳解誤差皆小於3.5%。

 [@more@]

二、簡介
  有看過家裡常常會有螞蟻在牆壁上或是角落,排成一排,比值的從巢穴朝著食物而去?螞蟻依賴的不是視力,更不可能是他們的智慧,螞蟻們所憑藉的是牠們身上獨特的費洛蒙,靠著費洛蒙,讓許多螞蟻可以選擇到相對來說較好的路徑來行走。

    現實生活中我們不可能去預測螞蟻的複雜行為,那我們該如何利用螞蟻的特性去研究這項演算法?其實我們可以利用訂定幾項規則出來,藉以突顯螞蟻這些複雜行為中的規律,所以我們可以由這些規則,撰寫出簡單的程式碼,來控制螞蟻的行為。畢竟,我們不需要模擬螞蟻的所有行為,我們只是需要他們找尋出問題的最佳解出來罷了。

  三、訂定規則
  上面提到我們可以藉由制定一些規則來突顯、加強螞蟻行為的特色,然後就可以利用這些特徵,來撰寫出程式,那基本上我們制定規則分為兩大類。

? 路徑的選擇規則:『Pseudo-Random-Proportional Rule』
? 費洛蒙更新規則:『Online Update』、『Offline Update』

  1. 路徑的選擇規則
  在Dorigo於1997年提出的螞蟻演算法尋路規中,利用路徑選擇規則選擇路徑以縮短計算時間,而且只在最好的解增加費洛蒙的痕跡,經實驗證明,只在最好的解上增加費洛蒙的設計,確實有助於螞蟻能最快搜尋到最佳解。

  2. 費洛蒙更新規則
  螞蟻演算法中的費洛蒙更新規則也分為兩大類,一類是費洛蒙及時更新,另一類則是費洛蒙離線更新,前者用在每隻人工螞蟻走過該路徑後,後者是在該回合結束後,針對費洛蒙值做一些適度的變更。當然,這個機制不僅僅影響了接下來螞蟻做路徑選擇的決策,還對最後路徑解的好壞有著緊密的相關。

  (1)費洛蒙即時更新(Online Update)規則
  費洛蒙的濃度,顧名思義,跟路徑上的螞蟻數量成正比與此路徑的距離長度成反比。這項規則所著重的是路徑的熱門程度,也就是費洛蒙濃度對螞蟻做出選擇時的影響,並不把距離因素考慮進去。

  (2)費洛蒙離線更新(Offline Update)規則
  在該流程結束後,對於最佳路徑解,最一些費洛蒙濃度的調整、變更,這就稱為費洛蒙離線更新。同時,對其餘非最佳路徑之解做費洛蒙蒸發的動作,如此一來,在下次行程執行時,最佳路徑解被選擇的機率就會大大的增加。

  在完成規則的制定之後,螞蟻們之間都沒有什麼直接的關聯性,牠們處在這個大環境下利用散發費洛蒙來溝通。如果有一隻螞蟻找到了食物,那牠就利用走過的路徑上殘留的費洛蒙來告知他的親朋好友說『嘿!這有食物!』,那等到其他的螞蟻經過附近,發現費洛蒙的存在後,自然就會聚集在一起,想當然的,費洛蒙的濃度也就會越來越高。
  到目前為止我們都是屬於利用費洛蒙來判斷該路徑是否為最佳路徑解,那有沒有想過,第一個發現食物的螞蟻,牠是如何找到食物的呢?這隻小螞蟻從蟻穴出發時,所有路徑費洛蒙的濃度都是一樣的,也就是說,這隻螞蟻選擇任何一條路經的機率都是相同的,既然沒有外部因素的影響,那螞蟻就基於自身本能做移動了。小螞蟻會朝著一個方向前進,但是並不是保持直線,可能會走的歪歪扭扭,有一定的隨機性,使得螞蟻運動起來具有了一定的目的性,儘量保持原來的方向,但是卻又有新的試探,尤其當碰到障礙物的時候它會立刻改變方向,這可以看成一種選擇的過程,也就是環境的障礙物讓螞蟻的某個方向正確,而其他方向則不對。這就解釋了為什麼這隻小螞蟻在複雜像迷宮的現實世界中仍然能找到隱蔽的食物。
  螞蟻演算法也可以用來解決網狀網路跳點問題,當網路流量或基地站負載改變時,透過此規劃模式背後的改良式蟻群演算機制搜尋優化路由組合,可預見的,其能力將會優於目前WiMax所使用的傳統跳點規劃方法。ACO也被應用來解許多困難的尋優問題(NP- Hard problems), 如 Traveling salesman problem, quadratic assignment problem,等…

  四、螞蟻演算法範例
  1. Initialize:
    Set t:=0              {t is the time counter}
    Set NC:=0             {NC is the cycles counter}
    For every edge (i,j) set an initial value ?ij(t)=c for trail intensity and ??ij= 0
    Place the m ants on the n nodes

  2. Set s:=1 {s is the tabu list index}
   For k:=1 to m do
    Place the starting town of the k-th ant in tabuk(s)
  3. Repeat until tabu list is full   {this step will be repeated (n-1) times}
    Set s:=s+1
    For k:=1 to m do
     Choose the town j to move to, with probability pijk (t) given by equation (4)
                   {at time t the k-th ant is on town i=tabuk(s-1)}
    Move the k-th ant to the town j
    Insert town j in tabuk(s)

  4. For k:=1 to m do
    Move the k-th ant from tabuk(n) to tabuk(1)
    Compute the length Lk of the tour described by the k-th ant
    Update the shortest tour found
   For every edge (i,j)
    For k:=1 to m do
     ??ki , j ? Q/ Lk ,if (i, j) ??tour described by tabuk
           0 ,otherwise
     ??k ij : ????ij ????ij

  5. For every edge (i,j) compute ?ij(t+n) according to equation ?ij(t+n)=?.?ij(t)+??ij
   Set t:=t+n
   Set NC:=NC+1
   For every edge (i,j) set ??ij:=0

  6. If (NC < NCMAX)
   then
    Empty all tabu lists
    Goto step 2
   else
    Print shortest tour
    Stop

    若在該演算法執行NC圈後停止,這個演算法的時間複雜度會為O(NC.n2m),事實上,步驟1 is O(n2+m),步驟2 is O(m),步驟3 is O(n2.m),步驟4 is O(n2.m),步驟5 is O(n2),步驟6 is O(n.m)。既然已經利用實驗找到蟻穴跟螞蟻數量的線性關係,所以該演算法的時間複雜度為??NC.n3)。

  旅行推銷員問題 (TSP)
  一地區有若干的城市,城市之間都有道路相連,但卻有長短之分,有一位推銷員從某一城市出發,途中須經過所有城市,最後回到原點,問這位推銷員要怎麼走,才能讓這條路徑最短?
  Loop
    randomly position num_ants on nun_city cities
       for step=1 to run  city
          for k=1 to run ant
             Choose the next city to move to applying
             a probabilistic state transition rule
          end for
       end for
    Up date pheromone trails
  Until End_condition

  五、結論與心得
  這次演算法的期末專題,我選擇『螞蟻演算法』作為題目,了解了這個演算法的名字的由來、它是如何執行、它可以解決哪些問題,等…讓我對演算法這門課也多了解一點,雖然這學期以來,在小考以及作業部分大家還是互相cover的機會比較多。等到過了這學期之後,至少大家也都有了trace程式碼、解決問題的能力。我們也知道,演算法課程學到的許多方法,不僅僅只是應用在程式方面,現實生活中也可以利用演算法來幫你解決問題。
  這份報告真的事千呼萬喚始出來,其實我在前一天就已經把這份報告完成的差不多了,只剩後面一點點的心得跟程式碼的部分,經過兩小時我完成之後,我開開心新的整理桌面,刪除我的參考資料,我不曉得是眼花還是手殘,我竟然把我的成品直接用shift + delete刪掉了,我又花了很長的時間去找拯救檔案的軟體來試,final data和Drive Rescue不過竟然只找的到我的暫存檔,十分的不甘願下,我只好重做一份了。所以我對螞蟻演算法真的是有很深的體驗啊!

  六、參考資料
  http://eca2.mis.au.edu.tw/check/paper/GA3/GA3_5.doc
  http://en.wikipedia.org/wiki/Ant_colony_optimization
  http://iridia.ulb.ac.be/~mdorigo/ACO/about.html
  螞蟻演算法.pdf
  好用的google & yahoo知識+

"