譯者序
如今,人工智能科學(xué)的發(fā)展如火如荼,其應(yīng)用也深入到社會(huì)各個(gè)領(lǐng)域。集群智能作為人工智能的一個(gè)重要研究方向,也隨著互聯(lián)網(wǎng)技術(shù)、機(jī)器人技術(shù)、嵌入式系統(tǒng)開(kāi)發(fā)技術(shù)的發(fā)展而受到越來(lái)越多的關(guān)注。不過(guò),作為一門(mén)20世紀(jì)80年代才出現(xiàn)的科學(xué),集群智能尚未形成清晰、完備的研究理論和研究方法,甚至在集群智能的定義上也一直存在爭(zhēng)議。
本書(shū)是20世紀(jì)90年代的作品,作者寫(xiě)作本書(shū)的主要目的是向讀者展示一系列受到自然界中社會(huì)性昆蟲(chóng)行為啟發(fā)的有趣的研究成果;诖四康模緯(shū)并沒(méi)有涉及太多晦澀難懂的理論闡述、公式推導(dǎo)、性質(zhì)證明,而是從對(duì)蟻群、蜂群行為觀察的結(jié)果入手,使用一些成熟的模型,嘗試解決一些從實(shí)際問(wèn)題中抽象出來(lái)的數(shù)學(xué)問(wèn)題,進(jìn)一步基于模型、假設(shè)和推測(cè)設(shè)計(jì)真實(shí)的“代理”(機(jī)器人或偽代碼),來(lái)展示集群智能的作用。
譯者團(tuán)隊(duì)在第一次閱讀原著時(shí),腦子里冒出最多的想法是:“原來(lái)是這樣!”“還可以這樣做!”“這個(gè)方法也許對(duì)我的項(xiàng)目很有用!”這些想法也是促使我們決定翻譯并出版這本書(shū)的最大原動(dòng)力。雖然這本書(shū)原著完成于20世紀(jì)90年代,其中所描述的一些知識(shí)和算法稍顯陳舊,但是其留給讀者(無(wú)論是否為該領(lǐng)域的研究人員)的啟發(fā)——如分析與解決問(wèn)題的思路、對(duì)未知事物的探索與研究方法——永遠(yuǎn)不會(huì)過(guò)時(shí)。
在本書(shū)中,一條明確的思路就是向研究人員展示如何從自然界中獲得靈感并將靈感帶到人工系統(tǒng)的設(shè)計(jì)中。長(zhǎng)期不厭其煩地觀察和統(tǒng)計(jì)、創(chuàng)造將各個(gè)變量聯(lián)系起來(lái)的公式、對(duì)參數(shù)的不斷修正與探索、將問(wèn)題抽象化并將其和模型建立類(lèi)比,這些過(guò)程在本書(shū)中均有所涉及。另外,本書(shū)還明確地向讀者展示了一個(gè)概念:共識(shí)主動(dòng)性(Stigmergy),它是集群智能中不可或缺的原則之一,描述了集群中的個(gè)體通過(guò)改變環(huán)境、感受改變的環(huán)境完成個(gè)體間交流,從而達(dá)到集群行為協(xié)調(diào)的過(guò)程。共識(shí)主動(dòng)性讓集群智能從直接交互(有時(shí)可以簡(jiǎn)單理解為通信)中解放出來(lái),讓沒(méi)有直接聯(lián)系的個(gè)體可以利用環(huán)境作為介質(zhì)進(jìn)行組群,涌現(xiàn)出集群智能行為。這個(gè)概念貫穿了本書(shū)的每一個(gè)章節(jié),是作者認(rèn)為在不遠(yuǎn)的未來(lái)實(shí)現(xiàn)微小型智能集群機(jī)器人的重要途徑之一。
坦誠(chéng)地講,在翻譯本書(shū)的過(guò)程中,我們(譯者團(tuán)隊(duì))遇到了一些困難。其中最麻煩的是眼花繚亂的螞蟻和蜂的準(zhǔn)確名稱(chēng),各種專(zhuān)業(yè)的種、屬、科名稱(chēng)確實(shí)給翻譯工作造成了不小的困擾。直到定稿前,還有一些螞蟻和蜂沒(méi)有找到權(quán)威的中文譯名。但是由于這些瑕疵不會(huì)對(duì)讀者造成理解上的困擾,因此也并未對(duì)其進(jìn)行更進(jìn)一步的研究。另外,2020年突如其來(lái)的新型冠狀病毒疫情也拖慢了本書(shū)翻譯的腳步,算是翻譯過(guò)程中的一個(gè)小插曲。
本書(shū)的翻譯、校對(duì)與出版離不開(kāi)團(tuán)隊(duì)中所有人的共同努力。除譯者外,熊婧、王子泉、楊宇、楊亞超、葉波波、王振北、徐驍、康森波、徐華興等人均貢獻(xiàn)了自己的一份力量。在本書(shū)出版發(fā)行之際,特別要感謝馬寶華教授、沈曉軍高級(jí)工程師、程進(jìn)高級(jí)工程師對(duì)本書(shū)翻譯、出版工作的支持、指導(dǎo)與關(guān)心。
由于譯者水平有限,加之集群智能相關(guān)理論和技術(shù)發(fā)展迅速,書(shū)中難免有錯(cuò)誤和不當(dāng)之處,懇請(qǐng)讀者不吝賜教。最后,援引作者的話作為結(jié)束語(yǔ):“我們希望本書(shū)能作為催化劑,通過(guò)展示這類(lèi)方法的前景來(lái)激勵(lì)研究人員克服某些已有的困難!
譯者
2020年9月于北京理工大學(xué)
前言
近五年來(lái),類(lèi)比昆蟲(chóng)群落的方法成為求解問(wèn)題的一個(gè)熱點(diǎn),該方法強(qiáng)調(diào)分布式、簡(jiǎn)單個(gè)體之間的直接/間接交互、靈活性和魯棒性,已經(jīng)成功應(yīng)用于組合優(yōu)化、通信網(wǎng)絡(luò)和機(jī)器人領(lǐng)域。越來(lái)越多的研究者對(duì)這一形成人工智能、集群智能的方法產(chǎn)生興趣,其中集群智能是指一系列簡(jiǎn)單個(gè)體所涌現(xiàn)出來(lái)的集體智能。研究人員有充分的理由發(fā)現(xiàn)集群智能的強(qiáng)大吸引力,即當(dāng)世界復(fù)雜到人類(lèi)個(gè)體無(wú)法理解時(shí)、當(dāng)信息多到會(huì)威脅我們生命時(shí)、當(dāng)軟件系統(tǒng)變得難以處理而無(wú)法控制時(shí),集群智能提供了另外一種設(shè)計(jì)“智能”系統(tǒng)的方法。在該“智能”系統(tǒng)中,自治、涌現(xiàn)和分布式機(jī)制代替控制、預(yù)編程和集中式機(jī)制。然而,集群智能領(lǐng)域在很大程度上依賴(lài)于零散的知識(shí),并且沒(méi)有嘗試將所有零散知識(shí)綜合在一起。
因此,本書(shū)首次將集群智能領(lǐng)域的知識(shí)進(jìn)行總結(jié),并給出有序調(diào)研的完美時(shí)機(jī)。一方面,我們不僅有足夠的資料來(lái)輔助有關(guān)集群智能圖書(shū)的出版;另一方面,研究人員日漸濃郁的興趣和將社會(huì)昆蟲(chóng)群落功能原理與人工系統(tǒng)設(shè)計(jì)原理明確聯(lián)系起來(lái)的潛在有用性,都是促使我們出版本書(shū)的緣由。
本書(shū)的每一章均圍繞一個(gè)生物學(xué)示例展開(kāi)描述,例如覓食、分工、尸體聚集、幼蟲(chóng)分揀、筑巢和合作運(yùn)輸。本書(shū)首先對(duì)上述示例進(jìn)行描述,當(dāng)存在模型時(shí)對(duì)其進(jìn)行建模,并類(lèi)比其機(jī)制來(lái)設(shè)計(jì)算法、多智能體系統(tǒng)和集群機(jī)器人。由于生物學(xué)建模和工程同等重要,所以盡管本書(shū)的寫(xiě)作方式顯得與眾不同,但希望讀者能發(fā)現(xiàn)我們所做工作的有趣性和有用性。
當(dāng)然,本書(shū)的成功出版少不了許多人的幫助和關(guān)心。我們要感謝羅納德·C.阿金(Ronald C.Arkin),淺間一(Hajime Asama),約翰·S.貝(John S.Bay),斯科特·卡瑪津(Scott Camazine),路易斯·德納堡(Louis Deneubourg),巴勃羅·富內(nèi)斯(Pablo Funes),西爾萬(wàn)·介朗(Sylvain Guérin),弗洛里安·埃諾(Florian Hénaux),阿蘭·赫茨(Alain Hertz),克勞斯·羅納德·庫(kù)貝(Claus Ronald Kube),帕斯卡萊·孔茨(Pascale Kuntz),阿爾切里奧·馬丁諾利(Alcherio Martinoli),喬丹·波拉克(Jordan Pollack),安德魯·羅素(Andrew Russell),多米尼克·斯奈爾斯(Dominique Snyers)和張洪(Hong Zhang)為我們提供有價(jià)值的文章,在發(fā)表之前分享他們的結(jié)果或傳達(dá)他們的熱情。特別感謝貝恩德·布爾恩海默(Bernd Bullnheimer),達(dá)妮埃萊·科斯塔(Daniele Costa),詹尼·迪卡羅(Gianni Di Caro),托馬斯·施蒂茨勒(Thomas Stützle)以及馬可·威寧(Marco Wiering)閱讀并評(píng)論了本書(shū)的初稿;感謝埃麗卡·珍(Erica Jen)和圣達(dá)菲研究所的支持;感謝IRIDIA實(shí)驗(yàn)室所有研究者的友誼;感謝菲利普·斯梅茨(Philippe Smets)和于格·貝尼尼(Hugues Bersini)對(duì)于馬爾科·多里戈(Marco Dorigo)研究工作的支持;感謝格雷格·奇里克吉安(Greg Chirikjian),奈杰爾·R.弗蘭克斯(Nigel R.Franks),巴勃羅·富內(nèi)斯,歐文·霍蘭(Owen Holland),細(xì)川一夫(Kazuo Hosokawa),克勞斯·羅納德·庫(kù)貝, 阿爾切里奧·馬丁諾利, 喬丹·波拉克和吉田英一(Eiichi Yoshida)對(duì)書(shū)中圖片及其他方面給予的幫助。最后,要感謝我們靈感的來(lái)源:路易斯·德納堡。馬爾科·多里戈謹(jǐn)感謝米蘭理工大學(xué)的研究生阿爾貝托·科洛爾尼(Alberto Colorni)和維托里奧·曼尼佐(Vittorio Maniezzo),是他們?yōu)橄伻簝?yōu)化做出了研究;感謝盧卡·甘巴爾代拉(Luca Gambardella)和吉安尼·迪卡洛(Gianni Di Caro),他們以其前沿的想法和編程技巧為本書(shū)中部分研究的成功做出了巨大貢獻(xiàn)。感謝米蘭理工大學(xué)人工智能和機(jī)器人項(xiàng)目組(the Artificial Intelligence and Robotics Project)所有成員的支持(期間馬爾科·多里戈展開(kāi)了關(guān)于蟻群優(yōu)化的研究);此外,特別感謝馬爾科·索馬爾維科(Marco Somalvico),安德烈亞·博納里尼(Andrea Bonarini)以及馬爾科·科隆貝蒂(Marco Colombetti)。
此外,埃里克·博納博(Eric Bonabeau)非常感謝圣達(dá)菲研究所對(duì)其階段性研究獎(jiǎng)學(xué)金的支持,埃里克·博納博和蓋伊·特洛拉茲(Guy Theraulaz)從GIS(Groupement dIntérêt Scientifique)科學(xué)獎(jiǎng)獲得了資助。蓋伊·特洛拉茲是國(guó)家科學(xué)研究中心(Centre National pour la Recherche Scientifique,CNRS)的負(fù)責(zé)人。 馬爾科·多里戈得到了比利時(shí)科學(xué)研究基金會(huì)FNRS的職業(yè)認(rèn)證。
最后,如果沒(méi)有龍達(dá)·巴特勒維拉(Ronda ButlerVilla),瑪麗莉·麥金尼斯(Marylee McInnes)以及德利婭·烏利瓦里(Della Ulibarri)的幫助和照顧,本書(shū)將一文不值。
埃里克·博納博,馬爾科·多里戈和蓋伊·特洛拉茲敬上
目錄
第1章簡(jiǎn)介1
1.1社會(huì)性昆蟲(chóng)1
1.2社會(huì)性昆蟲(chóng)群落的集體行為建模7
1.2.1建模與設(shè)計(jì)7
1.2.2社會(huì)性昆蟲(chóng)群落中的自組織8
1.2.3共識(shí)主動(dòng)性(Stigmergy)13
1.3交互建模15
1.4從算法到機(jī)器人16
1.5閱讀導(dǎo)引18
第2章螞蟻覓食行為在通信網(wǎng)絡(luò)中的應(yīng)用:組合優(yōu)化和路由20
2.1概述20
2.2蟻群覓食策略20
2.2.1自然界中的優(yōu)化:二元橋?qū)嶒?yàn)20
2.2.2自然界中的優(yōu)化:子巢穴間的“交通網(wǎng)絡(luò)”26
2.2.3行軍蟻的狩獵模式26
2.3蟻群優(yōu)化算法:旅行商問(wèn)題32
2.3.1螞蟻系統(tǒng)33
2.3.2蟻群系統(tǒng)38
2.3.3基于螞蟻系統(tǒng)或蟻群系統(tǒng)的其他方法45
2.4蟻群優(yōu)化:二次分配問(wèn)題46
2.4.1螞蟻系統(tǒng)應(yīng)用于二次分配問(wèn)題46
2.4.2混合螞蟻系統(tǒng)51
2.4.3ASQAP算法的擴(kuò)展56
2.5蟻群算法在優(yōu)化領(lǐng)域中的其他應(yīng)用56
2.5.1ASJSP:一種用于作業(yè)車(chē)間調(diào)度問(wèn)題的ACO算法59
2.5.2ANTCOL:用于圖形著色問(wèn)題的ACO算法60
2.5.3ASVRP:針對(duì)車(chē)輛路徑問(wèn)題的ACO算法61
2.5.4HASSOP:順序排序問(wèn)題的ACO算法62
2.5.5ASSCS:最短公共序列問(wèn)題中的ACO算法63
2.6關(guān)于ACO算法的幾點(diǎn)思考64
2.6.1ACO算法和神經(jīng)網(wǎng)絡(luò)64
2.6.2ACO算法和進(jìn)化算法65
2.6.3連續(xù)優(yōu)化65
2.7電信網(wǎng)絡(luò)中的應(yīng)用67
2.7.1ABC:電話網(wǎng)絡(luò)中的路由68
2.7.2ANTNET:數(shù)據(jù)通信網(wǎng)絡(luò)中的路由78
2.7.3一種基于螞蟻系統(tǒng)的螞蟻路由算法85
2.7.4約束條件與討論87
2.7.5在網(wǎng)絡(luò)環(huán)境中查找信息88
2.8要點(diǎn)謹(jǐn)記89
第3章勞力分工和任務(wù)分配90
3.1概述90
3.2社會(huì)性昆蟲(chóng)中的勞力分工90
3.3響應(yīng)閾值91
3.3.1引言91
3.3.2響應(yīng)閾值:簡(jiǎn)介和實(shí)驗(yàn)證明93
3.3.3單任務(wù)模型98
3.3.4模型分析:確定性方程100
3.3.5多任務(wù)模型104
3.3.6“緊急”任務(wù)接續(xù)模型105
3.4專(zhuān)一化110
3.5多智能體系統(tǒng)中的差異化和自適應(yīng)任務(wù)分配117
3.5.1多智能體系統(tǒng)或機(jī)器人群體中的差異化117
3.5.2自適應(yīng)任務(wù)分配117
3.5.3與“競(jìng)標(biāo)”算法的聯(lián)系122
3.6要點(diǎn)謹(jǐn)記123
第4章墓地結(jié)構(gòu)、育雛分選、數(shù)據(jù)分析和圖分割124
4.1概述124
4.2墓地結(jié)構(gòu)和育雛分選124
4.3一種墓地聚類(lèi)和育雛分選的模型126
4.3.1聚類(lèi)126
4.3.2分類(lèi)128
4.3.3空間熵及其變體128
4.4探索性數(shù)據(jù)分析129
4.5圖分割136
4.6機(jī)器人應(yīng)用144
4.6.1介紹144
4.6.2示例144
4.6.3其他工作147
4.6.4從聚類(lèi)到分類(lèi)149
4.6.5發(fā)展設(shè)想149
4.7要點(diǎn)謹(jǐn)記150
第5章自組織與模板:在數(shù)據(jù)分析和圖形分區(qū)中的應(yīng)用152
5.1概述152
5.2自組織和模板的相互作用152
5.3建造蟻后房的一種“反應(yīng)擴(kuò)散”模型156
5.4細(xì)胸蟻屬albipennis螞蟻巢壁建造159
5.5應(yīng)用165
5.5.1數(shù)據(jù)分析166
5.5.2圖像分割166
5.6要點(diǎn)謹(jǐn)記168
第6章筑巢和自組裝169
6.1概述169
6.2社會(huì)性昆蟲(chóng)的筑巢行為169
6.2.1定量的共識(shí)主動(dòng)性:共識(shí)主動(dòng)性和自組織170
6.2.2定性/離散的共識(shí)主動(dòng)性171
6.3自組裝模型175
6.3.1模型175
6.3.2仿真176
6.3.3分析180
6.3.4探索建筑結(jié)構(gòu)的空間180
6.4生物學(xué)之外的應(yīng)用188
6.4.1簡(jiǎn)介188
6.4.2自組裝機(jī)器人189
6.4.3建筑設(shè)計(jì)201
6.4.4不斷發(fā)展的功能201
6.5要點(diǎn)謹(jǐn)記203
第7章昆蟲(chóng)和機(jī)器人的合作運(yùn)輸204
7.1概述204
7.2螞蟻對(duì)獵物的協(xié)同運(yùn)輸204
7.2.1單獨(dú)運(yùn)輸與合作運(yùn)輸206
7.2.2從獨(dú)立到合作運(yùn)輸206
7.2.3招募行為208
7.2.4合作運(yùn)輸中的協(xié)調(diào)209
7.2.5合作運(yùn)輸中參與者的數(shù)量210
7.2.6死鎖和恢復(fù)210
7.3集群機(jī)器人合作運(yùn)輸211
7.3.1簡(jiǎn)介211
7.3.2基本模型及其實(shí)現(xiàn)212
7.3.3停滯后恢復(fù):模型和機(jī)器人實(shí)現(xiàn)214
7.4要點(diǎn)謹(jǐn)記217
第8章結(jié)語(yǔ)218
參考文獻(xiàn)220