基于偵察學習策略的粒子群算法優(yōu)化

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

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

0 引 言

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

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

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

1 算法基礎(chǔ)理論

1.1 標準粒子群算法

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

(1)

(2)

1.2 偵察學習策略

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

(3)

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

2 結(jié)合拓撲結(jié)構(gòu)和偵察學習策略的新型粒子群算法

2.1 基于拓撲結(jié)構(gòu)的種群構(gòu)建

粒子群體應(yīng)用不同的拓撲結(jié)構(gòu)，粒子間的信息交流方式與信息交流量也不同。以All型、Ring型為例，Ring型拓撲結(jié)構(gòu)中粒子間的交流局限于相鄰兩粒子間，而All型拓撲結(jié)構(gòu)中所有粒子可實現(xiàn)互相交流。兩類拓撲結(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型全局版本搜索方式。若粒子的信息交流局限于鄰居粒子中，則為局部版本。文獻[8]指出Ring型拓撲結(jié)構(gòu)收斂精度與收斂速率最高，因此本算法應(yīng)用Ring型局部版本搜索方式。兩種搜索方式的不同之處在于粒子的速度更新方式不同，局部版本速度的“社會認知”項由鄰居中表現(xiàn)最好的粒子引導(dǎo)，而全局版本速度的“社會認知”項由群體中表現(xiàn)最好的粒子引導(dǎo)。式(4)、式(5)分別代表全局搜索版本以及局部搜索版本的粒子速度。具體表述如式(4)、式(5):

(4)

(5)

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

(6)

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

(7)

2.2 偵察學習策略的引入

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

改進的偵察學習策略階段的速度和位置公式如式(8)、式(9)：

(8)

(9)

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

2.3 算法模型

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

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

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

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

2) 計算個體適應(yīng)度值；

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

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

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

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

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

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

3 實驗仿真分析

3.1 實驗參數(shù)設(shè)置

選取BUPSO算法、CLPSO算法[9]、UPSO算法[10]、PSO算法、wFIPS算法在CEC2017檢測函數(shù)[11]旋轉(zhuǎn)環(huán)境和非旋轉(zhuǎn)環(huán)境下進行收斂性和魯棒性對比分析。其中，用“*”表示對檢測函數(shù)進行旋轉(zhuǎn)。選取的檢測函數(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個粒子、9×104次函數(shù)評價、獨立運行20次。其他參數(shù)設(shè)置與上文描述一致。

3.2 收斂性能分析

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

表3 Wilcoxon秩和檢驗p值Table 3 P values of Wilcoxon rank sum test

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

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

如圖4所示：BUPSO算法在求解多峰函數(shù)方面，尤其對于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)突出，說明此算法對求解多峰函數(shù)具有明顯優(yōu)勢；同樣，在求解單峰函數(shù)方面，對于Zakharov 函數(shù)，發(fā)現(xiàn)其收斂精度與收斂速率相較于其他算法，表現(xiàn)更優(yōu)。

如圖5所示：在旋轉(zhuǎn)環(huán)境下，無論多峰函數(shù)還是單峰函數(shù)，BUPSO算法都表現(xiàn)出良好的收斂性能。結(jié)合圖4和圖5，算法在前期過程的收斂曲線明顯比其他4種算法的收斂曲線下降更快，說明BUPSO算法與拓撲結(jié)構(gòu)的結(jié)合提升了解的質(zhì)量。此外，由收斂曲線整體趨勢可得，偵察學習策略的引入，明顯提高了算法的求解能力，說明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)檢測函數(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)檢測函數(shù)收斂特征圖Fig.5 Convergence features of rotation detection functions

3.3 魯棒性分析

為探測5種算法的運行穩(wěn)定性，每次運行都選用同一測試函數(shù)在不同的環(huán)境下進行測評比較。以Griewank′s 函數(shù)、Zakharov函數(shù)、Expanded Schaffer′s F6函數(shù)為例，表4給出了算法的魯棒性分析。這里的魯棒性分析指各算法獨立運行50次，在算法評價次數(shù)內(nèi)所得到的全局最小值達到給定閾值的水平。FEs代表達到給定閾值時算法的評價次數(shù)，S代表在算法評價次數(shù)內(nèi)所得到的全局最小值達到給定閾值的比例，給定的閾值分別為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)境下，對于Griewank′s函數(shù)，CLPSO算法和BUPSO算法都100%達到了閾值，但BUPSO算法比CLPSO算法用了較少的函數(shù)評價次數(shù)，對于Zakharov函數(shù)和Expanded Schaffer′s F6函數(shù)，僅BUPSO算法成功達到閾值且評價次數(shù)最少；在旋轉(zhuǎn)環(huán)境下，對于Expanded Schaffer′s F6函數(shù)，CLPSO算法與BUPSO算法都達到了閾值，對于Zakharov函數(shù)和Griewank′s函數(shù)，只有BUPSO算法達到了閾值，且該算法對Zakharov函數(shù)的評價次數(shù)最少。

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

4 結(jié)束語

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