演化学习：理论与算法进展

适读人群 ：机器学习、人工智能、进化计算方面的研究人员和算法设计人员，包括科研院所、高校、企业的研究和高级开发人员，以及相关专业方向的研究生。

机器学习知名学者周志华教授新作；

中国高校知名人工智能研究团队20年攻关的新理论成果；

给强大的演化算法找到“所以然”的理论支撑，指导机器学习优化问题的进一步发展；

关键定理详细证明过程以附录形式给出，以供有余力的读者深挖。

演化学习利用演化算法求解机器学习中的复杂优化问题, 在实践中取得了许多成功, 但因其缺少坚实的理论基础, 在很长时期内未获得机器学习社区的广泛接受. 本书主要内容为三位作者在这个方向上过去二十年中主要工作的总结.

全书共18 章, 分为四个部分: 第一部分(第1～2 章) 简要介绍演化学习和一些关于理论研究的预备知识; 第二部分(第3～6章) 介绍用于分析运行时间复杂度和逼近能力这两个演化学习的基本理论性质的通用工具; 第三部分(第7～12 章) 介绍演化学习关键因素对算法性能影响的一系列理论结果, 包括交叉算子、解的表示、非精确适应度评估、种群的影响等; 第四部分(第13～18 章) 介绍一系列基于理论结果启发的具有一定理论保障的演化学习算法.

本书适合对演化学习感兴趣的研究人员、学生和实践者阅读. 书中第二部分内容或可为有兴趣进一步探索演化学习理论基础的读者提供分析工具, 第三部分内容或有助于读者进一步理解演化学习过程并为新算法设计提供启发, 第四部分内容或可为读者解决一些现实机器学习问题提供新的算法方案.

周志华，南京大学计算机科学与技术系主任、人工智能学院院长、计算机软件新技术国家重点实验室常务副主任、机器学习与数据挖掘研究所（LAMDA）所长。ACM/AAAS/AAAI/IEEE/IAPR/IET/CCF/CAAI会士，欧洲科学院外籍院士。中国计算机学会常务理事、中国人工智能学会副理事长。

周志华教授主要从事人工智能、机器学习、数据挖掘等领域的研究工作。著有《机器学习》（西瓜书）等广受好评的著作，在本领域顶刊和顶会发表论文两百余篇，被引五万余次。现任AI Magazine顾问，Frontiers of Computer Science（FCS）、Artificial Intelligence等国内外知名期刊主编、副主编、编委等；也担任IJCAI理事会成员(2018-2023)，曾担任IJCAI顾问委员会委员、IJCAI 2021程序委员会主席、AAAI 2019程序委员会主席等会议职务。

俞扬，南京大学计算机科学与技术系和LAMDA教授，博导，主要研究领域为人工智能、机器学习、强化学习。

曾获2013年全国优秀博士学位论文奖。发表论文40余篇，包括多篇人工智能、机器学习和数据挖掘国际顶级期刊和顶级会议论文，受邀在IJCAI'18做Early Career Spotlight演讲、在IEEE ICA'17做主旨报告。入选2018年全球AI's 10 to Watch，获2018 PAKDD Early Career Award，并任FCS、Artificial Intelligence等多个一流期刊评审人和IJCAI、ICPR等会议领域主席、程序委员。

钱超，南京大学人工智能学院副教授、博导，国家优青。目前主要关注演化算法理论分析、安全演化算法设计与演化学习。作为第一作者在国际一流期刊和会议上发表二十余篇论文。担任IEEE计算智能分会生物启发计算理论基础任务组主席、IEEE演化计算技术委员会委员、中国人工智能学会青工委副秘书长、Memetic Computing编委、JCST和FCS青年副编。获ACM GECCO’11最佳理论论文奖、IDEAL’16 最佳论文奖，博士论文获中国人工智能学会、江苏省和南京大学优秀博士论文奖。

序 i

主要符号表　iii

第一部分　绪论与预备知识　1

第　1 章 绪论　3

1.1　机器学习　3

1.2　演化学习　4

1.3　多目标优化　6

1.4　本书组织　8

第　2 章 预备知识　9

2.1　演化算法　9

2.2　伪布尔函数　12

2.3　运行时间复杂度　15

2.4　马尔可夫链建模　16

2.5　分析工具　18

第二部分　分析方法　23

第　3 章 运行时间分析: 收敛分析法　25

3.1　收敛分析框架　25

3.2　收敛分析应用例释　29

3.3　小结　33

第　4 章 运行时间分析: 调换分析法　35

4.1　调换分析框架　35

4.2　调换分析应用例释　40

4.3　小结　43

第　5 章 运行时间分析方法的比较　45

5.1　分析方法的形式化　45

5.2　调换分析与适应层分析　47

5.3　调换分析与漂移分析　50

5.4　调换分析与收敛分析　55

5.5　分析方法综论　58

5.6　小结　59

第　6 章 近似分析　61

6.1　SEIP 框架　62

6.2　SEIP 应用例释　67

6.3　小结　70

第三部分　理论透视　71

第　7 章 边界问题　73

7.1　边界问题辨识　74

7.2　案例分析　76

7.3　小结　80

第　8 章 交叉算子　81

8.1　交叉与变异　82

8.2　采用交叉算子的多目标演化算法　83

8.3　案例分析　86

8.4　实验验证　92

8.5　小结　94

第　9 章 解的表示　95

9.1　遗传编程之解表示　96

9.2　案例分析: 最大匹配　98

9.3　案例分析: 最小生成树　103

9.4　实验验证　109

9.5　小结　111

第　10 章 非精确适应度评估　113

10.1　带噪优化　114

10.2　带噪适应度的影响　115

10.3　抗噪: 阈值选择　119

10.4　抗噪: 抽样　124

10.5　实验验证　130

10.6　小结　134

第　11 章 种群　135

11.1　种群的影响　136

11.2　种群对噪声的鲁棒性　139

11.3　小结　151

第　12 章 约束优化　153

12.1　不可行解的影响　154

12.2　帕累托优化的效用　160

12.3　小结　170

第四部分　学习算法　171

第　13 章 选择性集成　173

13.1　选择性集成　173

13.2　POSE 算法　175

13.3　理论分析　177

13.4　实验测试　182

13.5　小结　188

第　14 章 子集选择　189

14.1　子集选择　190

14.2　POSS 算法　194

14.3　理论分析　195

14.4　实验测试　199

14.5　小结　203

第　15 章 子集选择: 次模最大化　205

15.1　单调 次模函数最大化　206

15.2　PO SM 算法　210

15.3　理论分析　212

15.4　实验测试　216

15.5　小结　223

第　16 章 子集选择: 比率最小化　225

16.1　单调次模函数的比率最小化　226

16.2　PORM 算法　228

16.3　理论分析　230

16.4　实验测试　235

16.5　小结　236

第　17 章 子集选择: 噪声　237

17.1　带噪子集选择　238

17.2　PONSS 算法　244

17.3　理论分析　245

17.4　实验测试　248

17.5　小结　250

第　18 章 子集选择: 加速　251

18.1　PPOSS 算法　251

18.2　理论分析　253

18.3　实验测试　256

18.4　小结　258

附录　A: 证明　259

参考文献　299