基于全組合策略的多目標陰陽對算法

李大海，艾志剛，王振東

江西理工大學 信息工程學院，江西 贛州341000

復雜的工程優化問題經常涉及對多個目標函數的優化，而這些目標函數往往是相互沖突的[1-2]，即對于一個目標函數的改善可能會伴隨著另一個目標函數的劣化。例如，在一個工廠中，必須同時考慮提高生產速度、產品優良率和質量，以及降低成本等多個問題。但提高生產速度可能會損失成品率，而降低成本則一般會犧牲產品質量。多目標優化算法具有高度的通用性，可用于優化復雜的問題[3-5]，例如大型煉油廠調度[6]以及控制器設計[7]優化等。

一般來說，在多目標優化問題中，一個目標函數的最優解通常不是另一個目標函數的最優解。因此，當一個多目標問題的解不能同時滿足所有目標函數時，必須在這些目標函數之間平衡不同的解，從而產生一組該多目標的Pareto最優解集。

目前，已經有多種基于單目標優化算法的多目標優化算法被提出用于求解多目標優化問題。在這類多目標優化算法中，每一個目標函數都各自使用特定的單目標優化算法求解該目標函數的當前最優解，并使用一個集合保存由多個目標函數的當前最優構成的非支配解，作為最終的輸出。故此類多目標優化算法只需要一次執行就可以得到一定量的Pareto前沿。

基于前沿的陰陽對優化算法（Front-based Yin-Yang-Pair Optimization，F-YYPO）[8]是一種基于單目標陰陽對優化算法[9]（Yin-Yang-Pair Optimization，YYPO）發展而來的多目標優化算法。F-YYPO增加一個Pareto前沿集合SF，用于保存最新的非支配解，并為每個目標函數分配一對點——局部開發點Pi1 和全局探索點Pi2，然后對每個目標函數按照YYPO 的機制搜索該目標函數的解。F-YYPO在存檔操作時會將所有解集合并，并通過快速非支配排序對解集進行篩選以確定解集的Pareto前沿。F-YYPO總體上保持了YYPO的輕量特性和快速優化的能力，使其能夠在相對較短的時間內提供可靠的Pareto前沿。在文獻[8]中，Punnathanam等應用F-YYPO解決斯特林熱機的參數優化問題，并與兩個多目標優化算法MOGWO和gamultiobj進行性能比較，實驗結果表明F-YYPO 在斯特林熱機的參數優化問題上能取得比其他兩種算法更高的優化性能。

因為F-YYPO特殊的基于兩點交換的優化機制，在優化過程中，其優化個體易陷入停滯。該算法的性能也十分依賴于單一參數的設置與控制，并且其也沒有考慮多個目標函數之間的關聯性。本文對F-YYPO 算法存在的問題進行了細致的分析，并提出了一種新的改進算法F-ACYYPO。相比于F-YYPO，新算法采用了以下所示的三項改進措施：

（1）擴充優化個體，對不同的目標函數進行全組合優化，增加了對于不同優化目標函數之間相關性的考慮。

（2）引入了由本文作者提出并已在YYPO算法中被證明能有效增強搜索性能的縮放因子α的自適應調整機制[10]，將此項機制推廣到多目標優化算法F-ACYYPO上，以增強算法對不同優化問題的適應性。

（3）改進原F-YYPO 算法對存檔階段的操作，以提高優化個體的隨機分布。

為了測試提出的新改進算法F-ACYYPO 的性能，本文采用了CEC2009多目標優化算法性能評估特別會議（競賽）中的UF測試套件作為雙目標優化性能評估的測試用例。將F-ACYYPO與F-YYPO，以及目前已知的具有代表性的性能優良的5種多目標優化算法NSGA2、MOPSO、SPEA2、MOGWO，以及因易于使用和效果良好而被廣泛應用的gamultiobj算法進行性能比較。實驗結果表明，對于雙目標優化問題，在綜合性能指標反轉世代距離（Inverted Generational Distance，IGD）與超體積（Hyper Volume，HV）的統計下，F-ACYYPO明顯優于F-YYPO，并且相比于其他多目標優化算法，F-ACYYPO能夠在保持Pareto前沿解集質量的情況下，耗時更少且尋優速度更快。

為了公平地反映F-ACYYPO在三目標問題下的性能優勢，本文還采用了PlatEMO平臺上的DTLZ測試套件進行性能測試，并將F-ACYYPO 與在該平臺上已實現的5 個高性能多目標尋優算法NSGA2、MOPSO、SPEA2、MOEAD、GDE3 進行性能比較。實驗結果表明，對于三目標優化問題，在IGD、HV、GD 指標下，F-ACYYPO的性能明顯優于F-YYPO，并且相比于其他多目標優化算法，F-ACYYPO 能在將近1/2 的測試用例下占據更大的優勢。這表明在三目標優化問題中，F-ACYYPO能獲取更可靠的Pareto前沿。

1 相關工作

1985 年，Schaffer 提出向量評價遺傳算法[11]（Vector Evaluated Genetic Algorithm，VEGA），該算法被看作是進化算法求解多目標優化問題的開創性工作。1989年，Goldberg提出了用進化算法實現多目標的優化技術[12]，對多目標進化算法的研究具有重要的指導意義。

自20世紀90年代，多目標進化算法（Multi-Objective Evolutionary Algorithm，MOEA）的研究得到快速發展。基于Pareto 等級的個體選擇方法和基于適應度共享機制的種群保持策略的算法被稱為第一代多目標優化算法[13]。以保留精英機制為特征的算法被稱為第二代多目標優化算法[14-16]，其中以NSGA2[17]最具代表性。

目前已知的大多數具有代表性的高性能多目標優化算法都是基于已有的單目標算法發展而來，例如基于遺傳算法的NSGA2[17]、基于差分進化[18]算法的多目標差分進化算法[19]、基于灰狼優化算法[20]的多目標灰狼優化算法[21]、基于粒子群優化[22]的多目標粒子群優化[23-24]以及基于人工蜂群[25]的多目標人工蜂群[26]。上述多目標優化算法大都基于種群，而基于種群的多目標優化算法通常有結構復雜且計算量大等固有缺點。

Punnathanam等人[9]于2016年提出單目標YYPO算法，該算法為每個目標函數分配兩個點，并通過兩點的交替交換進行優化，大大降低了整體的計算量與復雜性。Punnathanam 等人于2017 年又提出了基于單目標YYPO 的多目標F-YYPO 算法[8]，其將YYPO 進行了簡單的擴展，并且引入快速非支配排序與擁擠距離測量來解決多目標優化問題。在文獻[8]中，F-YYPO被成功地應用于求解斯特林熱機多目標系統優化問題，并且實驗結果顯示，F-YYPO相比于MOGWO算法能在求解斯特林熱機的多目標系統優化問題中，取得更高的求解精度以及具有更快的搜索速度。

對于單目標YYPO問題，目前已經有多項研究對其進行改進，以在保持其輕量化搜索特性的前提下提高YYPO的搜索性能。Yang等人[7]使用YYPO算法對太陽能發電廠最佳控制參數進行尋優，并通過實驗證明，與其他單目標隨機搜索算法（ABC、ALO、DE、GWO、PSO）相比，YYPO 能在具有更低的計算復雜性的前提下擁有更強的求解精度與更快的搜索速度。Son等人[27]通過對YYPO 的Imax、α參數進行簡單的改進以及添加新的拆分，得到新的3D-YYPO算法，并成功將改進后的新算法應用于風力渦輪機優化設計。文獻[27]的實驗結果證明，3D-YYPO 的迭代次數和收斂時間遠小于PSO[28]和YYPO。2020 年，許秋艷等人[29]對YYPO 引入了混沌搜索和錯卦變換，使新算法計算精度更高和優化速度更快。本文作者也提出了一種采用縮放因子自適應的YYPO 改進算法IYYPO[12]，實驗結果表明，即使只是簡單地改進原YYPO的縮放因子的調整機制，也能有效地提高YYPO的搜索性能。

雖然YYPO以及其改進算法以計算輕量、容易實現以及高性能的特點，表明其是求解單目標優化問題的一個較好的選擇，但目前已知的基于單目標YYPO的多目標隨機搜索算法只有F-YYPO。因此有必要將新出現的關于YYPO 的改進措施引入F-YYPO，并進一步改進F-YYPO所采用的對于YYPO的簡單擴展方式，以得到性能更強，卻保持了YYPO結構與機制簡單并且計算輕量化特點的新多目標算法，從而為復雜多目標優化問題的求解提供更多的選擇。

2 基于前沿的陰陽對優化算法概述

F-YYPO 是單目標YYPO 算法在多目標問題上的簡單擴展。F-YYPO 為多目標問題的每個目標函數各分配一對優化個體和一對搜索半徑，并使用YYPO的基本機制進行解空間的搜索。每完成一次搜索后，F-YYPO將更新之后的個體保存在存檔集合SA中，當存檔大小達到閾值時則觸發存檔操作，更新點集SP與Pareto 集合SF。和YYPO 相似，F-YYPO 同樣有3 個用戶自定義參數(Imax、Imin、α)，其中Imax與Imin用于控制存檔集合的大小，縮放因子α用于控制搜索半徑δ的縮放程度。設多目標問題為求多個目標函數的最小化問題，并設fi,2 ≤i≤M為待優化的有限個目標函數。F-YYPO算法的步驟大致如下：

初始化：點集SP用于保存優化個體的決策變量，Pareto 前沿集合SF作為最終輸出的Pareto 前沿，存檔集合SA用于保存點集SP、最大存檔大小SizeArch等參數。

步驟1F-YYPO在每次開始迭代之前，都會進行適應度值比較，確保第i個目標的局部開發點Pi1 優于全局探索點Pi2，即fi(Pi1)＜fi(Pi2),1 ≤i≤M。然后將SP中的優化個體直接復制保存在SA中。隨后進行分割操作。

步驟2F-YYPO 的分割操作繼承自YYPO，其本質是基于超球體的解更新，即分別以優化個體為中心，以各自的δ為搜索半徑在超球體內進行位置更新。其中分割操作分為單向分割和D向分割，其更新公式分別如式（1）和式（2）所示：

其中，NP為新解的集合，表示第k個解中的第j個決策變量的值，P代表當前優化個體對應的解，Pj代表該解的第j個決策變量，δ是搜索半徑，r是0到1之間的隨機數，B是一個長度為D的二維隨機二進制字符串的矩陣。分割后會對優化個體P進行更新，更新方式如下：

步驟3如果存檔大小達到閾值則進行存檔操作，反之轉至步驟1。因為SP、SF、SA集合保存的是優化個體的決策變量，故只需去重合并。F-YYPO會對合并后的集合進行非支配排序，選出非支配點（排序等級為1的個體）進行操作，隨后進行擁擠度評估，確定角點與非角點。

算法1 F-YYPO偽代碼

為保持算法原有較低的計算復雜度，F-YYPO在存檔操作中參考了NSGA2中的快速非支配排序算法及擁擠度評估來確定Pareto 前沿。快速非支配排序算法以優化個體集合作為輸入，在輸入集合上附帶排序等級等信息作為輸出。

3 基于全組合策略的改進多目標陰陽對優化算法

3.1 F-ACYYPO設計前提

雖然F-YYPO相比部分算法（MOGWO、gamultiobj）有一定的性能優勢，但是F-YYPO依然存在一定的不足之處。

3.1.1 簡單的多目標優化方式

F-YYPO 的主要特性是利用兩點的持續交換進行目標函數的優化。從算法1 的偽代碼可以看出（第5～9行），F-YYPO 對不同的優化目標函數各分配了一對優化個體Pi1 和Pi2，但是每個優化個體只負責單一的目標。如P11 始終優化f1較小的解，P21 始終優化f2較小的解。

通過對F-YYPO 算法原理的分析可知，F-YYPO 只是將多目標問題拆分成多個單目標問題進行單獨優化，每個個體僅僅優化各自的目標函數，并沒有考慮到不同目標函數之間的相互影響。這種優化機制容易使優化個體陷入兩端，無法更好地進行全局優化。

圖1顯示了F-YYPO在多目標測試用例UF2上的迭代分布圖，每個子圖代表一對優化個體中的局部開發點從開始運行至結束所求解的目標函數值。UF2 是一個雙目標優化問題，具體表達式見表1，局部開發點P11 和全局探索點P12 負責優化目標函數f1；局部開發點P21和全局探索點P22 則負責優化目標函數f2。從圖1 中可以看出，在前200 次的迭代過程中，P11、P21 都能快速地將各自的優化函數優化至接近于0的值，并且在隨后的迭代過程中，依然能保持在0值附近進行局部搜索開發。但無論是P11 還是P21 均出現了分層的現象，出現此現象的原因在于P11、P21 共享同一個Pareto 前沿集，在對Pareto 前沿集更新后，會隨機地將角點更新為自身的值。例如：將f2較小但f1較大的值更新為P11；將f2較大但f1較小的值更新為P21。

圖1 F-YYPO求解過程分布圖Fig.1 Distribution of F-YYPO solution process

雖然P11 和P21 優化個體能各盡其職，并在各自負責的目標函數上都能獲得很好的解，但在多目標優化問題中，算法求解出的Pareto 前沿應盡可能地均勻分布，即應該均勻地鋪滿整個f2和f1區域。從圖1 中看出P11 與P21 優化個體在求解過程中存在大部分空白區域，這表明F-YYPO在求解的分布性上還有提高的空間。

3.1.2 固定的縮放因子α

F-YYPO使用了3個用戶定義參數(Imax、Imin、α)，而這3 個參數值的設置對算法的全局搜索與局部開發行為有重要影響。

式（3）是F-YYPO算法中對于Pi1 的搜索半徑δ1和Pi2 的搜索半徑δ2的變化公式。文獻[10]表明其中最關鍵的參數是α。若α設置得過大，則搜索半徑Pi1 的變化幅度小，此時算法的收斂速度將會大大降低；若α設置得過小，則搜索半徑δ的變化幅度大，此時Pi1 的搜索半徑會快速收縮，Pi2 的搜索半徑快速擴大，算法也會快速收斂并且極容易陷入局部最優。

2020 年，文獻[10]對YYPO 中的縮放因子α的調整機制進行了改進，提出了線性與非線性三種自適應變化情況的YYPO改進算法。實驗結果表明，改進后的新算法相比于原YYPO算法，擁有更快的收斂速度與求解精度。因為F-YYPO 繼承了YYPO 中的縮放因子α的調整機制，所以引入縮放因子α的自適應調整機制以進一步提高F-YYPO的性能。

3.1.3 存檔操作的局限性

從算法1存檔操作偽代碼（第25～33行）中可以看出，算法進行存檔操作時合并了優化個體集合SP、存檔集合SA和Pareto 集合SF，將合并后的算法進行非支配排序。但在后續的更新中F-YYPO 只選取了排序后的M ＋1 個點，將M個角點分別分配給每個優化個體的局部開發點Pi1，而將1個非角點同時復制給每個優化個體的全局搜索點Pi2。這種分配方式能夠使每個優化個體的局部開發點Pi1 更好地搜索其附近更優的解，但可能造成在算法求解過程中求解個體分布不均勻，使算法易陷入局部最優，從而難以更好地進行全局優化。

另外，從圖1 中也可以看出，每個優化個體的分布都集中在某一局部區域，比如P21 的分布解較為明顯地集中在f1值為0、0.6這兩塊區域，而P11 的分布解也有明顯地在局部區域集中表現。這也從側面說明，造成優化個體分布解不均勻的主要原因可能是F-YYPO 的存檔操作對排序后選出的點集的分配方式存在缺陷。

3.2 F-ACYYPO詳述

針對F-YYPO 存在的3 個缺陷，本文提出了一種基于F-YYPO的改進算法F-ACYYPO，即一種基于全組合策略的改進多目標陰陽對優化算法。

算法2 F-ACYYPO偽代碼

需要說明的是，F-ACYYPO 雖然增加了優化個體，但是并沒有增加目標函數的維度，其依然是在M個優化問題下進行優化。以下將詳細介紹算法的優化原理。

3.2.1 優化個體與目標問題的組合

多目標優化問題中目標函數之間一般存在一定的相互影響，并非是完全相互獨立。F-ACYYPO算法不僅考慮單一的目標適應度值，也考慮其他目標的適應度值，從而體現出多目標優化問題的整體性。以下以三目標優化問題為例進行介紹。

由于F-YYPO特殊的優化機制，算法會將每一步的優化個體保存在存檔中，存檔僅僅保存了個體的決策變量，存檔中個體的多樣性直接影響非支配排序后的排序等級。因此個體的選擇對算法性能有著重要影響，在F-YYPO 中選擇個體的標準是相關目標函數的適應度值，其會選擇適應度值最小的個體進行保存。F-YYPO中的優化個體P1只對f1進行優化，在兩點交換與分割操作時，以f1值為標準判斷更優個體，f1越小代表個體越優，其本質是對1×f1＋0×f2＋0×f3的優化，個體P2、P3同理。在此基礎上，F-ACYYPO 增加了4 個優化個體，P4以f1＋f2的和為標準判斷更優個體，和越小代表個體越優，P4本質是對1×f1＋1×f2＋0×f3的優化，個體P5、P6、P7同理。擇優標準的改變會使得在F-YYPO下的劣質個體，在F-ACYYPO下成為優質個體，從而選出更有多樣性的個體。

圖2 三目標組合方式Fig.2 Combination of three objectives

以DTLZ2真實前沿舉例，圖3是個體負責優化區域的大致示意圖。P1、P2、P3負責優化圖中右三角、左三角、下三角標志區域，可以看出，FYYPO 簡單地優化個體并沒有很好地對整個Pareto 前沿進行搜索優化。而F-ACYYPO 增加的P4、P5、P6、P7負責優化圖中圓形、方形、菱形、實心點所示區域，可以看出，由于擇優標準不同，F-ACYYPO增加的個體能更好地對整個前沿的個體進行選擇。

圖3 全組合優化個體示意圖Fig.3 Diagram of full-combination optimization

雖然優化個體的選擇標準可以通過設置權重進行一定調整，如w1×f1＋w2×f2＋w3×f3，但是在面對不同的多目標優化問題時，無法知道權重的取值會有最優的效果。因此為了算法對不同多目標優化問題的通用性，將所有標準的權重默認設置為1，這樣既能保持Pareto前沿的多樣性，又能使獲得的解均勻地分布在各個區間。

3.2.2 縮放因子α 的自適應調整機制

在文獻[10]中，作者將δ1與δ2的變化趨勢與迭代次數整合，提出對于縮放因子α的自適應調整機制。文獻中的實驗結果表明，指數函數型變化趨勢有較好的性能提升效果。故本文引入其中的指數函數型縮放因子α自適應調整機制代替原有的固定的縮放因子α，其具體公式如式（4）所示。

其中，k、c為用戶輸入的控制參數，k用于控制變化趨勢的快慢，c用于控制變化趨勢的下限，t為當前迭代次數，T為最大迭代次數。一般情況下需要滿足不等式k ＋c≤1，且c∈(0,1)，原因是在多目標陰陽對優化算法控制δ變化趨勢的同時，也要保證δ的合法性，其需要確保在每一次迭代中，δ1的變化比例小于1，而δ2的變化比例要大于1。

引入的自適應調整機制將直接替換掉原來的縮放因子α，消除搜索空間δ對縮放因子α的單一依賴。在每次進行存檔操作的最后對搜索空間δ通過式（4）進行更新。

圖4 是UF2 測試用例上優化個體P11 搜索空間δ的變化圖。圖中展示了不同α參數與自適應調整機制下的變化效果。

圖4 α 參數與自適應效果圖Fig.4 α parameters and adaptive renderings

從圖4中可以看出，較大的參數α快速收縮搜索空間δ，在200次迭代之前就已經收縮至0值附近，這樣雖然能使P11 有很好的局部開發能力，但極易使尋優過程陷入局部最優。然而較小的α雖然能保持搜索空間δ緩慢變化，但到了算法結束時搜索空間δ依然保持一個較大的值，這明顯是降低了算法的收斂性。而自適應調整機制能夠在前期很好地使搜索空間δ下降到0 值附近，在后期優化個體的兩點進行交換時也能保持快速地下降，使搜索空間δ保持較強的局部開發能力。

3.2.3 改進的存檔操作

如3.1.1小節中分析所示，F-YYPO在存檔操作中只使用了非支配排序后的M ＋1 個點進行更新，這種存檔更新方式存在較大的可能性使得算法求得的Pareto 前沿不能均勻分布，從而陷入局部最優。本文通過增大隨機性的方法跳出局部極值。通過增大隨機性跳出局部極值的典型算法有模擬退火（SA）算法。SA 算法前期大概率接受次優解就是一種增加隨機性的體現。

F-ACYYPO改進了存檔方式，其會選出非支配排序后所有等級為1 的點，并進行擁擠度評估，隨后通過隨機可重復的方式將角點分配給Pi1，非角點分配給Pi2。改進的目的是提高算法求解的多樣性，從而使算法求解的Pareto 前沿分布得更為均勻。F-ACYYPO 選擇隨機的方式更新個體，不需要擁擠度評估。

為觀察新存檔方法的效果，本文將F-ACYYPO 在多目標測試用例UF2 上并在相同的條件下進行測試。使P11 優化目標函數f1的值，P21 優化目標函數f2的值，P31 優化目標函數f2＋f1的值。

從圖5中可以看出，在前200次迭代中，各優化個體均能快速地將各自的優化函數值優化至一個較低的水平。并且在整個迭代過程中，各優化個體都均勻地分布在各自的目標函數值內，在大部分迭代次數下P11 與P21 均能控制在真實Pareto 前沿(f2,f1∈[0,1])區域內，同時新增的P31 優化個體在整個迭代過程中，都表現出均勻的穩定分布過程。

圖5 F-ACYYPO求解過程分布圖Fig.5 Distribution of F-ACYYPO solution process

3.2.4 復雜度分析

本小節對算法的復雜度進行漸進分析表述。通過文獻[9-10]可知，單目標優化算法YYPO 的時間復雜度與優化問題的維度D相關，其最好情況與最壞情況的時間復雜度均為O(D2)。

F-YYPO 在YYPO 的基礎上引入了NSGA2 中的非支配快速排序與擁擠距離評估，快速非支配排序算法的時間復雜度為O(MN2)，擁擠距離評估的時間復雜度為O(N2)，其中M代表目標個數，N代表種群大小。在F-YYPO中，因為目標個數M與種群大小N是相等的，所以F-YYPO 中的非支配快速排序與擁擠距離評估的時間復雜度分別為O(M3)=O(N3)、O(M2)=O(N2)。因為F-YYPO 為每個目標個數分配一個優化個體進行優化，所以F-YYPO算法的時間復雜度為O(MD2)。

F-ACYYPO 算法是F-YYPO 算法的改進，從FACYYPO中的3個改進措施來看，只有增加優化個體這個操作會增加算法的復雜度。結合F-ACYYPO的偽代碼，其具體的時間復雜度為O((2M－1)D2)。

雖然F-ACYYPO算法的復雜度與目標函數個數M呈指數階關系，但在眾多文獻中優化目標個數M通常只取2或者3，如文獻[30]對室內布局優化問題優化了f1總造價與f2審美需求，文獻[31]對集裝箱碼頭送箱外集卡預約問題優化了f1排隊長度與f2調度時間窗差異，文獻[32]對倉儲系統配置優化問題優化了f1系統吞吐能力最大化和f2系統成本最小化。也有文獻[33]指明，當優化問題涉及3個以上時，這類優化問題被進一步劃分為超多目標優化問題。因此在多目標優化問題上FYYPO與F-ACYYPO的時間復雜度可以近似為O(D2)，由此可以看出，本質上F-ACYYPO 時間復雜度相比FYYPO并沒有顯著增加。值得注意的是，在本文的所有實驗中，對測試函數的評估次數是相同的，這表明隨著F-ACYYPO優化個體的增多，每個優化個體的迭代次數會相應地減小，從而保證函數評估次數相同。

4 實驗

為測試F-ACYYPO 算法的性能，本文采用了2009年IEEE進化計算會議多目標優化算法性能評估特別會議（競賽）中的6個雙目標優化測試實例進行數值實驗，并進一步使用MATLAB 平臺下的PlatEMO 框架[34]的6個三目標用例進行數值實驗。

4.1 CEC2009測試用例

CEC2009 包含一組無約束測試實例和一組一般約束測試實例，考慮到對測試用例的仿真圖排版等問題，本文采用無約束測試實例中的6 個（UF2～UF7）進行實驗，剔除了相對簡單的UF1測試用例。表1顯示了各測試用例的表達式、搜索空間及其最優前沿。本文在實驗中將原F-YYPO算法與改進后的F-ACYYPO算法，以及經典的具有代表性的多目標優化算法NSGA2、SPEA2、MOPSO、MOGWO 和gamultiobj 算法進行評測，并比較分析各算法的優化性能。

表1 UF測試套件Table 1 UF test suite

CEC2009對性能評估做了如下規定：

（1）每個問題獨立運行30次，每次限定最大函數評估次數為300 000次。

（2）每獨立運行一次算法產生的非支配集中的最大個體數為：兩目標為100個，三目標為150個。

4.1.1 性能指標

反轉世代距離（IGD）[35]：世代距離的逆向映射，是一個綜合性能評價指標。它通過計算Pareto 最優解集前沿面上的每個點到算法獲取的非支配解集之間的最小距離和，來評價算法的收斂性能和分布性能。具體計算公式如下：

設P*為沿PF（Pareto Front）的一組均勻分布點（在目標空間中）。設A為PF的近似集，P*到A的平均距離定義為：

其中，d(v,A)是v與A中的點之間的最小歐幾里德距離。如果 |P*|足夠大，可以很好地表示PF，則IGD(A,P*)可以在某種意義上測量A的多樣性和收斂性。要使IGD(A,P*)的值較低，集合A必須非常接近PF，并且不能漏掉整個PF的任何部分，計算原理如圖6所示。

圖6 IGD指標示意圖Fig.6 Schematic diagram of IGD

除IGD 指標外，為綜合驗證算法的有效性和收斂性，本文還引入了GD指標與HV指標。

世代距離（Generational Distance，GD）[36]：表示算法求解獲得的Pareto 前沿（PFknown）與測試用例實際的

Pareto前沿（PFture）之間的間隔距離，計算公式如下：

其中，n是PFknown 中的向量個數，p=2,di表示目標空間上每一維向量與PFture 中最近向量之間的歐幾里德距離。若結果為0，則表示PFture等于PFknown；而其他的值表示PFknown 偏離PFtrue 的程度。計算原理如圖7所示。

圖7 GD指標示意圖Fig.7 Schematic diagram of GD

超體積（HV）[37]：近年來廣泛運用的一種綜合評價指標。通過非支配解集與參考點圍成的空間的超體積的值來評價多目標優化算法的綜合性能，計算公式如下：

其中，λ代表勒貝格測度，vi代表參考點和非支配個體構成的超體積，S代表非支配解集。計算原理如圖8所示。

圖8 HV指標示意圖Fig.8 Schematic diagram of HV

4.1.2 參數設置與實驗

參考文獻[8]中的實驗設置，在實驗中將F-YYPO的3 個主要參數分別設置為Imin=1,Imax=3，縮放因子α=20。

為保持公平性，F-ACYYPO參數也分別設置為Imin=1,Imax=3。關于縮放因子α自適應調整機制的2個參數k和c的設置，為了使F-ACYYPO在搜索前期能擁有較高的全局搜索性，并在后期擁有較快的收斂能力，將用于縮放因子的自適應調控參數k、c分別設置為0.6、0.4。其他對比算法[38-42]的參數均使用默認值。

表2是各算法30次運行后的平均IGD值。從表中可以看出，F-ACYYPO在IGD指標上全面優于原F-YYPO。與其他算法相比，F-ACYYPO 在4 個測試用例（UF2、UF5～UF7）上獲得了最優的IGD值。圖9是不同測試用例運行30次的IGD指標箱形圖，從圖中可以看出，在大部分測試用例上，F-ACYYPO算法求解的IGD值都較為穩定，異常值較少。這意味著F-ACYYPO 算法得到的解集比其他算法更接近最優Pareto前沿，并擁有更好的分布性與收斂性。

圖9 IGD指標箱形圖Fig.9 Box-plot of IGD

表2 雙目標IGDTable 2 Two-objective IGD

表3是各算法30次運行后的平均GD值。從表3中可以看出，改進后的F-ACYYPO，在GD 指標上均優于F-YYPO。但是在與其他算法進行比較時，效果甚微，只有在UF5上取得最優效果。在其他測試用例上NSGA2均獲得了最優的效果。這表明NSGA2算法擁有很強的收斂性，在局部更接近Pareto前沿。NSGA2有如此高的收斂效果可能是因為其基于種群的優化機制以及精英保留策略，使其在優化過程中一直保持從最優的整體進行優化。造成F-ACYYPO收斂性沒有占優的原因可能在于，算法在對新解的產生與篩選上較為笨拙，在分割操作中，無論是單向分割還是D向分割都是一次性產生大量解，并從產生出的大量解中只選出相對最優的一個解，這樣不僅造成了其他解的浪費，也對算法的收斂性有一定影響。文獻[27]對YYPO的分割操作進行了一定的改進，在產生新解時，將每次產生的新解與自身點進行比較，如果產生的新解優于原始點，則新解將替換為原始點，這確保每一代的點是當前的最佳點。文獻中的實驗數據也表明，該方法可以加快收斂速度。同理，F-ACYYPO 的分割操作也可以參照文獻[27]進行一定的改進，從而提高在多目標優化問題上的收斂性。

表3 雙目標優化GD Table 3 Two-objective GD

圖10 是不同測試用例上運行各算法30 次后的GD指標的箱型圖。從圖中可以看出，在大部分測試用例上，F-ACYYPO 比F-YYPO 都有更低更穩定的GD 值，這表明F-ACYYPO 在很大程度上提高了原算法F-YYPO 的收斂性。

圖10 GD指標箱形圖Fig.10 Box-plot of GD

與其他算法相比，F-ACYYPO 在UF5 測試用例上獲得了最優的GD 值。而NSGA2 在4 個測試用例上（UF2～UF3、UF6～UF7）都取得了最優的GD值。這意味著NSGA2 有更強的收斂性，除NSGA2 和SPEA2 之外，F-ACYYPO比其他算法（MOPSO、MOGWO、gamultiobj）能在大部分測試用例上獲得更優和更穩定的GD值。這表明F-ACYYPO依然擁有一定的競爭性。為了進一步說明F-ACYYPO的收斂性，對各算法的GD值、F-ACYYPO與NSGA2的GD值分別進行Friedman檢驗分析，見表4。

表4 Friedman檢驗Table 4 Friedman test

Friedman檢驗是一種非參數雙向方差分析方法，目的在于檢測兩個或多個數據之間的顯著性差異[43]。在各算法的GD值指標上，通過Friedman檢驗獲得的漸進顯著性p值為1.0×10－4，因為得到的p值小于0.05，所以在GD 值上效果最好的NSGA2 與其他算法之間存在顯著性的差異。其次通過對F-ACYYPO 與NSGA2 的GD 值進行Friedman 檢驗，得到的漸進顯著性p值為5.88×10－2，因為得到的p值大于0.05，所以在NSGA2與F-ACYYPO的GD指標上，兩者并不存在顯著性的差異。這說明NSGA2 在收斂性GD 指標上雖然獲得了各算法中最優的效果，但是通過F-ACYYPO 與NSGA2 的Friedman 檢驗可以知道，F-ACYYPO 與NSGA2 的GD值是很近似的，并沒有顯著性的差異。

表5是各算法在30次運行后的平均HV值，其值越大代表綜合性能越好。從表中可以看出，在該性能指標上，F-ACYYPO依然全面優于F-YYPO。F-ACYYPO在6 個測試用例中的3 個測試用例上（UF2、UF5、UF7）達到了最優值，而NSGA2 在2 個測試用例上達到了最優值。這再一次證實了F-ACYYPO不僅全面優于F-YYPO，而相比于其他算法，亦有很強的優化性能。

圖11 是不同測試用例運行各算法30 次后的關于HV 指標的箱型圖。從圖中可以看出，F-ACYYPO 比F-YYPO有更好的分布。與其他算法相比，F-ACYYPO在大部分測試用例中的HV 值都是相對穩定的。值得注意的是，在UF5 測試用例上，其他大部分算法的HV值接近于0，而F-ACYYPO 并沒有出現HV 值為0 的情況。這意味著F-ACYYPO使用的多組合優化個體的改進措施的確提高了Pareto前沿的分布效果。

圖11 HV指標箱形圖Fig.11 Box-plot of HV

結合表2、表3、表5進行綜合分析，F-ACYYPO雖然在收斂性指標GD上表現得不是十分出色，但與求解最優的GD值上并沒有顯著性的差異，在可接受的范圍之內；在綜合性指標IGD 與HV 上，F-ACYYPO 都具有較大的優勢，并且與其他算法相比，其在大部分用例下所用的時間是最少的。表明F-ACYYPO所采用的改進措施是有效的。

表5 雙目標HVTable 5 Two-objective HV

圖12 分別顯示了各算法在6 個測試用例上得到的解與真實的Pareto 前沿。從圖中可以直觀地看出，F-ACYYPO 在大部分的測試用例上收斂性與分布性都要比F-YYPO 更好，并且與其他算法相比，F-ACYYPO依然能保持較好的分布與收斂性。同時可從圖上看出，F-ACYYPO解的分布在雙目標問題上有著更優的表現。

圖12 UF各算法的Pareto前沿Fig.12 Pareto front of each algorithm on UF

4.2 PlatEMO平臺

PlatEMO[34]是一個供研究人員對現有多目標優化算法進行基準測試的開源平臺，該平臺實現了較多的高性能多目標優化算法。為了進一步測試新算法在三目標問題上的性能，進一步使用PlatEMO上的三目標測試用例，將F-ACYYPO和在該平臺上已經實現的5個高性能多目標算法NSGA2、GDE3、MOEAD、MOPSO、SPEA2在DTLZ測試套件（DTLZ2～DTLZ7）下進行三目標優化問題的數值實驗和性能比較。每個測試用例獨立運行10次。F-YYPO與F-ACYYPO的參數設置均與4.1.2小節相同。其他PlatEMO 平臺下的算法均使用默認參數。表6、表7、表8 展示了在DTLZ 測試套件上的所有算法中獲得的IGD、GD、和HV指標的測試值，限于篇幅原因，使用標準差來代替箱形圖表示獨立運行后各項指標的波動性。

表6 三目標IGDTable 6 Three-objective IGD

表7 三目標GDTable 7 Three-objective GD

表8 三目標HVTable 8 Three-objective HV

如表6所示，F-ACYYPO在所有測試用例上獲得了比F-YYPO 更好的IGD 值，并在4 個測試用例（DTLZ2、DTLZ3、DTLZ5、DTLZ7）上獲得了比其他算法更好的IGD 值。這意味著F-ACYYPO 所得到的解比其他算法更接近最優Pareto前沿，并且有更好的分布性。從各測試用例的標準差可以看出，F-ACYYPO所得到的解集波動性更小，也更具穩定性。

如表7所示，F-ACYYPO在所有測試用例上依然獲得了比F-YYPO 更好的GD 值，并在3 個測試用例（DTLZ2、DTLZ3、DTLZ5）上獲得了比其他算法更好的GD值。這表明在三目標優化問題上，F-ACYYPO 有較強的收斂性。

如表8所示，F-ACYYPO在大部分測試用例上獲得了比F-YYPO 更好的HV 值，并在DTLZ2、DTLZ5 兩個測試用例上獲得了比其他算法更大的HV 值。其中各算法在DTLZ3上的HV值均為0，這可能與DTLZ3優化問題自身有關，導致各算法都難以有較好的HV值。但在其他測試用例上各算法的HV值相差不大。

結合表6、表7、表8分析，F-ACYYPO在各項評價指標中均優于原F-YYPO 算法，并且與其他算法的對比中，在DTLZ2、DTLZ3、DTLZ5測試用例上，F-ACYYPO能在大多數測試用例中占據性能優勢。總的來說FACYYPO 在三目標問題上也有很好的表現。文獻[44]指出沒有一種算法能夠很好地解決每個優化問題，從而F-ACYYPO 算法對于求解多目標優化也有重要的研究意義。

圖13分別顯示了部分算法在各測試用例上得到的解與真實的Pareto前沿。因為部分算法的Pareto前沿相差較大，所以圖13 只描繪出了F-ACYYPO、NSGA2、MOEAD 以及SPEA2 算法的Pareto 前沿。從圖中可以直觀地看出，與其他算法相比F-ACYYPO 在大部分的三目標測試用例上，依然能保持較好的分布與收斂性。同時可從圖上看出，F-ACYYPO解的分布在雙目標問題上有著更優的表現。

圖13 DTLZ部分算法的Pareto前沿Fig.13 Pareto front of some algorithms on DTLZ

5 結束語

本文針對F-YYPO算法易陷入局部最優的情況，通過增加不同的優化個體作用于不同的目標函數以提高Pareto前沿分布的均勻性；引入已有研究成果的縮放因子α的自適應變化策略，消除了算法中搜索空間半徑δ值對于縮放因子α的單一依賴；改進了原文中的存檔操作等三項措施，以提高算法在全局上的探索，從而提出了F-ACYYPO 算法。從測試用例的實驗結果來看，無論是雙目標還是三目標優化問題，新改進算法F-ACYYPO在搜索精度和收斂速度上相比F-YYPO 全面占優。與其他代表性的高性能多目標優化算法相比，F-ACYYPO也有很強的競爭性，并且其還繼承了原F-YYPO的結構簡單、易實現以及計算輕量性的優點。F-ACYYPO仍存在值得改進的部分，如進一步增加算法在對多目標優化問題上的收斂性，擴展算法至超多目標優化問題，也可以改進算法，使算法適應組合優化問題和約束性問題等。