帶有退火和雜交變異思想的改進(jìn)粒子群算法

黃煒霖 ，劉建軍 ，張 明 ，呂照明 ，伍 建

1.中國(guó)石油大學(xué)（北京）理學(xué)院，北京 102249

2.中國(guó)石油大學(xué)（北京）油氣資源與探測(cè)國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京 102249

3.中國(guó)石油大學(xué)（北京）CNPC物探重點(diǎn)實(shí)驗(yàn)室，北京 102249

1 引言

粒子群優(yōu)化算法（PSO）是由Kennedy和Eberhart在1995年提出的一種新型進(jìn)化計(jì)算方法[1-2]。PSO算法原理簡(jiǎn)單且易實(shí)現(xiàn)，迭代運(yùn)算的參數(shù)少，具有較快的收斂速度。近年來(lái)的研究表明，該算法在許多優(yōu)化問(wèn)題中表現(xiàn)優(yōu)秀，已被成功應(yīng)用到參數(shù)辨識(shí)、模式識(shí)別、網(wǎng)絡(luò)優(yōu)化等許多領(lǐng)域[3-6]。

但是，基本PSO算法在求解復(fù)雜函數(shù)優(yōu)化問(wèn)題時(shí)，求解過(guò)程中易出現(xiàn)“早熟現(xiàn)象”，進(jìn)而無(wú)法找到全局最優(yōu)解，同時(shí)搜索的精度不高。針對(duì)算法的這些不足，很多學(xué)者將其他優(yōu)化算法思想融入PSO算法中，Lovbjerg等人提出了帶交叉算子的PSO算法[7]；Liu等人將混沌算法的思想引入PSO算法中[8]；Holden等人混合PSO算法和蟻群算法[9]等等[10-16]。為了解決PSO應(yīng)用中出現(xiàn)的早熟現(xiàn)象，本文首先應(yīng)用信息熵算法產(chǎn)生分布更為均勻的初始群體，然后基于模擬退火算法中依概率接受劣解，和遺傳算法中雜交變異產(chǎn)生新解的思想，提出了粒子群算法的一種新改進(jìn)算法。

2 基本粒子群算法

PSO優(yōu)化算法將待優(yōu)化的參數(shù)組合成群體，再利用個(gè)體（粒子）的適應(yīng)度使其向好的區(qū)域移動(dòng)，每個(gè)粒子代表問(wèn)題的一個(gè)可能解，每個(gè)粒子具有位置和速度兩個(gè)特征[1-2]。在D維搜索空間中，第i個(gè)粒子的位置可以表示成Xi，其速度表示成Vi，粒子位置坐標(biāo)對(duì)應(yīng)的目標(biāo)函數(shù)值即可作為該粒子的適應(yīng)度，算法依據(jù)適應(yīng)度來(lái)衡量粒子的優(yōu)劣。算法首先初始化一群隨機(jī)粒子，然后通過(guò)迭代找到最優(yōu)解。在每次迭代中，粒子的更新是通過(guò)跟蹤兩個(gè)“極值”：一個(gè)是粒子本身經(jīng)歷過(guò)的最優(yōu)解，即個(gè)體極值pbesti；另一個(gè)是整個(gè)粒子群經(jīng)歷過(guò)的最優(yōu)解，即全局極值gbest，最后輸出的gbest就是算法得到的最優(yōu)解。第i個(gè)粒子從第k代進(jìn)化到第k+1代時(shí)，根據(jù)下面兩個(gè)公式更新速度與位置：

其中，ω為慣性權(quán)重，其作用是維護(hù)全局和局部搜索能力的平衡；c1和c2為加速因子，作用是控制粒子向pbesti和gbest移動(dòng)的速度大??；rand為[0，1]范圍內(nèi)的隨機(jī)數(shù)。

粒子群優(yōu)化算法具有結(jié)構(gòu)簡(jiǎn)單，運(yùn)行速度快的優(yōu)點(diǎn)。在算法搜索過(guò)程中，某粒子發(fā)現(xiàn)一個(gè)當(dāng)前最優(yōu)位置，其他粒子便會(huì)迅速向其靠攏。但是，如果該最優(yōu)位置為一局部最優(yōu)點(diǎn)時(shí)，算法很容易陷入局部最優(yōu)，粒子群就無(wú)法在解空間內(nèi)重新搜索，出現(xiàn)了所謂的早熟收斂現(xiàn)象。

3 基于信息熵控制初始群體的生成

若初始群體沒(méi)有較均勻的分布在解空間，那么群體的多樣性將降低，導(dǎo)致算法全局搜索能力減弱。對(duì)此應(yīng)用信息熵來(lái)提高初始群體的多樣性[17-18]。

在信息論中，熵通常也稱(chēng)做信息熵或Shannon熵，它主要采用數(shù)值形式表達(dá)隨機(jī)變量取值的不確定性程度，或一個(gè)系統(tǒng)的混亂性、遍歷性、隨機(jī)性[19-21]。設(shè)初始群體由N個(gè)D維個(gè)體組成，并用X=(X1,X2,…,XD)來(lái)表示（每個(gè)分量為N維列向量），則第j維分量的信息熵Hj表示為：

其中，pj(x)為隨機(jī)變量Xj的概率密度函數(shù)，Xj為第j維分量的取值范圍。

整個(gè)系統(tǒng)的信息熵H表示為：

其中，Qj為信息熵確定的權(quán)重。

對(duì)于概率密度函數(shù)，采取高斯核函數(shù)方法[22-23]來(lái)近似估計(jì)：

其中，為第j維分量的第i個(gè)值，σ為核函數(shù)的寬度。

由式（4）可知，熵值H越大，群體多樣性越好，即個(gè)體間差異越大，相反熵值H越小，群體多樣性越低，即個(gè)體間差異越小，當(dāng)熵值H為零時(shí)，個(gè)體間無(wú)差異。因此，可以用熵值H來(lái)控制群體的生成，生成多樣性較好、遍歷性較高的初始群體，如圖1所示。

圖1 不同熵值H對(duì)應(yīng)的初始種群分布

由于混沌序列具有混沌運(yùn)動(dòng)的遍歷性、隨機(jī)性和規(guī)律性等特點(diǎn)，能在一定范圍內(nèi)按自身的規(guī)律不重復(fù)地遍歷所有狀態(tài)，所以很多學(xué)者用混沌映射來(lái)生成初始群體[24-25]?；煦缒Ｐ陀泻芏啵畛Ｓ玫氖莑ogistic映射，即：

其中，n=0,1,…，0≤y(n)≤1，u是控制參量，當(dāng)u=4時(shí)，上述系統(tǒng)處于完全混沌狀態(tài)。

由于logistic映射生成的粒子分布在區(qū)間兩頭的概率遠(yuǎn)大于中間，而中間分布較均勻，所以這里只取落在區(qū)間[0.1，0.9]里面粒子，舍棄其他粒子。

4 帶有模擬退火和雜交變異思想的粒子群算法4.1 雜交變異思想

遺傳算法中雜交算子能使個(gè)體間交換信息，而變異算子能使某些個(gè)體發(fā)生基因突變，使個(gè)體具有更大的遍歷性[26-27]。本文借鑒這個(gè)思想，通過(guò)雜交和變異來(lái)產(chǎn)生多樣性更好的后代。

圖2 二維粒子分布和每維上的分布情況比較（100個(gè)）

4.1.1 雜交

在PSO算法迭代中，選取一定數(shù)目的粒子放入雜交池中，池中的粒子隨機(jī)進(jìn)行雜交，然后產(chǎn)生同樣數(shù)目的子代粒子（child），再用子代粒子替換父代粒子（parent）。子代粒子由父代粒子算術(shù)交叉得到：

其中，p是0到1之間的隨機(jī)數(shù)。

4.1.2 變異

在PSO算法迭代中，以一小概率μ選取粒子，并隨機(jī)選取其某一維或者幾維，將它的值改變，改變的值為搜索范圍內(nèi)的隨機(jī)數(shù)。這個(gè)概率μ可以是固定的，也可以是以某種方式下降的。

雜交和變異的操作，目的是增加群體的多樣性，幫助算法跳出局部最優(yōu)，防止算法“早熟”。

4.2 退火思想

借鑒模擬退火算法搜索過(guò)程中具有概率突跳的能力，且不但接受好解，還以一定的概率接受劣解，同時(shí)這種概率受到溫度參數(shù)的控制[27-28]。本文對(duì)其進(jìn)行修改，將這種思想融合到粒子群算法中。在4.1.1小節(jié)所述的雜交操作中，是以這樣的步驟選取粒子放入雜交池中：

步驟2計(jì)算初始溫度：

其中fmax、fmin分別表示最大的適應(yīng)值和最小的適應(yīng)值。

步驟3計(jì)算雜交比例：

其中λ為取值在0到1之間的比例系數(shù)，作用是控制比例大小，k為當(dāng)前迭代步數(shù)，M為最大迭代步數(shù)。

其中rand表示0到1之間的一個(gè)隨機(jī)數(shù)，Δfj表示第j個(gè)粒子的適應(yīng)值與全局最優(yōu)點(diǎn)適應(yīng)值之差。

步驟5降溫：

其中μ為降溫系數(shù)，作用是控制溫度下降的快慢。

上述過(guò)程可以這樣理解：當(dāng)j＞(1-P)N，就進(jìn)行雜交，相當(dāng)于模擬退火算法中接受收好解的過(guò)程，這里是接受劣解進(jìn)入雜交池；當(dāng)j≤(1-P)N，就依概率R來(lái)判斷是否雜交，相當(dāng)于模擬退火算法中依概率接受劣解，這里是依概率接受好解進(jìn)入雜交池，且粒子越好，進(jìn)入雜交池的可能性就越小。

上述操作的目的有二：一是加速算法的收斂速度，越到迭代后期，雜交比例P和接受好解進(jìn)入雜交池的概率R越小；二是使算法具有突跳能力，能有效的跳出局部極小點(diǎn)。

4.3 算法步驟

步驟1給定一個(gè)臨界熵值H0，隨機(jī)產(chǎn)生初始群體并按式（3）、（4）、（5）、（6）計(jì)算他的熵值H，若H＞H0則隨機(jī)初始化該初始群體的速度，轉(zhuǎn)步驟2；否則重新隨機(jī)產(chǎn)生初始群體直到滿足H＞H0為止。

步驟2評(píng)價(jià)每個(gè)粒子的適應(yīng)度，將當(dāng)前各粒子的位置和適應(yīng)值存儲(chǔ)在各粒子的pbesti中，將所有pbesti中適應(yīng)值最優(yōu)個(gè)體的位置和適應(yīng)值存儲(chǔ)在gbest中。

步驟3按式（9）計(jì)算初始溫度T0。

步驟4按式（1），（2）更新每個(gè)粒子的速度和位置。

步驟5對(duì)粒子群體進(jìn)行變異操作。

步驟6計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值，按式（10）、（11）、（12）計(jì)算出放入雜交池的粒子，以及保留的粒子。

步驟7將步驟6中雜交池中的粒子按式（8）隨機(jī)進(jìn)行雜交，然后產(chǎn)生同樣數(shù)目的子代粒子，再用子代粒子替換父代粒子。

步驟8更新每個(gè)粒子的pbesti以及群體的gbest。

步驟9若滿足停止條件（精度或者迭代次數(shù)等），搜索停止，輸出結(jié)果；否則轉(zhuǎn)步驟10。

步驟10按式（12）進(jìn)行降溫操作，轉(zhuǎn)步驟4。

5 仿真實(shí)驗(yàn)

下面通過(guò)4個(gè)典型函數(shù)優(yōu)化問(wèn)題（求解最小值）來(lái)測(cè)試本文提出的算法的性能。

測(cè)試函數(shù)1，Sphere函數(shù)：

其中-100＜xi＜100，最優(yōu)狀態(tài)和最優(yōu)值為：

測(cè)試函數(shù)2，Rastrigin函數(shù)：

其中-5.12＜xi＜5.12，最優(yōu)狀態(tài)和最優(yōu)值為：

測(cè)試函數(shù)3，Ackley函數(shù)：

其中-32＜xi＜32，最優(yōu)狀態(tài)和最優(yōu)值為：

測(cè)試函數(shù)4，Griewank函數(shù)：

其中-600＜xi＜600，最優(yōu)狀態(tài)和最優(yōu)值為：

對(duì)每個(gè)測(cè)試函數(shù)，分別采用標(biāo)準(zhǔn)粒子群算法（PSO）、遺傳粒子群算法（GAPSO）[29-30]和本文所提出的帶有模擬退火和雜交變異思想的粒子群算法（SAHMPSO）進(jìn)行測(cè)試。

為了保證實(shí)驗(yàn)的客觀性，對(duì)于基本參數(shù)的設(shè)定，3種算法均為：種群大小N為40；函數(shù)維數(shù)D分別為10、20、30；加速因子c1=c2=1.4；慣性權(quán)重ω=0.65；最大迭代次數(shù)為5 000。對(duì)于每個(gè)測(cè)試函數(shù)，每種算法運(yùn)行100遍，其中Avg表示運(yùn)行100次的結(jié)果的平均值，Var表示運(yùn)行100次的結(jié)果的方差，Best表示運(yùn)行100次的結(jié)果的最小值。運(yùn)算結(jié)果如表1所示。

為了分析算法的收斂性能，將3種算法在4個(gè)測(cè)試函數(shù)上的最優(yōu)值best記錄下來(lái)，以橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為函數(shù)的對(duì)數(shù)值，作出圖形如圖3所示（僅展示10維情況）。

Sphere函數(shù)為連續(xù)的單峰函數(shù)，自變量之間互相獨(dú)立，Rastrigin、Ackley、Griewank這3個(gè)函數(shù)為復(fù)雜的非線性多峰函數(shù)，存在大量局部極小值。從表1可以看到，本文提出的算法，無(wú)論是在搜索精度還是在穩(wěn)定性都明顯的高于其他兩種算法。

Sphere函數(shù)常用于測(cè)試算法的收斂速度，Rastrigin函數(shù)常用于測(cè)試算法的全局搜索性能。由圖3（a）和（b）看到，在迭代早期，3種算法的收斂速度基本相當(dāng)，而在迭代的中后期，由于PSO算法的“早熟”使得算法停滯不前，陷入了局部極小，而GASPSO算法雖然找到了比PSO算法更好的解，但很快也陷入了局部極小。而SAHMPSO算法由于雜交，變異操作，在保持收斂速度的同時(shí)，大大地加強(qiáng)了抗“早熟”的能力。

Ackley函數(shù)常用于測(cè)試算法跳出局部極值的能力。由圖3（c）可以看到，PSO算法和GASPSO算法很快就陷入局部極值難以跳出，而SAHMPSO算法能一直保持著一個(gè)較快的速度下降，即使陷入局部極值，在若干次迭代后仍可跳出。

Griewank函數(shù)常用于測(cè)試算法對(duì)全局與局部搜索能力的平衡性能。由于本文算法融入了退火的思想，使得算法在兼顧局部搜索能力的同時(shí)，在迭代后期加快全局收斂速度，由圖3（d）可以看到，PSO算法同樣是在迭代次數(shù)不到100的時(shí)候就已經(jīng)停滯不前了，而SAHMPSO算法在迭代前期保持了種群較大的多樣性，強(qiáng)化了算法的全局搜索能力，在迭代后期降低種群的多樣性，加快收斂，強(qiáng)化了算法的快速下降搜索能力。而信息熵控制的方法產(chǎn)生了均勻性良好的初始群體，加強(qiáng)了群體的多樣性，是算法的較高收斂性能的基礎(chǔ)。

6 結(jié)論

本文提出的改進(jìn)算法中，利用信息熵控制生成初始群體，保證了初始群體的多樣性，為后續(xù)進(jìn)化提供了基礎(chǔ)。改進(jìn)算法中融入了模擬退火算法中的退火方法和遺傳算法中的雜交、變異算子，使得算法不僅保持了PSO算法前期函數(shù)值的快速下降性，還克服了原算法的“早熟”缺點(diǎn)，從而使算法的搜索性能得到很大的提高。通過(guò)數(shù)值實(shí)驗(yàn)可以發(fā)現(xiàn)，本文的改進(jìn)算法在抗“早熟”、搜索精度和穩(wěn)定性方面均優(yōu)于PSO及GAPSO，本文算法可進(jìn)一步應(yīng)用到實(shí)際問(wèn)題中。

表1 3種算法針對(duì)4個(gè)函數(shù)在10、20和30維下的實(shí)驗(yàn)結(jié)果（運(yùn)行100次）

圖3 3種算法優(yōu)化4個(gè)函數(shù)的收斂性能比較（小圖為前100步的迭代情況放大）

[1]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proc of the 1st IEEE International Conference on Neural Networks，Perth，Australia，1995：1942-1948.

[2]Eberhart R C，Kennedy J.A new optimizer using particle swarm theory[C]//Proc of 6th Int Symp Micro Machine and Human Science，Nagoya，Japan，1995：39-43.

[3]戴運(yùn)桃.粒子群優(yōu)化算法研究及其在船舶運(yùn)動(dòng)參數(shù)辨識(shí)中的應(yīng)用[D].哈爾濱：哈爾濱工程大學(xué)，2010.

[4]Yoshida H，Kawata K，F(xiàn)ukuyama Y，et al.A particle swarm optimization for reactive power and voltage control considering voltage security assessment[J].IEEE Transactions on Power Systems，2001，15（4）：1232-1239.

[5]Sousa T，Silva A，Neves A.Particle swarm based data mining algorithms for classification tasks[J].Parallel Computing，2004，30（5/6）：767-783.

[6]He Z，Wei C，Yang L，et al.Extracting rules from fuzzy neural network by particle swarm optimization[C]//Proceedings of IEEE Congress on Evolutionary Computation，Anchorage，Alaska，USA，1998.

[7]Lovbjerg M，Rasmussen T K，Krink T.Hybrid particle swarm optimizer with breeding and subpopulation[C]//Proceedings of Genetic and Evolutionary Computation Conf.San Francisco：Morgan Kaufmann Publishers Inc，2001：469-476.

[8]Liu Bo，Wang Ling，Jin Yihui，et a1.Improved particle swann optimization combined with chaos[J].Chaos，Solitons and Fractals，2005，25（5）：1261-1271.

[9]Holden N，F(xiàn)reitas A A.Hybrid particle swarm，ant colony algorithm for the classification of hierarchical biological data[C]//Proc of the IEEE Swarm Intelligence Symposium，Delhi，India，2005：100-107.

[10]胥小波，鄭康鋒，李丹，等.新的混沌粒子群優(yōu)化算法[J].通信學(xué)報(bào)，2012（1）：24-30.

[11]李季，孫秀霞，李士波，等.基于遺傳交叉因子的改進(jìn)粒子群優(yōu)化算法[J].計(jì)算機(jī)工程，2008（2）：181-183.

[12]楊俊杰，周建中，喻菁，等.基于混沌搜索的粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2005，41（16）：69-71.

[13]Kiel R T，Thiemo K.Improved hidden Markov model training for multiples equence alignment hybrid[J].Bio-systems，2003，72（1/2）：5-17.

[14]Ji M J，Tang H W.Application of chaos in simulated annealing[J].Chaos，Solitons and Fractals，2004，21：933-941.

[15]張頂學(xué).遺傳算法與粒子群算法的改進(jìn)及應(yīng)用[D].武漢：華中科技大學(xué)，2007.

[16]潘昊，侯清蘭.基于粒子群優(yōu)化算法的BP網(wǎng)絡(luò)學(xué)習(xí)研究[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（16）：41-43.

[17]Chun J，Kim M.Shape optimization of electromagnetic devices using immune algorithm[J].IEEE Trans on Magnetics，1997，33（3）：1876-1879.

[18]袁曉輝，袁艷斌，王乘，等.一種新型的自適應(yīng)混沌遺傳算法[J].電子學(xué)報(bào)，2006（4）：708-712.

[19]Cover T M，Thomas J A.Elements of information theory[M].New York：Wiley，1991.

[20]Cover T M，Thomas J A.信息論基礎(chǔ)[M].阮吉壽，張華，譯.北京：機(jī)械工業(yè)出版社，2005：9-28.

[21]張妍，楊志峰，何孟常，等.基于信息熵的城市生態(tài)系統(tǒng)演化分析[J].環(huán)境科學(xué)學(xué)報(bào)，2005（8）：1127-1134.

[22]Parzen E.On estimation of a probability density funcion and mode[J].Annals of Math Statistics，1962，33：1065-1076.

[23]Beirlant J，Dudewicz E J，Gyorfi L，et al.Nonparametric entropy estimation：An overview[J].International Journal of the Mathematical Statistics Sciences，1997，6：17-39.

[24]Tavazoei M S，Haeri M.An optimization algorithm based on chaotic behaviorand fractalnature[J].Journalof Computational and Applied Mathematics，2007，206（2）：1070-1081.

[25]周燕，劉培玉，趙靜，等.基于自適應(yīng)慣性權(quán)重的混沌粒子群算法[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2012（3）：27-32.

[26]Holland J H.Adaptation in natural and artificial systems[M].Cambridge，Massachusetts：MIT Press，1992：87-95.

[27]邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京：清華大學(xué)出版社，1999：90-183.

[28]Metropolis N，Rosenbluth A.Rosenbluth metal，equation of state calculations by fast computing machines[J].Journal of Chemical Physics，1953，56（21）：1087-1092.

[29]龔純，王正林.精通MATLAB最優(yōu)化計(jì)算[M].2版.北京：電子工業(yè)出版社，2012：273-311.

[30]彭曉波，桂衛(wèi)華，黃志武，等.GAPSO：一種高效的遺傳粒子混合算法及其應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，2008，20（18）：5025-5027.