《搜尋方法論——最佳化與決策支持技術入門教程》是2014年7月28日清華大學出版社出版的圖書，作者是（英）伯克（Edmund K. Burke）、 （英）肯德爾（Graham Kendall），譯者是許瑩、郭斯羽、李仁發。
基本介紹
內容簡介,圖書目錄,圖書前言,
內容簡介
本書是一本涵蓋多個領域，如計算機科學、數學和運籌學的解決各種複雜問題的搜尋、最佳化和決策支持技術的入門教程。本書精心組織，通過19個章節系統介紹了大量經典和最新的最佳化技術和搜尋方法。每章的作者均是相關領域的國際知名專家。第1章是概述，第2章和第3章介紹了一些經典的基於數學的搜尋方法，如分支限界法、動態規劃、網路流規劃、整數規劃等。第4章至第8章介紹了一些經典和常用的人工智慧方法，包括遺傳算法、演化計算、模擬退火、禁忌搜尋、變鄰域搜尋。接著介紹了一些較新的最佳化技術，包括約束規劃、多目標最佳化、機器學習、人工免疫系統、群體智慧型、模糊推理、基於粗糙集的決策支持、超啟發式和近似算法等。此外，本書還介紹了搜尋和最佳化領域涉及的一些理論知識，如複雜理論、適應值曲面等。 本書幾乎涵蓋了所有經典、實用和目前最新的搜尋和最佳化技術，內容豐富、層次分明、重點突出。每章都附有大量相關參考文獻，具有權威性和實用性。作為介紹搜尋和最佳化技術的入門教程，本書非常適合作為高等院校高年級本科生和研究生的教材，並可用作相關領域研究人員的參考資料。
各種決策支持系統的套用涉及眾多領域，如工業、商業、科學和政府部門。決策支持系統可以用來解決許多實際問題，包括交通調度、生物信息最佳化、人事調度、醫療診斷、時間表、生產調度和商業決策等。其中，實現決策支持系統的關鍵是其底層的搜尋和最佳化技術。因此，搜尋和最佳化技術是一個至關重要的研究領域。
圖書目錄
第1章概述1
1.1跨學科決策支持： 動力1
1.2本書的結構1
1.3基本概念和底層問題2
附加信息資源7
參考文獻8
第2章經典方法10
2.1引言10
2.2線性規劃11
2.2.1簡介11
2.2.2線性規劃的問題形式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動態規劃22
2.4.1簡介22
2.4.2建立DP模型23
2.4.3其他問題27
2.5網路流規劃28
2.5.1簡介28
2.5.2最大流問題28
2.5.3最小費用流問題30
2.5.4其他問題34
2.6若干有用的模型34
2.6.1最短路徑問題： 動態規劃方法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有關動態規劃的小提示40
2.8.4有關網路流規劃的小提示41
2.9結論41
附加信息源42
參考文獻43
第3章整數規劃45
3.1介紹45
3.1.1設備選址46
3.1.2解決設備選址整數規劃問題47
3.1.3整數規劃中的難點49
3.2在方程中具有創新性49
3.2.1整數數量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修正分支限界法的參數59
3.7.1問題描述59
3.7.2線性規劃的求解方法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章遺傳規劃84
5.1引言84
5.2遺傳規劃的準備步驟85
5.3遺傳規劃的執行步驟86
5.4運行一個遺傳規劃的實例92
5.5遺傳規劃的深入特徵95
5.5.1約束的語法結構95
5.5.2自動定義的函式95
5.5.3自動定義的疊代、循環、遞歸和存儲96
5.5.4程式結構以及結構改變操作96
5.5.5遺傳規劃問題的解算機97
5.5.6啟發式遺傳規劃97
5.6通過遺傳規劃生成的人類競爭結果97
5.7未來套用的前景領域100
5.8遺傳規劃理論100
5.9訣竅103
5.10結論104
附加信息源104
參考文獻106
第6章禁忌搜尋110
6.1引言110
6.2示例問題110
6.2.1作業車間調度問題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替代與輔助目標函式118
6.5未來套用的前景領域119
6.6訣竅119
6.6.1起步119
6.6.2更多提示120
6.6.3機率禁忌搜尋的更多提示120
6.6.4參數調校和計算測試121
6.7結論121
附加信息源122
參考文獻122
第7章模擬退火126
7.1引言126
7.2局部搜尋126
7.3基本模擬退火128
7.4數學建模130
7.5平衡態統計132
7.6實際套用135
7.6.1靜態冷卻進度表136
7.6.2動態冷卻進度表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章約束規劃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最最佳化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動態約束，軟約束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增加搜尋啟發式算法182
9.12.7使用一個不完備搜尋技術182
附加信息源182
參考文獻183
第10章多目標最佳化186
10.1引言186
10.2多目標最佳化的兩個方法188
10.3非支配解和Pareto最優解191
10.3.1特殊解191
10.3.2支配的概念192
10.3.3支配關係的性質193
10.3.4Pareto最優解193
10.3.5求非支配解的步驟195
10.4多目標最佳化的一些方法197
10.4.1經典方法： 權重求和的方法197
10.4.2經典方法： ε限制方法198
10.4.3多目標進化最佳化方法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經典的多目標最佳化207
10.7.2進化多目標最佳化207
10.7.3最佳化後研究209
10.7.4評價一個多目標最佳化算法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學習規則的演化247
12.3.3演化神經網路的一般框架248
12.4未來套用的前景領域249
12.5訣竅250
12.6結論251
附加信息來源252
參考文獻252
第13章人工免疫系統255
13.1前言255
13.2生物免疫系統的概述255
13.2.1免疫網路理論257
13.2.2消極的選擇機制257
13.2.3克隆選擇原則257
13.3說明性問題258
13.3.1入侵檢測系統258
13.3.2數據挖掘——協同過濾和聚類258
13.4人工免疫系統的基本概念259
13.4.1初始化/編碼259
13.4.2相似度或者相關性測度259
13.4.3消極、克隆或近鄰選擇260
13.4.4體細胞突變261
13.5遺傳算法和神經網路的比較262
13.6人工免疫系統的延伸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蟻群最佳化（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粒子群最佳化280
14.3.1示例1： 基本的PSO和連續函式最佳化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隸屬度函式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推理規則302
15.2.10逆問題302
15.2.11模糊相似度測度302
15.3模糊推理系統的基本結構303
15.3.1去模糊化單元304
15.3.2規則庫的設計305
15.4案例研究： 模糊控制系統306
15.4.1模糊邏輯控制閉環306
15.4.2比例積分（PI）和比例微分（PD）形式的模糊邏輯控制器306
15.4.3示例307
15.4.4模糊自適應控制方法310
15.5模型辨識與模糊系統穩定性312
15.5.1模糊系統建模312
15.5.2模糊系統的穩定性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由粗近似導出的決策規則329
16.2.4由不可區分性到相似性330
16.3知識發現的範式以及先驗知識331
16.4基於支配的粗糙集方法334
16.4.1基於支配錐的粒計算334
16.4.2決策規則的導出338
16.4.3一個示例340
16.5用於多判據選擇和排名的基於支配的粗糙集方法343
16.5.1作為偏好信息和學習樣本的成對比較表344
16.5.2成對比較表給定的排名不低於和排名低於關係的粗近似345
16.5.3由排名不低於和排名低於關係的粗近似導出決策規則347
16.5.4將決策規則用於決策支持347
16.5.5說明性示例348
16.5.6總結350
16.6訣竅351
16.7結論與有前景的未來研究領域352
附加信息源353
參考文獻353
第17章超啟發式358
17.1超啟發式的概念358
17.2一個簡單的例子： 裝箱問題360
17.3簡要概述363
17.4一些研究問題363
17.4.1沒有免費午餐363
17.4.2什麼是問題族364
17.4.3應該選擇什麼啟發式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組合最佳化399
19.3數學描述402
19.3.1鄰域結構402
19.3.2局部最優403
19.3.3吸引域404
19.3.4圖表示404
19.3.5拉普拉斯矩陣405
19.3.6圖的特徵系統405
19.3.7重組曲面407
19.3.8總結407
19.4統計度量408
19.4.1自相關408
19.4.2最優解的數量408
19.5憑經驗的研究409
19.6未來套用的前景領域411
19.7訣竅411
19.8結論412
附加信息源412
參考文獻413
圖書前言
譯 者 序
本書的英文原版是我在英國諾丁漢大學計算機學院攻讀博士學位時用過的一本研究生教材，它是由英國人工智慧最佳化及自動調度領域的知名專家Edmund Burke教授和Graham Kendall教授在2005年編輯整理完成的一本系統介紹解決各種複雜問題的搜尋、最佳化和決策支持技術的入門教程。從這本書的目錄就可以看到，這本書幾乎涵蓋了所有經典、實用和最新的搜尋和最佳化技術，內容豐富，層次分明，特別是每一章的作者都是由該領域的國際知名專家執筆。當我再深入閱讀書的每一章時，更被書中深入淺出的介紹和恰到好處的實例分析所吸引。此外，每章的末尾都提供一些學習和掌握這些方法和技術的訣竅，以及這些方法的一些可能的套用領域、待解決的一些研究方向等，並提供了大量翔實的信息資源，方便我們進行深入研究。就像Fred Glover教授在前言中所提到的，我發現這是一本介紹搜尋和最佳化技術的不可多得的好書，它將以一種輕鬆的方式帶著讀者認識、了解和掌握一些經典和實用的搜尋和最佳化技術。
於是，當我博士畢業回國後，我就萌發了將這本書翻譯成中文的想法，以便讓更多的中國的讀者有機會接觸和學習這本書。從準備翻譯直到完成本書的翻譯工作，我們用了前後1年多的時間。特別要感謝本書的另外兩位譯作者湖南大學信息科學與工程學院李仁發教授和湖南大學電氣與信息工程學院郭斯羽副教授對本書出版翻譯所做的大量工作。另外，還要感謝湖南大學信息科學與工程學院李智勇教授參與本書的核對工作。此外，要感謝清華大學出版社和德國斯普林格出版社對本書翻譯出版工作給予的支持和幫助。最後，感謝所有對本書的翻譯出版提供過幫助的人！
希望這本書，就像它的子標題“——最佳化與決策支持技術入門教程”，能夠給最佳化、運籌學和決策支持領域的讀者提供一個很好的入門資料。由於時間倉促和水平有限，本書中的翻譯難免出現不足之處，敬請諒解。您可以聯繫我們，幫助我們進一步完善本書的翻譯，我們將非常歡迎您的任何意見或建議。
許瑩
湖南大學信息科學與工程學院，中國湖南長沙
2014年6月搜尋方法論——最佳化與決策支持技術入門教程式序
這不是很像一個前言而更像一個證明。當我開始閱讀這本書的各章節的愉快旅程時，我便意識到這是一本目前能找到的最好的介紹以搜尋方法為主題的入門書籍。這本書的小標題“最佳化與決策支持技術的入門教程”，巧妙地描述了它的目的，並且本書的主編和撰稿人已經非常成功地達到這一目的。
書中的各章節示範性地提供了實現描述的方法和框架的有用指導。它們以教程應有的方式設計教程。我發現第一章節都提供了有趣和相關的信息，同時對一些章節能評定為非常討人喜歡。
我們這些貢獻了大部分精力在研究和精心設計搜尋方法的人常常希望能以簡單的方式向這個領域的新手傳遞核心的概念（順便說一句，我必須承認對於書中的一些領域我也是一個新手）。雖然簡單在一定程度上存在於旁觀者的眼中(就像美麗)，沒有通用的或神奇的公式來獲得它，這本書幾乎接近了我之前可能考慮到的目標。它將占據我給想了解搜尋方法基礎或有興趣讓自己深入探究的學生或同事推薦清單中的一個特有位置。
好的書籍可能被比喻成幫助我們攀登更高知識和認知台階的梯子，大家都知道儘管很多書在技術領域寫得看上去更像障礙，或者最多是像破損的凳子，把我們放置在隔離的角落而沒有提供清楚的獲得繼續上升的方法。這本書不是這樣。它的每一章節都提供了供進一步研究的有價值的網址，並且提供了進一步追求它的想法和框架的不可抗拒的動力。如果我的預測不完全出錯，那么這些讀這本書的人將找到大量的理由來分享我的信念，即我們要給本書的編輯和作者一個真正的感謝，是他們將這些工作綜合在一起。
Fred Glover 教授
里茲商學院
美國科羅拉多州博爾德大學搜尋方法論——最佳化與決策支持技術入門教程前言前言
我們是在三年前有了編寫這本書的想法。它源自2003年8月在諾丁漢召開的一個名為“搜尋、最佳化和決策支持方法的入門教程（INTROS）”的專題討論會。這個研討會的目的是對涉及廣大範圍的交叉學科的搜尋方法提供基礎的介紹。研討會受到英國工程與物理科學研究委員會（EPSRC）和倫敦數學協會（LMS）的資助，來自全世界100多名代表出席了該研討會。我們非常幸運地請到了11位搜尋方法領域的世界首席科學家製作了振奮人心和蘊涵大量知識的教程。所有的INTROS的報告者都對本書做出了貢獻，我們還增加了一些內容，加入其他的具有特定目標的補充章節。我們很高興能夠在這個極其重要的領域呈現一個完整的、集合多學科的教程。
我們想借這個機會感謝許多對準備本書做出貢獻的人。我們非常感謝各章節的作者。就像我們對這些傑出的科學家所希望的，他們以絕對可靠和專業的方式取得了成果。當然，沒有他們，將不可能有這本書。我們非常感激我們的文字編輯，Piers Maddox超越了自己，把我們發給他的各種檔案匯聚並整理成條理清晰的結構。我們也非常感謝Gary Folven、Carolyn Ford 和他們的Springer員工，他們在出版過程中的每一步給予我們寶貴的建議和支持。我們要表達對撰寫本書前言的Fred Glover的感謝。他的熱情的讚揚特別令人高興。一個特殊的感謝應該送給EmmaJayne和Alison Payne，因為他們在本書的準備和組織支撐本書的INTROS專題研討會方面給予了管理方面的支持。我們也非常感謝EPSRC和LMS在資金方面對組織這個研討會的支持。最後，我們要特別感謝INTROS代表的熱情和鼓勵。
我們希望讀者能享受讀這本書就像我們享受把它集合在一起的過程一樣。我們將準備再版，如果您有任何能幫助我們改進這本書的意見，請毫不猶豫地跟我們聯繫。我們歡迎您的建議。
