启发式优化算法理论及应用

启发式优化算法是相对于精确算法而言的。一个问题的精确算法，是指求得该问题的精确解，而启发式算法则是基于直观或经验所构造的算法，在可接受的成本(计算时间、占用内存等)下寻找最优解，但不一定能保证所得解的可行性和精确性。启发式算法一般具有严密的理论依据，而不是仅凭专家经验，理论上可在一定时间内找到精确解或近似精确解。

启发式算法的兴起源于实际问题的需要。随着20世纪70年代算法复杂性理论的完善，人们不再强调花费大量的时间求得精确解，只要能在较短的时间内求得相对较好的结果，也可以接受。因此，20世纪80年代初兴起的启发式优化算法在当今得到了巨大的发展。

本书第1章对最优化方法的求解对象即最优化问题的定义及分类进行了介绍，并分析了最优化方法的特点及其分类，再重点介绍最优化方法之一的启发式算法的定义及特点。第2章介绍了遗传算法的思想及特点、设计原则，并重点分析了遗传算法在01背包问题、函数极值问题、旅行商问题、带时间窗的车辆路径问题及机器学习领域中的应用。第3章介绍了蚁群算法的思想及特点，并重点分析了蚁群算法在旅行商问题及函数极值问题中的应用。第4章首先介绍了模拟退火算法的
思想及特点、设计原则，然后介绍了该算法在经典优化问题如旅行商问题、图像处理等问题中的应用，并针对该算法在实际问题如电商物流配送问题、登机口分配问题中的具体应用进行了分析。第5章首先介绍了禁忌搜索算法的基本思想，然后介绍了该算法各个组成模块如初始解、邻域、禁忌表等的设计思路，最后重点分析了禁忌搜索算法在旅行商问题、双层级医疗设施选址问题及机场外航服务人员班型生成问题中的应用。第6章首先介绍了大邻域搜索算法的基本思想，然后重点分析了该算法在路径问题和调度问题中的应用。第7章介绍了变邻域搜索算法的原理及改进策略，然后介绍了该算法在某类优化问题如组合优化问题中的应用，并针对该算法在实际问题如物流配送系统集成优化问题、开放式带时间窗车辆路径问题中的具体应用进行了分析。第8章介绍了迭代局部搜索算法的基本原理及优化策略，并着重分析了该算法在旅行商问题中的应用。第9章介绍了粒子群算法的起源及原理，分析了算法的关键参数，并阐述了该算法在模糊系统设计问题和满载需求可拆分车辆路径问题中的应用。第10章首先介绍了人工免疫算法的基本原理，然后分别介绍了免疫遗传算法、免疫规划算法和免疫策略算法，最后分析了免疫优化算法在物流中心选址问题中的应用。第11章首先介绍了人工神经网络的起源及相关概念，如人工神经元、传递函数； 其次介绍了7种神经网络模型，分别为单层感知机、多层感知机、径向基函数神经网络、自组织竞争人工神经网络、对向传播神经网络、前向神经网络及反馈型神经网络； 然后介绍了神经网络权值的3种混合优化学习策略，分别为BPSA、BPGA、GASA； 最后分析了人工神经网络在组合优化问题中的应用。

本书为湖南工商大学2021年教材建设基金资助项目成果。在本书的编写过程中，受到了与智能优化算法相关的精品课程教材的启发。同时，清华大学出版社的编辑为本书的出版付出了艰辛的努力，在此表示由衷的感谢。

一本好的教材不仅需要不断地修订打磨，也需要编写团队反复地协同沟通，本书编者们将一直致力于提高本书质量。鉴于编者能力水平有限，书中难免有疏漏或不足之处，恳请广大读者批评指正。

邹晔2023年9月

习题答案

程序代码

本书系统、全面地介绍了用于求解**化问题的10种智能启发式算法的基本思想、设计原理及应用案例，分别为遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法、大邻域搜索算法、变邻域搜索算法、迭代局部搜索算法、粒子群算法、人工免疫算法及人工神经网络。 本书可作为高等院校计算机科学与技术、人工智能等理工类相关专业本科生及研究生教材，也可作为物流管理、经济管理等管理类相关专业本科生及研究生教材。

第1章绪论

1.1最优化问题定义及分类

1.1.1最优化问题定义

1.1.2最优化问题分类

1.2最优化方法特点及分类

1.2.1最优化方法特点

1.2.2最优化方法分类

1.3启发式算法定义及特点

1.3.1启发式算法定义

1.3.2启发式算法特点

1.4本章小结

1.5习题

第2章遗传算法

2.1遗传算法思想及特点

2.1.1算法思想

2.1.2算法特点

2.2遗传算子

2.2.1选择算子

2.2.2交叉算子

2.2.3变异算子

2.3遗传算法设计原则

2.3.1适应度和初始群体选取原则

2.3.2参数设计原则

2.4遗传算法的应用

2.4.1遗传算法在01背包问题中的应用

2.4.2遗传算法在函数极值问题中的应用

2.4.3遗传算法在旅行商问题中的应用

2.4.4遗传算法在机器学习中的应用

2.4.5遗传算法在其他领域中的应用

2.5本章小结

2.6习题

第3章蚁群算法

3.1蚁群算法思想及特点

3.1.1算法思想

3.1.2算法特点

3.2蚁群算法的应用

3.2.1蚁群算法在旅行商问题中的应用

3.2.2蚁群算法在函数极值问题中的应用

3.3本章小结

3.4习题

第4章模拟退火算法

4.1模拟退火算法思想及特点

4.1.1算法思想

4.1.2算法特点

4.2模拟退火算法设计原则

4.3模拟退火算法的应用

4.3.1模拟退火算法在旅行商问题中的应用

4.3.2模拟退火算法在电商物流配送问题中的应用

4.3.3模拟退火算法在登机口分配问题中的应用

4.3.4模拟退火算法在多核多用户任务卸载调度问题中的应用

4.3.5模拟退火算法在同时取送货车辆路径问题中的应用

4.5本章小结

4.6习题

第5章禁忌搜索算法

5.1禁忌搜索算法思想及特点

5.1.1算法思想

5.1.2算法特点

5.2禁忌搜索算法设计原则

5.3禁忌搜索算法的应用

5.3.1禁忌搜索算法在旅行商问题中的应用

5.3.2禁忌搜索算法在双层级医疗设施选址问题中的应用

5.3.3禁忌搜索算法在机场外航服务人员班型生成问题中的应用

5.4本章小结

5.5习题

第6章大邻域搜索算法

6.1邻域搜索及超大规模邻域搜索定义

6.1.1邻域搜索定义

6.1.2超大规模邻域搜索定义

6.2大邻域搜索算法介绍

6.3自适应大邻域搜索算法介绍

6.3.1算法思想

6.3.2算法设计原则

6.3.3算法特点

6.4大邻域搜索算法的应用

6.4.1大邻域搜索算法在路径问题中的应用

6.4.2大邻域搜索算法在调度问题中的应用

6.5本章小结

6.6习题

第7章变邻域搜索算法

7.1变邻域搜索算法原理

7.1.1变邻域深度搜索算法原理

7.1.2简化变邻域搜索算法原理

7.1.3基本变邻域搜索算法原理

7.1.4偏态变邻域搜索算法原理

7.1.5变邻域分解搜索算法原理

7.1.6并行变邻域搜索算法原理 

7.2变邻域搜索算法的改进策略 

7.3变邻域搜索算法的应用

7.3.1变邻域搜索算法在组合优化问题中的应用

7.3.2变邻域搜索算法在连续优化问题中的应用

7.3.3变邻域搜索算法在物流配送系统集成优化问题中的应用

7.3.4变邻域搜索算法在开放式带时间窗车辆路径问题中的应用

7.4本章小结

7.5习题

第8章迭代局部搜索算法

8.1迭代局部搜索算法原理

8.2迭代局部搜索算法设计原则

8.2.1初始解设计原则

8.2.2扰动机制设计原则

8.2.3解接受准则设计原则

8.2.4局部搜索设计原则

8.2.5全局优化设计原则

8.3迭代局部搜索算法的应用

8.3.1迭代局部搜索算法在旅行商问题中的应用

8.3.2迭代局部搜索算法在其他问题中的应用

8.4本章小结

8.5习题

第9章粒子群算法

9.1粒子群算法起源

9.2粒子群算法原理

9.2.1原始粒子群算法原理

9.2.2标准粒子群算法原理

9.3粒子群算法参数分析

9.3.1惯性权重分析

9.3.2学习因子分析

9.3.3其他参数分析

9.4粒子群算法的应用

9.4.1粒子群算法在模糊系统设计问题中的应用

9.4.2粒子群算法在满载需求可拆分车辆路径问题中的应用

9.5本章小结

9.6习题

第10章人工免疫算法

10.1人工免疫算法介绍

10.1.1生物免疫系统

10.1.2生物免疫基本原理

10.1.3人工免疫系统及免疫算法

10.1.4人工免疫算法与遗传算法的比较

10.2免疫遗传算法介绍

10.3免疫规划算法介绍

10.4免疫策略算法介绍

10.5免疫优化算法在物流中心选址问题中的应用

10.6本章小结

10.7习题

第11章人工神经网络

11.1人工神经网络起源

11.2人工神经网络概念

11.2.1人工神经元

11.2.2传递函数

11.3神经网络模型

11.3.1单层感知机

11.3.2多层感知机

11.3.3径向基函数神经网络

11.3.4自组织竞争人工神经网络

11.3.5对向传播神经网络

11.3.6反馈型神经网络

11.4神经网络权值的混合优化学习策略

11.4.1BPSA混合学习策略

11.4.2BPGA混合学习策略

11.4.3GASA混合学习策略

11.5人工神经网络在组合优化问题中的应用

11.6本章小结

11.7习题

参考文献

本书系统、全面地介绍了用于求解**化问题的10种智能启发式算法的基本思想、设计原理及应用案例，分别为遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法、大邻域搜索算法、变邻域搜索算法、迭代局部搜索算法、粒子群算法、人工免疫算法及人工神经网络。 本书可作为高等院校计算机科学与技术、人工智能等理工类相关专业本科生及研究生教材，也可作为物流管理、经济管理等管理类相关专业本科生及研究生教材。

本书系统全面地介绍了用于求解最优化问题的10种智能启发式算法，即遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法、大邻域搜索算法、变邻域搜索算法、迭代局部搜索算法、粒子群算法、人工免疫算法以及人工神经网络。本书可作为高等院校管理科学与工程、物流管理、经济管理等管理类相关专业本科生及研究生的教材，也可作为计算机科学与技术、人工智能等理工类相关专业本科生及研究生的教材。