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

第1章概述1
1.1跨學(xué)科決策支持： 動力1
1.2本書的結(jié)構(gòu)1
1.3基本概念和底層問題2
附加信息資源7
參考文獻8
第2章經(jīng)典方法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網(wǎng)絡(luò)流規(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運輸與指派問題和轉(zhuǎn)運問題： 網(wǎng)絡(luò)流方法36
2.6.3其他有用的模型37
2.7今后的應(yīng)用領(lǐng)域37
2.7.1預(yù)處理和后處理38
2.7.2真混成38
2.7.3雜交39
2.8訣竅39
2.8.1簡介39
2.8.2有關(guān)分支限界法的小提示40
2.8.3有關(guān)動態(tài)規(guī)劃的小提示40
2.8.4有關(guān)網(wǎng)絡(luò)流規(guī)劃的小提示41
2.9結(jié)論41
附加信息源42
參考文獻43
第3章整數(shù)規(guī)劃45
3.1介紹45
3.1.1設(shè)備選址46
3.1.2解決設(shè)備選址整數(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結(jié)論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ī)劃的準(zhǔn)備步驟85
5.3遺傳規(guī)劃的執(zhí)行步驟86
5.4運行一個遺傳規(guī)劃的實例92
5.5遺傳規(guī)劃的深入特征95
5.5.1約束的語法結(jié)構(gòu)95
5.5.2自動定義的函數(shù)95
5.5.3自動定義的迭代、循環(huán)、遞歸和存儲96
5.5.4程序結(jié)構(gòu)以及結(jié)構(gòu)改變操作96
5.5.5遺傳規(guī)劃問題的解算機97
5.5.6啟發(fā)式遺傳規(guī)劃97
5.6通過遺傳規(guī)劃生成的人類競爭結(jié)果97
5.7未來應(yīng)用的前景領(lǐng)域100
5.8遺傳規(guī)劃理論100
5.9訣竅103
5.10結(jié)論104
附加信息源104
參考文獻106
第6章禁忌搜索110
6.1引言110
6.2示例問題110
6.2.1作業(yè)車間調(diào)度問題110
6.2.2選址運輸問題111
6.3基本概念112
6.3.1歷史背景112
6.3.2禁忌搜索112
6.3.3搜索空間與鄰域結(jié)構(gòu)113
6.3.4禁忌114
6.3.5特赦準(zhǔn)則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替代與輔助目標(biāo)函數(shù)118
6.5未來應(yīng)用的前景領(lǐng)域119
6.6訣竅119
6.6.1起步119
6.6.2更多提示120
6.6.3概率禁忌搜索的更多提示120
6.6.4參數(shù)調(diào)校和計算測試121
6.7結(jié)論121
附加信息源122
參考文獻122
第7章模擬退火126
7.1引言126
7.2局部搜索126
7.3基本模擬退火128
7.4數(shù)學(xué)建模130
7.5平衡態(tài)統(tǒng)計132
7.6實際應(yīng)用135
7.6.1靜態(tài)冷卻進度表136
7.6.2動態(tài)冷卻進度表136
7.7訣竅136
7.8結(jié)論138
附加信息源138
參考文獻139
第8章變鄰域搜索142
8.1引言142
8.2預(yù)備知識： 文檔編集144
8.3變鄰域下降145
8.4簡化變鄰域搜索147
8.5基本和廣義變鄰域搜索149
8.6偏變鄰域搜索152
8.7變鄰域分解搜索153
8.8性能分析154
8.9有前景的研究領(lǐng)域155
8.10訣竅157
8.10.1起步157
8.10.2更多提示158
8.11結(jié)論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修復(fù)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擴展和修復(fù)搜索173
9.9約束語言174
9.9.1約束邏輯編程174
9.9.2建模語言175
9.10應(yīng)用175
9.10.1當(dāng)前的應(yīng)用領(lǐng)域175
9.10.2在控制、查證和確認中的應(yīng)用175
9.10.3組合問題的解決176
9.10.4其他的應(yīng)用177
9.11未來應(yīng)用的前景領(lǐng)域177
9.11.1動態(tài)約束，軟約束177
9.11.2混合技術(shù)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使用一個不完備搜索技術(shù)182
附加信息源182
參考文獻183
第10章多目標(biāo)優(yōu)化186
10.1引言186
10.2多目標(biāo)優(yōu)化的兩個方法188
10.3非支配解和Pareto最優(yōu)解191
10.3.1特殊解191
10.3.2支配的概念192
10.3.3支配關(guān)系的性質(zhì)193
10.3.4Pareto最優(yōu)解193
10.3.5求非支配解的步驟195
10.4多目標(biāo)優(yōu)化的一些方法197
10.4.1經(jīng)典方法： 權(quán)重求和的方法197
10.4.2經(jīng)典方法： ε限制方法198
10.4.3多目標(biāo)進化優(yōu)化方法199
10.4.4樣例的仿真結(jié)果201
10.4.5其他的多目標(biāo)進化算法202
10.5約束處理203
10.6一些應(yīng)用204
10.6.1航天器軌跡設(shè)計204
10.6.2懸臂板設(shè)計問題205
10.7訣竅207
10.7.1經(jīng)典的多目標(biāo)優(yōu)化207
10.7.2進化多目標(biāo)優(yōu)化207
10.7.3優(yōu)化后研究209
10.7.4評價一個多目標(biāo)優(yōu)化算法209
10.8未來方向210
10.9總結(jié)211
附加信息源211
參考文獻213
第11章復(fù)雜性理論與無免費午餐定理217
11.1引言217
11.2P和NP復(fù)雜性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當(dāng)前及未來的研究方向229
11.6結(jié)論230
附加信息源230
參考文獻231
第12章機器學(xué)習(xí)233
12.1引言233
12.1.1學(xué)習(xí)模型233
12.1.2學(xué)習(xí)任務(wù)和機器學(xué)習(xí)中的問題234
12.2學(xué)習(xí)算法綜述235
12.2.1學(xué)習(xí)決策樹235
12.2.2歸納邏輯編程236
12.2.3貝葉斯學(xué)習(xí)238
12.2.4強化學(xué)習(xí)239
12.2.5神經(jīng)網(wǎng)絡(luò)241
12.2.6演化學(xué)習(xí)244
12.3學(xué)習(xí)和演化245
12.3.1演化神經(jīng)網(wǎng)絡(luò)245
12.3.2學(xué)習(xí)規(guī)則的演化247
12.3.3演化神經(jīng)網(wǎng)絡(luò)的一般框架248
12.4未來應(yīng)用的前景領(lǐng)域249
12.5訣竅250
12.6結(jié)論251
附加信息來源252
參考文獻252
第13章人工免疫系統(tǒng)255
13.1前言255
13.2生物免疫系統(tǒng)的概述255
13.2.1免疫網(wǎng)絡(luò)理論257
13.2.2消極的選擇機制257
13.2.3克隆選擇原則257
13.3說明性問題258
13.3.1入侵檢測系統(tǒng)258
13.3.2數(shù)據(jù)挖掘——協(xié)同過濾和聚類258
13.4人工免疫系統(tǒng)的基本概念259
13.4.1初始化/編碼259
13.4.2相似度或者相關(guān)性測度259
13.4.3消極、克隆或近鄰選擇260
13.4.4體細胞突變261
13.5遺傳算法和神經(jīng)網(wǎng)絡(luò)的比較262
13.6人工免疫系統(tǒng)的延伸262
13.6.1獨特型網(wǎng)絡(luò)——網(wǎng)絡(luò)互動（抑制）262
13.6.2危險理論264
13.7未來應(yīng)用的前景領(lǐng)域266
13.8訣竅267
13.9結(jié)論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解決調(diào)度問題276
14.2.4ACO算法的高級屬性278
14.2.5ACO在未來應(yīng)用中的前景領(lǐng)域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未來應(yīng)用的前景領(lǐng)域286
14.4訣竅287
14.5結(jié)論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模糊集的笛卡兒內(nèi)積300
15.2.6模糊關(guān)系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)的基本結(jié)構(gòu)303
15.3.1去模糊化單元304
15.3.2規(guī)則庫的設(shè)計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模糊自適應(yīng)控制方法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結(jié)論與展望314
附加信息來源315
參考文獻315
第16章基于粗糙集的決策支持322
16.1引言322
16.2粗糙集基礎(chǔ)323
16.2.1通過示例進行的說明323
16.2.2經(jīng)典粗糙集方法的正式描述327
16.2.3由粗近似導(dǎo)出的決策規(guī)則329
16.2.4由不可區(qū)分性到相似性330
16.3知識發(fā)現(xiàn)的范式以及先驗知識331
16.4基于支配的粗糙集方法334
16.4.1基于支配錐的粒計算334
16.4.2決策規(guī)則的導(dǎo)出338
16.4.3一個示例340
16.5用于多判據(jù)選擇和排名的基于支配的粗糙集方法343
16.5.1作為偏好信息和學(xué)習(xí)樣本的成對比較表344
16.5.2成對比較表給定的排名不低于和排名低于關(guān)系的粗近似345
16.5.3由排名不低于和排名低于關(guān)系的粗近似導(dǎo)出決策規(guī)則347
16.5.4將決策規(guī)則用于決策支持347
16.5.5說明性示例348
16.5.6總結(jié)350
16.6訣竅351
16.7結(jié)論與有前景的未來研究領(lǐng)域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應(yīng)該選擇什么啟發(fā)式365
17.4.4應(yīng)該使用什么搜索算法365
17.4.5在搜索中，如何評估性能365
17.4.6應(yīng)該尋找什么類型的算法366
17.5未來應(yīng)用的前景領(lǐng)域366
17.5.1時間表366
17.5.2帶時間窗的車輛路徑367
17.5.3其他前景領(lǐng)域368
17.6訣竅369
17.6.1滑雪旅館問題369
17.6.2構(gòu)造性方法的簡單框架373
附加信息源374
參考文獻374
第18章近似算法378
18.1引言378
18.2近似策略380
18.2.1預(yù)備知識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近似與隨機算法有前景的應(yīng)用領(lǐng)域391
18.4.1隨機回溯與后門391
18.4.2用于引導(dǎo)完全回溯搜索的近似392
18.4.3平均情況下的復(fù)雜度和近似392
18.5訣竅393
18.6結(jié)論393
附加信息源394
參考文獻395
第19章適應(yīng)度曲面398
19.1歷史回溯398
19.2組合優(yōu)化399
19.3數(shù)學(xué)描述402
19.3.1鄰域結(jié)構(gòu)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總結(jié)407
19.4統(tǒng)計度量408
19.4.1自相關(guān)408
19.4.2最優(yōu)解的數(shù)量408
19.5憑經(jīng)驗的研究409
19.6未來應(yīng)用的前景領(lǐng)域411
19.7訣竅411
19.8結(jié)論412
附加信息源412
參考文獻413