宋 威，華子彧

1.江南大學 人工智能與計算機學院，江蘇 無錫 214122

2.江南大學 江蘇省模式識別與計算智能工程實驗室，江蘇 無錫 214122

1 引言

受自然界動物群體行為的啟發(fā)，Kennedy 和Eberhart 在1995 年提出了粒子群優(yōu)化（particle swarm optimization，PSO）算法[1]。PSO 模擬鳥群覓食的行為來尋找解空間中的最優(yōu)解。具體而言，每個具有位置矢量和速度矢量的粒子根據(jù)自身和種群中最優(yōu)粒子的歷史經(jīng)驗確定其下一步搜索軌跡。由于PSO 對優(yōu)化問題的要求很少，只要能評估解決方案的質(zhì)量，便可用于求解。在過去的20 年中，PSO 已引起了學術界的廣泛關注。此外，在面對復雜優(yōu)化問題時，PSO 的有效性也已得到驗證[2]。目前，PSO 已廣泛應用于電機設計[3]、路徑優(yōu)化[4]、應用檢測[5]等多個領域。

PSO 的參數(shù)直接影響粒子的搜索過程，協(xié)調(diào)算法的全局“探勘”和局部“開發(fā)”能力。Shi 和Eberhart 最早利用慣性權重來更新粒子的速度[6]，并研究了不同慣性權重對種群的影響。在粒子的搜索過程中，他們對慣性權重進行線性遞減控制，兼顧了搜索的廣度和精度。此后，還逐漸發(fā)展出一系列的PSO 變體。鄧志誠等人[7]提出具有動態(tài)子空間的隨機單維變異策略和Pareto 速度分配策略，以解決全局最優(yōu)粒子與普通粒子進化方向不一致問題。周蓉等人[8]提出一種基于灰狼優(yōu)化的反向?qū)W習PSO，平衡了算法的全局和局部搜索能力。

除了PSO，目前還有多種基于群體的優(yōu)化算法，比如遺傳算法（genetic algorithm，GA）、差分進化（differential evolution，DE）和人工蜂群（artificial bee colony，ABC）等。GA 是一種模擬生物進化規(guī)律的仿生算法。根據(jù)基因的重組與進化，GA 將問題求解過程轉(zhuǎn)化為基因的選擇、交叉和變異三個過程，并利用多次世代遺傳，以獲取尋優(yōu)結果[9]。然而，GA 的求解時間隨種群規(guī)模呈指數(shù)級增加，往往造成過高的時間開銷。與GA 類似，DE 也包括選擇、交叉和變異操作，只是這些操作的具體定義與GA 有所區(qū)別[10]。然而，隨著迭代次數(shù)的增加，DE 的種群規(guī)模會不斷縮小，容易造成算法的停滯或過早地陷入局部最小點。ABC 利用跟隨蜂貪婪選擇雇傭蜂來進行局部搜索，同時利用偵查蜂的全局搜索特性跳出局部最優(yōu)，拓展了搜索空間[11]。但是，由于從雇傭蜂到跟隨蜂的角色頻繁轉(zhuǎn)換，會導致蜜蜂位置振蕩，從而造成ABC的收斂速度過慢。相較而言，PSO 的求解時間與種群規(guī)模線性相關，求解速度較快。其種群規(guī)模在搜索過程中恒定，不存在算法停滯問題。而且，由于全局最優(yōu)經(jīng)驗能在整個種群中得到快速分享，PSO 具有較快的收斂速度。

目前，在標準PSO 及其大多數(shù)變體中，全局最優(yōu)粒子用于分享種群的最優(yōu)經(jīng)驗。但是，在搜索過程中，當前全局最優(yōu)粒子位置可能并非位于全局最優(yōu)解附近，若僅考慮全局最優(yōu)粒子對個體的影響，會導致種群學習對象單一，學習的多樣性不足，使得算法易陷入局部最優(yōu)。針對此問題，本文提出一種融入社會影響力的粒子群算法。具體而言，該算法設計了三種策略。首先，每個粒子將選擇全局最優(yōu)粒子和最優(yōu)伙伴粒子作為其“社會學習”的對象，為每個粒子帶來更豐富的有用知識。其次，引入引力系數(shù)分別描述各榜樣帶來的影響，在保證最優(yōu)經(jīng)驗得到分享的同時，更多地是增強了種群學習的多樣性。此外，每個粒子還在各維度上進一步向其最優(yōu)伙伴粒子學習，實現(xiàn)從全局到局部的變尺度搜索，以提升算法的整體收斂能力。這三種策略從整體上有助于算法收斂到全局最優(yōu)。并且通過廣泛實驗，其結果驗證了PSOSI（PSO with social influence）的優(yōu)越性。

2 粒子群算法

Shi和Eberhart于1998 年提出了帶有慣性權重的標準PSO。該算法的各個粒子更新方式如下：

其中，t表示當前迭代次數(shù)，d代表維度，r1和r2是[0，1]范圍內(nèi)的隨機數(shù)。pbesti是第i個粒子的歷史最優(yōu)位置，而gbest是種群歷史最優(yōu)位置。c1和c2代表學習因子。w是慣性權重，用于控制各粒子的上一代速度對當前速度的影響。目前通用的慣性權重控制方式是隨著迭代次數(shù)的增加而線性減?。?/p>

其中，winit為初始權重值，wend為最終權重值，Tmax代表最大迭代次數(shù)。

3 PSOSI算法

3.1 社會學習

在標準的PSO 中，每個粒子將全局最優(yōu)粒子視為其“社會學習”的唯一榜樣，但其學習的廣度是遠遠不夠的。類似于人類社會，向多個榜樣學習是一種更為普遍的現(xiàn)象。并且，許多研究也已證明，向多個榜樣學習的個體比僅從一個榜樣學習的個體擁有更強的學習能力[12]。目前，多榜樣學習已被應用于多個PSO 的變體。例如，Liang 等人[13]提出的全面學習PSO，各粒子選擇不同粒子的最優(yōu)歷史信息作為其多個學習的榜樣。

受人類社會的學習現(xiàn)象啟發(fā)，每個粒子在其“社會學習”部分將向多個榜樣學習。在PSOSI 中，各粒子選擇全局最優(yōu)粒子和最優(yōu)伙伴粒子作為其“社會學習”的兩個榜樣。其中，最優(yōu)伙伴粒子是每個粒子隨機選擇的兩個伙伴中最好的個體。當粒子的適應值在連續(xù)若干代中沒有提升時，粒子將重新隨機地選擇伙伴。

3.2 基于引力系數(shù)的社會學習

近年來，研究人員嘗試利用引力模型從力學角度來解釋各種社會現(xiàn)象[14]。研究表明，人們對他人的影響隨著距離的增加而減弱。受此啟發(fā)，本節(jié)基于社會學習來定義粒子向多個榜樣學習的引力系數(shù)。

為了直觀反映pbest和gbest對個體的影響，刪除式（1）中獨立隨機變量r1和r2，學習因子c1和c2，以及慣性權重w。簡化后的速度更新公式為：

顯然，粒子的速度僅受pbest和gbest影響。根據(jù)牛頓第一定律，即力是改變物體運動的唯一因素，式（4）中的兩個向量，即可視為兩個力，因為它們影響著粒子的運動。然而，這種力隨著距離的增大而變大，導致種群多樣性的降低。針對此問題，本文定義引力系數(shù)，從力學角度分別描述兩個榜樣對各粒子的影響。具體地，第i個粒子受全局最優(yōu)粒子影響的引力系數(shù)ggri定義為：

同時，第i個粒子受最優(yōu)伙伴粒子影響的引力系數(shù)cgri定義為：

其中，distgmax代表全局最優(yōu)粒子與其最遠粒子的距離。由于全局最優(yōu)粒子是當前種群中最優(yōu)秀的個體，用于分享種群的最優(yōu)經(jīng)驗，它影響著種群中的所有個體。dist_gi是第i個個體與全局最優(yōu)粒子間的距離。distcmax，i代表第i個個體的最優(yōu)伙伴粒子與該粒子最遠伙伴間的距離。dist_ci代表第i個個體與其最優(yōu)伙伴粒子間的距離。

由于distgmax是dist_gi的上界，基于式（5），ggri的取值范圍為[0.5，1.0]。此外，由于個體i與其最優(yōu)伙伴粒子分別選擇各自的伙伴，即distcmax，i與dist_ci沒有必然的聯(lián)系，基于式（6），cgri的取值范圍為（0，1）。在所提的基于引力系數(shù)的社會學習方式下，全局最優(yōu)粒子負責向每個粒子傳遞當前的最優(yōu)經(jīng)驗，將ggri設置為一個較大的值（0.5 ≤ggri≤1.0），以保證最優(yōu)經(jīng)驗能得到分享。區(qū)別于全局最優(yōu)粒子，最優(yōu)伙伴粒子用于擴展種群學習的多樣性，將cgri的取值范圍設置為（0 ＜cgri＜1）。具體地，個體距離其最優(yōu)伙伴粒子越近，cgri越大，因為距離的減小伴隨著最優(yōu)伙伴粒子影響力的增大。此外，與原始的PSO 相比，本文利用ggri一方面減弱了最優(yōu)粒子的影響力，另一方面利用cgri來擴展多樣性。因此，相對于原始的PSO，本文所提的基于引力系數(shù)的社會學習方式更多地是用于增強種群學習的多樣性。通過引入引力系數(shù)ggri和cgri，粒子的速度更新公式定義為：

其中，cbesti是第i個粒子的最優(yōu)伙伴粒子。類似于式（1），r1、r2、r3是[0，1]范圍內(nèi)的隨機數(shù)，c1、c2、c3是學習因子。

3.3 基于最優(yōu)伙伴的變尺度搜索

本文首先引入社會學習和引力系數(shù)兩個策略來豐富種群學習的多樣性，增加了算法收斂于全局最優(yōu)解的可能性。為了進一步使算法趨于全局最優(yōu)收斂，本文基于最優(yōu)伙伴在各維度上的經(jīng)驗，進而利用提出的變尺度搜索策略，提高算法的整體收斂能力。具體地，各粒子根據(jù)式（7）和式（2）更新完速度與位置后，會進一步在各個維度上根據(jù)其與最優(yōu)伙伴粒子的距離執(zhí)行變尺度搜索：

其中，隨機數(shù)r服從[-1，1] 的均勻分布。在算法初期，由于粒子在搜索空間中彼此相距較遠，變尺度搜索將覆蓋較大空間，增強算法的全局搜索能力。隨著算法的迭代，當種群逐漸趨于收斂時，粒子間的距離相對較小，各粒子則在其自身周圍進行較細致的局部搜索，提高了算法的收斂精度，使算法趨于全局最優(yōu)收斂。同時，本文采用競爭性原理，該策略的結果當且僅當所產(chǎn)生子代位置的適應值更好時才保留。

3.4 時間復雜度分析

標準PSO 的時間耗費主要包括初始化、適應值評估，以及速度和位置的更新，由于它們的復雜度分別為O（mn）、O（mn）、O（2mn），其中m和n分別代表種群規(guī)模和解空間的維度，因此標準PSO 的時間復雜度為O（mn）。與之相比，改進的PSO 算法或多或少地引入了一些額外策略，但它們的時間復雜度大多仍與標準PSO 相同，比如Xia 等人[15]提出的XPSO（expanded PSO）需進行額外的遺忘學習；Tanweer 等人[16]提出的SRPSO（self-regulating PSO）引入自我感知策略來指導粒子的搜索過程，但XPSO 和SRPSO的時間復雜度仍為O（mn）[15-16]。區(qū)別于標準PSO，本文提出的PSOSI需要更新學習榜樣。但是，榜樣僅在粒子的適應值長時間沒有改善時才會重選。重新選擇學習榜樣在最壞情況下的時間復雜度為O（m）。因此，PSOSI 在最壞情況下的復雜度仍然是O（mn），包括初始化的復雜度O（mn+m），評估的復雜度O（mn），更新的復雜度O（2mn+m），以及變尺度搜索的復雜度O（mn）。因此，PSOSI 的時間復雜度與標準PSO 算法保持相同。

3.5 算法流程

PSOSI 的流程圖如圖1 所示。相應地，PSOSI 的步驟如下：

輸入：最大迭代次數(shù)Max，重選伙伴的閾值F。

輸出：最后一代中最優(yōu)粒子的適應值。

步驟1初始化每個粒子。

步驟2選擇每個粒子的伙伴粒子。

步驟3計算每個粒子的適應值。

步驟4計算各粒子與其榜樣間的距離。

步驟5若連續(xù)F代粒子的適應值沒有提升，將重選伙伴，并計算各粒子與其榜樣間的距離；否則，直接跳轉(zhuǎn)至步驟6。

Fig.1 Flow chart of PSOSI圖1 PSOSI流程圖

步驟6計算每個粒子的全局引力系數(shù)ggr與伙伴引力系數(shù)cgr。

步驟7更新每個粒子的速度v和位置x，并計算粒子在當前位置的適應值。

步驟8執(zhí)行變尺度搜索。

步驟9更新每個粒子的位置x，并計算粒子在當前位置的適應值。

步驟10判斷是否滿足結束條件，若不滿足，則跳轉(zhuǎn)至步驟5；否則，算法結束。

4 仿真實驗及結果分析

4.1 實驗設置

為了驗證PSOSI算法的有效性，本文在CEC2013測試集的28 個基準函數(shù)上進行了廣泛測試。這28個函數(shù)的具體信息如表1 所示，f1～f5為單峰函數(shù)，f6～f20為多峰函數(shù)，f21～f28則為復合函數(shù)[17]，在每個維度上的搜索范圍均為[-100，100]。根據(jù)CEC2013 會議的統(tǒng)一要求，最大演化次數(shù)FEs設置為104D，其中D為解空間的維度，在本實驗中設為30。同時，PSOSI的種群規(guī)模定義為50。為了獲取統(tǒng)計結果，在以下所有實驗中每種算法將在每個測試函數(shù)上獨立運行30 次。

本文實驗采用Xia 等人[15]提出的學習因子自適應調(diào)整方法來控制c1、c2、c3。首先，利用正態(tài)分布Ν（μi，0.12）初始化每個粒子的3 個學習因子，其中μi代表正態(tài)分布的數(shù)學期望，0.1 代表標準差。根據(jù)正態(tài)分布特性，所有粒子的學習因子都在μi的周圍擾動。在搜索過程中，每個粒子會根據(jù)其當前榜樣粒子的經(jīng)驗來調(diào)整μi，具體規(guī)則如下：

其中，η代表學習權重，并且η=0.1 時已被驗證具有良好的學習效果[15]。是榜樣粒子的學習因子，代表榜樣粒子的學習因子均值。在每次搜索時，粒子的學習因子ci均服從Ν（μi，0.12），即ci在當前μi周圍擾動。因此，只需獲取初始的μi，在每次搜索時即可根據(jù)式（9）來更新當前μi，進而利用正態(tài)分布產(chǎn)生對應的ci。為了選取合適的初始μi，本文根據(jù)Xia 等人[15]的方法為所有粒子設置相同的初始μi，即所有粒子的初始μ1=μ2=μ3=μ。本文實驗在CEC2013 測試集的28 個函數(shù)上對μ的取值進行分析，圖2 展示了部分函數(shù)上不同μ對算法適應值的影響。由圖2 所示，在f6、f10、f12、f28上，當μ為1.0 時，算法的適應值最低（本文中算法的適應值越低，反映其表現(xiàn)越好）。當μ為1.4 和1.2 時，雖然算法在f1和f22上分別表現(xiàn)最好，但在其他函數(shù)上表現(xiàn)較差。同時，當μ為1.0 時，算法在f1上的表現(xiàn)僅次于μ為1.3 和1.4，在f22上的表現(xiàn)僅次于μ為1.2。進一步地，綜合考慮在28 個函數(shù)上不同μ對算法適應值的影響，本文最終將μ設置為1.0。

Table 1 Specific information of CEC2013 benchmark functions表1 CEC2013 基準函數(shù)具體信息

Fig.2 Fitness of PSOSI with different μ圖2 不同μ 對PSOSI算法適應值的影響

4.2 不同策略的有效性分析

為了提高PSO 多樣性和收斂性，以進一步提升其求解復雜問題的能力，本文提出三種策略，包括社會影響、引力系數(shù)和變尺度搜索。為了驗證這些策略的有效性，本文對PSOSI、PSOSI-VS（PSO with social influence-variable-scale search）、PSOSI-GC（PSO with social influence-gravity coefficient）和PSO[15]進 行 比較，其中PSOSI-VS 和PSOSI-GC 分別表示去除變尺度搜索（variable-scale search，VS）和引力系數(shù)（gravity coefficient，GC）的PSOSI，圖3 展示了在部分函數(shù)上的比較結果。

從圖3 可以看出，在所有的12 個函數(shù)中，PSOSI的適應值和收斂速度均整體優(yōu)于XPSO，這是由于PSOSI 不僅利用引力系數(shù)擴展了種群的多樣性，還利用變尺度搜索提高了算法的收斂性能。同時，通過比較PSOSI-GC 和PSOSI-VS，前者在12 個函數(shù)上的收斂速度快于后者，這是因為PSOSI-GC 利用變尺度搜索增強了算法的收斂性能。另一方面，由于引力系數(shù)豐富了種群的多樣性，特別是在f13、f21、f23和f24上，即使在搜索末期，PSOSI-VS 也能夠找到更好的解。

為了更加直觀地描述引力系數(shù)對PSOSI種群多樣性的影響，以f12為例，對PSOSI-GC 和PSOSI 進行多樣性比較。圖4（a）和圖4（c）分別是這兩種算法在初始化時的種群分布圖，圖4（b）和圖4（d）分別是迭代后期這兩種算法的種群分布圖。由圖4（a）和圖4（c）可以看出，這兩種算法在初始化時的粒子分布均較為均勻。而到了迭代后期，由圖4（b）和圖4（d）可以看出，PSOSI 仍保持著較高的多樣性，粒子分布較均勻，具有較強的進化能力。而PSOSI-GC 的多樣性明顯劣于PSOSI，其種群已呈現(xiàn)出聚集狀態(tài)。

4.3 PSOSI與PSO 變體的比較

本節(jié)實驗比較PSOSI 和主流的10種PSO 變體，包括F-PSO（Frankenstein’s PSO）[18]、OLPSO（orthogonal learning PSO）[19]、DEPSO（differential evolution and PSO）[20]、PSODDS（PSO using dimension selection methods）[21]、CCPSO-ISM（competitive and cooperative PSO with information sharing mechanism）[22]、SRPSO[16]、HCLPSO（heterogeneous comprehensive learning PSO）[23]、GLPSO（genetic learning PSO）[24]、EPSO（ensemble PSO）[25]

Fig.3 Comparison of fitness with respect to different strategies圖3 不同策略的適應值比較

和XPSO[15]。這些算法均采用其原始論文中的參數(shù)設置。每種算法都獨立運行30 次，表2 至表4 展示了這11種算法的適應值均值，并以粗體和下劃線標記這些算法中的最好結果。為了體現(xiàn)各算法的綜合性能，表5 對這11種算法進行通用的弗里德曼檢測（顯著性水平α=0.05）。另外，表6 還對這11種算法進行了實時比較。

Fig.4 Population fitness distribution of PSOSI-GC and PSOSI圖4 PSOSI-GC 和PSOSI種群適應值分布

Table 2 Mean fitness comparison of 11 algorithms on 5 unimodal functions on CEC2013 test suite表2 11種算法在CEC2013 測試集5 個單峰函數(shù)上的平均適應值比較

表2 比較了這11種算法在5 個單峰函數(shù)上的平均適應值。由表2 可以看出，PSOSI 在f4上獲得最好的平均適應值，而OLPSO、PSODDS、XPSO 和GLPSO則分別在f1、f2、f3和f5上獲得最優(yōu)的平均適應值。根據(jù)表5 中的弗里德曼測試結果，可以看出PSOSI 在這5個單峰函數(shù)上獲得最佳的綜合表現(xiàn)，其排名為3.40，優(yōu)于其他10種算法。

表3 比較了這11種算法在15 個多峰函數(shù)上的平均適應值。由表3 可以看出，PSOSI 在f8、f10、f13和f18上獲得最好的平均適應值。同時，結合表5 可以看出，盡管PSOSI 在這15 個多峰函數(shù)上僅獲得次優(yōu)的綜合表現(xiàn)。與取得最優(yōu)表現(xiàn)的GLPSO 相比，PSOSI 的平均排名僅低了0.40。

表4 比較了這11種算法在8 個復合函數(shù)上的平均適應值。由表4 可以看出，PSOSI 在f24和f28這兩個函數(shù)上獲得最好的平均適應值。同時，結合表5 可以看出，PSOSI 在這8 個復合函數(shù)上獲得最佳的綜合表現(xiàn)，其排名為3.13，比次好的GLPSO 在平均排名上高了1.0。

Table 3 Mean fitness comparison of 11 algorithms on 15 multimodal functions on CEC2013 test suite表3 11種算法在CEC2013 測試集15 個多峰函數(shù)上的平均適應值比較

Table 4 Mean fitness comparison of 11 algorithms on 8 composition functions on CEC2013 test suite表4 11種算法在CEC2013 測試集8 個復合函數(shù)上的平均適應值比較

Table 5 Friedman test of 11 algorithms on CEC2013 test suite表5 11種算法在CEC2013 測試集上的弗里德曼檢測

Table 6 Time comparison of 11 algorithms on CEC2013 test suite表6 11種算法在CEC2013 測試集上的耗時比較 s

從表6 中可以看出，在f1～f5這5 個單峰函數(shù)上，PSOSI 的時間耗費僅比OLPSO 長，比其他9種PSO的變體算法快。在其他的復雜函數(shù)上，PSOSI 比起其在單峰函數(shù)上的表現(xiàn)，時間耗費排名有所下降，這是由于PSOSI需要頻繁地更新伙伴粒子，并計算引力系數(shù)，以進行社會學習。幸運的是，在3.4 節(jié)的分析中，PSOSI 的時間復雜度與標準的PSO 保持相同。同時考慮到表5 中PSOSI 出色的綜合表現(xiàn)，這些額外的時間耗費是可以接受的。

4.4 PSOSI與其他優(yōu)化算法的比較

為了進一步驗證PSOSI 的有效性，在本節(jié)中將PSOSI 和其他3種非PSO 算法進行比較，這3種算法包括CoDE（DE with composite trial vector generation strategies and control parameters）[26]、TPC-GA（GA with three-parent crossover）[27]和MABC-NS（modified ABC with neighborhood search）[28]，分別屬于差分進化算法、遺傳算法和人工蜂群算法的變體。表7 展示了這4種算法的平均適應值和通用的弗里德曼檢測（顯著性水平α=0.05）。

從表7 中可以看出，PSOSI在這28 個函數(shù)上的10個函數(shù)中取得了最好的平均適應值，這10個函數(shù)包括f3、f7、f8、f9、f10、f20、f24、f25、f27和f28。此外，PSOSI 在28個函數(shù)上以2.11 的平均排名獲得了最佳的綜合性能。

Table 7 Mean fitness comparison of PSOSI and three other optimization algorithms on CEC2013 test suite表7 PSOSI與其他3種優(yōu)化算法在CEC2013測試集上的平均適應值比較

5 結束語

本文提出了一種融入社會影響力的粒子群優(yōu)化算法。首先，每個粒子將選擇全局最優(yōu)粒子和最優(yōu)伙伴粒子作為其“社會學習”的對象，從而為每個粒子帶來更豐富的有用知識。其次，引入引力系數(shù)分別描述各榜樣帶來的影響，在保證最優(yōu)經(jīng)驗得到分享的同時，更多地是增強了種群學習的多樣性。此外，每個粒子還在各維度上進一步向其最優(yōu)伙伴粒子學習，實現(xiàn)從全局到局部的變尺度搜索，增強算法的整體收斂能力。為了驗證所提出方法的有效性，在CEC2013 測試集上將其與主流的10種PSO 變體及3種其他優(yōu)化算法進行比較。實驗結果表明，PSOSI的表現(xiàn)優(yōu)于以上其他算法。

在未來的工作中，將結合PSOSI和一些表現(xiàn)良好的演化計算或群體智能算法，考慮這些方法的優(yōu)缺點及結合點，以進一步提高復合優(yōu)化算法的性能。