朱成功

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

基于RAGA的投影尋蹤分類模型改進與實例分析

朱成功

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

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

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

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

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

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

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

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

為一般起見，不妨設優(yōu)化問題為如下最小化問題

(1)

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

(1)初始化。設群體規(guī)模為N，生成N組取值為[0,1]上均勻分布的隨機數(shù)，每組有p個，即{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)化變量代入目標函數(shù)f，得到目標函數(shù)值(即適應度值)f(i)(i=1～N)，按目標函數(shù)值的大小升序排列，排序后前S個個體為優(yōu)秀個體，直接進入下一代，剩下(N-S)個個體通過輪盤賭的方式選擇，得到第一代N個個體x1；

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

(2)

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

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

(3)

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

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

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

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

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

(4)

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

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

(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)

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

2 投影尋蹤分類模型

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

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

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

對于越大越優(yōu)的指標

(8)

對于越小越優(yōu)的指標

(9)

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

2.2 構建投影指標函數(shù)

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

(10)

投影指標函數(shù)為

Q(a)=Sz·Dz

(11)

(12)

(13)

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

(14)

式中，Sz為樣本投影值z(i)的標準差；Dz為局部密度值；E(z)為樣本投影值z(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)化投影指標函數(shù)

當構造的投影指標函數(shù)Q(a)達到極大值時即可找到最優(yōu)投影方向a。即

Q(a)=max(Sz·Dz)

(15)

約束條件為

(16)

2.4 聚類及排序

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

3 改進的RAGA-PPC建模實例分析

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

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

選定父代初始種群規(guī)模N=400，優(yōu)秀個體數(shù)目為50個，迭代20次進行一次加速，利用Matlab編程計算可得到最優(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)

各個樣本的投影值

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)投影指標函數(shù)值Q(a)=27.624 3，局部密度窗口半徑R=0.478 5。根據(jù)求解出的投影值排序，可得如表1所示。

表1 兩種算法對比研究

結(jié)果分析：

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

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

(3)為比較兩種算法的優(yōu)劣，計算這兩種算法所得的投影指標函數(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，說明原論文中并未求得真正的最優(yōu)解。

由于本文中R=max(ri,k)/5，即將樣本分為五類。根據(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)投影值相對集中，說明將樣本分為5類是合理的。

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

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

結(jié)果分析：

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

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

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

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

4 結(jié)束語

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

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

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

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

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

[4] 金菊良,丁晶,魏一鳴.加速遺傳算法在地下水位動態(tài)分析中的應用[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] 周成成.大型活動突發(fā)事件下交通疏散效率評價研究[D].成都:西南交通大學,2014.

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

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

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

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

[11] 樓文高,喬龍.投影尋蹤分類建模理論的新探索與實證研究[J].數(shù)理統(tǒng)計與管理,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