全局最優化——算法評價與數值比較

目   錄

第 1 部分 全局最優化問題與算法

第 1 章 全局最優化問題 3

1.1 最優化問題的數學模型與解的定義 3

1.1.1 最優化問題的數學模型  3

1.1.2 局部最優解與全局最優解 5

1.2 最優化問題的最優性條件  6

1.2.1 局部最優化問題的最優性條件  6

1.2.2 梯度引領：局部最優化算法的有限輝煌  8

1.2.3 稠密搜索與智能啟發：全局最優化的無奈與堅守 10

1.2.4 融合與未來發展  11

第 2 章 全局最優化算法簡介  14

2.1 確定性全局最優化算法簡介  14

2.1.1 分支定界算法  14

2.1.2 DIRECT 算法  16

2.2 隨機性全局最優化算法簡介  19

2.2.1 基因算法  19

2.2.2 粒子群優化算法  20

2.2.3 差分演化算法  23

第 2 部分 全局最優化算法的理論評價與數值比較

第 3 章 全局最優化算法的理論評價  29

3.1 穩定性與收斂性. 29

3.1.1 最優化算法的穩定性  29

3.1.2 最優化算法的收斂性  35

3.2 收斂率與復雜度. 38

3.2.1 最優化算法的收斂率  38

3.2.2 最優化算法的復雜度  41

3.3 準確性與有效性. 43

3.3.1 基於搜索空間的準確性與有效性度量  44

3.3.2 基於目標空間的準確性與有效性度量  46

第 4 章 數值比較的必要性、可行性與流程  50

4.1 從理論評估到數值比較: 必要性  50

4.1.1 理論的有效率不能代替實踐的有效性  50

4.1.2 極限狀態性質不能代替有限狀態性能  51

4.2 從理論評估到數值比較：可行性. 52

4.2.1 沒有免費午餐定理和數值比較的不可行性  52

4.2.2 免費午餐: 超越黑箱優化和置換封閉性  55

4.3 最優化算法數值比較的流程  58

4.3.1 最優化算法與測試問題選擇  58

4.3.2 數值實驗與數據收集  60

4.3.3 數據分析與結果解讀  62

第 5 章 測試問題  67

5.1 常用測試問題集. 67

5.2 度量測試問題的代表性: 理論與方法  69

5.2.1 三個不同層級的代表性問題  69

5.2.2 度量測試問題 (集) 的代表性: 基於 III 型代表性問題的方法框架  71

5.3 度量測試問題 (集) 的代表性: 單目標無約束條件下的實踐  74

5.3.1 現有測試問題的特徵矩陣  74

5.3.2 測試問題 (集) 的代表性計算  92

5.3.3 前 5% 高代表性測試問題集合  98

第 6 章 數據分析方法 100

6.1 描述性統計與 L 形曲線法 100

6.1.1 描述性統計: 用表格呈現數據特徵  101

6.1.2  L 形曲線法: 用 L 形曲線呈現原始數據  104

6.2 基於推斷統計的數據分析方法  106

6.2.1 非參數檢驗  106

6.2.2 參數檢驗  116

6.3 基於累積分佈函數的數據分析方法  129

6.3.1 performance profile 方法和 data profile 方法  129

6.3.2 其他基於累積分佈函數的數據分析方法 134

第 3 部分 數值比較中的策略選擇與悖論消除

第 7 章 數值比較的策略  139

7.1 數據分析方法與比較策略  139

7.1.1 兩種比較策略. 139

7.1.2 方法選擇與策略選擇  141

7.2 集體比較策略 142

7.2.1 元素層集體比較和集合層集體比較  142

7.2.2 元素層集體比較與投票選舉  143

7.2.3 集體比較的投票模型  144

7.3 兩兩比較策略 146

7.3.1 元素層兩兩比較和集合層兩兩比較  146

7.3.2 兩兩比較的數學模型  147

7.3.3 相對多數規則與結果匯總  148

第 8 章 數值比較中的悖論  151

8.1 兩種悖論的實例  151

8.1.1 循環排序悖論的例子  151

8.1.2 非適者生存悖論的例子 152

8.1.3 兩種悖論的實際案例  153

8.2 悖論發生的概率計算  155

8.2.1 概率計算的數學鋪墊  155

8.2.2 循環排序悖論的發生概率  157

8.2.3 非適者生存悖論的發生概率  162

8.2.4 正常事件的發生概率  166

8.3 悖論的影響及原因和對策  167

8.3.1 悖論的影響  167

8.3.2 悖論發生的原因和對策 169

第 9 章 序的過濾與悖論的避免  172

9.1 序與序的過濾 172

9.1.1 基於序關系的數據分析方法及其數學模型  173

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

9.2 算法依賴的過濾條件與悖論實例 176

9.2.1 選拔考試的例子  177

9.2.2 算法比較的例子  179

9.3 算法無關的過濾條件與悖論的避免  181

9.3.1 循環排序悖論的避免  181

9.3.2 非適者生存悖論的避免 185

第 10 章 均值 Borda 計數法與悖論的消除  190

10.1 矩陣降維與最優化算法的數值比較  190

10.1.1 降維與基於累積分佈函數的數據分析方法  191

10.1.2 降維與基於假設檢驗的數據分析方法  191

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

10.2.1 假設檢驗與均值比較的等價性 194

10.2.2 均值 Borda 計數法與循環排序的消除  195

10.3 均值 Borda 計數法的理論優越性與數值有效性  198

10.3.1 循環排序的建模與判別  198

10.3.2 均值 Borda 計數法的理論優越性  201

10.3.3 均值 Borda 計數法的數值有效性  204

第 11 章 總結與展望  208

參考文獻  210