基于全組合策略的多目標(biāo)陰陽(yáng)對(duì)算法

李大海，艾志剛，王振東

江西理工大學(xué) 信息工程學(xué)院，江西 贛州341000

復(fù)雜的工程優(yōu)化問(wèn)題經(jīng)常涉及對(duì)多個(gè)目標(biāo)函數(shù)的優(yōu)化，而這些目標(biāo)函數(shù)往往是相互沖突的[1-2]，即對(duì)于一個(gè)目標(biāo)函數(shù)的改善可能會(huì)伴隨著另一個(gè)目標(biāo)函數(shù)的劣化。例如，在一個(gè)工廠中，必須同時(shí)考慮提高生產(chǎn)速度、產(chǎn)品優(yōu)良率和質(zhì)量，以及降低成本等多個(gè)問(wèn)題。但提高生產(chǎn)速度可能會(huì)損失成品率，而降低成本則一般會(huì)犧牲產(chǎn)品質(zhì)量。多目標(biāo)優(yōu)化算法具有高度的通用性，可用于優(yōu)化復(fù)雜的問(wèn)題[3-5]，例如大型煉油廠調(diào)度[6]以及控制器設(shè)計(jì)[7]優(yōu)化等。

一般來(lái)說(shuō)，在多目標(biāo)優(yōu)化問(wèn)題中，一個(gè)目標(biāo)函數(shù)的最優(yōu)解通常不是另一個(gè)目標(biāo)函數(shù)的最優(yōu)解。因此，當(dāng)一個(gè)多目標(biāo)問(wèn)題的解不能同時(shí)滿(mǎn)足所有目標(biāo)函數(shù)時(shí)，必須在這些目標(biāo)函數(shù)之間平衡不同的解，從而產(chǎn)生一組該多目標(biāo)的Pareto最優(yōu)解集。

目前，已經(jīng)有多種基于單目標(biāo)優(yōu)化算法的多目標(biāo)優(yōu)化算法被提出用于求解多目標(biāo)優(yōu)化問(wèn)題。在這類(lèi)多目標(biāo)優(yōu)化算法中，每一個(gè)目標(biāo)函數(shù)都各自使用特定的單目標(biāo)優(yōu)化算法求解該目標(biāo)函數(shù)的當(dāng)前最優(yōu)解，并使用一個(gè)集合保存由多個(gè)目標(biāo)函數(shù)的當(dāng)前最優(yōu)構(gòu)成的非支配解，作為最終的輸出。故此類(lèi)多目標(biāo)優(yōu)化算法只需要一次執(zhí)行就可以得到一定量的Pareto前沿。

基于前沿的陰陽(yáng)對(duì)優(yōu)化算法（Front-based Yin-Yang-Pair Optimization，F(xiàn)-YYPO）[8]是一種基于單目標(biāo)陰陽(yáng)對(duì)優(yōu)化算法[9]（Yin-Yang-Pair Optimization，YYPO）發(fā)展而來(lái)的多目標(biāo)優(yōu)化算法。F-YYPO增加一個(gè)Pareto前沿集合SF，用于保存最新的非支配解，并為每個(gè)目標(biāo)函數(shù)分配一對(duì)點(diǎn)——局部開(kāi)發(fā)點(diǎn)Pi1 和全局探索點(diǎn)Pi2，然后對(duì)每個(gè)目標(biāo)函數(shù)按照YYPO 的機(jī)制搜索該目標(biāo)函數(shù)的解。F-YYPO在存檔操作時(shí)會(huì)將所有解集合并，并通過(guò)快速非支配排序?qū)饧M(jìn)行篩選以確定解集的Pareto前沿。F-YYPO總體上保持了YYPO的輕量特性和快速優(yōu)化的能力，使其能夠在相對(duì)較短的時(shí)間內(nèi)提供可靠的Pareto前沿。在文獻(xiàn)[8]中，Punnathanam等應(yīng)用F-YYPO解決斯特林熱機(jī)的參數(shù)優(yōu)化問(wèn)題，并與兩個(gè)多目標(biāo)優(yōu)化算法MOGWO和gamultiobj進(jìn)行性能比較，實(shí)驗(yàn)結(jié)果表明F-YYPO 在斯特林熱機(jī)的參數(shù)優(yōu)化問(wèn)題上能取得比其他兩種算法更高的優(yōu)化性能。

因?yàn)镕-YYPO特殊的基于兩點(diǎn)交換的優(yōu)化機(jī)制，在優(yōu)化過(guò)程中，其優(yōu)化個(gè)體易陷入停滯。該算法的性能也十分依賴(lài)于單一參數(shù)的設(shè)置與控制，并且其也沒(méi)有考慮多個(gè)目標(biāo)函數(shù)之間的關(guān)聯(lián)性。本文對(duì)F-YYPO 算法存在的問(wèn)題進(jìn)行了細(xì)致的分析，并提出了一種新的改進(jìn)算法F-ACYYPO。相比于F-YYPO，新算法采用了以下所示的三項(xiàng)改進(jìn)措施：

（1）擴(kuò)充優(yōu)化個(gè)體，對(duì)不同的目標(biāo)函數(shù)進(jìn)行全組合優(yōu)化，增加了對(duì)于不同優(yōu)化目標(biāo)函數(shù)之間相關(guān)性的考慮。

（2）引入了由本文作者提出并已在YYPO算法中被證明能有效增強(qiáng)搜索性能的縮放因子α的自適應(yīng)調(diào)整機(jī)制[10]，將此項(xiàng)機(jī)制推廣到多目標(biāo)優(yōu)化算法F-ACYYPO上，以增強(qiáng)算法對(duì)不同優(yōu)化問(wèn)題的適應(yīng)性。

（3）改進(jìn)原F-YYPO 算法對(duì)存檔階段的操作，以提高優(yōu)化個(gè)體的隨機(jī)分布。

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

為了公平地反映F-ACYYPO在三目標(biāo)問(wèn)題下的性能優(yōu)勢(shì)，本文還采用了PlatEMO平臺(tái)上的DTLZ測(cè)試套件進(jìn)行性能測(cè)試，并將F-ACYYPO 與在該平臺(tái)上已實(shí)現(xiàn)的5 個(gè)高性能多目標(biāo)尋優(yōu)算法NSGA2、MOPSO、SPEA2、MOEAD、GDE3 進(jìn)行性能比較。實(shí)驗(yàn)結(jié)果表明，對(duì)于三目標(biāo)優(yōu)化問(wèn)題，在IGD、HV、GD 指標(biāo)下，F(xiàn)-ACYYPO的性能明顯優(yōu)于F-YYPO，并且相比于其他多目標(biāo)優(yōu)化算法，F(xiàn)-ACYYPO 能在將近1/2 的測(cè)試用例下占據(jù)更大的優(yōu)勢(shì)。這表明在三目標(biāo)優(yōu)化問(wèn)題中，F(xiàn)-ACYYPO能獲取更可靠的Pareto前沿。

1 相關(guān)工作

1985 年，Schaffer 提出向量評(píng)價(jià)遺傳算法[11]（Vector Evaluated Genetic Algorithm，VEGA），該算法被看作是進(jìn)化算法求解多目標(biāo)優(yōu)化問(wèn)題的開(kāi)創(chuàng)性工作。1989年，Goldberg提出了用進(jìn)化算法實(shí)現(xiàn)多目標(biāo)的優(yōu)化技術(shù)[12]，對(duì)多目標(biāo)進(jìn)化算法的研究具有重要的指導(dǎo)意義。

自20世紀(jì)90年代，多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm，MOEA）的研究得到快速發(fā)展?；赑areto 等級(jí)的個(gè)體選擇方法和基于適應(yīng)度共享機(jī)制的種群保持策略的算法被稱(chēng)為第一代多目標(biāo)優(yōu)化算法[13]。以保留精英機(jī)制為特征的算法被稱(chēng)為第二代多目標(biāo)優(yōu)化算法[14-16]，其中以NSGA2[17]最具代表性。

目前已知的大多數(shù)具有代表性的高性能多目標(biāo)優(yōu)化算法都是基于已有的單目標(biāo)算法發(fā)展而來(lái)，例如基于遺傳算法的NSGA2[17]、基于差分進(jìn)化[18]算法的多目標(biāo)差分進(jìn)化算法[19]、基于灰狼優(yōu)化算法[20]的多目標(biāo)灰狼優(yōu)化算法[21]、基于粒子群優(yōu)化[22]的多目標(biāo)粒子群優(yōu)化[23-24]以及基于人工蜂群[25]的多目標(biāo)人工蜂群[26]。上述多目標(biāo)優(yōu)化算法大都基于種群，而基于種群的多目標(biāo)優(yōu)化算法通常有結(jié)構(gòu)復(fù)雜且計(jì)算量大等固有缺點(diǎn)。

Punnathanam等人[9]于2016年提出單目標(biāo)YYPO算法，該算法為每個(gè)目標(biāo)函數(shù)分配兩個(gè)點(diǎn)，并通過(guò)兩點(diǎn)的交替交換進(jìn)行優(yōu)化，大大降低了整體的計(jì)算量與復(fù)雜性。Punnathanam 等人于2017 年又提出了基于單目標(biāo)YYPO 的多目標(biāo)F-YYPO 算法[8]，其將YYPO 進(jìn)行了簡(jiǎn)單的擴(kuò)展，并且引入快速非支配排序與擁擠距離測(cè)量來(lái)解決多目標(biāo)優(yōu)化問(wèn)題。在文獻(xiàn)[8]中，F(xiàn)-YYPO被成功地應(yīng)用于求解斯特林熱機(jī)多目標(biāo)系統(tǒng)優(yōu)化問(wèn)題，并且實(shí)驗(yàn)結(jié)果顯示，F(xiàn)-YYPO相比于MOGWO算法能在求解斯特林熱機(jī)的多目標(biāo)系統(tǒng)優(yōu)化問(wèn)題中，取得更高的求解精度以及具有更快的搜索速度。

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

雖然YYPO以及其改進(jìn)算法以計(jì)算輕量、容易實(shí)現(xiàn)以及高性能的特點(diǎn)，表明其是求解單目標(biāo)優(yōu)化問(wèn)題的一個(gè)較好的選擇，但目前已知的基于單目標(biāo)YYPO的多目標(biāo)隨機(jī)搜索算法只有F-YYPO。因此有必要將新出現(xiàn)的關(guān)于YYPO 的改進(jìn)措施引入F-YYPO，并進(jìn)一步改進(jìn)F-YYPO所采用的對(duì)于YYPO的簡(jiǎn)單擴(kuò)展方式，以得到性能更強(qiáng)，卻保持了YYPO結(jié)構(gòu)與機(jī)制簡(jiǎn)單并且計(jì)算輕量化特點(diǎn)的新多目標(biāo)算法，從而為復(fù)雜多目標(biāo)優(yōu)化問(wèn)題的求解提供更多的選擇。

2 基于前沿的陰陽(yáng)對(duì)優(yōu)化算法概述

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

初始化：點(diǎn)集SP用于保存優(yōu)化個(gè)體的決策變量，Pareto 前沿集合SF作為最終輸出的Pareto 前沿，存檔集合SA用于保存點(diǎn)集SP、最大存檔大小SizeArch等參數(shù)。

步驟1F-YYPO在每次開(kāi)始迭代之前，都會(huì)進(jìn)行適應(yīng)度值比較，確保第i個(gè)目標(biāo)的局部開(kāi)發(fā)點(diǎn)Pi1 優(yōu)于全局探索點(diǎn)Pi2，即fi(Pi1)＜fi(Pi2),1 ≤i≤M。然后將SP中的優(yōu)化個(gè)體直接復(fù)制保存在SA中。隨后進(jìn)行分割操作。

步驟2F-YYPO 的分割操作繼承自YYPO，其本質(zhì)是基于超球體的解更新，即分別以?xún)?yōu)化個(gè)體為中心，以各自的δ為搜索半徑在超球體內(nèi)進(jìn)行位置更新。其中分割操作分為單向分割和D向分割，其更新公式分別如式（1）和式（2）所示：

其中，NP為新解的集合，表示第k個(gè)解中的第j個(gè)決策變量的值，P代表當(dāng)前優(yōu)化個(gè)體對(duì)應(yīng)的解，Pj代表該解的第j個(gè)決策變量，δ是搜索半徑，r是0到1之間的隨機(jī)數(shù)，B是一個(gè)長(zhǎng)度為D的二維隨機(jī)二進(jìn)制字符串的矩陣。分割后會(huì)對(duì)優(yōu)化個(gè)體P進(jìn)行更新，更新方式如下：

步驟3如果存檔大小達(dá)到閾值則進(jìn)行存檔操作，反之轉(zhuǎn)至步驟1。因?yàn)镾P、SF、SA集合保存的是優(yōu)化個(gè)體的決策變量，故只需去重合并。F-YYPO會(huì)對(duì)合并后的集合進(jìn)行非支配排序，選出非支配點(diǎn)（排序等級(jí)為1的個(gè)體）進(jìn)行操作，隨后進(jìn)行擁擠度評(píng)估，確定角點(diǎn)與非角點(diǎn)。

算法1 F-YYPO偽代碼

為保持算法原有較低的計(jì)算復(fù)雜度，F(xiàn)-YYPO在存檔操作中參考了NSGA2中的快速非支配排序算法及擁擠度評(píng)估來(lái)確定Pareto 前沿?？焖俜侵渑判蛩惴ㄒ?xún)?yōu)化個(gè)體集合作為輸入，在輸入集合上附帶排序等級(jí)等信息作為輸出。

3 基于全組合策略的改進(jìn)多目標(biāo)陰陽(yáng)對(duì)優(yōu)化算法

3.1 F-ACYYPO設(shè)計(jì)前提

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

3.1.1 簡(jiǎn)單的多目標(biāo)優(yōu)化方式

F-YYPO 的主要特性是利用兩點(diǎn)的持續(xù)交換進(jìn)行目標(biāo)函數(shù)的優(yōu)化。從算法1 的偽代碼可以看出（第5～9行），F(xiàn)-YYPO 對(duì)不同的優(yōu)化目標(biāo)函數(shù)各分配了一對(duì)優(yōu)化個(gè)體Pi1 和Pi2，但是每個(gè)優(yōu)化個(gè)體只負(fù)責(zé)單一的目標(biāo)。如P11 始終優(yōu)化f1較小的解，P21 始終優(yōu)化f2較小的解。

通過(guò)對(duì)F-YYPO 算法原理的分析可知，F(xiàn)-YYPO 只是將多目標(biāo)問(wèn)題拆分成多個(gè)單目標(biāo)問(wèn)題進(jìn)行單獨(dú)優(yōu)化，每個(gè)個(gè)體僅僅優(yōu)化各自的目標(biāo)函數(shù)，并沒(méi)有考慮到不同目標(biāo)函數(shù)之間的相互影響。這種優(yōu)化機(jī)制容易使優(yōu)化個(gè)體陷入兩端，無(wú)法更好地進(jìn)行全局優(yōu)化。

圖1顯示了F-YYPO在多目標(biāo)測(cè)試用例UF2上的迭代分布圖，每個(gè)子圖代表一對(duì)優(yōu)化個(gè)體中的局部開(kāi)發(fā)點(diǎn)從開(kāi)始運(yùn)行至結(jié)束所求解的目標(biāo)函數(shù)值。UF2 是一個(gè)雙目標(biāo)優(yōu)化問(wèn)題，具體表達(dá)式見(jiàn)表1，局部開(kāi)發(fā)點(diǎn)P11 和全局探索點(diǎn)P12 負(fù)責(zé)優(yōu)化目標(biāo)函數(shù)f1；局部開(kāi)發(fā)點(diǎn)P21和全局探索點(diǎn)P22 則負(fù)責(zé)優(yōu)化目標(biāo)函數(shù)f2。從圖1 中可以看出，在前200 次的迭代過(guò)程中，P11、P21 都能快速地將各自的優(yōu)化函數(shù)優(yōu)化至接近于0的值，并且在隨后的迭代過(guò)程中，依然能保持在0值附近進(jìn)行局部搜索開(kāi)發(fā)。但無(wú)論是P11 還是P21 均出現(xiàn)了分層的現(xiàn)象，出現(xiàn)此現(xiàn)象的原因在于P11、P21 共享同一個(gè)Pareto 前沿集，在對(duì)Pareto 前沿集更新后，會(huì)隨機(jī)地將角點(diǎn)更新為自身的值。例如：將f2較小但f1較大的值更新為P11；將f2較大但f1較小的值更新為P21。

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

雖然P11 和P21 優(yōu)化個(gè)體能各盡其職，并在各自負(fù)責(zé)的目標(biāo)函數(shù)上都能獲得很好的解，但在多目標(biāo)優(yōu)化問(wèn)題中，算法求解出的Pareto 前沿應(yīng)盡可能地均勻分布，即應(yīng)該均勻地鋪滿(mǎn)整個(gè)f2和f1區(qū)域。從圖1 中看出P11 與P21 優(yōu)化個(gè)體在求解過(guò)程中存在大部分空白區(qū)域，這表明F-YYPO在求解的分布性上還有提高的空間。

3.1.2 固定的縮放因子α

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

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

2020 年，文獻(xiàn)[10]對(duì)YYPO 中的縮放因子α的調(diào)整機(jī)制進(jìn)行了改進(jìn)，提出了線性與非線性三種自適應(yīng)變化情況的YYPO改進(jìn)算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的新算法相比于原YYPO算法，擁有更快的收斂速度與求解精度。因?yàn)镕-YYPO 繼承了YYPO 中的縮放因子α的調(diào)整機(jī)制，所以引入縮放因子α的自適應(yīng)調(diào)整機(jī)制以進(jìn)一步提高F-YYPO的性能。

3.1.3 存檔操作的局限性

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

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

3.2 F-ACYYPO詳述

針對(duì)F-YYPO 存在的3 個(gè)缺陷，本文提出了一種基于F-YYPO的改進(jìn)算法F-ACYYPO，即一種基于全組合策略的改進(jìn)多目標(biāo)陰陽(yáng)對(duì)優(yōu)化算法。

算法2 F-ACYYPO偽代碼

需要說(shuō)明的是，F(xiàn)-ACYYPO 雖然增加了優(yōu)化個(gè)體，但是并沒(méi)有增加目標(biāo)函數(shù)的維度，其依然是在M個(gè)優(yōu)化問(wèn)題下進(jìn)行優(yōu)化。以下將詳細(xì)介紹算法的優(yōu)化原理。

3.2.1 優(yōu)化個(gè)體與目標(biāo)問(wèn)題的組合

多目標(biāo)優(yōu)化問(wèn)題中目標(biāo)函數(shù)之間一般存在一定的相互影響，并非是完全相互獨(dú)立。F-ACYYPO算法不僅考慮單一的目標(biāo)適應(yīng)度值，也考慮其他目標(biāo)的適應(yīng)度值，從而體現(xiàn)出多目標(biāo)優(yōu)化問(wèn)題的整體性。以下以三目標(biāo)優(yōu)化問(wèn)題為例進(jìn)行介紹。

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

圖2 三目標(biāo)組合方式Fig.2 Combination of three objectives

以DTLZ2真實(shí)前沿舉例，圖3是個(gè)體負(fù)責(zé)優(yōu)化區(qū)域的大致示意圖。P1、P2、P3負(fù)責(zé)優(yōu)化圖中右三角、左三角、下三角標(biāo)志區(qū)域，可以看出，F(xiàn)YYPO 簡(jiǎn)單地優(yōu)化個(gè)體并沒(méi)有很好地對(duì)整個(gè)Pareto 前沿進(jìn)行搜索優(yōu)化。而F-ACYYPO 增加的P4、P5、P6、P7負(fù)責(zé)優(yōu)化圖中圓形、方形、菱形、實(shí)心點(diǎn)所示區(qū)域，可以看出，由于擇優(yōu)標(biāo)準(zhǔn)不同，F(xiàn)-ACYYPO增加的個(gè)體能更好地對(duì)整個(gè)前沿的個(gè)體進(jìn)行選擇。

圖3 全組合優(yōu)化個(gè)體示意圖Fig.3 Diagram of full-combination optimization

雖然優(yōu)化個(gè)體的選擇標(biāo)準(zhǔn)可以通過(guò)設(shè)置權(quán)重進(jìn)行一定調(diào)整，如w1×f1＋w2×f2＋w3×f3，但是在面對(duì)不同的多目標(biāo)優(yōu)化問(wèn)題時(shí)，無(wú)法知道權(quán)重的取值會(huì)有最優(yōu)的效果。因此為了算法對(duì)不同多目標(biāo)優(yōu)化問(wèn)題的通用性，將所有標(biāo)準(zhǔn)的權(quán)重默認(rèn)設(shè)置為1，這樣既能保持Pareto前沿的多樣性，又能使獲得的解均勻地分布在各個(gè)區(qū)間。

3.2.2 縮放因子α 的自適應(yīng)調(diào)整機(jī)制

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

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

引入的自適應(yīng)調(diào)整機(jī)制將直接替換掉原來(lái)的縮放因子α，消除搜索空間δ對(duì)縮放因子α的單一依賴(lài)。在每次進(jìn)行存檔操作的最后對(duì)搜索空間δ通過(guò)式（4）進(jìn)行更新。

圖4 是UF2 測(cè)試用例上優(yōu)化個(gè)體P11 搜索空間δ的變化圖。圖中展示了不同α參數(shù)與自適應(yīng)調(diào)整機(jī)制下的變化效果。

圖4 α 參數(shù)與自適應(yīng)效果圖Fig.4 α parameters and adaptive renderings

從圖4中可以看出，較大的參數(shù)α快速收縮搜索空間δ，在200次迭代之前就已經(jīng)收縮至0值附近，這樣雖然能使P11 有很好的局部開(kāi)發(fā)能力，但極易使尋優(yōu)過(guò)程陷入局部最優(yōu)。然而較小的α雖然能保持搜索空間δ緩慢變化，但到了算法結(jié)束時(shí)搜索空間δ依然保持一個(gè)較大的值，這明顯是降低了算法的收斂性。而自適應(yīng)調(diào)整機(jī)制能夠在前期很好地使搜索空間δ下降到0 值附近，在后期優(yōu)化個(gè)體的兩點(diǎn)進(jìn)行交換時(shí)也能保持快速地下降，使搜索空間δ保持較強(qiáng)的局部開(kāi)發(fā)能力。

3.2.3 改進(jìn)的存檔操作

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

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

為觀察新存檔方法的效果，本文將F-ACYYPO 在多目標(biāo)測(cè)試用例UF2 上并在相同的條件下進(jìn)行測(cè)試。使P11 優(yōu)化目標(biāo)函數(shù)f1的值，P21 優(yōu)化目標(biāo)函數(shù)f2的值，P31 優(yōu)化目標(biāo)函數(shù)f2＋f1的值。

從圖5中可以看出，在前200次迭代中，各優(yōu)化個(gè)體均能快速地將各自的優(yōu)化函數(shù)值優(yōu)化至一個(gè)較低的水平。并且在整個(gè)迭代過(guò)程中，各優(yōu)化個(gè)體都均勻地分布在各自的目標(biāo)函數(shù)值內(nèi)，在大部分迭代次數(shù)下P11 與P21 均能控制在真實(shí)Pareto 前沿(f2,f1∈[0,1])區(qū)域內(nèi)，同時(shí)新增的P31 優(yōu)化個(gè)體在整個(gè)迭代過(guò)程中，都表現(xiàn)出均勻的穩(wěn)定分布過(guò)程。

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

3.2.4 復(fù)雜度分析

本小節(jié)對(duì)算法的復(fù)雜度進(jìn)行漸進(jìn)分析表述。通過(guò)文獻(xiàn)[9-10]可知，單目標(biāo)優(yōu)化算法YYPO 的時(shí)間復(fù)雜度與優(yōu)化問(wèn)題的維度D相關(guān)，其最好情況與最壞情況的時(shí)間復(fù)雜度均為O(D2)。

F-YYPO 在YYPO 的基礎(chǔ)上引入了NSGA2 中的非支配快速排序與擁擠距離評(píng)估，快速非支配排序算法的時(shí)間復(fù)雜度為O(MN2)，擁擠距離評(píng)估的時(shí)間復(fù)雜度為O(N2)，其中M代表目標(biāo)個(gè)數(shù)，N代表種群大小。在F-YYPO中，因?yàn)槟繕?biāo)個(gè)數(shù)M與種群大小N是相等的，所以F-YYPO 中的非支配快速排序與擁擠距離評(píng)估的時(shí)間復(fù)雜度分別為O(M3)=O(N3)、O(M2)=O(N2)。因?yàn)镕-YYPO 為每個(gè)目標(biāo)個(gè)數(shù)分配一個(gè)優(yōu)化個(gè)體進(jìn)行優(yōu)化，所以F-YYPO算法的時(shí)間復(fù)雜度為O(MD2)。

F-ACYYPO 算法是F-YYPO 算法的改進(jìn)，從FACYYPO中的3個(gè)改進(jìn)措施來(lái)看，只有增加優(yōu)化個(gè)體這個(gè)操作會(huì)增加算法的復(fù)雜度。結(jié)合F-ACYYPO的偽代碼，其具體的時(shí)間復(fù)雜度為O((2M－1)D2)。

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

4 實(shí)驗(yàn)

為測(cè)試F-ACYYPO 算法的性能，本文采用了2009年IEEE進(jìn)化計(jì)算會(huì)議多目標(biāo)優(yōu)化算法性能評(píng)估特別會(huì)議（競(jìng)賽）中的6個(gè)雙目標(biāo)優(yōu)化測(cè)試實(shí)例進(jìn)行數(shù)值實(shí)驗(yàn)，并進(jìn)一步使用MATLAB 平臺(tái)下的PlatEMO 框架[34]的6個(gè)三目標(biāo)用例進(jìn)行數(shù)值實(shí)驗(yàn)。

4.1 CEC2009測(cè)試用例

CEC2009 包含一組無(wú)約束測(cè)試實(shí)例和一組一般約束測(cè)試實(shí)例，考慮到對(duì)測(cè)試用例的仿真圖排版等問(wèn)題，本文采用無(wú)約束測(cè)試實(shí)例中的6 個(gè)（UF2～UF7）進(jìn)行實(shí)驗(yàn)，剔除了相對(duì)簡(jiǎn)單的UF1測(cè)試用例。表1顯示了各測(cè)試用例的表達(dá)式、搜索空間及其最優(yōu)前沿。本文在實(shí)驗(yàn)中將原F-YYPO算法與改進(jìn)后的F-ACYYPO算法，以及經(jīng)典的具有代表性的多目標(biāo)優(yōu)化算法NSGA2、SPEA2、MOPSO、MOGWO 和gamultiobj 算法進(jìn)行評(píng)測(cè)，并比較分析各算法的優(yōu)化性能。

表1 UF測(cè)試套件Table 1 UF test suite

CEC2009對(duì)性能評(píng)估做了如下規(guī)定：

（1）每個(gè)問(wèn)題獨(dú)立運(yùn)行30次，每次限定最大函數(shù)評(píng)估次數(shù)為300 000次。

（2）每獨(dú)立運(yùn)行一次算法產(chǎn)生的非支配集中的最大個(gè)體數(shù)為：兩目標(biāo)為100個(gè)，三目標(biāo)為150個(gè)。

4.1.1 性能指標(biāo)

反轉(zhuǎn)世代距離（IGD）[35]：世代距離的逆向映射，是一個(gè)綜合性能評(píng)價(jià)指標(biāo)。它通過(guò)計(jì)算Pareto 最優(yōu)解集前沿面上的每個(gè)點(diǎn)到算法獲取的非支配解集之間的最小距離和，來(lái)評(píng)價(jià)算法的收斂性能和分布性能。具體計(jì)算公式如下：

設(shè)P*為沿PF（Pareto Front）的一組均勻分布點(diǎn)（在目標(biāo)空間中）。設(shè)A為PF的近似集，P*到A的平均距離定義為：

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

圖6 IGD指標(biāo)示意圖Fig.6 Schematic diagram of IGD

除IGD 指標(biāo)外，為綜合驗(yàn)證算法的有效性和收斂性，本文還引入了GD指標(biāo)與HV指標(biāo)。

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

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

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

圖7 GD指標(biāo)示意圖Fig.7 Schematic diagram of GD

超體積（HV）[37]：近年來(lái)廣泛運(yùn)用的一種綜合評(píng)價(jià)指標(biāo)。通過(guò)非支配解集與參考點(diǎn)圍成的空間的超體積的值來(lái)評(píng)價(jià)多目標(biāo)優(yōu)化算法的綜合性能，計(jì)算公式如下：

其中，λ代表勒貝格測(cè)度，vi代表參考點(diǎn)和非支配個(gè)體構(gòu)成的超體積，S代表非支配解集。計(jì)算原理如圖8所示。

圖8 HV指標(biāo)示意圖Fig.8 Schematic diagram of HV

4.1.2 參數(shù)設(shè)置與實(shí)驗(yàn)

參考文獻(xiàn)[8]中的實(shí)驗(yàn)設(shè)置，在實(shí)驗(yàn)中將F-YYPO的3 個(gè)主要參數(shù)分別設(shè)置為Imin=1,Imax=3，縮放因子α=20。

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

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

圖9 IGD指標(biāo)箱形圖Fig.9 Box-plot of IGD

表2 雙目標(biāo)IGDTable 2 Two-objective IGD

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

表3 雙目標(biāo)優(yōu)化GD Table 3 Two-objective GD

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

圖10 GD指標(biāo)箱形圖Fig.10 Box-plot of GD

與其他算法相比，F(xiàn)-ACYYPO 在UF5 測(cè)試用例上獲得了最優(yōu)的GD 值。而NSGA2 在4 個(gè)測(cè)試用例上（UF2～UF3、UF6～UF7）都取得了最優(yōu)的GD值。這意味著NSGA2 有更強(qiáng)的收斂性，除NSGA2 和SPEA2 之外，F(xiàn)-ACYYPO比其他算法（MOPSO、MOGWO、gamultiobj）能在大部分測(cè)試用例上獲得更優(yōu)和更穩(wěn)定的GD值。這表明F-ACYYPO依然擁有一定的競(jìng)爭(zhēng)性。為了進(jìn)一步說(shuō)明F-ACYYPO的收斂性，對(duì)各算法的GD值、F-ACYYPO與NSGA2的GD值分別進(jìn)行Friedman檢驗(yàn)分析，見(jiàn)表4。

表4 Friedman檢驗(yàn)Table 4 Friedman test

Friedman檢驗(yàn)是一種非參數(shù)雙向方差分析方法，目的在于檢測(cè)兩個(gè)或多個(gè)數(shù)據(jù)之間的顯著性差異[43]。在各算法的GD值指標(biāo)上，通過(guò)Friedman檢驗(yàn)獲得的漸進(jìn)顯著性p值為1.0×10－4，因?yàn)榈玫降膒值小于0.05，所以在GD 值上效果最好的NSGA2 與其他算法之間存在顯著性的差異。其次通過(guò)對(duì)F-ACYYPO 與NSGA2 的GD 值進(jìn)行Friedman 檢驗(yàn)，得到的漸進(jìn)顯著性p值為5.88×10－2，因?yàn)榈玫降膒值大于0.05，所以在NSGA2與F-ACYYPO的GD指標(biāo)上，兩者并不存在顯著性的差異。這說(shuō)明NSGA2 在收斂性GD 指標(biāo)上雖然獲得了各算法中最優(yōu)的效果，但是通過(guò)F-ACYYPO 與NSGA2 的Friedman 檢驗(yàn)可以知道，F(xiàn)-ACYYPO 與NSGA2 的GD值是很近似的，并沒(méi)有顯著性的差異。

表5是各算法在30次運(yùn)行后的平均HV值，其值越大代表綜合性能越好。從表中可以看出，在該性能指標(biāo)上，F(xiàn)-ACYYPO依然全面優(yōu)于F-YYPO。F-ACYYPO在6 個(gè)測(cè)試用例中的3 個(gè)測(cè)試用例上（UF2、UF5、UF7）達(dá)到了最優(yōu)值，而NSGA2 在2 個(gè)測(cè)試用例上達(dá)到了最優(yōu)值。這再一次證實(shí)了F-ACYYPO不僅全面優(yōu)于F-YYPO，而相比于其他算法，亦有很強(qiáng)的優(yōu)化性能。

圖11 是不同測(cè)試用例運(yùn)行各算法30 次后的關(guān)于HV 指標(biāo)的箱型圖。從圖中可以看出，F(xiàn)-ACYYPO 比F-YYPO有更好的分布。與其他算法相比，F(xiàn)-ACYYPO在大部分測(cè)試用例中的HV 值都是相對(duì)穩(wěn)定的。值得注意的是，在UF5 測(cè)試用例上，其他大部分算法的HV值接近于0，而F-ACYYPO 并沒(méi)有出現(xiàn)HV 值為0 的情況。這意味著F-ACYYPO使用的多組合優(yōu)化個(gè)體的改進(jìn)措施的確提高了Pareto前沿的分布效果。

圖11 HV指標(biāo)箱形圖Fig.11 Box-plot of HV

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

表5 雙目標(biāo)HVTable 5 Two-objective HV

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

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

4.2 PlatEMO平臺(tái)

PlatEMO[34]是一個(gè)供研究人員對(duì)現(xiàn)有多目標(biāo)優(yōu)化算法進(jìn)行基準(zhǔn)測(cè)試的開(kāi)源平臺(tái)，該平臺(tái)實(shí)現(xiàn)了較多的高性能多目標(biāo)優(yōu)化算法。為了進(jìn)一步測(cè)試新算法在三目標(biāo)問(wèn)題上的性能，進(jìn)一步使用PlatEMO上的三目標(biāo)測(cè)試用例，將F-ACYYPO和在該平臺(tái)上已經(jīng)實(shí)現(xiàn)的5個(gè)高性能多目標(biāo)算法NSGA2、GDE3、MOEAD、MOPSO、SPEA2在DTLZ測(cè)試套件（DTLZ2～DTLZ7）下進(jìn)行三目標(biāo)優(yōu)化問(wèn)題的數(shù)值實(shí)驗(yàn)和性能比較。每個(gè)測(cè)試用例獨(dú)立運(yùn)行10次。F-YYPO與F-ACYYPO的參數(shù)設(shè)置均與4.1.2小節(jié)相同。其他PlatEMO 平臺(tái)下的算法均使用默認(rèn)參數(shù)。表6、表7、表8 展示了在DTLZ 測(cè)試套件上的所有算法中獲得的IGD、GD、和HV指標(biāo)的測(cè)試值，限于篇幅原因，使用標(biāo)準(zhǔn)差來(lái)代替箱形圖表示獨(dú)立運(yùn)行后各項(xiàng)指標(biāo)的波動(dòng)性。

表6 三目標(biāo)IGDTable 6 Three-objective IGD

表7 三目標(biāo)GDTable 7 Three-objective GD

表8 三目標(biāo)HVTable 8 Three-objective HV

如表6所示，F(xiàn)-ACYYPO在所有測(cè)試用例上獲得了比F-YYPO 更好的IGD 值，并在4 個(gè)測(cè)試用例（DTLZ2、DTLZ3、DTLZ5、DTLZ7）上獲得了比其他算法更好的IGD 值。這意味著F-ACYYPO 所得到的解比其他算法更接近最優(yōu)Pareto前沿，并且有更好的分布性。從各測(cè)試用例的標(biāo)準(zhǔn)差可以看出，F(xiàn)-ACYYPO所得到的解集波動(dòng)性更小，也更具穩(wěn)定性。

如表7所示，F(xiàn)-ACYYPO在所有測(cè)試用例上依然獲得了比F-YYPO 更好的GD 值，并在3 個(gè)測(cè)試用例（DTLZ2、DTLZ3、DTLZ5）上獲得了比其他算法更好的GD值。這表明在三目標(biāo)優(yōu)化問(wèn)題上，F(xiàn)-ACYYPO 有較強(qiáng)的收斂性。

如表8所示，F(xiàn)-ACYYPO在大部分測(cè)試用例上獲得了比F-YYPO 更好的HV 值，并在DTLZ2、DTLZ5 兩個(gè)測(cè)試用例上獲得了比其他算法更大的HV 值。其中各算法在DTLZ3上的HV值均為0，這可能與DTLZ3優(yōu)化問(wèn)題自身有關(guān)，導(dǎo)致各算法都難以有較好的HV值。但在其他測(cè)試用例上各算法的HV值相差不大。

結(jié)合表6、表7、表8分析，F(xiàn)-ACYYPO在各項(xiàng)評(píng)價(jià)指標(biāo)中均優(yōu)于原F-YYPO 算法，并且與其他算法的對(duì)比中，在DTLZ2、DTLZ3、DTLZ5測(cè)試用例上，F(xiàn)-ACYYPO能在大多數(shù)測(cè)試用例中占據(jù)性能優(yōu)勢(shì)?？偟膩?lái)說(shuō)FACYYPO 在三目標(biāo)問(wèn)題上也有很好的表現(xiàn)。文獻(xiàn)[44]指出沒(méi)有一種算法能夠很好地解決每個(gè)優(yōu)化問(wèn)題，從而F-ACYYPO 算法對(duì)于求解多目標(biāo)優(yōu)化也有重要的研究意義。

圖13分別顯示了部分算法在各測(cè)試用例上得到的解與真實(shí)的Pareto前沿。因?yàn)椴糠炙惴ǖ腜areto前沿相差較大，所以圖13 只描繪出了F-ACYYPO、NSGA2、MOEAD 以及SPEA2 算法的Pareto 前沿。從圖中可以直觀地看出，與其他算法相比F-ACYYPO 在大部分的三目標(biāo)測(cè)試用例上，依然能保持較好的分布與收斂性。同時(shí)可從圖上看出，F(xiàn)-ACYYPO解的分布在雙目標(biāo)問(wèn)題上有著更優(yōu)的表現(xiàn)。

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

5 結(jié)束語(yǔ)

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