智能演化優化（簡體書）

近年來，演化計算作為計算智能領域的經典優化技術，已經廣泛應用於求解組合優化、工程優化等理論和工程類的優化問題，形成了一種基於演化的智能優化方法。針對高維空間的多目標優化問題，近年來基於分解的多目標演化算法（MOEAs）利用了分而治之的思想有效降低了求解多目標或高維多目標優化問題的難度。根據分解的形式不同，基於分解的MOEAs又進一步細分為基於聚合的MOEAs和基於參考點的MOEAs。盡管基於分解的MOEAs是目前求解高維多目標優化問題最有前景的技術之一，然而它在方法和應用層面均存在著缺陷和不足。本書第一部分圍繞該類方法，著眼於“如何在目標空間中平衡收斂性和多樣性”“如何在決策空間中平衡探索與開發”以及“如何進行有效的降維”等科學問題，展開了系統性的研究，旨在進一步完善其理論框架並推廣其在具體問題上的應用。另外，針對多目標柔性作業車間調度這一類典型的NP難工程優化問題，本書基於演化優化的求解思路，分別研究了面向單目標優化的融合問題知識的混合和聲搜索方法（HHS）、面向高維空間單目標優化的混合和聲搜索和大鄰域搜索的集成搜索方法（HHS/LNS），以及面向多目標優化的基於目標重要性分解的模因演化方法，並在多個基線數據集上取得了優異的效果。
本書可作為演化計算、智能優化、大數據及人工智能等相關專業研究參考和研究生教學用書。

l 基於自然界啟發式的求解算法，介紹了與經典數學規劃原理不同的優化算法，通過仿生智能優化算法解決複雜多目標優化問題，豐富了現代優化技術，並提供了解決傳統優化技術難以處理的高維組合優化問題的實際可行方案。
l 高維多目標優化問題的研究：關注高維多目標優化問題，提出新型算法和技術，包括目標降維方法和代理模型輔助優化等，探討在高維目標空間中進行有效的搜索和優化。為處理現實世界中複雜的決策問題提供重要的方法和工具。
l 探索智能演化優化在不同領域的應用：涵蓋了智能演化優化在工業互聯網等領域的柔性作業車間調度問題的研究和開發工作，為相關領域的專業人員提供實用的指導和解決方案。

習近平總書記在黨的二十大報告中指出: 教育、科技、人才是全面建設社會主義現代化國家的基礎性、戰略性支撐。必須堅持科技是第一生產力、人才是第一資源、創新是第一動力，深入實施科教興國戰略、人才強國戰略、創新驅動發展戰略，這三大戰略共同服務於創新型國家的建設。報告同時強調: 推動戰略性新興產業融合集群發展，構建新一代信息技術、人工智能、生物技術、新能源、新材料、高端裝備、綠色環保等一批新的增長引擎。
當前，人工智能日益成為引領新一輪科技革命和產業變革的核心技術。其中，智能演化優化作為一種重要的計算方法，在諸多領域，如控制系統設計、工業調度、軟件工程等實際應用中，已經展現出其獨特的優勢和巨大的潛力。
演化算法（Evolutionary Algorithms，EAs）是一類模擬自然界生物進化過程的基於群體的全局優化算法。EAs已經成功應用於多目標優化領域，為求解“多目標優化問題”(MOPs)開辟了一條新的途徑。由於EAs在多目標優化方面具有獨特的優勢，能夠有效克服傳統方法的局限性，多目標演化算法（MultiObjective Evolutionary Algorithms，MOEAs）的研究已成為演化計算（Evolutionary Computation，EC）領域的熱門方向之一，並已發展成為一個重要而活躍的研究分支: 演化多目標優化（Evolutionary Multiobjective Optimization，EMO）。
相對於單目標優化問題（Singleobjective Optimization Problems，SOPs），多目標優化問題（Multiobjective Optimization Problems，MOPs）的求解一般更加困難。在SOPs中，由於解之間是全序關係，通常只存在唯一的最優解；而在MOPs中，由於目標之間存在一定程度的衝突，導致解之間只存在偏序關係，因此一般不是得到單個的最優解，而是得到一組折中的解，即所謂的Pareto最優解集或非支配解集。
近幾年來，EMO領域的研究焦點逐漸轉向高維多目標優化問題（Many Objective Optimization Problems，MaOPs），即目標數目大於3的MOPs，這類研究的興起主要有以下兩個原因。一方面，涉及許多優化目標的優化問題確實廣泛存在於各種實際應用中，如控制系統設計、工業調度、軟件工程等。因此，實踐者迫切需要有效的優化方法能夠很好地解決他們所面臨的這類問題。另一方面，非常流行的基於Pareto支配的MOEAs，如第二代非支配排序遺傳算法（Nondominated Sorting Genetic Algorithm Ⅱ，NSGAⅡ）、第二代強度Pareto演化算法（Strength Pareto Evolutionary Algorithm 2，SPEA2）、第二代基於Pareto包絡的選擇算法（Pareto Envelopebased Selection Algorithm Ⅱ，PESAⅡ）等，雖然在具有兩個或三個優化目標的MOPs上顯示出了優異的性能，但是它們在高維多目標優化中卻遇到了很大的困難。
本書將基於分解的MOEAs作為研究物件，在方法和應用兩個層面均展開了研究工作，旨在進一步提升這類算法在高維多目標優化中的性能，並拓展其新型應用領域，為求解生產調度領域的複雜多目標優化問題提供高效的求解方法。在理論方法層面，本書系統化地研究了在基於聚合的多目標演化算法中平衡收斂性和多樣性的方法、基於新型支配關係的多目標演化算法、基於分解的多目標演化算法中的變化算子比較性研究、多目標優化中的目標降維方法，以及利用支配預測輔助的高成本多目標演化優化方法；在工程優化應用層面，針對實際集成電路製造領域的工藝調度優化問題，將具有多腔室、多機器人、多加工路徑、多優化目標等複雜生產環境抽象為多目標柔性作業車間調度問題（MultiObjective Flexible Jobshop Scheduling Problem，MoFJSP），系統化地研究了面向單目標優化的融合問題知識的混合和聲搜索方法（HHS）、面向高維空間單目標優化的混合和聲搜索和大鄰域搜索的集成搜索方法（HHS/LNS），以及面向多目標優化的基於目標重要性分解的模因演化方法。
本書是“演化學習與智能優化”系列學術專著的第二部，筆者的研究團隊後續將及時梳理和歸納總結相關的最新成果，以系列圖書的形式分享給讀者。本書既可以作為演化學習、智能優化等領域的教材，同時也可以作為優化調度、演化學習、智能系統等方面系統與產品研發重要的理論方法參考書。本書相關的內容資料（算法、代碼、數據集等）可在開源社區下載（下載地址可查閱THUAIR官網或者聯繫作者）。由於智能演化優化是一個嶄新的快速發展的研究領域，受限於作者的學識和知識的認知範圍，書中疏漏和不足之處在所難免，衷心地希望讀者能提出寶貴的意見和建議，請聯繫bailj@tup.tsinghua.edu.cn。
本書的相關工作受國家自然科學基金項目（No. 61673235、No. 61175110、No. 60875073、No. 60575057）的持續資助與支持。同時更要感謝本書書寫過程中，清華大學計算機科學與技術系智能技術與系統國家重點實驗室趙錦櫟、陳小飛等對書稿整理所付出的艱辛努力，以及楊甲東、王勃等在相關研究方向上不斷持續的合作創新工作成果。沒有各位團隊成員的努力，本書無法以體系化的形式呈現在讀者面前。

作者2023年12月於北京

上篇多目標優化問題與智能演化優化方法
第1章引言3
1.1研究背景3
1.2基本概念以及基本框架5
1.2.1多目標優化問題5
1.2.2多目標演化算法簡介6
1.3相關研究工作綜述8
1.3.1進化高維多目標優化8
1.3.2多目標演化算法中的變化算子11
1.4本章小結12
第2章基礎知識13
2.1典型的基於分解的多目標演化算法13
2.1.1問題分解多目標演化算法13
2.1.2集成適應度排序14
2.1.3第三代非支配排序遺傳算法14
2.1.4多目標遺傳局部搜索15
2.2差分進化16
2.3柔性作業車間調度的析取圖模型17
2.4標準測試問題19
2.4.1高維多目標優化測試問題19
2.4.2柔性作業車間調度測試問題20
2.5性能指標20
2.6本章小結22
第3章在基於聚合的多目標演化算法中平衡收斂性和多樣性24
3.1前言24
3.2類似算法簡介25
3.3基本思想26
3.4算法詳解27
3.4.1增強MOEA/D28
3.4.2增強EFR29
3.4.3可選歸一化過程30
3.4.4計算複雜度30
3.4.5討論31
3.5實驗設計32
3.5.1測試問題32
3.5.2性能指標34
3.5.3比較算法34
3.5.4實驗設置35
3.6算法的性能分析37
3.6.1參數K的影響38
3.6.2收斂性和多樣性的研究40
3.7與先進算法的比較44
3.7.1在歸一化問題上的比較44
3.7.2在非歸一化問題上的比較53
3.7.3進一步討論56
3.8本章小結57
目錄 智能演化優化〖2〗〖2〗 〖1〗 第4章基於新型支配關係的多目標演化算法58
4.1前言58
4.2基於θ支配的演化算法59
4.2.1算法框架59
4.2.2參考點的生成60
4.2.3重組算子61
4.2.4自適應歸一化62
4.2.5聚類算子62
4.2.6θ支配64
4.2.7θDEA的計算複雜度65
4.3實驗設計65
4.3.1測試問題65
4.3.2性能指標66
4.3.3比較算法67
4.3.4實驗設置68
4.4實驗結果70
4.4.1與NSGAⅢ和MOEA/D的比較70
4.4.2與先進算法的比較79
4.4.3參數θ的影響92
4.4.4進一步討論95
4.5本章小結96
第5章基於分解的多目標演化算法中的變化算子97
5.1前言97
5.2目標算法98
5.3實驗研究99
5.3.1實驗設置99
5.3.2NSGAⅢDE中參數的影響100
5.3.3NSGAⅢDE、NSGAⅢSBX: 探索與開發102
5.3.4NSGAⅢ變體之間的比較104
5.4本章小結109
第6章多目標優化中的目標降維: 演化多目標優化方法與綜合分析110
6.1前言110
6.2基本知識和背景112
6.2.1多目標優化112
6.2.2目標降維的基本概念113
6.2.3Pareto前沿的表示和誤導114
6.2.4目標降維的現有方法115
6.3多目標優化方法117
6.3.1基於支配結構的多目標優化公式117
6.3.2基於相關性的多目標優化公式118
6.3.3使用多目標演化優化算法119
6.3.4採用多目標優化方法的好處120
6.4對基於支配結構的方法和基於相關性方法的分析121
6.4.1理論基礎121
6.4.2基於支配結構的方法的優缺點122
6.4.3基於相關性方法的優勢和局限性123
6.5基準實驗125
6.5.1基準問題125
6.5.2樣本集的生成126
6.5.3算法的比較126
6.5.4多目標降維方法行為研究127
6.5.5演化多目標優化搜索的有效性130
6.5.6在演化多目標搜索領域中確定關鍵目標集的比較132
6.6應用於現實問題141
6.6.1應用於水資源問題141
6.6.2應用於汽車側面碰撞問題142
6.6.3討論143
6.7方法的優勢145
6.7.1關於輔助優化的目標降維145
6.7.2關於可視化和決策制定147
6.8本章小結148
第7章利用支配預測輔助的高成本多目標演化優化150
7.1前言150
7.2背景知識152
7.2.1多目標優化152
7.2.2θ支配153
7.2.3深度前饋神經網絡154
7.3θDEADP算法155
7.3.1概述155
7.3.2Representative解157
7.3.3基於支配預測的代理模型158
7.3.4兩階段預選策略160
7.3.5討論161
7.4實驗162
7.4.1實驗設計162
7.4.2多目標優化問題的性能166
7.4.3眾多目標優化問題的性能171
7.4.4θDEADP組成部分的研究177
7.5本章小結180
上篇總結181
下篇柔性作業車間調度問題及其優化求解
第8章FJS問題概述185
8.1多目標柔性作業車間調度問題185
8.2多目標柔性作業車間調度的研究現狀187
8.3模因算法189
8.3.1模因算法簡介189
8.3.2求解多目標組合優化問題的模因算法190
8.4本章小結191
第9章基於混合和聲搜索的柔性作業車間調度192
9.1前言192
9.2相關工作介紹193
9.2.1柔性車間調度193
9.2.2和聲搜索算法（HS算法）194
9.2.3混合和聲搜索（HHS）算法和混合TS算法（TSPCB）之間的差異194
9.3HHS算法196
9.3.1算法框架196
9.3.2和聲向量的表示196
9.3.3和聲向量的評估196
9.3.4初始化和聲記憶201
9.3.5新和聲向量生成202
9.3.6依賴問題的局部搜索203
9.3.7更新和聲記憶207
9.4實驗207
9.4.1實驗設置207
9.4.2計算結果和比較209
9.4.3HHS與其他算法的進一步比較215
9.5討論218
9.6本章小結219
第10章基於混合差分進化的柔性作業車間調度算法220
10.1前言220
10.2基本DE算法222
10.2.1算法初始化222
10.2.2不同載體的突變222
10.2.3交叉223
10.2.4選擇223
10.3針對FJSP的HDE223
10.3.1HDE概述223
10.3.2表示和初始化225
10.3.3雙向量編碼225
10.3.4轉換技術227
10.3.5局部搜索算法229
10.4實驗233
10.4.1實驗設置233
10.4.2Kacem實例的結果235
10.4.3BRdata實例的結果235
10.4.4BCdata實例的結果235
10.4.5HUdata實例的結果239
10.4.6HDE的進一步性能分析244
10.5本章小結251
第11章大規模柔性作業車間調度問題的集成搜索啟發式算法252
11.1前言252
11.2混合和聲搜索253
11.2.1HS簡介253
11.2.2HHS程序254
11.2.3HHS對FJSP的適配255
11.3大鄰域搜索260
11.3.1LNS概述260
11.3.2FJSP的基於約束的模型261
11.3.3約束破壞算法261
11.3.4構造算法262
11.4集成的啟發式搜索方法: HHS/LNS262
11.5實驗研究263
11.5.1實驗設置263
11.5.2HHS模塊性能分析263
11.5.3LNS模塊性能分析268
11.5.4整合效應269
11.5.5大規模基準實例的計算結果269
11.6本章小結276
第12章求解多目標柔性作業車間調度的模因算法278
12.1前言278
12.2算法概述279
12.3全局搜索策略280
12.3.1染色體編碼280
12.3.2染色體解碼281
12.3.3遺傳操作282
12.4局部搜索策略283
12.4.1個體選擇283
12.4.2針對個體的局部搜索284
12.5實驗分析289
12.5.1評價指標290
12.5.2局部搜索中接受準則的實驗研究291
12.5.3遺傳搜索和局部搜索混合的有效性293
12.5.4局部搜索中分層策略的有效性297
12.5.5與先進算法的比較299
12.6進一步討論307
12.7本章小結308
下篇總結309
參考文獻310
附錄A334
A.1英文縮寫對照表334
A.2圖片索引338
A.3表格索引342