蟻群算法ACO

這次要介紹的蟻群算法(Ant colony Algorithm)卻是一種源於自然現象的算法，也是一種 meta heuristic，即與具體問題關係不大的最佳化算法，也就是它是一種用來在圖中尋找最佳化路徑的機率型技術。Marco Dorigo於1992年在他的博士論文中引入，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。

小小的螞蟻總是能夠找到食物，他們具有什麼樣的智慧型呢？構想，如果我們要為螞蟻設計一個人工智慧的程式，那么這個程式要多么複雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據適當的地形給它編進指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點；再次，如果要讓螞蟻找到最短的路徑，那么需要計算所有可能的路徑並且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因為程式的錯誤也許會讓你前功盡棄。這是多么不可思議的程式！太複雜了，恐怕沒人能夠完成這樣繁瑣冗餘的程式。
為什麼這么簡單的程式會讓螞蟻幹這樣複雜的事情？答案是：簡單規則的湧現。事實上，每隻螞蟻並不是像我們想像的需要知道整個世界的信息，他們其實只關心很小範圍內的眼前信息，而且根據這些局部信息利用幾條簡單的規則進行決策，這樣，在蟻群這個集體裡，複雜性的行為就會凸現出來。這就是人工生命、複雜性科學解釋的規律！
下面就是實現如此複雜性的七條簡單規則：

1、範圍：

螞蟻觀察到的範圍是一個方格世界，螞蟻有一個參數為速度半徑（一般是3），那么它能觀察到的範圍就是3*3個方格世界，並且能移動的距離也在這個範圍之內。

2、環境：

螞蟻所在的環境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它範圍內的環境信息。環境以一定的速率讓信息素消失。

3、覓食規則：

在每隻螞蟻能感知的範圍內尋找是否有食物，如果有就直接過去。否則看是否有信息素，並且比較在能感知的範圍內哪一點的信息素最多，這樣，它就朝信息素多的地方走，並且每隻螞蟻多會以小機率犯錯誤，從而並不是往信息素最多的點移動。螞蟻找窩的規則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。

4、移動規則：

每隻螞蟻都朝向信息素最多的方向移，並且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，並且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉圈，它會記住最近剛走過了哪些點，如果發現要走的下一點已經在最近走過了，它就會儘量避開。

5、避障規則：

如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，並且有信息素指引的話，它會按照覓食的規則行為。

6、播撒信息素規則：

每隻螞蟻在剛找到食物或者窩的時候撒發的信息素最多，並隨著它走遠的距離，播撒的信息素越來越少。
下面的程式開始運行之後，螞蟻們開始從窩裡出動了，尋找食物；他們會順著螢幕爬滿整個畫面，直到找到食物再返回窩。
其中，‘F’點表示食物，‘H’表示窩，白色塊表示障礙物，‘+’就是螞蟻了。
參數說明：
最大信息素：螞蟻在一開始擁有的信息素總量，越大表示程式在較長一段時間能夠存在信息素。信息素消減的速度：隨著時間的流逝，已經存在於世界上的信息素會消減，這個數值越大，那么消減的越快。
錯誤機率表示這個螞蟻不往信息素最大的區域走的機率，越大則表示這個螞蟻越有創新性。
速度半徑表示螞蟻一次能走的最大長度，也表示這個螞蟻的感知範圍。
記憶能力表示螞蟻能記住多少個剛剛走過點的坐標，這個值避免了螞蟻在本地打轉，停滯不前。而這個值越大那么整個系統運行速度就慢，越小則螞蟻越容易原地轉圈。