搜索方法论

第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

各种决策支持系统的应用涉及众多领域，如工业、商业、科学和政府部门。决策支持系统可以用来解决许多实际问题，包括交通调度、生物信息优化、人事调度、医疗诊断、时间表、生产调度和商业决策等。其中，实现决策支持系统的关键是其底层的搜索和优化技术。因此，搜索和优化技术是一个至关重要的研究领域。 　　伯克、肯德尔所著的《搜索方法论--优化与决策支持技术入门教程》是一本涵盖多个领域，如计算机科学、数学和运筹学的解决各种复杂问题的搜索、优化和决策支持技术的入门教程。本书精心组织，通过19个章节系统介绍了大量经典和最新的优化技术和搜索方法。每章的作者均是相关领域的国际知名专家。 　　第1章是概述，第2章和第3章介绍了一些经典的基于数学的搜索方法，如分支限界法、动态规划、网络流规划、整数规划等。第4章至第8章介绍了一些经典和常用的人工智能方法，包括遗传算法、演化计算、模拟退火、禁忌搜索、变邻域搜索。接着介绍了一些较新的优化技术，包括约束规划、多目标优化、机器学习、人工免疫系统、群体智能、模糊推理、基于粗糙集的决策支持、超启发式和近似算法等。此外，本书还介绍了搜索和优化领域涉及的一些理论知识，如复杂理论、适应值曲面等。 　　本书几乎涵盖了所有经典、实用和目前最新的搜索和优化技术，内容丰富、层次分明、重点突出。每章都附有大量相关参考文献，具有权威性和实用性。 　　作为介绍搜索和优化技术的入门教程，本书非常适合作为高等院校高年级本科生和研究生的教材，并可用作相关领域研究人员的参考资料。

几乎涵盖了所有经典、实用和目前最新的搜索和优化技术，内容丰富、层次分明、重点突出。每章都附有大量相关参考文献，具有权威性和实用性。作为介绍搜索和优化技术的入门教程，《世界著名计算机教材精选·搜索方法论:优化与决策支持技术入门教程》非常适合作为高等院校高年级本科生和研究生的教材，并可用作相关领域研究人员的参考资料。