ga-pso混合規(guī)劃算法研究

ga-pso混合規(guī)劃算法研究

遺傳計(jì)劃（又稱遺傳方案，簡稱ep）可以通過沒有完整的系統(tǒng)結(jié)構(gòu)信息來集成系統(tǒng)結(jié)構(gòu)預(yù)測和參數(shù)估計(jì)，這在預(yù)測、分類和系統(tǒng)建模等領(lǐng)域產(chǎn)生了廣泛應(yīng)用。該領(lǐng)域已引起越來越多的相關(guān)學(xué)者們的興趣。GP來源于遺傳算法(GA),但它采用了樹型結(jié)構(gòu)來描述層次問題,其解的描述長度不定,而且結(jié)構(gòu)復(fù)雜。如果能夠?qū)P所描述的層次型問題轉(zhuǎn)換為具有固定長度的線形結(jié)構(gòu)的解,就可以利用許多成熟的GA改進(jìn)算法對其進(jìn)行優(yōu)化。粒子群優(yōu)化算法(Particleswarmoptimizationalgorithms,簡稱PSO)最早是由Kennedy和Eberhart于1995年提出的,是受到人工生命研究啟發(fā)而形成的一個(gè)算法,其基本概念源于對鳥群捕食行為的研究。由于粒子群優(yōu)化算法對解的“創(chuàng)新”加入了局部以及全局最優(yōu)的啟發(fā)式信息,較一般的遺傳算法,PSO算法具有收斂速度快的特征,而且需要用戶確定的經(jīng)驗(yàn)性參數(shù)少,使用比較方便,是目前解決優(yōu)化問題的一個(gè)研究熱點(diǎn)。由于PSO需要利用全局以及局部最優(yōu)位置信息更新當(dāng)前粒子的位置,解被描述為D維空間中的一個(gè)“點(diǎn)”,PSO同樣需要固定長度線形結(jié)構(gòu)解的描述,因此不能夠直接利用PSO解決GP所描述的規(guī)劃問題。本文首先對規(guī)劃(Programming)問題的描述進(jìn)行了改進(jìn),利用一個(gè)固定長度線性表來描述,從而使其轉(zhuǎn)變?yōu)橐粋€(gè)一般的GA算法,即GA規(guī)劃算法。接著,在GA的框架之內(nèi),通過定義運(yùn)算符而加入了PSO的優(yōu)化過程,得到GA-PSO混合規(guī)劃算法。將GA-PSO混合規(guī)劃算法應(yīng)用于城市客運(yùn)量預(yù)測的實(shí)證研究,結(jié)果表明該算法優(yōu)于一般的GP算法以及單純的GA規(guī)劃算法。1基于層次型的轉(zhuǎn)換與GP相同,GA-PSO混合規(guī)劃算法中,描述問題的表達(dá)式中主要由函數(shù)和終止符組成,其意義完全等同于GP中的函數(shù)與終止符。在函數(shù)集F中引入函數(shù)LT,RT。其中LT表示取其左子樹的運(yùn)算符,RT表示取其右子樹的運(yùn)算符,則函數(shù)集F={LT,RT,f1,f2,…,fn};終止符集T不變。通過改造函數(shù)集F,可以將GP中所有層次型問題,通過一個(gè)完全二叉樹來描述。圖1完全二叉樹描述出式(1),其中#表示被忽略的終止符或者函數(shù)。y=a*ln(x1)+b*exp(x1*x2)。(1)用完全二叉樹表示一個(gè)表達(dá)式,葉子結(jié)點(diǎn)在終止符集中取得,而其他結(jié)點(diǎn)可以在函數(shù)集中取得。設(shè)表達(dá)式樹的深度為d,可以采用2d-1個(gè)結(jié)點(diǎn)的靜態(tài)表存儲這個(gè)深度為d的二叉樹,用前序遍歷,得靜態(tài)表所示的二叉樹。由靜態(tài)表的第1個(gè)單元起保持了一個(gè)順序表,從而得到了一個(gè)線形結(jié)構(gòu)的層次型問題的描述。令D=2d-1,則深度為d的二叉樹所表示的所有表達(dá)式都可用一個(gè)D維向量來表示,樹的結(jié)構(gòu)由對表達(dá)式樹的遍歷順序決定,按照前序遍歷。圖1可以表示為表1中的串S。經(jīng)過上述轉(zhuǎn)換,將層次型的問題轉(zhuǎn)換為一個(gè)普通遺傳算法問題。對于遺傳算法來說,每一個(gè)解向量都可以表示成一個(gè)染色體,而基因的類型與基因所處的位置有關(guān),根據(jù)位置就可以確定基因是屬于函數(shù)集還是屬于運(yùn)算符集,及確定其在表達(dá)式二叉樹中的位置。2基于標(biāo)準(zhǔn)的ga的規(guī)劃問題描述通過線性結(jié)構(gòu)靜態(tài)表對層次型規(guī)劃問題的描述,利用標(biāo)準(zhǔn)的GA算法可解決此類規(guī)劃問題。以下從解的初始化、適應(yīng)度的計(jì)算以及遺傳操作對GA規(guī)劃算法進(jìn)行說明。1非葉節(jié)點(diǎn)索引解的初始化非常簡單。設(shè)函數(shù)集中有n個(gè)函數(shù),終止符集中有m個(gè)終止符,取[0,n-1]區(qū)間上的一個(gè)隨機(jī)數(shù)來表示非葉子節(jié)點(diǎn)對應(yīng)的函數(shù)索引;取[0,m-1]區(qū)間上的一個(gè)隨機(jī)數(shù)表示葉子節(jié)點(diǎn)上對應(yīng)的終止符索引。2原始適應(yīng)度計(jì)算方法設(shè)個(gè)體所描述的串為S,對應(yīng)的表達(dá)式二叉樹所描述的表示式為f,根據(jù)樣本數(shù)據(jù),可以得到表達(dá)式f的值y*;設(shè)共有n組樣本;通過式(3),得串S的原始適應(yīng)度。fit(y)=n∑t=1(y*i-yi)2fit(y)=∑t=1n(y?i?yi)2。(2)其中:y為觀測值;y*為表達(dá)式f的預(yù)測值,計(jì)算方法如式(3):y*=f(x1,x2)。(3)3d個(gè)基因的更新及交叉選擇操作:可以采用多種選擇算法,這里推薦使用k選n錦標(biāo)賽式的選擇法,如3選2,3選1等。變異操作:在染色體上隨機(jī)選擇一個(gè)基因,然后按照初始解的生成方式隨機(jī)變異,設(shè)染色體由D個(gè)基因構(gòu)成,在第2位發(fā)生變異,即對第2位的值隨機(jī)更新,更新規(guī)則按照初始解的生成方式進(jìn)行。交叉操作:隨機(jī)取得交叉點(diǎn)p與交叉長度L;交叉的長度L不超過1/2個(gè)染色體長度,交叉的過程如圖2所示。設(shè)交叉點(diǎn)為6,交叉長度為4,則由|p-L|=|6-2|=2開始交叉,長度為4,交叉的過程如圖3所示。3ga-pso混合規(guī)劃算法PSO算法與一般的GA算法所不同的是:將個(gè)體的更新轉(zhuǎn)換為“粒子”在解空間上位置的移動,而移動的方向是受全局最優(yōu)粒子的位置與個(gè)體所找到的最優(yōu)位置所決定的;對解的更新加入了全局與局部最優(yōu)的信息,位置的移動更有目的性,算法具有較高的收斂速度。關(guān)于PSO算法對粒子位置的更新,是按照式(4)進(jìn)行的。{Vi=w*Vi+c*1r*1(Xip-Xi)+c*2r*2(Xg-Xi)?Xi=Xi+a*Vi。(4)其中:Vi表示當(dāng)前粒子i的速度;Xi表示當(dāng)前粒子的位置;Xip表示粒子i所搜索到的局部最優(yōu)粒子的位置;Xg表示全局最優(yōu)粒子的位置;c1,r1,c2,r2是隨機(jī)數(shù);w為慣性因子;a為速度控制約束因子。解向量的運(yùn)算符定義是GA-PSO混合規(guī)劃的關(guān)鍵。對離散量,設(shè)函數(shù)集由m個(gè)元素構(gòu)成,終止集由n個(gè)元素構(gòu)成,vj是D維解向量V的第j個(gè)分量,構(gòu)造向量與向量⊕以及常數(shù)與向量ue067運(yùn)算符。令ki={m,當(dāng)vi屬于函數(shù)集時(shí)?n,當(dāng)vi屬于終止集時(shí)。(5){V1⊕V2=(|v10+v20|%k0|v11+v12|%k1???|v1D-1+v2D-1|%kD-1)?c?V=(|c*v0|%v0|%k0|c*v1|%k1,?,|c*vD-1|%kD-1)。(6)其中:+,*是數(shù)學(xué)運(yùn)算符,%是取余運(yùn)算符,c是常數(shù),則構(gòu)造出⊕和ue067如式(6)。{Vi=w?Vi⊕c1*r1?(Xip⊕-Xi)⊕c2*r2?(Xg⊕-Xi)?Xi=Xi+a?Vi。(7)對連續(xù)量,⊕與ue067等同于數(shù)學(xué)運(yùn)算符+,*。式(4)變?yōu)槭?7)。試驗(yàn)顯示:單純使用PSO算法效果并不理想,將GA與PSO算法進(jìn)行結(jié)合,從而建立GA-PSO混合規(guī)劃算法(見圖4)。GA-PSO混合規(guī)劃算法與GA規(guī)劃算法存在兩點(diǎn)不同:1)在計(jì)算適應(yīng)度時(shí),需要監(jiān)測全局最優(yōu)個(gè)體的位置并記錄;監(jiān)測當(dāng)前個(gè)體所搜尋的最優(yōu)位置并記錄。2)在GA遺傳算子執(zhí)行完畢后,再執(zhí)行PSO優(yōu)化過程,一般情況下可以采用2選1或者3選1錦標(biāo)賽選擇算法。相對于單純的GA規(guī)劃算法,GA-PSO混合規(guī)劃算法除種群規(guī)模、選擇強(qiáng)度、交叉變異的概率以外,還需要確定PSO優(yōu)化的概率。在PSO優(yōu)化的過程中,需要確定慣性因子w以及方向約束因子a。4統(tǒng)計(jì)動態(tài)分析交通量的預(yù)測,對解決城市地理系統(tǒng)中城市交通問題至關(guān)重要,是城市交通規(guī)劃、管理的重要依據(jù)。最常采用方法是回歸分析法、指數(shù)平滑法、灰色預(yù)測模型、彈性系數(shù)法、時(shí)間序列分析法、神經(jīng)網(wǎng)絡(luò)、遺傳算法等等。但是,在實(shí)際預(yù)測中,問題往往非常復(fù)雜,在許多情況下需要綜合多種模型預(yù)測的結(jié)果,如常用的交通物理量向量空間非線性預(yù)測理論,是對現(xiàn)有的多種預(yù)測模型優(yōu)化選擇綜合應(yīng)用的方法。本文提出的GA-PSO混合規(guī)劃算法,具有很強(qiáng)的非線形數(shù)據(jù)擬合能力,能夠應(yīng)用于數(shù)值預(yù)測模型的構(gòu)建,它不需要任何經(jīng)驗(yàn)公式,能夠建立更為直觀的預(yù)測模型。利用2003年西安市城市交通預(yù)測及規(guī)劃提供的西安市歷年GDP與城市客運(yùn)量的統(tǒng)計(jì)數(shù)據(jù),分別應(yīng)用GP算法、GA規(guī)劃算法、GA-PSO混合規(guī)劃算法建立GDP與城市客運(yùn)量的關(guān)聯(lián)預(yù)測模型,并在GDP預(yù)測數(shù)據(jù)的基礎(chǔ)上對2007年2015年、2020年的城市客運(yùn)量進(jìn)行預(yù)測。表2列出了西安歷年GDP與客運(yùn)量之間的統(tǒng)計(jì)數(shù)據(jù)。圖5列出了GA-PSO混合規(guī)劃算法、GA算法、GP算法3種算法的收斂性能比較曲線;其中Y軸表示運(yùn)行10次的平均適應(yīng)度,X軸為時(shí)間周期,單位為s。經(jīng)過整理,預(yù)測模型為公式(8),精度最高模型求得的方差為61.09,相關(guān)系數(shù)R2=0.985880。式(8)列出了利用GA-PSO混合規(guī)劃算法求得的精度最高的預(yù)測模型;由此預(yù)測得2007,2015,2020年的客運(yùn)量分別為:11640,16880,19654,與表2中列出的西安市城市交通預(yù)測與規(guī)劃中綜合預(yù)測結(jié)果非常接近。Q=8990+3.784*GDΡ+5560.2GDΡ-736.81.138+19.3GDΡ+20.3GDΡ-998.4。(8)模型分析:從GA-PSO混合規(guī)劃算法、GA規(guī)劃算法以及一般的GP算法的收斂性能比較上看,GA-PSO混合規(guī)劃算法優(yōu)于GA規(guī)劃算法,而GA規(guī)劃算法優(yōu)于GP算法。結(jié)果顯示:在模型運(yùn)行的初期,GA規(guī)劃算法以及GA-PSO混合規(guī)劃算法具有非常優(yōu)異的收斂性能。GP算法一般要經(jīng)過較長時(shí)間的運(yùn)行,從試驗(yàn)的周期看GA-PSO混合規(guī)劃算法和GA規(guī)劃算法,其收斂速度以及全局優(yōu)化性能上都顯著優(yōu)于一般的GP算法。GA-PSO混合規(guī)劃算法較GA規(guī)劃算法,在算法執(zhí)行的過程中,不僅處理了模型的結(jié)構(gòu),更重要的是通過PSO算法對表達(dá)為連續(xù)量的參數(shù)進(jìn)行了優(yōu)化,而在GA規(guī)劃算法以及GP算法中,參數(shù)的更新僅僅通過隨機(jī)變異獲得?？傊?PSO對結(jié)構(gòu)的優(yōu)化不及對參數(shù)優(yōu)化效果明顯?？梢栽O(shè)想。如果當(dāng)前最優(yōu)個(gè)體所代表的模型結(jié)構(gòu)較優(yōu),則參數(shù)優(yōu)化能夠起到較大的效果。如果當(dāng)前較優(yōu)個(gè)體所代表的模型結(jié)構(gòu)較差,則PSO參數(shù)優(yōu)化的效果就不明顯。因此,即便是GA-PSO混合規(guī)劃模型,PSO的優(yōu)化率對模型的最終效果也有一定的影響,是一個(gè)經(jīng)驗(yàn)值。5ga-pso混合規(guī)劃算法利用GA解決規(guī)劃問題的算法,已經(jīng)廣泛地應(yīng)用于系統(tǒng)預(yù)測之中。本文通過對