基于新型擁擠度距離的多目標麻雀搜索算法

溫澤宇，謝 珺，謝 剛，2，續欣瑩

1.太原理工大學 電氣與動力工程學院，太原030024

2.太原科技大學 電子信息工程學院 先進控制與裝備智能化山西省重點實驗室，太原030024

3.太原理工大學 信息與計算機學院，山西 晉中030600

在現代科學研究和工程實際應用中，需要優化的目標往往不止一個，而且各個目標存在相互制約的關系，傳統的優化算法很難處理這些復雜的問題，其優化過程存在較大的挑戰，因此對于多目標優化算法的研究是非常必要的。這種要求多個目標同時達到最優的問題叫作多目標優化問題（Multi-objective Optimization Problem，MOP）。

近年來，多目標進化算法的研究取得了長足的進步，國內外許多學者將在單目標問題上表現突出的智能優化算法應用于多目標問題。例如基于進化算法的多目標優化方法：非支配排序遺傳算法（Non-dominated Sorted Genetic Algorithm，NSGA）[1]及改進版本（NSGA-II）[2]、強度Pareto進化算法（Strength Pareto Evolutionary Algorithm，SPEA）[3]及改進版本（SPEA2）[4]等；基于生物群體的多目標優化方法：多目標粒子群算法（Multi-Objective Particle Swarm Optimization，MOPSO）[5]、多目標灰狼算法（Multi-Objective Grey Wolf Optimizer，MOGWO）[6]等。同時，為了使多目標優化算法擁有更好的收斂性和分布性，學者們將一些新的機制和進化范例引入到多目標優化領域。文獻[7]在多目標螢火蟲算法的基礎上利用混合水平正交實驗設計方法產生初始種群，并采用三點最短路徑方法維護外部檔案的多樣性，取得了較好的效果；文獻[8]采用簡化的K-最近鄰方法維持多目標粒子群算法的外部存檔，并對其中的粒子采取有生存期的淘汰機制，提高了算法的性能；文獻[9]提出一種基于群體分布信息的自適應多目標粒子群算法，通過統計方法分析歸檔集在決策空間的分布特征，劃分進化狀態，指導全局引導粒子的選擇。

麻雀搜索算法[10]（Sparrow Search Algorithm，SSA）是2020 年提出的一種新的智能優化算法，具有可調參數少、局部搜索能力強的優點。文獻[11]通過大量實驗證明了SSA算法在收斂速度、收斂精度和穩定性方面的優越性。之后學者們將SSA應用于無人機航跡規劃[12]、圖像分割[13]等問題中，取得了較好的實驗效果。本文基于SSA 算法和部分學者提出的算法啟示，提出一種新型的多目標優化算法——多目標麻雀搜索算法（Multiobjective Sparrow Search Algorithm，MSSA）。在麻雀搜索算法基礎上，以外部存檔收斂性作為麻雀種群比例因子自適應調節的依據，動態調整算法的全局搜索和局部開發能力，并引入多項式變異算子在算法求解停滯時觸發變異，跳出局部最優；借鑒NSGA-II 算法非支配排序對麻雀種群進行排序[2]和外部存檔機制，并提出新的擁擠度距離計算公式，提高算法優化效率和Pareto解集的質量。采用多種標準測試函數以及盤式制動器模型對算法進行仿真實驗，與多種多目標優化算法進行對比，結果表明MSSA具有更好的優化性能和穩定性。

1 基本概念

1.1 多目標優化問題

多目標優化問題在解決優化問題時需要同時考慮多個相關因素，對于有N個優化目標的MOP，其一般數學描述形式如下：

其中，fi代表了第i個目標優化函數，x代表所要優化的n維變量，N是目標函數的個數。

1.2 麻雀搜索算法

在麻雀覓食過程中，麻雀種群分為發現者和加入者，通過種群比例因子w進行控制。發現者在種群中負責尋找食物，并為整個麻雀種群提供覓食區域和方向，而加入者則是利用發現者來獲取食物。

1.2.1 發現者數學模型

在SSA中，具有較好適應度值的發現者在搜索過程中會優先獲取食物。此外，因為發現者負責為整個麻雀種群尋找食物，并為所有加入者提供覓食的方向，所以發現者可以獲得比加入者更大的覓食搜索范圍。在每次迭代的過程中，發現者的位置更新描述如下：

其中，t代表當前迭代數；G是一個常數，表示最大的迭代次數；α∈(0,1]是一個隨機數；R2(R2∈[0,1])和ST(ST∈[0.5,1.0])分別表示預警值和安全值；Q是服從正態分布的隨機數。

1.2.2 加入者數學模型

加入者的位置更新描述如下：

其中，Xp是目前發現者所占據的最優位置；Xworst表示當前全局最差的位置；A表示一個1×d的矩陣，其中每個元素隨機賦值為1或－1，并且A＋=AT(AAT)－1。

1.2.3 反哺食行為

當意識到危險時，麻雀種群會做出反捕食行為，其位置更新如下：

其中，Xbest是當前的全局最優位置；β是步長控制參數，是服從均值為0，方差為1的正態分布的隨機數；K∈[－1,1]是一個隨機數；fg和fw分別是當前全局最佳和最差的適應度值；ε是一個常數，避免分母出現0。

2 多目標麻雀搜索算法

為了將麻雀搜索算法應用于多目標優化問題，對麻雀種群排序時借鑒NSGA-II 中的非支配排序[2]方法，以及在麻雀搜索算法中引入外部種群，用于存儲非支配解。

2.1 自適應調整種群比例因子

MSSA由于缺乏待優化問題的先驗知識，有必要根據種群收斂狀態的反饋信息動態調整參數。文獻[14]證明了以粒子對外部存檔收斂性的貢獻為標準反映種群收斂狀態，改進了多目標粒子群算法，可以提高算法性能。受此啟發，本文在MSSA 中引入收斂貢獻因子Q，動態調整種群比例因子w，協調算法的全局探索能力和局部開發能力。

通常算法所求得的非支配解對外部存檔S中解的收斂性貢獻按式（4）求得[14]：

其中，S為外部存檔；ρ(xi,x)為xi對x的支配程度，按式（5）計算：

其中，M為目標函數個數；fj,max和fj,min為外部存檔S中非支配解在第j個目標函數上的最大值和最小值。ρ(xi,x)定量地給出了xi對x的支配程度。在此基礎上，當xi加入檔案時，以xi對檔案解的支配程度最大者作為其收斂性貢獻。如果xi被檔案中的解支配或者互不支配，則其對檔案收斂性貢獻為0。當所有粒子對檔案的收斂性貢獻趨近0時，表明種群達到收斂穩定狀態。

當算法在第t次迭代時，生成xi(i=1,2,…,np)個非支配解，其收斂貢獻因子為Q，即：

Q反映算法每次迭代的收斂性，當Q較大時，算法全局搜索能力強，當Q減小時，算法逐步收斂穩定。

圖1為本文算法在多模態測試函數ZDT4上的收斂因子變化曲線，其變化幅度較大且周期較長，表明算法不斷產生新解替換檔案的舊解；同時，算法在兩次運行過程中變化幅度與趨勢不同，說明種群在迭代過程中具有非線性和不確定性，根據進化過程調節算法搜索能力有助于提高算法性能。借鑒Logistic函數更新種群比例因子w，如式（7）所示：

圖1 收斂因子變化曲線Fig.1 Change curve of convergence factor

其中，Q∈[0,1]。當Q較大時，說明算法處在全局探索階段，此時w增大，擴大發現者比例，促進搜索個體在更大范圍內尋找新解；Q值較小時，w減小，擴大加入者比例，提升算法的局部尋優能力，有效改善了Pareto解集的質量。

2.2 多項式變異算子

在優化迭代過程中，由于優化問題的復雜性，算法往往會陷入局部最優問題。麻雀搜索算法中發現者有重要的作用，引導群體向最優解移動，若發現者陷入局部最優，則容易導致群體出現搜索停止，群體多樣性喪失。而在算法中引入變異算子，不僅可以使算法加速向最優解收斂，而且也可以維持解的多樣性。多項式變異算子[15]是學者Deb提出來的一種變異方法，也是研究者們研究多目標優化時主要使用的一種變異算子。因此，對多目標麻雀搜索算法中的發現者引入多項式變異。

多項式變異算子形式如式（8）所示：

式中，δ1=(vk－lk)/(uk－lk),δ2=(uk－vk)/(uk－lk),u是一個[0,1]區間內的隨機數，ηm是分布指數，ηm越大，變異產生的子代個體越靠近父代，lk表示位置下限，uk表示位置上限。

決定進行變異的概率Pm如式（10）所示：

其中，t為當前迭代次數，Tm為最大迭代次數。從式（10）可以看出，初始的多項式變異頻率較大，接近2P0，隨著迭代次數的增加，變異頻率變小，接近P0。這樣，既能在算法求解停滯時觸發變異，又避免了不利的變異。

2.3 麻雀個體非支配排序

與麻雀搜索算法不同，多目標優化算法的適應度值是目標向量，而不是標量，無法通過某一函數值進行直接比較。因此，在多目標麻雀搜索算法中，將種群進行非支配排序[2]以確定適應度值大小，對麻雀種群個體進行排序，進而區分發現者和加入者。

在非支配排序過程中，麻雀種群中的個體都有兩個參數N(i)和S(i)，N(i)為在種群中支配個體i的解的個體的數量，S(i)為被個體i所支配的解的個體的集合。根據Pareto 支配關系，個體被支配的次數越少，個體越優。步驟如下：

（1）計算種群中每個個體的兩個參數N(i)和S(j)。

（2）將所有N(i)=0 的個體存入當前的集合F(1)。

（3）對于當前集合F(1)中的個體j，考察其所支配的個體S(j)，將集合S(j)中的每個個體k的解個體數減去1。

（4）如果N(k)－1=0，則將個體存入另外一個集合H。

（5）將F(1)作為第一級非支配個體集合，并賦予該集合內個體一個相同的非支配序i(rank)，然后繼續對H做上述分級操作并賦予相應的非支配序，直到所有的個體都被分級排序。

2.4 外部存檔策略

與單目標麻雀搜索算法不同，多目標優化算法的適應度是目標向量，而不是標量，無法進行直接比較。因此，多目標麻雀搜索算法將種群進行非支配排序[2]確定適應度大小，以及在種群外設置一個外部存檔[6，16]，利用算法每次迭代所產生的非支配解，不斷更新外部存檔。

（1）算法每次迭代產生的新個體，如果在外部存檔中存在一個解支配該新個體，則不加入外部存檔。

（2）新個體支配外部存檔中一個或多個個體，則新個體替換外部存檔中被其支配的個體。

（3）新個體與外部存檔中所有個體均互不支配，將該新個體加入外部存檔。

（4）在更新過程中，外部存檔種群中個體可能會越來越多，通常外部存檔設有上限，為了使外部存檔種群個體數不超過上限，同時保持種群多樣性，借鑒NSGA-II[2]中根據解的擁擠度大小剔除相似個體的方法對種群進行裁剪：

①計算外部存檔種群中每個麻雀個體的目標函數值F(f1(x),f2(x),…,fN(x)),并找出每個目標函數極值fimin(x)和fimax(x)。

②計算每一個麻雀個體的擁擠度距離Dc(j)：

其中，fi(j－1)和fi(j ＋1)為麻雀個體j相鄰的兩個個體在第i個目標函數的適應度值。

③每個可行解在整個解空間中都有擁擠程度的屬性，當外部存檔種群個體數超過上限時，優先選擇擁擠度高的，即Dc(j)值較小的個體剔除出外部存檔種群，以維持種群個體上限，同時保持種群多樣性。

從圖2中可以看出，盡管按照式（11）計算出的擁擠度相等，但是個體B和個體E的分布是不同的，個體B擁擠程度要好于E。

圖2 擁擠距離示意圖Fig.2 Schematic diagram of crowding distance

為了更好地體現個體的均勻分布，采用一種新的擁擠度距離計算公式，具體描述如下：

其中，Di為個體j在第i個目標函數的距離比值，恒小于1，其更為細致地反映出個體之間的分布比例。個體j在多目標的總擁擠度距離計算如下：

其中，N為目標函數的個數。Dc的值大小越接近N，擁擠度越均勻；Dc的值越小，擁擠度越高。當個體B和E擁有相同的鄰居時，且B更靠近鄰居的中間位置時，可以正確地求解出個體的擁擠距離好于E，有利于提高解分布的均勻性。

圖3 為MSSA 在測試函數ZDT2 上迭代次數為100時分別利用式（11）和式（12）對種群進行裁剪的結果，可以看出圖（a）解分布均勻性好于圖（b）。

圖3 兩種結果對比Fig.3 Comparison of two results

2.5 MSSA算法流程

結合前面提到的策略，本文提出一種新的多目標優化算法——多目標麻雀搜索算法。具體流程如下：

2.6 算法復雜度分析

假設待優化MOP問題的目標個數為M，麻雀種群個數為N，當前外部存檔的個數為Ar，個體維度為n。

算法初始化的時間復雜度為O(nN)，求解目標函數適應度的時間復雜度為O(MN)，種群中的個體非支配排序的時間復雜度為O(MN2)；循環體內發現者位置更新的時間復雜度為O(r1Nn)，其中r1為發現者占種群比例；多項式變異操作的時間復雜度為O(r3Nn)，其中r3為變異操作個體占比；加入者位置更新的時間復雜度為O((1－r1)Nn)；警戒者位置更新的時間復雜度為O(r2Nn)，其中r2為警戒者占種群比例；將非支配解集存到外部存檔，對外部存檔維護的時間復雜度為O(M(N ＋Ar)2log(N ＋Ar))，輸出最優解的時間復雜度為O(MAr)。綜上所述，MSSA的時間復雜度為O(nN)＋O(MN2)＋O(MN)＋O(r1Nn)＋O((1－r1)Nn)＋O(r2Nn)＋O(M(N ＋Ar)2log(N ＋Ar))＋O(r3Nn)＋O(MAr)。從整體上看，算法的時間復雜度主要與種群規模和外部存檔規模有關。

3 仿真實驗

3.1 實驗設置

本文為了驗證MSSA的性能，以多目標粒子群算法（MOPSO）、多目標灰狼算法（MOGWO）、NSGA-II 和SPEA2作為對比算法。實驗過程中，為保證公平性和客觀性，所有算法的主要參數設置如下：外部存檔規模N′=200,種群規模N=200,最大迭代次數Tmax=150。各對比算法的主要參數如表1所示，其余變量按照對應的參考文獻設置。

表1 算法參數設置Table 1 Algorithm parameter setting

3.2 性能指標

為比較不同優化算法的性能，選取兩種評價指標來量化算法的性能。

（1）反轉迭代距離（IGD）[17]

用于衡量所求Pareto解集和Pareto參考解集間的平均最小距離，IGD 值越小，說明算法的收斂性與多樣性越好，越接近真實的Pareto前沿。IGD的數學表達式如下所示：

其中，P*是真實的Pareto前沿；P為算法所獲得的最優解集；mindis(x,P)為Pareto 真實解x和算法所得解P的最小歐氏距離；|P*|是解集P*中的個數。

（2）空間評價（SP）[18]

用于衡量每個解到其他相鄰解之間最小距離的標準差，SP值越小，說明解集越均勻。SP數學表達式如下所示：

3.3 標準測試函數

為了驗證所提算法的有效性，選取ZDT[19]系列（雙目標f1和f2）和DTLZ[20]系列（三目標f1、f2和f3）部分函數考察算法求解不同MOP問題時的性能。這些測試函數擁有不同的Pareto 最優前沿，形狀各不相同，被認為是具有挑戰性的測試問題。標準測試函數如表2所示。

表2 標準測試函數Table 2 Standard test functions

3.4 實驗結果與分析

各測試函數運行20 次，平均所需時間如表3 所示。可以看出，MSSA和NSGA-II在大多數測試函數上取得了優于對比算法的效果。在算法迭代過程中，環境是實時變化的，種群比例因子w根據算法環境變化進行調整，達到算法參數精細化調控的目的，縮短了算法的運行時間。

表3 運行時間Table 3 Running time s

表4 和表5 分別列出了5 種算法在8 個測試問題上的IGD、SP 的平均值和標準差，每個結果均為同一算法在同一測試問題上獨立運行20次的統計結果。采用粗體字標出每一個測試函數的最優IGD值和SP值。為了直觀展示各算法所得解集的收斂性和分布性，圖4 和圖5 給出了5 種算法在部分測試問題上的Pareto 前沿。f1和f2為優化目標函數。

表4 IGD測試結果Table 4 Test results of IGD

表5 SP測試結果Table 5 Test results of SP

圖4 ZDT3測試結果Fig.4 Test result of ZDT3

圖5 ZDT4測試結果Fig.5 Test result of ZDT4

由表4 可知，本文的MSSA 算法在8 個測試函數上取得了4個最優的IGD均值，NSGA-II獲得2個最優值，SPEA2 獲得1 個最優值，MOGWO 獲得了1 個最優值。在一些比較簡單的多目標測試函數上如ZDT1和ZDT3上，MSSA取得了較好的收斂性，在ZDT2上的收斂效果僅次于NSGA-II，且兩種算法的結果具有相同的數量級。MSSA 算法以外部存檔的收斂性為指標更新麻雀種群比例因子，使得算法較快地度過全局搜索階段，進而進行充分的局部搜索，提高了算法收斂精度。在多模態問題測試函數如ZDT4和DTLZ7上，MSSA算法因為在發現者位置更新階段引入多項式變異因子，可以緩解算法早熟收斂現象，有助于提高算法跳出局部最優的能力，所以MSSA 在如上所述多模態測試函數上運行20 次所得IGD 均值最優。在DTLZ5 上取得了僅次于NSGA-II的收斂性。

通過表5 對比分析5 種算法的SP 性能指標可以看出，MSSA 算法在8 個測試函數上取得4 個最優值，NSGA-II 獲得3 個最優的SP 值，MOPSO 獲得1 個最優值，而其余的對比算法未能在分布性能指標上獲得最優值。在MSSA 算法中，改進了擁擠度距離計算公式，更充分地考慮了解的空間性，使其在多目標優化問題Pareto解集上有良好的分布性能，即SP值均較小。

為了進一步比較MSSA與文中其他對比算法性能，本文將兩種性能指標結果進行Wlicoxon 秩和檢驗實驗。按照顯著性水平α=0.5，將MSSA算法與其他4種算法進行對比分析。分析結果如表6 和表7 所示，“+”“-”“≈”分別表示MSSA的性能指標優于、劣于、近似于其余對比算法。從表6 和表7 可以看出，MSSA 算法的性能指標在大部分測試函數中優于MOPSO、MOGWO和SPEA2對比算法，具有明顯優勢，只有在個別測試函數上近似于或劣于NSGA-II。通過上述實驗可以看出，MSSA具有較優的收斂精度和分布性能。

表6 IGD Wilcoxon秩和檢驗Table 6 Wilcoxon rank sum test of IGD

表7 SP Wilcoxon秩和檢驗Table 7 Wilcoxon rank sum test of SP

3.5 盤式制動器設計

設計優化，特別是結構設計，在工程當中有著廣泛的應用。盤式制動器設計[21]是一個廣為人知的多目標工程設計問題。該問題有4個設計變量：圓盤外半徑R和內半徑r，接合力F和摩擦表面數目s。目標是最小化制動器質量f1(x)和制動時間f2(x)。該設計的約束包括半徑之間的最小距離、制動器的最大長度、壓力、溫度和扭矩的限制，分別用g1(x)、g2(x)、g3(x)、g4(x)和g5(x)表示。問題描述如下：

最小化目標：

為測試MSSA算法在解決實際優化問題中的有效性，將其應用于盤式制動器設計問題。采用MOPSO和NSGAII作為對比算法，算法初始種群規模設定為100，最大迭代次數設定為200，其余參數設置與表1 一致。各算法獨立運行10 次并取平均值得到的Pareto 前沿如圖6 所示。通過圖6可以看出，MSSA得到的結果是平滑的，與MOPSO和NSGA-II的結果相同甚至更好。MSSA的解分布在（0.286，14.682）和（2.751，2.101）之間，MOPSO的解分布在（0.312，14.012）和（2.712，2.187）之間，NSGA-II的解分布在（0.463，13.924）和（2.647，2.154）之間。為了更好地驗證MSSA 的性能，選取前文提到的空間評價SP和運行時間進行實驗，如表8所示。

圖6 盤式制動器設計測試結果Fig.6 Test result of disc brake design

表8 空間評價和運行時間Table 8 SP and running time

4 結束語

近些年，基于新型啟發式算法和協同策略的多目標優化算法逐漸成為多目標優化領域新的研究熱點。本文基于麻雀搜索算法，將其應用到多目標問題中，提出一種新型多目標優化算法——多目標麻雀搜索算法（MSSA）。在種群更新過程中，將外部存檔收斂性與麻雀種群發現者比例相結合，動態調整算法的全局搜索和局部開發能力，提高多目標算法的收斂性，并引入多項式變異算子在算法求解停滯時觸發變異，跳出局部最優，借鑒非支配排序方法對種群個體進行排序，并利用新型擁擠度距離計算方式對外部存檔進行裁剪，解決了解的優劣判定問題，提高算法優化效率和非支配解集的質量。采用測試函數和盤式制動器設計模型對算法進行仿真實驗，結果表明與其余多目標優化算法相比，MSSA可以獲得具有良好分布性的可行解。

未來將從兩方面做進一步的工作：（1）是否可以從外部存檔中選取個體作為發現者，提升多目標算法的收斂性；（2）利用更多的MOP測試函數對算法進行測試。