周 寧，張嵩霖，張 晨

(蘭州交通大學(xué)電子與信息工程學(xué)院 蘭州 730070)

全局尋優(yōu)問題在工程[1-2]、金融[3]、自然科學(xué)等領(lǐng)域中廣泛存在，求解全局尋優(yōu)問題有很強的理論與現(xiàn)實意義?，F(xiàn)階段對全局尋優(yōu)問題求解的重要途徑是使用群體智能算法，該算法是受自然界生物的行為模式啟發(fā)后設(shè)計的一類算法，旨在以更快的速度與更高的精度求解復(fù)雜的全局尋優(yōu)問題。近幾十年來，群體智能算法發(fā)展迅速，如蟻群算法[4-6]、粒子群優(yōu)化算法[7]、蝙蝠算法[8]、灰狼算法[9]、鯨魚算法[10]、麻雀搜索算法(sparrow search algorithm,SSA)[11]等。其中，麻雀搜索算法有收斂速度快、收斂精度高、魯棒性強等優(yōu)點[12]，但同其他群體智能算法一樣，它在迭代后期依然有種群多樣性減少，容易陷入局部最優(yōu)的問題。在提高優(yōu)化算法全局尋優(yōu)能力方面，文獻[13]將遺傳算法進行優(yōu)化，通過在每一代中引入一個較低維度的活動子空間，使算法以較低的成本保證種群的多樣性，提高算法的全局尋優(yōu)能力。文獻[14]將牛頓方法與非單調(diào)線搜索方法進行結(jié)合，當(dāng)牛頓方法尋優(yōu)結(jié)果不再下降時，使用非單調(diào)線搜索幫助尋優(yōu)，提高算法的全局尋優(yōu)能力。文獻[15]在遺傳算法的框架下提出了新的算法，利用歷史信息幫助算法自適應(yīng)地選擇局部搜索與全局搜索，提出了新的“誘導(dǎo)”算子，提高了算法的種群多樣性，幫助算法收斂至全局最優(yōu)。

對于麻雀搜索算法的改進是近期群體智能算法研究的熱點之一。為了解決麻雀搜索算法中存在的問題，文獻[16]引入混沌理論，豐富了種群的多樣性，對迭代結(jié)果進行混沌擾動，增加算法跳出局部最優(yōu)的能力；文獻[17]結(jié)合鳥群算法，對麻雀搜索算法的位置更新公式進行改進，提高了算法的穩(wěn)定性；文獻[18]使用混沌理論對麻雀搜索算法進行初始化過程的優(yōu)化，并且使用危險轉(zhuǎn)移策略與動態(tài)演化策略提高了算法的全局尋優(yōu)能力。

Hammersley[19]序列是一種低差異序列，常被用于圖像渲染等領(lǐng)域。在群體智能算法中，Hammersley序列可以應(yīng)用于種群初始化，提高初始種群的多樣性，提升算法的全局搜索能力，相較于隨機數(shù)生成器與混沌序列有更好的效果，且均勻分布的初始種群可以使粗糙數(shù)據(jù)推理的論域更加完整。文獻[20]介紹了一種名為粗糙數(shù)據(jù)推理的方法，該方法在數(shù)據(jù)間建立一種不明確、非確定、似存在的推理關(guān)系，與經(jīng)典邏輯推理不同，粗糙數(shù)據(jù)推理的對象為數(shù)據(jù)，保證了該理論可以運用于算法優(yōu)化中。文獻[21]將聚類的思想與進化算法相結(jié)合，并通過實驗證明了對算法種群進行合理劃分，能有效提高算法的尋優(yōu)能力。

為了提高麻雀搜索的全局搜索能力，加快算法的收斂速度，增加種群的多樣性，本文提出一種融合粗糙數(shù)據(jù)推理的多策略改進麻雀搜索算法(sparrow search algorithm, RSSA)。首 先 基 于Hammersley 點集完成種群初始化，為粗糙數(shù)據(jù)推理提供完整的論域；其次使用粗糙數(shù)據(jù)推理，結(jié)合種群的經(jīng)驗建立數(shù)據(jù)間的推理關(guān)系，提高算法的收斂速度，并且增強算法跳出局部最優(yōu)的能力；最后對搜索中超界的個體進行優(yōu)化，保證種群多樣性。

1 原始麻雀搜索算法

麻雀搜索算法主要是受自然界中麻雀覓食與反捕食行為的啟發(fā)而提出，設(shè)計規(guī)則為：適應(yīng)度前20%的個體為發(fā)現(xiàn)者，在安全值大于預(yù)警值時它們可以進行大范圍的搜索，否則將飛往適應(yīng)度高的安全區(qū)域；除去發(fā)現(xiàn)者以外的個體被稱為加入者，加入者中適應(yīng)度靠前的個體將與發(fā)現(xiàn)者爭奪適應(yīng)度高的位置，靠后的個體因為競爭激烈，將飛往其他地方進行搜索；同時種群中有15%的個體會觸發(fā)預(yù)警機制，迅速向適應(yīng)度較好的區(qū)域移動，或者隨機移動以靠近其他個體。

麻雀種群及個體表示為：

2 基于Hammersley 序列的初始化

文獻[19]指出，在對尋優(yōu)問題進行求解時，若解空間的分布未知，則個體的初始值應(yīng)該在個體空間中盡量均勻地分布，這樣可保證種群的多樣性，而對于粗糙數(shù)據(jù)推理，分布均勻的數(shù)據(jù)集能保證論域的完整，增強粗糙數(shù)據(jù)推理的完備性。

種群初始化的常用手段有易于實現(xiàn)的隨機數(shù)生成器和具有隨機性、遍歷性和規(guī)律性等特點的Tent混沌序列[17]。但在大規(guī)模尋優(yōu)問題中，隨機數(shù)生成器的效果很差，Tent 序列在小周期點及不穩(wěn)周期點有相鄰點相關(guān)太強和容易迭代到不動點等缺陷。

低差異序列又稱為擬蒙特卡羅序列，是一種確定性的初始化方法，低差異意味著高均勻度，而高均勻度的種群能提高群體智能算法的探索能力，且?guī)椭惴ㄊ諗康揭粋€更好的解。常見的低差異序列有Faure、Halton 和Hammersley 等，Hammersley點集在高維度，分布更均勻，更適合在算法優(yōu)化中使用。Hammersley 二維序列的分布如圖1 所示，圖中的點分布非常均勻。

圖1 Hammersley 序列的二維分布圖

Hammersley 序列初始化種群的方法如下：設(shè)個體取值范圍為 [xmin,xmax]。由Hammersley 序列產(chǎn)生的第i個準(zhǔn)隨機數(shù)為Ri∈[0,1]，則初始種群中個體xi可表示為：

3 粗糙數(shù)據(jù)推理

3.1 粗糙集理論

粗糙集思想來源于近似理論，依托于等價關(guān)系與近似空間建立，粗糙數(shù)據(jù)推理則以粗糙集為基礎(chǔ)。粗糙集的一些概念和定義如下。

定義 1 設(shè)R是數(shù)據(jù)集U上的等價關(guān)系，令U/R={[x]R|x∈U}， 即U/R是U中數(shù)據(jù)x確 定的R等價類的集合，稱U/R為U相對于R的 劃分，其中 [x]R為x確 定的R等價類。

結(jié)論1 設(shè)U是任意一數(shù)據(jù)集，則U上等價關(guān)系的個數(shù)與U上劃分的個數(shù)相同。即U上等價關(guān)系R對 應(yīng) 劃 分U/R， 反 之U的 劃 分S={S1,S2,···,Sr}對 應(yīng)等價關(guān)系R， 且U/R={S1,S2,···,Sr}。

定義1 與結(jié)論1 表明U上的等價關(guān)系R和U的劃分U/R之間一一對應(yīng)，而建立劃分與等價關(guān)系的“橋梁”便是等價類，劃分的依據(jù)是等價類。

解釋粗糙推理需要引入上近似的概念，首先定義近似空間。設(shè)U是數(shù)據(jù)集，R是U上的等價關(guān)系，把U和R構(gòu) 成的結(jié)構(gòu)記為M=(U,R)，稱為近似空間，其中U稱為論域[22]，由于近似空間中R的存在可知，對于論域U根據(jù)等價關(guān)系進行多少種劃分，就可得到多少個近似空間。

上下近似的定義建立在近似空間上，設(shè)M=(U,R)為 近似空間，則U的任意子集X的上近似與下近似定義如下：

在近似空間M=(U,R)中 ，U/R是U相對于R的劃分，上近似和下近似都是通過這個劃分進行定義。其中子集X的上近似是所有和X的交集不是空集劃分的并，子集X的下近似是等于所有包含在X中的劃分的并。

下近似從X內(nèi)部逼近X，上近似是從X外部逼近，如果X視為精確信息，則上近似包含更多信息。當(dāng)上下近似空間不相等時稱X為粗糙集。

3.2 粗糙推理空間

粗糙推理空間是對近似空間M=(U,R)的擴展。定義粗糙推理空間時，設(shè)U是數(shù)據(jù)集，稱為論域，其元素稱為數(shù)據(jù)；令K={R1,R2,···,Rn}，n?1，其中R1,R2,···,Rn是U上n個 不同的等價關(guān)系；給定U上的二元關(guān)系S?U×U， 稱S為推理關(guān)系。將U、K和S構(gòu)成的結(jié)構(gòu)記作W=(U,K,S)，稱為粗糙推理空間。引入粗糙推理空間是為了完善粗糙數(shù)據(jù)推理，使運作于該空間上的粗糙數(shù)據(jù)推理理論更加具體、清晰。粗糙推理空間中的S是確定的推理關(guān)系，麻雀搜索算法中加入者向最優(yōu)位置個體靠近的操作便是加入者與最優(yōu)位置個體間建立了確定的推理關(guān)系。

3.3 粗糙數(shù)據(jù)推理

數(shù)據(jù)是對象的符號表示，可以是一個數(shù)值、一個物體、或者算法的個體信息。如果把推理建立在算法優(yōu)化中，由確定的位置更新公式，經(jīng)過推理與演繹得出其他可行的位置更新策略，可以增加種群移動的選擇，幫助算法跳出局部最優(yōu)解，且增大個體收斂到理論最優(yōu)位置的可能。

實際生活當(dāng)中存在不明確或潛存于數(shù)據(jù)之間的粗糙數(shù)據(jù)聯(lián)系，挖掘數(shù)據(jù)潛在聯(lián)系，給定一些聯(lián)系規(guī)則，使得這些粗糙數(shù)據(jù)聯(lián)系有依據(jù)地表示，且通過一定的規(guī)則程序化粗糙數(shù)據(jù)聯(lián)系，即粗糙數(shù)據(jù)推理[22]。定義粗糙數(shù)據(jù)推理時，設(shè)W=(U,K,S)為粗糙推理空間，對于 ∈S以及R∈K，存在以下3 個定義與2 個引理。

定義2設(shè)b∈U，如果b∈R?([a?R])， 則a關(guān)于R直接粗糙推出b， 記作a?Rb。 其中 [a?R]稱為后繼集，其定義為： [a?R]={x|x∈U且存在z∈[a]R，使得∈S}。

定 義3b1,b2,···,bn∈U，如果a?Rb1，b1?Rb2，b2?Rb3, ···,bn?1?Rbn(n?0)， 則 稱a關(guān) 于R粗糙推出b， 記作a|=Rb，容易看出a?Rb是a|=Rb的特殊形式。

定義4對于R∈K，a關(guān) 于R直 接粗糙推出或粗糙推出b的 推理稱為W=(U,K,S)中 的關(guān)于R的粗糙數(shù)據(jù)推理，簡稱為粗糙數(shù)據(jù)推理。

引理1[22]設(shè)W=(U,K,S)為粗糙推理空間，a,b∈U且R∈K，則a?Rb當(dāng) 且僅當(dāng)[b]R∩[a?R]?當(dāng)且僅當(dāng)[a]R∩[a?R]?。

引理2[22]設(shè)R是U上的等價關(guān)系，如果a,b∈U， 那么a∈[b]R當(dāng) 且僅當(dāng) [a]R=[b]R當(dāng)且僅當(dāng)b∈[a]R。

以上3 個定義確定了基于劃分的粗糙數(shù)據(jù)推理，同理可定義出多種劃分下的粗糙數(shù)據(jù)推理，例如a|=R1b與a|=R2b。在考慮多種劃分下的數(shù)據(jù)推理時可引入嵌入算法[22]，該算法作用為：假設(shè)a|=R1b與a|=R2b都 成立，若存在等價關(guān)系R=R1∩R2，嵌入算法可以判斷a|=Rb是否成立。

4 融合粗糙數(shù)據(jù)推理的多策略改進麻雀搜索算法

傳統(tǒng)麻雀搜索算法收斂速度較快，但從式(6)、式(7)中容易看出，加入者更新公式與預(yù)警機制中都有向全體最優(yōu)靠攏的操作，這些操作導(dǎo)致算法容易陷入局部最優(yōu)，且在算法迭代后期種群多樣性將嚴(yán)重減少。為了改進以上缺點，本文設(shè)計了一種融合粗糙數(shù)據(jù)推理的多策略改進麻雀搜索算法，通過引入不確定、似存在的模糊關(guān)系，增大算法的搜索空間，提高算法跳出局部最優(yōu)的能力。

粗糙數(shù)據(jù)推理理論基于上近似理論提出，上近似集包含的潛在聯(lián)系能極大提高算法的搜索空間，進而提高算法跳出局部最優(yōu)解的能力，在此證明上近似集具有包含潛在聯(lián)系等模糊信息的能力。

證明1：在粗糙推理空間下，對任意的x∈X，由等價類的性質(zhì)可知x∈[x]R， 所以 [x]R∩X?。由上近似R?(X)的 定義可知[x]R?R?(X)， 于是x∈R?(X)，因此X?R?(X)。

由證明1 可知，集合的上近似集由外部逼近該集合，包含更多信息，在麻雀搜索算法中，由于發(fā)現(xiàn)者、加入者等個體集合的操作中包含大量靠近局部最優(yōu)的操作，降低了種群多樣性，使用基于上近似的粗糙數(shù)據(jù)推理理論，便可以包含更多模糊信息，擴大搜索空間，是粗糙數(shù)據(jù)推理理論能幫助算法跳出局部最優(yōu)解的有力證明。

對于算法與粗糙數(shù)據(jù)推理理論結(jié)合的合理性，做出如下證明，首先證明粗糙數(shù)據(jù)推理理論能保留算法確定的收斂操作信息。

證明2：在粗糙推理空間下，對于任意由劃分確立的等價關(guān)系R∈K，以及算法中的個體a,b∈U，由等價類的定義可知，a∈[a]R。若存在明確的收斂信息∈S，由后繼集的定義可知b∈[a?R]。又因為[a?R]?R?([a?R])( 證明1)，所以b∈R?([a?R])，因此可得a?Rb或a|=Rb(定義2)。

通過證明2 可得到如下結(jié)論。

結(jié)論2 對于算法個體a,b∈U，若存在確定的收斂信息 ∈S，則對任意基于劃分的等價關(guān)系R∈K，有a?Rb或a|=Rb。

該結(jié)論闡明了粗糙數(shù)據(jù)推理能保證算法確定的收斂信息不丟失，是粗糙數(shù)據(jù)推理理論可與算法相結(jié)合的先決條件。

其次證明粗糙數(shù)據(jù)推理理論能引入模糊信息，擴大算法的搜索空間。

證明3：在粗糙推理空間下，對于任意由劃分確立的等價關(guān)系R∈K，以及算法中的個體a,b,u,v∈U，若存在確定的 ∈S，則a?Rb(證明2)，故[b]R∩[a?R]?( 引理1)。當(dāng)u∈[b]R時 ，由于[u]R∈[b]R( 引理2)，所以 [u]R∩[a?R]?， 可得a?Ru(引理1)。同樣，當(dāng)v∈[a]R時易知v?Rb。

通過證明3 可得到如下結(jié)論。

結(jié)論3 設(shè)W=(U,K,S)為粗糙推理空間，如果R∈K且a,b,u,v∈U，則有：

1)若a?Rb， 則當(dāng)u∈[b]R時 ，有a?Ru；

2)若a?Rb， 則當(dāng)v∈[a]R時，有v?Rb。

該結(jié)論表明，粗糙數(shù)據(jù)推理挖掘出了模糊信息，通過已有確定的收斂信息，合理的將具有粗糙聯(lián)系的u,v引入，擴大了算法的搜索空間，幫助算法跳出局部最優(yōu)解，是粗糙數(shù)據(jù)推理理論與算法結(jié)合可行的有力證明。

證明2 與證明3 證明了粗糙數(shù)據(jù)推理理論能與麻雀搜索算法有機結(jié)合，且能完成引入該理論的預(yù)期目標(biāo)，同時也一定程度上解決了群體智能算法在優(yōu)化時，改進方案多從實驗與經(jīng)驗出發(fā)，可解釋性差的問題。

定義1 與結(jié)論1 闡述了等價關(guān)系與劃分的對應(yīng)關(guān)系，所以粗糙數(shù)據(jù)推理基于等價關(guān)系建立也可稱為依據(jù)劃分建立。

根據(jù)麻雀搜索算法原理做以下劃分：1)依照適應(yīng)度劃分，其對應(yīng)等價關(guān)系關(guān)系記為R1；2)依照高緯歐氏距離劃分，其對應(yīng)關(guān)系記為R2。高緯歐氏距離公式為：

在麻雀搜索算法運行過程中，假設(shè)發(fā)生了加入者xi向 最優(yōu)個體 xp靠攏的操作，即認(rèn)為出現(xiàn)了確定推理 ， 此為確定的S路徑，由于麻雀搜索算法的發(fā)現(xiàn)者?加入者模型可以認(rèn)為符合適應(yīng)度劃分，所以該確定推理可以表示為確定路徑xi?R1xp ， 假設(shè)種群共有n個 個體，加入者為m個，發(fā)現(xiàn)者為n?m個，則有[xi]R1={x1,···,xi,···,xm}和 [xp]R1={xm+1,···,xP,···,xn}，根據(jù)等價類與劃分的關(guān)系、結(jié)論2 和結(jié)論3 可得圖2a 所示的粗糙推理關(guān)系。進一步依照高緯歐氏距離進行劃分，分別選取與 xp、xi歐式距離最近的占總體數(shù)量20%的個體，且保證所選個體互不相同，依照個體將論域劃分，根據(jù)等價類與劃分的關(guān)系、結(jié)論2 和結(jié)論3 可得圖2b 所示推理關(guān)系。

圖2 R1、R2 和R 的粗糙推理關(guān)系

接下來建立另一種推理關(guān)系，它由以下函數(shù)推出：

式中，f(xi)2?f(xj)2表 示xi、xj個體適應(yīng)度的平方差yD(xi,xj)為xi、xj兩點間的歐式距離。該函數(shù)考慮到個體間的適應(yīng)度與歐氏距離，使用式(12)對xi與 xp分別求出占總體數(shù)量10%的互不相同的個體，依據(jù)個體將論域劃分，假設(shè)該劃分對應(yīng)的等價關(guān)系為R， 且已知R=R1∩R2，同樣可得圖2c 所示的推理關(guān)系，由嵌入算法可得該推理關(guān)系成立，從而可融合粗糙數(shù)據(jù)推理理論對麻雀搜索算法進行如下改進：在 成 立時，記錄xi向 xp靠近后的適應(yīng)度，同時通過迭代次數(shù)與一組隨機數(shù)的控制執(zhí)行以下3 種策略。

1) 當(dāng)xi向 xp靠 攏時，在 xp的R2等價類中隨機選擇一個個體xj靠攏。

2) 當(dāng)xi向 xp靠 攏時，同時在 xp的R1等價類中隨機選擇一個個體xm+1靠攏，依據(jù)適應(yīng)度貪心選擇xi的靠攏對象。

3) 當(dāng)xi向 xp靠 攏時，同時在 xp的R等價類中隨機選擇一個個體xk靠 攏，依據(jù)適應(yīng)度貪心選擇xi的靠攏對象。

3 種策略的推理關(guān)系如圖3 所示。

圖3 3 種策略的推理關(guān)系

RSSA 的算法流程圖如圖4。

圖4 RSSA 算法流程圖

5 合理性分析

5.1 策略執(zhí)行概率分析

采用正交實驗分析3 種策略執(zhí)行概率對RSSA尋優(yōu)能力的影響，測試函數(shù)如表1 所示。依據(jù)當(dāng)前迭代次數(shù)與最大迭代次數(shù)的比值將算法劃分為前、中、后期，對應(yīng)關(guān)系為前期[0, 0.15]、中期(0.15,0.8]、后期(0.8, 1]。算法的種群個數(shù)為100，迭代次數(shù)為500，獨立運行10 次，求出收斂至最優(yōu)值時迭代次數(shù)的平均值，若未收斂至最優(yōu)則最小迭代次數(shù)取500。表2 為函數(shù)F1 的正交實驗統(tǒng)計結(jié)果。

表1 待測試函數(shù)

由表2 可知，組合1 的最優(yōu)迭代次數(shù)平均值最小，所以函數(shù)F1 采用組合1 的執(zhí)行概率，對其他函數(shù)采用同樣的組合進行正交實驗，得到最佳的執(zhí)行概率組合結(jié)果，如表3 所示。

由表3 可知，函數(shù)對執(zhí)行概率有敏感度，但結(jié)合表2 與表3 可以看出組合1 對比其他組合有一定的優(yōu)勢，對于最優(yōu)解未知函數(shù)而言，從算法普遍適用性的角度出發(fā)可以先采用組合1 的執(zhí)行概率，為了追求收斂速度與精度，則應(yīng)對不同函數(shù)采用不同的策略執(zhí)行概率組合。

表2 F1 正交實驗結(jié)果

表3 剩余函數(shù)正交實驗結(jié)果

續(xù)表

5.2 策略合理性分析

策略1 使用依托高維歐氏距離的劃分，增大了算法的搜索范圍，使算法具有了跳出局部最優(yōu)的能力；策略2 使用依托適應(yīng)度的劃分，提高了算法的收斂速度；策略3 使用式(12)推導(dǎo)出的劃分，從高維歐氏距離與適應(yīng)度兩個方面同時逼近最優(yōu)值，提高算法的收斂精度。為了證明以上推論，使用SSA 與RSSA 進行多次對比實驗，選擇對算法收斂能力與跳出局部最優(yōu)能力要求較高的函數(shù)，如表1中的F6、F9 和F10，繪制其中一次實驗的收斂曲線如圖5 所示。對比實驗的種群個數(shù)為50，迭代次數(shù)為100。

從圖5a、圖5b 的左小框部分可以看出，在算法運行的初期由于策略1 的影響，算法的收斂速度與SSA 相比并不快，且有一定波動，說明算法犧牲了收斂速度擴大了搜索范圍增大；從圖5c 的左長方形框部分可以看出，在算法運行的中期由于主要執(zhí)行策略2，算法的收斂速度大幅度提升；從圖5a、圖5c 的中間小框部分可以看出，由于3 種策略的共同影響，算法具有了跳出局部最優(yōu)的能力，且在跳出局部最優(yōu)后能夠繼續(xù)向最優(yōu)解收斂，或收斂至最優(yōu)解；從圖5a 的右小框部分可以看出，在算法運行的后期策略1 與策略3 的共同影響下，算法的收斂速度放緩，但是精度提高，收斂曲線表明算法在迭代中后期已經(jīng)陷入局部最優(yōu)，但由于策略1 的影響，算法最終跳出局部最優(yōu)并開始向全局最優(yōu)收斂。對比實驗證明粗糙數(shù)據(jù)推理理論的引入達到了預(yù)期的效果。

圖5 收斂曲線對比

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

時間復(fù)雜度是評價算法執(zhí)行效率的重要指標(biāo)。假設(shè)求解問題規(guī)模是D維，麻雀種群規(guī)模為正整數(shù)N，求解目標(biāo)函數(shù)所需的時間為f(D)。文獻[23]指出傳統(tǒng)麻雀搜索算法的時間復(fù)雜度為：

麻雀搜索算法位置更新公式的時間復(fù)雜度為：

在RSSA 中，產(chǎn)生一個D維Hammersley 序列的時間復(fù)雜度為T=O(D)，但基于Hammersley 序列的初始化方法是一種確定性的初始化方法，在確定算法個體數(shù)N后僅需執(zhí)行一次，便可作為本地信息直接調(diào)取。假設(shè)調(diào)取本地Hammersley 序列所需執(zhí)行時間為t1，按式(8)生成單個個體所需時間為t2，則RSSA 的初始化種群時間復(fù)雜度為：

策略1 需要依據(jù)高維歐氏距離進行劃分，假設(shè)計算一次D維歐式距離耗時為t3D，共需計算N?1次，總耗時(N?1)t3D；且需要隨機選擇一個個體向其靠攏，隨機選擇個體耗時t4，靠攏操作與具體的位置更新公式耗時相同，復(fù)雜度為O(D)，所以策略1 的時間復(fù)雜度為：

策略2 需要依據(jù)適應(yīng)度進行劃分，計算一次D維函數(shù)耗時為f(D)，共需計算N?1 次，總耗時(N?1)f(D)；同樣需要隨機選擇一個個體執(zhí)行靠攏操作，隨機選擇個體耗時t5，靠攏操作復(fù)雜度為O(D)，且需要進行貪心選擇，即計算兩次D維函數(shù)，并進行對比，該操作耗時2f(D)+t6。所以策略2 的時間復(fù)雜度為：

在計算策略3 前，依照式(12)計算，需要求解兩次D維函數(shù)，耗時為2f(D)，且計算一次D維歐氏距離，耗時為t7D，式(12)的時間復(fù)雜度為：

策略3 在劃分后，還需要隨機選擇個體進行靠攏操作與貪心選擇，所以策略3 的時間復(fù)雜度為：

故最大迭代次數(shù)為itermax時，RSSA 的時間復(fù)雜度為：

綜上可知，RSSA 與SSA 時間復(fù)雜度相同，即基于低差異序列的初始化與粗糙數(shù)據(jù)推理理論的引入并不會提高算法的時間復(fù)雜度。

6 實驗與結(jié)果分析

6.1 實驗環(huán)境與基準(zhǔn)函數(shù)

利用3 種不同類型共計11 個測試函數(shù)進行對比仿真實驗，來驗證RSSA 對于麻雀搜索算法改進的科學(xué)性以及相較于灰狼優(yōu)化(grey wolf optimization, GWO)算法、鵜鶘優(yōu)化算法(Pelican optimization algorithm, POA)[24]、被囊群算法(tunicate swarm algorithm, TSA)[25]、麻雀搜索算法(sparrow search algorithm, SSA)等智能算法的優(yōu)越性。各測試函數(shù)如表1 所示，6 個可變維度的單峰函數(shù)F1～F6，4 個可變維度的多峰函數(shù)F7～F10，1 個固定維多峰函數(shù)F11。為了保證實驗的公平性，所有算法的種群個數(shù)均為100，迭代次數(shù)為500，實驗在同一環(huán)境下獨立運行50 次。將各個算法最優(yōu)值的平均值與標(biāo)準(zhǔn)差作為評價指標(biāo)，如表4 所示。

表4 實驗結(jié)果對比表

6.2 實驗結(jié)果及分析

通過表4 可以得出，在F1～F6 的高維單峰值函數(shù)測試中，RSSA 均優(yōu)于其他算法多個數(shù)量級，除F2 與F5 外，RSSA 算法平均最優(yōu)值都能收斂到理論最優(yōu)解0；標(biāo)準(zhǔn)差是反映數(shù)據(jù)離散程度的數(shù)值，從標(biāo)準(zhǔn)差上可以看出收斂到0 的情況非常穩(wěn)定，即每次實驗都可以得到理論最優(yōu)解。在F7～F10的高維多峰值函數(shù)測試中RSSA 也強于其他算法，跳出局部最優(yōu)解的能力有所提升，在大多數(shù)情況下收斂到最優(yōu)解0；對于最優(yōu)解不在0 處的高維多峰值函數(shù)F7，RSSA 算法也最接近最優(yōu)解?12 569.487，標(biāo)準(zhǔn)差也屬于可接受的范圍，相較于其他群體智能算法收斂精度更高也更穩(wěn)定。

為了證明同時引入低差異序列與粗糙數(shù)據(jù)推理的必要性，選取對算法收斂速度與跳出局部最優(yōu)能力要求較高的多峰值函數(shù)F7～F10，分別對SSA、引入低差異序列的SSA、引入粗糙數(shù)據(jù)推理的SSA 和RSSA 進行對比實驗。實驗的種群個數(shù)與迭代次數(shù)分別為100 和500，獨立運行30 次記錄找到的最優(yōu)解結(jié)果如表5 所示。

表5 多峰值函數(shù)不同策略對比表

通過表5 可得，對于簡單的多峰值函數(shù)F8，4 種算法都能收斂到最優(yōu)解，說明每種改進單獨存在都是可行的，而對于復(fù)雜的多峰值函數(shù)，在單獨引入低差異序列或粗糙數(shù)據(jù)推理后，算法的性能都有所提高，但是依然無法收斂到全局最優(yōu)，在同時引入低差異序列與粗糙數(shù)據(jù)推理后，RSSA 全局尋優(yōu)能力增強，求解出了理論最優(yōu)值。這說明同時引入低差異序列與粗糙數(shù)據(jù)推理是必要的，進一步證明了粗糙數(shù)據(jù)推理的引入并非簡單地增加策略和迭代中的種群多樣性，而是利用適應(yīng)度、高緯歐氏距離與式(12)中內(nèi)涵的3 種等價關(guān)系進行策略的推理，通過表2、表3 執(zhí)行概率控制。在算法執(zhí)行過程中，將推理出的3 種策略有機的結(jié)合，自適應(yīng)地選擇，最終保證算法能夠兼顧收斂速度與搜索范圍，增大收斂到全局最優(yōu)的可能。

綜上所述，在融合粗糙數(shù)據(jù)推理以及使用低差異序列進行初始化后，算法具備了跳出局部最優(yōu)的能力，全局搜索能力也有提升。

為比較5 種算法的收斂性能，本文對5 種算法進行仿真對比，結(jié)果如圖6 所示。

收斂曲線圖反映了算法每次迭代所獲得的最優(yōu)解，當(dāng)收斂曲線在某次迭代中消失時即代表已經(jīng)收斂為0。觀察圖6 可得出結(jié)論：RSSA 算法的收斂速度與精度都高于其他算法，能夠隨迭代次數(shù)的增加不斷地尋優(yōu)，多數(shù)情況下都可以收斂到理論最優(yōu)值，全局尋優(yōu)能力有所提高，相較于其他算法有優(yōu)勢。

7 結(jié) 束 語

為了提高基本麻雀搜索算法解決高維多峰值問題的能力及群體智能算法改進策略的可解釋性，本文將粗糙數(shù)據(jù)推理與麻雀搜索算法合理融合，提出了一種融合粗糙數(shù)據(jù)推理的多策略改進麻雀搜索算法(RSSA)，并使用3 種類型共計11 個測試函數(shù)對RSSA 進行性能測試，與灰狼算法(GWO)、鵜鶘優(yōu)化算法(POA)、被囊群算法(TSA)等群體智能算法以及傳統(tǒng)麻雀搜搜算法(SSA)算法進行對比，得出以下結(jié)論：

1) RSSA 的優(yōu)化效果明顯，算法性能提升較大，且可有效地跳出局部最優(yōu)解。2) 11 個基準(zhǔn)函數(shù)的對比實驗結(jié)果與收斂曲線表明：RSSA 算法在收斂速度、收斂精度與跳出局部最優(yōu)的能力上優(yōu)于其他算法。后續(xù)將把RSSA 算法應(yīng)用在求解具體的工程問題中。