基于新型擁擠度距離的多目標(biāo)麻雀搜索算法

溫澤宇，謝 珺，謝 剛，2，續(xù)欣瑩

1.太原理工大學(xué) 電氣與動(dòng)力工程學(xué)院，太原030024

2.太原科技大學(xué) 電子信息工程學(xué)院 先進(jìn)控制與裝備智能化山西省重點(diǎn)實(shí)驗(yàn)室，太原030024

3.太原理工大學(xué) 信息與計(jì)算機(jī)學(xué)院，山西 晉中030600

在現(xiàn)代科學(xué)研究和工程實(shí)際應(yīng)用中，需要優(yōu)化的目標(biāo)往往不止一個(gè)，而且各個(gè)目標(biāo)存在相互制約的關(guān)系，傳統(tǒng)的優(yōu)化算法很難處理這些復(fù)雜的問題，其優(yōu)化過程存在較大的挑戰(zhàn)，因此對(duì)于多目標(biāo)優(yōu)化算法的研究是非常必要的。這種要求多個(gè)目標(biāo)同時(shí)達(dá)到最優(yōu)的問題叫作多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problem，MOP）。

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

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

1 基本概念

1.1 多目標(biāo)優(yōu)化問題

多目標(biāo)優(yōu)化問題在解決優(yōu)化問題時(shí)需要同時(shí)考慮多個(gè)相關(guān)因素，對(duì)于有N個(gè)優(yōu)化目標(biāo)的MOP，其一般數(shù)學(xué)描述形式如下：

其中，fi代表了第i個(gè)目標(biāo)優(yōu)化函數(shù)，x代表所要優(yōu)化的n維變量，N是目標(biāo)函數(shù)的個(gè)數(shù)。

1.2 麻雀搜索算法

在麻雀覓食過程中，麻雀種群分為發(fā)現(xiàn)者和加入者，通過種群比例因子w進(jìn)行控制。發(fā)現(xiàn)者在種群中負(fù)責(zé)尋找食物，并為整個(gè)麻雀種群提供覓食區(qū)域和方向，而加入者則是利用發(fā)現(xiàn)者來獲取食物。

1.2.1 發(fā)現(xiàn)者數(shù)學(xué)模型

在SSA中，具有較好適應(yīng)度值的發(fā)現(xiàn)者在搜索過程中會(huì)優(yōu)先獲取食物。此外，因?yàn)榘l(fā)現(xiàn)者負(fù)責(zé)為整個(gè)麻雀種群尋找食物，并為所有加入者提供覓食的方向，所以發(fā)現(xiàn)者可以獲得比加入者更大的覓食搜索范圍。在每次迭代的過程中，發(fā)現(xiàn)者的位置更新描述如下：

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

1.2.2 加入者數(shù)學(xué)模型

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

其中，Xp是目前發(fā)現(xiàn)者所占據(jù)的最優(yōu)位置；Xworst表示當(dāng)前全局最差的位置；A表示一個(gè)1×d的矩陣，其中每個(gè)元素隨機(jī)賦值為1或－1，并且A＋=AT(AAT)－1。

1.2.3 反哺食行為

當(dāng)意識(shí)到危險(xiǎn)時(shí)，麻雀種群會(huì)做出反捕食行為，其位置更新如下：

其中，Xbest是當(dāng)前的全局最優(yōu)位置；β是步長(zhǎng)控制參數(shù)，是服從均值為0，方差為1的正態(tài)分布的隨機(jī)數(shù)；K∈[－1,1]是一個(gè)隨機(jī)數(shù)；fg和fw分別是當(dāng)前全局最佳和最差的適應(yīng)度值；ε是一個(gè)常數(shù)，避免分母出現(xiàn)0。

2 多目標(biāo)麻雀搜索算法

為了將麻雀搜索算法應(yīng)用于多目標(biāo)優(yōu)化問題，對(duì)麻雀種群排序時(shí)借鑒NSGA-II 中的非支配排序[2]方法，以及在麻雀搜索算法中引入外部種群，用于存儲(chǔ)非支配解。

2.1 自適應(yīng)調(diào)整種群比例因子

MSSA由于缺乏待優(yōu)化問題的先驗(yàn)知識(shí)，有必要根據(jù)種群收斂狀態(tài)的反饋信息動(dòng)態(tài)調(diào)整參數(shù)。文獻(xiàn)[14]證明了以粒子對(duì)外部存檔收斂性的貢獻(xiàn)為標(biāo)準(zhǔn)反映種群收斂狀態(tài)，改進(jìn)了多目標(biāo)粒子群算法，可以提高算法性能。受此啟發(fā)，本文在MSSA 中引入收斂貢獻(xiàn)因子Q，動(dòng)態(tài)調(diào)整種群比例因子w，協(xié)調(diào)算法的全局探索能力和局部開發(fā)能力。

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

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

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

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

Q反映算法每次迭代的收斂性，當(dāng)Q較大時(shí)，算法全局搜索能力強(qiáng)，當(dāng)Q減小時(shí)，算法逐步收斂穩(wěn)定。

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

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

其中，Q∈[0,1]。當(dāng)Q較大時(shí)，說明算法處在全局探索階段，此時(shí)w增大，擴(kuò)大發(fā)現(xiàn)者比例，促進(jìn)搜索個(gè)體在更大范圍內(nèi)尋找新解；Q值較小時(shí)，w減小，擴(kuò)大加入者比例，提升算法的局部尋優(yōu)能力，有效改善了Pareto解集的質(zhì)量。

2.2 多項(xiàng)式變異算子

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

多項(xiàng)式變異算子形式如式（8）所示：

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

決定進(jìn)行變異的概率Pm如式（10）所示：

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

2.3 麻雀?jìng)€(gè)體非支配排序

與麻雀搜索算法不同，多目標(biāo)優(yōu)化算法的適應(yīng)度值是目標(biāo)向量，而不是標(biāo)量，無法通過某一函數(shù)值進(jìn)行直接比較。因此，在多目標(biāo)麻雀搜索算法中，將種群進(jìn)行非支配排序[2]以確定適應(yīng)度值大小，對(duì)麻雀種群個(gè)體進(jìn)行排序，進(jìn)而區(qū)分發(fā)現(xiàn)者和加入者。

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

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

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

（3）對(duì)于當(dāng)前集合F(1)中的個(gè)體j，考察其所支配的個(gè)體S(j)，將集合S(j)中的每個(gè)個(gè)體k的解個(gè)體數(shù)減去1。

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

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

2.4 外部存檔策略

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

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

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

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

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

①計(jì)算外部存檔種群中每個(gè)麻雀?jìng)€(gè)體的目標(biāo)函數(shù)值F(f1(x),f2(x),…,fN(x)),并找出每個(gè)目標(biāo)函數(shù)極值fimin(x)和fimax(x)。

②計(jì)算每一個(gè)麻雀?jìng)€(gè)體的擁擠度距離Dc(j)：

其中，fi(j－1)和fi(j ＋1)為麻雀?jìng)€(gè)體j相鄰的兩個(gè)個(gè)體在第i個(gè)目標(biāo)函數(shù)的適應(yīng)度值。

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

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

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

為了更好地體現(xiàn)個(gè)體的均勻分布，采用一種新的擁擠度距離計(jì)算公式，具體描述如下：

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

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

圖3 為MSSA 在測(cè)試函數(shù)ZDT2 上迭代次數(shù)為100時(shí)分別利用式（11）和式（12）對(duì)種群進(jìn)行裁剪的結(jié)果，可以看出圖（a）解分布均勻性好于圖（b）。

圖3 兩種結(jié)果對(duì)比Fig.3 Comparison of two results

2.5 MSSA算法流程

結(jié)合前面提到的策略，本文提出一種新的多目標(biāo)優(yōu)化算法——多目標(biāo)麻雀搜索算法。具體流程如下：

2.6 算法復(fù)雜度分析

假設(shè)待優(yōu)化MOP問題的目標(biāo)個(gè)數(shù)為M，麻雀種群個(gè)數(shù)為N，當(dāng)前外部存檔的個(gè)數(shù)為Ar，個(gè)體維度為n。

算法初始化的時(shí)間復(fù)雜度為O(nN)，求解目標(biāo)函數(shù)適應(yīng)度的時(shí)間復(fù)雜度為O(MN)，種群中的個(gè)體非支配排序的時(shí)間復(fù)雜度為O(MN2)；循環(huán)體內(nèi)發(fā)現(xiàn)者位置更新的時(shí)間復(fù)雜度為O(r1Nn)，其中r1為發(fā)現(xiàn)者占種群比例；多項(xiàng)式變異操作的時(shí)間復(fù)雜度為O(r3Nn)，其中r3為變異操作個(gè)體占比；加入者位置更新的時(shí)間復(fù)雜度為O((1－r1)Nn)；警戒者位置更新的時(shí)間復(fù)雜度為O(r2Nn)，其中r2為警戒者占種群比例；將非支配解集存到外部存檔，對(duì)外部存檔維護(hù)的時(shí)間復(fù)雜度為O(M(N ＋Ar)2log(N ＋Ar))，輸出最優(yōu)解的時(shí)間復(fù)雜度為O(MAr)。綜上所述，MSSA的時(shí)間復(fù)雜度為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)。從整體上看，算法的時(shí)間復(fù)雜度主要與種群規(guī)模和外部存檔規(guī)模有關(guān)。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

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

表1 算法參數(shù)設(shè)置Table 1 Algorithm parameter setting

3.2 性能指標(biāo)

為比較不同優(yōu)化算法的性能，選取兩種評(píng)價(jià)指標(biāo)來量化算法的性能。

（1）反轉(zhuǎn)迭代距離（IGD）[17]

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

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

（2）空間評(píng)價(jià)（SP）[18]

用于衡量每個(gè)解到其他相鄰解之間最小距離的標(biāo)準(zhǔn)差，SP值越小，說明解集越均勻。SP數(shù)學(xué)表達(dá)式如下所示：

3.3 標(biāo)準(zhǔn)測(cè)試函數(shù)

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

表2 標(biāo)準(zhǔn)測(cè)試函數(shù)Table 2 Standard test functions

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

各測(cè)試函數(shù)運(yùn)行20 次，平均所需時(shí)間如表3 所示?？梢钥闯?，MSSA和NSGA-II在大多數(shù)測(cè)試函數(shù)上取得了優(yōu)于對(duì)比算法的效果。在算法迭代過程中，環(huán)境是實(shí)時(shí)變化的，種群比例因子w根據(jù)算法環(huán)境變化進(jìn)行調(diào)整，達(dá)到算法參數(shù)精細(xì)化調(diào)控的目的，縮短了算法的運(yùn)行時(shí)間。

表3 運(yùn)行時(shí)間Table 3 Running time s

表4 和表5 分別列出了5 種算法在8 個(gè)測(cè)試問題上的IGD、SP 的平均值和標(biāo)準(zhǔn)差，每個(gè)結(jié)果均為同一算法在同一測(cè)試問題上獨(dú)立運(yùn)行20次的統(tǒng)計(jì)結(jié)果。采用粗體字標(biāo)出每一個(gè)測(cè)試函數(shù)的最優(yōu)IGD值和SP值。為了直觀展示各算法所得解集的收斂性和分布性，圖4 和圖5 給出了5 種算法在部分測(cè)試問題上的Pareto 前沿。f1和f2為優(yōu)化目標(biāo)函數(shù)。

表4 IGD測(cè)試結(jié)果Table 4 Test results of IGD

表5 SP測(cè)試結(jié)果Table 5 Test results of SP

圖4 ZDT3測(cè)試結(jié)果Fig.4 Test result of ZDT3

圖5 ZDT4測(cè)試結(jié)果Fig.5 Test result of ZDT4

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

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

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

表6 IGD Wilcoxon秩和檢驗(yàn)Table 6 Wilcoxon rank sum test of IGD

表7 SP Wilcoxon秩和檢驗(yàn)Table 7 Wilcoxon rank sum test of SP

3.5 盤式制動(dòng)器設(shè)計(jì)

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

最小化目標(biāo)：

為測(cè)試MSSA算法在解決實(shí)際優(yōu)化問題中的有效性，將其應(yīng)用于盤式制動(dòng)器設(shè)計(jì)問題。采用MOPSO和NSGAII作為對(duì)比算法，算法初始種群規(guī)模設(shè)定為100，最大迭代次數(shù)設(shè)定為200，其余參數(shù)設(shè)置與表1 一致。各算法獨(dú)立運(yùn)行10 次并取平均值得到的Pareto 前沿如圖6 所示。通過圖6可以看出，MSSA得到的結(jié)果是平滑的，與MOPSO和NSGA-II的結(jié)果相同甚至更好。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）之間。為了更好地驗(yàn)證MSSA 的性能，選取前文提到的空間評(píng)價(jià)SP和運(yùn)行時(shí)間進(jìn)行實(shí)驗(yàn)，如表8所示。

圖6 盤式制動(dòng)器設(shè)計(jì)測(cè)試結(jié)果Fig.6 Test result of disc brake design

表8 空間評(píng)價(jià)和運(yùn)行時(shí)間Table 8 SP and running time

4 結(jié)束語

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

未來將從兩方面做進(jìn)一步的工作：（1）是否可以從外部存檔中選取個(gè)體作為發(fā)現(xiàn)者，提升多目標(biāo)算法的收斂性；（2）利用更多的MOP測(cè)試函數(shù)對(duì)算法進(jìn)行測(cè)試。