基于迭代優(yōu)化度與直線搜索的改進粒子群算法

王斌

摘要：現(xiàn)有粒子群算法無論是在算法運行的前期還是后期，現(xiàn)有的改進方法都是以適應度值來作為評價粒子優(yōu)劣的唯一標準，本文根據(jù)挖掘有潛力粒子的思想，提出迭代優(yōu)化度概念來刻畫粒子的潛力，并對于潛力較大的粒子采用直線搜索的策略來進行搜索，這樣就避免所有的粒子均參考適應度值優(yōu)秀的粒子運動，提高了算法效率，保持了潛力大的粒子的獨立性。將改進粒子群算法用2個經(jīng)典的檢驗函數(shù)進行對比檢驗，結(jié)果表明提出的改進粒子群算法能大幅度增強擺脫局部最優(yōu)解的能力，有效地改善尋優(yōu)性能。

關(guān)鍵詞：PSO算法；改進PSO算法

1.引言

粒子群算法是基于個體有序運動的群體智能算法，是由Eberhart和Kennedy[1][2]在1995年提出來的。但是標準的PSO算法主要存在早熟和尋優(yōu)精度低的問題，因此為了實現(xiàn)加快收斂速度和避免陷入局部最優(yōu)解，改進的粒子群算法被提出。

現(xiàn)有的改進方式主要有改進算法參數(shù)、改進搜索方式和改進搜索領(lǐng)域的拓撲結(jié)構(gòu)[4]，然而到目前為止同時兼顧收斂速度和跳出局部最優(yōu)解的能力是很難的。比如，文獻[3]把重心放在避免陷入局部最優(yōu)解的問題上，卻帶來了收斂速度的變緩。2002年Clerc[5]等引入了收縮因子，提出了一種自適應PSO算法，到目前為止參數(shù)的自適應策略都是以種群迭代次數(shù)為參考變量的。2013年何茜[6]提出一種刪除機制，對于長期不更新的粒子，直接刪除。

2.粒子群算法簡介

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

粒子群優(yōu)化（particle swarm optimizer，簡稱PSO）算法是模仿鳥類群體智能行為而提出的算法，其實施過程：在算法開始時，對各粒子賦予初始值（初始速度和初始位置），初始種群在N維解空間中為均勻分布。其中第i個粒子在研究區(qū)域中所處的位置和速度分別表示為Xi=（xi1，xi2…，xin）和Vi=（vi1，vi2…，vin），根據(jù)迭代原則找到最優(yōu)解。在每次迭代時，粒子通過跟蹤兩個極值來更新自身的速度和位置，一個極值是粒子本身到目前為止所找到的最優(yōu)解，這個極值稱為個體極值，設(shè)為Pbesti=（Pbesti1，Pbesti2…，Pbestin）；另一個極值是該粒子的領(lǐng)域到目前為止找到的最優(yōu)解，這個極值稱為整個領(lǐng)域的最優(yōu)極值，設(shè)為Nbesti=（Nbesti1，Nbesti2…，Nbestin）。第i個粒子是根據(jù)以下公式（1）（2）（3）更新自身的速度和位置：

Vi=ωVi+c1×rand×（Nbesti-Xi）+c2×rand（）×（Pbesti-Xi）Xi=Xi+Vi

ω=（ω1-ω2）Imax-IImax+ω2

式中c1和c2是加速常量，rand是[0，1]之間的隨機數(shù)，ω1、ω2為慣性權(quán)重的初始值和終值，I為當前迭代次數(shù)，Imax為最大迭代次數(shù)。

3.粒子群優(yōu)化算法的改進

3.1迭代優(yōu)化度與直線搜索

現(xiàn)有的改進方法均采用將適應度值好壞作為評價粒子優(yōu)劣的唯一標準，對于適應度值暫時不優(yōu)秀的粒子，強制性地讓其以暫時優(yōu)秀的粒子為中心運動，這樣不僅會讓種群失去多樣性，而且還會造成潛在的優(yōu)秀粒子被忽略。因此，在粒子群算法中，應該給予那些進步程度大的潛在優(yōu)秀粒子獨立發(fā)展的空間，這樣就有更大的可能發(fā)現(xiàn)更優(yōu)秀的粒子。

現(xiàn)有的改進方法無一例外都存在一個嚴重的問題，那就是將適應度值好壞作為評價粒子優(yōu)劣的唯一標準，對于那些適應度值暫時不優(yōu)秀的粒子，很粗暴地讓它們以暫時優(yōu)秀的粒子為中心運動，這樣不僅會讓種群失去多樣性，而且還會失去很多尋找到更加優(yōu)秀粒子的機會。

基于以上的分析，本文提出迭代優(yōu)化度的概念來刻畫粒子的進步程度，對于求最小值的優(yōu)化問題，定義如下：

D_betteri，t=fiti，t-1-fiti，tfiti，t-1×100%（4）其中，i表示粒子的編號，t表示迭代種群迭代次數(shù)，fiti，t適應度值，D_betteri，t迭代優(yōu)化度。

最后，考慮對于迭代優(yōu)化度較大的粒子的獨立搜索，但是考慮到算法的復雜度，必須提出一種簡單有效的搜索方式。在此，本文提出了直線搜索的策略，對于迭代優(yōu)化度排名靠前的粒子進行沿著原來速度所對應方向的直線搜索，在直線上有序取點進行搜索。

4.性能測試分析

為了測試算法的性能，選擇2個標準的測試函數(shù)用于優(yōu)化實驗，2個函數(shù)的函數(shù)表達式、搜索空間、理論全局最小是入表1所示。

表1標準的測試函數(shù)

函數(shù)函數(shù)表達式搜索空間最優(yōu)解

Rosenbrockf2（x）=∑ni=1100（xi+1-x2i）2+（1-xi）2[-100，100]0

Griewankf4（x）=14000∑ni=1x2i-∏ni=1cos（xii）+1[-100，100]0

通過比較測試函數(shù)的平均適應度值、方差適應度值、最優(yōu)適應度值和最差適應度值的方式對三種算法進行評價，其中平均適應度值和方差適應度值用于評價算法的尋優(yōu)精度和魯棒性。下面將通過與文獻[22]中所提出的引入刪除機制的粒子群算法作對比，來說明本文引入迭代優(yōu)化度與線性搜索策略的粒子群算法的性能。

算法參數(shù)設(shè)置如下：測試函數(shù)的維數(shù)為10，迭代次數(shù)為2000次。種群規(guī)模為100，C1=C2=2.0，慣性權(quán)重w1=w2=0.8，適應度值選優(yōu)比例Rate_better=0.1，迭代優(yōu)化度選優(yōu)比例Rate_imp=0.1。結(jié)果如表2所示，其曲線如圖1—圖2所示。

表2測試函數(shù)的仿真結(jié)果比較

函數(shù)算法平均值方差最優(yōu)值最差值

f1

PSO4.6246.14874.62412.75

改進PSO2.242e-033.7259e-072.242e-033.923e-03

f2

PSO3.751e+032.576e+61.900e+037.129e+03

改進PSO1.41250.10340.78171.837

f3

PSO1.532e-022.195e-041.807e-035.069e-02

改進PSO1.683e-074.072e-141.183e-095.632e-07

f4

PSO0.56211.562e-020.36220.6667

改進PSO0.17182.469e-030.10100.2559