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

第1章概述1
1.1跨學(xué)科決策支持： 動(dòng)力1
1.2本書的結(jié)構(gòu)1
1.3基本概念和底層問題2
附加信息資源7
參考文獻(xiàn)8
第2章經(jīng)典方法10
2.1引言10
2.2線性規(guī)劃11
2.2.1簡(jiǎn)介11
2.2.2線性規(guī)劃的問題形式11
2.2.3對(duì)偶性12
2.2.4求解技巧13
2.3分支限界法13
2.3.1簡(jiǎn)介13
2.3.2基于部分解的分支限界法15
2.3.3一個(gè)推廣20
2.3.4其他問題21
2.4動(dòng)態(tài)規(guī)劃22
2.4.1簡(jiǎn)介22
2.4.2建立DP模型23
2.4.3其他問題27
2.5網(wǎng)絡(luò)流規(guī)劃28
2.5.1簡(jiǎn)介28
2.5.2最大流問題28
2.5.3最小費(fèi)用流問題30
2.5.4其他問題34
2.6若干有用的模型34
2.6.1最短路徑問題： 動(dòng)態(tài)規(guī)劃方法35
2.6.2運(yùn)輸與指派問題和轉(zhuǎn)運(yù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簡(jiǎn)介39
2.8.2有關(guān)分支限界法的小提示40
2.8.3有關(guān)動(dòng)態(tài)規(guī)劃的小提示40
2.8.4有關(guān)網(wǎng)絡(luò)流規(guī)劃的小提示41
2.9結(jié)論41
附加信息源42
參考文獻(xiàn)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ī)劃中的難點(diǎn)49
3.2在方程中具有創(chuàng)新性49
3.2.1整數(shù)數(shù)量50
3.2.2二進(jìn)制決策50
3.2.3固定費(fèi)用需求51
3.2.4邏輯約束51
3.2.5排序問題52
3.3尋找具有強(qiáng)松弛的公式52
3.4避免對(duì)稱55
3.5考慮多約束的公式56
3.6考慮帶多個(gè)變量的公式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
參考文獻(xiàn)62
第4章遺傳算法64
4.1引言64
4.1.1基本的遺傳算法算子65
4.1.2可勝任遺傳算法69
4.1.3基于效率和/或有效性的遺傳算法改進(jìn)72
4.2訣竅75
附加信息源76
參考文獻(xiàn)77
第5章遺傳規(guī)劃84
5.1引言84
5.2遺傳規(guī)劃的準(zhǔn)備步驟85
5.3遺傳規(guī)劃的執(zhí)行步驟86
5.4運(yùn)行一個(gè)遺傳規(guī)劃的實(shí)例92
5.5遺傳規(guī)劃的深入特征95
5.5.1約束的語(yǔ)法結(jié)構(gòu)95
5.5.2自動(dòng)定義的函數(shù)95
5.5.3自動(dòng)定義的迭代、循環(huán)、遞歸和存儲(chǔ)96
5.5.4程序結(jié)構(gòu)以及結(jié)構(gòu)改變操作96
5.5.5遺傳規(guī)劃問題的解算機(jī)97
5.5.6啟發(fā)式遺傳規(guī)劃97
5.6通過遺傳規(guī)劃生成的人類競(jìng)爭(zhēng)結(jié)果97
5.7未來(lái)應(yīng)用的前景領(lǐng)域100
5.8遺傳規(guī)劃理論100
5.9訣竅103
5.10結(jié)論104
附加信息源104
參考文獻(xiàn)106
第6章禁忌搜索110
6.1引言110
6.2示例問題110
6.2.1作業(yè)車間調(diào)度問題110
6.2.2選址運(yùn)輸問題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一個(gè)簡(jiǎn)單禁忌搜索的模板115
6.3.7終止條件116
6.3.8概率禁忌搜索與候選列表116
6.4基本概念的擴(kuò)展117
6.4.1強(qiáng)化117
6.4.2分散117
6.4.3允許不可行解118
6.4.4替代與輔助目標(biāo)函數(shù)118
6.5未來(lái)應(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)校和計(jì)算測(cè)試121
6.7結(jié)論121
附加信息源122
參考文獻(xiàn)122
第7章模擬退火126
7.1引言126
7.2局部搜索126
7.3基本模擬退火128
7.4數(shù)學(xué)建模130
7.5平衡態(tài)統(tǒng)計(jì)132
7.6實(shí)際應(yīng)用135
7.6.1靜態(tài)冷卻進(jìn)度表136
7.6.2動(dòng)態(tài)冷卻進(jìn)度表136
7.7訣竅136
7.8結(jié)論138
附加信息源138
參考文獻(xiàn)139
第8章變鄰域搜索142
8.1引言142
8.2預(yù)備知識(shí)： 文檔編集144
8.3變鄰域下降145
8.4簡(jiǎn)化變鄰域搜索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
參考文獻(xiàn)159
第9章約束規(guī)劃162
9.1引言162
9.2推理164
9.3建模165
9.4搜索165
9.4.1擴(kuò)展166
9.4.2修復(fù)167
9.5樣例167
9.6易處理性168
9.6.1理論169
9.6.2實(shí)驗(yàn)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擴(kuò)展和修復(fù)搜索173
9.9約束語(yǔ)言174
9.9.1約束邏輯編程174
9.9.2建模語(yǔ)言175
9.10應(yīng)用175
9.10.1當(dāng)前的應(yīng)用領(lǐng)域175
9.10.2在控制、查證和確認(rèn)中的應(yīng)用175
9.10.3組合問題的解決176
9.10.4其他的應(yīng)用177
9.11未來(lái)應(yīng)用的前景領(lǐng)域177
9.11.1動(dòng)態(tài)約束，軟約束177
9.11.2混合技術(shù)177
9.11.3知識(shí)獲取和注解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使用一個(gè)不完備搜索技術(shù)182
附加信息源182
參考文獻(xiàn)183
第10章多目標(biāo)優(yōu)化186
10.1引言186
10.2多目標(biāo)優(yōu)化的兩個(gè)方法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)進(jìn)化優(yōu)化方法199
10.4.4樣例的仿真結(jié)果201
10.4.5其他的多目標(biāo)進(jìn)化算法202
10.5約束處理203
10.6一些應(yīng)用204
10.6.1航天器軌跡設(shè)計(jì)204
10.6.2懸臂板設(shè)計(jì)問題205
10.7訣竅207
10.7.1經(jīng)典的多目標(biāo)優(yōu)化207
10.7.2進(jìn)化多目標(biāo)優(yōu)化207
10.7.3優(yōu)化后研究209
10.7.4評(píng)價(jià)一個(gè)多目標(biāo)優(yōu)化算法209
10.8未來(lái)方向210
10.9總結(jié)211
附加信息源211
參考文獻(xiàn)213
第11章復(fù)雜性理論與無(wú)免費(fèi)午餐定理217
11.1引言217
11.2P和NP復(fù)雜性217
11.3無(wú)免費(fèi)午餐220
11.3.1無(wú)免費(fèi)午餐： 同一主題的不同變化223
11.3.2無(wú)免費(fèi)午餐與排列閉包223
11.3.3免費(fèi)午餐定理與可壓縮性226
11.3.4無(wú)免費(fèi)午餐和NP?完全性227
11.3.5評(píng)價(jià)搜索算法228
11.4訣竅229
11.5當(dāng)前及未來(lái)的研究方向229
11.6結(jié)論230
附加信息源230
參考文獻(xiàn)231
第12章機(jī)器學(xué)習(xí)233
12.1引言233
12.1.1學(xué)習(xí)模型233
12.1.2學(xué)習(xí)任務(wù)和機(jī)器學(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強(qiáng)化學(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未來(lái)應(yīng)用的前景領(lǐng)域249
12.5訣竅250
12.6結(jié)論251
附加信息來(lái)源252
參考文獻(xiàn)252
第13章人工免疫系統(tǒng)255
13.1前言255
13.2生物免疫系統(tǒng)的概述255
13.2.1免疫網(wǎng)絡(luò)理論257
13.2.2消極的選擇機(jī)制257
13.2.3克隆選擇原則257
13.3說(shuō)明性問題258
13.3.1入侵檢測(cè)系統(tǒng)258
13.3.2數(shù)據(jù)挖掘——協(xié)同過濾和聚類258
13.4人工免疫系統(tǒng)的基本概念259
13.4.1初始化/編碼259
13.4.2相似度或者相關(guān)性測(cè)度259
13.4.3消極、克隆或近鄰選擇260
13.4.4體細(xì)胞突變261
13.5遺傳算法和神經(jīng)網(wǎng)絡(luò)的比較262
13.6人工免疫系統(tǒng)的延伸262
13.6.1獨(dú)特型網(wǎng)絡(luò)——網(wǎng)絡(luò)互動(dòng)（抑制）262
13.6.2危險(xiǎn)理論264
13.7未來(lái)應(yīng)用的前景領(lǐng)域266
13.8訣竅267
13.9結(jié)論268
附加信息源268
參考文獻(xiàn)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算法的高級(jí)屬性278
14.2.5ACO在未來(lái)應(yīng)用中的前景領(lǐng)域280
14.3粒子群優(yōu)化280
14.3.1示例1： 基本的PSO和連續(xù)函數(shù)優(yōu)化281
14.3.2示例2： 離散二進(jìn)制PSO的子集問題283
14.3.3PSO的高級(jí)屬性283
14.3.4PSO未來(lái)應(yīng)用的前景領(lǐng)域286
14.4訣竅287
14.5結(jié)論288
額外信息源288
參考文獻(xiàn)289
第15章模糊推理294
15.1引言294
15.2模糊集理論的基本定義295
15.2.1模糊集和隸屬度的概念295
15.2.2隸屬度函數(shù)296
15.2.3模糊集運(yùn)算299
15.2.4變換算子300
15.2.5模糊集的笛卡兒內(nèi)積300
15.2.6模糊關(guān)系301
15.2.7模糊集合成301
15.2.8模糊蘊(yùn)含301
15.2.9推理規(guī)則302
15.2.10逆問題302
15.2.11模糊相似度測(cè)度302
15.3模糊推理系統(tǒng)的基本結(jié)構(gòu)303
15.3.1去模糊化單元304
15.3.2規(guī)則庫(kù)的設(shè)計(jì)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模型辨識(shí)與模糊系統(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
附加信息來(lái)源315
參考文獻(xiàn)315
第16章基于粗糙集的決策支持322
16.1引言322
16.2粗糙集基礎(chǔ)323
16.2.1通過示例進(jìn)行的說(shuō)明323
16.2.2經(jīng)典粗糙集方法的正式描述327
16.2.3由粗近似導(dǎo)出的決策規(guī)則329
16.2.4由不可區(qū)分性到相似性330
16.3知識(shí)發(fā)現(xiàn)的范式以及先驗(yàn)知識(shí)331
16.4基于支配的粗糙集方法334
16.4.1基于支配錐的粒計(jì)算334
16.4.2決策規(guī)則的導(dǎo)出338
16.4.3一個(gè)示例340
16.5用于多判據(jù)選擇和排名的基于支配的粗糙集方法343
16.5.1作為偏好信息和學(xué)習(xí)樣本的成對(duì)比較表344
16.5.2成對(duì)比較表給定的排名不低于和排名低于關(guān)系的粗近似345
16.5.3由排名不低于和排名低于關(guān)系的粗近似導(dǎo)出決策規(guī)則347
16.5.4將決策規(guī)則用于決策支持347
16.5.5說(shuō)明性示例348
16.5.6總結(jié)350
16.6訣竅351
16.7結(jié)論與有前景的未來(lái)研究領(lǐng)域352
附加信息源353
參考文獻(xiàn)353
第17章超啟發(fā)式358
17.1超啟發(fā)式的概念358
17.2一個(gè)簡(jiǎn)單的例子： 裝箱問題360
17.3簡(jiǎn)要概述363
17.4一些研究問題363
17.4.1沒有免費(fèi)午餐363
17.4.2什么是問題族364
17.4.3應(yīng)該選擇什么啟發(fā)式365
17.4.4應(yīng)該使用什么搜索算法365
17.4.5在搜索中，如何評(píng)估性能365
17.4.6應(yīng)該尋找什么類型的算法366
17.5未來(lái)應(yīng)用的前景領(lǐng)域366
17.5.1時(shí)間表366
17.5.2帶時(shí)間窗的車輛路徑367
17.5.3其他前景領(lǐng)域368
17.6訣竅369
17.6.1滑雪旅館問題369
17.6.2構(gòu)造性方法的簡(jiǎn)單框架373
附加信息源374
參考文獻(xiàn)374
第18章近似算法378
18.1引言378
18.2近似策略380
18.2.1預(yù)備知識(shí)380
18.2.2貪婪方法382
18.2.3序貫算法386
18.2.4隨機(jī)化388
18.3近似類一覽389
18.3.1PTAS和FPTAS389
18.3.2APX390
18.3.3PCP簡(jiǎn)介391
18.4近似與隨機(jī)算法有前景的應(yīng)用領(lǐng)域391
18.4.1隨機(jī)回溯與后門391
18.4.2用于引導(dǎo)完全回溯搜索的近似392
18.4.3平均情況下的復(fù)雜度和近似392
18.5訣竅393
18.6結(jié)論393
附加信息源394
參考文獻(xiàn)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)計(jì)度量408
19.4.1自相關(guān)408
19.4.2最優(yōu)解的數(shù)量408
19.5憑經(jīng)驗(yàn)的研究409
19.6未來(lái)應(yīng)用的前景領(lǐng)域411
19.7訣竅411
19.8結(jié)論412
附加信息源412
參考文獻(xiàn)413