基于SOM聚類(lèi)和自適應(yīng)算子選擇的高維多目標(biāo)進(jìn)化算法

鐘沛龍，黎 明，何 超，陳 昊

（1.南昌航空大學(xué)信息工程學(xué)院，江西南昌 330063；2.南昌航空大學(xué)無(wú)損檢測(cè)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江西南昌 330063；3.南京航空航天大學(xué)自動(dòng)化學(xué)院，江蘇南京 211106）

1 引言

在實(shí)際生活中，多目標(biāo)優(yōu)化問(wèn)題存在于各類(lèi)現(xiàn)實(shí)場(chǎng)景中，往往存在多個(gè)彼此相互沖突的目標(biāo)，其中當(dāng)目標(biāo)個(gè)數(shù)為4 個(gè)及4 個(gè)以上時(shí)，多目標(biāo)優(yōu)化問(wèn)題又被稱(chēng)為高維多目標(biāo)優(yōu)化問(wèn)題（Many-Objective optimization Problems，MaOPs）［1］.為了有效地求解高維多目標(biāo)優(yōu)化問(wèn)題，現(xiàn)有的文獻(xiàn)采用了多種策略來(lái)增強(qiáng)高維多目標(biāo)進(jìn)化算法的性能［2～4］，例如引入新的指標(biāo)策略［5～7］、構(gòu)造新型支配關(guān)系［8～11］等.

現(xiàn)有方法主要將工作集中在如何去平衡算法的收斂性和多樣性，并保持向Pareto 前沿的選擇壓力.如NSGA-III［12］利用分解的思想來(lái)保持種群的多樣性，并且使用Pareto 支配加快種群的收斂速度；ε-MOEA［13］利用ε-支配和網(wǎng)格框架在環(huán)境選擇準(zhǔn)則中提出了收斂性和多樣性度量來(lái)保存精英個(gè)體進(jìn)入存檔；KnEA［14］，RVEA［15］和MOEA/DDU［16］等也是如此.然而上述算法并沒(méi)有考慮種群個(gè)體的數(shù)據(jù)結(jié)構(gòu)信息及個(gè)體間的相似性.盡管部分基于種群個(gè)體數(shù)據(jù)結(jié)構(gòu)信息的多目標(biāo)進(jìn)化算法被提出，但它們主要利用鄰域關(guān)系發(fā)掘多目標(biāo)優(yōu)化問(wèn)題的個(gè)體結(jié)構(gòu)，此外僅采用此類(lèi)結(jié)構(gòu)信息，并不能最有效地產(chǎn)生優(yōu)質(zhì)個(gè)體，具有一定的局限性.如基于多目標(biāo)優(yōu)化的細(xì)胞遺傳算法（Cell genetic algorithm based on Multi-Objective optimization，MOCell）［17］通過(guò)將每個(gè)個(gè)體置于一個(gè)網(wǎng)格結(jié)構(gòu)的元胞中來(lái)構(gòu)建個(gè)體之間的鄰域關(guān)系，其中每個(gè)個(gè)體僅同它的鄰域個(gè)體交互產(chǎn)生新個(gè)體，該方式對(duì)目標(biāo)空間的搜索能力有限；基于規(guī)則模型的多目標(biāo)分布估計(jì)算法（Regularity Model based Multi-objective Estimation of Distribution Algorithm，RMMEDA）［18］應(yīng)用主成分分析方法（Principal Component Analysis method，PCA）［19］將Pareto 集劃分為若干個(gè)不相交的類(lèi)，在每個(gè)類(lèi)中開(kāi)展主成分分析并建立概率模型，并在模型中抽樣產(chǎn)生新個(gè)體以更新種群，然而類(lèi)的數(shù)目K值難以設(shè)置，不同的K值，對(duì)算法性能的表現(xiàn)影響較大.

現(xiàn)有文獻(xiàn)顯示，利用相似個(gè)體作為父代進(jìn)行重組能夠顯著提高子代個(gè)體的質(zhì)量，并提高算法的搜索效率［20，21］.另外，聚類(lèi)算法是一類(lèi)將未知標(biāo)簽的數(shù)據(jù)對(duì)象集進(jìn)行分組的無(wú)監(jiān)督學(xué)習(xí)方法，其分類(lèi)的結(jié)果能夠保證同一類(lèi)的數(shù)據(jù)對(duì)象間的相似性較高，不同類(lèi)的數(shù)據(jù)對(duì)象間的相似性較低［22］.并且，聚類(lèi)算法僅利用數(shù)據(jù)本身的特征以及數(shù)據(jù)之間的相似性關(guān)系進(jìn)行分類(lèi).因此自組織映射網(wǎng)絡(luò)（Self-Organizing Map，SOM）模型能夠通過(guò)無(wú)監(jiān)督學(xué)習(xí)的方式對(duì)來(lái)自高維輸入空間的訓(xùn)練點(diǎn)產(chǎn)生低維的表征，并保持輸入數(shù)據(jù)間的近鄰關(guān)系，從而實(shí)現(xiàn)聚類(lèi)的目的.綜上所述，SOM模型能夠通過(guò)聚類(lèi)的方式保持種群個(gè)體原有的拓?fù)溥壿嬯P(guān)系，并可以自動(dòng)地根據(jù)個(gè)體的相似性構(gòu)建鄰域結(jié)構(gòu).因此本文提出了一種基于SOM 聚類(lèi)和自適應(yīng)算子選擇的方法（SOM Clustering and Adaptive Operator Selection，SCAOS）并將其作用于高維多目標(biāo)進(jìn)化算法中.與現(xiàn)有的基于數(shù)據(jù)結(jié)構(gòu)的方法不同，SCAOS 可以更好地利用種群個(gè)體的數(shù)據(jù)結(jié)構(gòu)信息及個(gè)體之間的相似性來(lái)增強(qiáng)高維多目標(biāo)進(jìn)化算法的性能.SCAOS 的主要貢獻(xiàn)在于：（1）采用SOM 聚類(lèi)算法提取數(shù)據(jù)結(jié)構(gòu)信息，獲得個(gè)體間相似性，將每個(gè)個(gè)體與相應(yīng)的神經(jīng)元相關(guān)聯(lián)，相似個(gè)體分配到相鄰神經(jīng)元；（2）在類(lèi)內(nèi)利用個(gè)體支配信息進(jìn)行自適應(yīng)算子選擇來(lái)產(chǎn)生優(yōu)質(zhì)子代引導(dǎo)個(gè)體重組，增強(qiáng)算法性能；（3）將提出的重組方法與環(huán)境選擇策略相結(jié)合，增強(qiáng)了種群個(gè)體的多樣性和收斂性.

2 相關(guān)工作

自組織映射網(wǎng)絡(luò)模型由Kohonen［23］提出，是一種無(wú)監(jiān)督學(xué)習(xí)的神經(jīng)元網(wǎng)絡(luò)模型，可以將輸入的n維空間數(shù)據(jù)映射到一個(gè)較低的維度輸出，并能夠保持?jǐn)?shù)據(jù)原有的拓?fù)溥壿嬯P(guān)系.SOM 這類(lèi)基于自組織映射的神經(jīng)網(wǎng)絡(luò)，已經(jīng)被廣泛應(yīng)用于數(shù)據(jù)聚類(lèi)［24］、圖像分割［25］、數(shù)據(jù)可視化［26］等實(shí)際應(yīng)用中.在處理多目標(biāo)優(yōu)化問(wèn)題方面，根據(jù)SOM 的使用方式不同，基于SOM 的多目標(biāo)進(jìn)化算法被分為兩類(lèi)：第一類(lèi)是直接應(yīng)用SOM 模型產(chǎn)生新解，第二類(lèi)是利用SOM引導(dǎo)算法的搜索.

在第一類(lèi)中，Hakimi-Asiabar 等［27］使用精英個(gè)體對(duì)SOM 模型進(jìn)行訓(xùn)練，然后將被訓(xùn)練后的SOM 輸出層神經(jīng)元的權(quán)值作為新產(chǎn)生的解，提高了產(chǎn)生優(yōu)質(zhì)新解的效率.Zhan 等［28］利用SOM 來(lái)學(xué)習(xí)多目標(biāo)優(yōu)化問(wèn)題Pareto解集的流型結(jié)構(gòu)，然后通過(guò)均勻隨機(jī)擾動(dòng)SOM的神經(jīng)元權(quán)值的方式來(lái)產(chǎn)生新個(gè)體以提高算法在目標(biāo)空間中的探索能力.在第二類(lèi)中，Norouzi等［29］使用NSGA-II先進(jìn)化一定代數(shù)以對(duì)目標(biāo)空間進(jìn)行初步勘探，然后利用SOM 將種群劃分到若干個(gè)子種群中，每個(gè)子種群獨(dú)立開(kāi)展遺傳操作并且進(jìn)化若干代，有效提高了算法的搜索性能.Gu等［30］提出了一種基于SOM 的權(quán)值向量設(shè)計(jì)方法，在基于分解的MOEA 的權(quán)值向量設(shè)計(jì)中利用SOM網(wǎng)絡(luò)來(lái)發(fā)現(xiàn)個(gè)體在目標(biāo)空間的分布.

以上研究表明，SOM 網(wǎng)絡(luò)模型不僅能夠通過(guò)提高產(chǎn)生個(gè)體的質(zhì)量來(lái)增強(qiáng)算法在處理多目標(biāo)優(yōu)化問(wèn)題時(shí)的性能，而且還可以通過(guò)引導(dǎo)算法搜索使優(yōu)質(zhì)的個(gè)體向著Pareto前沿移動(dòng)，進(jìn)而提高多目標(biāo)優(yōu)化算法的搜索效率.此外，利用SOM 進(jìn)行聚類(lèi)的方式較為簡(jiǎn)單，無(wú)需設(shè)置初始類(lèi)個(gè)數(shù)，對(duì)初始數(shù)據(jù)不太敏感.因此，基于SOM 的多目標(biāo)進(jìn)化算法能夠適用于各種復(fù)雜多目標(biāo)問(wèn)題的處理，具有較好的應(yīng)用前景.圖1 所示為典型的SOM拓?fù)浣Y(jié)構(gòu)，輸入層為n維空間，輸出層為二維空間，每個(gè)神經(jīng)元u上都有其對(duì)應(yīng)的權(quán)值向量神經(jīng)元權(quán)值的維數(shù)等于目標(biāo)個(gè)體的維數(shù).

圖1 典型的SOM拓?fù)浣Y(jié)構(gòu)

可以通過(guò)競(jìng)爭(zhēng)與合作的方式來(lái)對(duì)SOM 網(wǎng)絡(luò)進(jìn)行訓(xùn)練.

（1）競(jìng)爭(zhēng)：輸入個(gè)體X，根據(jù)個(gè)體X與神經(jīng)元的歐氏距離判斷獲勝神經(jīng)元，當(dāng)歐氏距離最小時(shí)，此神經(jīng)元即為獲勝神經(jīng)元，求解如下：

u′為當(dāng)前個(gè)體Xc的獲勝神經(jīng)元，其中，1≤c≤N.

（2）合作：在訓(xùn)練過(guò)程中，除了更新獲勝神經(jīng)元的權(quán)值，還要更新與獲勝神經(jīng)元鄰近神經(jīng)元的權(quán)值.表達(dá)式如下：

其中，U為獲勝神經(jīng)元u′的鄰近個(gè)體集合，σ為鄰域半徑，τ為當(dāng)前訓(xùn)練的學(xué)習(xí)率，u∈U.

3 基于SOM 聚類(lèi)和自適應(yīng)算子選擇的高維多目標(biāo)進(jìn)化算法

3.1 SOM聚類(lèi)

本文利用SOM 網(wǎng)絡(luò)特性來(lái)有效提取個(gè)體數(shù)據(jù)信息，獲得個(gè)體間相似性，并得到相似個(gè)體的集合.算法1為SOM聚類(lèi)算法的具體框架.

在算法1 中，Tmax和t分別表示最大迭代次數(shù)和當(dāng)前迭代次數(shù).SOM 聚類(lèi)算法先對(duì)網(wǎng)絡(luò)神經(jīng)元的權(quán)值向量W及神經(jīng)元鄰域半徑σ0進(jìn)行初始化操作（第1 行）.然后通過(guò)閾值δ限制學(xué)習(xí)率及鄰域半徑的更新策略來(lái)訓(xùn)練權(quán)值向量，其具體步驟為：首先學(xué)習(xí)率從τ0降低到δ，鄰域的大小從σ0降低到σ，持續(xù)優(yōu)化權(quán)值向量，使得輸出層能夠表示出輸入個(gè)體的分布情況；然后學(xué)習(xí)率τ0降低到δ后進(jìn)一步減小，而鄰域σ則保持不變，這種方式能夠自動(dòng)優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)，可以在一定程度上保持個(gè)體分布的多樣性（第5～10行）；再通過(guò)式（1）獲取當(dāng)前個(gè)體最接近的神經(jīng)元u′，由式（2）獲得鄰近神經(jīng)元集合U，式（3）更新鄰近神經(jīng)元的權(quán)值向量Wu（第11～16行）；最后將每個(gè)個(gè)體與神經(jīng)元關(guān)聯(lián)，相似個(gè)體將被分配到鄰近神經(jīng)元，得到相似個(gè)體集合Xu（第19～22行）.

3.2 自適應(yīng)算子選擇

在多目標(biāo)優(yōu)化過(guò)程中，相似個(gè)體之間重組，能夠提高產(chǎn)生新個(gè)體的質(zhì)量，增強(qiáng)算法的局部搜索能力［20］.本文依據(jù)此特點(diǎn)，設(shè)計(jì)一種自適應(yīng)算子選擇方式，充分利用相似個(gè)體數(shù)據(jù)信息產(chǎn)生高質(zhì)量的子代，引導(dǎo)算法在目標(biāo)空間中的搜索.其利用SOM網(wǎng)絡(luò)得到的相似個(gè)體集合，建立父代交配池，根據(jù)交配池內(nèi)個(gè)體支配信息選擇重組算子，產(chǎn)生優(yōu)質(zhì)子代.具體步驟如算法2所示.

在算法2中，首先根據(jù)相似個(gè)體集合Xu，獲得當(dāng)前個(gè)體交配池MP，大小設(shè)置為S（第2 行）；然后獲得當(dāng)前交配池內(nèi)個(gè)體支配信息（第3 行和第4 行）；最后根據(jù)個(gè)體支配信息選擇算子，若個(gè)體均互不支配，從交配池內(nèi)隨機(jī)選擇2 個(gè)作為父代個(gè)體進(jìn)行重組產(chǎn)生子代y，否則，從相似個(gè)體集合隨機(jī)選取2個(gè)不同于當(dāng)前個(gè)體的個(gè)體作為父代個(gè)體進(jìn)行重組產(chǎn)生子代y（第5～11行）.本文同時(shí)引入2種不同的重組算子，分別應(yīng)用在交配池內(nèi)和相似個(gè)體集合中產(chǎn)生子代，具體如算法3和算法4所示.

算法3為在交配池內(nèi)選擇父代個(gè)體進(jìn)行子代生成.首先在交配池內(nèi)選取2 個(gè)父代個(gè)體Xa，Xb；其次采用模擬二進(jìn)制交叉算子（Simulated Binary Crossover，SBX）［31］產(chǎn)生子代y′；然后為了防止新產(chǎn)生的子代y′超出個(gè)體的邊界值，對(duì)其進(jìn)行修正為y″；最后通過(guò)多項(xiàng)式變異操作［32］產(chǎn)生最終的子代y.

算法4 為在相似個(gè)體集合選擇父代個(gè)體進(jìn)行子代生成.首先在相似個(gè)體集合中隨機(jī)選擇2 個(gè)不同的個(gè)體Xa，Xb和當(dāng)前個(gè)體X作為父代個(gè)體；其次采用差分進(jìn)化交叉算子（Differential Evolution，DE）［33］產(chǎn)生子代y′；然后修正y′為y″；最后由多項(xiàng)式變異生成子代y.

值得注意的是，相較于比較所有個(gè)體，在交配池內(nèi)進(jìn)行比較可以有效減少計(jì)算復(fù)雜度并提取個(gè)體之間的相互信息，更加有利于優(yōu)質(zhì)個(gè)體的產(chǎn)生.此外，為了保持最終產(chǎn)生的子代個(gè)體數(shù)為N，在進(jìn)行SBX交叉算子操作時(shí)只產(chǎn)生1個(gè)子代.

3.3 MaOEA-SCAOS算法描述

MaOEA-SCAOS 如算法5 所述.首先初始化種群P、神經(jīng)元權(quán)值向量W和訓(xùn)練集TS；其次利用SOM 聚類(lèi)算法獲得相似個(gè)體集合Xu；然后通過(guò)集合Xu，構(gòu)建鄰域交配池，通過(guò)自適應(yīng)算子選擇操作重組生成優(yōu)質(zhì)子代；最后通過(guò)環(huán)境選擇策略選擇個(gè)體更新種群.值得注意的是本文環(huán)境選擇策略框架為NSGA-Ⅲ算法中環(huán)境選擇框架.NSGA-Ⅲ［12］是最著名的進(jìn)化多目標(biāo)優(yōu)化算法之一.它是在NSGA-Ⅱ［34］的基礎(chǔ)上進(jìn)一步提出的，該算法的基本算法框架和NSGA-Ⅱ算法相似，但是在選擇算子上進(jìn)行了改進(jìn)，它通過(guò)提供和自適應(yīng)更新一組預(yù)定義的參考點(diǎn)來(lái)維持種群個(gè)體間的多樣性.由于文章篇幅限制，NSGA-Ⅲ的環(huán)境選擇策略的詳細(xì)步驟見(jiàn)文獻(xiàn)［12］.另外在算法5 的第7行，TP 表示暫時(shí)保存訓(xùn)練好的個(gè)體，用于訓(xùn)練集TS的更新（第24 行），可以有效減少SOM 網(wǎng)絡(luò)的訓(xùn)練時(shí)間.

4 實(shí)驗(yàn)仿真與分析

為了驗(yàn)證本文算法（MaOEA-SCAOS）的有效性，選取2 種利用個(gè)體數(shù)據(jù)信息的多目標(biāo)進(jìn)化算法（MOCell［17］，RM-MEDA［18］）和3 種多目標(biāo)進(jìn)化算法（NSGA-Ⅲ［12］，MaOEA-CSS［35］，KnEA［14］）與本文所提算法進(jìn)行對(duì)比分析.所有的算法均是在多目標(biāo)進(jìn)化算法開(kāi)源平臺(tái)PlatEMO［36］上運(yùn)行.

4.1 測(cè)試問(wèn)題與性能指標(biāo)

在實(shí)驗(yàn)中，采用DTLZ 測(cè)試問(wèn)題集和WFG 測(cè)試問(wèn)題集.DTLZ 測(cè)試問(wèn)題集都有n=M+k-1 個(gè)決策變量，其中M為目標(biāo)維數(shù).根據(jù)文獻(xiàn)［37］中的決策變量設(shè)置建議，DTLZ1 中設(shè)置k=5，DTLZ2-DTLZ6 中設(shè)置k=10，DTLZ7 中設(shè)置k=20.WFG 測(cè)試問(wèn)題集中所有決策變量個(gè)數(shù)n=k+l，其中設(shè)置k=M-1，l=10.

為了驗(yàn)證MaOEA-SCAOS 獲得的近似Pareto 前沿的收斂性和多樣性，在實(shí)驗(yàn)研究中采用反世代距離（Inverted Generational Distance，IGD）和超體積指標(biāo)（Hyper-Volume，HV）.HV 指標(biāo)表示的是被種群中所有個(gè)體支配并且以參考點(diǎn)R為邊界的區(qū)域，其表達(dá)的是非支配個(gè)體覆蓋的目標(biāo)空間區(qū)域大小.給定參考點(diǎn)R，獲得的種群個(gè)體P*，那么關(guān)于參考點(diǎn)R的超體積定義為

其中，L為L(zhǎng)ebesgue 測(cè)度，|S|表示種群個(gè)體P*支配R的數(shù)目，vi表示參考點(diǎn)與種群中第i個(gè)個(gè)體構(gòu)成的超體積.從HV 定義可看出，HV 指標(biāo)的值越大，算法求得的種群質(zhì)量越高，算法性能優(yōu)化效果越佳.

IGD 指標(biāo)定義為每個(gè)參考點(diǎn)與其最近個(gè)體距離之和的平均值.其公式定義如下：

其中，dis(x，y)表示個(gè)體與參考點(diǎn)間的歐氏距離，由算法獲得的種群個(gè)體記為P*，P為真實(shí)的Pareto 前沿面均勻采樣得到的一組參考點(diǎn)，|P|為分布在真實(shí)Pareto 前沿面上種群P的規(guī)模.IGD的值越小表示所得種群個(gè)體越是靠近真實(shí)PF，個(gè)體分布越均勻.IGD 指標(biāo)既可以評(píng)價(jià)收斂性，也可以評(píng)價(jià)多樣性.

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

（1）種群大小N：本文采用文獻(xiàn)［12］中設(shè)置的方法.并且為了公平對(duì)比，其他算法的種群規(guī)模設(shè)置相同.所有算法種群大小設(shè)置如表1所示.

表1 種群大小設(shè)置

（2）終止條件：算法運(yùn)行一次的終止條件是最大評(píng)價(jià)次數(shù).最大評(píng)價(jià)次數(shù)等于種群規(guī)模乘以最大迭代次數(shù).本文在3目標(biāo)和5目標(biāo)的最大迭代次數(shù)設(shè)置為500，在8目標(biāo)和10目標(biāo)上設(shè)置為1 000.

我國(guó)爬升模板的研發(fā)晚于國(guó)外發(fā)達(dá)國(guó)家，80年代末，爬模施工技術(shù)應(yīng)用于橋梁及高層建設(shè)。至今爬模施工技術(shù)方法得到了明顯的提升。在很多橋梁高層建筑施工中應(yīng)用得到廣泛推廣。但對(duì)爬模的研發(fā)及施工工藝方面與國(guó)外發(fā)達(dá)國(guó)家相比仍存在很大差距。國(guó)內(nèi)爬模設(shè)備模塊化及規(guī)范化水平不高，需向國(guó)外先進(jìn)的爬模工藝技術(shù)學(xué)習(xí)。

（3）統(tǒng)計(jì)方法：所有算法在每個(gè)測(cè)試問(wèn)題上均獨(dú)立運(yùn)行20 次，對(duì)MaOEA-SCAOS 算法和其他對(duì)比算法獲得的結(jié)果采用Wilcoxon 秩和檢驗(yàn)方法進(jìn)行比較，其中均值分析的顯著性水平設(shè)置為5%.根據(jù)Wilcoxon 秩和檢驗(yàn)方法，其中“+”表示對(duì)比算法所得結(jié)果要優(yōu)于MaOEA-SCAOS，“-”表示對(duì)比算法所得結(jié)果要劣于MaOEA-SCAOS，“=”表示對(duì)比算法和MaOEA-SCAOS 獲得的結(jié)果沒(méi)有明顯的差異.

（4）對(duì)比算法主要參數(shù)設(shè)置：對(duì)于MOCell和NSGA-Ⅲ中DE 運(yùn)算符的控制參數(shù)F和CR 分別設(shè)置為0.3和0.2；在RM-MEDA 中，本地PCA 算法中的簇?cái)?shù)K設(shè)置為5；在MaOEA-CSS 中，環(huán)境選擇的閾值t大小設(shè)置為0；KnEA 的參數(shù)設(shè)置參照文獻(xiàn)［14］；本文算法MaOEASCAOS中初始SOM 學(xué)習(xí)率τ0、交配池大小MP和學(xué)習(xí)率下降閾值δ分別設(shè)置為0.9，5和0.1.

（5）交叉和變異算子設(shè)置：在MaOEA-SCAOS 算法中SBX 分布因子η設(shè)置為20，DE控制參數(shù)F和CR分別設(shè)置為0.5和1.多項(xiàng)式變異的變異分布因子ξ均設(shè)置為20，變異概率ρ均為1（n代表決策變量數(shù)目）.

4.3 參數(shù)分析

以DTLZ1～DTLZ7 測(cè)試問(wèn)題作為目標(biāo)函數(shù)進(jìn)行分析，使用不同參數(shù)的MaOEA-SCAOS 對(duì)每種測(cè)試問(wèn)題運(yùn)用IGD 性能指標(biāo)值隨性能評(píng)價(jià)次數(shù)的變化進(jìn)行分析，其中詳細(xì)分析了交配池大小MP和閾值δ.

4.3.1 交配池大小MP分析

為了客觀評(píng)價(jià)交配池大小對(duì)算法的影響，本文選取3，5，10，15和20 五種不同大小的交配池，并設(shè)置相同的其他參數(shù)來(lái)驗(yàn)證交配池對(duì)算法的影響.圖2 顯示了MaOEA-SCAOS 在DTLZ1，DTLZ3，DTLZ6和DTLZ7測(cè)試問(wèn)題上獨(dú)立運(yùn)行20次后的平均IGD 指標(biāo)值隨著評(píng)價(jià)次數(shù)的變化曲線.從圖2 可以看出，不同的MP 在不同測(cè)試問(wèn)題上有著不同的性能，其中較大的MP所得算法性能較低，較小的MP 所得算法性能較優(yōu)，故較小的交配池適合MaOEA-SCAOS 算法.可以看出，當(dāng)MP=5時(shí)，MaOEA-SCAOS 所呈現(xiàn)的收斂性能較好，故本文所設(shè)置交配池大小為5.

圖2 不同交配池大小在DTLZ測(cè)試問(wèn)題獨(dú)立運(yùn)行20次平均IGD指標(biāo)值

4.3.2 閾值δ分析

不同閾值δ，決定了鄰域的多樣性分布情況，最終會(huì)影響算法的收斂性.為了獲取最佳閾值參數(shù)，選取閾值大小為0.1，0.3，0.5，0.7來(lái)進(jìn)行驗(yàn)證，其他參數(shù)設(shè)置相同.圖3 顯示了MaOEA-SCAOS 在DTLZ1，DTLZ3，DTLZ6和DTLZ7測(cè)試問(wèn)題上獨(dú)立運(yùn)行20次后的平均IGD指標(biāo)值隨著評(píng)價(jià)次數(shù)的變化曲線.由圖3可以看出，較小的閾值得到算法的收斂性較優(yōu)，故本文設(shè)置閾值δ大小為0.1.

圖3 不同閾值大小在DTLZ 測(cè)試問(wèn)題獨(dú)立運(yùn)行20 次平均IGD 指標(biāo)值

4.4 計(jì)算復(fù)雜度分析

本小節(jié)分析MaOEA-SCAOS 算法在一代內(nèi)的最壞情況總體計(jì)算復(fù)雜度.在SOM 聚類(lèi)階段，首先訓(xùn)練階段通過(guò)個(gè)體尋找最近神經(jīng)元對(duì)其權(quán)值向量進(jìn)行更新；其次聚類(lèi)操作將每一個(gè)個(gè)體與最近神經(jīng)元相匹配，將相似個(gè)體分配到鄰近神經(jīng)元，因此該過(guò)程的計(jì)算復(fù)雜度為O(N2)，其中N為種群個(gè)體數(shù)量.在自適應(yīng)算子選擇階段，首先考慮交配選擇，對(duì)于一個(gè)個(gè)體規(guī)模為N和M目標(biāo)的優(yōu)化問(wèn)題，構(gòu)建交配池大小MP 需要O(MN·MP)；其次交叉變異對(duì)父代個(gè)體的每個(gè)決策變量，產(chǎn)生N個(gè)后代需要O(DN)的運(yùn)行時(shí)間，其中，D為決策變量的個(gè)數(shù).在環(huán)境選擇階段，在最壞的情況下需要O(MN2)的運(yùn)行時(shí)間.其他操作的復(fù)雜度較小.因此，MaOEA-SCAOS 在一代內(nèi)的最壞情況總體計(jì)算復(fù)雜度為O(MN2).MaOEA-SCAOS算法在計(jì)算上非常高效.

4.5 算法在WFG問(wèn)題上對(duì)比分析

表2和表3 分別給出了6 個(gè)算法在WFG1-WFG9 測(cè)試問(wèn)題上進(jìn)行20 次獨(dú)立計(jì)算HV和IGD 指標(biāo)的實(shí)驗(yàn)結(jié)果，其中表2 匯總了對(duì)比算法所獲得HV 值的均值和標(biāo)準(zhǔn)差（括號(hào)內(nèi)為標(biāo)準(zhǔn)差），表3 匯總了對(duì)比算法所獲得IGD值的均值和標(biāo)準(zhǔn)差（括號(hào)內(nèi)為標(biāo)準(zhǔn)差），其中用黑色粗體突出最好的結(jié)果.

表2 6種算法在WFG1～WFG9測(cè)試問(wèn)題上獲得的HV指標(biāo)值的實(shí)驗(yàn)結(jié)果

表3 6種算法在WFG1～WFG9測(cè)試問(wèn)題上獲得的IGD指標(biāo)值的實(shí)驗(yàn)結(jié)果

續(xù)表

續(xù)表

綜合HV和IGD 指標(biāo)的統(tǒng)計(jì)數(shù)據(jù)分析結(jié)果，對(duì)算法在WFG問(wèn)題上的性能進(jìn)行對(duì)比分析.WFG1具有復(fù)雜的Pareto 前沿，MaOEA-SCAOS 在3和8 目標(biāo)問(wèn)題上的IGD指標(biāo)相較其他對(duì)比方法具有較好的競(jìng)爭(zhēng)力.WFG2具有凸面不連續(xù)且多模態(tài)的Pareto 前沿，MaOEA-SCAOS 的HV指標(biāo)值在3和5目標(biāo)上獲得最優(yōu)性能，具有較好的魯棒性.WFG3 具有線性退化的Pareto 前沿，MaOEASCAOS 算法的HV 指標(biāo)結(jié)果在8 目標(biāo)取得最優(yōu)，并且在IGD指標(biāo)上也具有一定優(yōu)勢(shì).WFG4～WFG9在決策變量空間中的設(shè)計(jì)存在不同的困難，其中WFG4具有凹型和多模態(tài)的Pareto 前沿，WFG5加入欺騙性特征，WFG6具有不可分離且縮放的Pareto 前沿，WFG7 具有參數(shù)依賴(lài)性的可分離單峰，WFG8 在WFG7 基礎(chǔ)上增加了不可分特性，WFG9具有以上測(cè)試問(wèn)題特征，因此WFG4～WFG9測(cè)試問(wèn)題在多目標(biāo)進(jìn)化算法極具挑戰(zhàn)性.對(duì)于WFG4和WFG5測(cè)試問(wèn)題，MaOEA-SCAOS在HV指標(biāo)上均獲得最優(yōu)性能，這表明對(duì)于具有凹面的多目標(biāo)優(yōu)化問(wèn)題，本文方法具有較好的可靠性.圖4展示了各個(gè)算法獲得的非支配解在WFG4 上3 目標(biāo)實(shí)例中的分布情況，其中MaOEA-SCAOS算法獲得的非支配解集較好地平衡了收斂性和多樣性.對(duì)于WFG6測(cè)試問(wèn)題，MaOEA-SCAOS大體上優(yōu)于其他算法，僅在5 目標(biāo)問(wèn)題上性能略差于NSGA-Ⅲ算法，由圖5可以看到，各個(gè)算法獲得的非支配解在WFG6 上8 目標(biāo)實(shí)例中的分布情況，可以看出MaOEA-SCAOS獲得的非支配解優(yōu)于其他對(duì)比算法.對(duì)于WFG7和WFG8 測(cè)試問(wèn)題，MaOEA-SCAOS 在處理3，5，8和10 目標(biāo)時(shí)性能表現(xiàn)突出，說(shuō)明在WFG7和WFG8測(cè)試問(wèn)題上處理不同目標(biāo)數(shù)目的普適性較好.此外，在WFG9 問(wèn)題的測(cè)試中，本文算法也表現(xiàn)出一定的競(jìng)爭(zhēng)力.綜上所述，可以看出MaOEA-SCAOS在WFG測(cè)試問(wèn)題集上性能顯著且在處理不同目標(biāo)優(yōu)化問(wèn)題時(shí)普適性較高.

圖4 WFG4問(wèn)題3目標(biāo)上獲得的非支配解

圖5 WFG6問(wèn)題8目標(biāo)上獲得的非支配解

4.6 算法在DTLZ問(wèn)題上對(duì)比分析

表4和表5 分別給出了6 個(gè)算法在DTLZ1～DTLZ7測(cè)試問(wèn)題上進(jìn)行20 次獨(dú)立計(jì)算HV和IGD 指標(biāo)的實(shí)驗(yàn)結(jié)果，其中，表4 匯總了對(duì)比算法所獲得HV 值的均值和標(biāo)準(zhǔn)差（括號(hào)內(nèi)為標(biāo)準(zhǔn)差），表5 匯總了對(duì)比算法所獲得IGD 值的均值和標(biāo)準(zhǔn)差（括號(hào)內(nèi)為標(biāo)準(zhǔn)差），其中用黑色粗體突出最好的結(jié)果.

表4 6種算法在DTLZ1～DTLZ7測(cè)試問(wèn)題上獲得的HV指標(biāo)值的實(shí)驗(yàn)結(jié)果

表5 6種算法在DTLZ1～DTLZ7測(cè)試問(wèn)題上獲得的IGD指標(biāo)值的實(shí)驗(yàn)結(jié)果

續(xù)表

續(xù)表

綜合HV和IGD 指標(biāo)的統(tǒng)計(jì)數(shù)據(jù)對(duì)算法在DTLZ問(wèn)題上的實(shí)驗(yàn)結(jié)果進(jìn)行分析.由表4 可以看出，在具有規(guī)則形狀的Pareto 前沿的DTLZ1～DTLZ4 測(cè)試問(wèn)題上，MaOEA-SCAOS在HV性能指標(biāo)均獲得較優(yōu)的性能，這表明算法對(duì)具有規(guī)則的Pareto前沿面的優(yōu)化問(wèn)題具有較好的可靠性.圖6 展示了各個(gè)算法獲得的非支配解在DTLZ4上10目標(biāo)實(shí)例中的分布情況，MaOEA-SCAOS算法的搜索能力并沒(méi)有受到目標(biāo)個(gè)數(shù)增加的影響，依然表現(xiàn)出較強(qiáng)的性能.值得注意的是，在具有凹且退化特征的DTLZ5和DTLZ6 上，MaOEA-SCAOS 能夠獲得與NSGA-Ⅲ算法相似的性能，并且其在DTLZ5 測(cè)試問(wèn)題8目標(biāo)和10目標(biāo)上的指標(biāo)優(yōu)于NSGA-III.這說(shuō)明MaOEASCAOS相較NSGA-III更適合處理具有退化Pareto前沿的高維問(wèn)題.對(duì)于具有混合特征Pareto前沿的DTLZ7測(cè)試問(wèn)題，算法MaOEA-SCAOS 較難處理的主要原因在于沒(méi)有采用自適應(yīng)特征點(diǎn)的環(huán)境選擇策略.綜上可以看出，MaOEA-SCAOS在DTLZ測(cè)試問(wèn)題集中具有規(guī)則形狀PF的目標(biāo)問(wèn)題上具有良好的可靠性，能夠保持種群的收斂性和多樣性；在不規(guī)則的PF上不同目標(biāo)維數(shù)中仍然能夠保持算法的魯棒性，能夠較好地處理不同形狀Pareto前沿的問(wèn)題.

圖6 DTLZ4問(wèn)題10目標(biāo)上獲得的非支配解

5 總結(jié)

針對(duì)在多目標(biāo)優(yōu)化問(wèn)題中高維多目標(biāo)優(yōu)化算法的搜索效率及收斂效率降低，無(wú)法產(chǎn)生高質(zhì)量的子代個(gè)體去引導(dǎo)種群搜索的問(wèn)題，本文提出一種基于SOM 聚類(lèi)和自適應(yīng)算子選擇的方法作用于高維多目標(biāo)進(jìn)化算法.該方法首先利用SOM 網(wǎng)絡(luò)特性，訓(xùn)練提取種群個(gè)體結(jié)構(gòu)信息，獲得相似個(gè)體集合，構(gòu)建鄰域交配池；然后通過(guò)交配池內(nèi)支配信息進(jìn)行自適應(yīng)算子選擇，重組產(chǎn)生優(yōu)質(zhì)子代引導(dǎo)種群搜索；最后，引入NSGA-Ⅲ算法中環(huán)境策略，更新種群，以提高種群的多樣性和收斂性.與現(xiàn)有的高維多目標(biāo)優(yōu)化算法進(jìn)行實(shí)驗(yàn)對(duì)比，結(jié)果表明，本文所提出的個(gè)體重組方式的有效性?xún)?yōu)于同樣利用個(gè)體結(jié)構(gòu)信息的其他多目標(biāo)優(yōu)化算法.此外，與現(xiàn)有的其他算法相比，本文算法在所有基準(zhǔn)測(cè)試函數(shù)中均具有較強(qiáng)的競(jìng)爭(zhēng)力.