基本信息
- 原书名:Ant Colony Optimization
- 原出版社: MIT Press
- 作者: (意)Marco Dorigo (德)Thomas Stützle
- 译者: 张军 胡晓敏 罗旭耀
- 出版社:清华大学出版社
- ISBN:7302138877
- 上架时间:2007-1-12
- 出版日期:2007 年1月
- 开本:170×230
- 页码:298
- 版次:1-1
- 所属分类:计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
计算机 > 计算机控制与仿真 > 现代控制理论
内容简介
计算机书籍
通过对蚂蚁复杂的社会行为的研究,科学家们发现基于其行为模式的模型可以用来求解复杂的组合优化问题。为了解决计算机科学中的最短路径问题,基于蚂蚁行为特征所发展起来的算法演变成一个被广泛认可并非常成功的新的研究领域——蚁群优化(ACO)。本书从理论和实际应用两方面介绍了这个迅速发展的领域。.
本书首先介绍了如何将蚂蚁的行为转换成有效的优化算法,然后介绍蚁群元启发式算法及其在组合优化中的应用。随后介绍了主要的ACO算法并给出了最新的理论进展。书中综述了当前的ACO应用,包括路由问题、任务委派、调度安排、子集问题、机器学习和生物信息学问题等,详细描述了用于网络路由的蚁网蚁群优化算法AntNet。最后,对该领域的研究进展进行了总结,并给出了未来的研究方向。书中每一章都给出了建议阅读的参考书目、章节重点和练习题目。..
本书可作为高等院校计算机及相关专业的高年级学生、研究生的教材,也可供高校教师及科研院所的研究人员参考。...
目录
1.1 蚂蚁的觅食行为及其优化过程
1.1.1 双桥实验
1.1.2 随机模型
1.2 向人工蚂蚁转换
1.3 人工蚂蚁和最小成本路径
1.3.1 S-ACO
1.3.2 有关S-ACO的实验
1.4 书目评注
1.5 需要牢记的知识点
1.6 思考与计算习题
2 蚁群优化元启发式算法
2.1 组合优化
2.1.1 计算复杂度
2.1.2 NP-难问题的解决方法
2.1.3 什么是元启发式算法
2.2 ACO元启发式算法
2.2.1 问题描述
2.2.2 蚂蚁的行为
2.2.3 元启发式算法
译者序
Dorigo是蚁群优化的创始人,Statzle是对蚁群优化的算法与应用发展有重要贡献的学者。他们共同撰写了《蚁群优化》一书,从原理、算法描述、理论、应用、发展前景等各方面对蚁群优化作出了全面论述。我们相信,对于学术研究者来说,这本书能帮助您更深刻地理解蚁群优化,为学术研究提供新的思想源泉和研究方法;对于工程和应用研究者来说,这本书能为实际应用问题的求解提供全新的思路,为蚁群优化思想的应用提供指引;对于学生或优化算法爱好者来说,这本书将成为您打开蚁群优化之门的钥匙。
我们很幸运能够有机会翻译这本优秀的图书。一方面,在翻译这本书的过程中,我们可以仔细地体味蚁群优化的思想,加深对算法的理解;另一方面,我们也希望通过引进此书,能进一步普及蚁群优化在国内的研究和应用。
翻译工作的分工如下:张军博士负责全书的翻译和校对工作,胡晓敏翻译了前言、第1章、第2章和第5章的一部分,陈伟能翻译了第3章、第5章的一部分以及索引,罗旭耀翻译了第4、6、7章,谭旋负责全书图表的翻译工作,中山大学中文系的陈淑环博士对中译文进行了修饰。参与本书翻译和校对工作的还有中国科学院计算所的黄强,以及中山大学的许志坚、李慧芬和钟竞辉。
最后,我们要感谢Dorigo教授在百忙之中悉心回答译者的问题,并特为中译本撰写了序言。
由于翻译时间仓促,译者水平有限,翻译不当或疏漏之处在所难免,希望广大读者批评指正。...
张 军
2006年5月于中山大学
前言
令人惊讶的是,某些种类的蚂蚁所表现出来的路径寻找行为模式非常不可思议,这个模式就是计算机科学家平常所说的最短路径搜索。生物学家在实验中发现,蚂蚁可以通过感知和释放一种带有气味的化学物质——信息素来实现相互之间的通信交流。在求解优化问题的时候,正是蚂蚁这种特有的行为模式启发了计算机科学家建立新型算法的灵感。关于这类算法的第一次尝试出现在20世纪90年代初期,尽管那时的算法在今天看来非常幼稚,但重要的是它表明了此类算法是可行的。从那以后,关于这类算法以及其他类似思想方法的研究和成果不断涌现,而蚁群优化(ant colony optimization,ACO)正是众多成果之一。事实上,基于蚂蚁行为的ACO是最成功且受到最广泛认可的算法技术。ACO的成功不仅体现在能够求解众多不同类型的优化问题,而且更多体现在它在求解大量问题时所能获得的极佳性能。
全书纵览
本书介绍了蚁群优化这一飞速发展的领域里许多可行的ACO算法及其主要应用。全面详细地描述了ACO思想及其在各种组合优化问题上的应用等。本书分为七章,各章内容如下:
第1章解释了蚂蚁如何在受控实验条件下找出最短路径,并阐述了此种行为转换到优化算法的具体过程。
第2章介绍了ACO元启发式算法,并分析讨论了该算法在组合优化中应用的情况和问题。此外,本章还提出了NP-难等复杂性理论的基本概念,并简单论述了其他主要的元启发式算法。..
第3章深入描述了当前学术界所有可用的主流ACO算法。本章以旅行商问题作为应用例子说明算法的实现过程。有关算法的一个C语言基本实现的简要说明及可用的公共软件可在www.aco-metaheuristic.org/aco-code/中找到。
第4章讲述了当前已知的有关ACO算法的理论知识。本章证明了某些类型的ACO算法的收敛性,讨论了ACO与其他方法之间的关系,例如随机梯度下降、交互信息最大化输入聚类和交叉熵。
第5章综述了当前开发ACO用以解决一系列组合优化问题的现状。涉及的应用实例,除了包括路由、分配、调度和子集问题以外,还包括其他不同领域中的若干问题,例如机器学习和生物信息学。此外,本章还谈到了在使用算法的过程中遇到新问题时所要遵循的“使用原则”。
第6章重点描述了AntNet的详细内容。AntNet是一种用以解决网络路由问题的ACO算法,所谓网络路由问题是指分组交换通信网络中路由表的建立和维护问题。
第7章总结了所讨论领域中的主要成果,并描绘了未来研究中一些有趣的发展方向。
本书每一章(除了最后一章)的最后都包含以下三个小节:书目评注、需要牢记的知识点和思考与计算习题。
·“书目评注”是一种带短评的目录索引,包含了与当前章节中讨论话题有关的进一步的文献索引。
·在“需要牢记的知识点”中,列举了当前章节的重要知识点。
·“思考与计算习题”中包括思考习题和计算习题,具体采取哪种形式的习题与当前章节给出的材料有关。
本书的最后还列出了有关ACO算法的参考文献,其中包含了许多更深入的相关文献。
总体而言,本书适合任何具有大学水平和科研背景的人员阅读。对于熟悉有关图论、编程和概率的读者来说,本书所使用的元启发式算法除了第4章需要一些较为深入的概率理论知识以外,其余都是相当通俗的。本书面向的主要对象有:①从事运筹学、人工智能和计算智能等相关研究的科研人员和工程技术人员;②有志于研究如何把ACO算法应用于解决组合优化问题的练习者;③计算机科学、管理科学、运筹学和人工智能等专业的研究生和本科高年级学生。...
序言
当时我是无法预见到这种简单的算法可以获得如今这么大的成就的。过去的15年间,在很多研究者的帮助下,特别是Luca M.Gambardella和Thomas Stutzle,这种算法从意大利的一个实验室传播到了世界上千千万万个实验室中。这种传播模式类似于最近邻算法:首先,ACO在欧洲——这个大部分ACO的研究者居住的地方传播开来。然后,随着ACO这本书在MIT出版社的出版,这个算法传播到了美国以及世界的其他地方。然而,语言上的障碍使得到目前为止,ACO算法在世界上人口最多、发展最快的国家——中国的传播还遇到不少困难。..
因此,我非常高兴中文翻译版的面市,也非常感谢张军教授对这本书所做出的大量工作。...
Marco Dorigo
布鲁塞尔,2006年5月7日