目   录

第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