進化遷移優化算法綜述

伍洲，楊寒石，鄔俊俊，張海軍，宋晴

（1.重慶大學 自動化學院，重慶 400044；2.哈爾濱工業大學（深圳）計算機科學與技術學院，廣東 深圳 518055；3.北京郵電大學 人工智能學院，北京 100876）

0 概述

目前，智能優化已經成為科學和工程領域的研究熱點之一，可為復雜優化問題尋找最優解決方案［1］。常用優化算法可分為確定性算法和啟發式算法。確定性算法例如線性規劃［2］、非線性規劃［3］和最小二乘法［4］等，利用問題解析性質求解目標函數的全局或近似全局最優解［5］。啟發式算法例如遺傳算法（Genetic Algorithm，GA）［6］、差分進化（Differential Evolution，DE）算法［7］和蟻群算法［8］等，基于隨機過程搜索目標函數的全局或近似全局最優解。雖然確定性算法在線性或二次規劃問題中可保證最優解，但啟發式算法更加靈活且易于實現，特別是對于“黑盒”優化［9］、非凸優化［10］、NP 難組合優化［11-12］和大規模優化［13-14］等問題有較強的搜索能力。進化算法（Evolutionary Algorithm，EA）是模擬自然界生物進化的啟發式算法［15-17］，已成功應用于解決生物信息學、網絡安全等領域的優化問題［18-19］。傳統EA 在解決某個問題時往往默認先驗知識為零，從零開始進行隨機搜索［20-21］。然而，現實問題很少孤立存在，從已解決或正在解決的相關問題中提取的有效信息可以引導EA 高效解決新問題，降低計算過程的時間成本，提升計算結果的質量［22］。近年來，在機器學習中利用已解決任務的有用信息可求解相似學習任務，這種思想被稱為遷移學習（Transfer Learning，TL）［23］。然而，現有關于TL 的研究多數局限于機器學習和深度學習的應用，例如基于TL 的機器視覺［24］、醫學圖像識別［25］和機器故障診斷［26］等，將TL與EA 相結合的研究較少。通過學習歷史任務或正在優化任務中的有效知識，并遷移解決相關優化問題的進化算法統稱為進化遷移優化（Evolutionary Transfer Optimization，ETO）算法［27］。

現有少量國外研究成果與本文研究方向類似。文獻［23］首先簡要概述了2016 年至2021 年多任務進化計算領域的研究；其次重點介紹了多任務進化計算的基本實現方法，例如染色體編碼和解碼方案、何時進行知識遷移及個體評估和選擇方法等；然后介紹了多任務進化計算的相關擴展問題，例如算法框架、任務相似性度量和超多任務優化問題等。文獻［27］對ETO 領域已有工作進行了分類和概述，根據ETO 算法解決問題的類型將現有ETO 研究歸納為用于不確定環境優化的ETO 算法、用于多任務優化的ETO 算法、用于復雜優化的ETO 算法、用于多目標優化的ETO 算法及ETO 算法在機器學習上的應用等5 個方面。文獻［28］首先重點介紹了進化多任務優化（Evolutionary Multitask Optimization，EMTO）中任務選擇方法和任務遷移方法及兩者的關系；然后討論了EMTO 與EA 的融合問題，例如EMTO 算法在復雜優化問題上的應用、EMTO 算法演化過程中的資源分配策略和進化算法搜索策略等。文獻［29］根據知識遷移的模式（顯式或隱式）、算法的動態性質（靜態或自適應）及算法的設計模板（多因子優化或多種群多任務優化）對已有EMTO 算法進行分類和綜述。本文介紹ETO 的基本分類，并從源任務選擇、知識遷移、縮小搜索空間差異、進化算法搜索、進化資源分配等5 個角度入手對已有ETO 研究進行分類和綜述。

1 進化遷移優化分類

進化遷移優化是一種將遷移優化（Transfer Optimization，TO）的概念與進化算法結合在一起，將歷史任務或正在優化任務的種群演化軌跡、個體信息等知識遷移到相關新問題的EA 中，從而提升EA 優化性能的范式。目前，遷移優化可分為順序遷移優化（Sequential Transfer Optimization，STO）［30］、多任務優化（Multitask Optimization，MTO）［31］和多形式優化（Multiform Optimization，MFO）［32］。STO 旨在解決順序發生的任務，將解決歷史任務獲得的知識遷移到新任務中。MTO 旨在解決同時發生的多個任務，將任務優化過程中獲得的知識共享給其他任務。MFO 旨在通過使用不同的替代公式解決單個任務。

1.1 順序遷移優化

順序遷移優化是單方向的知識遷移。假設在求解任務Tk時，任務T1,T2,…,Tk-1已經在知識庫的協助下得到求解，且求解T1,T2,…,Tk-1獲得的有效信息被儲存在知識庫中［21］，其中，Tk表示為目標任務，T1,T2,…,Tk-1表示為源任務。STO 基本流程如圖1所示，STO 利用來自源任務的知識提升求解目標任務的EA 性能。

圖1 STO 基本流程Fig.1 Basic procedure of STO

1.2 多任務優化

多任務優化將當前所有同等優先級任務之間的有效信息共享，實現全方位知識遷移。MTO 基本流程如圖2 所示，任務T1,T2,…,Tk同時被優化，優化過程中得到的有效信息在公共知識庫中不斷更新并共享。

多任務優化算法解決的k個任務既可以是單目標優化問題（Single-objective Optimization Problem，SOP），也可以是多目標優化問題（Multi-objective Optimization Problem，MOP）。假設任務的目標函數及其搜索空間分別為fk和Ωk，則MTO 的定義如式（1）所示，MTO 的目標是找到每個任務的最優解［29］。

截至目前，實現進化多任務優化的范式有兩種：第一種是采用單個種群搜索多個任務的最優解，稱為單種群多任務優化（Single-population based Multitasking Optimization，SMO），多因子優化為SMO 的一種具體實現［33］；第二種是為每一個任務分配一個種群來搜索各自最優解的范式，稱為多種群多任務優化（Multi-population based Multitasking Optimization，MMO），生物群落共生進化算法為MMO 的一種具體實現［34］。

目前，在進化多任務優化算法中的知識遷移模式分為隱式知識遷移和顯式知識遷移。隱式知識遷移通過EA 的交叉算子實現不同任務種群間的知識交流，多數基于多因子優化范式的算法采用隱式知識遷移，例如多因子進化算法（Multifactorial Evolutionary Algorithm，MFEA）。顯式知識遷移是將一個任務完整的解決方案遷移到另一個任務的EA 中，在基于MMO 范式的算法中比較常見［35］。除此之外，顯式知識遷移也可以通過映射函數將源任務的解決方案映射到目標任務的搜索空間中［36］。

1.3 多形式優化

多形式優化的基本思想是將不同的替代公式組合成一個求解單目標優化問題的算法，避免了單一公式的缺陷。MFO 基本流程如圖3 所示。假設組合算法f含有k個替代公式f1,f2,…,fk，則MFO 的定義如式（2）所示，MFO 的目標是通過f1,f2,…,fk找到任務T的最優解。

圖3 MFO 基本流程Fig.3 Basic procedure of MFO

其中：ΩT為T的搜索空間。

2 進化遷移優化算法

本節從源任務選擇、知識遷移、縮小搜索空間差異、進化算法搜索、進化資源分配等5 個角度對ETO算法進行綜述。

2.1 源任務選擇

在進化遷移優化算法中，為目標任務選擇合適的源任務是知識遷移成功的關鍵。合適的源任務可以促進知識正向遷移，提升目標任務的優化效率。不合適的源任務會造成知識負遷移，對目標任務帶來負面影響。一些學者認為選擇源任務的關鍵指標是其他任務和目標任務的相似度。某個任務與目標任務的相似度越高，該任務越適合作為源任務。基于任務相似度的源任務選擇方法基本流程如圖4 所示。一種計算任務相似度的方法是測量任務解的分布差異。文獻［37］提出一種基于相似歷史信息遷移的骨干粒子群優化算法。該算法結合最大均值差異（Maximum Mean Discrepancy，MMD）和聚類算法提出一種基于多分布估計的最大均值差異指標來評價歷史任務和新任務解的分布差異，顯著提高了EA的收斂速度和搜索效率。另一種計算任務相似度的方法通過構建任務解的混合概率模型實現。文獻［38］介紹了任務解的混合概率模型與任務相似度的關系。每個源/目標任務概率模型代表一個任務的高質量解組成的種群?；旌细怕誓Ｐ蜑槊總€概率模型的加權和，概率模型的加權系數越大，源任務與目標任務間的互補性越強。基于該理論，文獻［38］提出一種基于自適應模型的遷移優化框架，首先建立源任務和目標任務的統一搜索空間，然后在統一搜索空間中利用求解源任務和目標任務獲得的知識建立混合概率模型來計算源任務和目標任務的相似度。該方法在SOP 和MOP 上均取得了較好的結果。文獻［39］證明了文獻［38］提出理論的正確性，并進一步證明了在混合概率模型中增加源任務概率模型的數量可縮小父代種群和子代種群的分布差異。

圖4 基于任務相似度的源任務選擇基本流程Fig.4 Basic procedure of source task selection based on task similarity

不同于以上根據任務相似度選擇源任務的方法，一些學者根據演化過程中其他任務的知識在目標任務上的反饋來選擇源任務。文獻［40］提出一種基于信用分配的自適應源任務選擇機制，在演化過程中為目標任務提供更多有利于解決方案的任務，獲得更高的知識遷移概率。

然而，一些學者認為僅根據任務的相似度或其他任務的知識遷移到目標任務后的反饋這種單一標準選擇源任務是不合適的，應該將兩者結合，綜合選擇源任務。文獻［41］提出一種基于高效代理輔助模型的多任務進化框架。首先利用協方差矩陣來表征任務歷史解的分布特征；然后計算不同任務協方差矩陣間的Kullback-Leibler 散度（Kullback-Leibler Divergence，KLD）來代表任務間的相似度；最后結合任務的相似度，利用基于信息素的協同搜索機制為目標任務選擇最合適的源任務。文獻［42］介紹一種多任務進化算法框架，并提出一種自適應選擇機制，通過種群進化過程中知識遷移積累的獎勵動態調整目標任務選擇其他任務作為源任務的概率，結合目標任務與其他任務的相似度來選擇源任務，同時采用檔案來記錄不同任務在演化過程中的相關信息，根據檔案中存儲的信息計算不同任務解的KLD 作為任務間的相似度。

2.2 知識遷移

在為目標任務選擇合適的源任務后，下一步就是任務間的知識遷移。學者們從多個角度對知識遷移策略進行設計。一些學者認為知識遷移策略需要與解決的問題類型相匹配，應該根據問題的特點設計知識遷移策略。例如動態優化問題，全局最優解會在優化過程中動態變化，即不同時間段的目標任務不同，因此解決動態優化問題的關鍵是如何為不斷變化的目標任務提供合適的知識。針對連續動態優化問題，一些學者將預測模型與ETO 算法相結合，利用求解歷史任務獲得的優秀種群個體訓練預測模型，在求解新任務時利用預測模型預測出適合求解新任務的種群個體，流程如圖5 所示。文獻［43］提出一種將EA 與時間序列模型相結合的種群個體位置預測模型。該模型利用歷史任務的最優解序列作為構建預測模型的知識。當檢測到目標函數發生變化時，預測出適合新任務的種群個體的位置。該方法在目標函數變化頻率較高的動態多目標優化問題中取得了較好的效果。文獻［44］提出一種基于回歸遷移學習的預測算法。該算法利用求解歷史問題得到的種群構建回歸預測模型，為求解新問題的EA 生成高質量的初始種群。2020 年至2021 年，該團隊在這個方向進行了較多的研究并取得了系列成果。文獻［45］提出一種基于內存驅動的流形遷移學習算法。該算法將EA 求解歷史任務獲得的最佳個體與流形遷移學習的特征相結合。當目標函數改變時，預測適合求解新任務的種群個體，將預測的種群個體與求解歷史任務得到的最佳種群個體合并，構成求解新任務的EA 初始種群。該算法顯著提高了EA初期的搜索能力，并降低了計算成本。文獻［46］定義了動態優化過程的膝關節點。當檢測到目標函數變化時，首先將膝關節點輸入預測模型獲得適應新問題的種群個體，然后采用基于不平衡遷移學習的方法生成新問題EA 的初始種群。該方法提高了EA的收斂速度和計算結果的質量。文獻［47］提出一種基于個體遷移的兩階段動態多目標進化算法。第一階段采用預學習策略生成引導種群來減少負遷移的可能性。第二階段采用文獻［48］提出的算法構建預測模型來產生優良的初始種群。

圖5 基于預測模型的知識遷移基本流程Fig.5 Basic procedure of knowledge transfer based on prediction models

在離散動態優化問題的背景下，文獻［49］提出一種具有學習能力的新型進化搜索范式來解決動態的車輛路徑規劃問題。該方法在優化過程的前期從其他相似車輛路徑規劃問題的解決方案中獲取結構化知識，當檢測到問題發生變化時利用獲取的結構化知識解決新問題，降低了求解新問題的時間成本。文獻［50］將遺傳規劃（Genetic Program，GP）與代理輔助模型結合，提出一種基于遺傳規劃和代理輔助模型的進化多任務算法。該算法為每個任務分配一個種群和一個代理輔助模型，通過代理輔助模型篩選種群中的優秀個體進入下一代，同時將代理輔助模型篩選出的優秀個體作為結構化知識在任務間進行遷移，提高了任務間知識遷移的效率和GP 的收斂速度。

對于不同領域相關問題間的知識遷移，文獻［51］介紹了一種進化模因計算范式，并基于該范式提出一種基于半正定規劃的同構遷移學習算法解決同構的帶有容量限制的車輛路徑規劃問題（Capacitated Vehicle Routing Problem，CVRP）和帶有容量限制的車輛弧路徑規劃問題（Capacitated Arc Routing Problem，CARP）。首先構造能夠表示源任務空間和目標任務空間共同特征的空間，然后利用半正定規劃在共同特征空間中對源任務進行學習，將獲得的知識模因存入知識庫。當解決新任務時，將知識庫中適合新任務的知識模因遷移到新任務的EA 種群中。該方法可以顯著提高EA 在CVRP 和CARP 上的搜索能力。文獻［52］在文獻［51］的基礎上提出一種基于半正定規劃的異構遷移學習算法來求解異構的CVRP 和CARP。

在單目標和多目標優化背景下，文獻［30］提出一種基于決策變量分析的進化順序遷移優化算法，實現了SOP、MOP 和超多目標優化問題（Manyobjective Optimization Problem，MaOP）之間的知識遷移。將MOP 和MaOP 的決策變量分為收斂性變量和決策性變量，收斂性變量含有源問題的搜索經驗，決策性變量含有源問題的搜索分布經驗。通過遷移收斂性變量加速目標問題EA 的收斂速度，通過遷移決策性變量增加目標問題EA 的種群多樣性。文獻［53］證明了將單目標優化問題轉化為多目標優化問題后進行求解，可有效降低EA 陷入局部最優解的風險。受文獻［53］的啟發，文獻［32］提出一種單目標和多目標多因子進化算法求解SOP。將SOP 分解為多個子問題，子問題組成MOP。采用MFEA 同時求解SOP 和MOP，將求解MOP 獲得的知識遷移到求解SOP 的種群中提升種群的局部搜索能力。文獻［54］提出一種多形式多目標進化優化算法求解MOP。通過高斯過程回歸構建目標MOP 的輔助任務，利用去噪自動編碼器實現目標MOP 和輔助任務間的顯式知識遷移。該方法能有效提高EA 種群的收斂速度。文獻［55］對多目標優化中的目標約簡進行了理論研究，并分析了兩種主流的目標縮減方法的優勢和劣勢。將目標縮減視為多目標搜索問題，介紹了該問題的3 個多目標公式。在此基礎上提出一種基于多目標約簡的多目標算法求解MOP。將根據目標MOP 構造的3 個多目標公式作為輔助任務，通過目標MOP 與輔助任務的知識交流提升求解目標MOP 的EA 性能。

在復雜優化問題背景下，文獻［56］構建一種基于結構遷移的遷移學習框架解決多標記標簽單核苷酸多態性選擇問題，并提出一種基于樹形結構的分布式估計算法（Estimation of Distributed Algorithm，EDA）來提取歷史問題中的結構知識，并利用結構知識構造聚合矩陣。當求解新問題時，將聚合矩陣遷移到新問題的EDA 中。該方法能夠降低學習EDA概率模型的時間成本，以及獲得高質量的計算結果。

除了上述針對ETO 算法解決的問題類型設計知識遷移策略這一研究方向，一些學者對演化過程中知識遷移的頻率或知識遷移的交叉算子等固定參數進行自適應設計。文獻［57］通過理論分析證明了知識遷移率對MFEA 的性能有較大的影響，合適的知識遷移率可以提升種群的收斂速度?；谠摾碚摚墨I［58］提出一種顯式多種群進化框架。首先計算通過知識遷移獲得的優于父代的子代個體數與父代個體數的比例，然后根據該比例自適應調整知識遷移的頻率。該方法有效抑制了負遷移的影響。文獻［59］提出一種基于自適應知識遷移的MFEA。該方法根據演化過程中獲得的知識遷移信息自適應選擇知識遷移的交叉算子，實驗結果表明其顯著優于MFEA。

2.3 搜索空間差異縮小

在進行任務間知識遷移時，如果源任務和目標任務的搜索空間相差較大，則需要考慮從源任務中遷移到目標任務的知識是否能夠適應目標任務的搜索空間，否則會造成知識負遷移。為了減少源任務和目標任務搜索空間的差異，學者們提出了一系列方法。一些學者通過設計搜索空間映射函數將求解歷史任務獲得的優秀種群個體映射到目標任務的搜索空間。本文以旅行商問題（Traveling Salesman Problem，TSP）來描述搜索空間映射的基本流程。如圖6 所示，源任務和目標任務均為含有6 個城市點的TSP，首先根據源TSP 和目標TSP 的城市點坐標學習兩者的映射關系，獲得映射函數M。例如，圖6 中源TSP 中的城市點S1與目標TSP 中的城市點T3間有映射關系，S1通過M映射到目標域后轉換為T3，然后將源TSP 的最優解通過M映射到目標TSP 的搜索空間中，與求解目標TSP 的EA 種群合并。文獻［60］提出一種基于單層去噪自動編碼器的進化搜索范式。該方法將歷史問題的知識通過單層去噪自動編碼器映射到新問題的搜索空間中，有效提升了異構問題間知識遷移的效率。文獻［61］對文獻［48］提出的算法缺陷進行分析，提出文獻［48］算法的改進版本。將EA 求解歷史任務獲得的種群個體通過線性核映射到新任務的搜索空間中作為新任務的EA 的初始種群。文獻［36］提出基于子空間對齊和自適應差分的多目標多任務進化算法。首先將源任務的數據和目標任務的數據輸入子空間對齊策略中生成映射矩陣，然后通過映射矩陣將源任務中的解映射到目標任務的搜索空間。

圖6 搜索空間映射基本流程Fig.6 Basic procedure of search space mapping

與上述通過設計搜索空間映射函數減少源任務和目標任務搜索空間差異的研究不同，文獻［62］提出一種決策變量翻譯策略。該策略將不同任務搜索空間中的解映射到統一的搜索空間中，減少了知識遷移時來自不同任務個體的位置差異。文獻［63］提出一種基于線性化領域自適應的進化多任務算法。該算法將簡單任務的搜索空間轉換為與復雜任務高度相關的重構空間，以減少簡單任務和復雜任務搜索空間的差異。

2.4 進化算法搜索

在ETO 算法中，EA 搜索目標任務最優解的過程可以分為兩部分：一部分是利用從源任務遷移到目標任務的知識引導EA 種群進行搜索；另一部分是目標任務EA 種群的進化搜索。上文介紹的策略均以通過提高知識遷移的效率來提升EA 的性能，而本節介紹的搜索策略旨在通過為EA 設計新的搜索算子［64］、將EA 中的某些固定參數改造成自適應參數［65］，以及針對特定問題為EA 構造搜索空間［66］等策略提升EA 種群的搜索能力，從而提升目標任務的優化效率。

一些學者利用代理模型來提升EA 的搜索能力。文獻［67］提出一種基于多問題代理的遷移進化多目標算法。該算法利用歷史問題或正在被優化的問題的模型知識和目標問題的模型知識構建多問題代理模型來增強目標問題上的EA 的搜索能力。該算法在測試函數尋優、復合材料制造和機器學習模型超參數自動調優等問題上的搜索能力顯著優于文獻［68］提出的算法。文獻［69］提出一種基于代理輔助模型的多任務模因算法。該算法為每個任務分配一個種群，種群的進化操作由3 個部分組成。首先利用DE 搜索任務的全局最優解，其次利用具有高斯過程的代理模型預測適合目標任務的種群個體，最后利用協方差矩陣自適應進化策略進行局部搜索。

一些學者通過設計新的搜索策略來提高EA 的搜索能力。文獻［70］提出一種基于遺傳變換策略和超矩形搜索策略的多因子進化算法。遺傳變換策略通過構造的任務映射向量將源任務的父代個體映射到距離目標任務的父代個體較近的位置上。基于對立學習的超矩形搜索策略旨在對每個任務的統一搜索空間和子空間進行高效的搜索和開發，使種群能夠搜索到更多的未探索區域。

一些學者針對ETO 算法解決的問題類型設計搜索策略。針對離散動態優化問題，文獻［71］提出一種基于GP 的進化多任務算法。該算法為每個任務分配一個種群，通過交叉算子實現任務間結構化知識的遷移，在求解同構和異構的動態柔性車間調度問題時均能獲得高質量的解。針對復雜的雙層優化問題，文獻［72］將TO 與文獻［73］提出的基于協同進化分解的雙層組合優化算法相結合，提出一種基于TO 的雙層組合優化算法。該算法通過協同進化策略提升EA 的全局搜索能力，在求解新問題時，利用從歷史問題中獲得的知識模因來指導EA 進行搜索，在求解供應鏈管理中的雙層生產分配問題上的表現優于文獻［73］提出的算法。

上述研究均是在傳統搜索策略的基礎上進行改進，文獻［74］則是對DE 中的多個傳統搜索策略進行理論研究，旨在選出最適合EMTO 算法的搜索策略。在參考文獻［75-77］后，文獻［74］提出一種通用的多任 務DE框架，包括DE/rand/1/bin、DE/best/1/bin 和DE/current-to-best/1/bin 這3 種傳統的DE 搜索策略，并通過設計對照實驗驗證3 種傳統DE 搜索策略的性能。通用的多任務DE 框架如圖7 所示。

圖7 多任務DE 框架Fig.7 Multitask DE framework

2.5 進化資源分配

在種群演化過程中，知識遷移并不總是有效的。當任務間的知識遷移對算法性能的提升小于種群的進化搜索對算法性能的提升時，應該將更多的進化資源分配給種群的進化搜索。反之，應把更多的資源分配給任務間的知識遷移?；谶@一思想，文獻［78］提出一種進化資源分配機制。當任務間的知識遷移產生負面影響時停止知識遷移，將進化資源全部分配給求解任務的EA 種群。該機制能夠有效平衡任務間和任務內計算資源的分配問題。

在多任務優化背景下，由于不同任務的復雜程度可能不同，在進化資源平均分配給每個任務的情況下，求解簡單任務的EA 收斂速度比求解復雜任務的EA 收斂速度快很多。因此，當求解簡單任務的EA 已經收斂到一個較好的解時，求解復雜任務的EA 還不能收斂到一個可接受的解。此時進行任務間的知識遷移，會破壞簡單任務EA 的收斂性，造成知識負遷移。針對這一問題，一些學者根據任務的計算復雜度為任務分配進化資源，復雜任務可獲得更多的進化資源，從而促進求解復雜任務的EA 種群收斂，流程如圖8 所示。

圖8 基于任務資源動態分配的進化資源分配流程Fig.8 Procedure of evolving resource allocation based on dynamic assignment of task resources

文獻［79］提出一種基于動態資源分配策略的進化多任務算法。該算法為每個任務分配一個種群，在每次分配計算資源前計算每個任務種群的進化程度，然后將種群進化程度轉換成進化指數。進化指數越低的任務被分配的計算資源越多。該方法能夠提升EA 的搜索能力，獲得較高質量的解。文獻［80］提出一種基于分解和動態資源分配策略的多目標多因子進化算法。該算法將多目標優化問題分解為多個單目標優化問題，使用單個種群同時求解所有單目標優化問題。種群在某個問題上的演化速度越快，分配給該問題的進化資源越多。該方法的整體性能優于文獻［81］提出的算法。

2.6 進化遷移優化算法總結

ETO 算法總結如表1 所示，對源任務選擇、知識遷移、縮小搜索空間差異、進化算法搜索和進化資源分配等5 個研究方向中提出的核心策略進行整理匯總，并分析它們的優劣勢。

表1 ETO 算法的核心策略和優劣勢分析Table 1 Analysis of the core strategies and advantages and disadvantages of the ETO algorithms

3 主要挑戰和未來研究方向

盡管進化遷移優化算法在進化計算領域取得了巨大的成功，但仍處于初步探索階段，在理論研究、算法設計和工程應用方面仍有許多潛在的研究方向。通過中國知網（China National Knowledge Infrastructure，CNKI）和Web of Science（WOS）對2014 年至2021 年發表的ETO 論文進行檢索，其中CNKI 檢索關鍵詞為“進化遷移優化”、“進化遷移學習”、“進化知識遷移”、“進化多任務優化”和“知識模因”。WOS檢索關鍵詞 為“evolutionary transfer optimization”、“evolutionary transfer learning”、“evolutionary knowledge transfer”、“evolutionary multitask optimization”和“knowledge memetic”。通過對文獻進行數據清洗，包括文獻合并除重、補全缺失信息及去除領域不相關文獻，最終得到41 篇中文文獻和180 篇英文文獻。2014 年至2021 年CNKI 及WOS 的ETO 論文數統計如圖9 所示，可以看出ETO相關論文發表數量在2018 年后增長迅速，ETO 在近幾年已成為研究熱點。

圖9 2014 至2021 年的ETO 論文數統計Fig.9 Statistics of ETO papers from 2014 to 2021

本文運用知識圖譜對ETO 相關論文進行數據挖掘、信息處理、知識計量和圖形繪制，揭示ETO 的發展趨勢，從而根據ETO 發展趨勢和經驗分析得出ETO 未來研究方向和每個方向面臨的挑戰。通過文獻關鍵詞搜索和聚類，對ETO 研究熱點分布進行可視化，圖10 為基于CNKI 的中文論文研究熱點分布，圖11 為基于WOS 的SCI 英文論文研究熱點分布。在圖10 和圖11 中：圓表示關鍵詞，圓的大小表示關鍵詞出現的頻次；連線表示節點與節點間曾經共現過；連線的密集程度表示該研究主題與其他主題聯系的緊密程度。通過對知識圖譜的分析，挖掘出ETO 未來研究方向：

圖10 CNKI 關鍵詞共現分析Fig.10 Co-occurrence analysis of CNKI keywords

圖11 WOS 關鍵詞共現分析Fig.11 Co-occurrence analysis of WOS keywords

1）多目標優化為當前最熱門的研究領域，在該領域中一些學者將研究重點放在如何提升任務間知識遷移的效率上，例如文獻［30，54-55］。為目標任務選擇合適的源任務是知識遷移成功的關鍵之一，而任務間的相似度是選擇合適任務的重要標準。目前還沒有能夠全面精確計算任務間相似度的方法，因此設計精準的相似度度量方法可作為未來研究方向之一。除了任務選擇方法，如何將源任務提供的知識轉換成適合目標任務搜索空間的知識也是知識遷移成功的關鍵，學者們對于該方向的研究多數基于同構問題，對異構問題間的知識遷移研究較少，例如SOP 與MOP 間的遷移、MOP 與MaOP 間的遷移，因此設計跨異構問題知識遷移的有效方法可作為未來研究方向之一。在該領域中還有一部分學者對如何提升ETO 算法的搜索能力和優化速度進行研究，如文獻［67，70］。雖然學者們在該方向上取得了巨大的成功，但是他們所解決的問題類型主要是中小規模優化問題，對于含有大量數據或決策變量的大規模優化問題，他們設計的算法可能會失效，因此開發解決大規模優化問題的ETO 算法也可作為未來的一個研究方向。

2）多形式優化是一種新興的遷移優化范式，在知識圖譜中還未出現與“多形式優化”和“multiform optimization”相關的關鍵詞，說明學者們對于設計基于多形式優化的ETO 算法的研究極少，因此基于多形式優化的ETO 算法是一個具有較大發展潛力的研究方向。

3）從知識圖譜中可以看出學者們在連續優化問題上的研究較多，在離散優化問題上的研究較少，如果能將針對連續優化問題提出的有效ETO 算法和理論轉譯成適合求解離散優化問題的ETO 算法和理論，則會極大地促進ETO 算法在離散優化領域的發展，對發電調度、物流配送和無人機路徑規劃等實際離散優化問題的求解具有借鑒作用。同樣地，將針對離散優化問題提出的ETO 算法和理論轉譯成適合求解連續優化問題的ETO 算法和理論，會對從事連續優化領域相關工作的學者提供啟發。因此，如何將連續優化理論與離散優化理論進行相互的轉譯可作為未來的一個研究方向。

基于以上分析，本文確定求解大規模優化問題的ETO 算法設計、跨異構問題知識遷移的有效方法設計、基于多形式優化范式的ETO 算法設計、精準的相似度度量方法設計和連續與離散優化問題的理論轉譯等5 個ETO 未來研究方向，下面將對這5 個未來研究方向和研究方向中存在的挑戰進行詳細敘述。

3.1 大規模優化問題求解

目前，利用進化算法求解大規模優化問題的研究越來越多，例如利用EA 求解激光雕刻［82］、物流調度［83］和車輛路徑規劃［84］等問題。由于大規模優化問題含有大量的數據或決策變量，EA 求解此類問題時無法在可接受的時間內搜索到較高質量的計算結果。為了提高EA 求解大規模優化問題的性能，學者們提出了不同的方法，例如采用“分治”的思想將大規模優化問題分解為許多適合EA 求解的小規模優化問題分別求解［85-86］，以及設計新的搜索算法［87］等。與以上方法相比，ETO 為提升EA 求解大規模優化問題的性能提供了新思路，正如前文所述，問題很少孤立存在，將EA 求解中小規模優化問題獲得的知識遷移到相似的大規模優化問題來指導EA 的搜索過程，有助于提升EA 的搜索能力，從而提升計算結果的質量。具體研究思路為：1）將ETO 和“分治”思想相結合，在利用“分治”思想將大規模優化問題分解成許多小規模優化問題后，采用ETO 算法實現多個小規模優化問題的知識遷移；2）設計能夠將中小規模優化問題中的知識高效遷移到大規模優化問題搜索空間中的方法。

3.2 跨異構問題的知識遷移

目前，一些學者已經實現了跨異構問題的知識遷移，例如文獻［30，71］實現了單目標優化問題和多目標優化問題間的知識轉移，文獻［60］采用去噪自編碼器作為異構問題間知識遷移的橋梁，將源問題的解映射到目標任務的搜索空間中。但是，在MOP領域，目前的跨異構問題知識遷移方法多數忽略了任務之間的關系［88］。從種群共生方式的角度看，存在3 種方式：第一種方式是共生，不同種群之間相互合作、互惠互利，對所有種群均帶來積極影響；第二種方式是寄生，不同種群共同生活，既有積極的影響，又有消極的影響；第三種方式是競爭，不同種群之間相互競爭，對所有種群均帶來消極影響。同時，任務關系也可以解釋為共生、寄生和競爭［54］，假設任務1 是三目標優化問題，任務2 是兩目標優化問題，兩個任務的Pareto 最優解集在目標函數空間的投影不同，任務為競爭關系，一個任務的改善會導致另一個任務的惡化［89］。該領域面臨的另一個挑戰是當源問題與目標問題維度差距過大時，現有的知識遷移方法往往會失效。具體研究思路為：1）設計考慮任務間關系的跨異構問題知識遷移方法；2）設計能夠有效解決維度相差較大問題間知識遷移的方法。

3.3 多形式優化范式

多形式優化是近期提出的新遷移優化概念，基本思想是將不同的替代公式組合成一個求解單目標優化問題的算法，避免了單一公式的缺陷［90］。由于不同的替代公式代表不同的搜索策略，在多任務環境中，每個公式都可以作為輔助任務將自身的搜索經驗傳遞給其他任務，因此在該環境下的多形式優化范式面臨的一個巨大挑戰是如何有效地跨不同公式進行知識遷移。由于EA 的種群個體和種群移動軌跡中包含搜索經驗，因此可以將EA 作為實現不同公式間有效知識遷移的媒介引入多形式優化中，利用源任務種群存儲的搜索經驗來指導目標任務的EA 的搜索過程。此外，多形式優化面臨的另一個挑戰是由于計算資源的限制，難以確定哪個公式最適合求解當前的問題。具體研究思路為：1）設計能夠針對特定問題自適應選擇替代公式的ETO 算法；2）設計可以實現跨異構問題知識遷移的方法，例如在高維度問題和低維度問題之間進行知識遷移。

3.4 相似度度量

在進化遷移優化算法中，為目標任務選擇合適的源任務是知識遷移能否成功的關鍵，任務間的相似度是選擇源任務的重要依據。當前度量任務間相似度的方法大致可以分為兩類：第一類是利用源問題和目標問題的數據樣本分布的差異來衡量任務間的相似度，例如文獻［37］計算源問題解和目標問題解的MMD，利用MMD 衡量任務間的相似度；第二類是利用源問題和目標問題解分布的差異來衡量任務間的相似度，例如文獻［41-42］將源任務和目標任務解分布的KLD 作為任務間的相似度。然而以上兩類方法均沒有考慮到求解不同任務的EA 種群進化方向的相似性，在忽略遷移時機是否恰當的情況下，當種群進化方向不相似時，很可能造成負遷移［88］。具體研究思路為：1）針對特定問題設計特定的任務相似度度量方法；2）研發新的衡量任務相似度的指標。

3.5 連續與離散優化問題的理論轉譯

目前，多數進化遷移優化理論均是基于連續優化問題背景或離散優化問題背景提出的，將適用于連續優化問題的進化遷移優化理論與適用于離散優化問題的理論互相轉譯，可有效促進ETO 在連續優化領域和離散優化領域的發展，一些學者在該方向進行了研究，例如文獻［91］將文獻［92］中的MFEAII 算法包含的理論轉譯成了適合求解離散優化問題的理論，提出dMFEA-II 算法來求解TSP。然而，據筆者所知目前在該方向的研究很少，阻礙該方向發展的主要挑戰是適用于連續優化問題的ETO 算法中所包含的一些理論只適用于連續型數據，缺少與之對等的適用于離散型數據的理論。具體研究思路為：1）設計求解連續優化問題的ETO 理論的離散型版本；2）開發測試轉譯后的算法性能的基準問題。

4 結束語

本文從源任務選擇、知識遷移、縮小搜索空間差異、進化算法搜索和進化資源分配等研究方向入手，對現有進化遷移優化算法進行歸納總結。通過分析5 個研究方向的核心策略和優劣勢得出，ETO 算法在搜索能力和收斂速度上相比于傳統EA 具有一定優勢。后續將對利用ETO 算法高效求解大規模優化問題、實現異構問題的高效知識遷移、多形式優化范式的研發、精準的相似度度量方法設計以及連續與離散問題的理論轉譯等方面做進一步研究。