張 倩， 劉衍民, 楊妹蘭， 舒小麗

(1.貴州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院， 貴陽(yáng) 550025；2.遵義師范學(xué)院 數(shù)學(xué)學(xué)院， 貴州 遵義 563006; 3.貴州民族大學(xué) 數(shù)據(jù)科學(xué)與信息工程學(xué)院， 貴陽(yáng) 550025)

0 引 言

群智能優(yōu)化算法衍生于生物群體行為，其中，粒子群算法(PSO)[1]由于其并行性高，全局搜索性強(qiáng)等優(yōu)點(diǎn)，被廣泛應(yīng)用于配電網(wǎng)輸送[2]領(lǐng)域，但此算法在迭代過(guò)程中易出現(xiàn)“早熟”現(xiàn)象。

為消除這一弊端，研究者對(duì)PSO算法進(jìn)行了多方向改進(jìn)。一是結(jié)合PSO算法與其他優(yōu)化算法。文獻(xiàn)[3]將差分進(jìn)化算法(DE)的突變過(guò)程與PSO算法結(jié)合，此方法保證了粒子的多樣性，但其計(jì)算復(fù)雜度卻大大增加。文獻(xiàn)[4]將PSO算法、生物地理信息優(yōu)化算法(BBO)[5]以及偵察學(xué)習(xí)策略三者互相融合，這樣雖然滿足算法對(duì)結(jié)果精度的需求，但降低了算法的收斂速率。二是對(duì)粒子間的信息交流進(jìn)行改進(jìn)。文獻(xiàn)[6]提出全信息PSO算法(wFIPS)。根據(jù)群體粒子經(jīng)歷的最優(yōu)值和其鄰域中表現(xiàn)優(yōu)異的粒子分量調(diào)整粒子速度，達(dá)到對(duì)粒子信息的“充分了解”，此算法在一定程度上提高了PSO算法的局部搜索性能，但是其局部搜索能力和全局搜索能力并未均衡。文獻(xiàn)[7]提出了合同協(xié)作PSO算法(CPSO)。該算法利用多個(gè)群體進(jìn)行不同粒子間的交叉操作，改進(jìn)粒子間的信息交換過(guò)程，此算法在增加粒子間信息交流的基礎(chǔ)上，造成了數(shù)據(jù)大量冗余。

為改善這些不足，本文提出了一種結(jié)合拓?fù)浣Y(jié)構(gòu)與偵察學(xué)習(xí)策略的新型PSO算法(BUPSO)，通過(guò)實(shí)驗(yàn)對(duì)比分析，該算法可兼顧算法的局部搜索能力和全局搜索能力，在提高算法收斂速率的同時(shí)規(guī)避算法陷入“早熟”現(xiàn)象，提升了算法的整體性能。

1 算法基礎(chǔ)理論

1.1 標(biāo)準(zhǔn)粒子群算法

在標(biāo)準(zhǔn)粒子群算法中，假設(shè)當(dāng)前種群規(guī)模為N，維度為D，粒子的位置表示為xi={x1,x2,x3,…，xN}，速度表示為vi={v1,v2,v3,…,vN}，整個(gè)搜尋過(guò)程如式(1)、式(2)所示：

(1)

(2)

1.2 偵察學(xué)習(xí)策略

PSO算法只有粒子的學(xué)習(xí)階段，若在此階段對(duì)粒子的速度和位置進(jìn)行多次迭代，算法搜索能力會(huì)因此降低而導(dǎo)致粒子群體在某一局部極值點(diǎn)停滯。因此，尋找一種合適的策略，使得算法跳出局部收斂顯得尤為重要。文獻(xiàn)[4]將偵察學(xué)習(xí)策略引入PSO算法。若PSO算法經(jīng)過(guò)數(shù)次迭代后發(fā)現(xiàn)最優(yōu)解的位置未被更新，則通過(guò)偵察學(xué)習(xí)策略產(chǎn)生新解，產(chǎn)生過(guò)程如式(3)：

(3)

其中，xij代表粒子i在第j維產(chǎn)生的隨機(jī)位置，xmaxj,xminj代表侯選解的范圍，r為[0，1]的隨機(jī)數(shù)。

2 結(jié)合拓?fù)浣Y(jié)構(gòu)和偵察學(xué)習(xí)策略的新型粒子群算法

2.1 基于拓?fù)浣Y(jié)構(gòu)的種群構(gòu)建

粒子群體應(yīng)用不同的拓?fù)浣Y(jié)構(gòu)，粒子間的信息交流方式與信息交流量也不同。以All型、Ring型為例，Ring型拓?fù)浣Y(jié)構(gòu)中粒子間的交流局限于相鄰兩粒子間，而All型拓?fù)浣Y(jié)構(gòu)中所有粒子可實(shí)現(xiàn)互相交流。兩類拓?fù)浣Y(jié)構(gòu)如圖1和圖2所示。

圖1 Ring型結(jié)構(gòu)Fig.1 Ring-type structure

圖2 All型結(jié)構(gòu)Fig.2 All-type structure

依據(jù)種群粒子間信息交流量的不同，可將搜索方式分為局部版本和全局版本。若群體中所有粒子均產(chǎn)生信息交換，則為全局版本。PSO算法使用的即為All型全局版本搜索方式。若粒子的信息交流局限于鄰居粒子中，則為局部版本。文獻(xiàn)[8]指出Ring型拓?fù)浣Y(jié)構(gòu)收斂精度與收斂速率最高，因此本算法應(yīng)用Ring型局部版本搜索方式。兩種搜索方式的不同之處在于粒子的速度更新方式不同，局部版本速度的“社會(huì)認(rèn)知”項(xiàng)由鄰居中表現(xiàn)最好的粒子引導(dǎo)，而全局版本速度的“社會(huì)認(rèn)知”項(xiàng)由群體中表現(xiàn)最好的粒子引導(dǎo)。式(4)、式(5)分別代表全局搜索版本以及局部搜索版本的粒子速度。具體表述如式(4)、式(5):

(4)

(5)

局部版本搜索方式有利于粒子勘探更優(yōu)質(zhì)解，而全局版本搜索方式有利于粒子開發(fā)新區(qū)域。為充分融合兩種搜索方式，本文引入聯(lián)合因子m這一指標(biāo)將兩種搜索方式均衡結(jié)合，既能保證粒子搜索的廣度，又可滿足算法的整體收斂精度。兩種搜索的結(jié)合方式如式(6)：

(6)

此外，為模擬生物進(jìn)化算法中的突變過(guò)程，規(guī)避算法陷入局部最優(yōu)的風(fēng)險(xiǎn)，本算法引入隨機(jī)參數(shù)r3。文獻(xiàn)[9]指出當(dāng)r3均值為0，標(biāo)準(zhǔn)差為0.01的正態(tài)分布隨機(jī)向量且m取0.1時(shí)，該算法收斂于全局最優(yōu)值的效果更優(yōu)。此更新過(guò)程如式(7)：

(7)

2.2 偵察學(xué)習(xí)策略的引入

傳統(tǒng)的偵察學(xué)習(xí)策略會(huì)在確定范圍內(nèi)隨機(jī)更新粒子位置，因而無(wú)法加強(qiáng)粒子間的信息交流，導(dǎo)致算法的運(yùn)算效率降低。故此，本文對(duì)偵察學(xué)習(xí)策略進(jìn)行了相應(yīng)改進(jìn)，引入了粒子的速度公式，并在粒子位置公式中引入新變量，以確保該粒子做到絕對(duì)更新，增加粒子尋求到最優(yōu)解的概率以及偵察學(xué)習(xí)策略在本文中的普適性。為了方便描述，用xi表示產(chǎn)生壞解的粒子，xj表示更新后的粒子。此階段的改進(jìn)思想如下：

改進(jìn)的偵察學(xué)習(xí)策略階段的速度和位置公式如式(8)、式(9)：

(8)

(9)

雖然如式(9)所示，新產(chǎn)生的粒子位置沒(méi)有超出粒子的位置下界，但是不排除粒子飛出位置上界的可能。所以，為將粒子的位置限定在[Vmin,Vmax]，在此公式后加入粒子的位置邊界處理?xiàng)l件。若粒子位置超出邊界，則拋棄掉此粒子，進(jìn)入下一次搜尋過(guò)程，以保證運(yùn)算結(jié)果的有效性和準(zhǔn)確性。同時(shí)，為了方便記錄最優(yōu)解未被更新的次數(shù)，每個(gè)最優(yōu)解都設(shè)一個(gè)標(biāo)記參數(shù)。若參數(shù)的數(shù)值達(dá)到閾值，則通過(guò)式(8)、式(9)產(chǎn)生候選解，并將此參數(shù)重置為0；否則參數(shù)加1，并進(jìn)入下一次迭代。此策略可有效規(guī)避算法過(guò)早收斂的問(wèn)題，有助于算法尋求到更有效的解。

2.3 算法模型

環(huán)形拓?fù)浣Y(jié)構(gòu)可提高粒子收斂于全局最優(yōu)解的效率，而偵察學(xué)習(xí)策略可擴(kuò)大粒子的全局搜索范圍。因此，將PSO算法與環(huán)形拓?fù)浣Y(jié)構(gòu)以及偵察學(xué)習(xí)策略的優(yōu)點(diǎn)相互融合，形成一種基于拓?fù)浣Y(jié)構(gòu)并且結(jié)合偵察學(xué)習(xí)策略的新型PSO算法(BUPSO)。此算法以PSO算法為主框架，構(gòu)建環(huán)形結(jié)構(gòu)粒子群體，同時(shí)結(jié)合偵察學(xué)習(xí)策略對(duì)粒子速度和位置進(jìn)行改進(jìn)，以增加粒子種群的多樣性，避免PSO算法陷入“早熟”問(wèn)題。BUPSO算法運(yùn)行流程如圖3所示。

圖3 BUPSO算法流程圖Fig.3 Flow chart of BUPSO

其步驟可總結(jié)如下：

1) 種群初始化，包括參數(shù)設(shè)置和種群構(gòu)建。參數(shù)設(shè)置包括標(biāo)記因子、最大飛行速度、種群規(guī)模以及粒子邊界條件，群體結(jié)構(gòu)設(shè)為環(huán)形拓?fù)浣Y(jié)構(gòu)，標(biāo)記因子閾值設(shè)為5；

2) 計(jì)算個(gè)體適應(yīng)度值；

3) 判斷是否更新全局最優(yōu)值；

4) 若更新全局最優(yōu)值，標(biāo)記因子重置為0；否則加1；

5) 若標(biāo)記因子重置為0，則將粒子的全局最優(yōu)值以及全局最優(yōu)變量更新，并轉(zhuǎn)到步驟7；若標(biāo)記因子加1，則判斷標(biāo)記因子是否超過(guò)閾值；

6) 若標(biāo)記因子超過(guò)5，則粒子通過(guò)偵察學(xué)習(xí)策略更新全局最優(yōu)值以及相關(guān)參量；否則，進(jìn)入下一迭代過(guò)程，返回步驟2)；

7) 判斷是否達(dá)到迭代停止條件。若達(dá)到迭代停止條件則輸出最優(yōu)解并結(jié)束算法；否則，返回步驟2)。

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

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

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

選取BUPSO算法、CLPSO算法[9]、UPSO算法[10]、PSO算法、wFIPS算法在CEC2017檢測(cè)函數(shù)[11]旋轉(zhuǎn)環(huán)境和非旋轉(zhuǎn)環(huán)境下進(jìn)行收斂性和魯棒性對(duì)比分析。其中，用“*”表示對(duì)檢測(cè)函數(shù)進(jìn)行旋轉(zhuǎn)。選取的檢測(cè)函數(shù)包括：Rosenbrock′s函數(shù)、Griewank′s函數(shù)、Levy函數(shù)、HappyCat函數(shù)、Expanded Griewank′s plus Rosenbrock′s函數(shù)、Zakharov函數(shù)、Rastrigin′s 函數(shù)、Expanded Schaffer′s F6函數(shù)。

5種算法均設(shè)置同一參數(shù)：種群規(guī)模為30個(gè)粒子、9×104次函數(shù)評(píng)價(jià)、獨(dú)立運(yùn)行20次。其他參數(shù)設(shè)置與上文描述一致。

3.2 收斂性能分析

為檢驗(yàn)BUPSO算法的優(yōu)化效果，在確定的函數(shù)評(píng)價(jià)次數(shù)下對(duì)不同算法的收斂特性進(jìn)行對(duì)比。如圖3和圖4所示，給出了5種算法在同一檢測(cè)函數(shù)下不同環(huán)境中的收斂特征圖。此外，本文選用兩種方式對(duì)算法性能測(cè)評(píng)比較。其一，通過(guò)不同算法在同一測(cè)試函數(shù)下的最小值(Min)、均值(Mean)以及方差(Std)進(jìn)行比較分析，判定算法的穩(wěn)定性和搜索精度；其二，在α=5%的顯著水平下，對(duì)50次獨(dú)立運(yùn)算下的BUPSO算法與其他4種算法進(jìn)行Wilcoxon秩和檢驗(yàn)，判定算法在結(jié)果上的優(yōu)越性。其中，p代表BUPSO算法與其他4種算法最優(yōu)結(jié)果是否具有顯著差異。p=0表示結(jié)果無(wú)顯著差異，p=1代表結(jié)果有顯著差異。以部分函數(shù)為例，非旋轉(zhuǎn)環(huán)境下的實(shí)驗(yàn)結(jié)果見(jiàn)表1，旋轉(zhuǎn)環(huán)境下的實(shí)驗(yàn)結(jié)果見(jiàn)表2，秩和檢驗(yàn)結(jié)果見(jiàn)表3。

表3 Wilcoxon秩和檢驗(yàn)p值Table 3 P values of Wilcoxon rank sum test

如表1和表2所示：數(shù)據(jù)表中加粗部分代表各算法在不同測(cè)試指標(biāo)下通過(guò)對(duì)比產(chǎn)生的最小值。針對(duì)這些函數(shù)，該算法的值基本上達(dá)到最小，說(shuō)明該算法的性能較優(yōu)。無(wú)論檢測(cè)函數(shù)在旋轉(zhuǎn)環(huán)境還是非旋轉(zhuǎn)環(huán)境下，從Min指標(biāo)來(lái)看，除了旋轉(zhuǎn)環(huán)境下的f4檢測(cè)函數(shù)，BUPSO算法的結(jié)果更接近于最優(yōu)值；從Mean指標(biāo)來(lái)看，該算法相比其他算法均值更小，說(shuō)明運(yùn)行多次，該新型算法的求解精度更好；從Std指標(biāo)來(lái)看，此算法的標(biāo)準(zhǔn)方差更小，說(shuō)明算法每次運(yùn)算得到的數(shù)值相對(duì)較穩(wěn)定，說(shuō)明該算法的收斂性能較好，且比較穩(wěn)定。

如表3所示：將該新型算法與其他算法的最優(yōu)結(jié)果進(jìn)行Wilcoxon秩和檢驗(yàn)，通過(guò)p值發(fā)現(xiàn)在對(duì)測(cè)試函數(shù)f1和f4進(jìn)行秩和檢驗(yàn)時(shí)，p值為0；在其他測(cè)試函數(shù)進(jìn)行對(duì)比檢驗(yàn)，發(fā)現(xiàn)其p值為1，說(shuō)明除了檢測(cè)函數(shù)f1和f4，BUPSO算法結(jié)果與其他4種算法最優(yōu)結(jié)果的差別在95%的置信區(qū)間內(nèi)有統(tǒng)計(jì)意義，進(jìn)而表明算法的優(yōu)越性在統(tǒng)計(jì)上是顯著的。

如圖4所示：BUPSO算法在求解多峰函數(shù)方面，尤其對(duì)于Rosenbrock′s 函數(shù)、Griewank′s函數(shù)、Levy 函數(shù)、HappyCat 函數(shù)、Expanded Griewank′s plus Rosenbrock′s 函數(shù)、Rastrigin′s 函數(shù)、Expanded Schaffer′s F6 函數(shù)，在收斂結(jié)果和收斂速率方面都表現(xiàn)突出，說(shuō)明此算法對(duì)求解多峰函數(shù)具有明顯優(yōu)勢(shì)；同樣，在求解單峰函數(shù)方面，對(duì)于Zakharov 函數(shù)，發(fā)現(xiàn)其收斂精度與收斂速率相較于其他算法，表現(xiàn)更優(yōu)。

如圖5所示：在旋轉(zhuǎn)環(huán)境下，無(wú)論多峰函數(shù)還是單峰函數(shù)，BUPSO算法都表現(xiàn)出良好的收斂性能。結(jié)合圖4和圖5，算法在前期過(guò)程的收斂曲線明顯比其他4種算法的收斂曲線下降更快，說(shuō)明BUPSO算法與拓?fù)浣Y(jié)構(gòu)的結(jié)合提升了解的質(zhì)量。此外，由收斂曲線整體趨勢(shì)可得，偵察學(xué)習(xí)策略的引入，明顯提高了算法的求解能力，說(shuō)明BUPSO算法相較于其他算法跳出局部最優(yōu)空間的能力顯著。

(a) Happy Cat函數(shù)

(b) Zakharov函數(shù)

(c) Rosenbrock′s function函數(shù)

(d) Expanded Schaffer′s F6函數(shù)

(e) Levy函數(shù)

(f) Expanded Griewank′s plus Rosenbrok′s函數(shù)

(g) HGBat函數(shù)圖4 非旋轉(zhuǎn)檢測(cè)函數(shù)收斂特征圖Fig.4 Convergence features of non-rotating detection functions

(a) Zakharov函數(shù)

(b) Non-continuous Rotated Rastrigin′s函數(shù)

(c) Grivwank′s函數(shù)

(d) Expanded Schaffer′s F6函數(shù)

(e) EXpanded Griewank′s plus Rosenbrok′s函數(shù)

(f) Rastrigin′s函數(shù)圖5 旋轉(zhuǎn)檢測(cè)函數(shù)收斂特征圖Fig.5 Convergence features of rotation detection functions

3.3 魯棒性分析

為探測(cè)5種算法的運(yùn)行穩(wěn)定性，每次運(yùn)行都選用同一測(cè)試函數(shù)在不同的環(huán)境下進(jìn)行測(cè)評(píng)比較。以Griewank′s 函數(shù)、Zakharov函數(shù)、Expanded Schaffer′s F6函數(shù)為例，表4給出了算法的魯棒性分析。這里的魯棒性分析指各算法獨(dú)立運(yùn)行50次，在算法評(píng)價(jià)次數(shù)內(nèi)所得到的全局最小值達(dá)到給定閾值的水平。FEs代表達(dá)到給定閾值時(shí)算法的評(píng)價(jià)次數(shù)，S代表在算法評(píng)價(jià)次數(shù)內(nèi)所得到的全局最小值達(dá)到給定閾值的比例，給定的閾值分別為1e-15、2.5e+04、1e-15、50、2e-04、1e+06。

表4 各種算法的魯棒性分析Table 4 Robustness analysis of various algorithms

如表4所示：在非旋轉(zhuǎn)環(huán)境下，對(duì)于Griewank′s函數(shù)，CLPSO算法和BUPSO算法都100%達(dá)到了閾值，但BUPSO算法比CLPSO算法用了較少的函數(shù)評(píng)價(jià)次數(shù)，對(duì)于Zakharov函數(shù)和Expanded Schaffer′s F6函數(shù)，僅BUPSO算法成功達(dá)到閾值且評(píng)價(jià)次數(shù)最少；在旋轉(zhuǎn)環(huán)境下，對(duì)于Expanded Schaffer′s F6函數(shù)，CLPSO算法與BUPSO算法都達(dá)到了閾值，對(duì)于Zakharov函數(shù)和Griewank′s函數(shù)，只有BUPSO算法達(dá)到了閾值，且該算法對(duì)Zakharov函數(shù)的評(píng)價(jià)次數(shù)最少。

總之，不論從算法的收斂特征結(jié)果還是從算法的魯棒性分析結(jié)果來(lái)看，BUPSO算法都表現(xiàn)出了較好的收斂特性和穩(wěn)定性。

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

PSO算法只有單一階段，存在收斂能力不足，粒子跳出局部最優(yōu)空間動(dòng)力不足，解的精度不高等弊端。為解決這些問(wèn)題，提出了基于偵察學(xué)習(xí)策略的BUPSO算法。該算法利用聯(lián)合因子對(duì)算法的全局搜索能力和局部搜索能力進(jìn)行均衡，提高了算法的收斂能力和運(yùn)算精度；當(dāng)粒子陷入局部收斂時(shí)，該算法引入偵察學(xué)習(xí)策略，對(duì)該粒子的速度和位置進(jìn)行更新，提高了粒子跳出局部最優(yōu)解的能力。通過(guò)Wilcoxon秩和檢驗(yàn)和基準(zhǔn)函數(shù)尋優(yōu)實(shí)驗(yàn)結(jié)果顯示，該算法有一定的有效性和優(yōu)越性，既保持了PSO算法簡(jiǎn)單、并行性高等特點(diǎn)，又在一定程度上提高了算法的收斂能力、局部極值逃逸能力和求解能力，具有深遠(yuǎn)的研究意義。