???? 這兩天上課....老師總是提到蟻群算法....聽起來似乎很有意思......找到一篇簡介.....放在這里有興趣的朋友...參考一下........
??
???? 程序開始運行，螞蟻們開始從窩里出動了，尋找食物；他們會順著屏幕爬滿整個畫面，直到找到食物再返回窩。
???? 其中，‘F’點表示食物，‘H’表示窩，白色塊表示障礙物，‘+’就是螞蟻了。
預(yù)期的結(jié)果：
? ?各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當(dāng)一只找到食物以后，它會向環(huán)境釋放一種信息素，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物！有些螞蟻并沒有象其它螞蟻一樣總重復(fù)同樣的路，他們會另辟蹊徑，如果令開辟的道路比原來的其他道路更短，那么，漸漸，更多的螞蟻被吸引到這條較短的路上來。最后，經(jīng)過一段時間運行，可能會出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。
原理：
?為什么小小的螞蟻能夠找到食物？他們具有智能么？設(shè)想，如果我們要為螞蟻設(shè)計一個人工智能的程序，那么這個程序要多么復(fù)雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據(jù)適當(dāng)?shù)牡匦谓o它編進指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點；再次，如果要讓螞蟻找到最短的路徑，那么需要計算所有可能的路徑并且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因為程序的錯誤也許會讓你前功盡棄。這是多么不可思議的程序！太復(fù)雜了，恐怕沒人能夠完成這樣繁瑣冗余的程序。
? 然而，事實并沒有你想得那么復(fù)雜，上面這個程序每個螞蟻的核心程序編碼不過100多行！為什么這么簡單的程序會讓螞蟻干這樣復(fù)雜的事情？答案是：簡單規(guī)則的涌現(xiàn)。事實上，每只螞蟻并不是像我們想象的需要知道整個世界的信息，他們其實只關(guān)心很小范圍內(nèi)的眼前信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進行決策，這樣，在蟻群這個集體里，復(fù)雜性的行為就會凸現(xiàn)出來。這就是人工生命、復(fù)雜性科學(xué)解釋的規(guī)律！那么，這些簡單規(guī)則是什么呢？下面詳細說明：
1、范圍：
? ?螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內(nèi)。
2、環(huán)境：
? ?螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。
3、覓食規(guī)則：
? ?在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻多會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。
4、移動規(guī)則：
? ?每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住最近剛走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經(jīng)在最近走過了，它就會盡量避開。
5、避障規(guī)則：
? ?如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。
7、播撒信息素規(guī)則：
? ?每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。
? ?根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關(guān)聯(lián)起來了。比如，當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過它附近的時候，就會感覺到信息素的存在，進而根據(jù)信息素的指引找到了食物。
問題：
? ? 說了這么多，螞蟻究竟是怎么找到食物的呢？
? ?在沒有螞蟻找到食物的時候，環(huán)境沒有有用的信息素，那么螞蟻為什么會相對有效的找到食物呢？這要歸功于螞蟻的移動規(guī)則，尤其是在沒有信息素時候的移動規(guī)則。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動（開始，這個前方是隨機固定的一個方向），而不是原地?zé)o謂的打轉(zhuǎn)或者震動；其次，螞蟻要有一定的隨機性，雖然有了固定的方向，但它也不能像粒子一樣直線運動下去，而是有一個隨機的干擾。這樣就使得螞蟻運動起來具有了一定的目的性，盡量保持原來的方向，但又有新的試探，尤其當(dāng)碰到障礙物的時候它會立即改變方向，這可以看成一種選擇的過程，也就是環(huán)境的障礙物讓螞蟻的某個方向正確，而其他方向則不對。這就解釋了為什么單個螞蟻在復(fù)雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。
? ? 當(dāng)然，在有一只螞蟻找到了食物的時候，其他螞蟻會沿著信息素很快找到食物的。
? ? 螞蟻如何找到最短路徑的？這一是要歸功于信息素，另外要歸功于環(huán)境，具體說是計算機時鐘。信息素多的地方顯然經(jīng)過這里的螞蟻會多，因而會有更多的螞蟻聚集過來。假設(shè)有兩條路從窩通向食物，開始的時候，走這兩條路的螞蟻數(shù)量同樣多（或者較長的路上螞蟻多，這也無關(guān)緊要）。當(dāng)螞蟻沿著一條路到達終點以后會馬上返回來，這樣，短的路螞蟻來回一次的時間就短，這也意味著重復(fù)的頻率就快，因而在單位時間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。也許有人會問局部最短路徑和全局最短路的問題，實際上螞蟻逐漸接近全局最短路的，為什么呢？這源于螞蟻會犯錯誤，也就是它會按照一定的概率不往信息素高的地方走而另辟蹊徑，這可以理解為一種創(chuàng)新，這種創(chuàng)新如果能縮短路途，那么根據(jù)剛才敘述的原理，更多的螞蟻會被吸引過來。
引申
? ?跟著螞蟻的蹤跡，你找到了什么？通過上面的原理敘述和實際操作，我們不難發(fā)現(xiàn)螞蟻之所以具有智能行為，完全歸功于它的簡單行為規(guī)則，而這些規(guī)則綜合起來具有下面兩個方面的特點：
1、多樣性
2、正反饋
? ?多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環(huán)，正反饋機制則保證了相對優(yōu)良的信息能夠被保存下來。我們可以把多樣性看成是一種創(chuàng)造能力，而正反饋是一種學(xué)習(xí)強化能力。正反饋的力量也可以比喻成權(quán)威的意見，而多樣性是打破權(quán)威體現(xiàn)的創(chuàng)造性，正是這兩點小心翼翼的巧妙結(jié)合才使得智能行為涌現(xiàn)出來了。
? ? 引申來講，大自然的進化，社會的進步、人類的創(chuàng)新實際上都離不開這兩樣?xùn)|西，多樣性保證了系統(tǒng)的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得到強化，兩者要恰到好處的結(jié)合。如果多樣性過剩，也就是系統(tǒng)過于活躍，這相當(dāng)于螞蟻會過多的隨機運動，它就會陷入混沌狀態(tài)；而相反，多樣性不夠，正反饋機制過強，那么系統(tǒng)就好比一潭死水。這在蟻群中來講就表現(xiàn)為，螞蟻的行為過于僵硬，當(dāng)環(huán)境變化了，螞蟻群仍然不能適當(dāng)?shù)恼{(diào)整。
? ? 既然復(fù)雜性、智能行為是根據(jù)底層規(guī)則涌現(xiàn)的，既然底層規(guī)則具有多樣性和正反饋特點，那么也許你會問這些規(guī)則是哪里來的？多樣性和正反饋又是哪里來的？我本人的意見：規(guī)則來源于大自然的進化。而大自然的進化根據(jù)剛才講的也體現(xiàn)為多樣性和正反饋的巧妙結(jié)合。而這樣的巧妙結(jié)合又是為什么呢？為什么在你眼前呈現(xiàn)的世界是如此栩栩如生呢？答案在于環(huán)境造就了這一切，之所以你看到栩栩如生的世界，是因為那些不能夠適應(yīng)環(huán)境的多樣性與正反饋的結(jié)合都已經(jīng)死掉了，被環(huán)境淘汰了！
參數(shù)說明：
最大信息素：螞蟻在一開始擁有的信息素總量，越大表示程序在較長一段時間能夠存在信息素。信息素消減的速度：隨著時間的流逝，已經(jīng)存在于世界上的信息素會消減，這個數(shù)值越大，那么消減的越快。
錯誤概率表示這個螞蟻不往信息素最大的區(qū)域走的概率，越大則表示這個螞蟻越有創(chuàng)新性。
速度半徑表示螞蟻一次能走的最大長度，也表示這個螞蟻的感知范圍。
記憶能力表示螞蟻能記住多少個剛剛走過點的坐標，這個值避免了螞蟻在本地打轉(zhuǎn)，停滯不前。而這個值越大那么整個系統(tǒng)運行速度就慢，越小則螞蟻越容易原地轉(zhuǎn)圈。
posted on 2006-11-02 12:25
Stefanie 閱讀(2283)
評論(0) 編輯 收藏 所屬分類:
算法