搜索方法論：優(yōu)化與決策支持技術入門教程

第1章概述1
1.1跨學科決策支持： 動力1
1.2本書的結構1
1.3基本概念和底層問題2
附加信息資源7
參考文獻8
第2章經典方法10
2.1引言10
2.2線性規(guī)劃11
2.2.1簡介11
2.2.2線性規(guī)劃的問題形式11
2.2.3對偶性12
2.2.4求解技巧13
2.3分支限界法13
2.3.1簡介13
2.3.2基于部分解的分支限界法15
2.3.3一個推廣20
2.3.4其他問題21
2.4動態(tài)規(guī)劃22
2.4.1簡介22
2.4.2建立DP模型23
2.4.3其他問題27
2.5網絡流規(guī)劃28
2.5.1簡介28
2.5.2最大流問題28
2.5.3最小費用流問題30
2.5.4其他問題34
2.6若干有用的模型34
2.6.1最短路徑問題： 動態(tài)規(guī)劃方法35
2.6.2運輸與指派問題和轉運問題： 網絡流方法36
2.6.3其他有用的模型37
2.7今后的應用領域37
2.7.1預處理和后處理38
2.7.2真混成38
2.7.3雜交39
2.8訣竅39
2.8.1簡介39
2.8.2有關分支限界法的小提示40
2.8.3有關動態(tài)規(guī)劃的小提示40
2.8.4有關網絡流規(guī)劃的小提示41
2.9結論41
附加信息源42
參考文獻43
第3章整數(shù)規(guī)劃45
3.1介紹45
3.1.1設備選址46
3.1.2解決設備選址整數(shù)規(guī)劃問題47
3.1.3整數(shù)規(guī)劃中的難點49
3.2在方程中具有創(chuàng)新性49
3.2.1整數(shù)數(shù)量50
3.2.2二進制決策50
3.2.3固定費用需求51
3.2.4邏輯約束51
3.2.5排序問題52
3.3尋找具有強松弛的公式52
3.4避免對稱55
3.5考慮多約束的公式56
3.6考慮帶多個變量的公式57
3.7修正分支限界法的參數(shù)59
3.7.1問題描述59
3.7.2線性規(guī)劃的求解方法60
3.7.3分支變量選擇60
3.7.4待解子問題選擇60
3.7.5分支方向60
3.7.6容忍度60
3.8訣竅61
3.9結論61
附加信息源61
參考文獻62
第4章遺傳算法64
4.1引言64
4.1.1基本的遺傳算法算子65
4.1.2可勝任遺傳算法69
4.1.3基于效率和/或有效性的遺傳算法改進72
4.2訣竅75
附加信息源76
參考文獻77
第5章遺傳規(guī)劃84
5.1引言84
5.2遺傳規(guī)劃的準備步驟85
5.3遺傳規(guī)劃的執(zhí)行步驟86
5.4運行一個遺傳規(guī)劃的實例92
5.5遺傳規(guī)劃的深入特征95
5.5.1約束的語法結構95
5.5.2自動定義的函數(shù)95
5.5.3自動定義的迭代、循環(huán)、遞歸和存儲96
5.5.4程序結構以及結構改變操作96
5.5.5遺傳規(guī)劃問題的解算機97
5.5.6啟發(fā)式遺傳規(guī)劃97
5.6通過遺傳規(guī)劃生成的人類競爭結果97
5.7未來應用的前景領域100
5.8遺傳規(guī)劃理論100
5.9訣竅103
5.10結論104
附加信息源104
參考文獻106
第6章禁忌搜索110
6.1引言110
6.2示例問題110
6.2.1作業(yè)車間調度問題110
6.2.2選址運輸問題111
6.3基本概念112
6.3.1歷史背景112
6.3.2禁忌搜索112
6.3.3搜索空間與鄰域結構113
6.3.4禁忌114
6.3.5特赦準則115
6.3.6一個簡單禁忌搜索的模板115
6.3.7終止條件116
6.3.8概率禁忌搜索與候選列表116
6.4基本概念的擴展117
6.4.1強化117
6.4.2分散117
6.4.3允許不可行解118
6.4.4替代與輔助目標函數(shù)118
6.5未來應用的前景領域119
6.6訣竅119
6.6.1起步119
6.6.2更多提示120
6.6.3概率禁忌搜索的更多提示120
6.6.4參數(shù)調校和計算測試121
6.7結論121
附加信息源122
參考文獻122
第7章模擬退火126
7.1引言126
7.2局部搜索126
7.3基本模擬退火128
7.4數(shù)學建模130
7.5平衡態(tài)統(tǒng)計132
7.6實際應用135
7.6.1靜態(tài)冷卻進度表136
7.6.2動態(tài)冷卻進度表136
7.7訣竅136
7.8結論138
附加信息源138
參考文獻139
第8章變鄰域搜索142
8.1引言142
8.2預備知識： 文檔編集144
8.3變鄰域下降145
8.4簡化變鄰域搜索147
8.5基本和廣義變鄰域搜索149
8.6偏變鄰域搜索152
8.7變鄰域分解搜索153
8.8性能分析154
8.9有前景的研究領域155
8.10訣竅157
8.10.1起步157
8.10.2更多提示158
8.11結論158
附加信息源159
參考文獻159
第9章約束規(guī)劃162
9.1引言162
9.2推理164
9.3建模165
9.4搜索165
9.4.1擴展166
9.4.2修復167
9.5樣例167
9.6易處理性168
9.6.1理論169
9.6.2實驗169
9.7最優(yōu)化169
9.8算法170
9.8.1管理約束170
9.8.2域和約束傳播170
9.8.3約束和搜索171
9.8.4全局約束172
9.8.5不同的約束行為173
9.8.6擴展和修復搜索173
9.9約束語言174
9.9.1約束邏輯編程174
9.9.2建模語言175
9.10應用175
9.10.1當前的應用領域175
9.10.2在控制、查證和確認中的應用175
9.10.3組合問題的解決176
9.10.4其他的應用177
9.11未來應用的前景領域177
9.11.1動態(tài)約束，軟約束177
9.11.2混合技術177
9.11.3知識獲取和注解177
9.11.4合成模型和算法178
9.11.5分布式處理178
9.11.6不確定性178
9.12訣竅178
9.12.1初始化變量179
9.12.2搜索和傳播179
9.12.3分支和邊界180
9.12.4代碼180
9.12.5引入冗余約束182
9.12.6增加搜索啟發(fā)式算法182
9.12.7使用一個不完備搜索技術182
附加信息源182
參考文獻183
第10章多目標優(yōu)化186
10.1引言186
10.2多目標優(yōu)化的兩個方法188
10.3非支配解和Pareto最優(yōu)解191
10.3.1特殊解191
10.3.2支配的概念192
10.3.3支配關系的性質193
10.3.4Pareto最優(yōu)解193
10.3.5求非支配解的步驟195
10.4多目標優(yōu)化的一些方法197
10.4.1經典方法： 權重求和的方法197
10.4.2經典方法： ε限制方法198
10.4.3多目標進化優(yōu)化方法199
10.4.4樣例的仿真結果201
10.4.5其他的多目標進化算法202
10.5約束處理203
10.6一些應用204
10.6.1航天器軌跡設計204
10.6.2懸臂板設計問題205
10.7訣竅207
10.7.1經典的多目標優(yōu)化207
10.7.2進化多目標優(yōu)化207
10.7.3優(yōu)化后研究209
10.7.4評價一個多目標優(yōu)化算法209
10.8未來方向210
10.9總結211
附加信息源211
參考文獻213
第11章復雜性理論與無免費午餐定理217
11.1引言217
11.2P和NP復雜性217
11.3無免費午餐220
11.3.1無免費午餐： 同一主題的不同變化223
11.3.2無免費午餐與排列閉包223
11.3.3免費午餐定理與可壓縮性226
11.3.4無免費午餐和NP?完全性227
11.3.5評價搜索算法228
11.4訣竅229
11.5當前及未來的研究方向229
11.6結論230
附加信息源230
參考文獻231
第12章機器學習233
12.1引言233
12.1.1學習模型233
12.1.2學習任務和機器學習中的問題234
12.2學習算法綜述235
12.2.1學習決策樹235
12.2.2歸納邏輯編程236
12.2.3貝葉斯學習238
12.2.4強化學習239
12.2.5神經網絡241
12.2.6演化學習244
12.3學習和演化245
12.3.1演化神經網絡245
12.3.2學習規(guī)則的演化247
12.3.3演化神經網絡的一般框架248
12.4未來應用的前景領域249
12.5訣竅250
12.6結論251
附加信息來源252
參考文獻252
第13章人工免疫系統(tǒng)255
13.1前言255
13.2生物免疫系統(tǒng)的概述255
13.2.1免疫網絡理論257
13.2.2消極的選擇機制257
13.2.3克隆選擇原則257
13.3說明性問題258
13.3.1入侵檢測系統(tǒng)258
13.3.2數(shù)據挖掘——協(xié)同過濾和聚類258
13.4人工免疫系統(tǒng)的基本概念259
13.4.1初始化/編碼259
13.4.2相似度或者相關性測度259
13.4.3消極、克隆或近鄰選擇260
13.4.4體細胞突變261
13.5遺傳算法和神經網絡的比較262
13.6人工免疫系統(tǒng)的延伸262
13.6.1獨特型網絡——網絡互動（抑制）262
13.6.2危險理論264
13.7未來應用的前景領域266
13.8訣竅267
13.9結論268
附加信息源268
參考文獻269
第14章群智能271
14.1引言271
14.2蟻群優(yōu)化（ACO）算法271
14.2.1示例1： 基本的ACO和TSP273
14.2.2示例2： 基于種群的ACO和TSP275
14.2.3示例3： ACO解決調度問題276
14.2.4ACO算法的高級屬性278
14.2.5ACO在未來應用中的前景領域280
14.3粒子群優(yōu)化280
14.3.1示例1： 基本的PSO和連續(xù)函數(shù)優(yōu)化281
14.3.2示例2： 離散二進制PSO的子集問題283
14.3.3PSO的高級屬性283
14.3.4PSO未來應用的前景領域286
14.4訣竅287
14.5結論288
額外信息源288
參考文獻289
第15章模糊推理294
15.1引言294
15.2模糊集理論的基本定義295
15.2.1模糊集和隸屬度的概念295
15.2.2隸屬度函數(shù)296
15.2.3模糊集運算299
15.2.4變換算子300
15.2.5模糊集的笛卡兒內積300
15.2.6模糊關系301
15.2.7模糊集合成301
15.2.8模糊蘊含301
15.2.9推理規(guī)則302
15.2.10逆問題302
15.2.11模糊相似度測度302
15.3模糊推理系統(tǒng)的基本結構303
15.3.1去模糊化單元304
15.3.2規(guī)則庫的設計305
15.4案例研究： 模糊控制系統(tǒng)306
15.4.1模糊邏輯控制閉環(huán)306
15.4.2比例積分（PI）和比例微分（PD）形式的模糊邏輯控制器306
15.4.3示例307
15.4.4模糊自適應控制方法310
15.5模型辨識與模糊系統(tǒng)穩(wěn)定性312
15.5.1模糊系統(tǒng)建模312
15.5.2模糊系統(tǒng)的穩(wěn)定性313
15.6訣竅313
15.7結論與展望314
附加信息來源315
參考文獻315
第16章基于粗糙集的決策支持322
16.1引言322
16.2粗糙集基礎323
16.2.1通過示例進行的說明323
16.2.2經典粗糙集方法的正式描述327
16.2.3由粗近似導出的決策規(guī)則329
16.2.4由不可區(qū)分性到相似性330
16.3知識發(fā)現(xiàn)的范式以及先驗知識331
16.4基于支配的粗糙集方法334
16.4.1基于支配錐的粒計算334
16.4.2決策規(guī)則的導出338
16.4.3一個示例340
16.5用于多判據選擇和排名的基于支配的粗糙集方法343
16.5.1作為偏好信息和學習樣本的成對比較表344
16.5.2成對比較表給定的排名不低于和排名低于關系的粗近似345
16.5.3由排名不低于和排名低于關系的粗近似導出決策規(guī)則347
16.5.4將決策規(guī)則用于決策支持347
16.5.5說明性示例348
16.5.6總結350
16.6訣竅351
16.7結論與有前景的未來研究領域352
附加信息源353
參考文獻353
第17章超啟發(fā)式358
17.1超啟發(fā)式的概念358
17.2一個簡單的例子： 裝箱問題360
17.3簡要概述363
17.4一些研究問題363
17.4.1沒有免費午餐363
17.4.2什么是問題族364
17.4.3應該選擇什么啟發(fā)式365
17.4.4應該使用什么搜索算法365
17.4.5在搜索中，如何評估性能365
17.4.6應該尋找什么類型的算法366
17.5未來應用的前景領域366
17.5.1時間表366
17.5.2帶時間窗的車輛路徑367
17.5.3其他前景領域368
17.6訣竅369
17.6.1滑雪旅館問題369
17.6.2構造性方法的簡單框架373
附加信息源374
參考文獻374
第18章近似算法378
18.1引言378
18.2近似策略380
18.2.1預備知識380
18.2.2貪婪方法382
18.2.3序貫算法386
18.2.4隨機化388
18.3近似類一覽389
18.3.1PTAS和FPTAS389
18.3.2APX390
18.3.3PCP簡介391
18.4近似與隨機算法有前景的應用領域391
18.4.1隨機回溯與后門391
18.4.2用于引導完全回溯搜索的近似392
18.4.3平均情況下的復雜度和近似392
18.5訣竅393
18.6結論393
附加信息源394
參考文獻395
第19章適應度曲面398
19.1歷史回溯398
19.2組合優(yōu)化399
19.3數(shù)學描述402
19.3.1鄰域結構402
19.3.2局部最優(yōu)403
19.3.3吸引域404
19.3.4圖表示404
19.3.5拉普拉斯矩陣405
19.3.6圖的特征系統(tǒng)405
19.3.7重組曲面407
19.3.8總結407
19.4統(tǒng)計度量408
19.4.1自相關408
19.4.2最優(yōu)解的數(shù)量408
19.5憑經驗的研究409
19.6未來應用的前景領域411
19.7訣竅411
19.8結論412
附加信息源412
參考文獻413