數(shù)據(jù)挖掘與技術(shù) ch 遺傳算法PPT學(xué)習(xí)教案

1、會計(jì)學(xué)1數(shù)據(jù)挖掘與技術(shù)數(shù)據(jù)挖掘與技術(shù) ch 遺傳算法遺傳算法第1頁/共38頁第2頁/共38頁第3頁/共38頁第4頁/共38頁第5頁/共38頁遺傳算法可定義為一個(gè)遺傳算法可定義為一個(gè)8 8元組：元組：GA = (GA = (C C, , E E, , P P0 0, , MM, , , , , , , , T T) ) 式中，式中， C C個(gè)體的編碼方法；個(gè)體的編碼方法； E E個(gè)體適應(yīng)值評價(jià)函數(shù)；個(gè)體適應(yīng)值評價(jià)函數(shù)； P P0 0初始種群；初始種群； MM群體大小；群體大?。?選擇算子；選擇算子； 交叉算子；交叉算子； 變異算子；變異算子； T T遺傳算法終止條件。遺傳算法終止條件。 第6頁/

2、共38頁初始化種群初始化種群編碼為染色體編碼為染色體種群種群計(jì)算各染色體的適應(yīng)值計(jì)算各染色體的適應(yīng)值遺傳操作遺傳操作( (選擇、交叉、變異選擇、交叉、變異) )種群種群停機(jī)條件滿足停機(jī)條件滿足？種群種群種群種群N NY Y結(jié)結(jié) 束束圖圖 遺傳算法的工作原理示意圖遺傳算法的工作原理示意圖) 1( tP)(tP第7頁/共38頁遺傳算法的關(guān)鍵技術(shù)包括：遺傳算法的關(guān)鍵技術(shù)包括： 編碼問題；編碼問題； 初始種群的產(chǎn)生；初始種群的產(chǎn)生； 確定適應(yīng)值函數(shù)；確定適應(yīng)值函數(shù)； 選擇遺傳操作算子；選擇遺傳操作算子； 停機(jī)條件。停機(jī)條件。 第8頁/共38頁編碼問題編碼問題由于遺傳算法不能直接處理解空間的解數(shù)據(jù)，由于

3、遺傳算法不能直接處理解空間的解數(shù)據(jù)，因此必須通過編碼將它們表示成遺傳空間的基因此必須通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。因型串結(jié)構(gòu)數(shù)據(jù)。編碼方法在很大程度上決定了如何進(jìn)行群體的編碼方法在很大程度上決定了如何進(jìn)行群體的遺傳進(jìn)化運(yùn)算以及遺傳進(jìn)化的效率。由于不同遺傳進(jìn)化運(yùn)算以及遺傳進(jìn)化的效率。由于不同的編碼方法具有不同的特點(diǎn)，為了提高遺傳算的編碼方法具有不同的特點(diǎn)，為了提高遺傳算法的效率，應(yīng)根據(jù)不同的情況采用不同的編碼法的效率，應(yīng)根據(jù)不同的情況采用不同的編碼方式。方式。主要的編碼方法有二進(jìn)制編碼、浮點(diǎn)數(shù)編碼、主要的編碼方法有二進(jìn)制編碼、浮點(diǎn)數(shù)編碼、符號編碼、多參數(shù)編碼、可變長染色體編碼等

4、符號編碼、多參數(shù)編碼、可變長染色體編碼等。第9頁/共38頁編碼問題編碼問題在遺傳算法中一般用二值（在遺傳算法中一般用二值（0 0，1 1）向量表示染）向量表示染色體，故先要對規(guī)則進(jìn)行編碼。色體，故先要對規(guī)則進(jìn)行編碼。編碼采用二進(jìn)制，將由特征和類別組成的訓(xùn)練編碼采用二進(jìn)制，將由特征和類別組成的訓(xùn)練例子集編碼成二進(jìn)制字符串的遺傳樣本。一個(gè)例子集編碼成二進(jìn)制字符串的遺傳樣本。一個(gè)樣本樣本MMi i是一個(gè)二元組，其形式如下：是一個(gè)二元組，其形式如下： MMi i = =x xi i，y yi i ，其中：，其中：i i為樣本號；為樣本號；x x為條件部分，即訓(xùn)為條件部分，即訓(xùn)練例子的各特征編碼；練例子

5、的各特征編碼；y y為結(jié)論部分，即訓(xùn)練為結(jié)論部分，即訓(xùn)練例子的類別。例子的類別。第10頁/共38頁具體的編碼規(guī)則如下：具體的編碼規(guī)則如下： 若屬性為范疇型，定義屬性段的寬度等于屬性取值個(gè)數(shù)。若屬性為范疇型，定義屬性段的寬度等于屬性取值個(gè)數(shù)。對于每個(gè)屬性段，若第一位為對于每個(gè)屬性段，若第一位為* *，表示該屬性取值可以，表示該屬性取值可以為任意；否則，各位若取值為為任意；否則，各位若取值為1 1，表示取該屬性值，表示取該屬性值，0 0表示表示不取該屬性值。例如，某條件屬性不取該屬性值。例如，某條件屬性C Ci i對應(yīng)的編碼二進(jìn)制串對應(yīng)的編碼二進(jìn)制串為為011001011001，表示該屬性取第二個(gè)

6、屬性值或第三個(gè)屬性值或，表示該屬性取第二個(gè)屬性值或第三個(gè)屬性值或第六個(gè)屬性值，即第六個(gè)屬性值，即 若屬性為數(shù)值型，定義屬性段的寬度若屬性為數(shù)值型，定義屬性段的寬度 ，其，其中中n n為該屬性的取值個(gè)數(shù)。對于每個(gè)屬性段，若第一位為為該屬性的取值個(gè)數(shù)。對于每個(gè)屬性段，若第一位為* *，表示該屬性取值可以為任意，表示該屬性取值可以為任意,632iiiiCCCC 2)(2lognw第11頁/共38頁 初始種群的產(chǎn)生初始種群的產(chǎn)生GAGA以初始種群作為初始點(diǎn)開始迭代。初始種群以初始種群作為初始點(diǎn)開始迭代。初始種群大小表示群體中所含個(gè)體的數(shù)量。當(dāng)個(gè)體數(shù)量取大小表示群體中所含個(gè)體的數(shù)量。當(dāng)個(gè)體數(shù)量取值較小時(shí)

7、，可提高遺傳算法的運(yùn)算速度，但值較小時(shí)，可提高遺傳算法的運(yùn)算速度，但搜索搜索空間分布范圍有限，空間分布范圍有限，降低了群體的多樣性，有可降低了群體的多樣性，有可能會引起遺傳算法的早熟現(xiàn)象；當(dāng)個(gè)體數(shù)量取值能會引起遺傳算法的早熟現(xiàn)象；當(dāng)個(gè)體數(shù)量取值較大時(shí)，一方面計(jì)算復(fù)雜，會使遺傳算法的運(yùn)行較大時(shí)，一方面計(jì)算復(fù)雜，會使遺傳算法的運(yùn)行效率降低，另一方面，部分高適應(yīng)值的個(gè)體可能效率降低，另一方面，部分高適應(yīng)值的個(gè)體可能被淘汰，影響交叉。初始種群的一般取值范圍是被淘汰，影響交叉。初始種群的一般取值范圍是2010020100。第12頁/共38頁產(chǎn)生初始種群的方法通常有兩種：產(chǎn)生初始種群的方法通常有兩種：（1

8、 1）對問題的解無任何先驗(yàn)知識的情況，采用隨機(jī)產(chǎn)生）對問題的解無任何先驗(yàn)知識的情況，采用隨機(jī)產(chǎn)生樣本的方法；樣本的方法；（2 2）對于具有某些先驗(yàn)知識的情況，可首先將這些先驗(yàn)）對于具有某些先驗(yàn)知識的情況，可首先將這些先驗(yàn)知識轉(zhuǎn)變?yōu)楸仨殱M足的一組要求，然后在滿足這些要知識轉(zhuǎn)變?yōu)楸仨殱M足的一組要求，然后在滿足這些要求的解中隨機(jī)地選取樣本。這樣選擇初始種群可使遺求的解中隨機(jī)地選取樣本。這樣選擇初始種群可使遺傳算法更快地達(dá)到最優(yōu)解。傳算法更快地達(dá)到最優(yōu)解。 第13頁/共38頁第14頁/共38頁第15頁/共38頁第16頁/共38頁0001100000010111100100000001011001110

9、1001010101010 （8） （5）（2）（10）（7）11100101101001011011110000000110011101000001010011（12）（5）（19）（10）（14）第17頁/共38頁第18頁/共38頁個(gè)體個(gè)體染色體染色體適應(yīng)度適應(yīng)度選擇概率選擇概率累計(jì)概率累計(jì)概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.347826611100101

10、10120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.000000第19頁/共38頁71234568910個(gè)體選擇概率累計(jì)概率10.0869570.08695720.0543481014130430.0217390.16304340.1086960.27173950.0760870.34782660.1304350.47826170.0543480.53260980.2065220.7391

11、3090.1086960.847826100.1521741.000000第20頁/共38頁71234568910 顯然，適應(yīng)度高的個(gè)體被選中的概率越大，而且可能被選中；而適應(yīng)度低的個(gè)體則很有可能被淘汰。第21頁/共38頁第22頁/共38頁第23頁/共38頁第24頁/共38頁第25頁/共38頁第26頁/共38頁第27頁/共38頁第28頁/共38頁x2)x(f第29頁/共38頁iiiiffPiinffffi第30頁/共38頁編號編號初始種群位串初始種群位串參數(shù)值參數(shù)值x值值目標(biāo)適應(yīng)值目標(biāo)適應(yīng)值選擇率選擇率期望值期望值實(shí)選值實(shí)選值1234011011100001000100111324819169

12、576643610.140.490.060.310.581.970.221.231201總和總和平均值平均值最大值最大值11702935761.000.250.494.001.001.974.01.02.0第31頁/共38頁選擇后的交配池選擇后的交配池交叉對象交叉對象交叉位置交叉位置新的種群新的種群x值值f(x)=x201101110001100010011214344220110011001110111000012252716144625729256總和總和平均值平均值最大值最大值1754439729第32頁/共38頁編號編號初始種群位串初始種群位串參數(shù)值參數(shù)值x值值目標(biāo)適應(yīng)值目標(biāo)適應(yīng)值選擇率選擇率期望值期望值實(shí)選值實(shí)選值123401100110011101110000122527161446257292560.080.360.420.150.331.421.660.580121總和總和平均值平均值最大值最大000.250.424.001.001.664