進化最佳化算法-基於仿生和種群的計算機智慧型方法

進化最佳化算法-基於仿生和種群的計算機智慧型方法

作者：[美]丹·西蒙（Dan Simon）著，陳曦 譯
　　定價：118元
印次：1-1
ISBN：9787302516057
出版日期：2018.12.01
印刷日期：2018.12.21

本書討論進化最佳化算法的理論、歷史、數學和編程.主要包括遺傳算法、遺傳規劃、蟻群最佳化、粒子群最佳化、差分進化、基於生物地理學最佳化以及其他多種算法. ?以一種直觀但理論上嚴謹的方式介紹進化算法，同時重視算法的實施. ?仔細討論了較新的進化算法,包括反向學習、人工魚群、細菌覓食以及其他多種算法. ?每章都配有練習題，教師可以線上獲得習題答案. ?藉助簡單的例子幫助讀者直觀理解理論. ?從作者的網頁上可以得到主要的原始碼. ?介紹分析進化算法的數學技巧，包括馬爾可夫建模和動態系統建模.

目錄

致謝 .17

縮寫 .19

第一篇進化最佳化引論 1

第 1章緒論 3

1.1術語 3

1.2又一本關於進化算法的書 5

1.3先修課程 .5

1.4家庭作業 .6

1.5符號 6

1.6本書的大綱 8

1.7基於本書的課程 .8

第 2章最佳化 10

2.1無約束最佳化 10

2.2約束最佳化 . 13

2.3多目標最佳化 14

2.4多峰最佳化 . 15

2.5組合最佳化 . 16

2.6爬山法 18

2.6.1有偏最佳化算法 21

2.6.2蒙特卡羅仿真的重要性 21

2.7智慧型 22

2.7.1自適應 22

2.7.2隨機性 22

2.7.3交流 . 23

2.7.4反饋 . 23

2.7.5探索與開發 . 24

2.8總結 24

習題 . 25

4目錄

第二篇經典進化算法 29

第 3章遺傳算法 31

3.1遺傳學的歷史 32

3.1.1查爾斯·達爾文 32

3.1.2格雷戈爾·孟德爾 . 33

3.2遺傳學 34

3.3遺傳算法的歷史 . 36

3.4一個簡單的二進制遺傳算法 38

3.4.1用於機器人設計的遺傳算法 38

3.4.2選擇與交叉 . 39

3.4.3變異 . 42

3.4.4遺傳算法的總結 42

3.4.5遺傳算法的參數調試及其例子 43

3.5簡單的連續遺傳算法 47

3.6總結50 習題.51

第4章遺傳算法的數學模型.53

4.1圖式理論.54

4.2馬爾可夫鏈57

4.3進化算法的馬爾可夫模型的符號61

4.4遺傳算法的馬爾可夫模型64

4.4.1選擇.64

4.4.2變異.65

4.4.3交叉.66

4.5遺傳算法的動態系統模型69

4.5.1選擇.69

4.5.2變異.71

4.5.3交叉.73

4.6總結77 習題.78

第5章進化規劃80

5.1連續進化規劃80

5.2有限狀態機最佳化.83

5.3離散進化規劃86

5.4囚徒困境.87

目錄5

5.5人工螞蟻問題90

5.6總結93 習題.94

第6章進化策略96

6.1(1+1)進化策略97

6.21/5規則:推導.100

6.3(μ+1)進化策略103

6.4(μ+λ)和(μ,λ)進化策略105

6.5自身自適應進化策略107

6.6總結112 習題.112

第7章遺傳規劃114

7.1LISP:遺傳規劃的語言115

7.2遺傳規劃的基礎.120

7.2.1適應度的度量120

7.2.2終止準則121

7.2.3終止集合121

7.2.4函式集合122

7.2.5初始化123

7.2.6遺傳規劃的參數125

7.3最短時間控制的遺傳規劃127

7.4遺傳規劃的膨脹.132

7.5演化實體而非電腦程式133

7.6遺傳規劃的數學分析135

7.6.1定義和記號.135

7.6.2選擇和交叉.136

7.6.3變異和最後結果139

7.7總結140 習題.142

第8章遺傳算法的變種145

8.1初始化145

8.2收斂準則.146

8.3用格雷編碼表示問題148

8.4精英150

8.5穩態與代際算法.152

6目錄

8.6種群多樣性153

8.6.1重複個體154

8.6.2基於小生境和基於物種的重組154

8.6.3小生境156

8.7選擇方案.160

8.7.1隨機遍歷採樣160

8.7.2超比例選擇.162

8.7.3Sigma縮放.162

8.7.4基於排名選擇164

8.7.5線性排名164

8.7.6錦標賽選擇.166

8.7.7種馬進化算法167

8.8重組168

8.8.1單點交叉(二進制或連續進化算法)169

8.8.2多點交叉(二進制或連續進化算法)169

8.8.3分段交叉(二進制或連續進化算法)169

8.8.4均勻交叉(二進制或連續進化算法)170

8.8.5多父代交叉(二進制或連續進化算法).170

8.8.6全局均勻交叉(二進制或連續進化算法)171

8.8.7洗牌交叉(二進制或連續進化算法)171

8.8.8平交叉和算術交叉(連續進化算法)171

8.8.9混合交叉(連續進化算法)172

8.8.10線性交叉(連續進化算法)172

8.8.11模擬二進制交叉(連續進化算法)172

8.8.12小結.173

8.9變異173

8.9.1以xi(k)為中心的均勻變異173

8.9.2以搜尋域的中央為中心的均勻變異174

8.9.3以xi(k)為中心的高斯變異174

8.9.4以搜尋域的中央為中心的高斯變異174

8.10總結174 習題.175

第三篇較新的進化算法179

第9章模擬退火181

9.1自然退火.181

9.2簡單的模擬退火算法183

目錄7

9.3冷卻調度.184

9.3.1線性冷卻184

9.3.2指數冷卻185

9.3.3逆冷卻185

9.3.4對數冷卻187

9.3.5逆線性冷卻.188

9.3.6依賴於維數的冷卻.190

9.4實施的問題192

9.4.1候選解的生成192

9.4.2重新初始化.193

9.4.3記錄最好的候選解.193

9.5總結193 習題.194

第10章蟻群最佳化196

10.1信息素模型198

10.2螞蟻系統.200

10.3連續最佳化.204

10.4其他螞蟻系統.207

10.4.1最大最小螞蟻系統207

10.4.2蟻群系統.208

10.4.3更多的螞蟻系統.211

10.5理論結果.212

10.6總結212 習題.213

第11章粒子群最佳化215

11.1基本粒子群最佳化算法.216

11.2速度限制.219

11.3慣性權重與壓縮係數.220

11.3.1慣性權重.220

11.3.2壓縮係數.222

11.3.3粒子群最佳化的穩定性.223

11.4全局速度更新.226

11.5完全知情的粒子群229

11.6從錯誤中學習.231

11.7總結234 習題.234

8目錄

第12章差分進化237

12.1基本差分進化算法237

12.2差分進化的變種.239

12.2.1試驗向量.240

12.2.2變異向量.242

12.2.3比例因子的調整.245

12.3離散最佳化.246

12.3.1混合整數差分進化247

12.3.2離散差分進化.248

12.4差分進化與遺傳算法.248

12.5總結250 習題.250

第13章分布估計算法.252

13.1分布估計算法:基本概念.253

13.1.1簡單的分布估計算法.253

13.1.2統計量的計算.253

13.2一階分布估計算法254

13.2.1一元邊緣分布算法254

13.2.2緊緻遺傳算法.256

13.2.3基於種群的增量學習.259

13.3二階分布估計算法261

13.3.1輸入聚類互信息最大化.261

13.3.2最佳化與互信息樹結合.266

13.3.3二元邊緣分布算法271

13.4多元分布估計算法273

13.4.1擴展緊緻遺傳算法273

13.4.2其他多元分布估計算法.276

13.5連續分布估計算法276

13.5.1連續一元邊緣分布算法.277

13.5.2基於增量學習的連續種群278

13.6總結281 習題.282

第14章基於生物地理學的最佳化284

14.1生物地理學285

14.2生物地理學是一個最佳化過程.288

14.3基於生物地理學最佳化.290

14.4BBO的擴展293

14.4.1遷移曲線.293

目錄9

14.4.2混合遷移.294

14.4.3BBO的其他方法296

14.4.4BBO與遺傳算法298

14.5總結299 習題.302

第15章文化算法304

15.1合作與競爭305

15.2文化算法中的信仰空間.307

15.3文化進化規劃.309

15.4自適應文化模型.311

15.5總結316 習題.317

第16章反向學習318

16.1反向的定義和概念318

16.1.1反射反向和模反向319

16.1.2部分反向.320

16.1.31型反向和2型反向.321

16.1.4準反向和超反向.321

16.2反向進化算法.322

16.3反向機率.326

16.4跳變比.329

16.5反向組合最佳化.331

16.6對偶學習.333

16.7總結334 習題.335

第17章其他進化算法.337

17.1禁忌搜尋.337

17.2人工魚群算法.338

17.2.1隨機行為.339

17.2.2追逐行為.340

17.2.3聚集行為.340

17.2.4搜尋行為.340

17.2.5跳躍行為.340

17.2.6人工魚群算法概要341

17.3群搜尋最佳化器.342

17.4混合蛙跳算法.344

10目錄

17.5螢火蟲算法346

17.6細菌覓食最佳化.347

17.7人工蜂群算法.350

17.8引力搜尋算法.352

17.9和聲搜尋.353

17.10基於教學的最佳化355

17.11總結358 習題.359

第四篇最佳化問題的特殊類型361

第18章組合最佳化363

18.1旅行商問題364

18.2旅行商問題的初始化.365

18.2.1最近鄰初始化.365

18.2.2最短邊初始化.367

18.2.3嵌入初始化367

18.2.4隨機初始化369

18.3旅行商問題的表示與交叉369

18.3.1路徑表示.369

18.3.2鄰接表示.372

18.3.3順序表示.375

18.3.4矩陣表示.376

18.4旅行商問題的變異379

18.4.1反轉379

18.4.2嵌入379

18.4.3移位379

18.4.4互換380

18.5旅行商問題的進化算法.380

18.6圖著色問題384

18.7總結387 習題.387

第19章約束最佳化389

19.1罰函式法.390

19.1.1內點法.390

19.1.2外點法.391

19.2處理約束的常用方法.393

19.2.1靜態懲罰方法.393

目錄11

19.2.2可行點優勢393

19.2.3折中進化算法.394

19.2.4協同進化懲罰.395

19.2.5動態懲罰方法.396

19.2.6自適應懲罰方法.397

19.2.7分離遺傳算法.398

19.2.8自身自適應的適應度描述398

19.2.9自身自適應罰函式399

19.2.10自適應分離約束處理.400

19.2.11行為記憶401

19.2.12隨機排名402

19.2.13小生境懲罰方法403

19.3特殊表示與特殊運算元.403

19.3.1特殊表示.404

19.3.2特殊運算元.405

19.3.3Genocop406

19.3.4GenocopII.407

19.3.5GenocopIII.407

19.4約束最佳化的其他方法.409

19.4.1文化算法.409

19.4.2多目標最佳化409

19.5候選解的排名.410

19.5.1最大違反約束排名410

19.5.2約束次序排名.410

19.5.3←-水平比較.411

19.6處理約束方法的比較.412

19.7總結414 習題.416

第20章多目標最佳化418

20.1帕雷托最優性.419

20.2多目標最佳化的目標423

20.2.1超體積.424

20.2.2相對覆蓋度427

20.3基於非帕雷托的進化算法427

20.3.1集結方法.427

20.3.2向量評價遺傳算法429

20.3.3字典排序.430

12目錄

20.3.4←-約束方法431

20.3.5基於性別的方法.431

20.4基於帕雷托進化算法.432

20.4.1多目標進化最佳化器433

20.4.2基於←的多目標進化算法434

20.4.3非支配排序遺傳算法.436

20.4.4多目標遺傳算法.438

20.4.5小生境帕雷托遺傳算法.439

20.4.6優勢帕雷托進化算法.440

20.4.7帕雷托歸檔進化策略.445

20.5基於生物地理學的多目標最佳化.446

20.5.1向量評價BBO446

20.5.2非支配排序BBO.447

20.5.3小生境帕雷托BBO.448

20.5.4優勢帕雷托BBO.449

20.5.5多目標BBO的仿真.450

20.6總結451 習題.452

第21章昂貴、有噪聲與動態適應度函式.455

21.1昂貴適應度函式.456

21.1.1適應度函式的近似457

21.1.2近似變換函式.465

21.1.3在進化算法中如何使用適應度近似.466

21.1.4多重模型.468

21.1.5過擬合.470

21.1.6近似方法的評價.471

21.2動態適應度函式.472

21.2.1預測進化算法.474

21.2.2遷入方案.475

21.2.3基於記憶的方法.478

21.2.4動態最佳化性能的評價.479

21.3有噪聲適應度函式479

21.3.1再採樣.480

21.3.2適應度估計482

21.3.3卡爾曼進化算法.483

21.4總結485 習題.486

目錄13

第五篇附錄.489

附錄A一些實際的建議491

A.1查錯.491

A.2進化算法是隨機的.491

A.3小變化可能會有大影響492

A.4大變化可能只有小影響492

A.5種群含有很多信息.492

A.6鼓勵多樣性.492

A.7利用問題的信息493

A.8經常保存結果493

A.9理解統計顯著性493

A.10善於寫作.493

A.11強調理論.494

A.12強調實踐.494

附錄B沒有免費午餐定理與性能測試495

B.1沒有免費午餐定理.495

B.2性能測試500

B.2.1基於仿真結果的大話.500

B.2.2如何報告(不報告)仿真結果.502

B.2.3隨機數.506

B.2.4t檢驗.508

B.2.5F檢驗.512

B.3總結.515

附錄C基準最佳化函式.516

C.1無約束基準.516

C.1.1Sphere函式.517

C.1.2Ackley函式.517

C.1.3Ackley測試函式518

C.1.4Rosenbrock函式518

C.1.5Fletcher函式.519

C.1.6Griewank函式.520

C.1.7Penalty#1函式.521

C.1.8Penalty#2函式.521

C.1.9Quartic函式522

C.1.10TenthPower函式.523

C.1.11Rastrigin函式524

14目錄

C.1.12Schwefel二重和函式.524

C.1.13Schwefel最大函式525

C.1.14Schwefel絕對值函式.526

C.1.15Schwefel正弦函式526

C.1.16Step函式.527

C.1.17Absolute函式528

C.1.18Shekel’sFoxhole函式.528

C.1.19Michalewicz函式.529

C.1.20SineEnvelope函式.530

C.1.21Eggholder函式530

C.1.22Weierstrass函式.531

C.2約束基準531

C.2.1C01函式.532

C.2.2C02函式.532

C.2.3C03函式.533

C.2.4C04函式.533

C.2.5C05函式.533

C.2.6C06函式.534

C.2.7C07函式.534

C.2.8C08函式.534

C.2.9C09函式.535

C.2.10C10函式.535

C.2.11C11函式.535

C.2.12C12函式.535

C.2.13C13函式.536

C.2.14C14函式.536

C.2.15C15函式.537

C.2.16C16函式.537

C.2.17C17函式.537

C.2.18C18函式.538

C.2.19約束基準的總結538

C.3多目標基準.539

C.3.1無約束多目標最佳化問題1539

C.3.2無約束多目標最佳化問題2540

C.3.3無約束多目標最佳化問題3541

C.3.4無約束多目標最佳化問題4541

C.3.5無約束多目標最佳化問題5542

C.3.6無約束多目標最佳化問題6542

C.3.7無約束多目標最佳化問題7543

目錄15

C.3.8無約束多目標最佳化問題8544

C.3.9無約束多目標最佳化問題9544

C.3.10無約束多目標最佳化問題10545

C.4動態基準545

C.4.1動態基準的完整描述.546

C.4.2簡化的動態基準描述.550

C.5噪聲基準551

C.6旅行商問題.551

C.7無偏化搜尋空間553

C.7.1偏差553

C.7.2旋轉矩陣.555

參考文獻557

索引.601

致謝

進化算法是一個令人著迷的研究領域,我涉足其間已有20年,感謝多年來為我的研究提供資助的每一位人士:TRW系統集成組的HossnyEl-Sherief,TRW汽車安全系統的DorinDragotoniu,NASAGlenn控制和動力學部門的SanjayGarg和DonaldSimon,福特汽車公司的DimitarFilev,克利夫蘭醫學中心的BrianDavis和WilliamSmith,國家科學基金和克利夫蘭州立大學.還要感謝和我一起工作,在進化算法領域發表論文的學生和同事：Je.Abell,DaweiDu,MehmetErgezer,BrentGardner,BorisIgelnik,PaulLozovyy,HaipingMa,BerneyMontavon,MirelaOvreiu,RickRarick,HanzRichter,DavidSadey,SergeySamorezov,NinaScheidegger,ArpitShah,SteveSzatmary,GeorgeThomas,OliverTiber,TonvandenBogert,ArunVenkatesan和TimWilmot.最後,我想感謝閱讀這些材料的初稿並給我許多有用建議的人士：EmileAarts,DanAshlock,ForrestBennett,Hans-GeorgBeyer,MauriceClerc,CarlosCoelloCoello,KalyanmoyDeb,GuszEiben,Jin-KaoHao,YaochuJin,PedroLarranaga,MahamedOmran,KennethV.Price,Hans-PaulSchwefel,ThomasSt¨utzle,HamidTizhoosh,DarrellWhitley.還要感謝評審本書最初的出版計畫的三位匿名評閱人.這些評閱人不一定贊同這本書,但他們的建議和評論幫助我提升本書的品質.

丹·西蒙(DanSimon)

縮寫

ABC人工蜂群

ACM自適應文化模型

ACO蟻群最佳化

ACS蟻群系統

ADF自動定義的函式

AFSA人工魚群算法

AS螞蟻系統

ASCHEA自適應分離約束處理進化算法

BBO基於生物地理學的最佳化

BFOA細菌覓食最佳化算法

BMDA二元邊緣分布算法

BOA貝葉斯最佳化算法

CA文化算法

CAEP受文化算法影響的進化規劃

CEC進化計算大會

cGA緊緻遺傳算法

CMA-ES協方差陣自適應進化策略

CMSA-ES協方差陣自身自適應進化策略

COMIT最佳化與互信息樹結合

CX循環交叉

DACE計算機實驗的設計與分析

DAFHEA基於動態近似適應度的混合進化算法

DE差分進化

DEMO多樣性多目標進化最佳化器

←-MOEA基於←的多目標進化算法

EA進化算法

EBNA貝葉斯網路估計算法

ECGA擴展緊緻遺傳算法

20縮寫

EDA分布估計算法

EGNA高斯網路估計算法

EMNA多元正態估計算法

EP進化規劃

ES進化策略

FDA因子化分布算法

FIPS完全知情的粒子群

FSM有限狀態機

GA遺傳算法

GP進化規劃

GSA引力搜尋算法

GSO群搜尋最佳化器

hBOA分層貝葉斯最佳化算法

HCwL學習爬山法

HLGAHajela-Lin遺傳算法

HS和聲搜尋

HSI生境適宜度指數

IDEA疊代密度估計算法

IDEA不可行性驅動的進化算法

IUMDA增量一元邊緣分布算法

MMAS最大最小螞蟻系統

MMES多元進化策略

MIMIC輸入聚類的互信息最大化

MOBBO基於生物地理學的多目標最佳化

MOEA多目標進化算法

MOGA多目標遺傳算法

MOP多目標最佳化問題

MPM邊緣積模型

N(μ,σ2)均值為μ方差為σ2的常態分配

N(μ,Σ)均值為μ協方差為Σ的多元常態分配

NFL沒有免費午餐

NPBBO小生境帕雷托基於生物地理學最佳化

NPGA小生境帕雷托遺傳算法

NPSO負強化的粒子群最佳化

NSBBO非支配排序基於生物地理學最佳化

NSGA非支配排序遺傳算法

縮寫21

OBBO反向的基於生物地理學最佳化

OBL反向學習

OBX基於順序交叉

OX順序交叉

PAES帕雷托歸檔進化策略

PBIL基於種群的增量學習

PDF機率密度函式

PID比例積分微分

PMBGA機率建模遺傳算法

PMX部分匹配交叉

PSO粒子群最佳化

RMS均方根

RV隨機變數

SA模擬退火

SBX模擬二進制交叉

SAPF自身自適應罰函式

SCE混合複雜進化

SEMO簡單多目標進化最佳化器

SFLA混合蛙跳算法

SGA隨機梯度上升

SHCLVND由常態分配向量學習的隨機爬山法

SIV適應度指數變數

SPBBO優勢帕雷托基於生物地理學最佳化

SPEA優勢帕雷托進化算法

TLBO基於教學的最佳化

TS禁忌搜尋

TSP旅行商問題

U[a,b]在域[a,b]上均勻分布的機率密度函式.可為連續的也可為離散的,

根據上下文確定

UMDA一元邊緣分布算法

UMDAGc連續高斯一元邊緣分布算法

VEBBO向量評價基於生物地理學最佳化

VEGA向量評價遺傳算法