基于自變量簡約的大規(guī)模稀疏多目標(biāo)優(yōu)化

摘 要：現(xiàn)有的大多數(shù)進(jìn)化算法在求解大規(guī)模優(yōu)化問題時(shí)性能會隨決策變量維數(shù)的增長而下降。通常，多目標(biāo)優(yōu)化的Pareto有效解集是自變量空間的一個(gè)低維流形，該流形的維度遠(yuǎn)小于自變量空間的維度。鑒于此，提出一種基于自變量簡約的多目標(biāo)進(jìn)化算法求解大規(guī)模稀疏多目標(biāo)優(yōu)化問題。該算法通過引入局部保持投影降維，保留原始自變量空間中的局部近鄰關(guān)系，并設(shè)計(jì)一個(gè)歸檔集，將尋找到的非劣解存入其中進(jìn)行訓(xùn)練，以提高投影的準(zhǔn)確性。將該算法與四種流行的多目標(biāo)進(jìn)化算法在一系列測試問題和實(shí)際應(yīng)用問題上進(jìn)行了比較。實(shí)驗(yàn)結(jié)果表明，所提算法在解決稀疏多目標(biāo)問題上具有較好的效果。因此，通過自變量簡約能降低問題的求解難度，提高算法的搜索效率，在解決大規(guī)模稀疏多目標(biāo)問題方面具有顯著的優(yōu)勢。

關(guān)鍵詞：局部保持投影；進(jìn)化算法；大規(guī)模稀疏多目標(biāo)優(yōu)化問題

中圖分類號：TP18 文獻(xiàn)標(biāo)志碼：A文章編號：1001-3695（2024）06-009-1663-06

doi： 10.19734/j.issn.1001-3695.2023.10.0522

Evolutionary algorithm using dimensionality reduction for sparse multi-objective optimization

Abstract： The performance of most existing evolutionary algorithms tends to decrease as the dimension of the decision variables increases for solving large-scale optimization problems. The Pareto solution set of a multi-objective optimization is a low dimensional manifold in the decision space， whose dimension is much smaller than that of the decision variables space. Accordingly， this paper proposed a multi-objective evolutionary algorithm based on dimensionality reduction of decision variables to solve large-scale sparse multi-objective optimization problems. It preserved local neighborhood information in the original decision variables space by using locality preserving projections， and designed an archive set to train the non-dominated solutions as much as possible to raise the accuracy of projection. The proposed algorithm was compared with four popular evolutionary multi-objective optimization algorithms on a series of test problems and practical application problems. Experimental results show that the proposed algorithm is effective in solving sparse multi-objective problems. Therefore， the reduction of indepen-dent variables can reduce the difficulty of solving the problem， improve the search efficiency of the algorithm， and have significant advantages in solving large-scale sparse multi-objective problems.

Key words：locality preserving projection; multi-objective evolutionary algorithm; large-scale sparse multi-objective optimization problems

0 引言

多目標(biāo)優(yōu)化一直是進(jìn)化計(jì)算研究中一個(gè)有挑戰(zhàn)性的領(lǐng)域。多目標(biāo)優(yōu)化問題（multi-objective optimization problem，MOP） 不同于單目標(biāo)優(yōu)化問題，它沒有唯一的最優(yōu)解，MOP的最優(yōu)解通常是一組非劣解［1］。多目標(biāo)優(yōu)化進(jìn)化算法（multi-objective optimization evolutionary algorithm，MOEA） 在求解MOP時(shí)可以通過種群的不斷進(jìn)化迭代，找到一組類似于Pareto前沿界面的最優(yōu)解［2］。與傳統(tǒng)的優(yōu)化方法相比，MOEA在求解多目標(biāo)優(yōu)化問題時(shí)具有更好的效果，已成為求解MOP最有效的工具之一［3，4］。目前，MOEA已被證明能夠很好地解決一些測試問題，并在實(shí)際問題中得到了很好的應(yīng)用［5］。近年來，人們提出了許多經(jīng)典的多目標(biāo)進(jìn)化算法。根據(jù)選擇策略的不同，MOEA大致可分為基于支配關(guān)系的MOEA、基于指標(biāo)評價(jià)的MOEA和基于分解的MOEA三類。基于支配關(guān)系的MOEA利用Pareto支配關(guān)系促進(jìn)種群向Pareto前沿的進(jìn)化，典型代表有NSGA-Ⅱ［6］、SPEA2［7］和PESA［8］。基于指標(biāo)評價(jià)的MOEA通常采用HV等性能指標(biāo)來評價(jià)解的收斂性和多樣性［9，10］。基于分解的MOEA算法利用數(shù)學(xué)規(guī)劃將復(fù)雜的MOP轉(zhuǎn)換為一系列簡單的單目標(biāo)優(yōu)化子問題進(jìn)行求解［11］。

隨著問題維度的增加，當(dāng)輸入決策變量超過100維時(shí)，這類優(yōu)化問題被定義為大規(guī)模優(yōu)化問題［12］。隨著大規(guī)模多目標(biāo)優(yōu)化問題的出現(xiàn)，近年來也提出了多種求解大規(guī)模優(yōu)化問題的方法。目前，大規(guī)模優(yōu)化問題的求解方法主要有協(xié)同進(jìn)化策略和非協(xié)同進(jìn)化策略兩種。其中協(xié)同進(jìn)化策略采取的是分治思想，它把原始的大規(guī)模問題分解為多個(gè)低維度的子問題，每個(gè)子問題單獨(dú)進(jìn)化，將復(fù)雜的問題簡單化，只有在迭代過程中交換信息，合作產(chǎn)生適應(yīng)度值［13］。例如，Peng等人［14］提出的基于ε約束的協(xié)同進(jìn)化粒子群算法求解大規(guī)模優(yōu)化問題、Aguilar-Justo等人［15］設(shè)計(jì)的一種大規(guī)模優(yōu)化問題的局部合作搜索策略等。另一種非協(xié)同進(jìn)化策略則是運(yùn)用一些特殊的策略或聯(lián)合其他有效的算法，如群體智能優(yōu)化算法來改進(jìn)，將大規(guī)模優(yōu)化問題當(dāng)作整體進(jìn)行求解［16］。陳暄等人［17］提出了一種改進(jìn)的狼群算法，利用深度神經(jīng)網(wǎng)絡(luò)求解大規(guī)模優(yōu)化問題。Wang等人［18］通過改進(jìn)粒子群算法，在進(jìn)化的不同階段采用不同的學(xué)習(xí)策略，以提高算法的搜索能力。Tian等人［19］提出了一種求解具有稀疏Pareto最優(yōu)解的大規(guī)模多模態(tài)多目標(biāo)優(yōu)化問題的進(jìn)化算法。

所謂降維，就是將高維數(shù)據(jù)映射到低維空間，然后對得到的低維數(shù)據(jù)進(jìn)行處理，在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘中得到了廣泛的應(yīng)用。因此，自變量降維也叫自變量簡約，有望成為求解大規(guī)模優(yōu)化問題的有利工具，從而有效避免維數(shù)災(zāi)難問題。通過簡約，將高維自變量壓縮映射到低維空間中，并盡可能保留數(shù)據(jù)的有效信息［20］。通常，根據(jù)映射關(guān)系是否為線性，簡約技術(shù)可以細(xì)分為線性方法和非線性方法［21］。主成分分析（principal component analysis，PCA）是一種流行的線性降維方法，它通過線性投影，將高維數(shù)據(jù)嵌入低維線性空間，并通過最大化低維空間數(shù)據(jù)的方差來盡可能多地保留原始數(shù)據(jù)信息［22］。線性判別分析利用最大化類間距離與最小化類內(nèi)距離的思想來提取判別信息，尋找最優(yōu)的投影矩陣（linear discriminant analysis，LDA）［23］。線性降維方法不能有效地處理高維復(fù)雜非線性數(shù)據(jù)，為了處理非線性數(shù)據(jù)，出現(xiàn)了一些非線性方法。其中等距離映射（isometric feature mapping，Isomap）和局部線性嵌入（locally linear embedding，LLE）是目前為止最具有代表性的兩種非線性降維方法。局部線性嵌入假設(shè)高維數(shù)據(jù)點(diǎn)可以被其鄰居線性逼近，并在此假設(shè)的基礎(chǔ)上保留數(shù)據(jù)的非線性流形結(jié)構(gòu)［24］。等距映射引入了測地距離的概念，通過最小化高維空間中的成對測地距離矩陣和低維空間中的成對歐氏距離矩陣之間的距離來得到低維嵌入結(jié)果［25］。一般線性降維方法只保留了學(xué)習(xí)投影子空間中的全局線性結(jié)構(gòu)，導(dǎo)致分類性能較差。局域保持投影（locality preserving projections，LPP）作為一種線性降維技術(shù)，不僅擁有線性降維方法的速度，還利用線性投影映射來保持?jǐn)?shù)據(jù)的局部鄰域結(jié)構(gòu)，并且LPP具有許多非線性技術(shù)的數(shù)據(jù)表示特征［26］。此外，LPP算法的局域保持特性使其對異常值和噪聲相對不敏感。

隨著決策變量的增加，現(xiàn)有算法依舊不能很好地解決大規(guī)模多目標(biāo)優(yōu)化問題，且隨著問題維數(shù)的增加，問題愈加復(fù)雜，同時(shí)解在決策空間中的分布也變得稀疏，使得算法的搜索效率顯著下降［27，28］。事實(shí)上，維度災(zāi)難是大規(guī)模優(yōu)化問題求解困難的根本原因，優(yōu)化問題的求解難度與自變量的維度息息相關(guān)。因此，如何提高算法的可擴(kuò)展性，以應(yīng)對復(fù)雜大規(guī)模優(yōu)化問題，以及如何有效解決稀疏的大規(guī)模多目標(biāo)優(yōu)化問題，是當(dāng)前進(jìn)化算法急需面對的重要問題。

為了保證在大規(guī)模多目標(biāo)優(yōu)化問題下算法的搜索效率和準(zhǔn)確率，以及針對稀疏解在決策空間中的分布問題，本文提出一種基于自變量簡約的稀疏多目標(biāo)進(jìn)化算法（sparse multi-objective decision variable dimensionality reduction，SMDVDR）。該算法將MOEA和局部保持投影的降維技術(shù)相結(jié)合，使其不僅擁有進(jìn)化算法的自我學(xué)習(xí)能力，保證了算法的搜索效率，還擁有LPP降維技術(shù)的優(yōu)勢，即在降維的時(shí)候不受到異常值和數(shù)據(jù)噪聲的影響，能使得數(shù)據(jù)最大化地精減且明顯提升數(shù)據(jù)準(zhǔn)確率。該算法在迭代的過程中加入了一種采用非支配排序調(diào)整內(nèi)部個(gè)體的歸檔集，其目的是在目標(biāo)子代中尋找非劣解存入歸檔集進(jìn)行訓(xùn)練，在考慮當(dāng)前最優(yōu)解的同時(shí)考慮其他非劣解，并使用歸檔集訓(xùn)練轉(zhuǎn)換向量。該歸檔集能夠進(jìn)行動態(tài)調(diào)整，在面對大樣本時(shí)考慮非劣解以提升結(jié)果的準(zhǔn)確性；在面對小樣本時(shí)，也能通過這種方法擴(kuò)充樣本進(jìn)行訓(xùn)練，使得算法在小樣本的情況下也能求得問題更真實(shí)的Pareto前沿。與此同時(shí)，用局部保持投影進(jìn)行降維得到低維空間，并在低維空間上進(jìn)行交叉變異操作獲得子代，以提高算法的效率和可延展性，將來自每一代子代的非劣解存入歸檔集，并設(shè)置歸檔集的個(gè)數(shù)上限，在歸檔集達(dá)到上限的時(shí)候使用非支配排序調(diào)整歸檔集，最終得到代表原問題的近似Pareto前沿。實(shí)驗(yàn)選取稀疏多目標(biāo)問題進(jìn)行測試，并選取實(shí)際應(yīng)用問題對比，驗(yàn)證了該方法的有效性。

1 研究現(xiàn)狀

1.1 大規(guī)模多目標(biāo)優(yōu)化問題

現(xiàn)實(shí)中的許多優(yōu)化問題都包含幾個(gè)相互沖突的目標(biāo)，本文稱這類問題為多目標(biāo)優(yōu)化問題，其定義如下：

兩個(gè)解x和y之間的支配關(guān)系可以定義為

如果滿足上述條件，則x支配y，表示為xy。不受其他決策向量支配的向量x稱為帕累托最優(yōu)解。決策空間中的Pareto最優(yōu)解集稱為Pareto集合（Pareto set，PS），對應(yīng)的目標(biāo)向量集稱為Pareto前沿（Pareto front，PF）［28］。

一般來說，多目標(biāo)優(yōu)化算法不能得到?jīng)Q策空間中所有的Pareto最優(yōu)解和Pareto前沿的所有目標(biāo)向量。因此，多目標(biāo)優(yōu)化的目標(biāo)在于兩個(gè)方面：a）得到的目標(biāo)向量要盡可能接近真實(shí)的目標(biāo)向量；b）得到的目標(biāo)向量應(yīng)盡可能分散地分布在目標(biāo)向量上。

1.2 局部保持投影

LPP構(gòu)造鄰接圖的方式有兩種：a）使用ε鄰接，任意取兩個(gè)節(jié)點(diǎn)i和j，這兩個(gè)節(jié)點(diǎn)之間的歐氏距離小于等于ε，就認(rèn)定滿足條件，但是這種方式ε的取值難以把握；b）直接計(jì)算節(jié)點(diǎn)i和j之外的所有點(diǎn)的歐氏距離并進(jìn)行排序，找到距離最近的k個(gè)點(diǎn)。

選擇權(quán)重的方式也有兩種，分別是使用熱核函數(shù)和簡單的無參數(shù)近鄰選擇方法，其中熱核函數(shù)的選擇權(quán)重方法也受到參數(shù)的影響。

在計(jì)算投影矩陣的方式上，LPP采用的是廣義特征值分解的方法計(jì)算廣義特征向量問題的特征向量和特征值。

2 SMDVDR算法

2.1 基于局部保持投影的降維算法設(shè)計(jì)

結(jié)合稀疏多目標(biāo)問題的特征，本文在原有的局域保持投影算法上進(jìn)行改進(jìn)，使用特征值分解的方法代替原本的廣義特征值分解方法，得到最小特征值和特征向量。本文算法的降維具體步驟如下：

a）設(shè)G表示為具有m節(jié)點(diǎn)的鄰接圖。使用K近鄰來確定兩個(gè)數(shù)據(jù)點(diǎn)是否相鄰。如果點(diǎn)xi和xj是相鄰點(diǎn)，則節(jié)點(diǎn)i和j通過邊連接，構(gòu)成一個(gè)鄰接圖。

b）如果節(jié)點(diǎn)i和j之間存在邊連接，則使用式（3）對節(jié)點(diǎn)i和j進(jìn)行權(quán)值分配。

假設(shè)a是一個(gè)轉(zhuǎn)換向量，得到y(tǒng)T=aTX，其中，X的第i個(gè)列向量是xi，得到關(guān)于y的最小化問題可以化簡為

其中：D是對角矩陣，對角線上的元素值是對于W的行（或列）的和，即Dii=∑jWji。L=D－W是拉普拉斯矩陣，L是對稱的正半定矩陣，它可以看作是定義在鄰接圖G頂點(diǎn)上的函數(shù)算子。為防止消除任意的縮放因子，故施加了限制yTDy=1。

接下來用拉格朗日公式來表示這個(gè)最小化問題，引入拉格朗日乘子λ，并設(shè)z=D1/2y，使目標(biāo)函數(shù)最小的向量y由特征值分解的方法給出。

在經(jīng)過拉普拉斯特征映射后，特征向量y將是原始數(shù)據(jù)點(diǎn)的低維表示。

d）假設(shè)b是一個(gè)逆轉(zhuǎn)換向量，則需要最小化目標(biāo)函數(shù)min‖byT－X‖，進(jìn)而求得進(jìn)化過后低維空間投影到高維空間的數(shù)據(jù)X′。

X′=byT（7）

2.2 基于非支配排序調(diào)節(jié)的歸檔集設(shè)計(jì)

種群規(guī)模在進(jìn)化過程中起到不可忽視的作用，種群規(guī)模越小收斂越快，但是對于大規(guī)模問題而言容易進(jìn)入局部最優(yōu)解。而種群規(guī)模越大，個(gè)別的最優(yōu)解雖不容易主導(dǎo)全體解的進(jìn)化方向，避免陷入局部最優(yōu)解，但將導(dǎo)致計(jì)算復(fù)雜度提高，收斂速度變慢。如何在固定種群下規(guī)模盡可能有效和精準(zhǔn)地求出轉(zhuǎn)換向量a也是一個(gè)關(guān)鍵問題。

因此，結(jié)合以上問題，本文建立一個(gè)可進(jìn)行自我動態(tài)調(diào)整的歸檔集，在種群規(guī)模為N的情況下，初始化種群的同時(shí)也對歸檔集進(jìn)行初始化，即先讓種群進(jìn)化幾代，從這個(gè)過程中提取出2N個(gè)非劣解加入到歸檔集，并對歸檔集設(shè)置一個(gè)上限3N，避免規(guī)模無限增大，并將后續(xù)種群進(jìn)化過程中產(chǎn)生的非劣解加入該歸檔集。當(dāng)歸檔集里非劣解的個(gè)數(shù)超過3N的時(shí)候，通過非支配排序更新歸檔集，提取出非支配解，使歸檔集里解的數(shù)量降低到2N。

在非支配排序中，為了衡量在同一個(gè)等級中各個(gè)解質(zhì)量的優(yōu)劣，引入了一個(gè)擁擠度的計(jì)算，其目的是讓求得的Pareto最優(yōu)解在空間中盡量分散，也就有更大可能讓解在Pareto最優(yōu)前沿上均勻分布，第i個(gè)解的擁擠度ci的計(jì)算如下：

其中： fi+1j、fi－1j分別為第j個(gè)目標(biāo)函數(shù)數(shù)值排序后與第i個(gè)解相鄰的函數(shù)值； fmaxj和fminj分別為第j個(gè)目標(biāo)函數(shù)數(shù)值排序后的最大和最小值。

算法1 基于非支配排序調(diào)節(jié)的歸檔集

從公式以及算法1可以看出，在設(shè)計(jì)歸檔集時(shí)，對歸檔集設(shè)置上限和加入非劣解擴(kuò)充規(guī)模，保證了訓(xùn)練轉(zhuǎn)換向量a的歸檔集規(guī)模。

2.3 算法步驟

算法的具體流程如算法2和圖1所示。首先，本文初始化種群大小為N，種群為X，迭代數(shù)的最大值為T。然后，初始化歸檔集Arc，先將歸檔集設(shè)為空集，從種群中取交叉突變后新生成的非劣解加入到歸檔集中，生成具有流行結(jié)構(gòu)的歸檔集，以便于訓(xùn)練轉(zhuǎn)換向量a。

當(dāng)?shù)鷶?shù)t小于迭代最大值T時(shí)，繼續(xù)對種群進(jìn)行進(jìn)化計(jì)算。對于種群Xt，低維空間的種群yt可由公式訓(xùn)練過后的轉(zhuǎn)換向量a得到。對于每個(gè)解yi∈yt，從yi中隨機(jī)選擇一個(gè)解yj∈yt，通過在yi和yj上用遺傳算子生成子代。然后通過逆轉(zhuǎn)換向量b轉(zhuǎn)換得到一個(gè)新的種群X′t，并從X′t中提取新生成的非劣解，添加到歸檔集Arc中進(jìn)行更新。歸檔集Arc的更新如算法1所示。SMDVDR算法流程如圖1所示。

算法2 SMDVDR算法

3 實(shí)驗(yàn)與結(jié)果分析

3.1 對比算法

將基于自變量簡約的稀疏多目標(biāo)進(jìn)化算法與五個(gè)MOEA進(jìn)行比較，以研究所提算法的性能。這五個(gè)MOEA分別為NSGA-Ⅱ［6］、CMOPSO［29］、MOEA/D-DRA［30］和LMOCSO［31］，其中NSGA-Ⅱ?yàn)檫z傳算法，CMOPSO為粒子群優(yōu)化算法，MOEA/D-DRA為差分進(jìn)化算法，LMOCSO是一種針對大規(guī)模優(yōu)化問題粒子群優(yōu)化的仿生搜索算法。

3.2 測試問題

本文使用SMOP1～SMOP8八個(gè)基準(zhǔn)問題測試算法性能［12］。在這八個(gè)基準(zhǔn)問題中，每個(gè)函數(shù)都定義了一組稀疏Pareto最優(yōu)解。其中對于SMOP1～SMOP3，以及SMOP7和SMOP8，只有當(dāng)指定的決策變量設(shè)置為0時(shí)，它們的函數(shù)才能最小化。對于SMOP4～SMOP6，解的稀疏性直接涉及到函數(shù)，類似于特征選擇問題可以測試算法尋找稀疏Pareto最優(yōu)解的性能，總之，SMOP1～SMOP8具有多種函數(shù)且函數(shù)定義一組稀疏Pareto最優(yōu)解，其側(cè)重于測試算法尋找稀疏Pareto最優(yōu)解的性能。

除此以外，為了研究該算法在具體案例上的應(yīng)用。本文還使用了兩個(gè)實(shí)際問題，即稀疏社區(qū)檢測（community detection problem，Sparse CD）和稀疏神經(jīng)網(wǎng)絡(luò)應(yīng)用問題（neural network training，Sparse NN）。

對于SMOP1～SMOP8，本文在實(shí)驗(yàn)中將目標(biāo)個(gè)數(shù)M設(shè)為2，決策變量個(gè)數(shù)D設(shè)為100、500、1 000，Pareto最優(yōu)解的稀疏度θ設(shè)為0.1。在Sparse CD和Sparse NN中，目標(biāo)個(gè)數(shù)M設(shè)為2，Sparse CD的決策變量個(gè)數(shù)D設(shè)為34、62、105和115，Sparse NN的決策變量個(gè)數(shù)D設(shè)為321、401、521和1 241。

3.3 性能指標(biāo)

1）倒代距離IGD

倒代距離（inverted generational distance， IGD）可以用來評估不同算法的Pareto最優(yōu)集。IGD的空間意義可以理解為每個(gè)點(diǎn)到最近候選解的平均歐氏距離，解集的綜合性能越好，候選解集和點(diǎn)集更接近，因此IGD的值越低，代表結(jié)果越好。IGD的計(jì)算公式為

其中：P*為均勻分布在Pareto前沿的點(diǎn)的集合；P為算法得到的解的集合；d（v，P）是從v到P的歐氏距離。

2）超體積HV

超體積（hypervolume，HV）可以同時(shí)評價(jià)MOEA的收斂性和多樣性，是一個(gè)綜合性指標(biāo)。一個(gè)MOEA所獲得的解集的HV越大，說明該解集的收斂性和多樣性更好。HV的計(jì)算公式為

其中：Vol代表勒貝格測度，用來測量體積；S代表非支配解集；vi代表參考點(diǎn)和非支配個(gè)體構(gòu)成的超體積。

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

表1、2列出了SMOP1～SMOP8測試基準(zhǔn)問題和兩個(gè)實(shí)際問題的參數(shù)設(shè)置，包括種群規(guī)模、運(yùn)行次數(shù)、決策變量數(shù)D。實(shí)驗(yàn)采用模擬二元交叉和多項(xiàng)式突變產(chǎn)生子代，當(dāng)所有測試問題達(dá)到最大進(jìn)化生成數(shù)且最大生成數(shù)100×D時(shí)，算法終止。

3.5 實(shí)驗(yàn)結(jié)果及分析

首先在SMOP基準(zhǔn)測試問題的不同決策變量上進(jìn)行實(shí)驗(yàn)，用表3列出在決策變量為100、500和1 000時(shí)，五種算法在測試問題上的IGD對比，并對本文算法與NSGA-Ⅱ、CMOPSO、MOEA/D-DRA、LMOCSO和MOEA/DVA五種進(jìn)化算法在SMOP測試問題上運(yùn)行30次得到的IGD值進(jìn)行比較。在表中，“優(yōu)于”“近似于”“差于”表示本文SMDVDR在5%顯著性水平下的Wilcoxon秩和檢驗(yàn)與其他算法的對比結(jié)果。其中最好的結(jié)果已用粗體表示。

從表3可以看出，SMDVDR算法相比其他算法有明顯的優(yōu)勢。具體來說，在24個(gè)基準(zhǔn)測試?yán)又校琒MDVDR獲得了19個(gè)最優(yōu)的結(jié)果，其中NSGA-Ⅱ獲得了3個(gè)最優(yōu)的結(jié)果，CMOPSO和MOEADDRA各自獲得了1個(gè)最優(yōu)的結(jié)果。SMDVDR在除SMOP3以外的測試問題上均有較良好的結(jié)果。

為了進(jìn)一步觀察基于自變量簡約的稀疏多目標(biāo)進(jìn)化算法的優(yōu)劣，在決策變量為500時(shí)，通過圖2將基于自變量簡約的稀疏多目標(biāo)進(jìn)化算法與NSGA-Ⅱ、CMOPSO、MOEA/D-DRA和LMOCSO四種進(jìn)化算法的IGD值進(jìn)行對比。

觀察圖2可知，SMOP1、SMOP2、SMOP4～SMOP8這幾個(gè)稀疏測試問題中，NSGA-Ⅱ、CMOPSO、MOEA/D-DRA和LMOCSO都無法較好收斂到Pareto前沿，而SMDVDR算法在這幾個(gè)測試問題上獲得了較好的收斂種群。

接著在實(shí)際應(yīng)用問題上進(jìn)行實(shí)驗(yàn)測試，由于實(shí)際問題中的真實(shí)Pareto最優(yōu)解不可知，IGD指標(biāo)往往不可以直接用來評價(jià)實(shí)際問題中的算法性能，所以本文使用HV評價(jià)實(shí)際問題的算法性能。表4列出本文算法在Sparse CD和Sparse NN兩個(gè)實(shí)際問題上，與NSGA-Ⅱ、CMOPSO、MOEA/D-DRA、LMOCSO和MOEA/DVA五種進(jìn)化算法的HV值對比，其中最好的結(jié)果加粗顯示。

從表4可以看出，相比其他算法，SMDVDR在解決這些實(shí)際問題中具有顯著優(yōu)勢。具體而言，SMDVDR在八個(gè)測試?yán)又幸还踩〉昧税藗€(gè)最優(yōu)的結(jié)果，NSGA-Ⅱ和CMOPSO同時(shí)在稀疏社區(qū)檢測問題上獲得了三個(gè)最優(yōu)結(jié)果。總的來說，SMDVDR在決策變量的個(gè)數(shù)大于100的時(shí)候，表現(xiàn)得比其他算法更好，能說明SMDVDR在大規(guī)模多目標(biāo)優(yōu)化問題上有顯著的優(yōu)勢。

因此，SMDVDR算法在基準(zhǔn)測試問題上取得了較優(yōu)的結(jié)果，且在實(shí)際問題的應(yīng)用上也有顯著優(yōu)勢。

4 結(jié)束語

本文設(shè)計(jì)了一種基于自變量簡約的大規(guī)模稀疏多目標(biāo)進(jìn)化算法。首先，提出了一種基于LPP降維的自變量簡約方法，既保持?jǐn)?shù)據(jù)的局部鄰居結(jié)構(gòu)不變，又降低原始數(shù)據(jù)的維數(shù)，從而達(dá)到提取數(shù)據(jù)特征的目的。在進(jìn)化過程中，算法利用新生成的非劣解補(bǔ)充優(yōu)秀個(gè)體加入歸檔集，并利用歸檔集訓(xùn)練降維矩陣。然后利用降維矩陣將種群投影到低維空間上，并在低維空間進(jìn)行交叉變異操作。最后利用當(dāng)前已知的原始矩陣和低維矩陣，通過最小范數(shù)求低維空間到高維空間的逆矩陣，進(jìn)而求得進(jìn)化后的矩陣。通過8個(gè)SMOP測試問題和2個(gè)實(shí)際應(yīng)用問題，對基于自變量簡約的稀疏多目標(biāo)進(jìn)化算法的性能進(jìn)行了研究。實(shí)驗(yàn)結(jié)果表明，基于自變量簡約的稀疏多目標(biāo)進(jìn)化算法在解決SMOP問題時(shí)有較好的效果，在解決實(shí)際應(yīng)用問題上也有明顯的優(yōu)勢。

參考文獻(xiàn)：

［1］Cui Yunfei，Geng Zhiqiang，Zhu Qunxiong，et al. Review： multi-objective optimization methods and application in energy saving［J］. Energy，2017，125： 681-704.

［2］Suzuki S，Takeno S，Tamura T，et al. Multi-objective Bayesian optimization using Pareto-frontier entropy［C］// Proc of the 37th International Conference on Machine Learning. ［S.l.］： PMLR，2020： 9279-9288.

［3］Cai Xingjuan，Hu Zhaoming，Zhao Peng，et al. A hybrid recommendation system with many-objective evolutionary algorithm［J］. Expert Systems with Applications，2020，159： 113648.

［4］Pan Linqiang，Li Lianghao，He Cheng，et al. A subregion division-based evolutionary algorithm with effective mating selection for many-objective optimization［J］. IEEE Trans on Cybernetics，2019，50（8）： 3477-3490.

［5］Coelho D，Madureira A，Pereira I，et al. A review on MOEA and metaheuristics for feature-selection［C］// Proc of International Conference on Innovations in Bio-Inspired Computing and Applications. Cham： Springer，2021： 216-225.

［6］Verma S，Pant M，Snasel V. A comprehensive review on NSGA-Ⅱ for multi-objective combinatorial optimization problems［J］. IEEE Access，2021，9： 57757-57791.

［7］Singh J. A review and comparison of two archive based algorithms： SPEA2 and PAES［J］. AIP Conference Proceedings，2023，2819（1）： 090003.

［8］Ouelmokhtar H，Benmoussa Y，Diguet J P，et al. Near-optimal cove-ring solution for USV coastal monitoring using PAES［J］. Journal of Intelligent & Robotic Systems，2022，106（1）： 24.

［9］Guerreiro A P，F(xiàn)onseca C M，Paquete L. The hypervolume indicator： computational problems and algorithms［J］. ACM Computing Surveys，2021，54（6）： 1-42.

［10］Bader J，Zitzler E. HypE： an algorithm for fast hypervolume-based many-objective optimization［J］. Evolutionary Computation，2011，19（1）： 45-76.

［11］Bao Chunteng，Gao Diju，Gu Wei，et al. A new adaptive decomposition-based evolutionary algorithm for multi-and many-objective optimization［J］. Expert Systems with Applications，2023，213：119080.

［12］Tian Ye，Zhang Xingyi，Wang Chao，et al. An evolutionary algorithm for large-scale sparse multiobjective optimization problems［J］. IEEE Trans on Evolutionary Computation，2019，24（2）： 380-393.

［13］Zhou Xiangbing，Cai Xing，Zhang Hua，et al. Multi-strategy competitive-cooperative co-evolutionary algorithm and its application［J］. Information Sciences，2023，635： 328-344.

［14］Peng Chen，Hui Qing. Epsilon-constrained CCPSO with different improvement detection techniques for large-scale constrained optimization［C］// Proc of the 49th Hawaii International Conference on System Sciences. Piscataway，NJ： IEEE Press，2016： 1711-1718.

［15］Aguilar-Justo A E，Mezura-Montes E. A local cooperative approach to solve large-scale constrained optimization problems［J］. Swarm and Evolutionary Computation，2019，51： 100577.

［16］Cheng Ran，Jin Yaochu. A social learning particle swarm optimization algorithm for scalable optimization［J］. Information Sciences，2015，291： 43-60.

［17］陳暄，孟凡光，吳吉義. 求解大規(guī)模優(yōu)化問題的改進(jìn)狼群算法［J］. 系統(tǒng)工程理論與實(shí)踐，2021，41（3）： 790-808. （Chen Xuan，Meng Fanguang，Wu Jiyi. Improved wolf pack algorithm for large-scale optimization problems［J］. Systems Engineering-Theory and Practice，2021，41（3）： 790-808.）

［18］Wang Hao，Liang Mengnan，Sun Chaoli，et al. Multiple-strategy lear-ning particle swarm optimization for large-scale optimization problems［J］. Complex & Intelligent Systems，2021，7： 1-16.

［19］Tian Ye，Liu Ruchen，Zhang Xingyi，et al. A multipopulation evolutionary algorithm for solving large-scale multimodal multiobjective optimization problems［J］. IEEE Trans on Evolutionary Computation，2020，25（3）： 405-418.

［20］Suganya A，Singh R A，Velliangiri S，et al. Feature extraction using a residual deep convolutional neural network（ResNet-152） and optimized feature dimension reduction for MRI brain tumor classification［J］. Diagnostics，2023，13（4）： 668.

［21］Cunha B Z，Droz C，Zine A M，et al. A review of machine learning methods applied to structural dynamics and vibroacoustic［J］. Mechanical Systems and Signal Processing，2023，200： 110535.

［22］Hasan B M S，Abdulazeez A M. A review of principal component analysis algorithm for dimensionality reduction［J］. Journal of Soft Computing and Data Mining，2021，2（1）： 20-30.

［23］Anowar F，Sadaoui S，Selim B. Conceptual and empirical comparison of dimensionality reduction algorithms （PCA，KPCA，LDA，MDS，SVD，LLE，ISOMAP，LE，ICA，t-SNE）［J］. Computer Science Review，2021，40： 100378.

［24］Levada A L M. A curvature based isometric feature mapping ［C］// Proc of the 26th International Conference on Pattern Recognition. Piscataway，NJ： IEEE Press，2022： 557-563.

［25］Roth M，F(xiàn)ranke G，Rinderknecht S. A comprehensive approach for an approximative integration of nonlinear-bivariate functions in mixed-integer linear programming models［J］. Mathematics，2022，10（13）： 2226.

［26］Zhang Kai，Shen Chaonan，Yen G G，et al. Two-stage double niched evolution strategy for multimodal multiobjective optimization［J］. IEEE Trans on Evolutionary Computation，2021，25（4）： 754-768.

［27］Wang Xiangyu，Zhang Kai，Wang Jian，et al. An enhanced competitive swarm optimizer with strongly convex sparse operator for large-scale multiobjective optimization［J］. IEEE Trans on Evolutionary Computation，2021，26（5）： 859-871.

［28］Hua Yicun，Liu Qiqi，Hao Kuangrong，et al. A survey of evolutionary algorithms for multi-objective optimization problems with irregular Pareto fronts［J］. IEEE/CAA Journal of Automatica Sinica，2021，8（2）： 303-318.

［29］Zhang Xingyi，Zheng Xiutao，Cheng Ran，et al. A competitive mechanism based multi-objective particle swarm optimizer with fast convergence［J］. Information Sciences，2018，427： 63-76.

［30］Xu Meng，Zhang Maoqing，Cai Xingjuan，et al. Adaptive neighbourhood size adjustment in MOEA/D-DRA［J］. International Journal of Bio-Inspired Computation，2021，17（1）： 14-23.

［31］Tian Ye，Zheng Xiutao，Zhang Xingyi，et al. Efficient large-scale multiobjective optimization based on a competitive swarm optimizer［J］. IEEE Trans on Cybernetics，2019，50（8）： 3696-3708.