0%
第十五章 人工進化 15.8 螞蟻的演算法天賦

第十五章 人工進化

15.8 螞蟻的演算法天賦

真正的螞蟻通過名為信息素的化學系統來彼此交流。螞蟻在彼此之間以及自己的環境中散發信息素。這些芳香的氣味隨著時間的推移而消散。它還能通過一連串的螞蟻來接力傳播:它們嗅到某種氣味,複製它並傳給其它螞蟻。信息素可以被看作是在螞蟻系統內部傳播或交流的信息。
義大利人用標準的旅行商問題來測試他們的螞蟻機。這個問題是這樣描述的:你需要拜訪很多城市,但每座城市只能拜訪一次,那麼哪條路徑最短?為了求解這個問題,蟻群中的每個虛擬螞蟻會動身從一座城市漫遊到另一座城市,並在沿途留下信息素的氣味。路徑越短的話,信息素揮發得越少。而信息素的信號越強,循跡而來的螞蟻就越多。那些較短的路徑由此得到自我強化。運行5000回合之後,螞蟻的群體思維就會進化出一條相當理想的路徑。
米蘭小組還嘗試了各種變化。如果虛擬螞蟻都由一座城市出發或均勻分佈在各個城市,會有什麼不同嗎?(分佈的效果要好一些。)一個回合中虛擬螞蟻的數量會有影響么?(越多越好,直到螞蟻與城市的數量比為1: 1。)通過改變參數,米九九藏書蘭小組得到了一系列螞蟻搜索演算法。
并行的愚昧的小東西能夠「寫」出比人類更好的軟體,這讓雷想到了一個能得到我們想要的并行軟體的辦法。「你看,」他說,「生態的相互作用就是并行的最優化技術。多細胞生物本質上就是在宇宙尺度上運行大規模的并行代碼。進化能夠『想出』我們窮盡一生也無法想清楚的并行編程。如果我們能夠進化軟體,那我們就能大大往前邁進一步。」對於分散式網路這類事物,雷說,「進化是最自然的編程方式。」
并行計算機所面對的挑戰是所有分散式群系統都會面對的——包括電話網路、軍事系統、全球24小時金融網路,以及龐大的計算機網路。它們的複雜性考驗著我們掌控它們的能力。「為一個大規模并行機編程的複雜度可能超過了我們的能力。」湯姆·雷對我說。「我認為我們永遠也寫不出能充分利用并行處理能力的軟體。」
自然的編程方式!這聽起來真讓人有些泄氣。人類就應該只做自己最擅長的工作:那些小而靈的、快而精的系統。讓(人工注入的)自然進化去做那些雜亂無章的大事吧。
螞蟻把分九*九*藏*書散式并行系統摸了個門清。螞蟻既代表了社會組織的歷史,也代表了計算機的未來。一個蟻群也許包含百隻萬工蟻和數百隻蟻后,它們能建起一座城市,儘管每個個體只是模模糊糊地感覺到其他個體的存在。螞蟻能成群結隊地穿過田野找到上佳食物,彷彿它們就是一隻巨大的複眼。它們排成協調的并行行列,穿行在草木之間,並共同使其巢穴保持衡溫,儘管世上從未有任何一隻螞蟻知道如何調節溫度。
米蘭小組(成員為阿爾貝托·克羅尼、馬可·多利古和維多里奧·馬涅索)按照螞蟻的邏輯構建了方程式。他們的虛擬螞蟻是一大群并行運轉的愚笨處理器。每個虛擬螞蟻有一個微不足道的記憶系統,可以進行本地溝通。如果幹得好的話,所獲得的獎賞也以一種分散式計算的方式與其他同類分享。
直到1990年,并行計算機還遭到專家們的嘲笑,認為它尚有很多地方值得商榷,過於專業,屬於狂熱派的玩物。它們結構混亂,難以編程。但狂熱派卻不這麼看。1989年,丹尼·希利斯與一個知名計算機專家公開打賭,預測到1995年,并行機每月處理的數據量將超過串列機。看來他是對的。當串列計算機由於其狹窄的馮·諾依曼通道不堪複雜任務的重負而痛苦呻|吟時,專家的看法一夜之間就發生了變化,並迅速席捲了整個計算機產業。彼得·丹寧在《科學》雜誌上撰文(《高度并行的計算》,1990年11月30日),稱,「解決高級科學問題所需的計算速度,只能通過高度并行的計算架構來獲得。」斯坦福大學計算機科學系的約翰·柯扎更直截了當,「并行計算機是計算的未來。句號。」九_九_藏_書read.99csw.com
義大利米蘭的一組研究員提出了一些新的進化和學習方法。他們的方法填補了艾克利所提到的「所有可能的計算空間」中的一些空白。這些研究員們把自己的搜索方法稱為「蟻群演算法」,是因為他們受到了蟻群集體行為的啟迪。
一個螞蟻軍團,智愚而不知測量,視短而不及遠望,卻能迅速找到穿越崎嶇地面的最短路徑。這種計算正是對進化搜索的完美映射:一群無知而短視的個體們在數學意義上崎嶇不平的地形上同時作業,試圖找出一條最優路徑。蟻群就是一個并行處理機。
無論是真實的螞蟻,還是虛擬的螞蟻,它們的聰明在於,投入「傳播」的信息量非常少,範圍非常小,信號也非常弱。將弱傳播引入進化的提法相當有吸引力。即使地球的生物界中存在拉馬克進化,那它也一定被埋藏得很九*九*藏*書深。不過,仍然存在充滿了各種稀奇古怪演算法的空間,各種拉馬克式的傳播盡可以在那裡找到用武之地。我聽說有的程序員整天在鼓搗「彌母(文化基因)」式的進化演算法——即模仿思想流(彌母)從一個大腦進入另一個大腦,試圖捕捉到文化革命的精髓和力量。連接分散式計算機節點的方法有千千萬萬,迄今為止,只有極少數的方法(如螞蟻演算法)被人們考察過。
然而,并行計算機還是很難掌控。并行軟體是水平的、併發的、錯綜複雜的因果網路。你無法從這樣的非線性特性中找出缺陷所在,它們都隱藏了起來。沒有清晰的步驟可循,代碼無從分解,事件此起彼伏。製造并行計算機很容易,但要為其編程卻很難。
螞蟻演算法是拉馬克搜索的一種形式。當某隻螞蟻偶然發現一條短路徑,這個信息通過信息素的氣味間接地傳播給其它虛擬螞蟻。這樣,單隻螞蟻畢生的學習所得就間接地成為整個蟻群信息遺產的一部分。螞蟻個體把它學習到的知識有效地傳播給自己的群體。與文化教導一樣,傳播也是拉馬克搜索的一部分。艾克利說:「除了交配,信息交換還有許多方式。比如晚間新聞。」