基于混合遺傳算法的數(shù)據(jù)挖掘

摘要：隨著數(shù)據(jù)庫(kù)應(yīng)用的不斷深化，數(shù)據(jù)庫(kù)的規(guī)模急劇膨脹，人們需要對(duì)這些數(shù)據(jù)進(jìn)行分析，從中發(fā)現(xiàn)有價(jià)值的信息。但是數(shù)據(jù)庫(kù)管理系統(tǒng)本身卻沒(méi)有提供有效的工具和方法來(lái)利用這些數(shù)據(jù)，因此數(shù)據(jù)挖掘成為當(dāng)今研究的熱點(diǎn)。本文即以混合遺傳算法為基礎(chǔ)對(duì)數(shù)據(jù)挖掘中的算法問(wèn)題進(jìn)行系統(tǒng)研究。

關(guān)鍵詞：數(shù)據(jù)挖掘；遺傳算法；模擬退火算法；混合遺傳算法

中圖分類(lèi)號(hào)：TV697 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 22-0000-02

1 什么是數(shù)據(jù)挖掘

數(shù)據(jù)挖掘（Data Mining），又稱(chēng)為數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)（Knowledge Discovery in Database，KDD），就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中，提取有效的、新穎的、潛在有用的、最終可理解的模式的非平凡過(guò)程，簡(jiǎn)單的說(shuō)，數(shù)據(jù)挖掘就是從大量數(shù)據(jù)中提取或“挖掘”知識(shí)。數(shù)據(jù)挖掘所得到的信息應(yīng)具有先前未知，有效和可實(shí)用三個(gè)特征。先前未知的信息是指該信息是預(yù)先未曾預(yù)料到的，既數(shù)據(jù)挖掘是要發(fā)現(xiàn)那些不能靠直覺(jué)發(fā)現(xiàn)的信息或知識(shí)，甚至是違背直覺(jué)的信息或知識(shí)，挖掘出的信息越是出乎意料，就可能越有價(jià)值。

2 數(shù)據(jù)挖掘中的基本算法

2.1 模擬退火算法

模擬退火算法的依據(jù)是固體物質(zhì)退火過(guò)程和組合優(yōu)化問(wèn)題之間的相似性。物質(zhì)在加熱的時(shí)候，粒子間的布朗運(yùn)動(dòng)增強(qiáng)，到達(dá)一定強(qiáng)度后，固體物質(zhì)轉(zhuǎn)化為液態(tài)，這個(gè)時(shí)候再進(jìn)行退火，粒子熱運(yùn)動(dòng)減弱，并逐漸趨于有序，最后達(dá)到穩(wěn)定。也就是說(shuō)，模擬退火沒(méi)有像局部搜索那樣每次都貪婪地尋找比現(xiàn)在好的點(diǎn)，目標(biāo)函數(shù)差一點(diǎn)的點(diǎn)也有可能接受進(jìn)來(lái)。隨著算法的執(zhí)行，系統(tǒng)溫度T逐漸降低，最后終止于某個(gè)低溫，在該溫度下，系統(tǒng)不再接受變化。 模擬退火的典型特征是除了接受目標(biāo)函數(shù)的改進(jìn)外，還接受一個(gè)衰減極限，當(dāng)T較大時(shí)，接受較大的衰減，當(dāng)T逐漸變小時(shí)，接受較小的衰減，當(dāng)T為0時(shí)，就不再接受衰減。這一特征意味著模擬退火與局部搜索相反，它能避開(kāi)局部極小，并且還保持了局部搜索的通用性和簡(jiǎn)單性。值得注意的是，當(dāng)T為0時(shí)，模擬退火就成為局部搜索的一個(gè)特例。

2.2 遺傳算法

歷史中，人們對(duì)生命進(jìn)化和延續(xù)的探索中得知：經(jīng)歷長(zhǎng)時(shí)間的生命進(jìn)化并生存下來(lái)的生物，沒(méi)有逃脫殘酷的“適者生存，不適者被淘汰”的生存規(guī)則，實(shí)際上，優(yōu)勝劣汰的歷史是對(duì)物種的優(yōu)化過(guò)程。在某環(huán)境下具有特殊先天優(yōu)勢(shì)的個(gè)體有比較強(qiáng)大的生存能力和繁衍能力，并占據(jù)其它生物個(gè)體生存空間，對(duì)其它生物個(gè)體來(lái)說(shuō)，存在威脅。隨社會(huì)的強(qiáng)大和人們對(duì)生命及延續(xù)過(guò)程的認(rèn)知不斷加深，進(jìn)而模仿自然進(jìn)化和繁衍方法來(lái)透析優(yōu)化問(wèn)題的可能。通過(guò)達(dá)爾文的生物進(jìn)化論來(lái)看，人們制造出生物進(jìn)化過(guò)程的計(jì)算模型，即遺傳算法。是人們摸索自然進(jìn)化過(guò)程的高技術(shù)。產(chǎn)生出一個(gè)代表性問(wèn)題，在此問(wèn)題的一個(gè)解集中隱藏著一個(gè)種群，遺傳算法便開(kāi)始被探索了，但一個(gè)種群是由基因編碼中某固定數(shù)目的個(gè)體而形成。每一個(gè)生物都是具有某種特征染色體實(shí)體。染色體是遺傳物質(zhì)的主載體，也是多基因的集合，基因型的解釋為它的內(nèi)部表現(xiàn)，基因型也是某相關(guān)基因的合成，它決定一個(gè)物體外表形態(tài)，比如黑色頭發(fā)是由染色體中某基因經(jīng)組合而決定的。因此，剛開(kāi)始需做編碼工作，即實(shí)現(xiàn)表現(xiàn)型到基因型的映射。因仿照基因編碼的程序很繁瑣，所以適當(dāng)進(jìn)行簡(jiǎn)化，比如二進(jìn)制編碼，初代種群出現(xiàn)后，遵循適者生存和優(yōu)勝劣汰的生存原則，逐代演化產(chǎn)生出越來(lái)越好的近似解，每一代中據(jù)問(wèn)題域中個(gè)體的適應(yīng)程度挑出個(gè)體，然后借助自然遺傳算子，完成個(gè)體組合交叉和個(gè)體變異。產(chǎn)生出代表新的解集的種群。此過(guò)程會(huì)使自然進(jìn)化種群比前代適應(yīng)能力更強(qiáng)，末代種群里最優(yōu)個(gè)體通過(guò)解碼，可當(dāng)作問(wèn)題近似最佳解碼。

3 混合遺傳算法

目前，對(duì)遺傳算法的研究主要集中在數(shù)學(xué)基礎(chǔ)、各環(huán)節(jié)的實(shí)現(xiàn)方式以及與其他算法的結(jié)合方面。在此，我們以遺傳算法與模擬退火算法相結(jié)合來(lái)研究。由于遺傳算法具有開(kāi)放式的結(jié)構(gòu)，與問(wèn)題的關(guān)聯(lián)性不大，很容易和模擬退火算法進(jìn)行結(jié)合，所以融合了模擬退火算法思想和遺傳算法思想的模擬退火遺傳算法（混合遺傳算法）成了目前改進(jìn)遺傳算法研究的一個(gè)重要方向。下面將著重介紹模擬退火遺傳算法里的混合遺傳算法的基礎(chǔ)思想及應(yīng)用。

3.1 混合遺傳算法的基本思想

理論上已經(jīng)證明，遺傳算法能從概率的意義上以隨機(jī)的方式尋求到問(wèn)的最優(yōu)解。但實(shí)踐證明遺傳算法在運(yùn)用的時(shí)也不是十全十美的，伴有部分難題，主要問(wèn)題為易產(chǎn)生早熟現(xiàn)象、區(qū)域查優(yōu)的性能底、運(yùn)行率較低等。雖然前面對(duì)遺傳算法做了一些改進(jìn)，但僅從遺傳算法自身還無(wú)法好的消除這些缺點(diǎn)。另一方面，梯度法、爬山法、模擬退火算法等優(yōu)化算法本身存在高效搜索功能。顯然，在遺傳算法的搜索過(guò)程中融合這些優(yōu)化算法的思想構(gòu)成一種混合遺傳算法，可以提高運(yùn)行效率和求解的質(zhì)量。

3.2 遺傳模擬退火算法

模擬退火遺傳算法是多種優(yōu)化算法。子算法遺傳算法和模擬退火策略，基于廣義的鄰域搜索算法構(gòu)造模擬退火遺傳算法的優(yōu)化策略，為提高優(yōu)化的時(shí)間性能，可以利用遺傳算法的并行抽樣過(guò)程來(lái)實(shí)現(xiàn)，同時(shí)，要采取方案避免出現(xiàn)“早熟”的收斂現(xiàn)象，這時(shí)我們可以用模擬退火算法控制算法的收斂性來(lái)實(shí)現(xiàn)，采用這一方法，能更進(jìn)一步提高算法的優(yōu)化性能。另一方面，要使變異概率達(dá)到自適應(yīng)變化的目的，這就需要對(duì)變異算子引入自適應(yīng)變異的思想，以此達(dá)到使算法脫離局部最優(yōu)點(diǎn)的變異的出現(xiàn)，加強(qiáng)算法的查詢(xún)性能。分析模擬退火遺傳算法與基本遺傳算法，兩者的總體運(yùn)行過(guò)程相似，在此不詳加說(shuō)明。

模擬退火算法新解法的產(chǎn)生和接受大致分為以下四個(gè)步驟：

一個(gè)產(chǎn)生函數(shù)剛開(kāi)始以一個(gè)當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解法；因方便后面的算法和接受，降低算法所用時(shí)間，一般會(huì)擇取當(dāng)前新解通過(guò)轉(zhuǎn)換就可以產(chǎn)生新解的方法，產(chǎn)生新解的轉(zhuǎn)換法決定當(dāng)前新解的空間結(jié)構(gòu)，因此其對(duì)冷卻進(jìn)度表的擇取受某程度影響。

計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。因目標(biāo)函數(shù)差是由變換成分產(chǎn)出，因此計(jì)算時(shí)按照增量計(jì)算。實(shí)際上比較其它計(jì)算方法，這是算取函數(shù)差最速度的辦法。

新解如被確認(rèn)接受可用新解替換當(dāng)前解，這僅需要把當(dāng)前解中對(duì)應(yīng)產(chǎn)生新解時(shí)的變動(dòng)成分加以實(shí)現(xiàn)，并且修整目標(biāo)函數(shù)值。這時(shí)當(dāng)前解實(shí)現(xiàn)了一次迭代。從而進(jìn)一步開(kāi)始實(shí)驗(yàn)。然而在當(dāng)新解確認(rèn)被舍棄時(shí)，可在前當(dāng)前解的基礎(chǔ)上進(jìn)一步實(shí)驗(yàn)。

初始值和模擬退火算法沒(méi)有關(guān)系，算法求得的解與初始解狀態(tài)S（是算法迭代的起點(diǎn)）無(wú)關(guān)；模擬退火算法具有漸近收斂性和并行性。

本文提出的混合遺傳算法結(jié)合了遺傳算法和模擬退火算法，一方面極大地降低了陷入局部最優(yōu)的可能性；另一方面大大加快了算法的收斂速度。還有其他的算法已被引入到遺傳算法中來(lái)，在此，就不再過(guò)多介紹。

優(yōu)化遺傳算法的最佳方法即把它同其它算法與相關(guān)理論知識(shí)的結(jié)合。 伴隨社會(huì)發(fā)展和先進(jìn)技術(shù)設(shè)備的引進(jìn)，人類(lèi)深入探索混合遺傳，但在探索遺傳算法這條道路上會(huì)有更多的理論和方法被揭曉。相信在不久的將來(lái)，遺傳算法和其它算法的結(jié)合，再加上更好的自身實(shí)現(xiàn)方式，最終使混合遺傳算法的優(yōu)化能力在質(zhì)上得到一個(gè)很大的提升。

參考文獻(xiàn)：

[1]http：//baike.baidu.com/view/7893.htm 2008年4月10日訪問(wèn)。

[2]http：//hi.baidu.com/cy120032/blog/item/635b1ff413e2b86addc4741f.html2008年4月16日訪問(wèn)。

[3]余建坤，張文彬，陸玉昌；《遺傳算法及其應(yīng)用》；云南民族學(xué)院學(xué)報(bào)（自然科學(xué)版），2002，11（4）；193-197。