李慶芳，孫合明

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

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

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

1 標(biāo)準(zhǔn)粒子群優(yōu)化算法

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

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

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

2.1 粒子群濃度的計(jì)算

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

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

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

3.2 粒子群的更新策略

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

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

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

3.3 改進(jìn)的粒子群算法描述

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

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

步驟3 根據(jù)目標(biāo)函數(shù)評價(jià)每個(gè)粒子的適應(yīng)度。

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

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

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

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

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

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

為測試改進(jìn)的粒子群算法的性能，本文選擇了5個(gè)著名的benchmark測試函數(shù)對該算法和標(biāo)準(zhǔn)PSO進(jìn)行對比測試。

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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

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

［14］梁鴻生，郝勇娜，王凱等.免疫算法［J］.昆明理工大學(xué)學(xué)報(bào):理工版，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ìn)的自適應(yīng)逃逸微粒群算法及實(shí)驗(yàn)分析［J］.軟件學(xué)報(bào)，2005，12(16):2036－2044.