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

關(guān)鍵詞：多目標(biāo)優(yōu)化； Pareto前沿； 麻雀搜索算法； 非支配排序； 競爭機(jī)制

中圖分類號：TP18 文獻(xiàn)標(biāo)志碼：A

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

doi：10.19734/j.issn.1001-3695.2021.12.0650

基金項目：國家重點(diǎn)研發(fā)計劃資助項目（2018YFC0808306）；河北省重點(diǎn)研發(fā)計劃資助項目（19270318D）；河北省物聯(lián)網(wǎng)監(jiān)控工程技術(shù)研究中心項目（3142018055）；青海省物聯(lián)網(wǎng)重點(diǎn)實(shí)驗室項目（2017-ZJ-Y21）

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

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 引言

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

1.2 麻雀搜索算法

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

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

其中：d表示優(yōu)化問題向量的維度；n表示麻雀的數(shù)量。所有麻雀的適應(yīng)度值可以用如下形式表示：

其中：f表示適應(yīng)度值。

在SSA中，發(fā)現(xiàn)者負(fù)責(zé)為整個種群尋找食物并為加入者提供覓食區(qū)域和方向，因此在SSA中，發(fā)現(xiàn)者擁有較大的搜索區(qū)域。根據(jù)規(guī)則，在算法的迭代過程中，發(fā)現(xiàn)者的位置更新描述如下：

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

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

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

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

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

2.1 新型非支配排序

不同于單目標(biāo)優(yōu)化算法，多目標(biāo)優(yōu)化算法的適應(yīng)度值是一個向量，而非一個標(biāo)量，對于向量的排序，不同于標(biāo)量，不可以直接比較大小。因此在多目標(biāo)優(yōu)化算法中，需要進(jìn)行非支配排序來比較適應(yīng)度值的大小。

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

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

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

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

2.2 競爭機(jī)制

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

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

2.3 正余弦策略

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

其中：a為常數(shù)；t代表當(dāng)前迭代的次數(shù)；T為最大迭代次數(shù)。

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

2.4 多項式變異

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

多項式變異的變異形式為

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

2.5 時間復(fù)雜度分析

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

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

2.6 穩(wěn)定性分析

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

從式（5）（6）可知，當(dāng)麻雀搜索算法處于全局搜索階段時，麻雀的位置是隨機(jī)進(jìn)行變化的且是離散的；當(dāng)麻雀找到最優(yōu)值時，麻雀會向著最優(yōu)值xmax靠近。跳過全局搜索階段，從局部最優(yōu)值區(qū)域開始來分析算法的穩(wěn)定性。

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

則有l(wèi)imt→∞‖x（t：x0，t0）-xmax‖≤ε，t≥t0。

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

即方程的解始終都在圓S（δ）內(nèi)。因此，圓S（δ）的半徑δ與t0無關(guān)，所以MOSSA的平衡狀態(tài)xmax是一致穩(wěn)定的。且MOSSA必然可以收斂到全局最優(yōu)值，根據(jù)式（14），MOSSA是漸進(jìn)穩(wěn)定的。此時，從S（δ）出發(fā)的點(diǎn)會在S（ε）的范圍內(nèi)，且t→∞，收斂于xe，即xmax，所以MOSSA的平衡狀態(tài)使一致漸進(jìn)穩(wěn)定的。綜上所述，MOSSA的平衡狀態(tài)xmax是一致漸進(jìn)穩(wěn)定的。

2.7 MOSSA流程

輸入：初始化種群N；最大迭代次數(shù)T；發(fā)現(xiàn)者比例ω；預(yù)警麻雀數(shù)目SD；預(yù)警值R2。

輸出：Pareto最優(yōu)前沿。

對初始解進(jìn)行非支配排序；

while（tlt;T） //t為當(dāng)前的迭代次數(shù)

對初始解進(jìn)行競爭選擇，選擇最優(yōu)和最劣個體；

for i=1：N*ω

使用式（8）更新發(fā)現(xiàn)者位置；

end for

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

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

end for

for j=1：SD

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

end for

使用式（11）對種群進(jìn)行多項式變異；

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

t=t+1

end while

輸出最優(yōu)解。

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

3 性能測試

3.1 實(shí)驗設(shè)置

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

3.2 性能指標(biāo)

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

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

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

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

3.4 實(shí)驗結(jié)果及分析

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

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

結(jié)合表3中的IGD性能統(tǒng)計可知，MOSSA在九個測試函數(shù)上取得了六個最優(yōu)的IGD均值和方差，MOABC獲得了兩個最優(yōu)值，MOEAD獲得了一個最優(yōu)值。在雙目標(biāo)測試函數(shù)中，MOSSA展現(xiàn)出了較好的尋優(yōu)能力；在多模態(tài)測試函數(shù)如ZDT4和DTLZ7上，MOSSA也表現(xiàn)出了不錯的尋優(yōu)性能。

分析可知，MOSSA在整個ZDT系列和部分DTLZ系列測試函數(shù)上具有明顯的性能優(yōu)勢，并且在雙目標(biāo)問題上的表現(xiàn)是優(yōu)于三目標(biāo)問題的，當(dāng)然，根據(jù)no free lunch定理，并不能期望算法在所有測試函數(shù)都有最好的表現(xiàn)。

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

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

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

3.5 MOSSA改進(jìn)策略有效性測試

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

［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：一種混合型多目標(biāo)螢火蟲算法 ［J］.軟件學(xué)報，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］李雅麗，王淑琴，陳倩茹，等.若干新型群智能優(yōu)化算法的對比研究 ［J］.計算機(jī)工程與應(yīng)用，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ìn)麻雀搜索算法的多閾值圖像分割 ［J］.系統(tǒng)工程與電子技術(shù)，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ìn)麻雀搜索算法求解作業(yè)車間調(diào)度問題 ［J］.計算機(jī)應(yīng)用研究，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ìn)正余弦優(yōu)化算法的多閾值圖像分割 ［J］.計算機(jī)應(yīng)用研究，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熵的多目標(biāo)粒子群優(yōu)化算法 ［J］.軟件學(xué)報，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］薛建凱.一種新型的群智能優(yōu)化技術(shù)的研究與應(yīng)用 ［D］.上海：東華大學(xué)，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］溫澤宇，謝珺，謝剛，等.基于新型擁擠度距離的多目標(biāo)麻雀搜索算法［J］.計算機(jī)工程與應(yīng)用，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.）