朱成功

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

基于RAGA的投影尋蹤分類模型改進(jìn)與實(shí)例分析

朱成功

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

針對(duì)實(shí)數(shù)編碼加速遺傳算法(RAGA)在求解投影尋蹤分類(PPC)模型陷入局部最優(yōu)的問(wèn)題，通過(guò)引入?yún)^(qū)間擴(kuò)展因子：在變量區(qū)間過(guò)小時(shí)，對(duì)變量區(qū)間進(jìn)行適當(dāng)擴(kuò)展；在擴(kuò)展區(qū)間"越界"時(shí)，即以邊界作為變量的取值。并選取合理的局部密度窗口半徑R，建立了改進(jìn)的RAGA-PPC分類模型，并以文獻(xiàn)中S縣15個(gè)鄉(xiāng)鎮(zhèn)申請(qǐng)糧援項(xiàng)目的投資順序?yàn)槔M(jìn)行驗(yàn)證分析。研究表明，改進(jìn)的RAGA-PPC模型對(duì)樣本分類評(píng)價(jià)，確立指標(biāo)因素的貢獻(xiàn)程度大小具有一定的可行性和廣泛的通用性。

實(shí)數(shù)編碼加速遺傳算法；區(qū)間擴(kuò)展；窗口半徑；投影尋蹤分類

自從金菊良等[1]提出加速遺傳算法，已在干旱環(huán)境監(jiān)測(cè)、自然災(zāi)害、水文地質(zhì)工程地質(zhì)等眾多領(lǐng)域得到了廣泛應(yīng)用[2-4]。相比于標(biāo)準(zhǔn)遺傳算法(SGA)，加速遺傳算法克服了在實(shí)際應(yīng)用中存在早熟收斂、計(jì)算量大和解的精度差等缺點(diǎn)[5]，但目前一些論文并沒(méi)有對(duì)變量區(qū)間進(jìn)行改進(jìn)，如文獻(xiàn)[6]采用了自適應(yīng)的交叉和變異操作，解決了因交叉概率和變異概率不變而導(dǎo)致過(guò)快出現(xiàn)局部收斂的現(xiàn)象，文獻(xiàn)[7]提出了基于個(gè)體修正模型的改進(jìn)加速遺傳算法，根據(jù)各子目標(biāo)函數(shù)值對(duì)應(yīng)因素的重要性程度，運(yùn)用層次分析法確定各因素的權(quán)重，依次采用相應(yīng)的權(quán)重構(gòu)造總目標(biāo)函數(shù)。

投影尋蹤模型(Projection Pursuit Clustering，PPC)是由Friedman和Turkey于1974年提出的，是處理和分析高維數(shù)據(jù)的新興統(tǒng)計(jì)方法，傳統(tǒng)的投影尋蹤技術(shù)存在計(jì)算量大等缺點(diǎn)[8]，因此金菊良等提出用RAGA求解投影尋蹤模型[9]。

本文根據(jù)實(shí)數(shù)編碼的加速遺傳算法(RAGA)的思想，通過(guò)改進(jìn)加速時(shí)優(yōu)化變量的區(qū)間來(lái)擴(kuò)大變量的搜索范圍：在區(qū)間過(guò)小時(shí)，對(duì)加速區(qū)間進(jìn)行適當(dāng)擴(kuò)展；當(dāng)擴(kuò)展后的區(qū)間超過(guò)邊界時(shí)，即以邊界值作為優(yōu)化變量的值。將改進(jìn)的實(shí)數(shù)編碼加速遺傳算法應(yīng)用于RAGA-PPC模型中，結(jié)合文獻(xiàn)[10]中的數(shù)據(jù)及樓文高在文獻(xiàn)[11]中的基本定理和推理，驗(yàn)證了改進(jìn)的RAGA算法，在投影尋蹤分類模型中能夠求得全局最優(yōu)解和最優(yōu)投影方向。

1 改進(jìn)區(qū)間的實(shí)數(shù)編碼加速遺傳算法

實(shí)數(shù)編碼的加速遺傳算法(RAGA)主要包括選擇，交叉，變異和加速等步驟，通過(guò)問(wèn)題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，逐代演化得到優(yōu)秀個(gè)體。并利用優(yōu)秀個(gè)體逐步縮小優(yōu)化變量的初始變化區(qū)間，達(dá)到加速目的。

為一般起見(jiàn)，不妨設(shè)優(yōu)化問(wèn)題為如下最小化問(wèn)題

(1)

其中，x(j)為第j個(gè)優(yōu)化變量；[a(j),b(j)]為x(j)的變化區(qū)間；p為優(yōu)化變量的個(gè)數(shù)；f為目標(biāo)函數(shù)。

(1)初始化。設(shè)群體規(guī)模為N，生成N組取值為[0,1]上均勻分布的隨機(jī)數(shù)，每組有p個(gè)，即{u(i,j)|(i=1-N,j=1～p)}，然后根據(jù)線性變換公式x(i,j)=a(j)+u(i,j)×(b(j)-a(j))把u(i,j)變換成[a(j),b(j)]上的優(yōu)化變量x(i,j)；

(2)選擇。將初始化生成的N組優(yōu)化變量代入目標(biāo)函數(shù)f，得到目標(biāo)函數(shù)值(即適應(yīng)度值)f(i)(i=1～N)，按目標(biāo)函數(shù)值的大小升序排列，排序后前S個(gè)個(gè)體為優(yōu)秀個(gè)體，直接進(jìn)入下一代，剩下(N-S)個(gè)個(gè)體通過(guò)輪盤賭的方式選擇，得到第一代N個(gè)個(gè)體x1；

(3)交叉。第二代子代群體由交叉得到，通過(guò)隨機(jī)挑選父代群體中的兩個(gè)個(gè)體x(x1,j)，x(i2,j)，通過(guò)如下線性組合得到兩個(gè)新的個(gè)體x2(k1,j)和x2(k2,j)。

(2)

式(2)中，u為隨機(jī)數(shù)，這樣共產(chǎn)生N個(gè)子代個(gè)體x2；

(4)變異。第三代子代群體由變異得到，通過(guò)求目標(biāo)函數(shù)值得到個(gè)體x(i,:)(i=1～N)被選擇的概率ps(i)，由于目標(biāo)函數(shù)值越小，其選擇的概率越小，其變異的概率則越大，因此x(i,:)變異的概率pm(i)=1-ps(i)，從而得到第三代 個(gè)個(gè)體 。即

(3)

式(3)中，u(j)(j=1～p)，um均為隨機(jī)數(shù)；

(5)迭代。由前面選擇，交叉和變異得到的三代群體x1，x2，x3共3N個(gè)個(gè)體，計(jì)算其適應(yīng)度值，并按照升序排列，取出適應(yīng)度值靠前的前N個(gè)個(gè)體作為新的的父代群體，算法轉(zhuǎn)入步驟3；

(6)加速。在進(jìn)行若干次的選擇，交叉，變異操作后，對(duì)得到的N個(gè)個(gè)體x(i,j)=(i=1～N,j=1～p)作如下改進(jìn)：

1)對(duì)于N個(gè)個(gè)體的任意一列x(:,j)(j=1～p)，其最大值maxx為max(x(:,j))，其最小值minx為min(x(:,j))，則進(jìn)入下一次迭代的父代xnew由以下公式產(chǎn)生

xnew(i,j)=minx+u×(maxx-minx)

(4)

式(4)中xnew(i,j)(i=1～N,j=1～p)，u為[0，1]的隨機(jī)數(shù)；

2)若在若干次迭代后出現(xiàn) 個(gè)個(gè)體的某一列陷入局部最優(yōu)的情況，即某列變量的最大值和最小值幾乎相等，即(maxx-minx<ε)，ε為任意一個(gè)很小的常數(shù)，本文取0.000 1，則需對(duì)該列區(qū)間進(jìn)行適當(dāng)擴(kuò)展，如下所示

(5)

式(5)中x1為>1的常數(shù)，本文取1.1，c2為<1的常數(shù)，本文取0.9；

3)若步驟2處理數(shù)據(jù)后出現(xiàn)maxx>b(j)或minx

maxx=b(j)

(6)

或

minx=a(j)

(7)

此時(shí)再將區(qū)間擴(kuò)展后的最大值和最小值代入上式中生成下一次迭代的父代xNEW，然后算法轉(zhuǎn)入步驟3，進(jìn)行下一輪的演化，如此循環(huán)，直至算法達(dá)到預(yù)定的迭代次數(shù)或目標(biāo)函數(shù)值滿足條件，算法結(jié)束，并將當(dāng)前群體中的最優(yōu)個(gè)體作為算法的最優(yōu)化結(jié)果。

2 投影尋蹤分類模型

投影尋蹤模型是一種適用于非線性，處理高維數(shù)據(jù)的尋優(yōu)方法，其通過(guò)采用某種目標(biāo)函數(shù)使所有樣本點(diǎn)形成若干個(gè)類，并要求類與類之間盡可能分散，而同一類內(nèi)的樣本點(diǎn)則盡可能密集。具體實(shí)現(xiàn)步驟主要包括評(píng)價(jià)指標(biāo)歸一化處理，構(gòu)建投影指標(biāo)函數(shù)，優(yōu)化投影指標(biāo)函數(shù)以及聚類等[9]。設(shè)給定數(shù)據(jù)的第i個(gè)樣本的第j個(gè)指標(biāo)為x(i,j)(i=1～n,j=1～p)，其中n為樣本個(gè)數(shù)，p為指標(biāo)個(gè)數(shù)。

2.1 數(shù)據(jù)預(yù)處理

為了消除數(shù)據(jù)樣本指標(biāo)量綱不同的影響，需要對(duì)數(shù)據(jù)進(jìn)行歸一化處理。

對(duì)于越大越優(yōu)的指標(biāo)

(8)

對(duì)于越小越優(yōu)的指標(biāo)

(9)

其中，xmax(:,j)和xmin(:,j)分別為第j個(gè)指標(biāo)的最大值和最小值；x*(i,j)為樣本指標(biāo)歸一化后的值。

2.2 構(gòu)建投影指標(biāo)函數(shù)

設(shè)a(j)為投影方向向量，第i個(gè)樣本在該投影方向上的投影值z(mì)(i)為

(10)

投影指標(biāo)函數(shù)為

Q(a)=Sz·Dz

(11)

(12)

(13)

ri,k=|z(i)-z(k)|

(14)

式中，Sz為樣本投影值z(mì)(i)的標(biāo)準(zhǔn)差；Dz為局部密度值；E(z)為樣本投影值z(mì)(i)的平均值；R為局部密度的窗口半徑；ri,k為樣本i樣本k投影值之間的距離。根據(jù)樓文高等[11]的研究結(jié)果，密度窗口半徑R合理取值范圍為max(ri,k)/5≤R≤max(ri,k)/3，即將樣本分為3～5類，本文取R=max(ri,k)/5。

2.3 優(yōu)化投影指標(biāo)函數(shù)

當(dāng)構(gòu)造的投影指標(biāo)函數(shù)Q(a)達(dá)到極大值時(shí)即可找到最優(yōu)投影方向a。即

Q(a)=max(Sz·Dz)

(15)

約束條件為

(16)

2.4 聚類及排序

將由步驟3求得的最優(yōu)投影方向a代入式(10)各樣本點(diǎn)的投影值z(mì)(i)。將z(i)與z(k)進(jìn)行比較,二者越接近，表示樣本i樣本k傾向于分為同一類。若按z(i)值從大到小排序，則可將樣本從優(yōu)到劣進(jìn)行排序。若對(duì)求得的最優(yōu)投影方向a的各個(gè)分量進(jìn)行從小到大排序，則可判別各個(gè)指標(biāo)對(duì)樣本的影響程度，分量值越大，影響程度越大。

3 改進(jìn)的RAGA-PPC建模實(shí)例分析

應(yīng)用改進(jìn)后的RAGA-PPC模型，計(jì)算文獻(xiàn)[10]中S縣15個(gè)鄉(xiāng)鎮(zhèn) 申請(qǐng)糧援項(xiàng)目的投資順序以及判斷各個(gè)指標(biāo)因素的貢獻(xiàn)程度大小。

根據(jù)原文中的要求，選取經(jīng)濟(jì)因素、社會(huì)因素和自然因素3方面的12個(gè)因素作為評(píng)價(jià)指標(biāo)，在12項(xiàng)指標(biāo)因子中：缺水人口比例x1，庫(kù)區(qū)移民率x2，文盲率x7，病床率x8，山坡耕地比例x9，大齡青年比例x10及瓜干比例x12這幾項(xiàng)指標(biāo)因子屬于越大越優(yōu)指標(biāo)，因此原始數(shù)據(jù)越大，對(duì)該項(xiàng)目的需求度越大；而人均收入x3，人均口糧x4，統(tǒng)銷糧x5，人均耕地x6，灌溉面積比例x11這幾項(xiàng)指標(biāo)屬于越小越優(yōu)指標(biāo)，原始數(shù)據(jù)越大，對(duì)該項(xiàng)目的需求度越小。具體數(shù)據(jù)見(jiàn)文獻(xiàn)[10]。

選定父代初始種群規(guī)模N=400，優(yōu)秀個(gè)體數(shù)目為50個(gè)，迭代20次進(jìn)行一次加速，利用Matlab編程計(jì)算可得到最優(yōu)投影方向：

a=(0.309 5,-0.085 8,0.450 7,-0.045 0,0.079 5,-0.266 6,0.281 4,-0.441 0,-0.056 0,0.385 5,0.193 3,0.389 2)

各個(gè)樣本的投影值

z=(-0.690 9,0.931 5,0.985 3,1.701 7,0.831 2,0.946 9,0.168 4,0.786 6,0.941 7,0.931 1,0.786 1,0.831 6,0.526 7,0.786 7,0.829 4)

最優(yōu)投影指標(biāo)函數(shù)值Q(a)=27.624 3，局部密度窗口半徑R=0.478 5。根據(jù)求解出的投影值排序，可得如表1所示。

表1 兩種算法對(duì)比研究

結(jié)果分析：

(1)由表1可知，鄉(xiāng)鎮(zhèn)S4對(duì)項(xiàng)目的需求度最大，這與原論文中加速遺傳投影尋模型的評(píng)價(jià)結(jié)果一致，從決策上分析，這說(shuō)明改進(jìn)的RAGA算法具有一定得適用性；

(2)但對(duì)于其他鄉(xiāng)鎮(zhèn)，改進(jìn)的方法與原論文有一定的差異。如原文中鄉(xiāng)鎮(zhèn)S14對(duì)該項(xiàng)目的需求度最小，而改進(jìn)的算法求得鄉(xiāng)鎮(zhèn)S1的需求度最??；從整體上來(lái)看，原文中需求度最小的3個(gè)鄉(xiāng)鎮(zhèn)依次為S14，S1和S13，而改進(jìn)的算法求得的需求度最小的3個(gè)鄉(xiāng)鎮(zhèn)依次為S1，S7和S13，具有一定的相似性;

(3)為比較兩種算法的優(yōu)劣，計(jì)算這兩種算法所得的投影指標(biāo)函數(shù)值。根據(jù)原文給出的最優(yōu)投影方向

a=(0.327,0.167 8,0.291 9,0.324 3,0.093 9,0.404 3,0.177 4,0.128,0.183 9,0.298 5,0.349 5,0.457 5)

以及式(10)～式(14)可以求解出Q(a)=0.538 6，小于本文求解的結(jié)果(Q(a))=27.624 3，說(shuō)明原論文中并未求得真正的最優(yōu)解。

由于本文中R=max(ri,k)/5，即將樣本分為五類。根據(jù)計(jì)算的投影值，值為1.701 7的分為一類，值為0.985 3,0.946 9和0.941 7的分為一類，值為0.831 6,0.831 5,0.831 2,0.831 1,0.829 4,0.786 7，0.786 6,0.786 1的分為一類，值為0.526 7的分為一類，值為0.168 4,-0.690 9的分為一類。即S4為一類，S3，S6，S9為一類，S12，S2，S5，S10，S15，S14，S8，S11為一類，S13為一類，S7，S1為一類，總共5類，且類與類之間投影值差異明顯，而類內(nèi)投影值相對(duì)集中，說(shuō)明將樣本分為5類是合理的。

為進(jìn)一步驗(yàn)證上述結(jié)論的可靠性，正確性。根據(jù)文獻(xiàn)[11]中的定理1同一指標(biāo)的數(shù)據(jù)采用式(8)和式(9)進(jìn)行歸一化預(yù)處理，其權(quán)重必定互為相反數(shù)以及相應(yīng)的結(jié)論：通過(guò)改變某些指標(biāo)的歸一化方式，從權(quán)重是否是互為相反數(shù)，便可判定最優(yōu)化過(guò)程是否求得了真正的全局最優(yōu)解?，F(xiàn)做如下試驗(yàn)，采用改進(jìn)的RAGA算法和式(8)及式(9)求得的最優(yōu)投影向量為a，改變歸一化的方式，令全部指標(biāo)均為越大越優(yōu)指標(biāo)，只用式(8)再次求得的最優(yōu)投影向量為a*，令全部指標(biāo)為越小越優(yōu)指標(biāo)，只用式(9)求得的最優(yōu)投影向量為a**。具體數(shù)據(jù)如表2所示。

表2 3種不同歸一化方式下的最優(yōu)投影向量對(duì)比

結(jié)果分析：

(1)由表2可知，比較最優(yōu)投影向量a和a*，a為采用越大越優(yōu)和越小越優(yōu)兩種歸一化方式得到的投影向量，而a*為全部采用越大越優(yōu)歸一化方式得到的投影向量，兩者相比，除x3，x4，x5，x6，x11指標(biāo)的的投影分量互為相反數(shù)外，其余皆近似相等。同理，a與a**相比，a**為全部指標(biāo)采用越小越優(yōu)歸一化方式得到的投影向量，除x3，x4，x5，x6，x11指標(biāo)的的投影分量近似相等外，其余皆為相反數(shù)，這說(shuō)明改變歸一化方式后改進(jìn)的RAGA算法求得的權(quán)重變?yōu)榱讼喾磾?shù);

(2)再根據(jù)3種歸一化方式求得的最優(yōu)投影值可知，3種方式均求得了近似相等的投影值，這符合定理一的結(jié)論: 改變指標(biāo)歸一化方式前后，其權(quán)重互為相反數(shù)，投影函數(shù)值保持不變;

(3)綜合改進(jìn)后的RAGA算法求得了更小的最優(yōu)投影值以及符合了PPC模型的定理及推論，可認(rèn)為改進(jìn)的RAGA算法在投影尋蹤模型中的應(yīng)用是有效、正確的;

(4)根據(jù)最優(yōu)投影方向，可進(jìn)一步判斷各指標(biāo)因素對(duì)各個(gè)鄉(xiāng)鎮(zhèn)申請(qǐng)糧援項(xiàng)目的貢獻(xiàn)大小。最優(yōu)投影方向各分量的大小實(shí)際上反映了各指標(biāo)對(duì)申請(qǐng)糧援項(xiàng)目的影響程度，值越大則對(duì)應(yīng)的指標(biāo)對(duì)結(jié)果的影響程度就越大。最優(yōu)投影方向向量a表明各個(gè)指標(biāo)對(duì)申請(qǐng)糧援項(xiàng)目的影響程度大小依次為人均收入x3，瓜干比例(農(nóng)作物曬干后與含有水分時(shí)的質(zhì)量比)x12，大齡青年比例x10，缺水人口比例x1，文盲率x7，灌溉面積比例x11，統(tǒng)銷糧x5，人均口糧x4，山坡耕地比例x9，庫(kù)區(qū)移民率x2，人均耕地x6，病床率x8。

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

(1)在RAGA算法加速過(guò)程中對(duì)不斷壓縮的優(yōu)化變量區(qū)間進(jìn)行適當(dāng)?shù)財(cái)U(kuò)展：在區(qū)間小于某個(gè)很小的常數(shù)ε(本文取0.000 1)時(shí)，對(duì)區(qū)間的上界乘以常數(shù)c1(c1>1，本文取1.1)區(qū)間的下界乘以常數(shù)c2(c2<1,本文取0.9)，可以擴(kuò)大優(yōu)化變量的搜索區(qū)間，防止變量陷入局部最優(yōu)。該常數(shù)是按照經(jīng)驗(yàn)選取，其取值并不唯一，當(dāng)出現(xiàn)越界的情況時(shí)即按照式(6)和式(7)處理;

(2)將改進(jìn)后的RAGA算法應(yīng)用于PPC模型，選取合理的局部密度的窗口半徑R，將樣本分為3～5類。研究結(jié)果表明，這種改進(jìn)方案是合理的，并由已知定理證明，改進(jìn)算法能夠求得當(dāng)前加速次數(shù)下的最優(yōu)解，這能使應(yīng)用PPC模型的聚類或優(yōu)序排列的結(jié)果更加可靠，也為生產(chǎn)實(shí)踐中判斷各個(gè)指標(biāo)因素的影響程度大小提供了參考。

[1] 金菊良,楊曉華,張國(guó)桃,等.非線性環(huán)境模型優(yōu)化的一種數(shù)值方法[J].環(huán)境工程學(xué)報(bào),1997 (S1): 108-112.

[2] 楊曉華,張國(guó)桃,金菊良.灰色系統(tǒng)模型GM(1, 1)的參數(shù)估計(jì)方法[J].干旱環(huán)境監(jiān)測(cè),1998, 12(2):76-80.

[3] 楊曉華,金菊良,張國(guó)桃.加速遺傳算法及其在暴雨強(qiáng)度公式參數(shù)優(yōu)化中的應(yīng)用[J].自然災(zāi)害學(xué)報(bào),1998,7(3):71-76.

[4] 金菊良,丁晶,魏一鳴.加速遺傳算法在地下水位動(dòng)態(tài)分析中的應(yīng)用[J].水文地質(zhì)工程地質(zhì),1999,26(5):4-7.

[5] Mirjalili S. The ant lion optimizer[J].Advances in Engineering Software,2015,83(3):80-98.

[6] 周成成.大型活動(dòng)突發(fā)事件下交通疏散效率評(píng)價(jià)研究[D].成都:西南交通大學(xué),2014.

[7] 張宇亮,張禮兵,周玉良,等.基于改進(jìn)加速遺傳算法的作物灌水率圖修正研究[J].灌溉排水學(xué)報(bào),2015,34(11):80-83.

[8] 吳承禎,洪偉,洪滔.基于改進(jìn)的投影尋蹤的森林生態(tài)系統(tǒng)生態(tài)價(jià)位分級(jí)模型[J].應(yīng)用生態(tài)學(xué)報(bào),2006,17(3):357-361.

[9] 付強(qiáng),金菊良,梁川.基于實(shí)碼加速遺傳算法的投影尋蹤分類模型在水稻灌溉制度優(yōu)化中的應(yīng)用[J].水利學(xué)報(bào),2002(10):39-45.

[10] 張科舉,緱慧娟.加速遺傳投影尋蹤模型在工程項(xiàng)目決策中的應(yīng)用研究[J].土木工程與管理學(xué)報(bào),2015,32(1):93-96.

[11] 樓文高,喬龍.投影尋蹤分類建模理論的新探索與實(shí)證研究[J].數(shù)理統(tǒng)計(jì)與管理,2015, 34(1):47-58.

Based on Projection Pursuit Classification Model Improvement and Analysis of Examples RAGA

ZHU Chenggong

(School of Optical-Electrical and Computer Engineering,University of Shanghai for Science and Technology，Shanghai 200093, China)

Aiming at the problem that real-coded accelerating genetic algorithm (RAGA) could not solve global optimal solution of PPC Model, this paper proposes an improvement: when variableinterval is too small, then extends variable interval by an appropriate constant; when the extension crosses the border, set the boundary as the variable’s value. Combining with properRvalue, the improved RAGA-PPC model is established, and using it in food aid project investment order of S county’s 15 towns, more reasonable sequences and each factor’s influence on the investment order are obtained. The results show that the improved RAGA-PPC model has strong applicability and generality of sample classification and evaluation as well as estimating each factor’s contribution.

real-coded accelerating genetic algorithm;interval extension; window radius;projection pursuit clustering

2016- 03- 22

朱成功(1991-)，男，碩士研究生。研究方向：投影尋蹤。

10.16180/j.cnki.issn1007-7820.2017.01.030

TP391

A

1007-7820(2017)01-107-05