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

周 寧，張嵩霖，張 晨

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

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

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

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

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

1 原始麻雀搜索算法

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

麻雀種群及個(gè)體表示為：

2 基于Hammersley 序列的初始化

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

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

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

圖1 Hammersley 序列的二維分布圖

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

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

3.1 粗糙集理論

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

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

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

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

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

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

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

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

3.2 粗糙推理空間

粗糙推理空間是對(duì)近似空間M=(U,R)的擴(kuò)展。定義粗糙推理空間時(shí)，設(shè)U是數(shù)據(jù)集，稱為論域，其元素稱為數(shù)據(jù)；令K={R1,R2,···,Rn}，n?1，其中R1,R2,···,Rn是U上n個(gè) 不同的等價(jià)關(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ù)推理，使運(yùn)作于該空間上的粗糙數(shù)據(jù)推理理論更加具體、清晰。粗糙推理空間中的S是確定的推理關(guān)系，麻雀搜索算法中加入者向最優(yōu)位置個(gè)體靠近的操作便是加入者與最優(yōu)位置個(gè)體間建立了確定的推理關(guān)系。

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

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

實(shí)際生活當(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í)，設(shè)W=(U,K,S)為粗糙推理空間，對(duì)于 ∈S以及R∈K，存在以下3 個(gè)定義與2 個(gè)引理。

定義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對(duì)于R∈K，a關(guān) 于R直 接粗糙推出或粗糙推出b的 推理稱為W=(U,K,S)中 的關(guān)于R的粗糙數(shù)據(jù)推理，簡(jiǎn)稱為粗糙數(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上的等價(jià)關(guān)系，如果a,b∈U， 那么a∈[b]R當(dāng) 且僅當(dāng) [a]R=[b]R當(dāng)且僅當(dāng)b∈[a]R。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) 當(dāng)xi向 xp靠 攏時(shí)，在 xp的R2等價(jià)類中隨機(jī)選擇一個(gè)個(gè)體xj靠攏。

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

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

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

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

RSSA 的算法流程圖如圖4。

圖4 RSSA 算法流程圖

5 合理性分析

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

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

表1 待測(cè)試函數(shù)

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

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

表2 F1 正交實(shí)驗(yàn)結(jié)果

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

續(xù)表

5.2 策略合理性分析

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

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

圖5 收斂曲線對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

利用3 種不同類型共計(jì)11 個(gè)測(cè)試函數(shù)進(jìn)行對(duì)比仿真實(shí)驗(yàn)，來(lái)驗(yàn)證RSSA 對(duì)于麻雀搜索算法改進(jìn)的科學(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)越性。各測(cè)試函數(shù)如表1 所示，6 個(gè)可變維度的單峰函數(shù)F1～F6，4 個(gè)可變維度的多峰函數(shù)F7～F10，1 個(gè)固定維多峰函數(shù)F11。為了保證實(shí)驗(yàn)的公平性，所有算法的種群個(gè)數(shù)均為100，迭代次數(shù)為500，實(shí)驗(yàn)在同一環(huán)境下獨(dú)立運(yùn)行50 次。將各個(gè)算法最優(yōu)值的平均值與標(biāo)準(zhǔn)差作為評(píng)價(jià)指標(biāo)，如表4 所示。

表4 實(shí)驗(yàn)結(jié)果對(duì)比表

6.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

7 結(jié) 束 語(yǔ)

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

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