基于遺傳機(jī)制的歸納學(xué)習(xí)算法研究.pdf

1、機(jī)器學(xué)習(xí)是人工智能的基礎(chǔ)理論之一。近年來(lái)，它越來(lái)越引起人們的重視，并成為人工智能研究的焦點(diǎn)，目前已有許多學(xué)習(xí)系統(tǒng)成功的應(yīng)用到自動(dòng)知識(shí)獲取、模式識(shí)別、智能控制等領(lǐng)域。歸納學(xué)習(xí)是機(jī)器學(xué)習(xí)理論中較為成熟的分支。知識(shí)獲取已公認(rèn)為專(zhuān)家系統(tǒng)發(fā)展的知識(shí)瓶頸，于是歸納學(xué)習(xí)方法的研究更加引起人們的重視。擴(kuò)張矩陣?yán)碚撌怯晌覈?guó)學(xué)者提出的AE類(lèi)規(guī)則學(xué)習(xí)算法，具有分類(lèi)精度高、知識(shí)表達(dá)力強(qiáng)，適合專(zhuān)家系統(tǒng)的自動(dòng)知識(shí)獲取的特點(diǎn)。在基于擴(kuò)張矩陣?yán)碚摰氖纠龑W(xué)習(xí)中，最短公式

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

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

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