張 鑫，鄒德旋，沈 鑫

(江蘇師范大學(xué) 電氣工程及自動化學(xué)院，江蘇 徐州 221116)(*通信作者電子郵箱ZhangXin_1994@126.com)

0 引言

為了彌補粒子群優(yōu)化算法(Particle Swarm Optimization， PSO)的缺陷，各學(xué)者提出了不同的改進方案，目前主要包含以下六個研究熱點：

1)粒子群算法原理研究。2018年，Xu等[1]使用鞅理論對粒子群算法的收斂性進行分析，結(jié)果顯示粒子群優(yōu)化算法達到全局最佳概率，并證明量子粒子群優(yōu)化算法也具有全局收斂性；胡旺等[2]分析了速度項對算法收斂性的影響和算法陷入局部最優(yōu)解的原因，并根據(jù)分析的結(jié)論對粒子群算法進行改進，提出簡化粒子群優(yōu)化算法(Simple Particle Swarm Optimization， SPSO)和帶極值擾動的粒子群算法，性能均十分優(yōu)秀。

2)粒子群算法參數(shù)改進。2017年，Li等[3]提出一種具有適應(yīng)性調(diào)整參數(shù)的粒子群優(yōu)化算法，可以快速收斂到近似最優(yōu)點，實驗結(jié)果使用Wilcoxon符號秩檢驗法分析，粒子群算法的收斂速度和解的質(zhì)量都有了提升；2013年，周俊等[4]對粒子群算法的權(quán)重改進進行了簡單的歸類綜述，將權(quán)重改進分為固定權(quán)重和時變權(quán)重兩大類，自適應(yīng)粒子群算法(Self-adjusted Particle Swarm Optimization algorithm， SelPSO)被歸類為時變權(quán)重中的基于反饋信息的改進中。

3)粒子群算法拓撲結(jié)構(gòu)改進。2015年，Netjinda等[5]受八哥鳥的集群反應(yīng)啟發(fā)，利用集體響應(yīng)機制令當(dāng)前粒子的速度和位置受到相鄰七個粒子的影響，從而增加粒子多樣性；2016年，Liu等[6]分析了拓撲度與其他參數(shù)對粒子群算法性能的影響，基于結(jié)論提出了兩個公式來幫助選擇最佳拓撲或參數(shù)，提高了PSO的易用性和適用性；同年，Wang等[7]提出了一種動態(tài)錦標(biāo)賽拓撲策略，該拓撲策略利用從種群中隨機選擇的幾個較好方案指導(dǎo)每個粒子的搜索，結(jié)果表明，這種拓撲結(jié)構(gòu)可以良好地運用于人工神經(jīng)網(wǎng)絡(luò)優(yōu)化。

4)粒子群算法的迭代公式改進。2017年，Zou等[8]使用全局定位更新粒子位置，并在搜索后期使用基于均勻分布的隨機化分布方法增加粒子群多樣性，避免早熟收斂，仿真結(jié)果顯示這種改進的迭代公式可以更好地應(yīng)用于電力系統(tǒng)經(jīng)濟調(diào)度；2016年，趙志剛等[9]使用了一種均值粒子群算法，并在此基礎(chǔ)上對權(quán)重進行自適應(yīng)改進，得到一種基于自適應(yīng)慣性權(quán)重的均值粒子群算法(Mean Particle Swarm Optimization algorithm based on Adaptive inertia Weight， MAWPSO)。

5)混合粒子群算法研究。2015年，羌曉清等[10]將模擬退火和粒子群算法的混合改進算法應(yīng)用于測試點優(yōu)化，與遺傳算法和貪婪算法相比，該方法具有更好的故障檢測率和隔離率；2016年，汪沖等[11]提出一種將蟻群算法與粒子群算法混合的新算法，并將其應(yīng)用于旅行商問題的求解。

6)粒子群算法實際應(yīng)用。2017年，尚俊娜等[12]提出將利用正弦函數(shù)改進慣性權(quán)重的粒子群算法(Particle Swarm Optimization algorithm for improved weight using Sine function， SinPSO)應(yīng)用于優(yōu)化無線傳感網(wǎng)絡(luò)節(jié)點室內(nèi)定位；2018年，Wang等[13]將具有對數(shù)似然比的混沌粒子群優(yōu)化粒子濾波算法用于GPS接收機自主完整性監(jiān)測，與單純的粒子群優(yōu)化粒子濾波算法相比，實驗中有效地檢測和隔離了非高斯測量噪聲條件下的衛(wèi)星故障。

本文提出了一種適用于慣性權(quán)重模型，并引入交叉因子和簡化思想的自適應(yīng)隨機權(quán)重二范數(shù)粒子群算法——HTPSO。該算法應(yīng)用于無約束問題尋優(yōu)，其基本思想是：在消去影響收斂速度項的基礎(chǔ)上利用二范數(shù)將粒子分層，并在迭代過程中加入交叉因子，這樣不但增強了算法在局部搜索中的能力，保證了種群的多樣性，還可以幫助粒子跳出局部最優(yōu)，防止早熟收斂和后期粒子過于密集。利用8個常用測試函數(shù)對其進行仿真實驗，并與四種近期提出的改進粒子群算法進行比較，包括：利用正弦函數(shù)改進慣性權(quán)重的粒子群優(yōu)化算法(SinPSO)、自適應(yīng)粒子群優(yōu)化算法(SelPSO)、基于自適應(yīng)慣性權(quán)重的均值粒子群優(yōu)化算法(MAWPSO)、簡化粒子群優(yōu)化算法(SPSO)。結(jié)果顯示，本文提出的改進粒子群算法在全局搜索上表現(xiàn)更加突出。

1 相關(guān)研究

1.1 利用正弦函數(shù)改進權(quán)重的粒子群算法

粒子群算法最初是為實數(shù)值問題而設(shè)計的，后來，該算法逐步擴展到解決二進制和離散問題。原始粒子群優(yōu)化算法由以下兩個公式組成：

(1)

(2)

這兩個公式的數(shù)學(xué)描述為：設(shè)在一個n維的搜索空間中，第i個粒子的位置為xi=(xi1,xi2, …,xin)T，其中i∈[1,m]，m是種群數(shù)量，其速度為vi=(vi1,vi2, …,vin)T，它的個體歷史最優(yōu)解為pi=(pi1,pi2, …,pin)T，種群的全局最優(yōu)解為gn=(g1,g2, …,gn)T。t為當(dāng)前迭代次數(shù)；T是最大迭代次數(shù)；r1和r2是分布在[0, 1]的隨機數(shù)；c1和c2是認知與社交因子。此外，為了使粒子速度不至于過大，可設(shè)置速度上限Vmax，即當(dāng)式(1)中vin>Vmax時取vin=Vmax，vin<-Vmax時取vin=-Vmax。

為了平衡全局和局部搜索能力，令算法盡可能跳出局部最優(yōu)，引入了慣性權(quán)重ω，取值范圍為[0, 1]，改進后的算法便是常用的經(jīng)典粒子群優(yōu)化算法。慣性權(quán)重越大，全局搜索能力越強，局部搜索能力弱；反之，則全局搜索能力變?nèi)?，局部搜索能力增強。引入慣性權(quán)重后的式(1)變?yōu)槭?3)形式：

(3)

本文實驗中為了驗證算法有效性使用的是利用正弦函數(shù)改進慣性權(quán)重的粒子群算法。該改進方式由尚俊娜等[12]在2017年提出，慣性權(quán)重的函數(shù)形式為：

(4)

其中：ωmax為最大慣性權(quán)重，ωmin為最小慣性權(quán)重，T是最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。

SinPSO算法步驟如下：

步驟1 初始化。設(shè)置最大迭代次數(shù)、種群數(shù)量、認知與社交因子、初始和最終慣性權(quán)重、粒子速度上限，初始化隨機產(chǎn)生粒子初始位置。

步驟2 根據(jù)適應(yīng)度函數(shù)計算粒子適應(yīng)度。

步驟3 將每個粒子的當(dāng)前適應(yīng)度與其自身最優(yōu)解Pbest進行比較。如果適應(yīng)度大于Pbest，則令當(dāng)前適應(yīng)度等于Pbest，否則不改變。再將此時的適應(yīng)度與全局最優(yōu)解Gbest比較，如果大于Gbest，則令其等于Gbest，否則不改變。

步驟4 利用式(4)改變慣性權(quán)重ω。

步驟5 利用式(2)和式(3)改變粒子的位置和速度，并控制速度范圍。

步驟6 檢查是否達到理論最優(yōu)解或最大迭代次數(shù)，若未達到則返回步驟2，直到達到理論最優(yōu)解或者完成最大迭代次數(shù)。

1.2 自適應(yīng)粒子群算法

自適應(yīng)粒子群算法也是一種對慣性權(quán)重進行改進的算法。粒子群算法在實現(xiàn)尋優(yōu)時，每個粒子追逐優(yōu)秀粒子前進，在收斂后期大都聚集在一起，收斂速度會急速減慢，極易陷入局部最優(yōu)。為了有效利用慣性權(quán)重的作用，有學(xué)者提出了自適應(yīng)粒子群算法。該改進方法是將1.1節(jié)中提到的慣性權(quán)重線性變化公式(4)用式(5)替換，算法步驟不改變：

(5)

式中：ωmax和ωmin為最大和最小權(quán)重，xin為當(dāng)前粒子適應(yīng)度，favg為粒子的平均適應(yīng)度，fmin為粒子的最小適應(yīng)度。

當(dāng)粒子的當(dāng)前適應(yīng)度大于平均適應(yīng)度時，算法一般在尋優(yōu)初期，慣性權(quán)重賦予一個較大的值，有利于算法的全局尋優(yōu)；隨著算法公式的迭代，當(dāng)前適應(yīng)度小于等于平均適應(yīng)度時，慣性權(quán)重則根據(jù)當(dāng)前粒子適應(yīng)度改變，使算法更利于局部尋優(yōu)，加速收斂。這樣的改進不但加速了粒子群算法的收斂，而且提高了尋優(yōu)精度。

1.3 基于自適應(yīng)慣性權(quán)重的均值粒子群算法

2016年，趙志剛等[9]提出了MAWPSO。在迭代時，先將得到的適應(yīng)度值進行從小到大的排序，分別計算前半部分和后半部分的適應(yīng)度平均值，令粒子與這兩個平均值進行比較，從而將所有粒子分為三部分，每一部分使用不同的權(quán)重。其權(quán)重方程可表示如下：

(6)

其中：favg1表示當(dāng)前迭代中前半部分平均值，favg2則表示后半部分的平均值。因為在計算平均值之前進行了排序，所以必然有favg1favg2表示粒子遠大于理論最優(yōu)，則給它較大慣性權(quán)重，令粒子能更快地跳出此區(qū)域；介于兩者之間時則使用[0.4, 0.6]的隨機數(shù)賦給慣性權(quán)重。

文獻[9]中的改進粒子群算法使用均值粒子群算法的迭代公式，速度迭代公式可參考式(7)。

(7)

均值粒子群算法即將原本認知項中的個體最優(yōu)和社交項中的全局最優(yōu)用兩者的線性組合代替。

文獻[9]的測試函數(shù)檢驗展示了尋優(yōu)結(jié)果和函數(shù)進化曲線，實驗表明MAWPSO細致地分開了粒子等級，兩種改進策略的組合提高了函數(shù)收斂速度和全局搜索能力。

1.4 簡化粒子群算法

Clere[14]在其論文中證明了原始粒子群的搜索過程與粒子的速度項無關(guān)。運用這一理論，2007年胡旺等[2]提出了一種簡化粒子群算法，該改進算法只使用一個公式進行迭代，即放棄了原始粒子群算法的速度公式，僅使用位置公式完成進化過程。其迭代公式如下：

(8)

文獻[2]對簡化算法的收斂性進行了證明，數(shù)據(jù)顯示該算法具有進化速度快、搜索效率高的特點。但是速度項的丟失令粒子的多樣性變得較差，這個現(xiàn)象帶來的后果便是在解決一些具有陷阱或者峰值較多的函數(shù)時算法極容易陷入局部最優(yōu)解，這個缺陷將在第3章中的大量仿真數(shù)據(jù)中有所展示。

2 含交叉項的混合二范數(shù)粒子群算法

本文提出的改進策略主要包含三部分：1)利用二范數(shù)原理對其粒子群的速度迭代公式進行改變，提出二范數(shù)粒子群算法，并通過Clere[14]的理論簡化；2)通過當(dāng)前粒子位置與歐氏距離的比較，令慣性權(quán)重有一定規(guī)律的隨機分布；3)與差分進化算法的交叉策略結(jié)合。

為了粒子收斂后期粒子不至于過分聚集而造成收斂緩慢，本文利用粒子目前所在位置與此次迭代中個體最優(yōu)位置的“歐氏距離”，即二范數(shù)，平衡社交項對粒子速度的影響。改進的粒子群速度迭代公式如下：

(9)

(10)

Rt在每次迭代時都是一個定值，都可以看作一個常數(shù)。則在迭代中，粒子受Gbest影響情況可繪制如圖1所示。

圖1 二范數(shù)粒子群算法中粒子受Gbest影響圖

權(quán)重也參考歐氏距離Rt進行改進，公式如下：

(11)

ωmax和ωmin與式(5)中的最大和最小權(quán)重意義相同，r是一個在區(qū)間[0,1]中的隨機數(shù)，t是當(dāng)前迭代次數(shù)，T是最大迭代次數(shù)。如果當(dāng)前粒子位置小于此次迭代的歐氏距離時，令慣性權(quán)重按照公式隨機分布；否則，賦予權(quán)重一個較小的值，讓粒子盡量減少活動范圍，經(jīng)過多次實驗，權(quán)重在[0.2,0.4]時效果最佳，本文取0.3作為較小的權(quán)重。假設(shè)迭代次數(shù)為100時，權(quán)重分布圖如圖2所示。

這樣的權(quán)重分布可以讓算法始終保持活力，避免過于收斂，而且權(quán)重在逐漸變大的同時還保持一種分散變化的趨勢，足以保證搜索過程中粒子的多樣性。

將二范數(shù)粒子群算法的速度迭代公式與位置迭代公式合并為一個公式如下：

(12)

圖2 隨機權(quán)重分布圖

根據(jù)Clere[14]對粒子群算法中速度項與算法性能的研究，本文中也省去式(12)中的速度項，并在簡化公式的第一項前添加權(quán)重，如此便可以將原本的兩個迭代公式簡化成一個，這樣的簡化操作可以減少粒子群算法的搜索時間。改進后的公式可以參考式(13)：

(13)

繼這兩步改進之后插入交叉因子。通過隨機數(shù)與不斷改變的交叉因子進行比較，在一定概率下將當(dāng)前粒子與自身曾經(jīng)搜索到的最優(yōu)解進行交換，粒子交叉公式可參考式(14)：

(14)

CR=CRinit-(CRinit-CRfin)2×(t/T)2

(15)

其中CRinit和CRfin分別是初始交叉率和最終交叉率。當(dāng)?shù)_始時，初始的交叉率是一個較大的值，可以令粒子更加活躍，而迭代后期，雖然還是通過隨機數(shù)與交叉率的比較改變當(dāng)前粒子位置，但是較大的交叉率可能會使粒子過于頻繁地交換，反而會打亂粒子群算法本來的收斂軌跡，故本文設(shè)置交叉率隨著迭代次數(shù)的增加逐漸減小。

該算法結(jié)構(gòu)簡單，所需設(shè)置的參數(shù)較少。實現(xiàn)步驟如下：

步驟1 初始化。設(shè)置最大迭代次數(shù)、種群數(shù)量、認知因子、最大和最小慣性權(quán)重、初始和最終交叉率、粒子速度上限，初始化隨機產(chǎn)生粒子初始位置。

步驟2 根據(jù)適應(yīng)度函數(shù)計算粒子適應(yīng)度，通過比較獲得個體歷史最優(yōu)解Pbest和全局最優(yōu)解Gbest。

步驟3 利用式(10)計算粒子與當(dāng)前個體最優(yōu)解的歐氏距離。

步驟4 利用式(11)改變慣性權(quán)重ω。

步驟5 通過式(15)計算當(dāng)前迭代中的交叉率，并利用式(14)在一定概率下將粒子當(dāng)前位置與個體最優(yōu)位置進行交叉。

步驟6 利用式(13)更新粒子的當(dāng)前位置，并控制粒子位置不超過函數(shù)解范圍。

步驟7 檢查是否達到理論最優(yōu)解或最大迭代次數(shù)，若未達到則返回步驟2，直到達到理論最優(yōu)解或者完成最大迭代次數(shù)。

3 仿真實驗與數(shù)據(jù)分析

3.1 測試函數(shù)

本文改進算法主要應(yīng)用于無約束問題尋優(yōu)。為了全面測試算法的性能，本文利用8個測試函數(shù)，并分別讓SinPSO、SelPSO、MAWPSO、SPSO和HTPSO對這8個測試函數(shù)進行尋優(yōu)搜索，最后將5個算法搜索到的一系列數(shù)據(jù)比較分析。

以下給出了這8個函數(shù)的具體公式，按照首字母排序。因為函數(shù)版本多樣，為了統(tǒng)一，本文中展示的函數(shù)可能在形式上略有變化，但不改變實現(xiàn)效果。具體可以參考文獻[15-16]引用的測試函數(shù)。容忍度為搜索100維問題時期望搜索到的精度，該容忍度將在3.3.4節(jié)計算成功率和平均迭代次數(shù)時使用。

1)Ackley’s Path Function：

定義域為[-32,32],理論最優(yōu)解為f1(0,…,0)=8.8E-16,容忍度為10-15。

2)Inverted Cosine Wave Function：

定義域為[-5,5]，理論最優(yōu)解為f2(0,…,0)=-n+1，容忍度為-99。

3)Quartic Function, i.e, noise：

定義域為[-1.28,1.28]，理論最優(yōu)解為f3(0,…,0)=0，容忍度為10-2。

4)Rastrigin Problem：

定義域為[-5.12,5.12]，理論最優(yōu)解為f4(0,…,0)=0，容忍度為0。

5)Schwefel’s Problem 1.2:

定義域為[-100,100]，理論最優(yōu)解為f5(0,…,0)=0，容忍度為10-290。

6)Schwefel’s Problem 2.21：

定義域為[-100,100]，理論最優(yōu)解為f6(0,…,0)=0，容忍度為10-290。

7)Schwefel’s Problem 2.22：

定義域為[-10,10]，理論最優(yōu)解為f7(0,…,0)=0，容忍度為10-220。

8)Sphere Function：

定義域為[-100,100]，理論最優(yōu)解為f8(0,…,0)=0，容忍度為10-250。

以上函數(shù)包含以Sphere Function為代表的單峰函數(shù)；以Rastrigin Problem為代表的含有大量局部解的復(fù)雜多峰函數(shù)；以及一些特殊函數(shù)比如有噪聲干擾的Quartic Function等；Ackley’s Path Function和Inverted Cosine Wave Function的理論最優(yōu)解為非零解。這些函數(shù)包含了大部分可能出現(xiàn)的情況。

3.2 參數(shù)設(shè)置與仿真環(huán)境

為了保證算法比較實驗中的公正性與科學(xué)性，性能檢測前應(yīng)合理設(shè)置參數(shù)。

粒子群算法結(jié)構(gòu)簡單，需要設(shè)置的參數(shù)較少，且尋優(yōu)能力強大，在搜索簡單問題時只需要將種群數(shù)量設(shè)置在40個左右，只有在搜索復(fù)雜問題時才需要適當(dāng)增加種群數(shù)量。本文使用的是基本的測試函數(shù)進行算法性能檢驗，所以均將種群數(shù)量設(shè)置為40；根據(jù)文獻[17]的結(jié)論，除了MAWPSO根據(jù)原文要求將最大慣性權(quán)重設(shè)置為0.6外，文中其他算法的最大權(quán)重和最小權(quán)重分別設(shè)置為0.9和0.4；參考文獻[18]推論1，5個對比算法在仿真中認知因子和社交因子均設(shè)置為2；為了保證結(jié)果具有普遍性，本文實驗令每個算法均搜索同一個函數(shù)30次。

表1是本次仿真實驗的參數(shù)設(shè)置表。A1～A5分別表示SinPSO、SelPSO、MAWPSO、SPSO和HTPSO；NR表示算法搜索函數(shù)次數(shù)；m是粒子個數(shù)；T表示最大迭代次數(shù)，且不同維度問題最大迭代次數(shù)設(shè)置也不同，10D、50D和100D分別表示10維、50維和100維，這三個維度對應(yīng)的最大迭代次數(shù)分別是100、500和1 000；c1,2是算法的認知因子和社交因子；ωmax和ωmin分別是最大權(quán)重和最小權(quán)重；CRinit和CRfin是本文提出的改進算法HTPSO的初始和最終交叉率。

表1 參數(shù)設(shè)置

本文中的仿真實驗均在Matlab R2014a中進行，PC內(nèi)存4.00 GB，CPU速度為2.26 GHz。

3.3 與其他算法的比較與分析

對比實驗包括三個部分：1)令5種粒子群算法分別搜索10維、50維、100維的測試函數(shù)，比較搜索出來的最小值、平均值等，并使用T-test對搜索得到的100維問題結(jié)果進行差異性檢驗，有差異地使用勝率進一步比較；2)在不改變算法迭代次數(shù)的前提下，比較5種算法在函數(shù)維度從1維增加到100維時性能的變化情況；3)參考精度要求，計算每個算法搜索同一個測試函數(shù)30次后達到本文實驗期望精度的成功率和平均迭代次數(shù)。

3.3.1 維度比較結(jié)果與分析

觀察算法性能最直接的方法就是比較算法對不同維度測試函數(shù)搜索的結(jié)果，這也是目前最實用的方法之一。當(dāng)測試函數(shù)維度增加時，問題解空間隨之變大，搜索難度也會上升。如果某個算法不但在解決低維度問題時得到較好的解，而且在解決高維度問題時效果也不差，則可以說該改進算法的性能非常好。

表2是5個改進算法對10維和50維問題的搜索結(jié)果。因為啟發(fā)式算法的隨機性，所以每次搜索的結(jié)果可能不相同。表2中，最小值是該算法搜索這個維度問題30次后的最小結(jié)果；平均值是30個結(jié)果的平均，更具有普遍性，可以更科學(xué)地展示出能搜索到的最優(yōu)范圍；標(biāo)準(zhǔn)差可以表現(xiàn)30次結(jié)果的波動性，標(biāo)準(zhǔn)差越小則表示該算法搜索結(jié)果越穩(wěn)定；時間是算法迭代一個周期的運行時間，可以作為簡單的算法性能參考依據(jù)，在本文中的單位為“秒”，一個算法如果搜索時間過長，即使可以得到更好的解，也無法應(yīng)用于實際中，在與其他算法尋優(yōu)時間相差不多的情況下能搜索到更好的解則可以說明該改進是成功的。

參考表2，從最小值分析，HTPSO在解決10維和50維問題時，8個函數(shù)均可以搜索到比其他算法更好的解。其中，面對10維和50維問題時，f1、f2和f4均被搜索到理論最優(yōu)值。從平均值分析，f3和f4的平均值可以明顯看出HTPSO在解決這兩個問題時并不能保證每次搜索的結(jié)果都比其他4個算法優(yōu)秀，存在波動性，搜索10維f3時的能力略差于MAWPSO，在搜索50維f4時也表現(xiàn)出相同的問題。標(biāo)準(zhǔn)差顯示，本文提出的算法更穩(wěn)定，在解決10維問題時，對3個函數(shù)的搜索結(jié)果標(biāo)準(zhǔn)差都為0，50維問題上升至4個。對比算法搜索時間，HTPSO使用的時間與SelPSO和MAWPSO相差不大，在幾乎相同的時間內(nèi)搜索到了比SelPSO和MAWPSO更好的解。

綜合最小值、平均值、標(biāo)準(zhǔn)差和尋優(yōu)時間的結(jié)果排名，本文提出的改進算法HTPSO明顯優(yōu)于其他四個算法。由此可見，HTPSO與其他算法相比具有更高的穩(wěn)定性能和準(zhǔn)確率。

因為SinPSO和SelPSO的搜索結(jié)果中常會有較大的異常點，因此繪制出的大部分箱型圖縱坐標(biāo)會過大，導(dǎo)致很多箱型圖無法觀察，圖3展示的是利用4個10維函數(shù)(f1、f2、f4、f8)搜索結(jié)果繪制的箱型圖，橫坐標(biāo)A～E分別表示SinPSO、SelPSO、MAWPSO、SPSO和HTPSO。由圖3可以觀察到f2和f4能搜索到理論最優(yōu)解，且其中f2的搜索結(jié)果無任何波動，不存在四分之一位和四分之三位，30次每次結(jié)果都是理論解，很穩(wěn)定；f4也搜索到理論解，但有3個靠得很近的異常點?？傮w來看，本文提出的改進算法性能穩(wěn)定。

3.3.2 T-test檢驗分析

T-test全稱Student’s t test，是一種數(shù)理統(tǒng)計中利用t分布理論檢驗兩組數(shù)據(jù)差異性的檢驗方法。本文將對比算法搜索到的30個解與同條件下HTPSO搜索到的30個解進行差異性檢驗，使用兩獨立樣本T-test方法，計算公式如下：

(16)

(17)

100維問題的搜索結(jié)果如表3所示。表中的最小值、平均值、標(biāo)準(zhǔn)差與時間與表2中的意義相同；T-test展示的是使用T檢驗法檢驗的結(jié)果，如果檢驗結(jié)果顯示無差異則記為“=”，否則則使用勝率來判斷兩個算法搜索結(jié)果孰優(yōu)孰劣，故表中“+”“-”和“=”分別表示HTPSO搜索到的結(jié)果優(yōu)于、劣于和無差別于與之比較的改進算法，相應(yīng)的“1”“-1”和“0”表示得分，方便計算凈得分。凈得分即優(yōu)于比較函數(shù)得到的分數(shù)減去劣于之的次數(shù)得到的分數(shù)，以SinPSO與HTPSO的凈得分為例，HTPSO在T-test和勝率分析后優(yōu)于SinPSO的分數(shù)是7分，而劣于SinPSO的次數(shù)是0，故凈得分為7-0=7，其他凈得分的計算方法相同。通過凈得分可以更直觀地看出HTPSO的優(yōu)秀程度。

表2 5個改進粒子群優(yōu)化算法搜索10維和50維函數(shù)時的結(jié)果比較

表3中HTPSO表現(xiàn)最優(yōu)秀，最小值有8次搜索到比其他算法好的值，平均值有7個解比其他算法優(yōu)秀；其次是MAWPSO，該算法在搜索f2和f4時都搜索到與HTPSO一樣好或更好的解，其中搜索f4時得到的平均值也相對最小，但即便如此，與HTPSO相比依然相形見絀。

觀察T-test結(jié)果，SinPSO與HTPSO比較相比，HTPSO得到了7分；與SelPSO相比得到7分；比較MAWPSO得到5分；對比SPSO，HTPSO獲得凈得分8分。T-test的結(jié)果再一次顯示出HTPSO的優(yōu)越性能，搜索能力顯著地優(yōu)于其他4個改進粒子群算法。

圖3 搜索10維函數(shù)的30次結(jié)果箱型圖

函數(shù)指標(biāo)SinPSOSelPSOMAWPSOSPSOHTPSOf1f2f3f4f5f6f7f8最小值2.00E+012.00E+014.44E-152.05E+018.88E-16平均值2.00E+012.00E+014.56E-152.07E+018.88E-16標(biāo)準(zhǔn)差5.51E-049.38E-036.49E-165.41E-020.00E+00時間2.67 3.05 3.01 2.47 3.30 T-test+(1)+(1)+(1)+(1)最小值-2.83E+01-1.65E+01-9.90E+01-6.29E+00-9.90E+01平均值-1.99E+01-9.27E+00-9.67E+01-4.19E+00-9.90E+01標(biāo)準(zhǔn)差3.39E+004.71E+001.24E+018.83E-011.04E-05時間3.29 3.64 4.14 3.21 3.87 T-test+(1)+(1)=(0)+(1)最小值2.18E+011.36E+046.32E-034.69E+031.22E-03平均值1.90E+021.36E+045.18E-025.75E+033.49E-02標(biāo)準(zhǔn)差1.01E+022.08E-023.45E-023.73E+022.89E-02時間4.27 4.67 4.80 4.20 5.33 T-test+(1)+(1)+(1)+(1)最小值7.06E+022.89E+030.00E+001.83E+030.00E+00平均值8.56E+022.89E+034.50E-152.01E+033.09E-08標(biāo)準(zhǔn)差7.74E+012.31E-126.96E-155.91E+011.63E-07時間2.77 3.19 3.49 2.71 3.50 T-test+(1)+(1)=(0)+(1)最小值1.24E+061.53E+061.90E+016.64E-2940.00E+00平均值3.99E+063.82E+066.12E+061.67E-2880.00E+00標(biāo)準(zhǔn)差2.13E+061.58E+066.62E+060.00E+000.00E+00時間6.17 6.54 6.68 6.09 7.15 T-test+(1)+(1)+(1)+(1)最小值3.93E-992.73E-1182.92E-2282.27E-2960.00E+00平均值4.18E-881.73E-1028.15E-2064.59E-2770.00E+00標(biāo)準(zhǔn)差2.21E-879.23E-1020.00E+000.00E+000.00E+00時間2.34 2.72 3.07 2.25 3.32 T-test=(0)=(0)+(1)+(1)最小值1.46E+022.18E+021.41E-2252.63E-1964.88E-260平均值2.54E+022.64E+024.51E-2243.00E-1961.26E-259標(biāo)準(zhǔn)差4.58E+012.52E+010.00E+000.00E+000.00E+00時間2.37 2.74 2.97 2.31 3.13 T-test+(1)+(1)+(1)+(1)最小值1.84E+021.00E+067.28E-2554.00E-2990.00E+00平均值3.21E+041.00E+062.06E-2391.99E-2930.00E+00標(biāo)準(zhǔn)差1.49E+040.00E+000.00E+000.00E+000.00E+00時間2.36 2.75 3.44 2.35 3.39 T-test+(1)+(1)+(1)+(1)

同時觀察表2和表3的數(shù)據(jù)內(nèi)容。觀察平均值，在解決10維問題時，HTPSO 搜索到3個函數(shù)的理論最優(yōu)解，分別是f1、f2、f4;在解決50維問題時，搜索到理論最優(yōu)解的函數(shù)依然是f1和f2;100維問題中則有4個函數(shù)被搜索到最優(yōu)解，且理論解為非零解的兩個函數(shù)f1和f2始終都可以搜索到理論值。由此可見，本文提出的算法在解決高維度問題時顯得游刃有余。但如果不考慮是否搜索到理論解，只考慮是否得到比其他算法更好的解時，可以發(fā)現(xiàn)對于帶噪聲10維Quartic的函數(shù)，HTPSO可能搜索到比其他算法更好的解但幾率較小，在問題維度提升到50維和100維時，本文算法效果更加顯著，不管是最小值還是平均值都優(yōu)于其他算法；對于復(fù)雜的多峰函數(shù)Rastrigin，在10維時HTPSO可以輕松搜索到理論解，但是維度提升后從平均值可以看出，搜索到理論解的幾率明顯變低。

圖4是改進算法在搜索100維基準(zhǔn)函數(shù)時的曲線進化圖。篇幅有限，此處只展示比較有代表性的6幅曲線進化圖。由圖4可以看出，本文算法從一開始就具有較快的收斂速度。在相同的進化代數(shù)時，本文提出算法的進化曲線總在其他4個算法的下方；從“平均函數(shù)解”向右觀察會發(fā)現(xiàn)HTPSO總是離縱坐標(biāo)軸最近，這再一次證明了該算法收斂速度快的特點。

進一步觀察不難看出，HTPSO在搜索f5、f6這兩個函數(shù)時的進化曲線在遠沒有到達1 000次總迭代次數(shù)時就已經(jīng)搜索到了理論最優(yōu)解，即在相同情況下HTPSO會更有效率地搜索到符合要求的結(jié)果。綜合上述兩點優(yōu)勢足以說明本文提出的改進策略是成功的。

3.3.3 函數(shù)維度對算法性能影響

由表2、表3中的數(shù)據(jù)不難看出，維度增加對本文算法影響較弱，且HTPSO隨著函數(shù)維度的增加搜索結(jié)果有變好趨勢。但引起以上現(xiàn)象的原因也可能是增加問題維度的同時也適量增加了總迭代次數(shù)導(dǎo)致的，因此在不改變迭代次數(shù)的情況下，本文算法是否依然可以隨著維度的增加搜索能力更強或者是否依然很穩(wěn)定便值得近一步探討。以下實驗就在不改變迭代次數(shù)的情況下令函數(shù)維度從1增加到100，5個算法搜索結(jié)果的變化情況如圖5所示。橫坐標(biāo)是函數(shù)維度，從1維以步長為1的速度增加到100維；縱坐標(biāo)是不同維度下算法搜索到的函數(shù)解；總迭代次數(shù)均設(shè)置為500；其他參數(shù)的設(shè)置參考表1。

由圖5可知，本文算法HTPSO的搜索結(jié)果更好，且十分穩(wěn)定。圖5(a)中，HTPSO變化曲線是一條與橫坐標(biāo)平行的直線，從1維開始到100維，該算法都能搜索到理論解；f1在10維以下時，MAWPSO的曲線與HTPSO重合，但是在10維以后曲線上升，此時搜索到的解相對HTPSO較差；SinPSO在5維以前結(jié)果與HTPSO相同，之后便大幅度上升，且呈大鋸齒狀，十分波折；SelPSO和SPSO效果較差。查詢表1，圖5(b)的函數(shù)理論值是跟隨維度變化的，HTPSO的解變化曲線很平穩(wěn)地下潛，總是可以搜索到理論解；MAWPSO大部分曲線與HTPSO重合，但是在40維和50維左右，出現(xiàn)了一些波動，未能搜索到理論解；其他三條曲線雖然也有隨維度增加逐漸下降的趨勢，但是并不明顯，且有較多波折，穩(wěn)定性差。圖5(c)中的函數(shù)具有噪聲項干擾，5個算法曲線均表現(xiàn)出較強烈的波動性，但可以看出HTPSO的搜索結(jié)果依舊比較好，整體并沒有上升趨勢。

HTPSO在總迭代次數(shù)不變的情況下，面對不同維度問題時，性能十分穩(wěn)定，且搜索結(jié)果都較好；當(dāng)搜索函數(shù)在10維以下時有一定概率搜索到比超過10維更好的解，維度高于10維后，算法結(jié)果趨于穩(wěn)定。

圖4 適應(yīng)度進化曲線

圖5 算法尋優(yōu)結(jié)果變化曲線

3.3.4 成功率與平均迭代次數(shù)分析

比較尋優(yōu)不同維度函數(shù)結(jié)果的實驗是在相同的條件下增加函數(shù)的維度比較算法的搜索性能，成功率和平均迭代次數(shù)則是設(shè)定需要搜索到的容忍度，比較算法是否在同一條件下更有效率地達到期望精度。

成功率即該算法在規(guī)定的最大迭代次數(shù)和尋優(yōu)次數(shù)內(nèi)，搜索得到最優(yōu)解達到容忍精度要求的次數(shù)與尋優(yōu)總次數(shù)的比值。在相同條件下，某個算法成功率越高，算法搜索到容忍精度的概率就越大，性能就顯得更加穩(wěn)定。平均迭代次數(shù)指的是在相同條件下，規(guī)定每個算法搜索同一個函數(shù)的次數(shù)，并記錄該算法每次搜索該函數(shù)時達到容忍度的迭代次數(shù)，規(guī)定次數(shù)搜索完后計算記錄下來的迭代次數(shù)平均值。該數(shù)據(jù)可以判斷算法的尋優(yōu)效率，平均迭代次數(shù)越小則表明該算法相比其他算法搜索到規(guī)定容忍度的速度更快。

本節(jié)中成功率和平均迭代次數(shù)的獲得參考3.1節(jié)函數(shù)介紹的容忍度，參數(shù)依然遵循表1設(shè)置，規(guī)定每個算法搜索同一個函數(shù)30次。表4中展示的是5個改進粒子群優(yōu)化算法在面對100維問題時成功率與平均迭代次數(shù)的具體數(shù)據(jù)。其中：SR(Success Rate)表示成功率；AIT(Average Iteration Time)表示平均迭代次數(shù)；“—”表示未能在1 000次迭代次數(shù)內(nèi)搜索到理想的精度，也可以理解為30次搜索中一次也沒能搜索到容忍度。

由表4可知，SinPSO和SelPSO未獲得較高的成功率，MAWPSO和SPSO在相同條件下各有1次，HTPSO在尋優(yōu)8個函數(shù)時成功率都是最高的。觀察平均迭代次數(shù)可以發(fā)現(xiàn)，SelPSO、MAWPSO、SPSO一次也沒有得到最小的平均迭代次數(shù)，SinPSO有1次獲得最小的平均迭代次數(shù)，HTPSO對其中7個函數(shù)都可以獲得比其他算法更少的平均迭代次數(shù)，只對f6表現(xiàn)得較差?？梢灾庇^地看出MAWPSO和HTPSO均具有較快的搜索能力，且同樣達到容忍度時，HTPSO的速度更快?？傮w上，HTPSO成功率和平均迭代次數(shù)均優(yōu)于對比算法。

表4 解決100維問題時5個改進粒子群優(yōu)化算法的成功率與平均迭代次數(shù)對比

4 結(jié)語

本文提出了一種含交叉項的混合二范數(shù)粒子群優(yōu)化算法(HTPSO)，即將差分進化算法中的交叉項與只使用位置迭代公式的二范數(shù)粒子群算法相結(jié)合。二范數(shù)在公式中的引入有效平衡了粒子受全局最優(yōu)點的影響程度，當(dāng)前粒子又在一定概率下與其自身搜索到的最優(yōu)值進行交叉，這樣的改進令粒子更多樣化，搜索過程充滿活力，極大地減少了陷入局部解的可能。檢驗分析表明，本文的改進策略成功有效，且算法對于高維度問題的搜索能力十分穩(wěn)定，對算法迭代公式的簡化也讓HTPSO的搜索時間與對比算法相差不大，完全在容忍范圍內(nèi)。HTPSO這一系列改進策略是否可以運用于實際應(yīng)用問題將是下一步待研究的工作。