搜索方法论：优化与决策支持技术入门教程

搜索方法论：优化与决策支持技术入门教程
出版时间：2014年版
内容简介
　　各种决策支持系统的应用涉及众多领域，如工业、商业、科学和政府部门。决策支持系统可以用来解决许多实际问题，包括交通调度、生物信息优化、人事调度、医疗诊断、时间表、生产调度和商业决策等。其中，实现决策支持系统的关键是其底层的搜索和优化技术。因此，搜索和优化技术是一个至关重要的研究领域。本书是一本涵盖多个领域，如计算机科学、数学和运筹学的解决各种复杂问题的搜索、优化和决策支持技术的入门教程。本书精心组织，通过19个章节系统介绍了大量经典和最新的优化技术和搜索方法。每章的作者均是相关领域的国际知名专家。第1章是概述，第2章和第3章介绍了一些经典的基于数学的搜索方法，如分支限界法、动态规划、网络流规划、整数规划等。第4章至第8章介绍了一些经典和常用的人工智能方法，包括遗传算法、演化计算、模拟退火、禁忌搜索、变邻域搜索。接着介绍了一些较新的优化技术，包括约束规划、多目标优化、机器学习、人工免疫系统、群体智能、模糊推理、基于粗糙集的决策支持、超启发式和近似算法等。此外，本书还介绍了搜索和优化领域涉及的一些理论知识，如复杂理论、适应值曲面等。本书几乎涵盖了所有经典、实用和目前最新的搜索和优化技术，内容丰富、层次分明、重点突出。每章都附有大量相关参考文献，具有权威性和实用性。作为介绍搜索和优化技术的入门教程，本书非常适合作为高等院校高年级本科生和研究生的教材，并可用作相关领域研究人员的参考资料。
目录
第1章概述1
1.1跨学科决策支持： 动力1
1.2本书的结构1
1.3基本概念和底层问题2
附加信息资源7
参考文献8
第2章经典方法10
2.1引言10
2.2线性规划11
2.2.1简介11
2.2.2线性规划的问题形式11
2.2.3对偶性12
2.2.4求解技巧13
2.3分支限界法13
2.3.1简介13
2.3.2基于部分解的分支限界法15
2.3.3一个推广20
2.3.4其他问题21
2.4动态规划22
2.4.1简介22
2.4.2建立DP模型23
2.4.3其他问题27
2.5网络流规划28
2.5.1简介28
2.5.2最大流问题28
2.5.3最小费用流问题30
2.5.4其他问题34
2.6若干有用的模型34
2.6.1最短路径问题： 动态规划方法35
2.6.2运输与指派问题和转运问题： 网络流方法36
2.6.3其他有用的模型37
2.7今后的应用领域37
2.7.1预处理和后处理38
2.7.2真混成38
2.7.3杂交39
2.8诀窍39
2.8.1简介39
2.8.2有关分支限界法的小提示40
2.8.3有关动态规划的小提示40
2.8.4有关网络流规划的小提示41
2.9结论41
附加信息源42
参考文献43
第3章整数规划45
3.1介绍45
3.1.1设备选址46
3.1.2解决设备选址整数规划问题47
3.1.3整数规划中的难点49
3.2在方程中具有创新性49
3.2.1整数数量50
3.2.2二进制决策50
3.2.3固定费用需求51
3.2.4逻辑约束51
3.2.5排序问题52
3.3寻找具有强松弛的公式52
3.4避免对称55
3.5考虑多约束的公式56
3.6考虑带多个变量的公式57
3.7修正分支限界法的参数59
3.7.1问题描述59
3.7.2线性规划的求解方法60
3.7.3分支变量选择60
3.7.4待解子问题选择60
3.7.5分支方向60
3.7.6容忍度60
3.8诀窍61
3.9结论61
附加信息源61
参考文献62
第4章遗传算法64
4.1引言64
4.1.1基本的遗传算法算子65
4.1.2可胜任遗传算法69
4.1.3基于效率和/或有效性的遗传算法改进72
4.2诀窍75
附加信息源76
参考文献77
第5章遗传规划84
5.1引言84
5.2遗传规划的准备步骤85
5.3遗传规划的执行步骤86
5.4运行一个遗传规划的实例92
5.5遗传规划的深入特征95
5.5.1约束的语法结构95
5.5.2自动定义的函数95
5.5.3自动定义的迭代、循环、递归和存储96
5.5.4程序结构以及结构改变操作96
5.5.5遗传规划问题的解算机97
5.5.6启发式遗传规划97
5.6通过遗传规划生成的人类竞争结果97
5.7未来应用的前景领域100
5.8遗传规划理论100
5.9诀窍103
5.10结论104
附加信息源104
参考文献106
第6章禁忌搜索110
6.1引言110
6.2示例问题110
6.2.1作业车间调度问题110
6.2.2选址运输问题111
6.3基本概念112
6.3.1历史背景112
6.3.2禁忌搜索112
6.3.3搜索空间与邻域结构113
6.3.4禁忌114
6.3.5特赦准则115
6.3.6一个简单禁忌搜索的模板115
6.3.7终止条件116
6.3.8概率禁忌搜索与候选列表116
6.4基本概念的扩展117
6.4.1强化117
6.4.2分散117
6.4.3允许不可行解118
6.4.4替代与辅助目标函数118
6.5未来应用的前景领域119
6.6诀窍119
6.6.1起步119
6.6.2更多提示120
6.6.3概率禁忌搜索的更多提示120
6.6.4参数调校和计算测试121
6.7结论121
附加信息源122
参考文献122
第7章模拟退火126
7.1引言126
7.2局部搜索126
7.3基本模拟退火128
7.4数学建模130
7.5平衡态统计132
7.6实际应用135
7.6.1静态冷却进度表136
7.6.2动态冷却进度表136
7.7诀窍136
7.8结论138
附加信息源138
参考文献139
第8章变邻域搜索142
8.1引言142
8.2预备知识： 文档编集144
8.3变邻域下降145
8.4简化变邻域搜索147
8.5基本和广义变邻域搜索149
8.6偏变邻域搜索152
8.7变邻域分解搜索153
8.8性能分析154
8.9有前景的研究领域155
8.10诀窍157
8.10.1起步157
8.10.2更多提示158
8.11结论158
附加信息源159
参考文献159
第9章约束规划162
9.1引言162
9.2推理164
9.3建模165
9.4搜索165
9.4.1扩展166
9.4.2修复167
9.5样例167
9.6易处理性168
9.6.1理论169
9.6.2实验169
9.7最优化169
9.8算法170
9.8.1管理约束170
9.8.2域和约束传播170
9.8.3约束和搜索171
9.8.4全局约束172
9.8.5不同的约束行为173
9.8.6扩展和修复搜索173
9.9约束语言174
9.9.1约束逻辑编程174
9.9.2建模语言175
9.10应用175
9.10.1当前的应用领域175
9.10.2在控制、查证和确认中的应用175
9.10.3组合问题的解决176
9.10.4其他的应用177
9.11未来应用的前景领域177
9.11.1动态约束，软约束177
9.11.2混合技术177
9.11.3知识获取和注解177
9.11.4合成模型和算法178
9.11.5分布式处理178
9.11.6不确定性178
9.12诀窍178
9.12.1初始化变量179
9.12.2搜索和传播179
9.12.3分支和边界180
9.12.4代码180
9.12.5引入冗余约束182
9.12.6增加搜索启发式算法182
9.12.7使用一个不完备搜索技术182
附加信息源182
参考文献183
第10章多目标优化186
10.1引言186
10.2多目标优化的两个方法188
10.3非支配解和Pareto最优解191
10.3.1特殊解191
10.3.2支配的概念192
10.3.3支配关系的性质193
10.3.4Pareto最优解193
10.3.5求非支配解的步骤195
10.4多目标优化的一些方法197
10.4.1经典方法： 权重求和的方法197
10.4.2经典方法： ε限制方法198
10.4.3多目标进化优化方法199
10.4.4样例的仿真结果201
10.4.5其他的多目标进化算法202
10.5约束处理203
10.6一些应用204
10.6.1航天器轨迹设计204
10.6.2悬臂板设计问题205
10.7诀窍207
10.7.1经典的多目标优化207
10.7.2进化多目标优化207
10.7.3优化后研究209
10.7.4评价一个多目标优化算法209
10.8未来方向210
10.9总结211
附加信息源211
参考文献213
第11章复杂性理论与无免费午餐定理217
11.1引言217
11.2P和NP复杂性217
11.3无免费午餐220
11.3.1无免费午餐： 同一主题的不同变化223
11.3.2无免费午餐与排列闭包223
11.3.3免费午餐定理与可压缩性226
11.3.4无免费午餐和NP?完全性227
11.3.5评价搜索算法228
11.4诀窍229
11.5当前及未来的研究方向229
11.6结论230
附加信息源230
参考文献231
第12章机器学习233
12.1引言233
12.1.1学习模型233
12.1.2学习任务和机器学习中的问题234
12.2学习算法综述235
12.2.1学习决策树235
12.2.2归纳逻辑编程236
12.2.3贝叶斯学习238
12.2.4强化学习239
12.2.5神经网络241
12.2.6演化学习244
12.3学习和演化245
12.3.1演化神经网络245
12.3.2学习规则的演化247
12.3.3演化神经网络的一般框架248
12.4未来应用的前景领域249
12.5诀窍250
12.6结论251
附加信息来源252
参考文献252
第13章人工免疫系统255
13.1前言255
13.2生物免疫系统的概述255
13.2.1免疫网络理论257
13.2.2消极的选择机制257
13.2.3克隆选择原则257
13.3说明性问题258
13.3.1入侵检测系统258
13.3.2数据挖掘——协同过滤和聚类258
13.4人工免疫系统的基本概念259
13.4.1初始化/编码259
13.4.2相似度或者相关性测度259
13.4.3消极、克隆或近邻选择260
13.4.4体细胞突变261
13.5遗传算法和神经网络的比较262
13.6人工免疫系统的延伸262
13.6.1独特型网络——网络互动（抑制）262
13.6.2危险理论264
13.7未来应用的前景领域266
13.8诀窍267
13.9结论268
附加信息源268
参考文献269
第14章群智能271
14.1引言271
14.2蚁群优化（ACO）算法271
14.2.1示例1： 基本的ACO和TSP273
14.2.2示例2： 基于种群的ACO和TSP275
14.2.3示例3： ACO解决调度问题276
14.2.4ACO算法的高级属性278
14.2.5ACO在未来应用中的前景领域280
14.3粒子群优化280
14.3.1示例1： 基本的PSO和连续函数优化281
14.3.2示例2： 离散二进制PSO的子集问题283
14.3.3PSO的高级属性283
14.3.4PSO未来应用的前景领域286
14.4诀窍287
14.5结论288
额外信息源288
参考文献289
第15章模糊推理294
15.1引言294
15.2模糊集理论的基本定义295
15.2.1模糊集和隶属度的概念295
15.2.2隶属度函数296
15.2.3模糊集运算299
15.2.4变换算子300
15.2.5模糊集的笛卡儿内积300
15.2.6模糊关系301
15.2.7模糊集合成301
15.2.8模糊蕴含301
15.2.9推理规则302
15.2.10逆问题302
15.2.11模糊相似度测度302
15.3模糊推理系统的基本结构303
15.3.1去模糊化单元304
15.3.2规则库的设计305
15.4案例研究： 模糊控制系统306
15.4.1模糊逻辑控制闭环306
15.4.2比例积分（PI）和比例微分（PD）形式的模糊逻辑控制器306
15.4.3示例307
15.4.4模糊自适应控制方法310
15.5模型辨识与模糊系统稳定性312
15.5.1模糊系统建模312
15.5.2模糊系统的稳定性313
15.6诀窍313
15.7结论与展望314
附加信息来源315
参考文献315
第16章基于粗糙集的决策支持322
16.1引言322
16.2粗糙集基础323
16.2.1通过示例进行的说明323
16.2.2经典粗糙集方法的正式描述327
16.2.3由粗近似导出的决策规则329
16.2.4由不可区分性到相似性330
16.3知识发现的范式以及先验知识331
16.4基于支配的粗糙集方法334
16.4.1基于支配锥的粒计算334
16.4.2决策规则的导出338
16.4.3一个示例340
16.5用于多判据选择和排名的基于支配的粗糙集方法343
16.5.1作为偏好信息和学习样本的成对比较表344
16.5.2成对比较表给定的排名不低于和排名低于关系的粗近似345
16.5.3由排名不低于和排名低于关系的粗近似导出决策规则347
16.5.4将决策规则用于决策支持347
16.5.5说明性示例348
16.5.6总结350
16.6诀窍351
16.7结论与有前景的未来研究领域352
附加信息源353
参考文献353
第17章超启发式358
17.1超启发式的概念358
17.2一个简单的例子： 装箱问题360
17.3简要概述363
17.4一些研究问题363
17.4.1没有免费午餐363
17.4.2什么是问题族364
17.4.3应该选择什么启发式365
17.4.4应该使用什么搜索算法365
17.4.5在搜索中，如何评估性能365
17.4.6应该寻找什么类型的算法366
17.5未来应用的前景领域366
17.5.1时间表366
17.5.2带时间窗的车辆路径367
17.5.3其他前景领域368
17.6诀窍369
17.6.1滑雪旅馆问题369
17.6.2构造性方法的简单框架373
附加信息源374
参考文献374
第18章近似算法378
18.1引言378
18.2近似策略380
18.2.1预备知识380
18.2.2贪婪方法382
18.2.3序贯算法386
18.2.4随机化388
18.3近似类一览389
18.3.1PTAS和FPTAS389
18.3.2APX390
18.3.3PCP简介391
18.4近似与随机算法有前景的应用领域391
18.4.1随机回溯与后门391
18.4.2用于引导完全回溯搜索的近似392
18.4.3平均情况下的复杂度和近似392
18.5诀窍393
18.6结论393
附加信息源394
参考文献395
第19章适应度曲面398
19.1历史回溯398
19.2组合优化399
19.3数学描述402
19.3.1邻域结构402
19.3.2局部最优403
19.3.3吸引域404
19.3.4图表示404
19.3.5拉普拉斯矩阵405
19.3.6图的特征系统405
19.3.7重组曲面407
19.3.8总结407
19.4统计度量408
19.4.1自相关408
19.4.2最优解的数量408
19.5凭经验的研究409
19.6未来应用的前景领域411
19.7诀窍411
19.8结论412
附加信息源412
参考文献413