基于遺傳機制的歸納學習算法研究.pdf

1、機器學習是人工智能的基礎理論之一。近年來，它越來越引起人們的重視，并成為人工智能研究的焦點，目前已有許多學習系統(tǒng)成功的應用到自動知識獲取、模式識別、智能控制等領域。歸納學習是機器學習理論中較為成熟的分支。知識獲取已公認為專家系統(tǒng)發(fā)展的知識瓶頸，于是歸納學習方法的研究更加引起人們的重視。擴張矩陣理論是由我國學者提出的AE類規(guī)則學習算法，具有分類精度高、知識表達力強，適合專家系統(tǒng)的自動知識獲取的特點。在基于擴張矩陣理論的示例學習中，最短公式

2、問題、最優(yōu)覆蓋問題、最優(yōu)特種子集問題都已經(jīng)被證明是NP難度問題，求解這些問題一般是采用各種啟發(fā)式方法來尋求問題的近似解，這表明示例學習和自動知識獲取的困難性。而本文研究的集合覆蓋問題就是解決擴張矩陣的一種行之有效的辦法。
　　遺傳算法(GeneticAlgorithm簡稱GA)是20世紀七十年代由美國密切根大學JohnHolland教授為研究自然與人工系統(tǒng)的自適應行為而提出的一種算法，后經(jīng)其學生KennethDeJong、Davi

3、dE．Goldberg等人的改進推廣得以廣泛應用于各類優(yōu)化問題。遺傳算法作為一種全新的優(yōu)化搜索算法，與傳統(tǒng)的優(yōu)化算法相比，遺傳算法具有適應性廣、抗干擾性強、魯棒性強以及不受搜索空間限制性條件約束等顯著的特點。廣泛應用于自動控制、計算機科學、機器人學、模式識別和神經(jīng)網(wǎng)絡等領域。
　　本文首先簡要介紹了遺傳算法和集合覆蓋問題，然后詳細討論了遺傳算法相關的理論，包括遺傳算法的起源和搜索策略；遺傳算法的基本理論；遺傳算法的收斂性分析；遺傳

4、算法的改進方法。集合覆蓋問題是NP難度問題，執(zhí)行時間隨著問題規(guī)模的增大而急劇增大，遺傳算法對于解決NP難度問題非常有效。本文將遺傳算法應用到集合覆蓋中，提出了一種啟發(fā)式算法。通過用染色體來表示集合中的覆蓋情況，針對染色體進行啟發(fā)式修改,隨著在種群中隨著進化，通過合理的選取遺傳參數(shù)，能較快的收斂到最優(yōu)解。計算結果顯示應用本算法，對于小規(guī)模的集合覆蓋問題，可以產(chǎn)生最優(yōu)解，對于大規(guī)模的集合覆蓋問題，可以高效的產(chǎn)生較優(yōu)解。在本文的最后,詳細地介