倒数第二篇:11.2  JSP 的遗传算法
倒数第一篇:11.3  仿真结果
主页
第二篇: 第 1 章  引  言
第三篇:1. 2  最优化技术综述
文章列表

《用 于 最 优 化 的 计 算 智 能》

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

(京)新登字 158 号

内  容  简  介

本书从讨论组合优化中的基本问题——NP问题入手,系统地讲述了近年来所发展起来的智能最优化的各种技术和方法,其中包括启发式搜索、Hopfield神经网络、模拟退火和随机机、均场退火以及遗传算法等; 并在此基础上,通过一些典型的应用问题,如旅行商问题、模式识别中的点模式匹配问题、通信和任务调度等问题进一步阐明以上一些基本方法怎样用来解决这些原来具有NP 性质的困难问题。本书是作者在美国新泽西州理工学院多年讲授有关课程的基础上写成的。全书深入浅出,理论联系实际。为帮助学生掌握基本概念,提高学习能动性,各章编写了习题。

本书可作为通信、计算机、控制各专业的高年级学生和研究生学习有关课程的教材。它对于广大科研工作者也是一本很有实际价值的参考书。

ComputationalIntelligencefor Optimization

NirwanAnsariEdwinHou

Copyright ○C1997byKluwer AcademicPublishers

OriginalEnglishLanguageEditionPublishedbyKluwer AcademicPublishers

本书中文简体字版由Kluwer AcademicPublishers授权清华大学出版社独家出版、发行。未经出版者书面许可,不得以任何方式复制或抄袭本书的内容。

本书封面贴有清华大学出版社激光防伪标签,无标签者不得销售。

北京市版权局著作权合同登记号: 01-98-0945

书  名: 用于最优化的计算智能

作  者: Nirwan Ansari Edwin Hou 著  李军  边肇祺  译

出版者: 清华大学出版社(北京清华大学学研楼,邮编100084)

http://www.tup.tsinghua.edu.cn

印刷者: 北京大中印刷厂

发行者: 新华书店总店北京发行所

开  本: 787 1092 1/16  印张: 8.75  字数: 204千字

版  次: 1999年12月第1版  1999年12月第1次印刷

书  号: ISBN 7-302-03635-7/TP・2019

印  数: 0001~3000

定  价: 18.00元

译 者 的 话

洪伟年(Nirwan Ansari)与侯瑞海(Edwin Hou)两位教授集多年教学和科研成果合著的《用于最优化的计算智能》一书,是反映近年来最优化技术发展的专著。此书取材新颖、内容丰富、结构合理、论述清楚,在有限的篇幅中对所有重要方法都进行了透彻的阐述,不仅对于研究生掌握有关概念和方法十分有益,对通信、计算机、控制等领域的科研和工程技术人员也很有参考价值。

最近数年来计算智能技术发展迅速,在此基础上,本书论述了最优化基础理论和实际应用。书中涉及的多种智能最优化方法均已成为人工智能、模式识别和其它有关领域行之有效的方法,并已与经典的统计模式识别技术和结构模式识别技术一起,构成了现代模式识别方法的理论基础。鉴于国内有关智能计算在最优化中应用的资料大多散见于各种学术期刊和会议文集,相信本书中译版的出版将会有助于这一学科的发展,并推动相关领域的教学、科研和工程实践。

为了便于读者根据不同的学习和工作需要较快地掌握有关的算法,著者采用了一种相对独立的模块式结构。书中第2~6章每章各介绍一种基本的方法,首先对有关概念给出严格而明确的定义,然后再深入浅出地展开对理论部分的论述。在第7~11章每章围绕一个典型问题,对各种方法的应用实例加以描述,并进行适当比较。这样的安排不仅给读者一个清晰的概念,而且引导读者对各种方法的特点进行深入的比较,从而学会针对实际问题的特点选择有效的解决方法。

本书从第1章到第8章以及第10章,第11章由李军翻译,第9章由边肇祺翻译,边肇祺并对全书进行了校正。书中难免有翻译不确切的地方,望请读者批评指正。

感谢两位作者在本书的翻译过程中给予的帮助。清华大学出版社为本书的出版做了大量工作,译者在此一并致谢。

译  者

1998年11月

・Ⅰ・ 目  录

前言 ………………………………………………………………………………………… Ⅶ

第1章  引言………………………………………………………………………………… 1

1.1  计算复杂度 ……………………………………………………………………… 1

1.1.1  算法分析 ………………………………………………………………… 1

1.1.2  NP 完全问题 …………………………………………………………… 3

1.2  最优化技术综述 ………………………………………………………………… 3

1.2.1  启发式搜索 ……………………………………………………………… 3

1.2.2  霍普费尔德神经网络 …………………………………………………… 4

1.2.3  模拟退火与随机机 ……………………………………………………… 4

1.2.4  均场退火 ………………………………………………………………… 4

1.2.5  遗传算法 ………………………………………………………………… 5

1.3  本书的结构 ……………………………………………………………………… 5

1.4  习题 ……………………………………………………………………………… 5

第2章  启发式搜索方法…………………………………………………………………… 6

2.1  图搜索算法 ……………………………………………………………………… 6

2.2  启发函数………………………………………………………………………… 10

2.3  A* 搜索算法 …………………………………………………………………… 12

2.4  习题……………………………………………………………………………… 13

第3章  霍普费尔德神经网络 …………………………………………………………… 15

3.1  离散霍氏网……………………………………………………………………… 16

3.2  连续霍氏网……………………………………………………………………… 18

3.3  按内容联想的存储器…………………………………………………………… 19

3.4  组合最优化……………………………………………………………………… 20

3.4.1  旅行商问题……………………………………………………………… 21

3.4.2  二分图问题……………………………………………………………… 23

3.4.3  N 皇后问题 …………………………………………………………… 24

3.5  习题……………………………………………………………………………… 25

第4章  模拟退火和随机机 ……………………………………………………………… 27

・Ⅲ・ 4.1  统计力学和麦绰泼里斯算法…………………………………………………… 27

4.2  模拟退火………………………………………………………………………… 30

4.2.1  有限时间实现…………………………………………………………… 31

4.2.2  一个例子: TSP ………………………………………………………… 33

4.3  随机机…………………………………………………………………………… 35

4.3.1  波尔兹曼机……………………………………………………………… 35

4.3.2  高斯机…………………………………………………………………… 37

4.3.3  柯西机…………………………………………………………………… 38

4.4  习题……………………………………………………………………………… 40

第5章  均场退火 ………………………………………………………………………… 42

5.1  均场近似………………………………………………………………………… 42

5.2  鞍点展开………………………………………………………………………… 43

5.3  稳定性…………………………………………………………………………… 45

5.4  均场网的参数…………………………………………………………………… 45

5.5  二分图示例……………………………………………………………………… 47

5.6  习题……………………………………………………………………………… 48

第6章  遗传算法 ………………………………………………………………………… 49

6.1  简单遗传操作…………………………………………………………………… 49

6.1.1  繁殖……………………………………………………………………… 49

6.1.2  交叉……………………………………………………………………… 51

6.1.3  突变……………………………………………………………………… 51

6.2  一个示例………………………………………………………………………… 52

6.3  为什么遗传算法会奏效? ……………………………………………………… 54

6.4  其它遗传操作…………………………………………………………………… 56

6.5  习题……………………………………………………………………………… 57

第7章  旅行商问题 ……………………………………………………………………… 58

7.1  为什么霍氏网经常不能生成有效解答? ……………………………………… 58

7.1.1  霍氏网的动力学………………………………………………………… 60

7.1.2  拉格朗日参数的另一种表达方式……………………………………… 62

7.1.3  霍普费尔德的10城市问题 …………………………………………… 63

7.2  应用启发式搜索算法求解TSP ……………………………………………… 67

7.3  应用模拟退火算法求解TSP ………………………………………………… 69

7.4  应用遗传算法求解TSP ……………………………………………………… 70

7.5  本征值分析概述………………………………………………………………… 71

7.6  连接矩阵的λ1 的推导 ………………………………………………………… 72・Ⅳ・

7.7  习题……………………………………………………………………………… 73

第8章  电信 ……………………………………………………………………………… 74

8.1  卫星广播调度…………………………………………………………………… 74

8.1.1  SBS问题的神经网络表达……………………………………………… 74

8.1.2  SBS问题的均场公式…………………………………………………… 76

8.1.3  算法的参数……………………………………………………………… 77

8.1.4  临界温度Tc …………………………………………………………… 78

8.1.5  一个示例………………………………………………………………… 80

8.2  集成TDMA 通信系统的数据吞吐量最大化 ………………………………… 81

8.2.1  多路复用方案与数据吞吐量…………………………………………… 81

8.2.2  数据吞吐量的最大化…………………………………………………… 82

8.3  总结……………………………………………………………………………… 86

8.4  习题……………………………………………………………………………… 86

第9章  点模式匹配 ……………………………………………………………………… 87

9.1  问题的表述……………………………………………………………………… 87

9.2  模拟退火框架…………………………………………………………………… 89

9.2.1  编码方案………………………………………………………………… 89

9.2.2  能量函数………………………………………………………………… 90

9.2.3  扰动规则………………………………………………………………… 90

9.2.4  接受规则………………………………………………………………… 90

9.2.5  冷却流程………………………………………………………………… 90

9.2.6  停止准则………………………………………………………………… 91

9.3  进化程序设计…………………………………………………………………… 91

9.3.1  解空间的表示…………………………………………………………… 91

9.3.2  群体空间: 规模、初始化及其利用 …………………………………… 91

9.3.3  适度函数………………………………………………………………… 91

9.3.4  繁殖……………………………………………………………………… 91

9.3.5  遗传算子………………………………………………………………… 92

9.3.6  模拟结果………………………………………………………………… 94

9.4  总结……………………………………………………………………………… 96

第10章  多处理器调度…………………………………………………………………… 97

10.1  模型与定义 …………………………………………………………………… 97

10.2  均场退火 ……………………………………………………………………… 98

10.2.1  MSP 霍普费尔德能量函数…………………………………………… 98

10.2.2  均场近似……………………………………………………………… 100

・Ⅴ・ 10.2.3  MSP 的均场公式 …………………………………………………… 100

10.2.4  数值解法和仿真……………………………………………………… 100

10.3  遗传算法……………………………………………………………………… 102

10.3.1  符号串表示…………………………………………………………… 103

10.3.2  起始群体……………………………………………………………… 103

10.3.3  适度函数……………………………………………………………… 104

10.3.4  遗传操作……………………………………………………………… 104

10.3.5  完整的算法…………………………………………………………… 106

10.3.6  仿真结果……………………………………………………………… 107

10.4  习题…………………………………………………………………………… 108

第11章  作业调度 ……………………………………………………………………… 109

11.1  调度的分类…………………………………………………………………… 110

11.2  JSP 的遗传算法……………………………………………………………… 111

11.2.1  JSP 的编码方式……………………………………………………… 111

11.2.2  调度的生成…………………………………………………………… 112

11.2.3  遗传操作……………………………………………………………… 114

11.3  仿真结果……………………………………………………………………… 115

11.4  习题…………………………………………………………………………… 116

参考文献…………………………………………………………………………………… 117

各词术语中英文对照表(以汉语拼音排序)……………………………………………… 127

・Ⅵ・

前  言

最优化在本质上是一门交叉学科。它对多个学科产生了重大影响,并已成为不同领域中很多工作都不可或缺的工具。传统最优化方法已经十分完善且有多部优秀教材出版,然而一些已被证明在解决全局最优化问题上行之有效的新方法又涌现了出来,例如神经网络、模拟退火、随机机、均场理论和遗传算法等。

本书为高级最优化技术的最新发展,特别是启发式搜索、神经网络、模拟退火、随机机、均场理论和遗传算法,提供一个技术性的描述,并着重强调它们的数学基础、实现方法以及实际应用。这一教材适用于电类、计算机类等专业一年级研究生的教学,也可作为工程技术人员、科研人员及其他专业人员的参考书。本书是过去五年中我们所授几门课程的结晶,也凝聚了我们在这一领域多项交叉学科研究的成果。在过去的十年里,上述高级最优化技术受到越来越多的重视,但是新书却很少出版。绝大多数新的最优化理论及其应用都散见于期刊杂志、技术报告和会议文集。这使得初学入门者难于进行系统学习。我们希望这本书能使读者对这些方法综合了解,从而填补科学文献上的这一空缺。

本书在内容安排上采用了每一章都相对独立的模块式结构,其中第2~6章每章覆盖了一项最优化技术的理论,而第7~11章则侧重于不同范畴里最优化技术的实际应用。每章既可单独学习,又可作为一个大的综合性题目来研究。

我们深深得益于新泽西州理工学院那些在过去的五年中学习了我们的研究生课程“高级最优化技术”和“人工神经网络”的研究生们,尤其是G.Wang, J.Chen,D.Liu,A.Agrawal,Y.Yu,Z.Zhang,A.Arulumbalam,S.Balasekar,J.Li和N.Sezgin。他们这些年来的反馈和评论帮助我们形成了本书现在的样式。我们非常感谢L.Fitton对于编辑此书的帮助以及Kluwer 学术出版社的S.Rumsey在手稿输入方面所提供的支持。最后,我们衷心地表达对Kluwer 学术出版社A.Greene 的谢忱,感谢他对我们完成此书的不断鼓励。

Nirwan Ansari

Edwin Hou

・Ⅶ・