遺傳算法在數(shù)據(jù)挖掘中的應(yīng)用研究

張騫 西安工程大學(xué)計算機(jī)科學(xué)學(xué)院

1 研究背景及其意義

遺傳算法基于生物進(jìn)化，完成了一系列設(shè)計，從而達(dá)到優(yōu)化的目的，這些過程主要涉及到，交叉組合，自然選擇。遺傳算法從一組初始可行解，出發(fā)，從而在可行域全局搜索下得到全局最優(yōu)解，該特性在優(yōu)化函數(shù)與優(yōu)化組合方面得到了很好的利用，同時也為計算機(jī)智能技術(shù)提供的技術(shù)提供了技術(shù)支撐。為了增強(qiáng)數(shù)據(jù)挖掘的準(zhǔn)確性，很多學(xué)者紛紛在數(shù)據(jù)挖掘之中引入了遺傳算法，并且取得了一定的成就。

2 遺傳算法的基本原理

遺傳算法主要來源于生物系統(tǒng)，鐘中計算機(jī)模擬研究，該算法主要是用來模擬生物進(jìn)化，是計算機(jī)與自然遺傳學(xué)相結(jié)合的一種研究計算方法。遺傳算法的基礎(chǔ)是遺傳理論與自然選擇，該算法是將適者生存和群體內(nèi)染設(shè)計隨機(jī)交換相結(jié)合的搜索算法。在搜索前，先需要通過以某種方式把變量進(jìn)行編碼，產(chǎn)生的變量叫做染色體，不同的染色體形成一個群體，再以某種方法對這些染色體進(jìn)行評估，從而得出適應(yīng)值，產(chǎn)生群體的步驟總結(jié)如下：

第一，按照染色體的適應(yīng)值完成染色體的選擇和復(fù)制染色體的次數(shù)，第二，對染色體進(jìn)行重組，變異從而生成新的染色體。

3 遺傳算法的主要特點

為了處理優(yōu)化計算等各種難題，學(xué)者紛紛提出了多種優(yōu)化算法，比如分支定界法，梯度法，單純形法。沒有算法，有著各自的優(yōu)點與缺點，以及各自的限制，已轉(zhuǎn)算法作為一種應(yīng)用于復(fù)雜系統(tǒng)優(yōu)化計算的魯棒搜索算法，相比于其他算法而言，特點總結(jié)如下：

遺傳算法編碼方式的選擇。處理對象是參數(shù)的編碼及并非是問題參數(shù)，搜索過程不會受到優(yōu)化函數(shù)的約束。

遺傳算法的處理模式規(guī)模龐大，具有高定型性，同時搜索效率較高。

遺傳算法思想簡單，實現(xiàn)步驟以及運行方式，簡單易懂，形象生動，考慮到遺傳算法這些特點，從而使得遺傳算法在眾多領(lǐng)域得到廣泛應(yīng)用。

4 遺傳算法的步驟

遺傳算法是生物進(jìn)化模擬的一種優(yōu)化搜索算法，主要通過計算機(jī)對生物進(jìn)化過程進(jìn)行模擬，懟不斷優(yōu)化各種種群，從而找到最優(yōu)解遺傳算法的要素，主要包括適應(yīng)度函數(shù)，參數(shù)編碼，遺傳操作，群體設(shè)定，結(jié)束參數(shù)等。

4.1 編碼方法

遺傳算法中主要是通過編碼的方式對問題的可行解進(jìn)行描述，換言之，就是把問題可行解從空間向遺傳算法的搜索空間進(jìn)行轉(zhuǎn)換，這種方法被稱為編碼十進(jìn)制，編碼波動小，準(zhǔn)確度高，因此本文選擇的編碼方式是十進(jìn)制編碼。評估編碼機(jī)制通常選擇的規(guī)范總結(jié)如下：

(1）完備性（Completeness）

問題空間中的全部點都可以當(dāng)作是GA空間里的點（染色體）表現(xiàn)。

(2）健全性（Soundness）

GA 空間里的染色體可以對應(yīng)全部問題空間里候選解。

(3）非冗余性（Nonredundancy）

染色體和候選解一一對應(yīng)。

現(xiàn)今常用的編碼方式包括二進(jìn)制編碼，實數(shù)編碼，符號編碼。最常用的編碼方式是二進(jìn)制編碼，二進(jìn)制編碼中的另一種變形就是格雷碼編碼，這是數(shù)字排序系統(tǒng)中的一種，十進(jìn)制編碼主要運用于高精度要求的連續(xù)函數(shù)優(yōu)化問題中。

4.2 適應(yīng)度函數(shù)

評價遺傳算法的標(biāo)準(zhǔn)是適應(yīng)度函數(shù)，在ga 中，主要是運用適應(yīng)度函數(shù)來完成個體適宜程度的計算，所以適應(yīng)度函數(shù)也能夠叫做評價函數(shù)，該函數(shù)主要是用來完成，完整個體優(yōu)劣標(biāo)準(zhǔn)的評判。適應(yīng)度函數(shù)直接對遺傳算法的性能起到?jīng)Q定性作用，適應(yīng)度函數(shù)需要滿足條件，總結(jié)如下：

第一，單值、連續(xù)、非負(fù)、適應(yīng)度越大越好；

第二，設(shè)計的合理性、一致性；

第三，設(shè)計盡可能簡單，計算量越小越好；

第四，具有較強(qiáng)的通用性。

5 基于模擬退火遺傳算法的關(guān)聯(lián)規(guī)則挖掘

模擬退火算法首次在1953 年由Metropolis 等人提出的，Kirkpatrick 于1983 年將其應(yīng)用于組合優(yōu)化。這個算法具體是針對NP 復(fù)雜性問題、克服初值依賴性、克服優(yōu)化過程陷入局部極小。這個基本思想是對比統(tǒng)計熱力學(xué)的熱平衡問題與優(yōu)化過程，物理背景是固體退火過程的物理圖像和統(tǒng)計特性，Metropolis準(zhǔn)則接受新的解，避免算法陷入局部最優(yōu)，算法的合理應(yīng)用還需要合理的冷卻進(jìn)度表。

5.1 編碼

每個事物的每個屬性的取值，用十進(jìn)制數(shù)來標(biāo)識，：每個十進(jìn)制數(shù)就是一個，基因把事物的全部屬性的實踐次數(shù)連接，從而生成的十進(jìn)制串就一條染色體，也就是說每個染色體的構(gòu)成形式如：A1∧A2 ∧…∧An 構(gòu)成，編碼時字段順序一定要保持不變。

5.2 適應(yīng)度函數(shù)設(shè)計

適應(yīng)度一般用來衡量群體中每個個體在優(yōu)化計算的過程之中可能得到的最優(yōu)解的優(yōu)良程度，這是遺傳算法優(yōu)勝劣汰執(zhí)行的重要依據(jù)，適應(yīng)度函數(shù)主要是評價個體的適應(yīng)度，區(qū)分群體中優(yōu)勝劣汰的重要標(biāo)準(zhǔn)。本文取適應(yīng)度函數(shù)是：

通過上面的公式知道當(dāng)興趣度大于1 的時候，表示正相關(guān)，也就是說在選擇操作過程中，被選中的概率越高，假如興趣度小于1，表示負(fù)相關(guān)，選擇操作中被選中的概率就越小。

6 規(guī)則提取與評價

如果相鄰幾代的平均適應(yīng)度差值小于某個閥值ε，或者達(dá)到了最大進(jìn)化代數(shù)時，則結(jié)束，輸出結(jié)果。由上文描述可得出改進(jìn)的模擬退火遺傳算法的關(guān)聯(lián)規(guī)則算法流程圖：

圖2 模擬退火遺傳算法關(guān)聯(lián)規(guī)則流程圖

7 結(jié)語

20 世紀(jì)90 年代初，數(shù)據(jù)挖掘技術(shù)應(yīng)運而生，數(shù)據(jù)挖掘技術(shù)主要是將用戶真正需要的隱藏、有效的信息提取出來，并且進(jìn)行相應(yīng)的處理，該技術(shù)涉及到多學(xué)科研究。有用信息提取出來之前，用戶是完全不知情的，完全不知道大量的數(shù)據(jù)量之中，哪些是對自己有用的，哪些是對自己有價值的。

作為數(shù)據(jù)挖掘中重要算法之一，遺傳算法在數(shù)據(jù)挖掘方面取得重大應(yīng)用，另外遺傳算法在模糊規(guī)則，分類器獲取或者決策樹等各方面都有著廣泛的應(yīng)用，作為數(shù)據(jù)挖掘領(lǐng)域中一個重要的研究方向，遺傳算法模擬自然進(jìn)化者通用全局搜索算法，從而避免了搜索過程中的局部最優(yōu)解，用在規(guī)則發(fā)現(xiàn)方面有希望發(fā)現(xiàn)真正有用的規(guī)則。