一種基于濃度的粒子群優(yōu)化算法

李慶芳，孫合明

(河海大學理學院，南京 210098)

粒子群(PSO)算法起源于對簡單社會系統(tǒng)的模擬。該算法是1995年由美國電氣工程師Eberhard和社會心理學家 Kennedy［1－2］提出的。粒子群算法本質(zhì)上是一種并行的全局性的隨機搜索算法，具有容易實現(xiàn)、搜索速度快、優(yōu)化性能好等優(yōu)點［3－8］。該算法自提出以來，引起了國際上相關(guān)領域眾多學者的關(guān)注和研究，并被廣泛應用到神經(jīng)網(wǎng)絡訓練、工業(yè)系統(tǒng)優(yōu)化及控制［9－12］等領域。

作為一種進化算法，粒子群算法也有其缺點［13］。PSO算法是根據(jù)全體粒子和自身的搜索經(jīng)驗向著最優(yōu)解的方向“飛行”，在進化后期所有的粒子都向“最優(yōu)點”聚集，趨向同一化，群體的多樣性逐漸喪失，致使算法后期的收斂速度明顯變慢，甚至處于停滯狀態(tài)，出現(xiàn)早熟現(xiàn)象。針對PSO算法的這個缺點，本文將免疫算法中基于濃度選擇的概率引到PSO算法中，提出一種改進的粒子群算法。該算法根據(jù)濃度的大小對粒子的更新進行有選擇的指導，從而在一定程度上加快了算法的收斂速度，增強了算法的尋優(yōu)能力，同時對部分粒子進行初始化，增加種群多樣性。實驗結(jié)果表明，該算法具有較高的優(yōu)化性能。

1 標準粒子群優(yōu)化算法

在粒子群算法中，每個個體稱為一個粒子，代表著解空間中一個潛在的解。例如，在一個D維的目標搜索空間中，每個粒子看成是空間內(nèi)的一個點。設群體由m個粒子構(gòu)成，zi=(zi1，zi2，…，zin)為第 i個粒子(i=1，2，…，m)的D維位置矢量。根據(jù)事先設定的適應值函數(shù)(與要解決的問題有關(guān))計算zi當前的適應值，即可衡量粒子位置的優(yōu)劣。vi=(vi1，vi2，…，vid，…，viD)為粒子 i的飛行速度，pi=(pi1，pi2，…，pid，…，piD)為粒子i迄今為止搜索到的最優(yōu)位置，pg=(pg1，pg2，…，pgd，…，pgD)為整個粒子群迄今為止搜索到的最優(yōu)位置。在每次迭代中，粒子根據(jù)式(1)、(2)更新速度和位置:

其中:i=1，2，…，m;d=1，2，…，D;k 是迭代次數(shù);w是慣性權(quán)重;r1和r2為[0，1]的隨機數(shù);c1和c2為學習因子。式(1)的第2項是“認知”部分，代表了粒子對自身的學習，第3部分是“社會”部分，代表著粒子間的協(xié)作。式(1)表示粒子根據(jù)它上一次迭代的速度、當前位置和自身最好經(jīng)驗與群體最好經(jīng)驗之間的距離來更新速度，然后粒子根據(jù)式(2)飛向新的位置。

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

2.1 粒子群濃度的計算

濃度的概念來自人工免疫算法［14］，這是近幾年才提出來的一種模擬生物免疫系統(tǒng)的隨機優(yōu)化方法。在求解優(yōu)化問題時，滿足約束條件的最優(yōu)解即是抗原，候選解即是抗體，抗體與抗原之間的親和力反映了候選解和最優(yōu)解得接近程度。為了實現(xiàn)抗體(粒子)的多樣性和避免未成熟收斂，采用抗體生存期望值對抗體濃度進行促進和抑制。在種群更新過程中，總是希望適應度高的粒子被保留下來，但是如果此類粒子過于集中，即濃度過高，則很難保證粒子的多樣性，很容易使算法陷入局部極優(yōu)，而丟失那些適應度較差但卻保持著較好進化趨勢的粒子。因此采用基于濃度機制的多樣性保持策略。第i個粒子的濃度［15］定義為

由式(3)可以推導出基于粒子濃度的概率選擇公式:

其中xi和f( xi)分別表示第i個粒子及其適應度函數(shù)值。由式(4)知，與抗體i相似的抗體越多，抗體i被選中的概率就越小;反之，與抗體i相似度的抗體越少，抗體i被選中的概率就越大。這使得低適應度個體也可以獲得進化的機會。因此，基于抗體濃度的概率選擇公式在理論上保證了抗體的多樣性。

3.2 粒子群的更新策略

當粒子進化到一定程度時，通過引入基于濃度選擇的概率公式，避免粒子群陷入局部最優(yōu)解。將所有粒子的概率按升序排列，排在前面的粒子濃度較高、概率較小，即在空間上該粒子處于較密集的位置，未避免粒子陷入局部最優(yōu)。給其賦以較大的慣性權(quán)重，擺脫個體最優(yōu)的影響，按照式(5)更新。

對于濃度較低但概率較大的粒子，根據(jù)免疫原理，筆者認為該粒子自身有著很好的進化前景，因此，粒子只受當前自身最優(yōu)和其自身速度的影響，而忽略粒子的群體最優(yōu)的作用，速度按照式(6)更新。

為了增加種群的多樣性，對其余濃度處于中間位置的部分粒子重新初始化。

3.3 改進的粒子群算法描述

步驟1 初始化參數(shù)，確定種群大小N、最大迭代次數(shù)itermax、學習因子c1和c2，待求解的為問題維數(shù)D、區(qū)間長度。

步驟2 初始化種群，即隨機產(chǎn)生各個粒子的初始位置和速度。

步驟3 根據(jù)目標函數(shù)評價每個粒子的適應度。

步驟4 對每個粒子，將其適應度與該粒子經(jīng)過的個體極值比較，若較好，則將該位置作為當前的最好位置pbest，然后再與整個粒子群經(jīng)歷過的全局極值比較，若較好，則更新gbest。

步驟5 根據(jù)速度和位置公式(1)、(2)更新粒子的速度和位置。

步驟6 當種群進化到一定程度時出現(xiàn)停滯，按照式(3)、(4)計算粒子的濃度及概率，并按升序排列:① 選擇排列在前個濃度較低的粒子，按式(5)更新速度;② 選擇排列在后3個濃度較高的粒子，按式(6)更新速度;③ 其余的6個處于中間位置的粒子，重新初始化，隨機賦值。

步驟7 計算更新后的粒子適應度，并更新自身最優(yōu)解與全局最優(yōu)位置。

步驟8 判斷是否達到最大迭代次數(shù)。重復步驟4～6，最后輸出全局最優(yōu)解。

4 測試函數(shù)及結(jié)果

為測試改進的粒子群算法的性能，本文選擇了5個著名的benchmark測試函數(shù)對該算法和標準PSO進行對比測試。

F1:著名的Sphere函數(shù)，它在xi=0時達到最小值0。

F2:Rosenbrock函數(shù)，也叫香蕉函數(shù)，一個經(jīng)典的優(yōu)化函數(shù)，在xi=1處達到全局最小值0。

F3:Rastrigin函數(shù)，有很多正弦凸起的局部極小點，在xi=0達到全局最小值0。

F4:Ackley函數(shù)，在xi=0時達到全局最小值0。

F5:Griewank函數(shù)，在xi=0時達到全局最小值0。

F1是一個連續(xù)的簡單單模態(tài)函數(shù)，通常用來分析算法的執(zhí)行性能。F2是一個經(jīng)典復雜優(yōu)化函數(shù)，它的全局最優(yōu)點位于一個平滑狹長的拋物線形山谷內(nèi)，由于函數(shù)僅僅為優(yōu)化算法提供了少量信息，使算法很難辨別搜索方向，找到全局最小點的機會微乎其微，因此F2通常用來評價優(yōu)化算法的執(zhí)行效率。F3、F4是典型的具有大量局部最優(yōu)點的復雜多峰函數(shù)，易使算法陷入局部最優(yōu)，而不能得到全局最優(yōu)解。F5是旋轉(zhuǎn)不可分離的多峰函數(shù)，類似于 Rastrigin 函數(shù)［16］。

試驗中 F1、F2、F4、F5的最大進化代數(shù)取500，F(xiàn)3的進化代數(shù)取1000，維數(shù)均取30維，學習因子 c1=c2=1.49445，慣性權(quán)重 w 從 0.9 到 0.4線性減少。為方便算法比較，適應值取以10為底的對數(shù)。運行結(jié)果見圖1～5。

圖1 F1:Sphere函數(shù)的適應度曲線

圖2 F2:Rosenbrock函數(shù)的適應度曲線

圖3 F3:Rastrigin函數(shù)的適應度曲線

圖4 F4:Ackley函數(shù)的適應度曲線

圖5 F5:Griewank函數(shù)的適應度曲線

從圖1～5的實驗結(jié)果可以看出:改進的PSO比標準PSO有著更好的搜索性能;對于較易收斂的F1和F5，改進的PSO算法收斂速度明顯加快，且收斂精度很高;尤其對于比較難于收斂的F3，改進的算法明顯優(yōu)于標準PSO;相對而言F2、F4雖然收斂速度差一些，但收斂精度要好于標準PSO。

5 結(jié)束語

標準粒子群算法由于群體的多樣性在進化后期變差，從而導致收斂后期速度變慢，易陷于局部最優(yōu)且收斂精度降低。改進的算法借鑒免疫學習中濃度的概念，按基于濃度的選擇概率來指導粒子群的更新，使群體保持了很好的多樣性，有效地避免了算法陷于局部最優(yōu)。實驗結(jié)果表明，該算法的搜索性能優(yōu)于標準的粒子群算法。

［1］Kennedy J，Eberhart R.Particle swarm optimization［C］//IEEE Int’1 Conf On Neural Networks.Perth，Australia:［s.n.］，1995:1942 －1948.

［2］Eberhart R，Kennedy J.A new optimizer using particle swarm theory［C］//Proc of the sixth international symposium on Micro Machine and Human Science.Nagoya，Japan:［s.n.］，1995:39 －43.

［3］劉玉敏，俞重遠，張建忠，等.粒子群優(yōu)化算法用于光纖布拉格光柵綜合問題的研究［J］.激光雜志，2005(4):69－70.

［4］陳莉，張宏立.粒子群算法在六自由度并聯(lián)機器人位置正解中的應用［J］.重慶理工大學學報:自然科學版，2010(8):86 －90.

［5］王紅玲，鄭綱，何劍鋒.基于改進粒子群算法的生鮮農(nóng)產(chǎn)品配送路徑優(yōu)化研究［J］.安徽農(nóng)業(yè)科學，2010(31):17961－17962.

［6］徐傳忠，王永初，楊冠魯.模擬退火粒子群算法的Volterra主動噪聲消除器［J］.自動化與儀器儀表，2010(3):116－117.

［7］石玉秋，黃玲，曹乃文，等.基于粒子群算法的噴灑參數(shù)優(yōu)化算法［J］.安徽農(nóng)業(yè)科學，2010(13):6677－6678.

［8］趙吉武，鄒長武，盧曉寧.基于粒子群算法的綜合暴雨強度公式［J］.安徽農(nóng)業(yè)科學，2010(30):17175－17176.

［9］郭志濤，袁金麗，張秀軍，等.基于改進的 PSO神經(jīng)網(wǎng)絡的手寫體漢字識別［J］.河北工業(yè)大學學報，2007，36(4):65－69.

［10］寧國忠，孟科，顏學峰，等.改進的粒子群算法及其在軟測量建模中的應用［J］.華東理工大學學報:自然科學版，2007，33(3):400 －404.

［11］唐英干，劉冬，關(guān)新平.基于粒子群和二維 Otsu方法的快速圖像分割［J］.控制與決策，2007，22(2):202－205.

［12］楊晶東，洪炳镕，蔡則蘇，等.基于粒子群優(yōu)化的移動機器人全局定位算法［J］.吉林大學學報:工學版，2007，37(6):1402 －1408.

［13］崔志華，曾建潮.微粒群優(yōu)化算法［M］.北京:科學出版社，2011.

［14］梁鴻生，郝勇娜，王凱等.免疫算法［J］.昆明理工大學學報:理工版，2003，28(5):72 －76.

［15］Gang Lu，De-jian Tan.Improvement on regulating definition of antibody density of immume algorithm［C］//Proceedings of the 9thinternational conference on neural information processing(ICONIP 02).USA:［s.n.］，2012:2669－2672.

［16］赫然，王永吉，王青，等.一種改進的自適應逃逸微粒群算法及實驗分析［J］.軟件學報，2005，12(16):2036－2044.