基于多尺度選擇性學(xué)習(xí)和探測(cè)-收縮機(jī)制的PSO 算法

夏學(xué)文,桂　凌,戴志鋒,謝承旺,魏　波

(1.華東交通大學(xué)軟件學(xué)院,江西南昌,330013;2.華東交通大學(xué)智能優(yōu)化與信息處理研究所,江西南昌,330013;

?

基于多尺度選擇性學(xué)習(xí)和探測(cè)-收縮機(jī)制的PSO 算法

夏學(xué)文1,2,桂凌3,戴志鋒4,謝承旺1,2,魏波1,2

(1.華東交通大學(xué)軟件學(xué)院,江西南昌,330013;2.華東交通大學(xué)智能優(yōu)化與信息處理研究所,江西南昌,330013;

3.華東交通大學(xué)經(jīng)濟(jì)管理學(xué)院,江西南昌,330013;4.湖北經(jīng)濟(jì)學(xué)院信息管理學(xué)院,湖北武漢,430205)

針對(duì)粒子群算法逃離局部最優(yōu)能力差、易早熟收斂、求解精度低等缺點(diǎn),提出了一種具有多尺度選擇性學(xué)習(xí)和探測(cè)-收縮機(jī)制的PSO 算法.在多尺度選擇性學(xué)習(xí)機(jī)制中,粒子根據(jù)其自身進(jìn)化狀態(tài)在拓?fù)浣Y(jié)構(gòu)、鄰居個(gè)體、目標(biāo)變量維等多個(gè)尺度上進(jìn)行選擇性學(xué)習(xí),提升粒子個(gè)體的學(xué)習(xí)效率;在探測(cè)-收縮機(jī)制中,算法利用歷史信息指導(dǎo)種群最優(yōu)解進(jìn)行探測(cè),提高其逃離局部最優(yōu)的能力,當(dāng)判斷種群歷史最優(yōu)解處于全局最優(yōu)解附近時(shí),執(zhí)行空間收縮策略,將種群的搜索空間限定在較小的一個(gè)區(qū)域,增強(qiáng)算法的開采能力,提高算法的求解精度.通過和其它PSO算法在22個(gè)典型測(cè)試函數(shù)的實(shí)驗(yàn)對(duì)比表明,本算法能有效克服早熟收斂、加快收斂速度、提高求解精度.

粒子群算法;早熟收斂;多尺度學(xué)習(xí);探測(cè)策略

1　引言

粒子群算法(Particle Swarm Optimization,PSO)是Kennedy[1]等人于1995年提出的一種群智能優(yōu)化算法,由于其理論簡(jiǎn)單、易于實(shí)現(xiàn),因此,PSO算法在提出后被迅速應(yīng)用于許多領(lǐng)域.影響PSO算法性能的主要因素是粒子位置迭代公式中的參數(shù)以及粒子鄰域的拓?fù)浣Y(jié)構(gòu),因此眾多學(xué)者在這兩方面進(jìn)行了廣泛的研究和改進(jìn).第一類改進(jìn)是通過調(diào)整PSO的參數(shù)來提升算法性能.如Shi和Eberhart[2]對(duì)PSO算法的速度項(xiàng)引入了慣性權(quán)重來平衡全局搜索性能和收斂速度,Asanga Ratnaweera[3]則引入時(shí)變的加速因子(Time-Varying Acceleration Coefficients)調(diào)節(jié)粒子的自我學(xué)習(xí)和社會(huì)學(xué)習(xí)的強(qiáng)度.Ioan[4]和Jiang[5]先后對(duì)標(biāo)準(zhǔn)粒子群算法進(jìn)行了收斂性分析,并提出了收斂性和穩(wěn)定性較好的一組參數(shù)選擇.Zhan[6]則對(duì)慣性因子、加速因子及其它多個(gè)參數(shù)進(jìn)行自適應(yīng)調(diào)整以改善算法綜合性能;第二類改進(jìn)是通過采用不同類型的鄰域拓?fù)浣Y(jié)構(gòu)來提高種群的多樣性、改善算法性能.如Suganthan[7]和Peram[8]分別利用粒子間歐式距離和粒子適應(yīng)值來確定粒子的學(xué)習(xí)模式,通過這種動(dòng)態(tài)選擇學(xué)習(xí)對(duì)象的策略,改善種群的多樣性.Rui[9]和Liang[10]先后提出了完全感知PSO算法和綜合學(xué)習(xí)PSO算法,這兩種算法的共同特點(diǎn)是通過豐富粒子的社會(huì)學(xué)習(xí)模式,改善種群多樣性.眾多研究結(jié)果也表明動(dòng)態(tài)、多樣的鄰域拓?fù)浣Y(jié)構(gòu)對(duì)于多峰函數(shù)優(yōu)化具有很好的效果[11,12].需要指出的是,對(duì)PSO算法的改進(jìn)并非局限于某一方面的改進(jìn),很多時(shí)候是對(duì)參數(shù)、拓?fù)浣Y(jié)構(gòu)等同時(shí)進(jìn)行改進(jìn)[13～17].

上述對(duì)PSO算法的改進(jìn)的目的主要是在防止早熟收斂的同時(shí)盡量提高求解精度,但當(dāng)種群已經(jīng)陷入局部最優(yōu)時(shí),卻沒有先驗(yàn)知識(shí)指導(dǎo)種群跳出局部最優(yōu).因此,本文提出了一種具有多尺度選擇性學(xué)習(xí)和探測(cè)-收縮機(jī)制的PSO 算法(Multiscale-selective-learning hybrid with Detecting-shrinking PSO,MDPSO),MDPSO算法根據(jù)不同進(jìn)化階段時(shí)種群和個(gè)體生存環(huán)境的不同,在多個(gè)尺度上進(jìn)行了學(xué)習(xí)模式的選擇.同時(shí),MDPSO還利用探測(cè)機(jī)制對(duì)粒子個(gè)體的歷史信息進(jìn)行周期采樣與統(tǒng)計(jì),利用統(tǒng)計(jì)結(jié)果指導(dǎo)種群進(jìn)行探測(cè)和搜索空間的收縮.實(shí)驗(yàn)結(jié)果表明,上述改良機(jī)制有效地提升了PSO算法的綜合性能.

2　PSO算法

(1)

(2)

其中,ω為慣性權(quán)重,表示前一時(shí)刻的速度對(duì)本次移動(dòng)的影響,用于平衡算法的收斂速度和全局搜索能力,較大的ω有利于全局搜索,而較小的ω則可以提高算法的局部開采能力和求解精度[2,6];c1和c2為學(xué)習(xí)因子,表示粒子自我學(xué)習(xí)和社會(huì)學(xué)習(xí)的強(qiáng)度,即用來調(diào)節(jié)粒子向pBesti和gBest的學(xué)習(xí)強(qiáng)度;r1和r2為[0,1]內(nèi)均勻分布的隨機(jī)數(shù),用來增強(qiáng)算法搜索的隨機(jī)性.

3　MDPSO算法

PSO算法在復(fù)雜多峰函數(shù)優(yōu)化中較易出現(xiàn)早熟收斂,因此很多學(xué)者通過不同的策略來增強(qiáng)種群多樣性,從而避免算法陷入局部最優(yōu),但這也使得算法的收斂速度變慢.同時(shí),當(dāng)種群已陷入局部最優(yōu)后,缺少具有指導(dǎo)意義的逃逸策略來幫助種群跳出局部最優(yōu)并找到更優(yōu)位置.為此,本文提出了一種具有多尺度選擇性學(xué)習(xí)和探測(cè)-收縮機(jī)制的PSO算法(Multiscale-selective-learninghybridwithDetecting-shrinkingPSO,MDPSO).在MDPSO中,種群中的粒子個(gè)體將種群進(jìn)化過程和自身進(jìn)化狀態(tài)相結(jié)合,在拓?fù)浣Y(jié)構(gòu)、領(lǐng)域個(gè)體以及不同的變量維等多個(gè)尺度上進(jìn)行選擇性學(xué)習(xí).此外,為了增強(qiáng)算法跳出局部最優(yōu)的能力,還賦予了種群歷史最優(yōu)解gBest探測(cè)學(xué)習(xí)的能力.同時(shí),根據(jù)gBest以及pBesti的統(tǒng)計(jì)信息,對(duì)種群的搜索空間進(jìn)行收縮,以提高算法的求解精度.

3.1多尺度選擇性學(xué)習(xí)機(jī)制

3.1.1鄰域拓?fù)浣Y(jié)構(gòu)的選擇

為了改善PSO算法綜合性能,必須保證算法在進(jìn)化初期具有更好的全局搜索能力,盡可能地“勘探”到全局最優(yōu)解所在區(qū)域,避免“早熟”收斂;而在進(jìn)化后期,則希望種群能以較快的速度收斂到最優(yōu)解附近,提高求解精度.因此,本文提出了一種隨進(jìn)化過程依概率選擇不同鄰域拓?fù)浣Y(jié)構(gòu)的策略.該策略可描述如下:

(3)

其中,TOPneighbor表示種群的鄰域拓?fù)浣Y(jié)構(gòu);topstar和topring分別為星型和環(huán)形鄰域拓?fù)浣Y(jié)構(gòu);rand是[0,1]間均勻分布的隨機(jī)數(shù).從式(3)可看出:在進(jìn)化初期,種群選擇topring的概率較大,有利于算法保持種群多樣性,避免“早熟”收斂;而在進(jìn)化后期,種群選擇topstar的概率變大,種群的收斂速度得到提升,從而提高了算法的收斂速度和求解精度.

3.1.2鄰域粒子與目標(biāo)變量維的選擇

本文對(duì)粒子個(gè)體設(shè)置了一個(gè)最大連續(xù)“停滯”代數(shù)MaxStagind,當(dāng)粒子i在進(jìn)化過程中連續(xù)“停滯”次數(shù)stayi達(dá)到該閾值時(shí),將重新選擇學(xué)習(xí)對(duì)象及學(xué)習(xí)方式,具體策略如下:

(1)當(dāng)pBesti是其鄰域內(nèi)粒子的歷史最優(yōu)解中最優(yōu),則粒子i在進(jìn)行社會(huì)學(xué)習(xí)時(shí),從現(xiàn)有鄰域粒子中獲取有益信息的概率較低,此時(shí)應(yīng)考慮重新選擇合適的粒子作為其鄰域粒子,選擇策略可描述如下:

(4)

(5)

3.2探測(cè)-收縮機(jī)制

3.2.1探測(cè)機(jī)制

在復(fù)雜多維函數(shù)的優(yōu)化過程中,gBest的每維變量一般很難同時(shí)處于全局最優(yōu)解附近,這時(shí)就需要gBest有目的地探測(cè)該維空間的其它區(qū)域,以便能跳出當(dāng)前的局部最優(yōu).

為方便探測(cè)行為的操作,每維變量空間被等分為多個(gè)互不相交的子區(qū)間,即:

(6)

其中,Si為第i維(1≤i≤D)變量的搜索空間;si,j為第i維的第j個(gè) (1≤j≤M)搜索子區(qū)間;M 為第i維變量空間劃分為的子區(qū)間個(gè)數(shù).對(duì)搜索空間進(jìn)行劃分后,就可以確定gBest每維變量所在的子區(qū)間,同時(shí),gBest將以子區(qū)間為單位進(jìn)行探測(cè).為了使gBest的探測(cè)更有目的性,本文將利用粒子群的pBesti和gBest的統(tǒng)計(jì)信息來確定各子區(qū)間的優(yōu)勢(shì)度,結(jié)合當(dāng)前gBest所處的子區(qū)間來選擇合適的目標(biāo)子區(qū)間進(jìn)行探測(cè).具體為:通過每隔Cycle代對(duì)種群中pBesti進(jìn)行周期采樣和統(tǒng)計(jì),獲取每維變量在各個(gè)子區(qū)間上的優(yōu)勢(shì)度,gBest將利用子區(qū)間的優(yōu)勢(shì)度來指導(dǎo)其探測(cè)過程.

定義1子區(qū)間優(yōu)勢(shì)度.若pbesti,j為第i個(gè)粒子的歷史最優(yōu)解在第j維變量上的取值,sj,k為第j維變量第k個(gè)子區(qū)間,則當(dāng)前種群第j維變量第k個(gè)子區(qū)間的優(yōu)勢(shì)度Fj,k(1≤j≤D,1≤k

(7)

根據(jù)Fj,k值的大小,可將每維變量的子區(qū)間分為三類:優(yōu)勢(shì)子區(qū)間(superiorsubregion)、劣勢(shì)子區(qū)間(inferiorsubregion)和平凡子區(qū)間(ordinarysubregion).

定義2優(yōu)勢(shì)子區(qū)間.第j維變量?jī)?yōu)勢(shì)子區(qū)間為:

Supj={sj,k|max{Fj,k}},(1≤j≤D,1≤k

定義3劣勢(shì)子區(qū)間.第j維變量劣勢(shì)子區(qū)間為:

Infj={sj,k|min{Fj,k}},(1≤j≤D,1≤k

定義4平凡子區(qū)間.第j維變量平凡子區(qū)間為:

Ordj=Sj-(Supj+Infj),(1≤j≤D,1≤k

gBest根據(jù)第j維變量取值所屬的子區(qū)間類別進(jìn)行相應(yīng)的探測(cè).相應(yīng)的探測(cè)過程如下:

(1)若gbestj∈Supj,說明此時(shí)gbestj對(duì)種群第j維變量的影響很大,大部分粒子的pbesti,j取值都在gbestj附近,而在Infj內(nèi)的取值則很少(甚至沒有),若在Infj中存在第j維變量的全局最優(yōu)解,則粒子群在后續(xù)飛行的過程中發(fā)現(xiàn)該維全局最優(yōu)解的概率非常低或者需要更多次迭代.因此,gBest應(yīng)該首先選擇對(duì)Infj進(jìn)行探測(cè),以跳出當(dāng)前的局部最優(yōu).

(2)若gbestj∈Infj,說明此時(shí)gbestj與當(dāng)前種群中大部分粒子的pbesti,j不在同一子區(qū)間.出現(xiàn)這種現(xiàn)象有三種可能性:第一種是大部分pbesti,j陷入了局部最優(yōu),而當(dāng)前的gbestj處于第j維的全局最優(yōu)解附近,這種情況下,不必進(jìn)行探測(cè);第二種是大部分的pbesti,j均集中在全局最優(yōu)解附近,而gbestj則遠(yuǎn)離該區(qū)域,這時(shí)gBest可以選擇在Supj內(nèi)進(jìn)行探測(cè);第三種情況是當(dāng)前粒子種群在該維的取值都不在全局最優(yōu)區(qū)間,此時(shí)也不必進(jìn)行探測(cè).綜合考慮以上幾種情況,為了提高算法的收斂速度,此時(shí)選擇向Supj進(jìn)行探測(cè).

(3)若gbestj∈Ordj,gBest選擇在其它任一子區(qū)間內(nèi)進(jìn)行探測(cè).此時(shí)的探測(cè)過程和一般的變異操作類似,目的是為了增強(qiáng)種群的多樣性.

gbestj在進(jìn)行上述3種探測(cè)操作時(shí)均采用的貪心策略,即在相應(yīng)子區(qū)間隨機(jī)選擇值x,若將x替換gbestj后能改善gBest的適應(yīng)值,則保留x,并替換原gBest,否則將拋棄x.為防止gBest對(duì)同一子區(qū)間進(jìn)行連續(xù)多次探測(cè),本文采用了禁忌探測(cè)機(jī)制,即每次探測(cè)完某個(gè)子區(qū)間后,為該子區(qū)間置“已探測(cè)”標(biāo)志,下次再進(jìn)行探測(cè)時(shí)則不再將該子區(qū)間納為探測(cè)對(duì)象,而是選擇剩余子區(qū)間中符合要求的子區(qū)間.當(dāng)所有子區(qū)間都已被置為“已探測(cè)”,則清除所有子區(qū)間的“已探測(cè)”標(biāo)志.這樣,就保證了gBest在對(duì)重點(diǎn)子區(qū)間進(jìn)行探測(cè)的同時(shí),也滿足了gBest對(duì)整個(gè)搜索空間的遍歷性,增強(qiáng)了其搜索能力.綜上所述,gBest在第j維的探測(cè)過程可描述為算法1.

3.2.2收縮機(jī)制

當(dāng)算法在第j維進(jìn)行多次探測(cè)后,確定全局最優(yōu)解存在于某個(gè)或某些子區(qū)間中,就有必要將第j維的搜索限定在一定的有效區(qū)域內(nèi)(本文稱此過程為空間收縮),以加快算法收斂速度,提高求解精度.本文將以gBest在第j維上進(jìn)行多次探測(cè)后,其適應(yīng)值連續(xù)停滯代數(shù)作為執(zhí)行空間收縮的指標(biāo).這里,首先有如下定義:

(8)

3.3MDPSO算法

綜合3.1～3.2中提出的策略,MDPSO算法可描述為算法3.

4　仿真實(shí)驗(yàn)及結(jié)果分析

MDPSO算法的參數(shù)設(shè)置:種群規(guī)模N=20,粒子最大連續(xù)停滯代數(shù)MaxStagind=5,每維變量分割為的子區(qū)間數(shù)M=8;統(tǒng)計(jì)周期Cycle為3;種群停滯閾值MaxStagpop將隨著進(jìn)化代數(shù)線性遞增,其取值范圍為[20,100].實(shí)驗(yàn)環(huán)境為:Inteli3CPU2.93GHz.RAM4.00GB,Windows7操作系統(tǒng),MATLAB2009a.

4.1測(cè)試函數(shù)

本文選取了22個(gè)Benchmark函數(shù)進(jìn)行了對(duì)比測(cè)試,各函數(shù)簡(jiǎn)要說明如下:

·f1:Sphere,x∈[-100,100]D,Accept-error:0.001

·f2:Schwefel’sP2.22,x∈[-10,10]D,Accept-error:0.001

·f3:Rosenbrock,x∈[-30,30]D,Accept-error:100

·f4:Step,x∈[-100,100],Accept-error:0

·f5:Sumofdifferentpower,x∈[-1,1]D,Accept-error:0.001

·f6:Ackley,x∈[-32,32]D,Accept-error:0.001

·f7:Alpine,x∈[-10,10],Accept-error:0.001

·f8:Schwefel’sP1.2,x∈[-500,500]D,Accept-error:1000

·f9:Rastrigin,x∈[-5.12,5.12]D,Accept-error:100

·f10:Rastrigin-noncont,x∈[-5.12,5.12]D,Accept-error:100

·f11:Griewank,x∈[-600,600]D,Accept-error:0.01

·f12:Weierstrass,x∈[-0.5,0.5]D,Accept-error:0.01

·f13:GeneralizedPenalized,x∈[-50,50]D,Accept-error:0.001

·f14:ShiftedSphere,x∈[-100,100]D,Accept-error:0.001

·f15:ShiftedSchwefelP1.2,x∈[-100,100]D,Accept-error:1000

·f16:ShiftedSchwefelP1.2withNoise,x∈[-100,100]D,Accept-error:1000

·f17:ShiftedRosenbrock,x∈[-100,100]D,Accept-error:1000

·f18:ShiftedRotatedGriewank,x∈[-600,600]D,Accept-error:1000

·f19:ShiftedRotatedAckley,x∈[-32,32]D,Accept-error:1000

·f20:ShiftedRastrigin,x∈[-5,5]D,Accept-error:1000

·f21:ShiftedRotatedRastrigin,x∈[-5,5]D,Accept-error:1000

·f22:ExpandedExtendedGriewank’splusRosenbrock,x∈[-3,1]D,Accept-error:1000

其中,f1～f5為單峰函數(shù),主要用來檢驗(yàn)算法的求解精度;f6～f13為多峰函數(shù),主要用來檢驗(yàn)算法的全局搜索能力.f14～f22為shifted、rotated以及復(fù)合函數(shù).本文實(shí)驗(yàn)中,變量維數(shù)D=30,最大評(píng)價(jià)次數(shù)maxFEs=1000*D.每個(gè)函數(shù)獨(dú)立測(cè)試30次,取其統(tǒng)計(jì)結(jié)果(均值Mean、標(biāo)準(zhǔn)方差Std.Dev)進(jìn)行比較,加粗?jǐn)?shù)據(jù)表示對(duì)比算法在相應(yīng)函數(shù)上得到的最優(yōu)結(jié)果.

4.2不同策略的效果

為了檢驗(yàn)本文提出的不同策略對(duì)算法不同性能方面的貢獻(xiàn)度,我們選取了部分函數(shù)進(jìn)行了測(cè)試(f1,f4為單峰函數(shù),f6,f8,f9,f12為多峰函數(shù)),實(shí)驗(yàn)結(jié)果見表1.PSO-1和PSO-2分別表示從MDPSO算法中移除了多尺度選擇性學(xué)習(xí)機(jī)制和探測(cè)-收縮機(jī)制后得到的算法.

表1　不同策略的實(shí)驗(yàn)結(jié)果對(duì)比

從表1中可以看出,本文提出的策略有效改善了算法的性能,MDPSO在測(cè)試的6個(gè)函數(shù)中除f8外,都取得到最優(yōu)的結(jié)果.從表中也看出:移除了探測(cè)-收縮機(jī)制后,算法的性能急劇下降,這說明合理利用種群的歷史信息來指導(dǎo)粒子有目的地進(jìn)行探測(cè)是有效、可行的;移除了多尺度選擇性學(xué)習(xí)機(jī)制后,算法對(duì)大部分測(cè)試函數(shù)的求解精度都有所下降,從對(duì)f9優(yōu)化的結(jié)果可以看出,該策略提高了算法的學(xué)習(xí)效率,大大提升了求解精度.實(shí)驗(yàn)結(jié)果表明:本文提出的策略都對(duì)原PSO算法在不同性能指標(biāo)上進(jìn)行了優(yōu)化與提升.

4.3求解精度

為了進(jìn)一步說明本文算法的效果,這里選取了近年來的較為優(yōu)秀的一些PSO算法進(jìn)行實(shí)驗(yàn)對(duì)比,相關(guān)算法及其參數(shù)設(shè)置見表2.其中,DMS-PSO算法的種群規(guī)模設(shè)置為10個(gè)子種群,每個(gè)子種群規(guī)模為3,其它算法的種群規(guī)模均為20.其中,Merits表示該算法在測(cè)試函數(shù)上表現(xiàn)最優(yōu)的次數(shù).加粗?jǐn)?shù)值表示對(duì)比算法在相應(yīng)函數(shù)上得到的最優(yōu)結(jié)果.具體結(jié)果如表3所示.

表2　相關(guān)PSO算法的參數(shù)設(shè)置

表3　9種算法在22個(gè)測(cè)試函數(shù)上的實(shí)驗(yàn)結(jié)果對(duì)比

續(xù)表

從表3可以看出,本文提出的MDPSO在11個(gè)函數(shù)上都取得了最優(yōu)表現(xiàn),尤其是在f6、f9、f10、f13和f20等幾個(gè)多峰函數(shù)上取得了非常明顯的優(yōu)勢(shì),這說明本文提出的幾種策略可以有效地幫助算法跳出局部最優(yōu);DMS-PSO則在7個(gè)函數(shù)上取得了最優(yōu)表現(xiàn),這也說明利用小規(guī)模子種群間的協(xié)作是提升群智能算法的有效途徑之一.需要指出的是,盡管CLPSO只在1個(gè)函數(shù)上取得最優(yōu)表現(xiàn),但其在所有多峰函數(shù)上均取得了前3名的表現(xiàn),在多峰函數(shù)優(yōu)化上表現(xiàn)出良好的性能.

4.4t-檢驗(yàn)

為了驗(yàn)證數(shù)據(jù)的置信度,本文還進(jìn)一步對(duì)上述算法的優(yōu)化結(jié)果進(jìn)行了t-檢驗(yàn),置信水平α=0.05,檢驗(yàn)結(jié)果如表4所示.表中,MDPSO顯著優(yōu)于對(duì)比算法的用黑體標(biāo)出,顯著劣于對(duì)比算法的用方框標(biāo)出,Better、Same和Worse分別表示MDPSO比相應(yīng)的對(duì)比算法在t-檢驗(yàn)結(jié)果中具有顯著更優(yōu)、相同和顯著更劣的函數(shù)個(gè)數(shù).盡管MDPSO和FIPS、CLPSO、DMS-PSO、GDPSO等在各自的30次獨(dú)立測(cè)試中,均在函數(shù)f4上取得了全局最優(yōu)解(表中用-表示),但MDPSO能以最少的評(píng)價(jià)次數(shù)和時(shí)間耗費(fèi)取得全局最優(yōu)解(結(jié)果見表5).t-檢驗(yàn)的結(jié)果表明,MDPSO算法的綜合性能最優(yōu),該結(jié)論也驗(yàn)證了表3的實(shí)驗(yàn)結(jié)果.

4.5收斂速度

表5給出了對(duì)比算法在達(dá)到設(shè)定精度(Accept-error)時(shí)所需的評(píng)價(jià)次數(shù)及耗時(shí),其中“-”表示該算法在相應(yīng)函數(shù)上未能在最大評(píng)價(jià)次數(shù)內(nèi)達(dá)到所需精度.表中數(shù)據(jù)均為獨(dú)立運(yùn)行30次的平均值,其中平均評(píng)價(jià)次數(shù)Fes和耗時(shí)Time均為算法達(dá)到設(shè)定精度時(shí)的取值,Ratio表示在30次獨(dú)立運(yùn)行中算法能在最大評(píng)價(jià)次數(shù)內(nèi)獲得精度誤差要求的解的比例.

從表5可看出,MDPSO在大部分函數(shù)上均能以最少的評(píng)價(jià)次數(shù)和耗時(shí)取得設(shè)定精度的解.盡管本文提出的MDPSO算法中引入了多種不同的策略,在算法描述上較為復(fù)雜,但這三種策略本身耗時(shí)其實(shí)很少.一方面是因?yàn)檫@些策略并非每輪迭代都執(zhí)行,而是種群進(jìn)化到一定時(shí)期是才執(zhí)行一次;另一方面,每個(gè)策略本身的運(yùn)算也很簡(jiǎn)單,耗時(shí)較少,因此,加入這些策略后的算法在性能提升的同時(shí),運(yùn)算量增加很少.不同算法在測(cè)試函數(shù)上的收斂曲線也說明了MDPSO具有較快的速度,由于篇幅有限,本文省略了算法收斂曲線對(duì)比圖.

表4　均值的t-檢驗(yàn)結(jié)果(α=0.05)

續(xù)表

表5　設(shè)定誤差精度下的成功率及收斂速度對(duì)比

續(xù)表

5　結(jié)束語(yǔ)

本文提出了多尺度選擇性學(xué)習(xí)和探測(cè)-收縮機(jī)制來提高PSO的性能.在多尺度選擇性學(xué)習(xí)機(jī)制中,當(dāng)個(gè)體進(jìn)化出現(xiàn)停滯現(xiàn)象時(shí),該個(gè)體根據(jù)其自身與鄰居個(gè)體間適應(yīng)值的相對(duì)優(yōu)劣關(guān)系對(duì)拓?fù)浣Y(jié)構(gòu)、鄰居個(gè)體、目標(biāo)變量維等多個(gè)尺度上進(jìn)行變化與調(diào)整,實(shí)現(xiàn)多尺度上的自適應(yīng)學(xué)習(xí),從而幫助個(gè)體更有效地進(jìn)行學(xué)習(xí);探測(cè)-收縮策略則首先利用粒子個(gè)體的歷史最優(yōu)解的統(tǒng)計(jì)信息指導(dǎo)種群歷史最優(yōu)解進(jìn)行探測(cè),提高算法的全局搜索能力和跳出局部最優(yōu)的能力,當(dāng)種群歷史最優(yōu)解長(zhǎng)期在某局部區(qū)域搜索時(shí),則執(zhí)行空間收縮策略,將整個(gè)種群的搜索過程限定在更小的空間內(nèi),以提高算法的求解精度和收斂速度.通過和其它8個(gè)優(yōu)秀的PSO算法在22個(gè)測(cè)試函數(shù)上的實(shí)驗(yàn)對(duì)比表明,本文提出的策略能提高了算法的綜合性能,可以有效地幫助算法逃離局部最優(yōu),同時(shí)也具有較快的收斂速度.由于本文提出的改進(jìn)策略具有較好的通用性,下一步將利用該思想對(duì)其它群智能算法,如蟻群算法、蜂群算法等開展相關(guān)的研究.

[1]Kennedy J,Eberhart R C.Particle swarm optimization[A].Proceedings of IEEE International Conference on Neural Networks[C].Piscataway:IEEE Press,1995.1942-1948.

[2]Shi Y,Eberhart R C,Fuzzy adaptive particle swarm optimization[A].Proceedings of IEEE Congress on Evolutionary Computation[C].Seoul,Korea:IEEE Press,2001.1011-106.

[3]Asanga Ratnaweera,Saman K Halgamuge.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J].IEEE Transactions on Evolutionary Computation,2004,8(3):240-255.

[4]Ioan Cristian Trelea.The particle swarm optimization algorithm:convergence analysis and parameter selection[J].Information Processing Letters,2003,85(6):317-325.

[5]M Jiang,et al.Stochastic convergence analysis and parameter selection of the standard particle swarm optimization algorithm[J].Information Processing Letters,2007,102(1):8-16.

[6]Zhan Z H,Zhang J,Li Y,et al.Adaptive particle swarm optimization[J].IEEE Transaction on Systems,Man,and Cybernetics-Part B:Cybernetics,2009,39(6):1362-1381.

[7]Suganthan P N,Particle swarm optimizer with neighborhood operator[A].Proceedings of IEEE Congress on Evolutionary Computation[C].Washington,D C,USA:IEEE Press,1999.1958-1962.

[8]T Peram,K Veeramachaneni,C K Mohan.Fitness-distance-ratio based particle swarm optimization[A].Proceedings of Swarm Intelligence Symp.[C].Indianapolis,Indiana,USA:IEEE Press,2003.174-181.

[9]Rui Mendes,James Kennedy,José Neves.The fully informed particle swarm-simpler,maybe better[J].IEEE Transactions on Evolutionary Computation,2004,8(3):204-210.

[10]Liang J J,Qin A K,Suganthan P N,et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Transaction on Evolutionary Computation,2006,10(3):281-295.

[11]倪慶劍,等.一種基于可變多簇結(jié)構(gòu)的動(dòng)態(tài)概率粒子群優(yōu)化算法[J].軟件學(xué)報(bào),2009,20(2):339-349.

NI Qing-Jian,ZHANG Zhi-Zheng,WANG Zhen-Zhen,et al.Dynamic probabilistic particle swarm optimization based on varying multi-cluster structure[J].Journal of Software,2009,20(2):339-349.(in Chinese)

[12]湯可宗,柳炳祥,楊靜宇,等.雙中心粒子群優(yōu)化算法[J].計(jì)算機(jī)研究與發(fā)展,2012,49(5):1086-1094.

Tang Kezong,et al.Double center particle swarm optimization algorithm[J].Journal of Computer Research and Development,2012,49(5):1086-1094.(in Chinese)

[13]Xin Jin,Yongquan Liang,Dongping Tian,et al.Particle swarm optimization using dimension selection methods[J].Applied Mathematics and Computation,2013,219(10):5185-5197.

[14]喻飛,李元香,魏波 等,透鏡成像反學(xué)習(xí)策略在粒子群算法中的應(yīng)用[J].電子學(xué)報(bào),2014,42(2):230-235.YU Fei,LI Yuan-xiang,WEI Bo et al.The application of a novel OBL based on lens imaging principle in PSO[J].Acta Electronica Sinica,2014,42(2):230-235.(in Chinese)

[15]Xuewen Xia,et al.A quantum genetic algorithm based on cellular automata model,International Journal of Modelling[J].Identification and Control,2013,18(3):243-250.

[16]Xuewen Xia,Jingnan Liu,Zhongbo Hu.An improved particle swarm optimizer based on tabu detecting and local learning strategy in a shrunk search space[J].Applied Soft Computing,2014,23(10):76-90.

[17]Zhao S Z,Liang J J,Suganthan P N.Dynamic multi-swarm particle swarm optimizer with local search for large scale global optimization[A].Proceedings of IEEE Congress on Evolutionary Computation[C].Hong Kong,China:IEEE Press,2008.3845-3852.

夏學(xué)文男,1974年出生,博士,華東交通大學(xué)副教授,研究方向:計(jì)算智能及其應(yīng)用

E-mail:laughkid@163.com;xwxia@whu.edu.cn

桂凌女,1977年出生,本科,華東交通大學(xué)交通運(yùn)輸與經(jīng)濟(jì)研究所實(shí)驗(yàn)師,研究方向:計(jì)算機(jī)應(yīng)用.

戴志鋒男,1968年出生,博士,湖北經(jīng)濟(jì)學(xué)院副教授,研究方向:智能算法.

謝承旺男,1974年出生,博士,華東交通大學(xué)副教授,研究方向:多目標(biāo)優(yōu)化算法.

魏波男,1983年出生,博士,華東交通大學(xué)講師,研究方向:智能算法.

A PSO Algorithm Based on Multiscale-Selective-Learning and Detecting-Shrinking Strategies

XIA Xue-wen1,2,GUI Ling3,DAI Zhi-feng4,XIE Cheng-wang1,2,WEI Bo1,2

(1.SchoolofSoftware,EastChinaJiaotongUniversity,Nanchang,Jiangxi330013,China; 2.IntelligentOptimization&InformationProcessingLab,EastChinaJiaotongUniversity,Nanchang,Jiangxi330013,China; 3.SchoolofEconomicsandManagement,EastChinaJiaotongUniversity,Nanchang,Jiangxi330013,China4.SchoolofInformationManagement,HubeiUniversityofEconomics,Wuhan,Hubei430205,China)

To overcome the shortcomings the traditional particle swarm optimization algorithm (PSO),such as poor ability to escape a local optimal,premature convergence and low precision,we proposed a new PSO based on multiscale-selective-learning and detecting-shrinking strategies,which called MDPSO in short.In the multiscale-selective-learning strategy,a particle executes a multiscale learning process to improve its studying efficiency by adopting its topology,selecting neighbors,and choosing target variable dimensions.In the detecting-shrinking strategy,particles′ historical best solutions are periodic sampling and some useful information,which extracting from the sampling results,is used to direct the best solutions to carry out a detecting operation.The aims of the strategy are to improve PSO′s global searching ability and to help the population escape a local optimal solution.While the best solution situating around a global optimal solution,the algorithm implements the shrinking strategy to confine the search space to a small one the aims of which are to improve the PSO′s exploitation ability and to increase the accuracy of the solutions.The proposed method was applied to twenty-two typical benchmark functions,and the comparisons of the performance between MDPSO and other eight PSO algorithms were experimented.The results suggest that the proposed strategies can effectively overcome the premature convergence,speed up the convergence and improve solutions accuracy.

particle swarm optimization;premature convergence;multiscale learning;detecting strategy

2014-09-05;

2014-11-12;責(zé)任編輯:馬蘭英

國(guó)家自然科學(xué)基金 (No.41231174,No.61165004,No.61562028);華東交通大學(xué)校立科研項(xiàng)目(No.14JG03);江西省教育廳科研項(xiàng)目(No.GJJ150539);江西省自然科學(xué)基金(N0.2015BAB207022);新疆維吾爾自治區(qū)高?？蒲杏?jì)劃青年教師科研啟動(dòng)基金(No.2014JYT041606)

TP301

A

0372-2112 (2016)05-1090-11

電子學(xué)報(bào)URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.05.012