《全局化——从梯度引领到智能启发》围绕化问题的全局解，用12章内容，详细介绍了5大方向的10多个经典算法。这5大方向分别是梯度算法的多次重启、无导数优化、（元）启发式优化、演化优化和群体智能优化。在介绍算法之外，还系统介绍了如何对化算法进行理论和数值评价，并介绍了数值比较可能产生悖论以及如何消除悖论等前沿研究成果。在《全局化——从梯度引领到智能启发》第12章，还提供了设计和分析化算法的实操指引。《全局化——从梯度引领到智能启发》适合作为数学、计算机、工程、经济、管理等相关学科的高年级本科生和研究生学习化方法的教材，也适合从事化相关工作的研究人员或工程师阅读。

《全局化——从梯度引领到智能启发》不仅系统介绍了5大算法，还介绍了如何对化算法进行理论和数值评价，并介绍了数值比较可能产生悖论以及如何消除悖论等前沿研究成果，内容全面且前沿

全局化方法
——从梯度引领到智能启发
刘群锋 张 宁 编著
清华大学出版社
北 京
内 容 简 介
本书围绕化问题的全局解，用12 章内容，详细介绍了5 大方向的10 多个经典算法。 这5
大方向分别是梯度优化的多次重启、无导数优化、启发式优化、演化优化和群体智能优化。在介绍算法
之外，还系统介绍了如何对化算法进行理论和数值评价，并介绍了数值比较可能产生悖论以及如何
消除悖论等前沿研究成果。在本书第12 章，还提供了设计和分析化算法的实操指引。
本书适合作为数学、计算机、工程、经济、管理等相关学科的高年级本科生和研究生学习化方
法的教材，也适合从事化相关工作的研究人员或工程师阅读。
本书封面贴有清华大学出版社防伪标签，无标签者不得销售。
版权所有，侵权必究。举报：010-62782989, beiqinquan@tup.tsinghua.edu.cn。
图书在版编目 (CIP) 数据
全局化方法 : 从梯度引领到智能启发 / 刘群锋, 张宁编著. - - 北京 : 清华大学出版社,
2025. 8. - - ISBN 978-7-302-69970-5
Ⅰ. O242.23
中国国家版本馆CIP 数据核字第20254KS761 号
责任编辑：陈凯仁
封面设计：刘群锋
责任校对：欧 洋
责任印制：沈 露
出版发行：清华大学出版社
网 址：https://www.tup.com.cn, https://www.wqxuetang.com
地 址：北京清华大学学研大厦A 座 邮 编：100084
社 总 机：010-83470000 邮 购：010-62786544
投稿与读者服务：010-62776969, c-service@tup.tsinghua.edu.cn
质量反馈：010-62772015, zhiliang@tup.tsinghua.edu.cn
印装者：北京鑫海金澳胶印有限公司
经 销：新华书店
开 本：185mm×260mm 印张：27 插页：3 字数：663 千字
版次：2025 年9 月第1 版 印次：2025 年9 月第1 次印刷
定价：94.00 元
产品编号：100676-01
序
全局化方法就是化方法, 加上“全局” 二字是为了强调本书介绍的方法以获取
化问题的全局解为目的, 这一点有别于目前大多数的化方法教材。
化是大自然的固有属性, 例如, 宇宙是朝着熵最大的方向不断演化的; 化也是
人类的不舍追求, 例如, 消费者追求效用最大化, 而厂商追求利润最大化和成本最小化。因
此, 化问题广泛出现在科学研究、工程设计、经济生产、管理实践等人类活动中。正因
如此, 化方法是数学中应用最广泛的分支之一。
有趣的是, 数学领域往往更关注化问题的局部极值, 而不是真正的全局最值。原因
是有很好的性条件来检验某个解是否为局部极值, 却没有合适的数学条件来确认找到
的是否是真正的全局解。于是, 在很长一段时间里, 化方法被分割成两个分支。一
个是数学规划领域, 执着于数学性条件, 依赖真实的或近似的梯度信息, 设计和分析能
收敛到极值的局部化方法。另一个是全局化领域, 由少量(但越来越多) 数学规划
领域的研究人员和大量工程技术以及经济管理领域的研究人员组成, 不局限于梯度引导, 拥
抱各种有益的启发, 执着于开发能找到全局解或其良好近似的算法。后者在算法层面
非常繁荣, 不仅包含如分支定界等经典的确定性全局化算法, 也包含启发式优化、演化
优化和群体智能优化等源于工程技术领域的大量随机性全局优化算法。
由于全局化方法的研究人员来自数学、工程技术和经济管理等多个不同学科, 研
究内容跨度也很大, 导致目前很少有教材全面系统地介绍这些方法及其理论基础。幸运地,
围绕化问题, 本书作者在这些学科方向都有一些研究积累。因此, 本书试图全面系统地
介绍全局化问题及各类求解方法。
本书把全局化方法分成两大类: 优质类是梯度优化的多次重启以及无导数优化,
主要特点是(真实的或近似的) 梯度引导和多次重启, 一般是确定性的; 第二类是启发式优
化、演化优化和群体智能优化, 主要特点是群体搜索和智能启发, 一般是随机性的。在介绍
完这些算法后, 本书另一半篇幅详细介绍如何科学地对化方法进行理论评价和数值评
价, 特别关注关于数值比较可能出现悖论以及如何消除悖论的前沿成果。
本书是《全局化——基于递归深度群体搜索的新方法》(清华大学出版社, 2021 年)
和《全局化——算法评价与数值比较》(清华大学出版社, 2024 年) 的姊妹篇。前两本
书属于学术专著, 重点阐述作者研究团队在全局化领域的研究成果; 本书则属于教材,
提供了对经典算法和重要算法的详细介绍, 也提供了对化算法进行理论评价和数值评
价的系统论述, 还附带了化算法设计与分析的实操指引, 并配有大量习题。
本书共12 章, 除第2 章由张宁撰写外, 其余均由刘群锋撰写。第1 章介绍化问题
的数学模型与基本理论, 剩余11 章分为4 部分。第1 部分包含第2～4 章, 首先介绍数学规
划的经典算法, 然后介绍基于梯度优化的多次重启策略, 最后介绍无导数优化算法。第2 部
分包含第5～7 章, 分别介绍启发式优化、演化优化和群体智能优化。第3 部分包含第8～11
章, 首先介绍化算法的理论评估, 然后介绍化算法数值比较中的三大环节: 测试问
题、数据分析方法、策略选择与悖论消除。第4 部分包含第12 章, 介绍如何设计和分析一
个化算法, 具有实操指引作用。
本书得到了国家自然科学委(项目编号: 61773119, 12271095)、广东省普通高校
重点领域专项(项目编号: 2019KZDZX1005) 和广东省自然科学委(项目编号:
2022A1515010088) 的资助, 在此一并感谢!
本书适合作为数学、计算机、工程、经济、管理等相关学科的高年级本科生和研究生
学习化方法的教材, 也适合从事化相关工作的研究人员或工程师阅读。本书有配
套在线慕课课程和配套微信科普公众号(二维码如下), 可供教师开展教学和同学们自学。
最后, 由于作者水平有限, 欢迎同行朋友和广大读者不吝指出书中可能存在的纰漏和谬
误, 以携作者日后改进, 甚谢!
作者
2024 年12 月
教学设计与学时安排建议

本书包含了10 多个经典化算法的介绍, 也提供了化算法如何开展理论评价和
数值比较的详细介绍。根据不同的教学侧重与要求, 内容和学时安排建议如下:

表1 本书教学设计与学时安排建议

教学侧重(适用对象) 总学时(学分) 主要教学内容与学时安排

理解化算法, 能调用
或简单改进现成优化算法
进行问题求解, 了解算法
有效性和效率的主流评价
(适用一般本科生)
48～54 学时
(3 学分)
第1 章(3～4 学时), 第2 章(6 学时), 第3 章(3～4
学时), 第4 章(7～8 学时)，第5 章(4 学时), 第6 章
(5～6 学时), 第7 章(4～6 学时), 第8 章(4 学时), 第
9 章(2 学时), 第10 章(6 学时), 第12 章(4 学时)
32～36 学时
(2 学分)
第1 章(2 学时), 第2

目 录
第1章 化问题的数学模型与基本理论 1
1.1 化问题及其数学模型 1
1.1.1 化问题举例 1
1.1.2 化问题的数学模型 5
1.1.3 全局化问题与局部化问题 7
1.2 化问题的基本理论 8
1.2.1 全局解的存在性 9
1.2.2 全局解的NP-hard性质 9
1.2.3 局部化问题的性条件 11
1.2.4 全局化问题的性条件 13
1.3 化算法框架初瞰与本书后续安排 15
1.3.1 局部化问题的梯度型算法 15
1.3.2 全局化问题的智能启发类算法 17
1.3.3 全局化与局部化: 特色与融合 18
习题与思考 20
第1部分 梯度优化的多次重启与无导数优化
第2章 基于梯度信息的局部寻优 23
2.1 线搜索方法与下降算法的收敛性 24
2.1.1 线搜索方法 24
2.1.2 下降方法的收敛性 26
2.2 梯度下降法与共轭梯度法 29
2.2.1 梯度下降法 29
2.2.2 随机梯度下降法 34
2.2.3 共轭梯度法 38
2.3 牛顿法与拟牛顿法 47
2.3.1 牛顿法 47
2.3.2 拟牛顿法 50
2.4 约束优化算法 58
2.4.1 罚函数方法 59
2.4.2 增广拉格朗日函数方法 61
习题与思考 63
第3章 局部优化的多次重启 65
3.1 从局部寻优到全局优化 65
3.2 并行式多次重启 67
3.2.1 MultiStart算法 67
3.2.2 数值实验 68
3.3 序列式多次重启 70
3.3.1 GlobalSearch算法 70
3.3.2 散点搜索 72
3.3.3 局部搜索及其监控与重启 75
3.3.4 数值实验 77
习题与思考 81
第4章 直接搜索与无导数优化 83
4.1 直接搜索算法的基本理论 83
4.1.1 从空间的基到正基 84
4.1.2 正基与下降方向 85
4.1.3 正基的构造 86
4.2 直接搜索算法的主流实现 88
4.2.1 罗盘形直接搜索算法 88
4.2.2 单纯形直接搜索算法 93
4.3 采用近似梯度的无导数优化算法: 基本理论 99
4.3.1 插值 99
4.3.2 回归 101
4.3.3 单纯形梯度 102
4.4 采用近似梯度的无导数优化算法: 基本框架 104
4.4.1 线搜索型无导数优化算法 104
4.4.2 信赖域型无导数优化算法 107
4.4.3 点集适定性与数据点选取 108
4.5 全局化问题的无导数优化算法 115
4.5.1 DIRECT算法及其收敛性 115
4.5.2 DIRECT算法的改进 120
4.5.3 DIRECT算法与递归深度群体搜索技术 123
习题与思考 127
第2部分 启发式优化、演化优化与群体智能优化
第5章 启发式优化 131
5.1 启发式与元启发式 131
5.1.1 启发式 131
5.1.2 元启发式 132
5.1.3 元启发式优化算法的发展及分类 132
5.2 模拟退火算法 132
5.2.1 Metropolis抽样过程 133
5.2.2 简单模拟退火算法 134
5.2.3 从退火到再退火 136
5.2.4 渐近收敛性 137
5.2.5 算法的应用 138
5.3 禁忌搜索算法 139
5.3.1 算法理念与伪代码 139
5.3.2 邻域结构与禁忌表 140
5.3.3 收敛性 143
5.3.4 一个应用 144
习题与思考 147
第6章 演化优化 149
6.1 基因算法与基因规划 149
6.1.1 理念及发展简史 149
6.1.2 算法要素及伪代码 150
6.1.3 收敛性 154
6.1.4 基因算法的精炼 160
6.1.5 结构编码与基因规划 164
6.2 演化规划与演化策略 167
6.2.1 演化规划 168
6.2.2 有限状态机及其应用 170
6.2.3 演化策略 172
6.2.4 GA、GP、ES、EP的比较 176
6.3 差分演化与文化演化 178
6.3.1 差分演化 178
6.3.2 文化演化 180
习题与思考 182
第7章 群体智能优化 184
7.1 粒子群优化 184
7.1.1 理念与算法实现 185
7.1.2 动态方程的变化 188
7.1.3 拓扑选择与优化 192
7.1.4 收敛性和稳定性 197
7.2 蚁群优化 202
7.2.1 从蚂蚁到人工蚂蚁 203
7.2.2 蚁群优化算法 204
7.2.3 蚁群优化的理论性质 209
7.3 其他群体智能优化算法 214
7.3.1 烟花算法 214
7.3.2 头脑风暴优化算法 217
7.3.3 鸽群优化算法 220
习题与思考 223
第3部分 算法的理论评价与数值比较
第8章 化算法的理论评估 227
8.1 “稳”: 从稳定性到收敛性 227
8.1.1 化算法的稳定性 228
8.1.2 化算法的收敛性 233
8.2 “快”: 从收敛率到复杂度 234
8.2.1 化算法的收敛率 234
8.2.2 化算法的复杂度 237
8.3 “准”: 准确性与有效性 240
8.3.1 基于搜索空间的准确性与有效性度量 240
8.3.2 基于目标空间的准确性与有效性度量 243
习题与思考 245
第9章 化算法的数值比较 247
9.1 数值比较的必要性与可行性 247
9.1.1 化算法的数值比较是必要的 247
9.1.2 没有免费午餐定理与数值比较的总体可行性 248
9.2 化算法数值比较的流程 253
9.2.1 测试算法与测试问题的选取 254
9.2.2 数值实验与数据收集 255
9.2.3 数据分析方法与数值比较策略 256
9.2.4 结果的汇总与解读 259
9.3 测试问题的代表性度量 261
9.3.1 常用测试问题集 261
9.3.2 测试问题的代表性: 三种定义 263
9.3.3 测试问题的代表性度量: 一种方法框架 264
9.3.4 测试问题的代表性度量: 单目标无约束条件下的实践 267
9.3.5 一个高代表性的测试问题集 270
习题与思考 271
第10章 数值比较中的数据分析方法 272
10.1 描述性统计法与L形曲线法 272
10.1.1 描述性统计法: 用表格呈现数据特征 273
10.1.2 L形曲线法: 用L形曲线呈现原始数据 276
10.2 基于推断统计的数据分析方法 277
10.2.1 非参数检验 278
10.2.2 参数检验 287
10.3 基于累积分布函数的数据分析方法 299
10.3.1 performance profile方法和data profile方法 299
10.3.2 其他基于累积分布函数的数据分析方法 304
习题与思考 307
第11章 数值比较的策略选择与悖论消除 308
11.1 数值比较的策略选择 308
11.1.1 两种比较策略的定义 308
11.1.2 集体比较策略 310
11.1.3 两两比较策略 315
11.1.4 结果汇总中的相对多数规则 317
11.2 比较策略与悖论的发生 319
11.2.1 悖论的实例 319
11.2.2 悖论发生的概率计算: 一些数学铺垫 322
11.2.3 循环排序悖论的发生概率 324
11.2.4 非适者生存悖论的发生概率 327
11.2.5 正常事件的发生概率 330
11.3 序的过滤与悖论的避免 331
11.3.1 悖论的影响及对策 331
11.3.2 基于序的过滤的数据分析方法及其数学模型 334
11.3.3 算法无关的过滤条件与悖论的避免 336
11.4 均值Borda计数法与悖论的消除 344
11.4.1 矩阵降维与化算法的数值比较 345
11.4.2 均值Borda计数法与假设检验中的循环排序消除 348
11.4.3 均值Borda计数法的理论优越性与数值有效性 352
习题与思考 356
第4部分 实操指引篇
第12章 化算法的设计与评价 361
12.1 如何调用现成的算法来求解化问题 361
12.1.1 化工具箱 362
12.1.2 全局化工具箱 373
12.2 如何改进或设计化算法 383
12.2.1 基于多次重启的梯度型算法 384
12.2.2 种群协同型智能优化算法 386
12.3 如何评价一个化算法 387
12.3.1 对化算法进行数值测试 387
12.3.2 数据分析与结果解读 390
12.3.3 理论分析与评价 401
习题与思考 403
参考文献 405