基于新型非支配排序的多目標麻雀優化算法

摘 要：針對麻雀搜索算法在求解多目標問題中的不足，并且在求解過程中易陷入局部最優與收斂性差的問題，提出了一種改進的多目標麻雀搜索算法。首先，引入了新型非支配排序，找到最優前沿面；其次，將多項式變異和正余弦算法融合到種群進化策略中，增強其搜索能力，通過競爭機制的種群選擇方法，降低搜索過程中局部最優粒子和全局最優粒子導致的誤差；最后，將改進算法與多種多目標算法在標準測試函數上進行對比，仿真結果表明，改進算法的收斂性與搜索能力均優于其他算法。由此說明該算法具有可靠的多目標尋優能力，能夠有效解決多目標優化問題。

關鍵詞：多目標優化； Pareto前沿； 麻雀搜索算法； 非支配排序； 競爭機制

中圖分類號：TP18 文獻標志碼：A

文章編號：1001-3695（2022）07-014-2012-08

doi：10.19734/j.issn.1001-3695.2021.12.0650

基金項目：國家重點研發計劃資助項目（2018YFC0808306）；河北省重點研發計劃資助項目（19270318D）；河北省物聯網監控工程技術研究中心項目（3142018055）；青海省物聯網重點實驗室項目（2017-ZJ-Y21）

作者簡介：武文星（1996-），男，山西呂梁人，碩士研究生，主要研究方向為算法分析與優化（457120325@qq.com）；田立勤（1970-），男，陜西定邊人，教授，博導，主要研究方向為隨機Petri網、物聯網遠程信息監控、用戶行為認證；王志剛（1993-），男，河北張家口人，博士研究生，主要研究方向為智能優化算法；張藝（1995-），女，山東威海人，碩士研究生，主要研究方向為信任評估、用戶行為認證；吳駿一（1995-），男，河北承德人，碩士研究生，主要研究方向為算法優化；桂方燚（1998-），男，安徽池州人，碩士研究生，主要研究方向為計算機視覺.

Novel multi-objective sparrow optimization algorithm with improved non-dominated sorting

Wu Wenxing¹， Tian Liqin^1，2， Wang Zhigang²， Zhang Yi¹， Wu Junyi¹， Gui Fangyi¹

（1.School of Computer，North China Institute of Science amp; Technology，Beijing 101601，China；2.School of Computer，Qinghai Normal University， Xining 810016，China）

Abstract：

Targeting to the deficiency of sparrow search algorithm solved the multi-objective problems，and the problems can easily enter the partial optimization and inferior convergence in the counting process，this paper came up with a kind of improved multi-objective sparrow search algorithm.First of all，this paper used a new-type non-dominated sorting to find the Pareto front.Next，it integrated the polynomial mutation and cosine algorithm into species evolution strategy to strengthen its searching ability.It used the species selection method of competition mechanism to decrease the differentiation caused by partial optimized particle and overall optimized particle in the searching process.Finally，this paper compared the improved algorithm and various kinds of multi-objective algorithm in standard test function.The simulation results show that，the convergence and searching ability of the improved algorithm are all superior than other algorithm.Therefore，this algorithm can effectively address the multiple target optimization problem.

Key words：

multi-objective optimization；Pareto front；sparrow search algorithm；non-dominated sorting；competition mechanism

0 引言

在解決實際問題時存在著多種挑戰，需要特定的工具來解決這些問題，現實問題中，多個目標尋優是最具挑戰性的問題之一，稱之為多目標問題。為了解決這個問題，需要使用多目標優化器，目前主要有先驗和后驗^［1］兩種處理多個目標的方法。前一類優化器將多目標問題的目標與一組權值結合成一個單目標，該權值定義了每個目標的多樣性，并使用一個單目標優化器對其進行優化。對于后驗的方法來說，后驗方法保持了多目標問題的多樣性^［1］，與單目標問題不同的是，當選擇多個目標作為優化過程的目標時就不存在單一的解，在這種情況下，一組解決方案代表了目標之間的各種權衡，包括多目標最優解集。

1984年，Schaffer提出了使用隨機優化技術的多目標優化概念后^［2］，大量的多目標進化算法相繼被提出，如強度Pareto優化算法 （SPEA）^［3］、非支配排序遺傳算法（NSGA）^［4］及其改進后的版本（NSGA-Ⅱ）^［5］、多目標粒子群算法（MOPSO）^［6］、基于分解的多目標進化算法（MOEAD）^［7］、多目標灰狼優化算法（MOGWO）^［8］、多目標螢火蟲算法^［9］等，這些算法可以較好地逼近Pareto最優解。然而，no free lunch^［10］定理邏輯上證明了不存在解決所有優化問題的優化技術。根據這個定理，一個算法在一類問題上的優越性無法保證在其他問題上同樣的優越性，這個定理是許多文獻工作的基礎，并允許算法工作者在面對新問題的時候提出新的算法。

對于傳統的搜索算法，粒子群算法在迭代過程中存在著容易早熟、維度災難、沒有跳出局部最優值能力的問題；蟻群算法的主要應用于路徑規劃方面，并且存在著依賴參數，搜索速度慢的問題；差分進化算法是在遺傳算法的基礎上改進了其變異的過程，可以更好地逼近最優值，但是也存在著一些問題，比如在迭代過程中不記錄最優值，很容易陷入局部最優值，并且存在著停滯現象，在迭代過程中會收斂停止。對于一些新型算法，如灰狼優化算法，存在著過程復雜、前期搜索能力強而在后期容易陷入最優停滯問題；鯨魚優化算法存在著參數過多、種群多樣性不足的問題。當從單目標算法改為多目標算法時，傳統的改進方法存在著一些問題，例如需要維護存儲Pareto最優解集的檔案，需要使用合適的方法找到算法迭代過程中產生的全局最優解和局部最優解，并且利用這兩個解來引導其他粒子的移動，同時也需要平衡算法的收斂速度及其收斂性^［9］。

麻雀搜索算法（SSA）^［11］是2020年提出的一種新型智能優化算法，具有較強的局部搜索能力，文獻［12］證明了SSA在收斂速度和收斂穩定性方面有著較強的性能。基于SSA研究人員進行了許多的應用，Zhu等人^［13］使用SSA解決了質子交換膜燃料電池堆模型辨識問題；Liu等人^［14］將SSA應用于無人機航路規劃問題；呂鑫等人^［15］將SSA應用于圖像分割問題；劉麗娜等人^［16］將SSA應用于求解作業車間調度問題，均取得了較好的實驗效果。但上述方法均停留在單目標問題的優化上，對于麻雀搜索算法優化多目標問題的研究尚少。

針對以上問題，麻雀搜索算法具有結構簡單、優化參數少、搜索能力更強的優勢，被廣泛應用于工程問題的求解優化；并且相較于粒子群算法、差分進化算法等傳統算法，灰狼優化算法、鯨魚優化算法、螢火蟲算法等新型算法，在對單峰函數、多峰函數的求解測試中，麻雀搜索算法都有不錯的表現。本文在麻雀搜索的基礎上引入了新型的非支配排序算法，有效降低了原有非支配排序的時間復雜度。由于麻雀位置更新的過程中嚴重依賴于全局最優位置和當前最優位置的問題，借鑒了CMOPSO^［17］中的競爭機制，使得麻雀可以找到離自己最近的最優位置；為了提高麻雀的全局搜索能力，還引入了正余弦策略^［18］和多項式變異算子^［19］，在算法陷入停滯時，可以有效地引導算法走出局部最優值。采用多種測試函數對改進后的算法進行仿真實驗，并與多種多目標算法進行對比表明，本文提出的改進SSA具有較好的穩定性和收斂性。

1 相關工作

1.1 多目標優化問題

多目標優化問題是一種對于最小化無約束連續多目標問題的優化^［20］（在最優化計算中，最大化問題和最小化問題的求解是相似的，是對偶問題，在本文中，所指所有問題均為最小化問題），定義如下：

其中：x=［x1，x2，…，xD］T∈S；D代表決策向量的個數；S是D維決策空間；fi是優化函數，也可以表示為適應度值，將決策空間映射到目標空間；M代表目標函數的個數。

定義1 Pareto占優。對于向量x¹=（x¹1，x¹2，…，x¹n）和x²=（x²1，x²2，…，x²n），稱x¹支配x²，或稱x²被x¹支配，記做x¹x²，當且僅當：

定義2 Pareto最優解。如果一個解不被種群中其他任何解支配，則該解被稱為Pareto最優解或非支配解。

定義3 Pareto最優解集。算法所求得的所有解的集合被稱為Pareto最優解集或Pareto前沿。

1.2 麻雀搜索算法

SSA算法是2020年由Xue等人從麻雀覓食行為和預警行為受到啟發而提出的一種新型群體智能優化算法^［21］。在算法中，整個麻雀群體可抽象為加入者和發現者兩個群體，并定義了一種用于預警的麻雀。發現者通常擁有較高的能源儲備，并且在麻雀群體中負責搜索到擁有豐富食物的區域，為所有加入者提供覓食的區域和方向；加入者總是能搜索到提供最好食物的發現者，并在其周圍進行覓食，同時，一部分加入者會監視發現者以便于進行食物爭奪或在其周圍覓食。整個種群面臨捕食者的威脅或者意識到危險時會立即進行反捕食行為^［20］。

在模擬實驗中，由n只麻雀組成的種群可以表示為

其中：d表示優化問題向量的維度；n表示麻雀的數量。所有麻雀的適應度值可以用如下形式表示：

其中：f表示適應度值。

在SSA中，發現者負責為整個種群尋找食物并為加入者提供覓食區域和方向，因此在SSA中，發現者擁有較大的搜索區域。根據規則，在算法的迭代過程中，發現者的位置更新描述如下：

其中：t代表當前迭代次數；T表示最大的迭代次數；Xi，j表示第i只麻雀在第j維中的位置信息。α∈（0，1］是隨機數。R2（R2∈［0，1］）和ST（ST∈［0.5，1］）分別表示預警值和安全值；Q是服從正態分布的隨機數；L是一個1×d的矩陣，矩陣中每個元素都是1。當R2lt;ST時，意味著種群處于安全中，即周圍沒有捕食者的存在，發現者可以進行更加廣泛的搜索，找到更為合適的覓食場所；當R2≥ST時，群體發現捕食者并鳴叫發出警報，種群立刻停止覓食，作出反捕食行為，迅速向安全區靠攏。

在麻雀種群中，除去發現者剩下的即為加入者，加入者會跟隨發現者，同時也會監視著發現者，一旦發現者找到更好的覓食位置，它們會立刻離開現在的位置進行食物的爭奪。加入者的位置更新描述如下：

其中：Xp是發現者目前占據的最好的位置；Xworst代表全局最差的位置；A表示一個1×d的矩陣，矩陣中的元素為-1或1，并且A+=AT（AAT）^-1。當igt;n/2時，表明適應度低的加入者處于饑餓狀態，沒有食物，為獲得更高的能量，此時需要飛到其他地方覓食。在模擬實驗中，假設意識到危險的麻雀數量占整個種群的10%～20%，其初始位置是在種群中隨機生成的，其數學表達式如下：

其中：Xbest是當前的全局最優位置；β的作用是控制步長，服從均值為0、方差為1的正態分布；K是-1～1的一個隨機數；fi則是當前個體的適應度值；fg代表當前全局最優的適應度值；fw代表全局最差的適應度值；ε是一個非常小的常數，目的是為了防止分母為零。當figt;fg時，代表此時麻雀處于種群中間，當意識到捕食者的存在時，會靠近其他麻雀來避免捕食者的攻擊；當fi=fg時，此時麻雀處于種群的邊緣，極易受到捕食者的攻擊。

2 多目標麻雀搜索算法（MOSSA）

2.1 新型非支配排序

不同于單目標優化算法，多目標優化算法的適應度值是一個向量，而非一個標量，對于向量的排序，不同于標量，不可以直接比較大小。因此在多目標優化算法中，需要進行非支配排序來比較適應度值的大小。

非支配排序是計算密集型的，當總體大小增加時，計算量會大幅增加。為了解決這一問題，文獻［22］提出了一種非支配排序的思想應用于多目標優化算法中，并在遺傳算法中實現，其時間復雜度為O（MN³），空間復雜度為O（N），其中M為目標的個數，N為解的個數。文獻［6］提出了一種時間復雜度更低的非支配排序算法，被稱為快速非支配排序，其時間復雜度為O（MN²），但是需要更大的空間來進行存儲，所以空間復雜度增加到了O（N²）。文獻［23］提出了兩種改進的非支配排序方法，即攀登排序和演算排序。

在麻雀搜索算法，對于加入者和意識到危險的麻雀，對于其位置更新，需要找到種群的全局最優位置和全局最劣的位置，來確定麻雀個體的新位置。受文獻［24］的啟發，本文引入了一種新型的非支配排序方法可以提高算法的性能。對于現有的非支配排序方法，如果想確定某個解所屬的Pareto前沿，需要與現有的所有解進行比較，從而確定解所在的前沿。本文所引入的新型非支配排序方法則只需要與現有的已經分配到的前沿的解進行比較。

對于極小值的求解問題，該算法首先根據第一個目標值對所有解進行升序排列，直到所有個體被分類為止，對于這個排序總體P，如果ilt;j，則解pi永遠不會被解pj所支配，因為pi中至少存在一個目標值小于pj中的目標值。在進行排序之后，開始對排序后的種群P中的前沿逐個分配解，從第一個開始，到最后一個結束。如果解分配到某一個前沿，那么它一定不會被它后面的解所支配，也至少被一個前面的前沿解所支配，所以，將某個解與那些已經分配前沿的解進行比較，即可確定該解所在的前沿。

對于雙目標的優化問題，此排序方法會有更好的效果，根據上述可知，分配到前面的解是按照第一個目標的升序進行排序的，這就意味著第二個目標值是按照降序排列的，因為這些解彼此之間是非支配的。那么可以推斷出，如果一個即將要分配的解pj是被支配的解，那么它會被前面的最后一個解所支配，因為最后一個解在第二個目標中的值最小。所以，對于雙目標優化問題，只需要將每一個解與最后一個解進行比較即可確定出一個解所在的前沿數。

2.2 競爭機制

在麻雀搜索的過程中，跟隨者和意識到危險的麻雀在更新位置時會嚴重依賴于全局最優值和局部最優值，所以本文引入了一種基于競爭機制的全局最優粒子選擇法。在該策略中，位置較好的麻雀之間進行兩兩隨機競爭。優勝的麻雀來引導其他麻雀的位置。

基于競爭機制的學習策略由精英粒子選擇、成對競爭和粒子學習三部分組成。精英粒子的作用是用來提供候選粒子用于兩兩競爭，以競爭最佳粒子，引導種群的更新。精英粒子的產生過程主要是：首先對種群進行非支配排序，得到Pareto前沿F1，F2，…，Fn，其中，n為前沿的最大索引，然后根據前沿指數和各粒子的擁擠距離從中選擇k個粒子作為精英粒子。精英粒子集建立后，其中的粒子進行兩兩競爭，獲勝者將引導當前粒子的運動方向。對于每次競爭，給定集合中的一個粒子P，從精英粒子群中抽出兩個粒子a和b，分別計算a、b和P之間的夾角，夾角角度小的粒子贏得競爭，使得粒子P向著更接近其收斂方向的精英粒子學習。圖1給出了兩兩競爭之間的圖例。一旦確認優勝者，就可以通過學習優勝者來更新麻雀的位置。

2.3 正余弦策略

由發現者的位置更新公式（式（5））可知，第t+1只麻雀的位置會根據第t只麻雀的位置進行更新。在此過程中并沒有考慮位置x^t+1是否優于位置xt，這種單方向的位置更新機制會使得麻雀個體之間缺乏交流，信息利用率較低，而發現者在整個種群中負責發現最佳的覓食位置，為了進一步加強發現者的探索和開發能力，本文受文獻［16］的啟發，引入了正余弦策略。正余弦算法的算法方程為

其中：a為常數；t代表當前迭代的次數；T為最大迭代次數。

正余弦策略的引入可以有效地指導麻雀更新位置，無論是正弦策略或是余弦策略，麻雀個體都可以與食物的位置進行交互；另一方面，控制參數r1可以有效地平衡算法全局搜索能力和局部搜索能力；在算法初期，r1的值較大，算法具有較強的全局搜索能力，算法后期，r1的值逐漸減小，算法的局部搜索能力被增強。正余弦的交替使用可以很好地平衡算法的全局和局部搜索能力，促進算法的優化。

2.4 多項式變異

多項式變異的思想最早用于NSGA^［4］、NSGA-Ⅱ^［5］的早期版本和DEMB項目中，多項式變異的思想如圖2所示，對于決策變量xk，當xk陷入局部最優值時候對其進行擾動，新的值會在圖中的區域a和b生成。對于任意一個在決策變量區間［lk，uk］的變量xk，每個決策變量都有一個被擾動的概率Pm，并且對每一個決策變量繪制一個隨機值u，u是（0，1］的隨機數，如果u≤Pm，定義σ1=（xk-lk）/（uk-lk），σ2=（uk-xk）/（uk-lk），定義變量xk與改變后的值x′k的差異為δ，δ計算方法如式（11）所示。此時，如果u≤0.5，則取區域a的值，反之，則取區域b的值，值的計算方法如式（10）所示。

多項式變異的變異形式為

其中：ηm是分布指數，ηm越大，變異產生的個體就越接近父代，經過多次實驗，本文中ηm設置為20，這樣可以使得算法擁有跳出局部最優值的能力，且在算法迭代過程中不會因為不利變異而使得算法遠離全局最優值；lk代表位置下限，uk代表位置上限。

2.5 時間復雜度分析

本文使用M代表目標的個數，N代表種群大小，n代表個體的維度。在標準的SSA中，發現者位置更新需要的時間復雜度為O（r1Nn），其中，r1為發現者的比例；加入者的時間復雜度為O（（1-r1）Nn）；警戒者的時間復雜度為O（r2Nn），其中r2為警戒者的比例。本文引入了新型的非支配排序，新型的非支配排序的時間復雜度為O（MNN），擁擠度距離評估的時間復雜度為O（N²），進行多項式變異需要的時間復雜度為O（Nn），引入競爭機制的時間復雜度為O（Nn）。

綜上所述，本文提出算法MOSSA的時間復雜度為O（r1Nn）+O（（1-r1）Nn）+O（r2Nn）+O（MNN）+O（N²）+O（Nn）+O（Nn）。總體來看，算法時間復雜度的主要影響因素在于非支配排序的速度。

2.6 穩定性分析

設MOSSA的初始解在圓心為xmax、半徑為δ的圓S（δ）中，可以表示為‖x0-xmax‖≤δ，如圖3所示，圓S（ε）與f（x）相交于x3、x4，最優區域為Dmax，x1、x2為兩邊的點。

從式（5）（6）可知，當麻雀搜索算法處于全局搜索階段時，麻雀的位置是隨機進行變化的且是離散的；當麻雀找到最優值時，麻雀會向著最優值xmax靠近。跳過全局搜索階段，從局部最優值區域開始來分析算法的穩定性。

由MOSSA的收斂性可知當xi位于Dmax區域時，xi會向著xmax靠近且不會遠離，因此只要方程的初始解x（t0；x0，t0）在區域Dmax中，即圓S（δ）與目標函數相交的區域包含于Dmax，方程的解x（t；x0，t0）就會向著xmax靠近，公式表達為

則有limt→∞‖x（t：x0，t0）-xmax‖≤ε，t≥t0。

解x（t；x0，t0）在t→∞時，總是位于圓心為xmax、半徑為ε的圓S（ε）中，當Dmax滿足式（12），MOSSA的平衡狀態xmax在李雅普諾夫意義下是穩定的。所以，對于任意實數εgt;0，總存在滿足式（12）的實數δ，使得滿足‖x0-xmax‖≤δ的任意x0出發的運動都滿足

即方程的解始終都在圓S（δ）內。因此，圓S（δ）的半徑δ與t0無關，所以MOSSA的平衡狀態xmax是一致穩定的。且MOSSA必然可以收斂到全局最優值，根據式（14），MOSSA是漸進穩定的。此時，從S（δ）出發的點會在S（ε）的范圍內，且t→∞，收斂于xe，即xmax，所以MOSSA的平衡狀態使一致漸進穩定的。綜上所述，MOSSA的平衡狀態xmax是一致漸進穩定的。

2.7 MOSSA流程

輸入：初始化種群N；最大迭代次數T；發現者比例ω；預警麻雀數目SD；預警值R2。

輸出：Pareto最優前沿。

對初始解進行非支配排序；

while（tlt;T） //t為當前的迭代次數

對初始解進行競爭選擇，選擇最優和最劣個體；

for i=1：N*ω

使用式（8）更新發現者位置；

end for

for i=（N*w+1）：N

使用式（6）更新追隨者位置；

end for

for j=1：SD

使用式（7）更新警戒者位置；

end for

使用式（11）對種群進行多項式變異；

獲取更新后麻雀的非支配解；

t=t+1

end while

輸出最優解。

相比于原始的麻雀搜索算法，MOSSA主要做了兩方面的改進：a）將麻雀搜索算法從單目標改為了多目標算法，具體的方法是引入了新型的非支配排序方法，可以使得原始的麻雀搜索算法從搜索單一的最優點變為搜索Pareto最優前沿面，而且由于麻雀的位置更新嚴重依賴于局部最優值和全局最優值，所以算法中引入了競爭機制，使得麻雀個體在更新過程中可以選擇離自己最近的點來更新位置；b）對麻雀搜索算法本身的改進，麻雀搜索算法擁有強大的搜索能力，這種能力帶來的優點和缺點是非常明顯的，優點在于容易找到最優點，但是也容易陷入到局部最優值，于是本文引入了正余弦策略和多項式變異，正余弦策略的引入主要是為了平衡原有算法在迭代過程中的全局搜索能力和局部搜索能力。在迭代的前期，算法擁有較高的全局搜索能力，而在算法后期，算法擁有較高的局部搜索能力，而多項式變異的引入是為了使算法在陷入局部最優值的時候將麻雀的位置重新打散，使得麻雀重新進行尋優。特別地，如果變異是針對全體種群的，那么將會產生不利變異，不但不會提升尋優的性能，反而會對算法的運行產生不利的影響，通過調整ηm的值可以使得算法在產生變異的同時不會對算法的尋優造成影響。

3 性能測試

3.1 實驗設置

為了測試MOSSA的算法性能，本文選取MOPSO^［6］、MOGWO^［8］、NSGA-Ⅱ^［5］、MOEA/D^［7］、MOABC^［25］、DGEA^［26］算法作為對比算法。算法參數設置如下：種群規模N=200，最大迭代次數T=10 000。各算法的主要參數設置如表1所示。采用的實驗環境為Windows 10，64位操作系統，處理器為Intel Core^TM i5-10600KF CPU @ 4.10 GHz，算法基于PlatEMO^［27］平臺。

3.2 性能指標

反轉迭代距離（inverted generational distance，IGD）是一個綜合性的評價指標，用于均衡真實Pareto前沿與算法所求得的個體集合之間的最小距離。IGD值越小，說明算法收斂性和分布性越好，越接近真實的Pareto前沿。其表達式如下：

其中：P是真實的Pareto前沿；Q為算法獲取的真Pareto最優解集；d（v，Q）為P中個體v到種群Q的最小歐氏距離；|P|為分布在真實Pareto面上的解集的個數。

3.3 標準測試函數

為了驗證所提算法的有效性，本文選取了九種具有代表性的多目標優化問題來考察算法的性能，驗證算法在不同多目標問題下的性能。這些測試函數分別是：ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ3、DTLZ5、ZDT6、DTLZ7，其中，四個DTLZ問題為三目標優化問題，五個ZDT問題為雙目標優化問題。測試函數如表2所示，其箱線圖如圖4所示。

3.4 實驗結果及分析

根據圖4，MOSSA的箱線圖明顯比其他六種算法都要窄，表明MOSSA在收斂于真Pareto最優前沿方面具有穩定性。最差的是MOPSO，從圖4中可以看出，該算法收斂性較差，且不穩定，得到的Pareto前沿也更分散。各算法在ZDT1和ZDT3上得到的Pareto最優解如圖5、6所示。從圖中可以看出，MOSSA的收斂性和覆蓋率是要優于其他算法。

將MOSSA與其他算法進行了對比， 將IGD性能指標結果進行了Wilcoxon秩和檢驗實驗，結果如表3、4所示。按照顯著性水平，“+”“-”“=”分別代表MOSSA的性能指標劣于、優于、近似于其他對比算法。從表3可以看出，MOSSA的性能在大多數測試指標上是優于其他對比算法的，只有在個別函數上近似于或劣于NSGA-Ⅱ和MOABC算法。表4將MOSSA與其他算法進行了對比，將IGD性能指標結果進行了Wilcoxon秩和檢驗實驗。

結合表3中的IGD性能統計可知，MOSSA在九個測試函數上取得了六個最優的IGD均值和方差，MOABC獲得了兩個最優值，MOEAD獲得了一個最優值。在雙目標測試函數中，MOSSA展現出了較好的尋優能力；在多模態測試函數如ZDT4和DTLZ7上，MOSSA也表現出了不錯的尋優性能。

分析可知，MOSSA在整個ZDT系列和部分DTLZ系列測試函數上具有明顯的性能優勢，并且在雙目標問題上的表現是優于三目標問題的，當然，根據no free lunch定理，并不能期望算法在所有測試函數都有最好的表現。

在DTLZ系列測試函數中，MOABC在DTLZ5和DTLZ7上表現出了較好的尋優性能，NSGA在DTLZ5上表現僅次于MOABC，MOPSO和MOGWO均未表現出較好的性能，MOSSA在DTLZ5和DTLZ1函數中表現出了次優的性能，在DTLZ6上均表現出較好的性能，明顯優于其他函數。

為了更加直觀地展現算法的收斂性和均勻性，圖5、6給出了本文算法和對比算法在ZDT1、ZDT3、DTLZ6和DTLZ7上的Pareto前端。在圖5中，對于雙目標測試函數，NSGA-Ⅱ、MOSSA和MOABC均能表現出較好的收斂性和均勻性，MOPSO和DGEA擁有較好的均勻性，但沒有收斂到真實的Pareto前沿，MOEAD的收斂性略強于MOPSO，而均勻性較差，對于三目標測試函數DTLZ6和DTLZ7，MOPSO、MOEAD和DGEA的均勻性和收斂性都表現較差，都無法正確的收斂到真實的Pareto前沿，NSGA-Ⅱ、MOGWO、MOABC和本文算法均表現較好。對于三目標的多模態不連續DTLZ7函數，MOEAD雖然收斂到了真實的Pareto前沿，但是分布不均勻，MOPSO都不僅無法收斂到真實的Pareto前沿，甚至無法跳出局部最優值，本文算法雖然也未能均勻收斂到真實的Pareto前沿，但仍表現出較好的收斂性。

實驗結果表明，MOSSA能夠在多目標測試函數上提供有競爭力的結果。IGD的統計結果表明了MOSSA的收斂能力，MOSSA的高收斂性來源于算法中引入的競爭機制，可以讓個體選擇離自己最近的發現者來更新位置，使得粒子可以快速的引導到最佳的位置；此外，本文算法所引入的正余弦策略使得MOSSA在搜索過程中可以擁有較好的搜索能力，尤其是在算法陷入局部最優值時。從實驗結果可以看出，MOSSA在大多數情況下均優于MOPSO，由于MOPSO在每次迭代過程中更新Gbest，所以在每次迭代中，粒子會被相同（或者相似）的粒子所吸引。而MOSSA中的粒子會根據正余弦策略改進后的發現者位置來更新自己的位置，使得算法的搜索能力更強。結果表明，MOEA/D在非凸的Pareto最優前沿問題的搜索能力不強，對于線性前沿問題的搜索性較強，而MOSSA在非凸問題上明顯更具優勢，比其他六種算法的效果要強。

3.5 MOSSA改進策略有效性測試

由于原本的SSA沒有多目標優化的能力，所以本文引入的非支配排序和競爭機制的目的是為了賦予SSA多目標搜索的能力，SSA中，加入者和警戒者在進行位置更新的時候，需要根據全局最優位置和局部最優位置來確定麻雀下一次飛行的位置，非支配排序引入的目的是為了找到全局最優位置，而競爭機制的引入是為了找到麻雀的局部最優位置，使得麻雀可以飛行到離自己最近的位置，所以本文中的消融實驗將不會對引入的非支配排序和競爭機制進行消融實驗。

為了驗證MOSSA中改進競爭機制、引入正余弦策略和多項式變異的有效性，本文將完全不進行任何引入的算法記為SSA1，將只引入正余弦策略的算法記為SSA2，將只引入多項式變異的算法記為SSA3，將文獻［28］的改進算法記為MSSA，參數設置與3.1節中的參數設置相同，利用上述測試函數中的ZDT1，ZDT2，DTLZ2，DTLZ6，DTLZ7進行測試，測試結果如表5所示，對比圖像如圖7所示。

由表5、圖7可以看出，SSA2、SSA3與MOSSA均優于原始的SSA1算法，這表明本文引入的正余弦策略與多項式變異都可以增加算法的收斂精度和穩定性；對于非連續函數ZDT3，從圖7可以得知，SSA2和MOSSA均可以跳出局部最優值，證明引入正余弦策略可以避免函數求解時陷入局部最優值，而MOSSA的分布更為均勻，證明了引入多項式變異的有效性，在算法前期，多項式變異可以保證粒子搜索過程中的全局性，在算法后期，可以加速粒子向最優解進行收斂。通過與MSSA的算法對比可以得知，本文MOSSA在多種測試函數上均優于該算法，通過圖7的比較可以得知，MSSA有一定的緩解早熟的能力，但是在迭代后期，仍舊容易陷入局部最優值，并且在多模態函數上的表現欠佳，其優勢在于算法的運行時間，30次迭代實驗中，MSSA在五種測試函數中的平均用時為0.36 s，而本文MOSSA的平均用時為0.52 s。

使用以上兩種改進策略融合的MOSSA的收斂精度和均勻性都高于使用單一改進策略的SSA2和SSA3算法和原算法。因此可以得出，使用組合的改進策略可以有效地提高算法的尋優能力。

4 結束語

本文提出了一種新的多目標進化算法MOSSA。在SSA中引入了競爭機制和新型非支配排序，使得其能夠進行多目標優化。競爭機制是一種選擇機制，用于選擇離粒子最近的Pareto前沿值進行位置計算；新型非支配排序是一種排序機制，使得MOSSA能快速得到Pareto最優前沿，提高算法的運行速度；同時引入了正余弦策略和多項式變異，使得算法擁有更好的全局搜索能力。將提出算法與六種多目標優化算法進行對比，結果表明，MOSSA擁有較好的尋優能力。首先，采用IGD性能指標定量地證明了MOSSA擁有較好的收斂性。另一方面，所得到的Pareto最優解和Pareto前沿形狀表明，算法在定性和定量上都有較好的覆蓋。綜上，該算法在多目標問題上具有顯著的優點，具有一定的參考價值。在未來的研究中，計劃將該算法應用到無人機路徑規劃問題中，同時將算法進行擴展使得其可以解決多種實際問題。

參考文獻：

［1］

Branke J，Kauler T，Schmeck H.Guidance in evolutionary multi-objective optimization ［J］.Advances in Engineering Software，2001，32（6）：499-507.

［2］Carlos A，Coello C.Evolutionary multi-objective optimization：a historical view of the field ［J］.IEEE Computational Intelligence Magazine，2006，1（1）：28-36.

［3］Adham A M，Mohd-Ghazal N，Ahmad R.Performance optimization of a microchannel heat sink using the improved strength pareto evolutio-nary algorithm （SPEA2） ［J］.Journal of Engineering Thermophy-sics，2015，24（1）：86-100.

［4］Srinivas N，Deb K.Multi-objective optimization using nondominated sorting in genetic algorithms［J］.Evolutionary Computation，1994，2（3）：221-248.

［5］Deb K，Pratap A，Agarwal S，et al. A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ［J］.IEEE Trans on Evolutionary Computation，2002，6（2）：182-197.

［6］Coello C，Lechuga M S.MOPSO：a proposal for multiple objective particle swarm optimization ［C］//Proc of IEEE Congress on Evolutio-nary Computation.Piscataway，NJ：IEEE Press，2002：1051-1056.

［7］Zhang Qingfu，Li Hui.MOEA/D：a multi-objective evolutionary algorithm based on decomposition ［J］.IEEE Trans on Evolutionary Computation，2007，11（6）：712-731.

［8］Mirjalili S，Saremi S，Mirjalili S M，et al. Multi-objective grey wolf optimizer：a novel algorithm for multicriterion optimization ［J］.Expert Systems with Applications，2016，47（1）：106-119.

［9］謝承旺，肖馳，丁立新，等.HMOFA：一種混合型多目標螢火蟲算法 ［J］.軟件學報，2018，29（4）：1143-1162.（Xie Chengwang，Xiao Chi，Ding Lixin，et al. HMOFA：a hybrid multiobjective firefly algorithm ［J］.Journal of Software，2018，29（4）：1143-1162.）

［10］Wolpert D H，Macready W G.Remarks on a recent paper on the “no free lunch” theorems ［J］.IEEE Trans on Evolutionary Computation，2001，5（3）：295-296.

［11］Xue Jiankai，Shen Bo.A novel swarm intelligence optimization approach：sparrow search algorithm ［J］.Systems Science amp; Control Engineering，2020，8（1）：22-34.

［12］李雅麗，王淑琴，陳倩茹，等.若干新型群智能優化算法的對比研究 ［J］.計算機工程與應用，2020，56（22）：1-12.（Li Yali，Wang Shuqin，Chen Qianru，et al.Comparative study of several new swarm intelligence optimization algorithms ［J］.Computer Engineering and Applications，2020，56（22）：1-12.）

［13］Zhu Yanglong，Yousefi N.Optimal parameter identification of PEMFC stacks using adaptive sparrow search algorithm ［J］.International Journal of Hydrogen Energy，2021，46（14）：9541-9552.

［14］Liu Guiyun，Shu Cong，Liang Zhongwei，et al. A modified sparrow search algorithm with application in 3D route planning for UAV ［J］.Sensors，2021，21（4）：1224.

［15］呂鑫，慕曉冬，張鈞.基于改進麻雀搜索算法的多閾值圖像分割 ［J］.系統工程與電子技術，2021，43（2）：318-327.（Lyu Xin，Mu Xiaodong，Zhang Jun.Multi-threshold image segmentation based on improved sparrow search algorithm ［J］.Systems Engineering and Electronics，2021，43（2）：318-327.）

［16］劉麗娜，南新元，石躍飛.改進麻雀搜索算法求解作業車間調度問題 ［J］.計算機應用研究，2021，38（12）：3634-3639.（Liu Lina，Nan Xinyuan，Shi Yuefei.Improved sparrow search algorithm for solving Job-Shop scheduling problem ［J］.Application Research of Computers，2021，38（12）：3634-3639.）

［17］Zhang Xiangyi，Zheng Xiutao，Cheng Ran，et al. A competitive me-chanism based multi-objective particle swarm optimizer with fast convergence ［J］.Information Sciences，2018，427（1）：63-76.

［18］郎春博，賈鶴鳴，邢致愷，等.基于改進正余弦優化算法的多閾值圖像分割 ［J］.計算機應用研究，2020，37（4）：1215-1220.（Lang Chunbo，Jia Heming，Xing Zhikai，et al. Multi-threshold image segmentation based on improved sine cosine optimization algorithm ［J］.Application Research of Computers，2020，37（4）：1215-1220.）

［19］Deb K，Goyal M.A combined genetic adaptive search （GeneAS） for engineering design ［J］.Computer Sciences and Informatics，1996，26（4）：30-45.

［20］胡旺，Yen G G，張鑫.基于Pareto熵的多目標粒子群優化算法 ［J］.軟件學報，2014，25（5）：1025-1050.（Hu Wang，Yen G G，Zhang Xin.Multi-objective particle swarm optimization based on pareto entropy ［J］.Journal of Software，2014，25（5）：1025-1050.）

［21］薛建凱.一種新型的群智能優化技術的研究與應用 ［D］.上海：東華大學，2020.（Xue Jiankai.Research and application of a new swarm intelligence optimization technology ［D］.Shanghai：Donghua University，2020.）

［22］Jensen M T.Reducing the run-time complexity of multi-objective EAs：the NSGA-Ⅱ and other algorithms ［J］.IEEE Trans on Evolutionary Computation，2003，7（5）：503-515.

［23］McClymont K，Keedwell E.Deductive sort and climbing sort：new methods for non-dominated sorting［J］.Evolutionary Computation，2012，20（1）：1-26.

［24］Zhang Xingyi，Tian Ye，Cheng Ran，et al.An efficient approach to nondominated sorting for evolutionary multi-objective optimization［J］.IEEE Trans on Evolutionary Computation，2015，19（2）：201-213.

［25］Zhang Liming，Wang Saisai，Zhang Kai，et al. Cooperative artificial bee colony algorithm with multiple populations for interval multi-objective optimization problems［J］.IEEE Trans on Fuzzy Systems，2018，27（5）：1052-1065.

［26］He Cheng，Cheng Ran，Yazdani D.Adaptive offspring generation for evolutionary large-scale multi-objective optimization［J］.IEEE Trans on Systems，Man，and Cybernetics：Systems，2021，52（2）：786-798.

［27］Tian Ye，Cheng Ran，Zhang Xingyi，et al. PlatEMO：a MATLAB platform for evolutionary multi-objective optimization educational forum［J］.IEEE Computational Intelligence Magazine，2017，12（4）：73-87.

［28］溫澤宇，謝珺，謝剛，等.基于新型擁擠度距離的多目標麻雀搜索算法［J］.計算機工程與應用，2021，57（22）：102-109.（Wen Zeyu，Xie Jun，Xie Gang，et al. Multi-objective sparrow search algorithm based on new crowding distance［J］.Computer Engineering and Applications，2021，57（22）：102-109.）