目 錄
第1章 化問題的數(shù)學模型與基本理論 1
1.1 化問題及其數(shù)學模型 1
1.1.1 化問題舉例 1
1.1.2 化問題的數(shù)學模型 5
1.1.3 全局化問題與局部化問題 7
1.2 化問題的基本理論 8
1.2.1 全局解的存在性 9
1.2.2 全局解的NP-hard性質(zhì) 9
1.2.3 局部化問題的性條件 11
1.2.4 全局化問題的性條件 13
1.3 化算法框架初瞰與本書后續(xù)安排 15
1.3.1 局部化問題的梯度型算法 15
1.3.2 全局化問題的智能啟發(fā)類算法 17
1.3.3 全局化與局部化: 特色與融合 18
習題與思考 20
第1部分 梯度優(yōu)化的多次重啟與無導數(shù)優(yōu)化
第2章 基于梯度信息的局部尋優(yōu) 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 約束優(yōu)化算法 58
2.4.1 罰函數(shù)方法 59
2.4.2 增廣拉格朗日函數(shù)方法 61
習題與思考 63
第3章 局部優(yōu)化的多次重啟 65
3.1 從局部尋優(yōu)到全局優(yōu)化 65
3.2 并行式多次重啟 67
3.2.1 MultiStart算法 67
3.2.2 數(shù)值實驗 68
3.3 序列式多次重啟 70
3.3.1 GlobalSearch算法 70
3.3.2 散點搜索 72
3.3.3 局部搜索及其監(jiān)控與重啟 75
3.3.4 數(shù)值實驗 77
習題與思考 81
第4章 直接搜索與無導數(shù)優(yōu)化 83
4.1 直接搜索算法的基本理論 83
4.1.1 從空間的基到正基 84
4.1.2 正基與下降方向 85
4.1.3 正基的構(gòu)造 86
4.2 直接搜索算法的主流實現(xiàn) 88
4.2.1 羅盤形直接搜索算法 88
4.2.2 單純形直接搜索算法 93
4.3 采用近似梯度的無導數(shù)優(yōu)化算法: 基本理論 99
4.3.1 插值 99
4.3.2 回歸 101
4.3.3 單純形梯度 102
4.4 采用近似梯度的無導數(shù)優(yōu)化算法: 基本框架 104
4.4.1 線搜索型無導數(shù)優(yōu)化算法 104
4.4.2 信賴域型無導數(shù)優(yōu)化算法 107
4.4.3 點集適定性與數(shù)據(jù)點選取 108
4.5 全局化問題的無導數(shù)優(yōu)化算法 115
4.5.1 DIRECT算法及其收斂性 115
4.5.2 DIRECT算法的改進 120
4.5.3 DIRECT算法與遞歸深度群體搜索技術(shù) 123
習題與思考 127
第2部分 啟發(fā)式優(yōu)化、演化優(yōu)化與群體智能優(yōu)化
第5章 啟發(fā)式優(yōu)化 131
5.1 啟發(fā)式與元啟發(fā)式 131
5.1.1 啟發(fā)式 131
5.1.2 元啟發(fā)式 132
5.1.3 元啟發(fā)式優(yōu)化算法的發(fā)展及分類 132
5.2 模擬退火算法 132
5.2.1 Metropolis抽樣過程 133
5.2.2 簡單模擬退火算法 134
5.2.3 從退火到再退火 136
5.2.4 漸近收斂性 137
5.2.5 算法的應(yīng)用 138
5.3 禁忌搜索算法 139
5.3.1 算法理念與偽代碼 139
5.3.2 鄰域結(jié)構(gòu)與禁忌表 140
5.3.3 收斂性 143
5.3.4 一個應(yīng)用 144
習題與思考 147
第6章 演化優(yōu)化 149
6.1 基因算法與基因規(guī)劃 149
6.1.1 理念及發(fā)展簡史 149
6.1.2 算法要素及偽代碼 150
6.1.3 收斂性 154
6.1.4 基因算法的精煉 160
6.1.5 結(jié)構(gòu)編碼與基因規(guī)劃 164
6.2 演化規(guī)劃與演化策略 167
6.2.1 演化規(guī)劃 168
6.2.2 有限狀態(tài)機及其應(yīng)用 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章 群體智能優(yōu)化 184
7.1 粒子群優(yōu)化 184
7.1.1 理念與算法實現(xiàn) 185
7.1.2 動態(tài)方程的變化 188
7.1.3 拓撲選擇與優(yōu)化 192
7.1.4 收斂性和穩(wěn)定性 197
7.2 蟻群優(yōu)化 202
7.2.1 從螞蟻到人工螞蟻 203
7.2.2 蟻群優(yōu)化算法 204
7.2.3 蟻群優(yōu)化的理論性質(zhì) 209
7.3 其他群體智能優(yōu)化算法 214
7.3.1 煙花算法 214
7.3.2 頭腦風暴優(yōu)化算法 217
7.3.3 鴿群優(yōu)化算法 220
習題與思考 223
第3部分 算法的理論評價與數(shù)值比較
第8章 化算法的理論評估 227
8.1 “穩(wěn)”: 從穩(wěn)定性到收斂性 227
8.1.1 化算法的穩(wěn)定性 228
8.1.2 化算法的收斂性 233
8.2 “快”: 從收斂率到復(fù)雜度 234
8.2.1 化算法的收斂率 234
8.2.2 化算法的復(fù)雜度 237
8.3 “準”: 準確性與有效性 240
8.3.1 基于搜索空間的準確性與有效性度量 240
8.3.2 基于目標空間的準確性與有效性度量 243
習題與思考 245
第9章 化算法的數(shù)值比較 247
9.1 數(shù)值比較的必要性與可行性 247
9.1.1 化算法的數(shù)值比較是必要的 247
9.1.2 沒有免費午餐定理與數(shù)值比較的總體可行性 248
9.2 化算法數(shù)值比較的流程 253
9.2.1 測試算法與測試問題的選取 254
9.2.2 數(shù)值實驗與數(shù)據(jù)收集 255
9.2.3 數(shù)據(jù)分析方法與數(shù)值比較策略 256
9.2.4 結(jié)果的匯總與解讀 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章 數(shù)值比較中的數(shù)據(jù)分析方法 272
10.1 描述性統(tǒng)計法與L形曲線法 272
10.1.1 描述性統(tǒng)計法: 用表格呈現(xiàn)數(shù)據(jù)特征 273
10.1.2 L形曲線法: 用L形曲線呈現(xiàn)原始數(shù)據(jù) 276
10.2 基于推斷統(tǒng)計的數(shù)據(jù)分析方法 277
10.2.1 非參數(shù)檢驗 278
10.2.2 參數(shù)檢驗 287
10.3 基于累積分布函數(shù)的數(shù)據(jù)分析方法 299
10.3.1 performance profile方法和data profile方法 299
10.3.2 其他基于累積分布函數(shù)的數(shù)據(jù)分析方法 304
習題與思考 307
第11章 數(shù)值比較的策略選擇與悖論消除 308
11.1 數(shù)值比較的策略選擇 308
11.1.1 兩種比較策略的定義 308
11.1.2 集體比較策略 310
11.1.3 兩兩比較策略 315
11.1.4 結(jié)果匯總中的相對多數(shù)規(guī)則 317
11.2 比較策略與悖論的發(fā)生 319
11.2.1 悖論的實例 319
11.2.2 悖論發(fā)生的概率計算: 一些數(shù)學鋪墊 322
11.2.3 循環(huán)排序悖論的發(fā)生概率 324
11.2.4 非適者生存悖論的發(fā)生概率 327
11.2.5 正常事件的發(fā)生概率 330
11.3 序的過濾與悖論的避免 331
11.3.1 悖論的影響及對策 331
11.3.2 基于序的過濾的數(shù)據(jù)分析方法及其數(shù)學模型 334
11.3.3 算法無關(guān)的過濾條件與悖論的避免 336
11.4 均值Borda計數(shù)法與悖論的消除 344
11.4.1 矩陣降維與化算法的數(shù)值比較 345
11.4.2 均值Borda計數(shù)法與假設(shè)檢驗中的循環(huán)排序消除 348
11.4.3 均值Borda計數(shù)法的理論優(yōu)越性與數(shù)值有效性 352
習題與思考 356
第4部分 實操指引篇
第12章 化算法的設(shè)計與評價 361
12.1 如何調(diào)用現(xiàn)成的算法來求解化問題 361
12.1.1 化工具箱 362
12.1.2 全局化工具箱 373
12.2 如何改進或設(shè)計化算法 383
12.2.1 基于多次重啟的梯度型算法 384
12.2.2 種群協(xié)同型智能優(yōu)化算法 386
12.3 如何評價一個化算法 387
12.3.1 對化算法進行數(shù)值測試 387
12.3.2 數(shù)據(jù)分析與結(jié)果解讀 390
12.3.3 理論分析與評價 401
習題與思考 403
參考文獻 405