教與學信息交互粒子群優(yōu)化算法

聶方鑫，王宇嘉，賈欣

（上海工程技術大學電子電氣工程學院，上海 201620）

0 引言

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［1］于1995 年由Kennedy 與Eberhart 提出，該算法以群體智能作為基礎，采用沒有體積、沒有質(zhì)量的粒子作為個體，并規(guī)定每個粒子的行為方式，使得整個種群呈現(xiàn)出復雜的特征以求解優(yōu)化問題。PSO 算法因其簡單性和強大的收縮能力被廣泛用于不同領域，并得到了極為迅速的發(fā)展和推廣。雖然PSO 算法在很多方面有著不錯的表現(xiàn)，但其具有易陷入局部最優(yōu)和優(yōu)化后期收斂慢的缺陷。為了解決上述問題，研究者提出了各種方法來提高粒子群算法的搜索效率［2-4］，主要分為兩類：

第一類，與其他優(yōu)化算法相結合。例如，文獻［5］中提出了一種改進型粒子群算法，將PSO 算法、遺傳算法和模擬退火算法三者相融合，增強了算法的收斂能力，同時也抑制了算法“早熟”；文獻［6］中將量子行為粒子群和人工蜂群算法相結合來辨識模型參數(shù)，對于有噪聲的數(shù)據(jù)，雙種群算法表現(xiàn)最好；文獻［7］中將人類學習優(yōu)化算法與PSO 算法相融合，在人類學習優(yōu)化算法指導下，增強粒子學習能力，提高PSO搜索效率；文獻［8］中提出了一種新的粒子群與混合蛙跳融合算法，采用多種群方法，在每次進化后，將各子群中最優(yōu)粒子組成新的群體，并采用混合蛙跳模式進行進化，以提高種群多樣性；文獻［9］中提出了一種融合Rosenbrock 搜索法的混合粒子群算法，利用Tent 混沌序列將種群初始化，接著對個體極值進行擾動，增強了種群多樣性，并利用Rosenbrock搜索法對全局最優(yōu)個體進行局部搜索，最終提高了解的精度。上述研究都是將算法進行融合改進，在一定程度上提高了PSO 算法的性能，但并沒有從根本上解決PSO 算法收斂能力和多樣性之間的沖突。

第二類，研究各種改進PSO 算法。例如，文獻［10］中提出了一種具有重組學習和混合變異的動態(tài)多種群粒子群優(yōu)化算法，動態(tài)地劃分了多個子種群，并融入重構粒子作為引導因子，同時對最優(yōu)個體實施混合變異、反向?qū)W習策略和鄰域擾動操作，幫助粒子快速跳出局部最優(yōu)；文獻［11］中提出了一種快速多種群粒子群多模優(yōu)化算法，采用動態(tài)半徑和種群劃分策略，同時引入拓撲機制，使種群在快速收斂和多樣性之間達到了平衡；文獻［12］中提出了一種多種群綜合學習算法，引入多種群策略以提高全局勘探能力，并采用全局學習策略更新學習樣本，增加了種群多樣性；文獻［13］中提出了一種基于多種群的自適應遷移PSO 算法，將兩種常用鄰居拓撲結構進行融合，同時使多個子種群并行進化，利用不同的加速因子組合賦予了各子種群不同的搜索特性，最終提升了算法綜合性能。上述研究都是對種群劃分策略進行了改進，分群策略雖然能改善其性能，但是子種群間的交流也影響著算法收斂能力和種群多樣性，并且粒子學習模式固定，對算法性能的提升有限。

本文提出一種教與學信息交互粒子群優(yōu)化（Teaching and Learning information interactive PSO，TLPSO）算法，該算法根據(jù)進化過程將種群動態(tài)地劃分為兩個子種群，分別使用PSO 算法和教與學優(yōu)化（Teaching-Learning-Based Optimization，TLBO）算法［14］進行迭代，利用教與學優(yōu)化算法中學習者階段進行信息交互，發(fā)揮優(yōu)勢種群長處，提升個體成績，同時分別計算個體適應度值和個體間距離，采用指標加權策略，使粒子收斂性和多樣性得到平衡，防止陷入局部最優(yōu)。

1 基本理論

1.1 粒子群優(yōu)化算法

在粒子群優(yōu)化算法中，每個優(yōu)化問題的潛在解都是搜索空間中的一個“粒子”，所有粒子都有一個速度來決定它們飛行方向和距離，粒子通過追尋當前最優(yōu)粒子，在解空間中進行搜索。在每一次迭代中，粒子在追尋全局極值的同時，也追尋個體極值來更新自己位置。設在一個D維空間中，由m個粒子組成的種群X=(x1，x2，…，xi，…，xm)，其中，第i粒子位置為xi=(xi1，xi2，…，xiD)，其速度為vi=(vi1，vi2，…，viD)。個體 極值 為pi=(pi1，pi2，…，piD)，全局極值 為pg=(pg1，pg2，…，pgD)［15］。粒子xi的速度和位置更新公式為：

其中：ω表示權重系數(shù)；vid(t)和xid(t)分別表示粒子i在第d維第t次迭代中的速度和位置大??；c1和c2是加速因子；r1，r2和r3是分布在［0，1］內(nèi)的隨機數(shù)；pid和pgd分別表示粒子最優(yōu)位置和群體最優(yōu)位置。

1.2 教與學優(yōu)化算法

教與學優(yōu)化算法由Rao 等［14］提出，它模擬了班級中教師的教學行為和一些學習者的學習行為，教師和學習者等同于進化算法中的個體。在TLBO 算法中，將種群中所有個體集合稱之為班級，班級中某個點xi=(xi1，xi2，…，xiD)稱之為一個個體，D為優(yōu)化問題的維數(shù)，當前適應值最好的個體稱之為教師，用xteacher表示。該算法分為兩個階段，分別為教學階段和學習階段，這兩個階段的目標都是為了提高每個個體的成績［16］。

在教學階段，每個個體向群體中最好的個體xteacher學習，以提高自己的成績?？紤]到教師的教學成果也受平均成績的影響，因此個體在教學階段的更新公式為：

其中：xold，i和xnew，i分別是第i個個體學習前和學習后的個體；學習因子ri=rand(0，1)；教學因子TF=round[1 +rand(0，1)]；xmean是整個種群適應度值均值。如果xnew，i的適應度值優(yōu)于xold，i，就更新xold，i，否則不更新。

在學習階段，每個個體也通過與其他個體進行交流，來提高自己的成績。具體來說，個體xi隨機選擇另一個個體xj進行交流學習。

其中：學習因子ri=U(0，1)；如果xnew，i的適應度值優(yōu)于xold，i，則更新個體，否則不更新。

2 教與學信息交互粒子群優(yōu)化算法

2.1 種群動態(tài)調(diào)整方案

為了提高算法全局搜索能力，本文采用種群動態(tài)調(diào)整方案來增加種群多樣性。首先根據(jù)式（5）和式（6）將種群動態(tài)劃分為PSO 種群（P 群）和TLBO 種群（T 群），如圖1（a）所示。

其中：NP和NT分別是P 群和T 群種群規(guī)模；NP是整個種群規(guī)模；a1～a4是影響因子，a1和a4是調(diào)整P 群最終占比和初始占比的影響因子，a1越大說明算法后期T 群所占比例越大，a4越大說明算法初期P 群所占比例越大，a2和a3調(diào)整P 群增長速度，a2和a3越大說明P 群增長速度越快；iter是當前迭代次數(shù)；MaxIt是最大迭代次數(shù)。

在算法迭代初期，P 群中粒子采用PSO 算法進化；而在T群中，從中挑選出NT1個粒子組成A 組，只采用TLBO 算法中學習階段進行進化；剩下的粒子組成B 組，采用完整TLBO 算法進化，如圖1（b）所示。因為在P 群和T 群B 組中粒子會向全局極值學習，導致多樣性逐漸喪失，使算法陷入局部最優(yōu)；而在T 群A 組中的粒子向除自己之外任何粒子學習，相對于使用PSO 算法，可有效地提高全局搜索能力［17］。

在算法迭代中期，P 群種群規(guī)模比T 群小。隨著迭代次數(shù)增加，P 群種群規(guī)模逐漸變大，T 群種群規(guī)模逐漸變小，如圖1（c）所示。在T 群A 組中處于TLBO 算法學習階段的粒子具有良好的全局搜索能力，因此在調(diào)整子種群規(guī)模時，將這些粒子分配給P 群，但是在T 群中進化的粒子缺失速度這一參數(shù)，受PSO 算法位置更新策略啟發(fā)，由式（7）求出P 群中被分配來的粒子速度：

在算法迭代后期，T 群A 組中粒子都已經(jīng)分配給P 群，如圖1（d）所示。此時由于在P 群和T 群B 組中粒子會向全局極值學習，所以可以使粒子在極值點附近進行更精細的局部搜索，提高收斂速度。

圖1 子種群規(guī)模隨迭代次數(shù)變化的動態(tài)過程Fig.1 Dynamic process of subpopulation size changing with number of iterations

由上面描述可知，這兩個種群規(guī)模大小會影響算法全局探索和局部開發(fā)。因此，本文采用動態(tài)調(diào)整方案來控制進化過程中兩個種群規(guī)模，使所提算法在進化前期可以保證種群多樣性，提高全局搜索能力，進化后期可以提高收斂速度。

考慮到在整個種群進化過程中全局最優(yōu)位置對個體運動的影響［18］，本文對PSO 算法中個體速度更新公式如式（8）所示：

其中：pp，gd是P 群全局最優(yōu)位置；pgd是整個種群的全局最優(yōu)位置；b1和b2是影響因子，使c3從0.5 線性增長到1.5。

2.2 種群信息交互

將整個種群動態(tài)劃分為兩個子種群后，子種群之間信息交互也影響著算法的效果，因此采用了兩階段學習策略使粒子互相交流學習。

在第一階段，如圖2 右下角所示：T 群內(nèi)部A 組和B 組進行交流學習。首先比較兩個小組適應度值大小，擁有最小適應度值小組稱之為優(yōu)秀小組，另一個小組為普通小組。然后從優(yōu)秀小組中隨機挑選一個學習粒子xl，普通小組中所有粒子使用TLBO 算法學習階段的規(guī)則向?qū)W習粒子xl學習，并產(chǎn)生新后代。在T 群內(nèi)部學習后，可以使T 群保持良好的全局探索能力，同時采用分組措施，可以防止因為粒子被分配到P 群而導致的信息流失，并且在算法后期階段，還可以提升整個種群收斂速度，其更新公式為：

其中：xo，old，i和xo，new，i分別是A 組或者B 組中第i個個體學習前和學習后的個體；如果A 組擁有最小適應度值，則o為B，如果B 組擁有最小適應度值，否則o為A；xo，i表示A 組或者B 組中第i個粒子。

在第二階段，如圖2 所示，進行P 群和T 群交流學習。比較P 群和T 群適應度值大小，將擁有最小適應度值粒子稱之為xmin，并且擁有最小適應度值種群稱之為優(yōu)勢種群，另一個種群為普通種群。粒子xmin使用TLBO 算法教學階段的規(guī)則向普通種群中所有粒子進行教學，其更新公式為：

圖2 子種群的信息交互Fig.2 Information interaction of subpopulations

其中：xh，old，i和xh，new，i分別是P 群或T 群中第i個個體學習前和學習后的個體；如果P 群擁有最小適應度值，則h為T，如果T群擁有最小適應度值，則h為P；xaver為普通種群適應度值均值。

整個種群在進行信息交互后，算法具有了良好的全局探索能力，又提高了收斂速度。

2.3 收斂性和多樣性指標

為了使粒子收斂能力和多樣性在進化過程中保持平衡，引入收斂性和多樣性指標，分別用來計算粒子與最近鄰粒子以及全局最優(yōu)點s的距離。首先利用種群中適應度函數(shù)最大值和最小值對粒子xi進行歸一化，這種歸一化方法有助于消除振幅影響［19］。粒子xi歸一化適應度函數(shù)f′(xi)為：

其中fmax和fmin分別是整個種群適應度函數(shù)最大值和最小值。

歸一化多樣性距離D反映粒子xi與最近鄰粒子的距離，D較大則表示粒子xi距離它的鄰居較遠：

其中：dismax和dismin分別是整個種群中粒子之間最大和最小的歐氏距離，f″(xi)表示粒子xi與最近鄰粒子的適應度值之差，如式（13）所示：

歸一化收斂距離C反映粒子xi相對于理想點收斂能力［19］，C較大則說明粒子xi越接近理想點，如式（14）所示：

其中dis(xi)表示f′(xi)到理想點的歐氏距離。如式（15）所示：

對所有粒子按照式（11）～（15）進行收斂性和多樣性計算后，將所有粒子收斂性和多樣性按照式（16）進行加權：

將最大的mean(xi)值記為xleader。在t+1 次迭代后，如果xleader值沒有更新，算法可能缺失多樣性，并且陷入局部最優(yōu)。因此，對所有粒子進行多項式變異：

其中：μi是分布在［0，1］內(nèi)的隨機數(shù)；η是分布指數(shù)，實驗中η取11［20］。

2.4 TLPSO算法流程

TLPSO 算法具體步驟如下：

1）初始化所有粒子，種群大小為NP。

2）利用式（5）～（6）計算P 群、T 群大小，使用隨機抽樣的方法從T 群中選出相應粒子分配給P 群。

3）判斷粒子是否屬于P 群，如果是，則按照PSO 規(guī)則進行迭代：如果不是，則粒子屬于T 群，再次判斷粒子是否屬于T 群中A 組；如果是，則按照TLBO 算法教學階段進行迭代。如果不是，粒子屬于T 群B 組，則按照TLBO 規(guī)則進行迭代。

4）信息交互第一階段：T 群中A 組與B 組之間交流，普通小組向優(yōu)秀小組中的學習粒子xl學習并產(chǎn)生后代。信息交互第二階段：種群之間交流時，普通種群向優(yōu)勢種群中的粒子xmin學習產(chǎn)生后代。

5）先按照式（11）～（15）進行計算粒子收斂性和多樣性，再根據(jù)式（16）判斷xleader是否更新，沒有則進行多項式變異。

6）如果滿足迭代終止條件，則終止迭代，輸出全局最優(yōu)解；否則轉(zhuǎn)到步驟2）。

3 仿真實驗

3.1 測試函數(shù)

為了測試改進算法性能，本文采用15 個典型測試函數(shù)進行測試，給出了15 個函數(shù)的數(shù)學描述：

F1 函數(shù)：

其中：xi∈[-100，100]，維數(shù)D取30 和100，Global(fmin)為0。

F2 函數(shù)：

其中：xi∈[-10，10]，維數(shù)D取30 和100，Global(fmin)為0。

F3 函數(shù)：

其中：xi∈[-100，100]，維數(shù)D取30 和100，Global(fmin)為0。

F4 函數(shù)：

其中：xi∈[-100，100]，維數(shù)D取30 和100，Global(fmin)為0。

F5 函數(shù)：

其中：xi∈[-30，30]，維數(shù)D取30 和100，Global(fmin)為0。

F6 函數(shù)：

其中：xi∈[-100，100]，維數(shù)D取30 和100，Global(fmin)為0。

F7 函數(shù)：

其中：xi∈[-1.28，1.28]，維數(shù)D取30 和100，Global(fmin)為0。

F8 函數(shù)：

其中：xi∈[-5.12，5.12]，維數(shù)D取30 和100，Global(fmin)為0。

F9 函數(shù)：

其中：xi∈[-32，32]，維數(shù)D取30 和100，Global(fmin)為0。

F10 函數(shù)：

其中：xi∈[-600，600]，維數(shù)D取30 和100，Global(fmin)為0。

F11 函數(shù)：

其中：xi∈[-5，5]，維數(shù)D取2，Global(fmin)為-1.031 6。

F12 函數(shù)：

其中：xi∈[-5，5]，維數(shù)D取4，Global(fmin)為0.000 307。

F13 函數(shù)：

其中：xi∈[0，1]，維數(shù)D取3，Global(fmin)為-3.86。

F14 函數(shù)：

其中：xi∈[0，1]，維數(shù)D取6，Global(fmin)為-3.32。

F15 函數(shù)：

其中：xi∈[-50，50]，維數(shù)D取30 和100，Global(fmin)為0。

3.2 算法設置

將提出的TLPSO 算法與粒子群優(yōu)化算法（PSO）、協(xié)方差矩陣自適應進化策略（Covariance Matrix Adaptation Evolutionary Strategy，CMA-ES）算 法［21］、相量粒子群優(yōu)化（Phasor PSO，PPSO）算法［22］、混合灰狼粒子群（Hybrid PSO and Grey Wolf Optimizer，PSOGWO）算法［23］、混合引力搜索的粒子群優(yōu)化算法（PSO and Gravitational Search Algorithm，PSOGSA）［24］、重選精英個體的非線性收斂灰狼優(yōu)化算法EGWO（improved Grey Wolf Optimizer algorithm using nonlinear convergence factor and Elite re-election strategy）［25］進行仿真對比。在實驗中，所有算法的相關參數(shù)如表1 所示。對于所有的算法，群體大小設置為100，最大迭代次數(shù)是1 000。每種算法在實驗中獨立運行30 次，統(tǒng)計每個算法的測試函數(shù)平均值和標準差，平均值能夠體現(xiàn)出算法的收斂能力，方差體現(xiàn)出算法的穩(wěn)定性。

表1 不同算法參數(shù)設置Tab.1 Parameter settings for contrast algorithms

3.3 結果分析

表2～3 和圖3 分別為改進算法與其他六種算法的對比結果和對照圖。表格中：Ave 和Std 是30 次獨立運行后所獲得的平均值和標準差，加粗體字表示算法獲得的最優(yōu)值。圖3中，除了測試函數(shù)F11、F13 和F14，其余測試函數(shù)的縱軸是采用對數(shù)處理后的數(shù)量級。

圖3 低維收斂曲線對比Fig.3 Comparison of low dimensional convergence curves

表2 低維測試函數(shù)結果對比Tab.2 Experimental results comparison of low dimensional benchmark functions

從低維測試函數(shù)表3 中可以看到在測試函數(shù)F1、F2、F3、F4、F6、F7、F8、F9、F13、F14、F15 上，本文提出的TLPSO 算法性能明顯優(yōu)于其他六種算法，并且在測試函數(shù)F8、F10、F11、F12、F13、F14 上搜索到理論值，僅測試函數(shù)F5 上的優(yōu)化性能微弱于CMA-ES。在12 個測試函數(shù)上，TLPSO 算法性能都優(yōu)于PSOGWO 和PSOGSA，這說明粒子群優(yōu)化算法與教與學優(yōu)化算法的結合比上述兩種算法優(yōu)化效果更好，這是因為采用了指標加權策略，讓粒子收斂能力和多樣性在進化過程中保持平衡，提高了局部搜索能力，使TLPSO 算法可以獲得更好的平均最優(yōu)值。除了測試函數(shù)F4 和F12 以外，TLPSO 算法的標準差對于其他六種算法都是最好的，這表明TLPSO 算法具有良好的穩(wěn)定性。

在表3 中，可以看到在多峰函數(shù)F10 上，CMA-ES、PSOGWO、PSOGSA、EGWO 和TLPSO 算法都搜索到了理論值0，但是在圖4 的F10 上可以看出，TLPSO 算法收斂速度明顯優(yōu)于其他三種算法，在不到200 次迭代中就可以搜索到理論值0。對于測試函數(shù)F1、F2、F3、F4、F6、F9、F15 來說，TLPSO算法收斂精度和收斂速度都遠超其他六種算法；而對于測試函數(shù)F7、F8、F12 和F14 來說，雖然TLPSO 算法前期收斂速度較慢，但是在收斂精度上也優(yōu)于其他六種算法。這是由于教與學優(yōu)化算法學習者階段能夠讓粒子之間相互學習，提高全局搜索能力，從而探索到更多的可行域，使算法在求解精度上有了顯著優(yōu)勢，并且通過動態(tài)調(diào)整種群規(guī)模，使TLPSO 算法在迭代后期仍保持良好的收斂速度。從高維測試函數(shù)表4 中可以看到，在測試函數(shù)F1、F2、F3、F4、F5、F7、F8、F9、F10、F15 上，TLPSO 算法相較于其他對比算法仍能找到更好的解，并且其算法性能相對于低維測試函數(shù)也沒有明顯下降，說明TLPSO 算法對維數(shù)不敏感。綜上所述，TLPSO 算法與其他六種算法相比，具有更好的收斂性能和優(yōu)化精度。

表3 高維測試函數(shù)結果對比Tab.3 Experimental results comparison of high dimensional benchmark functions

圖4 是七種算法在低維測試函數(shù)F1、F2、F3、F4、F5、F6、F7、F9 和F15 上的最優(yōu)解集箱線圖，可以更加直觀地對比七種算法在獨立運行30 次后，最優(yōu)解集分布情況。從整體上看，算法TLPSO 在測試函數(shù)F1、F2、F3、F4、F6、F7、F9 和F15上，都遠比其他五種算法更接近理想值，在測試函數(shù)F5 上稍弱于算法CMA-ES，與表3 數(shù)據(jù)和圖4 曲線一致，說明在大多數(shù)測試函數(shù)上，該算法收斂性能都遠優(yōu)于其他算法。從最優(yōu)解集分布情況來看，算法TLPSO 在大部分測試函數(shù)上分布較小而其他算法分布較大，說明對大部分測試函數(shù)來說，算法TLPSO 的收斂性和穩(wěn)定性效果更佳。因此，算法TLPSO 具有收斂速度快、尋優(yōu)能力強、穩(wěn)定性好的優(yōu)點。

圖4 低維最優(yōu)解統(tǒng)計分布Fig.4 Low dimensional optimal solution statistical distribution

4 結語

針對單一種群在解決高維問題中收斂速度較慢和多樣性缺失問題，提出了一種基于教與學信息交互粒子群優(yōu)化算法。通過將種群動態(tài)地劃分為兩個子種群，分別采用粒子群優(yōu)化算法和基于教與學的優(yōu)化算法，通過子種群之間信息交互和收斂性和多樣性指標，使粒子收斂能力和多樣性在進化過程中得到平衡。為了驗證TLPSO 的有效性，通過15 個Benchmark 測試函數(shù)，與PSO、CMA-ES、PPSO、PSOGWO、PSOGSA 和EGWO 算法在低維和高維測試函數(shù)上進行比較，實驗結果驗證了TLPSO 算法在收斂精度和收斂速度方面有著較為明顯的改善效果。