演化學習利用演化算法求解機器學習中的復雜優化問題, 在實踐中取得了許多成功, 但因其缺少堅實的理論基礎, 在很長時期內未獲得機器學習社區的廣泛接受. 本書主要內容為三位作者在這個方向上過去二十年中主要工作的總結.

全書共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