How to find the food(chance, weak ties, risk .etc)—螞蟻演算法
Sciscape新聞:http://www.sciscape.org/news_detail.php?news_id=146
原文網站:Bonabeau, E., Dorigo, M. & Theraulaz, G. Inspiration for optimization from social insect behaviour. Nature 406, 39-42 (2000)
e蟻雄兵
誰說大腦發達的生物才聰明?頭腦簡單的螞蟻不但能建構驚人的地下蟻城,還將掀起一場人類電腦科技革命!
在「人不為己,天誅地滅」的天擇鐵律下,螞蟻、蜜蜂、甚至一些細菌卻選擇以相互合作為其生存策略。群體中每個個體僅執行一項動作,並針對外在情況做出簡單幾種反應。這種看似笨拙的行為卻使由動輒數萬隻個體組成的群體能極有效率的行動,甚至能表現某種程度的思考。現在這種生存行為模式已經成為科學家與工程師所師法的對象,在解決一些繁瑣的運算問題時,在電腦程式中放進一群虛擬的「螞蟻」,便能有效率的尋求最佳解答。
螞蟻是高度社會化的群體動物。當工蟻在巢穴外隨意地覓食時,發現食物的工蟻必須返回巢穴通知其他工蟻,而它的同伴們則必須跟隨它沿路留下的費洛蒙氣味,回到食物的地點。但是原先這隻工蟻所走的路徑可能並非最短路徑,其他的工蟻可能也跟著走冤枉路。所幸其他較便捷的路徑可能很快就由其他工蟻發現,並留下新的氣味以便友伴跟隨,這麼一來,蟻群便有可能找出通往食物的最短路徑。
這種解決問題的模式提供了專門解決繁瑣運算問題的電腦工程師們新的靈感。美國新墨西哥州聖塔菲研究所的Eric Bonabeau與其同僚在「自然」科學期刊上發表了這種新的電腦運算法。它的內容簡單的說,就是將所有可能的解算列出,再由電腦中的虛擬蟻群找出最佳答案:一個典型的例子就是一個推銷員如何以最短旅程造訪地圖上所有城鎮。電腦模擬一群出巢的螞蟻尋找目標,每隻虛擬螞蟻還會在它的運算路徑中留下「虛擬費洛蒙」,標示該路徑的長短。短的解算路徑比長的能夠吸引更多虛擬螞蟻:運算迴路中的虛擬費洛蒙也會以特定速率”蒸發”,以避免虛擬蟻群陷入次佳的解算路徑。研究人員稱這種運算為蟻群最佳化運算法(Ant Colony Optimization (ACO) algorithm)。現在ACO正被運用在計算瑞士運油卡車的運輸途徑。
真實的蟻群常常在開放的區域尋覓食物或標的:網路工程師們發現這種社會性昆蟲的特性也可運用在網路世界中。虛擬蟻群會穿梭在電腦網路中,標示最佳的通訊路徑:當遭遇網路壅塞的狀況時,這條路徑便不會被採用,而且替代的路徑很快便被找出。這種蟻群運算法有很高的彈性,而且能針對不同情形做出反應。英國電訊(British Telecom)目前正根據此一原理發展新的網路系統。
這種蟻群思考模式將來極有可能會應用在機器人的設計上:機器人將由共同運作的簡單操作元件組成:數量龐大的微機器人 (micro-robots)將比單一設計複雜的機器人更能有效執行任務,而且製造成本也會大幅降低,預料這種師法螞蟻雄兵的思考方式,將帶動新一波的科技革命。
本人閱讀心得^0^:
在六個人的小世界中的第一章有提到美國西部電路系統的故障事件,其發生的原因是來自於對於系統的相互依賴性,存在著錯誤的評估與了解,所以如何在複雜的網路中有效的預防個體負荷過重的問題,和避免無心的造成整體的連鎖崩潰變成為了非常重要的課題;「個別行為如何集結成群體行為」也正意味著不只是整個母體是動態演化著,連最微小的一個分子也是動態的,所以在傳輸資料的工具開發上,除了要有效的檢測這些看似不起眼的分子(如流量)變化,也要保持相當的彈性與效率,而從這篇文章我偶然的發現到原來螞蟻演算法可以同時一窩蜂的進行地毯式的搜索,並且適當的選擇沒有雍塞的路徑行走,從解決這樣的問題出發,相信可以有效地避免突破系統流量的承受臨界點的情形發生。
在small world的議題上,我們可以知道機會(如工作機會)往往皆發生在遠端的連結當中,而且這樣的連結是非常微弱的,又稱為弱連結,不同於上一段落,以另一個觀點出發,我們該如何彈性且有效的從C大L小的small world中取得對我們有所價值的資訊呢?針對此觀點希望能在網路上蒐集到是否能以螞蟻演算法這樣的搜尋工具找出跟發現弱連結有關的文章,我發現相關的資料少的可憐=.=,也可以說幾乎是沒有,因為我知道k<<N,當N非常大時,要藉此找到一個optimum的解勢必要花上非常多的時間,縱使派出非常多的螞蟻雄兵。
而當系統範圍是可以掌握的時候,我覺得可以期待的焦點便是設定費洛蒙的function了,費洛蒙的強度會隨著時間而慢慢的減弱,除非持續地有螞蟻經過,這剛好驗證了馬太效應(Matthew effect),再加上如果適當的將二分網路所投射出的群組交疊網路與角色派系網路來設定pheromone function,這樣就可以使得蟻群們保留適當的數量朝著可能發生弱連結的地方(網路社群的媒介點、轉接點)搜尋,便能降低落到區域解的可能性。
其他參考資料:
仿螞群的最佳化網路資源收集技術&群體螞蟻覓食行為模擬
http://140.115.11.235/~chen/talk/2000-05-26/5-3/5-3.htm
螞蟻演算法運用於推銷員問題(CH5的部份)
http://wayne.cs.nthu.edu.tw/~roland/nn/index2c.html
Previous in This Category: 弱連結(Weak Ties) Next in This Category: weak ties, strong ties v.s. 疾病的傳播

Sealed (Dec 9)