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

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

中圖分類號：TV697 文獻標識碼：A 文章編號：1007-9599 （2012） 22-0000-02

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

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

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

2.1 模擬退火算法

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

2.2 遺傳算法

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

3 混合遺傳算法

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

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

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

3.2 遺傳模擬退火算法

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

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

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

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

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

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

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

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

參考文獻：

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

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

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