最優(yōu)化方法及其 MATLAB實(shí)現(xiàn)

第1章 概 論…………………………………………………………………………………… 1
1.1 最優(yōu)化問(wèn)題及其分類…………………………………………………………………… 1
1.1.1 最優(yōu)化問(wèn)題舉例……………………………………………………………………… 1
1.1.2 函數(shù)優(yōu)化問(wèn)題………………………………………………………………………… 3
1.1.3 數(shù)學(xué)規(guī)劃……………………………………………………………………………… 4
1.1.4 組合優(yōu)化問(wèn)題………………………………………………………………………… 5
1.2 鄰域函數(shù)與局部搜索…………………………………………………………………… 6
1.3 優(yōu)化問(wèn)題的復(fù)雜性……………………………………………………………………… 6
1.4 優(yōu)化算法發(fā)展?fàn)顩r……………………………………………………………………… 7
上 篇 經(jīng)典優(yōu)化方法
第2章 無(wú)約束優(yōu)化方法……………………………………………………………………… 10
2.1 最優(yōu)性條件……………………………………………………………………………… 10
2.2 迭代法…………………………………………………………………………………… 10
2.3 收斂速度………………………………………………………………………………… 11
2.4 終止準(zhǔn)則………………………………………………………………………………… 12
2.5 一維搜索………………………………………………………………………………… 12
2.5.1 平分法……………………………………………………………………………… 12
2.5.2 牛頓法……………………………………………………………………………… 13
2.5.3 0.618法……………………………………………………………………………… 14
2.5.4 拋物線法……………………………………………………………………………… 15
2.5.5 二點(diǎn)三次插值法……………………………………………………………………… 16
2.5.6 “成功失敗”法……………………………………………………………………… 17
2.5.7 非精確一維搜索……………………………………………………………………… 17
2.6 基本下降法……………………………………………………………………………… 19
2.6.1 最速下降法…………………………………………………………………………… 19
2.6.2 牛頓法……………………………………………………………………………… 20
2.6.3 阻尼牛頓法…………………………………………………………………………… 20
2.6.4 修正牛頓法…………………………………………………………………………… 20
2.7 共軛方向法和共軛梯度法……………………………………………………………… 21
2.7.1 共軛方向和共軛方向法……………………………………………………………… 22
2.7.2 共軛梯度法…………………………………………………………………………… 23
2.8 變尺度法(擬牛頓法)…………………………………………………………………… 24
2.8.1 對(duì)稱秩1算法………………………………………………………………………… 24
2.8.2 DFP算法…………………………………………………………………………… 25
2.8.3 BFGS算法…………………………………………………………………………… 25
2.9 直接搜索法……………………………………………………………………………… 27
2.9.1 Hook-Jeeves方法…………………………………………………………………… 27
2.9.2 單純形法……………………………………………………………………………… 29
2.9.3 Powell方法…………………………………………………………………………… 29
2.10 算法的MATLAB實(shí)現(xiàn)……………………………………………………………… 31
第3章 約束優(yōu)化方法………………………………………………………………………… 36
3.1 最優(yōu)性條件……………………………………………………………………………… 36
3.1.1 等式約束問(wèn)題的最優(yōu)性條件…………………………………………………………… 36
3.1.2 不等式約束問(wèn)題的最優(yōu)性條件………………………………………………………… 37
3.1.3 一般約束問(wèn)題的最優(yōu)性條件…………………………………………………………… 37
3.2 罰函數(shù)法………………………………………………………………………………… 38
3.2.1 外罰函數(shù)法…………………………………………………………………………… 38
3.2.2 內(nèi)點(diǎn)法……………………………………………………………………………… 39
3.2.3 乘子法……………………………………………………………………………… 41
3.3 可行方向法……………………………………………………………………………… 43
3.3.1 Zoutendijk可行方向法………………………………………………………………… 43
3.3.2 梯度投影法…………………………………………………………………………… 45
3.3.3 簡(jiǎn)約梯度法…………………………………………………………………………… 47
3.3.4 廣義簡(jiǎn)約梯度法……………………………………………………………………… 49
3.4 二次逼近法……………………………………………………………………………… 50
3.4.1 二次規(guī)劃的概念……………………………………………………………………… 50
3.4.2 牛頓拉格朗日法……………………………………………………………………… 51
3.4.3 SQP算法…………………………………………………………………………… 52
3.5 極大熵方法……………………………………………………………………………… 56
3.6 算法的MATLAB實(shí)現(xiàn)………………………………………………………………… 57
第4章 最小二乘問(wèn)題………………………………………………………………………… 63
4.1 線性最小二乘問(wèn)題的數(shù)值解法………………………………………………………… 63
4.1.1 滿秩線性最小二乘問(wèn)題……………………………………………………………… 64
4.1.2 虧秩線性最小二乘問(wèn)題……………………………………………………………… 64
4.2 非線性最小二乘問(wèn)題的數(shù)值解法……………………………………………………… 65
4.2.1 Gauss-Newton法…………………………………………………………………… 65
4.2.2 Levenberg-Marquardt方法(L-M 方法)……………………………………………… 66
4.3 算法的MATLAB實(shí)現(xiàn)………………………………………………………………… 67
第5章 線性規(guī)劃……………………………………………………………………………… 71
5.1 線性規(guī)劃的標(biāo)準(zhǔn)形式…………………………………………………………………… 71
5.2 線性規(guī)劃的基本定理…………………………………………………………………… 72
5.3 單純形法………………………………………………………………………………… 73
5.3.1 基本單純形法………………………………………………………………………… 73
5.3.2 單純形法的改進(jìn)……………………………………………………………………… 77
5.4 線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題……………………………………………………………… 78
5.4.1 對(duì)偶單純形法………………………………………………………………………… 79
5.4.2 對(duì)偶線性規(guī)劃的應(yīng)用………………………………………………………………… 81
5.5 算法的MATLAB實(shí)現(xiàn)………………………………………………………………… 84
第6章 動(dòng)態(tài)規(guī)劃……………………………………………………………………………… 91
6.1 理論基礎(chǔ)………………………………………………………………………………… 91
6.2 最優(yōu)化原理和基本方程………………………………………………………………… 94
6.3 動(dòng)態(tài)規(guī)劃的建模方法及步驟…………………………………………………………… 96
6.4 函數(shù)空間迭代法和策略空間迭代法…………………………………………………… 98
6.4.1 函數(shù)空間迭代法……………………………………………………………………… 99
6.4.2 策略空間迭代法…………………………………………………………………… 100
6.5 動(dòng)態(tài)規(guī)劃與靜態(tài)規(guī)劃的關(guān)系………………………………………………………… 103
6.6 算法的MATLAB實(shí)現(xiàn)……………………………………………………………… 104
第7章 整數(shù)規(guī)劃……………………………………………………………………………… 112
7.1 理論基礎(chǔ)……………………………………………………………………………… 112
7.1.1 整數(shù)線性規(guī)劃的標(biāo)準(zhǔn)形式…………………………………………………………… 112
7.1.2 整數(shù)線性規(guī)劃的求解………………………………………………………………… 112
7.1.3 松 馳……………………………………………………………………………… 113
7.1.4 分 解……………………………………………………………………………… 113
7.2 分支定界法…………………………………………………………………………… 114
7.3 割平面法……………………………………………………………………………… 115
7.4 隱枚舉法……………………………………………………………………………… 118
7.4.1 0-1規(guī)劃的標(biāo)準(zhǔn)形式………………………………………………………………… 118
7.4.2 隱枚舉法的基本步驟………………………………………………………………… 119
7.5 匈牙利法……………………………………………………………………………… 120
7.5.1 指派問(wèn)題的標(biāo)準(zhǔn)形式………………………………………………………………… 120
7.5.2 匈牙利法的基本步驟………………………………………………………………… 121
7.6 算法的MATLAB實(shí)現(xiàn)……………………………………………………………… 123
第8章 二次規(guī)劃問(wèn)題………………………………………………………………………… 128
8.1 等式約束二次規(guī)劃的解法…………………………………………………………… 128
8.1.1 零空間方法………………………………………………………………………… 128
8.1.2 拉格朗日乘子法…………………………………………………………………… 129
8.2 一般凸二次規(guī)劃的有效集方法……………………………………………………… 130
8.3 算法的MATLAB實(shí)現(xiàn)……………………………………………………………… 132
第9章 多目標(biāo)規(guī)劃…………………………………………………………………………… 134
9.1 多目標(biāo)規(guī)劃的概念…………………………………………………………………… 134
9.2 有效解、弱有效解和絕對(duì)有效解……………………………………………………… 135
9.3 處理多目標(biāo)規(guī)劃問(wèn)題的一些方法…………………………………………………… 136
9.3.1 評(píng)價(jià)函數(shù)法………………………………………………………………………… 136
9.3.2 約束法……………………………………………………………………………… 140
9.3.3 逐步法……………………………………………………………………………… 140
9.3.4 分層求解法………………………………………………………………………… 141
9.3.5 圖解法……………………………………………………………………………… 143
9.4 權(quán)系數(shù)的確定方法…………………………………………………………………… 144
9.4.1 α 方法……………………………………………………………………………… 144
9.4.2 老手法……………………………………………………………………………… 144
9.4.3 最小平方法………………………………………………………………………… 145
9.5 目標(biāo)規(guī)劃法…………………………………………………………………………… 145
9.5.1 目標(biāo)規(guī)劃模型……………………………………………………………………… 145
9.5.2 目標(biāo)點(diǎn)法…………………………………………………………………………… 148
9.5.3 目標(biāo)規(guī)劃單純形法…………………………………………………………………… 149
9.6 算法的MATLAB實(shí)現(xiàn)……………………………………………………………… 153
第10章 圖 論……………………………………………………………………………… 161
10.1 圖的理論基礎(chǔ)………………………………………………………………………… 161
10.1.1 圖的基本概念 ……………………………………………………………………… 161
10.1.2 圖的矩陣表示……………………………………………………………………… 165
10.1.3 圖論的基本性質(zhì)和定理…………………………………………………………… 166
10.2 最短路………………………………………………………………………………… 166
10.2.1 Dijkstra算法……………………………………………………………………… 167
10.2.2 Warshall-Floyd算法……………………………………………………………… 167
10.2.3 求最大可靠路的算法……………………………………………………………… 168
10.2.4 求期望最大可靠容量路…………………………………………………………… 168
10.3 樹(shù)……………………………………………………………………………………… 169
10.3.1 求最小樹(shù)的Kruskal算法…………………………………………………………… 170
10.3.2 求最小樹(shù)的Prim算法……………………………………………………………… 171
10.4 歐拉(Euler)圖和Hamilton圖……………………………………………………… 171
10.4.1 Euler圖…………………………………………………………………………… 171
10.4.2 中國(guó)郵遞員問(wèn)題…………………………………………………………………… 172
10.4.3 Hamilton圖………………………………………………………………………… 173
10.4.4 旅行售貨員問(wèn)題…………………………………………………………………… 173
10.5 匹配問(wèn)題及其算法…………………………………………………………………… 174
10.5.1 匹配、完善匹配、最大匹配…………………………………………………………… 174
10.5.2 匹配的基本定理…………………………………………………………………… 174
10.5.3 人員分配問(wèn)題……………………………………………………………………… 175
10.5.4 最優(yōu)分派問(wèn)題……………………………………………………………………… 176
10.6 網(wǎng)絡(luò)流的算法………………………………………………………………………… 177
10.6.1 網(wǎng)絡(luò)和流…………………………………………………………………………… 177
10.6.2 割………………………………………………………………………………… 178
10.6.3 網(wǎng)絡(luò)的最大流問(wèn)題及Ford-Fulkerson算法………………………………………… 178
10.7 最小費(fèi)用流…………………………………………………………………………… 179
10.7.1 最小費(fèi)用流問(wèn)題…………………………………………………………………… 180
10.7.2 Busacker-Gowan迭代算法………………………………………………………… 181
10.8 圖的染色……………………………………………………………………………… 182
10.8.1 頂點(diǎn)染色及其算法………………………………………………………………… 182
10.8.2 邊染色及其算法…………………………………………………………………… 183
10.9 算法的MATLAB實(shí)現(xiàn)……………………………………………………………… 183
下 篇 現(xiàn)代智能優(yōu)化算法
第11章 進(jìn)化算法…………………………………………………………………………… 199
第12章 模擬退火算法……………………………………………………………………… 235
第13章 禁忌算法…………………………………………………………………………… 245
第14章 蟻群算法…………………………………………………………………………… 255
第15章 粒子群算法………………………………………………………………………… 269
第16章 人工魚(yú)群算法……………………………………………………………………… 279
第17章 混合蛙跳算法……………………………………………………………………… 294
第18章 量子遺傳算法……………………………………………………………………… 302
第19章 人工蜂群算法……………………………………………………………………… 314
第20章 混沌優(yōu)化算法……………………………………………………………………… 325
第21章 人工免疫算法……………………………………………………………………… 333
第22章 細(xì)菌覓食算法……………………………………………………………………… 354
第23章 貓群算法…………………………………………………………………………… 366
第24章 神經(jīng)網(wǎng)絡(luò)與神經(jīng)網(wǎng)絡(luò)優(yōu)化算法…………………………………………………… 373
第25章 其他群智能優(yōu)化算法……………………………………………………………… 392
第26章 混合優(yōu)化算法……………………………………………………………………… 433