全局最優化方法——從梯度引領到智能啟發

 

目   錄

第1章  最優化問題的數學模型與基本理論   1

1.1  最優化問題及其數學模型   1

1.1.1  最優化問題舉例   1

1.1.2  最優化問題的數學模型   5

1.1.3  全局最優化問題與局部最優化問題   7

1.2  最優化問題的基本理論   8

1.2.1  全局最優解的存在性   9

1.2.2  全局最優解的NP-hard性質   9

1.2.3  局部最優化問題的最優性條件   11

1.2.4  全局最優化問題的最優性條件   13

1.3  最優化算法框架初瞰與本書後續安排   15

1.3.1  局部最優化問題的梯度型算法   15

1.3.2  全局最優化問題的智能啟發類算法   17

1.3.3  全局最優化與局部最優化: 特色與融合   18

習題與思考   20

第1部分  梯度優化的多次重啟與無導數優化

第2章  基於梯度信息的局部尋優   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  約束優化算法   58

2.4.1  罰函數方法   59

2.4.2  增廣拉格朗日函數方法   61

習題與思考   63

第3章  局部優化的多次重啟   65

3.1  從局部尋優到全局優化   65

3.2  並行式多次重啟   67

3.2.1  MultiStart算法   67

3.2.2  數值實驗   68

3.3  序列式多次重啟   70

3.3.1  GlobalSearch算法   70

3.3.2  散點搜索   72

3.3.3  局部搜索及其監控與重啟   75

3.3.4  數值實驗   77

習題與思考   81

第4章  直接搜索與無導數優化   83

4.1  直接搜索算法的基本理論   83

4.1.1  從空間的基到正基   84

4.1.2  正基與下降方向   85

4.1.3  正基的構造   86

4.2  直接搜索算法的主流實現   88

4.2.1  羅盤形直接搜索算法   88

4.2.2  單純形直接搜索算法   93

4.3  采用近似梯度的無導數優化算法: 基本理論   99

4.3.1  插值   99

4.3.2  回歸   101

4.3.3  單純形梯度   102

4.4  采用近似梯度的無導數優化算法: 基本框架   104

4.4.1  線搜索型無導數優化算法   104

4.4.2  信賴域型無導數優化算法   107

4.4.3  點集適定性與數據點選取   108

4.5  全局最優化問題的無導數優化算法   115

4.5.1  DIRECT算法及其收斂性   115

4.5.2  DIRECT算法的改進   120

4.5.3  DIRECT算法與遞歸深度群體搜索技術   123

習題與思考   127

第2部分  啟發式優化、演化優化與群體智能優化

第5章  啟發式優化   131

5.1  啟發式與元啟發式   131

5.1.1  啟發式   131

5.1.2  元啟發式   132

5.1.3  元啟發式優化算法的發展及分類   132

5.2  模擬退火算法   132

5.2.1  Metropolis抽樣過程   133

5.2.2  簡單模擬退火算法   134

5.2.3  從退火到再退火   136

5.2.4  漸近收斂性   137

5.2.5  算法的應用   138

5.3  禁忌搜索算法   139

5.3.1  算法理念與偽代碼   139

5.3.2  鄰域結構與禁忌表   140

5.3.3  收斂性   143

5.3.4  一個應用   144

習題與思考   147

第6章  演化優化   149

6.1  基因算法與基因規劃   149

6.1.1  理念及發展簡史   149

6.1.2  算法要素及偽代碼   150

6.1.3  收斂性   154

6.1.4  基因算法的精煉   160

6.1.5  結構編碼與基因規劃   164

6.2  演化規劃與演化策略   167

6.2.1  演化規劃   168

6.2.2  有限狀態機及其應用   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章  群體智能優化   184

7.1  粒子群優化   184

7.1.1  理念與算法實現   185

7.1.2  動態方程的變化   188

7.1.3  拓撲選擇與優化   192

7.1.4  收斂性和穩定性   197

7.2  蟻群優化   202

7.2.1  從螞蟻到人工螞蟻   203

7.2.2  蟻群優化算法   204

7.2.3  蟻群優化的理論性質   209

7.3  其他群體智能優化算法   214

7.3.1  煙花算法   214

7.3.2  頭腦風暴優化算法   217

7.3.3  鴿群優化算法   220

習題與思考   223

第3部分  算法的理論評價與數值比較

第8章  最優化算法的理論評估   227

8.1  “穩”: 從穩定性到收斂性   227

8.1.1  最優化算法的穩定性   228

8.1.2  最優化算法的收斂性   233

8.2  “快”: 從收斂率到復雜度   234

8.2.1  最優化算法的收斂率   234

8.2.2  最優化算法的復雜度   237

8.3  “準”: 準確性與有效性   240

8.3.1  基於搜索空間的準確性與有效性度量   240

8.3.2  基於目標空間的準確性與有效性度量   243

習題與思考   245

第9章  最優化算法的數值比較   247

9.1  數值比較的必要性與可行性   247

9.1.1  最優化算法的數值比較是必要的   247

9.1.2  沒有免費午餐定理與數值比較的總體可行性   248

9.2  最優化算法數值比較的流程   253

9.2.1  測試算法與測試問題的選取   254

9.2.2  數值實驗與數據收集   255

9.2.3  數據分析方法與數值比較策略   256

9.2.4  結果的匯總與解讀   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章  數值比較中的數據分析方法   272

10.1  描述性統計法與L形曲線法   272

10.1.1  描述性統計法: 用表格呈現數據特征   273

10.1.2  L形曲線法: 用L形曲線呈現原始數據   276

10.2  基於推斷統計的數據分析方法   277

10.2.1  非參數檢驗   278

10.2.2  參數檢驗   287

10.3  基於累積分布函數的數據分析方法   299

10.3.1  performance profile方法和data profile方法   299

10.3.2  其他基於累積分布函數的數據分析方法   304

習題與思考   307

第11章  數值比較的策略選擇與悖論消除   308

11.1  數值比較的策略選擇   308

11.1.1  兩種比較策略的定義   308

11.1.2  集體比較策略   310

11.1.3  兩兩比較策略   315

11.1.4  結果匯總中的相對多數規則   317

11.2  比較策略與悖論的發生   319

11.2.1  悖論的實例   319

11.2.2  悖論發生的概率計算: 一些數學鋪墊   322

11.2.3  循環排序悖論的發生概率   324

11.2.4  非適者生存悖論的發生概率   327

11.2.5  正常事件的發生概率   330

11.3  序的過濾與悖論的避免   331

11.3.1  悖論的影響及對策   331

11.3.2  基於序的過濾的數據分析方法及其數學模型   334

11.3.3  算法無關的過濾條件與悖論的避免   336

11.4  均值Borda計數法與悖論的消除   344

11.4.1  矩陣降維與最優化算法的數值比較   345

11.4.2  均值Borda計數法與假設檢驗中的循環排序消除   348

11.4.3  均值Borda計數法的理論優越性與數值有效性   352

習題與思考   356

第4部分  實操指引篇

第12章  最優化算法的設計與評價   361

12.1  如何調用現成的算法來求解最優化問題   361

12.1.1  最優化工具箱   362

12.1.2  全局最優化工具箱   373

12.2  如何改進或設計最優化算法   383

12.2.1  基於多次重啟的梯度型算法   384

12.2.2  種群協同型智能優化算法   386

12.3  如何評價一個最優化算法   387

12.3.1  對最優化算法進行數值測試   387

12.3.2  數據分析與結果解讀   390

12.3.3  理論分析與評價   401

習題與思考   403

參考文獻   405