国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于GA-PSO的粗糙集屬性約簡(jiǎn)算法*

2015-07-10 01:23:24戴上平劉素軍鄭素菲
關(guān)鍵詞:約簡(jiǎn)粗糙集適應(yīng)度

戴上平,劉素軍,鄭素菲

(華中師范大學(xué)計(jì)算機(jī)學(xué)院,湖北 武漢 430079)

1 引言

粗糙集理論[1]是一種新的數(shù)學(xué)理論,用于處理不準(zhǔn)確和不完整的數(shù)據(jù)。它已被廣泛應(yīng)用在人工智能、知識(shí)和數(shù)據(jù)發(fā)現(xiàn)、模式識(shí)別和分類、數(shù)據(jù)分析和其他不精確推理的方面。其通過(guò)知識(shí)約簡(jiǎn)導(dǎo)出問(wèn)題的決策或分類規(guī)則來(lái)保持穩(wěn)定的分類能力。在該理論中屬性約簡(jiǎn)是一個(gè)核心問(wèn)題,它是指信息系統(tǒng)在保持能力或知識(shí)的歸類決定沒(méi)有改變的同時(shí),刪除不重要的或不相關(guān)的屬性。

遺傳算法GA(Genetic-Algorithm)具有隱含并行性、魯棒性、可擴(kuò)展性等優(yōu)點(diǎn),擅長(zhǎng)全局搜索,除了適應(yīng)度計(jì)算外,幾乎所有的遺傳操作都建立在全局統(tǒng)計(jì)處理的基礎(chǔ)上。這樣使得全局的重復(fù)計(jì)算量大且易“早熟”。遺傳算法在屬性約簡(jiǎn)過(guò)程中采用不同的編碼方法,會(huì)產(chǎn)生不同的問(wèn)題,從而導(dǎo)致沒(méi)有根據(jù)的積木假設(shè),最終使得屬性約簡(jiǎn)時(shí)GA過(guò)早收斂難以達(dá)到全局最優(yōu)。粒子群優(yōu)化PSO(Particle-Swarm-Optimization)算法是一種通過(guò)用無(wú)質(zhì)量無(wú)體積的粒子作為個(gè)體,同時(shí)為每個(gè)粒子提供簡(jiǎn)單行為規(guī)則使整個(gè)粒子群呈現(xiàn)出一定特性,以解決復(fù)雜的優(yōu)化問(wèn)題的進(jìn)化計(jì)算技術(shù)。

在粗糙集屬性約簡(jiǎn)[2]中,GA與PSO在進(jìn)化過(guò)程中均能保留和利用位置的信息,但除此之外,PSO算法還能利用速度(即位置的變化過(guò)程)信息,使得PSO比GA收斂于最優(yōu)解的速度更快。粒子群約簡(jiǎn)算法過(guò)程中,粒子群在迭代時(shí)容易陷入到局部極值點(diǎn)中,導(dǎo)致得不到全局最優(yōu)解,使得最后的約簡(jiǎn)結(jié)果不是最小相對(duì)屬性集。針對(duì)遺傳約簡(jiǎn)與粒子群約簡(jiǎn)的不足,本文提出了一種新的約簡(jiǎn)算法,即:基于GA-PSO的粗糙集屬性約簡(jiǎn)算法。

2 粗糙集基本知識(shí)與GA、PSO的引入

2.1 常用粗糙集基本定義

定義1設(shè)S=(U,A,V,F)為一個(gè)信息系統(tǒng),又稱知識(shí)表示系統(tǒng)。其中,U={U1,U2,…,U|U|}為論域?qū)ο罂臻g,U是有限非空集合,稱為;A={ɑ1,ɑ2,…,ɑ|A|}為屬性的有限非空集合;V=∪Vɑ,其中ɑ∈A,Vɑ為屬性ɑ的值域;F:U×A→V為信息函數(shù),對(duì)于?ɑ∈A、?x∈U,F(xiàn)(x,ɑ)∈Vɑ,它指定了U中每一對(duì)象的屬性值。若A中的屬性又可分為兩個(gè)不相交的子集,即條件屬性集C和決策屬性集D,即:A=C∪D,C∩D=?,則S稱為決策表。

定義2給定一個(gè)知識(shí)表示系統(tǒng)S=(U,A,V,F),P?A,X?U,x?U,集合X關(guān)于I的下近似、上近似、負(fù)區(qū)及邊界區(qū)分別為:

negP(X)=∪{x∈U:I(x)∩X≠?}

定義3設(shè)知識(shí)表達(dá)系統(tǒng)S=(U,A,V,F),A=C∪D,C∩D=?,條件屬性C對(duì)決策屬性D的支持度(決策屬性D對(duì)條件屬性C的依賴度)定義為:

(1)

式(1)稱D在K程度上依賴于C,其中|·|指集合包含的元素個(gè)數(shù),一般取0≤K≤1。當(dāng)屬性集中的屬性值決定著屬性的所有屬性值時(shí),本文把K取值為1;當(dāng)屬性集中的屬性值決定著屬性中的部分屬性值時(shí),K的取值范圍小于1。

定義4若S=(U,A,V,F)是一個(gè)知識(shí)表達(dá)系統(tǒng),當(dāng)B為C的一個(gè)(相對(duì)于決策屬性D的)相對(duì)約簡(jiǎn)時(shí),應(yīng)滿足條件:B?C,若KB=KC,且不存在R?B,使得KR=KB,此時(shí)約簡(jiǎn)結(jié)果可能有多個(gè)。相對(duì)約簡(jiǎn)的集合記為redD(C),所有C屬性約簡(jiǎn)的交集記為Core(C)(又稱C的核),且有CoreD(C)=∩redD(C)。最小約簡(jiǎn)指含有最少屬性的約簡(jiǎn)。

2.2 遺傳算法

2.2.1 染色體編碼

遺傳算法[3]的解集是從經(jīng)過(guò)基因編碼的一定數(shù)目個(gè)體組成的一個(gè)種群開(kāi)始,該種群中的各個(gè)體以染色體為載體,采用固定大小的二進(jìn)制串表示其基因值。長(zhǎng)度為15的染色體可用Y=110100101011001來(lái)表達(dá)。

2.2.2 選擇操作

從種群中選擇出質(zhì)量?jī)?yōu)的個(gè)體使之作為父代再生優(yōu)化同時(shí)淘汰劣質(zhì)個(gè)體的操作稱為選擇操作。輪盤(pán)賭方法選擇算子是傳統(tǒng)的遺傳屬性約簡(jiǎn)中的選擇運(yùn)算,在該操作中,各個(gè)體的選擇概率和其適應(yīng)度值成比例,其適應(yīng)度值比例越大,該染色體代表的種群個(gè)體被選擇交配的機(jī)會(huì)也越大。

2.2.3 交叉操作

交叉操作是把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新的個(gè)體。交叉運(yùn)算根據(jù)交叉率將種群中的兩個(gè)個(gè)體隨機(jī)地交換某些基因,能夠產(chǎn)生新的基因組合。在使用單點(diǎn)交叉操作中,從個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn),實(shí)行交叉時(shí),該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換,并生成兩個(gè)新的染色體個(gè)體。該處用到的雙親染色體由輪盤(pán)賭方法隨機(jī)選出,參照依據(jù)是每個(gè)染色體適應(yīng)度值。

2.2.4 變異操作

變異操作是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。其目的是保證遺傳操作具有局部搜索能力的同時(shí)又要維持群體的多樣性,進(jìn)而保證在加速向最優(yōu)解收斂的同時(shí)又能防止出現(xiàn)未成熟收斂。常用的變異運(yùn)算是根據(jù)變異概率Pm隨機(jī)選擇染色體的個(gè)體,實(shí)現(xiàn)在某些位置進(jìn)行0,1翻轉(zhuǎn)。

2.3 粒子群算法

粒子群算法的數(shù)學(xué)思想為:在D維搜索空間中,有一個(gè)群體由m個(gè)粒子組成,第i個(gè)粒子(i=1,2,…,m)的位置表示為Xi=(χi1,χi2,…,χid),速度表示為Vi=(υi1,υi2,…,υid)。第i個(gè)粒子搜索到的最優(yōu)位置為Pbesti=(ρbesti1,ρbesti2,…,ρbestid),整個(gè)粒子搜索到的最優(yōu)位置記為Gbest=(gbesti1,gbesti2,…,gbestid)。綜上定義,粒子群算法的進(jìn)化方程描述為:

(2)

(3)

其中,i= 1,2,…,m;d= 1,2,…,D;t為當(dāng)前迭代次數(shù);慣性權(quán)重ω取非負(fù)常數(shù);τ1、τ2為加速因子,取非負(fù)常數(shù),用來(lái)調(diào)節(jié)粒子向全局最優(yōu)粒子和個(gè)體最優(yōu)粒子方向飛行的步長(zhǎng);γ1、γ2為[0,1]內(nèi)兩個(gè)相互獨(dú)立的均勻分布的隨機(jī)函數(shù)。

3 GA-PSO屬性約簡(jiǎn)算法

3.1 編碼方法

ωk=KCore(C)∪ck-KCore(C)

(4)

(5)

屬性ck的對(duì)應(yīng)位lk取0或1由公式(6)決定:

(6)

即將屬性編碼為粒子。

3.2 粒子適應(yīng)度函數(shù)

適應(yīng)值函數(shù)的形式?jīng)Q定著群體的進(jìn)化行為,也是對(duì)粒子的適應(yīng)性進(jìn)行評(píng)價(jià)的唯一確定指標(biāo)。為控制粒子朝著約簡(jiǎn)的方向發(fā)展,保證所得到的粒子是一個(gè)約簡(jiǎn)。本文定義適應(yīng)度函數(shù)與平均適應(yīng)度函數(shù)如下:

Fitness(P)=k1*(KP/KC)+k2*(1-KP)

(7)

(8)

其中,k1的大小決定著待約簡(jiǎn)粒子適應(yīng)值的大小,與之成正比。種群中優(yōu)良粒子保留下來(lái)的概率越大,其對(duì)應(yīng)的取值也越大。而函數(shù)屬性數(shù)目的大小或者約簡(jiǎn)屬性數(shù)目的大小由k2判定,其值越大,它的適應(yīng)度值也越大。式(9)決定k1與k2的大小。當(dāng)KP/KC的值為“1”時(shí),得到的屬性集是一個(gè)約簡(jiǎn)。

(9)

3.3 遺傳操作與粒子更新

(10)

(11)

(12)

權(quán)重因子τ1、τ2和隨機(jī)數(shù)γ1、γ2決定變異的程度與方向,式(12)使得變異有了學(xué)習(xí)能力。

3.4 局部最優(yōu)與全局最優(yōu)

局部最優(yōu)是個(gè)體極值,即粒子在迭代更新過(guò)程中自身所找到的最優(yōu)解。全局最優(yōu)則是全局極值,即整個(gè)種群在進(jìn)化迭代中所找到的最優(yōu)解也就是適應(yīng)度值最好的一個(gè)位置。在GA-PSO算法中,局部最優(yōu)需要與粒子新的適應(yīng)度值進(jìn)行比較,由式(13)決定。全局最優(yōu)為種群中最優(yōu)質(zhì)粒子,按式(14) 與每個(gè)粒子的局部最優(yōu)進(jìn)行比較求得。

Pbesti=max(Pbesti,Fitness(i))

(13)

Gbest=max(Pbesti,Gbest)

(14)

3.5 GA-PSO約簡(jiǎn)算法執(zhí)行過(guò)程

輸入:一個(gè)決策表S=(U,A,V,F),A=C∪D,C是條件屬性集,D是決策屬性集。

輸出:此決策表最小相對(duì)屬性約簡(jiǎn)。

步驟1由式(1)計(jì)算出決策屬性D關(guān)于條件屬性C的支持度KC(D);

步驟2令Core(C) =?,逐個(gè)去掉一個(gè)屬性c∈C,若KC-c≠Kc,則Core(C)=Core(C)∪{c}。若KCore(D) =Kc(D),則Core(C)即為最小相對(duì)約簡(jiǎn)。否則,轉(zhuǎn)步驟3。

步驟3初始化粒子。除去核屬性,由式(4)計(jì)算其余各屬性權(quán)重,并把求得的權(quán)重按照公式(5)映射到[0,1],根據(jù)公式(6)初始化各粒子,設(shè)置最大迭代次數(shù)T=80。

步驟4更新粒子群。由式(7)計(jì)算第i個(gè)粒子在t時(shí)刻的適應(yīng)值Fitness(i),由式(8)計(jì)算當(dāng)前種群的平均適應(yīng)度AF。由式(11)和式(12)更新粒子位置,由式(13)更新局部最優(yōu)值,由式(14)更新全局最優(yōu)粒子,取種群中粒子最優(yōu)適應(yīng)度為全局最優(yōu)粒子。

步驟5將種群中每個(gè)粒子的適應(yīng)度值與當(dāng)前種群的AF值進(jìn)行比較,適應(yīng)度大于AF的粒子給予保留,適應(yīng)度小于AF的粒子,用上面提到的均勻交叉法交叉、變異操作到變異算子。

步驟6判斷是否滿足終止條件,若達(dá)到最大迭代次數(shù)或所求得的結(jié)果不再發(fā)生變化,則終止迭代,否則轉(zhuǎn)步驟4。

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

為了驗(yàn)證本文算法(記為GA-PSO屬性約簡(jiǎn))的有效性和正確性,本文用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的標(biāo)準(zhǔn)數(shù)據(jù)集作為測(cè)試數(shù)據(jù),從UCI數(shù)據(jù)庫(kù)中分別選取具有低、中、高維特征的Iris、Zoo、Sogbeanbarge三個(gè)數(shù)據(jù)集作為算例進(jìn)行計(jì)算,并同文獻(xiàn)[5]的基于遺傳算法的粗糙集屬性約簡(jiǎn)算法(記為GA屬性約簡(jiǎn))與文獻(xiàn)[6]的基于粒子群優(yōu)化算法的粗糙集屬性約簡(jiǎn)(記為PSO屬性約簡(jiǎn))在屬性約簡(jiǎn)過(guò)程中適應(yīng)度值和計(jì)算平均時(shí)間開(kāi)銷兩方面進(jìn)行比較。

對(duì)本文提出的GA-PSO算法,參數(shù)值分別取變異概率Pm=0.2,交叉概率Pc=0.75,m=25,在Windows7、內(nèi)存為2 GB的PC機(jī)上運(yùn)行10次;GA約簡(jiǎn)算法與粒子群約簡(jiǎn)算法參數(shù)設(shè)置參照參考文獻(xiàn)[5,6],最大迭代次數(shù)均設(shè)置為80。三組實(shí)驗(yàn)均在同一臺(tái)PC機(jī)上運(yùn)行,求得最小相對(duì)屬性約簡(jiǎn)集與平均運(yùn)行時(shí)間。三種算法的屬性約簡(jiǎn)結(jié)果如表1所示,為了更好地呈現(xiàn)出進(jìn)化過(guò)程,圖1給出了具體進(jìn)化過(guò)程中的適應(yīng)度值曲線;為了觀察收斂速度,圖2給出了三種算法進(jìn)行相同迭代次數(shù)的約簡(jiǎn)實(shí)驗(yàn)10次的運(yùn)行時(shí)間曲線圖。

Table 1 Results of attribute reduction

Figure 1 Fitness value curve of Zoo evolution圖1 Zoo進(jìn)化過(guò)程適應(yīng)度值變化曲線

Figure 2 Numbers of experiments vs run time about Zoo reduction圖2 Zoo約簡(jiǎn)實(shí)驗(yàn)不同次數(shù)運(yùn)行時(shí)間曲線

由實(shí)驗(yàn)結(jié)果可以看出,GA-PSO約簡(jiǎn)算法與遺傳算法相比,運(yùn)行時(shí)間短且能得到最小相對(duì)屬性集;與粒子群算法相比,雖然運(yùn)行時(shí)間相對(duì)較長(zhǎng),但是,其約簡(jiǎn)是以犧牲時(shí)間為代價(jià)獲得最小相對(duì)屬性集,進(jìn)而證實(shí)本文提出的算法是有效的。本算法在保證運(yùn)行速度相對(duì)快的前提下,能得到最小相對(duì)屬性集。

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

近年來(lái)粗糙集理論以其獨(dú)特的優(yōu)勢(shì)引起了廣泛的關(guān)注,并成功應(yīng)用于臨床醫(yī)療診斷、量子粒子群[7]、預(yù)測(cè)控制、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘[8]等諸多領(lǐng)域。粗糙集理論與人工智能算法相結(jié)合也是其應(yīng)用范圍之一。但是,粗糙集理論中求解最小約簡(jiǎn)是NP-hard 問(wèn)題。本文提出了一種基于GA-PSO的粗糙集屬性約簡(jiǎn)算法,在跨越局部搜索障礙的同時(shí)又保證了最小相對(duì)屬性約簡(jiǎn)。實(shí)驗(yàn)表明,該算法在決策表屬性約簡(jiǎn)中的有效性和實(shí)用性。本算法雖然求得了最小相對(duì)屬性約簡(jiǎn)集,但是以犧牲時(shí)間為代價(jià),如何高效地對(duì)決策表進(jìn)行屬性約簡(jiǎn)是今后進(jìn)一步研究的方向。

[1] Pawak Z.Rough sets[J].International Journal of Computer and Information Science,1982,11(5):314-356.

[2] Dai Jian-hua,Li Yuan-xiang.An algorithm for reduction of attributes in decision system based on rough set[J].Mini-Micro System,2003,3(3):523-526.(in Chinese)

[3] Xiao Hou-guo,Sang Lin.Rough set attribute reduction algorithm based on GA and its application[J].Computer Engineering and Applications,2008,44(15):228-230.(in Chinese)

[4] Walczak W,Massart D L.Tutorial,rough sets theory[J].Chemo Metrics and Intelligent Laboratory Systems,1999,47:1-16.

[5] Yan Yan,Yang Hui-zhong. Rough set attribute reduction algorithm based on GA [J].Computer Engineering and Applications,2007,43(31):156-158.(in Chinese)

[6] Dai Jian-hua,Chen Wei-dong,Gu Hong-ying,et al.Particle swarm algorithm for minimal attribute reduction of decision data tables[C]∥Proc of Multi-Symposiums on Computer and Computational Sciences,2006:572-575.

[7] Wang Jia-yang,Xie Ying.Minimal attribute reduction algorithm based on quantum particle swarm optimization[J].Computer Engineering,2009,35(12):148-150.(in Chinese)

[8] Huang Xiao-fang.Algorithm of decision tree in data mining and its application[J].O.I.Automation,2005,24(2):35-36.(in Chinese)

附中文參考文獻(xiàn):

[2] 代建華,李元香.一種基于粗糙集的決策系統(tǒng)屬性約簡(jiǎn)算法[J].小型微型計(jì)算機(jī)系統(tǒng),2003,3(3):523-526.

[3] 肖厚國(guó),桑琳.基于遺傳算法的粗糙集屬性約簡(jiǎn)及其應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(15):228-230.

[5] 顏艷,楊慧中.基于遺傳算法的粗糙集屬性約簡(jiǎn)算法[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(31):156-158.

[7] 王加陽(yáng),謝穎.基于量子粒子群優(yōu)化的最小屬性約簡(jiǎn)算法[J].計(jì)算機(jī)工程,2009,35(12):148-150.

[8] 黃曉芳.數(shù)據(jù)挖掘中決策樹(shù)算法及其應(yīng)用[J].兵工自動(dòng)化,2005,24(2):35-36.

猜你喜歡
約簡(jiǎn)粗糙集適應(yīng)度
改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
基于Pawlak粗糙集模型的集合運(yùn)算關(guān)系
基于二進(jìn)制鏈表的粗糙集屬性約簡(jiǎn)
實(shí)值多變量維數(shù)約簡(jiǎn):綜述
基于模糊貼近度的屬性約簡(jiǎn)
多?;植诩再|(zhì)的幾個(gè)充分條件
雙論域粗糙集在故障診斷中的應(yīng)用
基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
兩個(gè)域上的覆蓋變精度粗糙集模型
一種改進(jìn)的分布約簡(jiǎn)與最大分布約簡(jiǎn)求法
河南科技(2014年7期)2014-02-27 14:11:29
永州市| 竹山县| 新田县| 东城区| 张家口市| 白城市| 沈阳市| 通江县| 咸阳市| 元谋县| 灵川县| 中西区| 富阳市| 昭平县| 同德县| 阳东县| 大荔县| 临夏县| 应用必备| 绥棱县| 利辛县| 万年县| 通河县| 安图县| 黑河市| 崇文区| 恩平市| 连云港市| 长治县| 黎平县| 沂源县| 东乌珠穆沁旗| 红桥区| 高阳县| 哈巴河县| 阿图什市| 华池县| 贞丰县| 灌南县| 英德市| 合山市|