偽隨機(jī)數(shù)質(zhì)量對(duì)簡(jiǎn)單粒子群優(yōu)化算法性能的影響

譚 陽(yáng)

(湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院，湖南長(zhǎng)沙 410004)

偽隨機(jī)數(shù)質(zhì)量對(duì)簡(jiǎn)單粒子群優(yōu)化算法性能的影響

譚 陽(yáng)*

(湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院，湖南長(zhǎng)沙 410004)

偽隨機(jī)數(shù)對(duì)粒子群優(yōu)化算法的性能影響主要體現(xiàn)在算法種群多樣性上。低質(zhì)量的偽隨機(jī)數(shù)會(huì)導(dǎo)致粒子群優(yōu)化算法的性能出現(xiàn)不穩(wěn)定的現(xiàn)象，通過(guò)對(duì)幾種典型偽隨機(jī)數(shù)的分析比較之后得出，粒子編碼長(zhǎng)度和偽隨機(jī)數(shù)的周期的相互作用才是導(dǎo)致算法不穩(wěn)定的原因。相關(guān)實(shí)驗(yàn)也驗(yàn)證了這一結(jié)果。

偽隨機(jī)數(shù);粒子群優(yōu)化算法;種群多樣性;海明距離

一、引言

通常把通過(guò)軟件或數(shù)字電路實(shí)現(xiàn)一種確定性方法稱為偽隨機(jī)數(shù)算法，偽隨機(jī)數(shù)因?yàn)槠渖珊褪褂檬址奖?，所以被廣泛地應(yīng)用于各種科學(xué)和工程領(lǐng)域。目前各種偽隨機(jī)數(shù)發(fā)生器(pseudo－random number generator，PRNG)的類型很多，衡量其質(zhì)量的高低主要通過(guò)各種統(tǒng)計(jì)檢驗(yàn)來(lái)進(jìn)行，其中Knuth和Diehard 是兩個(gè)常用的統(tǒng)計(jì)檢驗(yàn)集［1］［2］。粒子群優(yōu)化算法 (Particle Swarm Optimization，PSO)是Kenney和Eberhart于1995年提出的一種智能優(yōu)化算法［3］，PSO算法源于對(duì)鳥群和魚群等群體運(yùn)動(dòng)行為的研究，與其他的演化算法一樣也是一種基于迭代的優(yōu)化工具;但相比較而言它具有算法簡(jiǎn)單，收斂速度快且對(duì)目標(biāo)函數(shù)要求少等特點(diǎn)，通常PSO采用下式(1)的作為其標(biāo)準(zhǔn)算法:

Vi+1=c0vi+c1(pbesti－xi)+c2(gbesti－xi)

xi+1=xi+vi+1(1)

其中，式(1)中 i=1，2，…，N，N 為該群體中粒子的總數(shù);vi是第i個(gè)粒子的速度向量;xi是第i個(gè)粒子當(dāng)前的位置;c0，c1，c2為非負(fù)常數(shù)用以表示群體的認(rèn)知系數(shù)，c0為粒子的慣性因子一般取(0，1)之間的隨機(jī)數(shù);c1，c2為粒子的學(xué)習(xí)因子一般取(0，2)之間的隨機(jī)數(shù);式(1)中的c1(pbesti－xi)部分被稱為“認(rèn)知”部分，表示粒子本身的思考，而c2(gbestixi)部分被稱為“社會(huì)”部分，表示粒子間的信息共享與合作。每一維粒子的速度都會(huì)被限制在一個(gè)最大速度 vmax(vmax＞0) 內(nèi)，即vi＞vmax或 vi＜ －max時(shí)，vi=vmax或vi=－vmax。粒子群的初始位置和速度隨機(jī)產(chǎn)生，然后按照公式(1)進(jìn)行迭代，直至達(dá)到最大迭代次數(shù)或找到滿意的解為止。

作為PSO算法的主要步驟PRNG的重要性一直備受關(guān)注，傳統(tǒng)觀點(diǎn)認(rèn)為應(yīng)在PSO中采用質(zhì)量更好的PRNG，以便促使PSO獲得更好的搜索性能。但通過(guò)一些學(xué)者近年來(lái)的研究后表明，PRNG的質(zhì)量的確能對(duì)PSO的性能產(chǎn)生影響但結(jié)果卻與傳統(tǒng)觀點(diǎn)存在差異［4］－［7］，PRNG 質(zhì)量的高低并不總是左右著PSO的性能;在某些情況下低質(zhì)量PRNG的表現(xiàn)與高質(zhì)量PRNG一樣甚至更好，呈現(xiàn)出不穩(wěn)定性。

二、PRNG對(duì)PSO性能影響的因素

在優(yōu)化算法中所有使用了隨機(jī)值的地方都會(huì)受到PRNG質(zhì)量的影響，但本文經(jīng)研究后發(fā)現(xiàn)對(duì)于PSO算法而言，隨機(jī)值在迭代過(guò)程中并不大量地被使用，相對(duì)而言在PSO初始化的過(guò)程中PRNG對(duì)其影響更為突出。在PSO初始化的過(guò)程中PRNG的質(zhì)量差異將直接影響PSO種群的多樣性。類型充足且豐富的種群是PSO得以進(jìn)行搜索的基礎(chǔ)，多樣性高的種群表現(xiàn)為個(gè)體粒子在解空間中的分布更為均勻，致使算法能在更大的范圍內(nèi)進(jìn)行搜索;若種群類型不足，則導(dǎo)致種群在解空間中分布不均甚至形成團(tuán)簇，這將直接限制粒子對(duì)解空間的搜索，從而導(dǎo)致PSO發(fā)生早熟收斂。圖1表示種群的多樣性對(duì)PSO性能存在顯著影響。

圖1 種群多樣性對(duì)PSO尋優(yōu)性能的影響

1.PRNG對(duì)種群多樣性的影響及其度量方法

在演化計(jì)算中為了衡量算法種群的多樣性，常使用計(jì)算并比較其種群海明距離(hamming distance)［8］的方法。不失一般性，若PSO種群為P，種群大小為N，采用固定長(zhǎng)度為L(zhǎng)的2進(jìn)制對(duì)粒子進(jìn)行編碼。那么粒子空間B={0，1}L，種群P(P?B)為一有限點(diǎn)的集合，分別記 P中的粒子為:xi，x2，…，xn;若 xi(i=1，2，…，L)為 B 中的一個(gè)點(diǎn)，xi=a1，a2，…aL，則 al(l=1，2，…，L)，al∈{0，1} 被稱為編碼基因位。通常將任意兩個(gè)粒子與xj(xi，xj∈B)之間的海明距離h(xi，xj)由下式(2)定義:

其中xil表示粒子xi的第l編碼基因位。由式(1)可知 0≤h(xi，xj)≤L，h(xi，xj)=h(xj，xi)即 h是對(duì)稱的，且只有在xi=xj時(shí)h(xj，xi)=0。若對(duì)采用均勻隨機(jī)初始化的種群P0來(lái)說(shuō)，種群中的粒子之間應(yīng)該是相互獨(dú)立且任意個(gè)體服從分布P{X=x}=1/2L;粒子的任意編碼基因位取值0或1的概率相等(p=q=0.5)且相互獨(dú)立。粒子xi與xj間的海明距離h(xi，xj)服從參數(shù)為L(zhǎng)和P的二項(xiàng)分布，即h(xi，xj) ～B(L，p);期望值 E(h)=Lp=L/2;方差 D(h)=Lpq=L/4。

只衡量2個(gè)獨(dú)立粒子的海明距離并沒(méi)有太多數(shù)學(xué)意義，為了能在各種大小的種群P之間進(jìn)行多樣性度量，這里定義Da(P)為對(duì)種群P中任意粒子的平均海明距離:

Dh(P)為種群P中任意2個(gè)粒子間海明距離的總和。由式(3)可知，0≤Da(P)≤L只有當(dāng)種群為齊次種群(指種群中所有粒子的值完全相等時(shí)，通常意味著PSO算法已經(jīng)停滯或已找到最優(yōu)值)時(shí)Da(P)=0。對(duì)于均勻隨機(jī)初始化的種群P0來(lái)說(shuō)Da(P0)是隨機(jī)的，并且Da(P)會(huì)隨著PSO搜索過(guò)程中種群多樣性的下降而下降，最終種群收斂為齊次種群時(shí)Da(P)=0。

2.PRNG對(duì)粒子周期的影響及其度量方法

在統(tǒng)計(jì)中若種群P中的粒子循環(huán)周期為m，則表現(xiàn)為在經(jīng)過(guò)m個(gè)粒子長(zhǎng)度之后會(huì)產(chǎn)生與之前完全相同的粒子;即這一種群中存在對(duì)任意粒子xi都有xi=xi+m的關(guān)系。在PSO中若經(jīng)PRNG隨機(jī)生成的獨(dú)立粒子產(chǎn)生重復(fù)，這將直接導(dǎo)致種群多樣性的下降，致使PSO算法惡化。通常若PRNG擁有足夠長(zhǎng)的周期T，PSO在初始化種群的過(guò)程是不可能用到超過(guò)PRNG單個(gè)生成周期數(shù)量的隨機(jī)數(shù)的，因此通常PRNG不會(huì)產(chǎn)生循環(huán)。但若采用短周期的PRNG則會(huì)使得PSO在初始化中容易產(chǎn)生循環(huán)，導(dǎo)致種群多樣性直接受到影響。若PRNG的周期長(zhǎng)度為T，用其對(duì)固定長(zhǎng)度 且采用二值編碼的種群的周期的影響如下式(5)所示:

其中m為該P(yáng)RNG對(duì)于固定長(zhǎng)度為L(zhǎng)的種群循環(huán)周期，lcm(T，L)為T和L的最小公倍數(shù)。

三、仿真實(shí)驗(yàn)

1.實(shí)驗(yàn)方法

為了方便對(duì)比，本文采用三種PRNG來(lái)進(jìn)行測(cè)試［1］:第一種是 Mersenne Twister(MT)，其周期長(zhǎng)度為且在高達(dá)623維的空間中分布均勻，是目前學(xué)術(shù)界公認(rèn)的最好的PRNG之一;第二種是普通長(zhǎng)整形的線性同余方法Linear Congruence(LC)，其周期為232－1;第三種同屬于MT算法，但是其周期被人為固定為1000，這里將其稱之為MT1000;該P(yáng)RNG在產(chǎn)生1000個(gè)隨機(jī)值后會(huì)使用固定數(shù)值的種子進(jìn)行重設(shè)，是一種典型的低質(zhì)量的 PRNG，文獻(xiàn)［4］［5］都曾使用其作為對(duì)比之用。測(cè)試函數(shù)采用陷阱函數(shù)Shubert其表達(dá)式如下式(6)所示:

圖2為Shubert函數(shù)在MATLEP中的模擬仿真圖像，該函數(shù)有9個(gè)全局極小值且這9個(gè)全局極值點(diǎn)呈規(guī)律分布;該函數(shù)常用于檢驗(yàn)優(yōu)化算法的種群多樣性。

圖2 Shubert函數(shù)的模擬圖像

具體操作方法為，對(duì)種群中所有粒子分別按200、199、500、503共四種不同長(zhǎng)度來(lái)進(jìn)行二值編碼。并且始終固定粒子種群數(shù)目為;分別固定式(1)中的認(rèn)知系數(shù)為 c0=0.5、c1=2、c2=2;PSO最大迭代次數(shù)為2000。使用前文提到的三種PRNG來(lái)對(duì)四種不同編碼長(zhǎng)度的粒子實(shí)行初始化;再使用不同編碼不同初始化的12種PSO分別對(duì)Shubert函數(shù)進(jìn)行5次優(yōu)化，記錄所有迭代過(guò)程中每代的平均海明距離Da(P)，并取相同代數(shù)的平均值。

2.實(shí)驗(yàn)結(jié)果

傳統(tǒng)觀點(diǎn)認(rèn)為PRNG的循環(huán)將引起PSO性能的降低。但實(shí)驗(yàn)表明，PRNG發(fā)生循環(huán)并不一定會(huì)導(dǎo)致PSO性能的降低，在某些情況下也會(huì)獲得很好的性能。圖3為在四種不同編碼長(zhǎng)度下PSO種群多樣性的對(duì)比。

3.結(jié)果分析

圖3 三種PRNG在不同編碼長(zhǎng)度下的種群多樣性

在觀察對(duì)比MT、LC和MT1000時(shí)可以發(fā)現(xiàn)MT和LC在圖3中所有編碼情況下，兩者表現(xiàn)基本一致，雖然MT和LC在自身周期長(zhǎng)度上差異巨大但是對(duì)PSO種群多樣性的影響上卻微乎其微。但是在通過(guò)圖3中對(duì)MT1000的觀察中卻可以看到兩種截然不同的結(jié)果:第一種如圖 3(a)、3(c)所示，MT1000對(duì)比MT和LC在影響PSO種群多樣性上的差異明顯，通過(guò)前式(5)可知 取值與 與 有關(guān)，當(dāng)時(shí)，這時(shí)MT1000初始化的粒子循環(huán)周期;而當(dāng)時(shí)。很小的粒子循環(huán)周期將導(dǎo)致種群中出現(xiàn)大量的同質(zhì)粒子從而致使Da(PMT1000)的取值下降。第二種情況如圖3(b)、3(d)所示，MT1000對(duì)PSO的種群多樣影響相對(duì)較小，甚至在部分區(qū)域還出現(xiàn)了優(yōu)于高質(zhì)量PRNG的情況。可以看出當(dāng)L=199和L=503時(shí)雖然與L=200和L=500和 數(shù)值差距不大，但是199和503均為素?cái)?shù)，這就使得在這兩種編碼長(zhǎng)度下的mMT1000取值要遠(yuǎn)高于編碼長(zhǎng)度為200和500的情況。

由此可知，短周期PRNG使PSO性能在粒子編碼長(zhǎng)度不同時(shí)呈現(xiàn)出不穩(wěn)定性，其原因在于個(gè)體循環(huán)周期的取值存在差異性，導(dǎo)致種群多樣性呈現(xiàn)不同的變化模式，從而影響PSO性能。m越小，則PSO種群多樣性下降幅度越大，導(dǎo)致PSO性能也將大幅下降;反之，m越大，則PSO種群多樣性下降幅度越小，PSO的性能也將越好。

四、結(jié)論

本文的研究結(jié)果表明，低質(zhì)量的PRNG主要通過(guò)初始化來(lái)影響PSO種群的多樣性從而使得PSO性能表現(xiàn)出不穩(wěn)定。但就本文的實(shí)驗(yàn)結(jié)果而言，表明質(zhì)量稍低甚至質(zhì)量一般的PRNG也能獲得與高質(zhì)量PRNG基本一致的性能，與文獻(xiàn)［9］提出的應(yīng)當(dāng)選用當(dāng)前質(zhì)量最好PRNG的建議有所不同，本文認(rèn)為高質(zhì)量的PRNG算法對(duì)PSO算法所帶來(lái)的收益并不明顯，相反其系統(tǒng)開(kāi)銷卻較大。對(duì)于簡(jiǎn)單的PSO更應(yīng)考慮在可行性和經(jīng)濟(jì)性的前提下適度提高PRNG的質(zhì)量。

［1］Knuth D E.The Art of Computer Programming［M］.USA:Addison－Wesley，1998.

［2］Marsaglia G，Zaman A.A New Class of Random Number Generators［J］.Annals of Applied Probability，1991，1(3):462－480.

［3］Kennedy J，Eberhart R C.Particle Swarm Optimization［C］.Proc IEEE International Conference on Neural Networks.Piscataway，NJ:IEEE Service Center，1995:1942－1948.

［4］Meysenburg M M，Hoelting D，McElvain D，et al.How Random Generator Quality Impacts GA Performance［C］.Proceedings of the Genetic and Evolutionary Computation Conference，2002.San Francisco USA:Morgan Kaufmann Publishers，2002:480 －487.

［5］李東，汪定偉.基于仿真的優(yōu)化方法綜述［J］.控制工程，2008，15(6):672 －677.

［6］江維，沈斌，胡中功.微粒群算法參數(shù)的理論分析［J］.化工自動(dòng)化及儀表，2009，36(4):38 －40.

［7］朱奇光，王洪瑞.IC－PSO算法的收斂性分析及應(yīng)用研究［J］.光電工程，2010，37(4):108 －112.

［8］Mattiussi C，Waibel M，F(xiàn)loreano D.Measures of Diversity for Populations and Distances Between Individuals with Highly Recognizable Genomes［J］.Evolutionary Computation，2004，12(4):495－515.

［9］Cantú －Paz E.On Random Numbers and the Performance of Genetic Algorithms［C］.Proceedings of the Genetic and Evolutionary Computation Conference，2002.San Francisco USA:Morgan Kaufmann Publishers，2002:311 －318.

Abstract:Pseudo－random number on the performance of PSO algorithm is mainly reflected in the diversity of the population.Low－quality pseudo－random number will lead to the performance of PSO instability phenomenon，through the typical pseudo－random number drawn after analysis and comparison of the particle and pseudo－random number code length interaction cycle is the result algorithm for the cause of instability.Experiments also confirmed this result.

Key words:pseudo －random number，particle swarm optimization，species diversity，hamming distance

On the Impact of Pseudo－random Number Quality on Simple Particle Swarm Optimization Performance

TAN Yang

TP301.6

A

1009－5152(2011)01－0048－04

2010－11－26

湖南省自然科學(xué)基金(06JJ50107)。

譚陽(yáng)(1979－ )，男，湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院講師，工程師。