译者序
如今,人工智能科学的发展如火如荼,其应用也深入到社会各个领域。集群智能作为人工智能的一个重要研究方向,也随着互联网技术、机器人技术、嵌入式系统开发技术的发展而受到越来越多的关注。不过,作为一门20世纪80年代才出现的科学,集群智能尚未形成清晰、完备的研究理论和研究方法,甚至在集群智能的定义上也一直存在争议。
本书是20世纪90年代的作品,作者写作本书的主要目的是向读者展示一系列受到自然界中社会性昆虫行为启发的有趣的研究成果。基于此目的,本书并没有涉及太多晦涩难懂的理论阐述、公式推导、性质证明,而是从对蚁群、蜂群行为观察的结果入手,使用一些成熟的模型,尝试解决一些从实际问题中抽象出来的数学问题,进一步基于模型、假设和推测设计真实的“代理”(机器人或伪代码),来展示集群智能的作用。
译者团队在第一次阅读原著时,脑子里冒出最多的想法是:“原来是这样!”“还可以这样做!”“这个方法也许对我的项目很有用!”这些想法也是促使我们决定翻译并出版这本书的最大原动力。虽然这本书原著完成于20世纪90年代,其中所描述的一些知识和算法稍显陈旧,但是其留给读者(无论是否为该领域的研究人员)的启发——如分析与解决问题的思路、对未知事物的探索与研究方法——永远不会过时。
在本书中,一条明确的思路就是向研究人员展示如何从自然界中获得灵感并将灵感带到人工系统的设计中。长期不厌其烦地观察和统计、创造将各个变量联系起来的公式、对参数的不断修正与探索、将问题抽象化并将其和模型建立类比,这些过程在本书中均有所涉及。另外,本书还明确地向读者展示了一个概念:共识主动性(Stigmergy),它是集群智能中不可或缺的原则之一,描述了集群中的个体通过改变环境、感受改变的环境完成个体间交流,从而达到集群行为协调的过程。共识主动性让集群智能从直接交互(有时可以简单理解为通信)中解放出来,让没有直接联系的个体可以利用环境作为介质进行组群,涌现出集群智能行为。这个概念贯穿了本书的每一个章节,是作者认为在不远的未来实现微小型智能集群机器人的重要途径之一。
坦诚地讲,在翻译本书的过程中,我们(译者团队)遇到了一些困难。其中最麻烦的是眼花缭乱的蚂蚁和蜂的准确名称,各种专业的种、属、科名称确实给翻译工作造成了不小的困扰。直到定稿前,还有一些蚂蚁和蜂没有找到权威的中文译名。但是由于这些瑕疵不会对读者造成理解上的困扰,因此也并未对其进行更进一步的研究。另外,2020年突如其来的新型冠状病毒疫情也拖慢了本书翻译的脚步,算是翻译过程中的一个小插曲。
本书的翻译、校对与出版离不开团队中所有人的共同努力。除译者外,熊婧、王子泉、杨宇、杨亚超、叶波波、王振北、徐骁、康森波、徐华兴等人均贡献了自己的一份力量。在本书出版发行之际,特别要感谢马宝华教授、沈晓军高级工程师、程进高级工程师对本书翻译、出版工作的支持、指导与关心。
由于译者水平有限,加之集群智能相关理论和技术发展迅速,书中难免有错误和不当之处,恳请读者不吝赐教。最后,援引作者的话作为结束语:“我们希望本书能作为催化剂,通过展示这类方法的前景来激励研究人员克服某些已有的困难。”
译者
2020年9月于北京理工大学
前言
近五年来,类比昆虫群落的方法成为求解问题的一个热点,该方法强调分布式、简单个体之间的直接/间接交互、灵活性和鲁棒性,已经成功应用于组合优化、通信网络和机器人领域。越来越多的研究者对这一形成人工智能、集群智能的方法产生兴趣,其中集群智能是指一系列简单个体所涌现出来的集体智能。研究人员有充分的理由发现集群智能的强大吸引力,即当世界复杂到人类个体无法理解时、当信息多到会威胁我们生命时、当软件系统变得难以处理而无法控制时,集群智能提供了另外一种设计“智能”系统的方法。在该“智能”系统中,自治、涌现和分布式机制代替控制、预编程和集中式机制。然而,集群智能领域在很大程度上依赖于零散的知识,并且没有尝试将所有零散知识综合在一起。
因此,本书首次将集群智能领域的知识进行总结,并给出有序调研的完美时机。一方面,我们不仅有足够的资料来辅助有关集群智能图书的出版;另一方面,研究人员日渐浓郁的兴趣和将社会昆虫群落功能原理与人工系统设计原理明确联系起来的潜在有用性,都是促使我们出版本书的缘由。
本书的每一章均围绕一个生物学示例展开描述,例如觅食、分工、尸体聚集、幼虫分拣、筑巢和合作运输。本书首先对上述示例进行描述,当存在模型时对其进行建模,并类比其机制来设计算法、多智能体系统和集群机器人。由于生物学建模和工程同等重要,所以尽管本书的写作方式显得与众不同,但希望读者能发现我们所做工作的有趣性和有用性。
当然,本书的成功出版少不了许多人的帮助和关心。我们要感谢罗纳德·C.阿金(Ronald C.Arkin),浅间一(Hajime Asama),约翰·S.贝(John S.Bay),斯科特·卡玛津(Scott Camazine),路易斯·德纳堡(Louis Deneubourg),巴勃罗·富内斯(Pablo Funes),西尔万·介朗(Sylvain Guérin),弗洛里安·埃诺(Florian Hénaux),阿兰·赫茨(Alain Hertz),克劳斯·罗纳德·库贝(Claus Ronald Kube),帕斯卡莱·孔茨(Pascale Kuntz),阿尔切里奥·马丁诺利(Alcherio Martinoli),乔丹·波拉克(Jordan Pollack),安德鲁·罗素(Andrew Russell),多米尼克·斯奈尔斯(Dominique Snyers)和张洪(Hong Zhang)为我们提供有价值的文章,在发表之前分享他们的结果或传达他们的热情。特别感谢贝恩德·布尔恩海默(Bernd Bullnheimer),达妮埃莱·科斯塔(Daniele Costa),詹尼·迪卡罗(Gianni Di Caro),托马斯·施蒂茨勒(Thomas Stützle)以及马可·威宁(Marco Wiering)阅读并评论了本书的初稿;感谢埃丽卡·珍(Erica Jen)和圣达菲研究所的支持;感谢IRIDIA实验室所有研究者的友谊;感谢菲利普·斯梅茨(Philippe Smets)和于格·贝尼尼(Hugues Bersini)对于马尔科·多里戈(Marco Dorigo)研究工作的支持;感谢格雷格·奇里克吉安(Greg Chirikjian),奈杰尔·R.弗兰克斯(Nigel R.Franks),巴勃罗·富内斯,欧文·霍兰(Owen Holland),细川一夫(Kazuo Hosokawa),克劳斯·罗纳德·库贝, 阿尔切里奥·马丁诺利, 乔丹·波拉克和吉田英一(Eiichi Yoshida)对书中图片及其他方面给予的帮助。最后,要感谢我们灵感的来源:路易斯·德纳堡。马尔科·多里戈谨感谢米兰理工大学的研究生阿尔贝托·科洛尔尼(Alberto Colorni)和维托里奥·曼尼佐(Vittorio Maniezzo),是他们为蚁群优化做出了研究;感谢卢卡·甘巴尔代拉(Luca Gambardella)和吉安尼·迪卡洛(Gianni Di Caro),他们以其前沿的想法和编程技巧为本书中部分研究的成功做出了巨大贡献。感谢米兰理工大学人工智能和机器人项目组(the Artificial Intelligence and Robotics Project)所有成员的支持(期间马尔科·多里戈展开了关于蚁群优化的研究);此外,特别感谢马尔科·索马尔维科(Marco Somalvico),安德烈亚·博纳里尼(Andrea Bonarini)以及马尔科·科隆贝蒂(Marco Colombetti)。
此外,埃里克·博纳博(Eric Bonabeau)非常感谢圣达菲研究所对其阶段性研究奖学金的支持,埃里克·博纳博和盖伊·特洛拉兹(Guy Theraulaz)从GIS(Groupement dIntérêt Scientifique)科学奖获得了资助。盖伊·特洛拉兹是国家科学研究中心(Centre National pour la Recherche Scientifique,CNRS)的负责人。 马尔科·多里戈得到了比利时科学研究基金会FNRS的职业认证。
最后,如果没有龙达·巴特勒维拉(Ronda ButlerVilla),玛丽莉·麦金尼斯(Marylee McInnes)以及德利娅·乌利瓦里(Della Ulibarri)的帮助和照顾,本书将一文不值。
埃里克·博纳博,马尔科·多里戈和盖伊·特洛拉兹敬上
目录
第1章简介1
1.1社会性昆虫1
1.2社会性昆虫群落的集体行为建模7
1.2.1建模与设计7
1.2.2社会性昆虫群落中的自组织8
1.2.3共识主动性(Stigmergy)13
1.3交互建模15
1.4从算法到机器人16
1.5阅读导引18
第2章蚂蚁觅食行为在通信网络中的应用:组合优化和路由20
2.1概述20
2.2蚁群觅食策略20
2.2.1自然界中的优化:二元桥实验20
2.2.2自然界中的优化:子巢穴间的“交通网络”26
2.2.3行军蚁的狩猎模式26
2.3蚁群优化算法:旅行商问题32
2.3.1蚂蚁系统33
2.3.2蚁群系统38
2.3.3基于蚂蚁系统或蚁群系统的其他方法45
2.4蚁群优化:二次分配问题46
2.4.1蚂蚁系统应用于二次分配问题46
2.4.2混合蚂蚁系统51
2.4.3ASQAP算法的扩展56
2.5蚁群算法在优化领域中的其他应用56
2.5.1ASJSP:一种用于作业车间调度问题的ACO算法59
2.5.2ANTCOL:用于图形着色问题的ACO算法60
2.5.3ASVRP:针对车辆路径问题的ACO算法61
2.5.4HASSOP:顺序排序问题的ACO算法62
2.5.5ASSCS:最短公共序列问题中的ACO算法63
2.6关于ACO算法的几点思考64
2.6.1ACO算法和神经网络64
2.6.2ACO算法和进化算法65
2.6.3连续优化65
2.7电信网络中的应用67
2.7.1ABC:电话网络中的路由68
2.7.2ANTNET:数据通信网络中的路由78
2.7.3一种基于蚂蚁系统的蚂蚁路由算法85
2.7.4约束条件与讨论87
2.7.5在网络环境中查找信息88
2.8要点谨记89
第3章劳力分工和任务分配90
3.1概述90
3.2社会性昆虫中的劳力分工90
3.3响应阈值91
3.3.1引言91
3.3.2响应阈值:简介和实验证明93
3.3.3单任务模型98
3.3.4模型分析:确定性方程100
3.3.5多任务模型104
3.3.6“紧急”任务接续模型105
3.4专一化110
3.5多智能体系统中的差异化和自适应任务分配117
3.5.1多智能体系统或机器人群体中的差异化117
3.5.2自适应任务分配117
3.5.3与“竞标”算法的联系122
3.6要点谨记123
第4章墓地结构、育雏分选、数据分析和图分割124
4.1概述124
4.2墓地结构和育雏分选124
4.3一种墓地聚类和育雏分选的模型126
4.3.1聚类126
4.3.2分类128
4.3.3空间熵及其变体128
4.4探索性数据分析129
4.5图分割136
4.6机器人应用144
4.6.1介绍144
4.6.2示例144
4.6.3其他工作147
4.6.4从聚类到分类149
4.6.5发展设想149
4.7要点谨记150
第5章自组织与模板:在数据分析和图形分区中的应用152
5.1概述152
5.2自组织和模板的相互作用152
5.3建造蚁后房的一种“反应扩散”模型156
5.4细胸蚁属albipennis蚂蚁巢壁建造159
5.5应用165
5.5.1数据分析166
5.5.2图像分割166
5.6要点谨记168
第6章筑巢和自组装169
6.1概述169
6.2社会性昆虫的筑巢行为169
6.2.1定量的共识主动性:共识主动性和自组织170
6.2.2定性/离散的共识主动性171
6.3自组装模型175
6.3.1模型175
6.3.2仿真176
6.3.3分析180
6.3.4探索建筑结构的空间180
6.4生物学之外的应用188
6.4.1简介188
6.4.2自组装机器人189
6.4.3建筑设计201
6.4.4不断发展的功能201
6.5要点谨记203
第7章昆虫和机器人的合作运输204
7.1概述204
7.2蚂蚁对猎物的协同运输204
7.2.1单独运输与合作运输206
7.2.2从独立到合作运输206
7.2.3招募行为208
7.2.4合作运输中的协调209
7.2.5合作运输中参与者的数量210
7.2.6死锁和恢复210
7.3集群机器人合作运输211
7.3.1简介211
7.3.2基本模型及其实现212
7.3.3停滞后恢复:模型和机器人实现214
7.4要点谨记217
第8章结语218
参考文献220