摘要 摘要 遺傳算法是一種抽象于生物體的進(jìn)化過程，通過全面模擬自然選擇和遺傳機(jī)制， 形成的全局優(yōu)化搜索算法。在進(jìn)化過程中，性能好的個體以更高的概率被選擇，主 要通過交叉和變異操作，形成新一代性能更好的個體。進(jìn)化終止時的最優(yōu)個體通常 被認(rèn)為是問題的最終解。遺傳算法已經(jīng)被廣泛應(yīng)用于多種優(yōu)化問題，機(jī)器學(xué)習(xí)，模 式識別等領(lǐng)域。 本文利用遺傳算法來解決符號學(xué)習(xí)問題，即從符號值數(shù)據(jù)集中抽取歸納出 i f - t h e n 規(guī)則。本文采用的是傳統(tǒng)的p i t t s b u r 曲方法，即一條染色體表示一個規(guī)則的 集合，種群中的染色體互相競爭，進(jìn)化終止時的最優(yōu)染色體即最優(yōu)規(guī)則集。該方法 的代表性系統(tǒng)是g a s s i s t 系統(tǒng)，本文對該系統(tǒng)進(jìn)行了如下進(jìn)一步研究。 為了提高規(guī)則集合的泛化能力和系統(tǒng)效率，本文提出了一種新的種群初始化方 法，引入了適應(yīng)值尺度變換；在g a s s i s t 系統(tǒng)發(fā)展過程中，等級選擇算子被拋棄， 本文對它進(jìn)行了改進(jìn)，重新引入到系統(tǒng)中；提出了一種新的g a 迭代終止標(biāo)準(zhǔn)；對 適應(yīng)度函數(shù)的不合理之處進(jìn)行了修正，最后對適應(yīng)度函數(shù)進(jìn)行了進(jìn)一步的改進(jìn)，即 在評價規(guī)則集合的整體性能時，考慮到單條規(guī)則的性能，實(shí)驗(yàn)證明，改進(jìn)后系統(tǒng)的 性能和效率都得到了提高。 關(guān)鍵詞遺傳算法符號學(xué)習(xí)種群初始化終止標(biāo)準(zhǔn)適應(yīng)度函數(shù) a b s t r a c t a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) i sag l o b a lo p t i m i z a t i o ns e a r c ha l g o r i m mm a ti n s p i r e db y n a t u r a lc v o l v i n gp r o c e s s i ti m i t a t e st h en a t u r a ls e l e c t i o na n dg e n e t i cm e c h a n i s m b e t t e r i n d i v i d u a l sa r es e l e c t e dw i t hh i g h e rp r o b a b i l i t yi nt h ei t e r a t i n gp r o c e s s t 1 1 r o u g hg e n e t i c r e c o m b i n a t i o na n dm u t a t i o np r o c e s s e s ，n e wi n d i v i d u a l sw i l lb eg e n e r a t e dt of o mn e w g e n e r a t i o n s w h e nt h ei t e r a t i n gp r o c c s si st e m i n a t e d ，t h eb e s ti n d i v i d u a l i sc o n s i d e r e dt o b et h e e x p e c t e d s o l u t i o n g e n e t i ca l g o r i m mh a sb e e n w i d e l y u s e di nv 撕o u s o p t i m i z a t i o np r o b l 鋤s ，m a c h i n e1 e a m i n ga n dp a t t 鋤r e c o g l l i t i o n i nt h i sp a p e r w eu s et h et r a d i t i o n a lp i t t s b u i 苫hm e t h o dt os o l v es y m b o l i cl e a m i n g p r o b l e m s ， w h i c hi n d u c e sr u l e s 行o ms y m b o l i cd a t a s e t s d u r i n gm es o l v i n gp r o c e s s ，雅 i n d i v i d u a lr e p r e s e n t sag r o u po f1 1 l l e sa n di n d i v i d u a l si nt h ep o p u l a t i o nc o m p e t et 0 s u r v i v e t h eb e s ti n d i v i d u a li so b t a i n e da sm ed e s i r e ds 0 1 u t i o nw h e nt h ei t e r a t i o np r o c e s s i st e r 耵f i i n a t e d o u rr e s e a r c hi sb a s e do ng a s s i s t ，w h i c hi sar 印f e s e n t a t i v es y s t e mo f p i t t s b u r g hm e t h o d t h em a i nc o n 塒b u t i o n so ft h i sw o r ka r ea sf o l l o w s ： i no r d e rt oi m p r o v em eg e n e r a l i z a t i o nc a p a c i t yo ft h ee x t r a c t e dr u l es e t ，an e w p o p u l a t i o ni n i t i a l i z a t i o nm e t h o di sa p p l i e da n df i t n e s ss c a l i n gi su s e dt op r o m o t et h e p o p u l a t i o n sc o n v e r g e n c e t h ei m p r o v e dh i e r a r c h i c a ls e l e c t i o no p e r a t o ri s c o m b i n e d w i t ht h em d l - b a s e df i t n e s s 如n c t i o nt oc o n t r o lt l l eb l o a te f 詫c t m o r e o v an e ws t o p c r i t e r i o ni sp r o p o s e dt om a k et h es y s t e ms t o pp r o p e r l y f u r t h e m o r e ，w ea l s op o i n to u t t h ei 1 1 r a t i o n a l i t yo ft h ef i t n e s s 如n c t i o no ft h eo r i g i n a ls y s t e ma n dt h e nm o d i 母i t f i n a l l y ， t h i sr e s e a r c hi n c o 叩o r a t e st h ep e r f o m a n c eo fas i n g l em l ei ne v a l u a t i n gt h ep e r f o 徹a n c e o far u l es e t t h ee x p e “m e n t a l r e s u l t ss h o wt h a tt h ep r o p o s e ds y s t e mi si m p r o v e di nb o t h g e n e r a l i z a t i o nc a p a c i t ya n de f f i c i e n c y k e yw o r d s ：g e n e t i ca l g o r i t h m ；s y m b o l i cl e a m i n g ；p o p u l a t i o ni n i t i a l i z a t i o n ；s t o p c r i t e r i o n ；f i t n e s sf u n c t i o n i l 河北大學(xué) 學(xué)位論文獨(dú)創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作 及取得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文 中不包含其他人已經(jīng)發(fā)表或撰寫的研究成果，也不包含為獲得河北大學(xué)或其他教 育機(jī)構(gòu)的學(xué)位或證書所使用過的材料。與我一同工作的同志對本研究所做的任何 貢獻(xiàn)均已在論文中作了明確的說明并表示了致謝。 作者簽名：一蘭蚤斜叁 學(xué)位論文使用授權(quán)聲明 本人完全了解河北大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留 并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。 學(xué)校可以公布論文的全部或部分內(nèi)容，可以采用影印、縮印或其他復(fù)制手段保存 論文。 本學(xué)位論文屬于 1 、保密口，在年月日解密后適用本授權(quán)聲明。 2 、不保密黽。 ( 請?jiān)谝陨舷鄳?yīng)方格內(nèi)打“妒) 作者簽名： 三魚盤9 差。 日期：地匿年二月衛(wèi)日 導(dǎo)師簽名： 保護(hù)知識產(chǎn)權(quán)聲明 本人為申請河北大學(xué)學(xué)位所提交的題目為環(huán)i l j 訊棗必私撳薦琴蚴麥規(guī)刪 的學(xué)位論文，是我個人在導(dǎo)師蓉寥指導(dǎo)并與導(dǎo)師合作下取得的研究成果，研 究工作及取得的研究成果是在河北大學(xué)所提供的研究經(jīng)費(fèi)及導(dǎo)師的研究經(jīng)費(fèi)資 助下完成的。本人完全了解并嚴(yán)格遵守中華人民共和國為保護(hù)知識產(chǎn)權(quán)所制定的 各項(xiàng)法律、行政法規(guī)以及河北大學(xué)的相關(guān)規(guī)定。 本人聲明如下：本論文的成果歸河北大學(xué)所有，未經(jīng)征得指導(dǎo)教師和河北大 學(xué)的書面同意和授權(quán)，本人保證不以任何形式公開和傳播科研成果和科研工作內(nèi) 容。如果違反本聲明，本人愿意承擔(dān)相應(yīng)法律責(zé)任。 聲明人：蘭魚到叁 日期：叢年月旦日 作者簽名： 導(dǎo)師簽名： 日期：盟年月生日 日期：2 鯉墨年上月衛(wèi)日 第l 章緒論 第1 章緒論 1 1 研究背景與意義 h h o l l a n d 教授提出了具有開創(chuàng)意義的遺傳算法理論和方法。遺傳算法抽象于生物 體的進(jìn)化過程，是一種通過全面模擬自然選擇和遺傳機(jī)制而形成的自適應(yīng)全局優(yōu)化概率 搜索算法，有很好的健壯性。 符號學(xué)習(xí)是指從符號值數(shù)據(jù)集中抽取歸納出一般規(guī)則。符號值數(shù)據(jù)集的特征為：數(shù) 據(jù)是離散的，無序的，數(shù)據(jù)之間是無運(yùn)算關(guān)系的，屬性的取值是有限的。連續(xù)型數(shù)據(jù)集 中的連續(xù)型屬性可以通過離散化算法轉(zhuǎn)變?yōu)榉栃?，因此，任何一個學(xué)習(xí)問題都可以轉(zhuǎn) 化為符號學(xué)習(xí)問題，對符號學(xué)習(xí)問題的研究有重要意義。本文主要研究利用遺傳算法來 解決符號學(xué)習(xí)問題，因此，本文的研究很有意義。和其它的符號學(xué)習(xí)系統(tǒng)相比，遺傳算 法對大多數(shù)數(shù)據(jù)集都有比較好的性能，即適合于解決更廣泛的問題，但是效率比較低， 還需要進(jìn)一步改進(jìn)。利用遺傳算法提取符號值分類規(guī)則的代表性系統(tǒng)是g a s s i s t 系統(tǒng)【l 】。 g a s s i s t 系統(tǒng)是g a b i l 系統(tǒng)【2 卅的改進(jìn)版本，它們均采用的是傳統(tǒng)的p i t t s b u 嘈1 方法， 即一條染色體表示一個規(guī)則的集合，種群中的染色體互相競爭，進(jìn)化終止時的最優(yōu)染色 體即最優(yōu)規(guī)則集。g a s s i s t 系統(tǒng)的主要貢獻(xiàn)為：染色體的長度得到了控制，即規(guī)則集中 含有的規(guī)則數(shù)變少；系統(tǒng)的效率得到了提高；提高了規(guī)則集的泛化能力；能處理連續(xù)型 屬性。但是，相對于其它的符號學(xué)習(xí)算法如擴(kuò)張矩陣( f c v ) f 5 】，基于關(guān)聯(lián)規(guī)則的分類算 法c m a r 【6 1 ，貝葉斯( b a y e s ) 【7 】，c 4 5 【8 1 等，該系統(tǒng)仍然存在系統(tǒng)的效率較低，泛化能力 差的不足。因此，本文在g a s s i s t 系統(tǒng)的基礎(chǔ)上進(jìn)行了進(jìn)一步研究。 1 2 本課題的國內(nèi)外發(fā)展現(xiàn)狀 符號學(xué)習(xí)問題也屬于分類問題，目前，利用遺傳算法來解決分類問題，即進(jìn)化學(xué)習(xí)， 常用的方法有四種：p i t t s b u 啦方法，m i c h i g a n 方法，n e r a t i v er u l el e a m i n g 方法和y u a n 方法。 p i t t s b u 轡1 方法最早由s m i m ，s 提出【9 1 0 1 ，該方法采用了標(biāo)準(zhǔn)遺傳算法的基本流程， 很容易理解。一條染色體表示一組規(guī)則的析取集合，每條規(guī)則的長度固定且相等，但染 色體的長度是可變的，每條染色體含有的規(guī)則數(shù)目不一定相等。種群中的染色體互相競 爭，最后次迭代產(chǎn)生的最優(yōu)染色體就是我們需要的分類規(guī)則集。代表性系統(tǒng)有三個： 1 河北人學(xué)f ：學(xué)碩+ 學(xué)位論文 g i l 系統(tǒng)，g a b i l 系統(tǒng)，和g a s s i s t 系統(tǒng)。j a n i k o w 等提出了g i l 系統(tǒng)【i l _ 1 2 1 ，該系統(tǒng)使 用了豐富的遺傳算子，這些遺傳算子是在更高層即語義層次對染色體進(jìn)行操作，同時該 系統(tǒng)的適應(yīng)度函數(shù)考慮了染色體的精度和復(fù)雜度兩個因素。但是，該系統(tǒng)涉及到大量參 數(shù)的設(shè)定問題，難以操作。同一時期，d e j o n g & s p e a f s 提出了g a b i l 系統(tǒng)【2 卅，該系統(tǒng) 是p i t t s b w 醢方法的第一個基本的有代表性的系統(tǒng)，有很重要的意義，但存在染色體的 長度過長，系統(tǒng)的運(yùn)行時間長和泛化能力差等問題。為了解決g a b i l 系統(tǒng)存在的問題， 達(dá)到控制染色體長度，提高系統(tǒng)的泛化能力和執(zhí)行效率的目的，j b a c a r d i t 在自己的博 士論文中總結(jié)了他對g a b i l 系統(tǒng)所做的一系列改進(jìn)工作，稱改進(jìn)后的系統(tǒng)為g a s s i s t 系統(tǒng)【l 】。采用的主要技術(shù)為：默認(rèn)規(guī)則機(jī)制【1 3 】，提高泛化能力和系統(tǒng)效率的窗口技術(shù)【1 4 】 和控制b l o a t 效應(yīng)，提高泛化能力的技術(shù)【1 5 】。2 0 0 6 年，j b a e a r d i t 對g a s s i s t 系統(tǒng)進(jìn)行了 完善，提出了一種多親靈活交叉算子s x 【i6 1 ，該算子不同于以前的交叉算子，它不產(chǎn)生 新規(guī)則，而是從若干條父代個體含有的規(guī)則中，選出一個精度最高且規(guī)則數(shù)目最少的規(guī) 則子集，作為產(chǎn)生的新個體。j b a c a r d i t 還提出使用一種類似b a g 西n g 的技術(shù)【1 7 1 ，來提 高規(guī)則集的測試精度。但是與其它的符號學(xué)習(xí)方法相比，g a s s i s t 系統(tǒng)的效率比較低， 因此，本文對該系統(tǒng)進(jìn)行了進(jìn)一步研究。 h o l l a n d 提出了m i c h i g a n 方法，該方法一條染色體表示一條規(guī)則，規(guī)則之間互相合 作，整個種群表示用來分類的規(guī)則集【1 8 j9 】。通常使用基于加強(qiáng)學(xué)習(xí)的方法來獎勵好的規(guī) 則，懲罰壞的規(guī)則。在m i c h i g a n 方法中，g a 并不是關(guān)鍵壞節(jié)，只是在需要的時候用來 發(fā)現(xiàn)新規(guī)則，m i c h i g a n 方法的代表性系統(tǒng)是x c s 系統(tǒng)f 2 0 。2 2 1 。但是與g a s s i s t 系統(tǒng)相比， 該系統(tǒng)容易發(fā)生過度擬合現(xiàn)象。 v c ：n 嘶n i 在s i a 系統(tǒng)中使用了i t e r a t i v er u l el e 鋤i n g 方法【2 3 】，它采用分治策略得到 規(guī)則集，每條規(guī)則由遺傳算法的一次迭代過程產(chǎn)生。一條染色體表示一條規(guī)則，每次迭 代得到的最優(yōu)染色體的串聯(lián)，就是我們需要的分類規(guī)則集。a g u i l a r 等將i t e r a t i v er u l e l e a m i n g 方法應(yīng)用在h i d e r 系統(tǒng)中【2 4 1 。該方法每次評價種群時，都要分類未被覆蓋的 全部樣例，效率不高。 y u f e iy u a n 等利用遺傳算法來產(chǎn)生模糊分類規(guī)則 2 5 】，該方法同樣適合于解決符號 學(xué)習(xí)問題。 第1 章緒論 1 3 本課題研究的主要內(nèi)容 本文在g a s s i s t 系統(tǒng)的基礎(chǔ)上，做進(jìn)一步研究，旨在提高規(guī)則集的泛化能力和系統(tǒng) 的效率。為了提高初始種群的性能，考慮產(chǎn)生初始種群時，利用部分訓(xùn)練集的信息；為 了保持種群中染色體之間的競爭性，促進(jìn)種群的收斂，考慮計(jì)算了染色體的適應(yīng)度值后， 引入了適應(yīng)值尺度變換；g a s s i s t 系統(tǒng)也是一個發(fā)展的過程，在它的發(fā)展過程中，等級 選擇算子被基于m d l 的適應(yīng)度函數(shù)所替代。本文仔細(xì)地對該算子的優(yōu)缺點(diǎn)進(jìn)行了分析， 對該算子進(jìn)行了改進(jìn)，考慮將其重新引入到系統(tǒng)中來。g a s s i s t 系統(tǒng)采用的是精英選擇 策略，設(shè)定最大繁衍代數(shù)為終止標(biāo)準(zhǔn)，實(shí)驗(yàn)過程中發(fā)現(xiàn)，最大繁衍代數(shù)的確定對系統(tǒng)的 性能影響很大，且該參數(shù)很難確定。因此，本文考慮提出一種新的終止標(biāo)準(zhǔn)，當(dāng)種群的 性能比較穩(wěn)定時，終止迭代過程。 基于m d l 原則的適應(yīng)度函數(shù)的提出，是g a s s i s t 系統(tǒng)的主要貢獻(xiàn)之一，它能有效 地控制染色體的長度，提高系統(tǒng)效率，而且還能提高系統(tǒng)的泛化能力。j b a c a 訂i t 認(rèn)為 規(guī)則集編碼位串中l(wèi) 的個數(shù)越多，規(guī)則集的泛化能力越高。但是，有時基于m d l 適應(yīng) 度函數(shù)的計(jì)算公式與該理論矛盾，因此，我們考慮對公式進(jìn)行修正。g a s s i s t 系統(tǒng)的一 條染色體對應(yīng)一個有序的規(guī)則集，它被看作一個決策列表，對未知樣例進(jìn)行預(yù)測時，匹 配樣例的第一條規(guī)則被用來分類，因此規(guī)則集中每條規(guī)則所起的作用不同，而基于m d l 適應(yīng)度函數(shù)僅對這一規(guī)則集合的整體性能進(jìn)行了評價。本文考慮對規(guī)則集的整體性能進(jìn) 行評價時，也結(jié)合考慮單條規(guī)則的性能。 1 4 本文組織 全文的組織結(jié)構(gòu)概括如下： 第l 章緒論。 第2 章遺傳算法介紹。本章首先通過一個數(shù)值計(jì)算的例子對遺傳算法的基本概念和 流程進(jìn)行了簡要地描述。然后通過一個簡單的數(shù)據(jù)集，把利用遺傳算法提取 符號值規(guī)則的過程進(jìn)行了較為詳細(xì)地描述。 第3 章利用遺傳算法提取符號值分類規(guī)則算法。利用遺傳算法提取符號值分類規(guī)則 有四種方法，即p i t t s b u r 曲方法，m i c h i g a i l 方法，i t e r a t i v er u l el e 鋤i n g 方法 和j a n 方法。本章對這四種方法及其各自的代表性系統(tǒng)進(jìn)行了介紹。其中， 重點(diǎn)介紹了g a b i l 系統(tǒng)和g a s s i s t 系統(tǒng)。 洞：l 匕人學(xué)?。捍T十學(xué)何論文 第4 章利用遺傳算法提取符號值分類規(guī)則算法改進(jìn)。為了提高規(guī)則集的泛化能力和 系統(tǒng)效率，提出了一種新的種群初始化方法，引入適應(yīng)值尺度變換，對等級選 擇算子進(jìn)行了改進(jìn)，將其重新引入到系統(tǒng)中來，還提出了一種新的g a 停止 標(biāo)準(zhǔn)。對基于m d l 的適應(yīng)度函數(shù)進(jìn)行了修正，同時評價規(guī)則集的整體性能 時，兼顧考慮單條規(guī)則的性能。 第5 章總結(jié)與展望。對本文所做工作及創(chuàng)新點(diǎn)進(jìn)行了總結(jié)，并對后續(xù)開展的工作進(jìn) 行了展望。 第2 章遺傳算法介紹 第2 章遺傳算法介紹 2 1 遺傳算法簡介 1 9 7 5 年，美國密西根大學(xué)的h h o l l a n d 教授提出了具有開創(chuàng)意義的遺傳算法理論和 方法。遺傳算法抽象于生物體的進(jìn)化過程，是一種通過全面模擬自然選擇和遺傳機(jī)制， 形成的具有“生成+ 檢驗(yàn)”特征的搜索算法【2 6 】。遺傳算法以編碼空間代替問題的參數(shù)空 間，以適應(yīng)度函數(shù)為評價依據(jù)，以編碼群體為進(jìn)化基礎(chǔ)，通過對群體中個體位串進(jìn)行選 擇，交叉和變異等遺傳操作，形成一次迭代過程。這一過程模仿了自然界的“優(yōu)勝劣汰， 適者生存”的原則，性能好的染色體以更高的概率被選擇，并通過交叉和變異操作，產(chǎn) 生新一代適應(yīng)性更好的群體，群體中的個體性能不斷提高，逐漸接近最優(yōu)解，最終達(dá)到 求解問題的目的。遺傳算法被廣泛應(yīng)用于多種優(yōu)化問題，自適應(yīng)控制，規(guī)劃設(shè)計(jì)，圖像 處理，模式識別和機(jī)器學(xué)習(xí)等領(lǐng)域。 遺傳算法包含了五個基本要素：參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、 遺傳操作的設(shè)計(jì)和參數(shù)的設(shè)定( 包括種群規(guī)模、選擇概率、交叉概率等) 。其運(yùn)行過程 為一個典型的迭代過程【2 引，如圖2 1 所示： 圖2 1 遺傳算法的基本流程框圖 下面以一個函數(shù)求最大值的問題為例，來簡要的描述遺傳算法的概念和操作流程。 假定求函數(shù)f ( x ，y ) = x 2 + y 2 的最大值。其中石【o ，3 l 】，y 【o ，3 l 】。下面我們?nèi)斯つM遺傳 河北大學(xué)1 ：學(xué)碩十學(xué)位論文 算法的運(yùn)行過程： 令編碼 遺傳算法操作的對象是表示一條染色體的位串，所以必須把變量x 和變量y 編碼，這 里采用二進(jìn)制編碼。因?yàn)閤 和y 介于。到3 1 之間，可用長度為5 的二進(jìn)制串來表示，比如： x = 5 ，) ，= 9 用二進(jìn)制編碼可表示為x = o o l 0 1 ，y ：0 1 0 0 1 。 產(chǎn)生初始種群 遺傳操作是針對群體進(jìn)行的，所以需要產(chǎn)生一個由若干個初始解組成的初始群體。 本例中種群規(guī)模設(shè)為4 ，即隨機(jī)生成4 條染色體。 比如：1 1 1 1 0 0 0 1 0 00 0 0 1 1 l o l l l 0 1 0 1 1 0 0 l o o0 1 1 0 1 0 1 1 1 0 奪評價群體 進(jìn)化過程中，遺傳算法通過適應(yīng)度值來判定染色體的優(yōu)劣，因此，需要計(jì)算種群中 每條染色體的適應(yīng)值。在本例中，目標(biāo)函數(shù)是平方和的形式，取值總是大于等于零，并 且優(yōu)化目標(biāo)是求函數(shù)的最大值，因此，可以直接把目標(biāo)函數(shù)值當(dāng)作染色體的適應(yīng)度值。 奪選擇操作 表2 1 選擇操作 適應(yīng)占百選擇 編號初始種群 x y 選擇結(jié)果 度值 分比 次數(shù) l1 1 1 1 0 0 0 1 0 03 049 1 6o 4 6 820 0 0 l l l o l l l 2 0 0 0 1 1 1 0 l l l 3 2 3 5 3 8o 2 7 411 1 1 l o 0 0 1 0 0 30 1 0 11 0 0 1 0 02 341 3 70 0 7 0oo l l o l o l ll o 4 0 1 1 0 1 0 1 1 1 0 1 31 43 6 5 o 1 8 7l l l1 1 0 0 0 1 0 0 總和 1 9 5 6l4 均值 4 8 9o 2 5i 最人值 9 1 62 該操作是依據(jù)了進(jìn)化論中“適者生存的原則。把當(dāng)前群體中適應(yīng)度值高的染色體， 按照某種方法直接遺傳到下一代，要求適應(yīng)度值高的個體以更大的概率被選擇。本例中， 采用輪盤選擇。首先計(jì)算群體中所有個體適應(yīng)度值的總和，再計(jì)算每個個體的適應(yīng)度值 所占的比例，即相應(yīng)的選擇概率，則全部概率值之和為1 ，最后產(chǎn)生o 到l 之間的隨機(jī)數(shù)， 用來確定個體被選擇的次數(shù)。 觀察表2 1 ，可以發(fā)現(xiàn)，對種群進(jìn)行了選擇操作后，適應(yīng)度值高的個體以更高的概 一6 第2 章遺傳算法介紹 率被選擇，且經(jīng)過一次選擇后，種群的整體性能提高了。 交叉操作 該操作是最主要的遺傳操作，可以產(chǎn)生新個體。在本例中，我們使用兩點(diǎn)交叉，操 作過程為：首先在種群中隨機(jī)選擇兩條染色體，然后隨機(jī)指定兩個交叉位置，最后交換 兩條染色體中間的部分。 表2 2 交義操作 配對個交義適應(yīng) 編號選擇結(jié)果一交義結(jié)果 x y 體點(diǎn)度值 l 0 0 0 l 1 1 0 1 1 1 】 1 20 0 0 1 0 0 0 1 0 0242 0 21 1 ll o o o l o o 】1 24 1 0l l l l l l o l l l3 l2 31 4 9 0 3 0 l l 【0 1 0 l l 】l o 3 - 43 _ 4 0 “1 0 0 0 l l o1 462 3 2 4 1 1l 【1 0 0 0 l 】0 0 3 8 l1 1 0 1 0 1 l o o 2 91 2 9 8 5 總和 2 7 2 7 均值 6 8 1 7 5 最人值 1 4 9 0 觀察表2 1 和表2 2 ，可以發(fā)現(xiàn)經(jīng)過了交叉操作后，種群的平均適應(yīng)度值提高了，而 且最優(yōu)染色體的性能也提高了。 變異操作 該操作也可以產(chǎn)生新個體，它以較小的概率改進(jìn)染色體位串中的某個基因位，即把 0 改為1 ，或者把1 改為o 。 觀察表2 3 ，可以發(fā)現(xiàn)，第二條染色體就是問題的最優(yōu)解。 在本例的模擬進(jìn)化中，只經(jīng)過一次迭代過程，就找到了問題的最優(yōu)解，在實(shí)際的操 作過程中，很可能經(jīng)歷多次迭代過程，隨著進(jìn)化過程的進(jìn)行，種群的整體性能會逐漸提 高，最優(yōu)染色體的性能會逐漸接近問題的最優(yōu)解。 表2 - 3 變異操作 編號交義結(jié)果變異點(diǎn)變異結(jié)果 x y 適應(yīng)度值 10 0 0 l o 0 0 1 0 011 0 0 1 0 0 0 1 0 01 843 4 0 21 1 1 1 1 1 0 l l l71 1 1 1 1 1 1 1 1 13 l3 l1 9 2 2 30 1 1 1 0 0 0 1 1 090 1 11 0 0 0 1 0 01 4 42 1 2 4l l l o l o l l 0 04l l l l l o l l 0 03 11 2l 1 0 5 總和 3 5 7 9 均值 8 9 4 7 5 最人值 1 9 2 2 河北大學(xué)一【：學(xué)碩十學(xué)位論文 2 2 一個利用遺傳算法提取符號值分類規(guī)則的例子 表2 _ 4p l a y l 朗n i s 的訓(xùn)緣樣例 d a y o u t l o o k t 啪p e r a t u r eh u m i d i t y w i n d p l a y t e n n i s l s u n n y h o t h i 曲 w e a kn o 2 s u n n y h o t h i 曲 s t r o n g n o 3o v e r c a s th o t h i g l l w e a k y e s 4 r a i n m i l d h i g l l w e a ky e s 5r a i nc o o in o 眥a lw e a ky e s 6r a i nc o o ln o m a l s t r o n g n o 7o v e r c a s tc o o ln o m a l s l r o n g y e s 8 s u n n y m i l d h i g l l w e a kn 0 9 s u l l i l y c o o ln o 瑚a lw e a l cy e s 1 0r a i nm i l dn o 珊a lw e a ky e s l l s u n n y m i l dn o m a l s t r o n g y e s 1 2o v e r c a s tm i l d h i 曲s t r o n g y e s 1 3 o v e r c a s th o tn o 衄a lw e a k y e s 1 4r a i nm i l d h i 曲s t r o n g n o 表2 5 參數(shù)設(shè)置 參數(shù)設(shè)置取值 種群規(guī)模 1 5 聯(lián)賽規(guī)模 3 最人繁衍代數(shù) 2 0 0 交叉概率o 6 變異概率 o ，6 染色體中初始規(guī)則數(shù) 5 編碼中出現(xiàn)l 的概率 o 7 5 為了演示遺傳算法從符號型數(shù)據(jù)集中提取規(guī)則的過程，考慮表2 4 中的訓(xùn)練數(shù)據(jù)所 代表的學(xué)習(xí)任務(wù)。這里，目標(biāo)屬性p l a 姍i s 對于不同的星期六上午具有y e s 和n o 兩 個值，我們將根據(jù)其它屬性來預(yù)測這個目標(biāo)屬性值。下面對利用g a 提取符號值規(guī)則的 過程進(jìn)行簡要的描述、 第一步：確定問題參數(shù)。 為了演示方便，種群規(guī)模設(shè)的比較小，詳細(xì)參數(shù)設(shè)置見表2 5 。 第二步：對1 4 個訓(xùn)練樣例進(jìn)行編碼。 使用二進(jìn)制編碼，比如屬性o u t l o o k ，有三個取值s u r u l y ，o v e r c a s t ，r a i n ，編碼時使 用長度為3 的位串對其進(jìn)行描述，可以取某個值對應(yīng)位設(shè)為l ，比如o u t l o o k 取值為 r 第2 章遺傳算法介紹 o v e f c a s t ，就把第2 位設(shè)為l ，其它兩位設(shè)為o ，即編碼為0 1 0 。按照這種方式，對樣 例的條件屬性進(jìn)行編碼，決策屬性有兩個取值，我們用l 位來表示，取l 表示n o ，取0 表示y 醯。按照這種方式。則表2 - 4 中1 4 個樣例的編碼如下： l 0 0 1 0 0 1 0 1 0 1il 0 0 1 0 0 l o o l ll0 1 0 1 0 0 1 0 1 0 0 lo o l 0 1 0 1 0 l o oio o l 0 0 1 0 1 1 0 0 o o l o o l 0 1 0 1 ll0 1 0 0 0 1 0 l o l o il o 0 0 1 0 1 0 1 0 li1 0 0 0 0 1 0 1 1 0 0i0 0 l o l 0 0 l l o o l 0 0 0 l 0 0 1 0 1 0l0 1 0 0 1 0 l 0 0 1 0 l0 1 0 1 0 0 0 l l o oio o l 0 1 0 1 0 0 1 1 第三步：產(chǎn)生初始種群。 本例中，一條染色體表示一組規(guī)則的析取集合，初始種群隨機(jī)產(chǎn)生。比如：隨機(jī)產(chǎn) 生下面1 5 條染色體，每條染色體含有5 條規(guī)則。 0 1 1 1 l o o l l l li1 1 l o o l l l l l l10 1 1 1 1 1 1 1 0 1 ll1 1 1 1 1 l l l l 0 1il o l 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0l1 1 1 0 1 1 1 1 1 1 0i1 1 1 1 1 1 1 1 1 1 0i1 0 1 0 1 1 1 1 1 1 0l1 1 1 1 1 l o l l l o “0 1 1 1 1 1 1 l ll 1 0 1 l l l l l o l o l l l l l l 0 1 1 1i1 0 1 1 l 1 0 1 1 1 1i1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 li1 0 0 1 1 1 1 0 1 1 l1 1 1 1 1 l l l o l ll0 1 1 1 1 1 1 0 1 0 1i1 1 1 1 1 1 1 0 0 1 1 第四步：評價群體 在本例中，適應(yīng)度函數(shù)只考慮訓(xùn)練精度，忽略染色體的復(fù)雜度等因素3 1 ，染色體i 的適應(yīng)度計(jì)算形式為： 砌p 鼬( f ) = ( c d ，坨c t 尺以胞( f ) ) 2( 1 ) 表2 石初始種群性能 染色體準(zhǔn)確率適應(yīng)度值 lo 2 8 5 70 0 8 1 6 2 0 5 7 1 40 3 2 6 5 3o 4 2 8 6 0 1 8 3 7 40 4 2 8 60 1 8 3 7 5o 4 2 8 60 1 8 3 7 6o 5 7 1 40 3 2 6 5 70 5 7 1 40 3 2 6 5 80 4 2 8 6o 1 8 3 7 9 o 2 8 5 7o 0 8 1 6 l o o 5 7 1 4o 3 2 6 5 llo 5 7 1 40 3 2 6 5 1 2o 4 2 8 60 1 8 3 7 1 3o 5 7 1 40 3 2 6 5 1 4o 5 7 1 4o 3 2 6 5 1 50 7 1 4 30 5 1 0 2 河北大學(xué)丁學(xué)碩十學(xué)位論文 評價種群的過程如下： 把訓(xùn)練樣例分成兩份，第一次迭代使用第l 份樣例，第2 次迭代使用第2 份，按照 這種方法輪流使用這兩份樣例，最后一次迭代使用全部的樣例。預(yù)測樣例時，規(guī)則集中 第一條匹配樣例的規(guī)則被用來分類。下面給出了計(jì)算初始種群中第一條染色體適應(yīng)度值 的過程： 染色體：0 1 1 1 1 0 0 l l l l1 1 l 0 0 1 1 1 1 1 ll0 1 1 1 1 1 l 1 0 1 1l1 1 1 1 1 1 1 1 1 0 li1 0 1 0 1 0 0 1 1 0 l 。 第一次迭代使用第一份樣例，即前7 個樣例，這些樣例的編碼為： 1 0 0 1 0 0 1 0 1 0 1l1 0 0 l 0 0 1 0 0 1 110 l o l o o l 0 1 0 0 o o l 0 1 0 1 0 1 0 00 0 l 0 0 1 0 1 1 0 0i0 0 1 0 0 1 0 1 0 1 l1 0 1 0 0 0 1 0 1 0 l o 第一條樣例：第四條規(guī)則與之匹配，預(yù)測為第1 類，預(yù)測正確。 第二條樣例：五條規(guī)則都不與之匹配，指定樣例類別為默認(rèn)類別，即第o 類，預(yù)測 錯誤。 第三條樣例：第四條規(guī)則與之匹配，預(yù)測為第l 類，預(yù)測錯誤。 第四條樣例：第四條規(guī)則與之匹配，預(yù)測為第l 類，預(yù)測錯誤。 第五條樣例：第二條規(guī)則與之匹配，預(yù)測為第l 類，預(yù)測錯誤。 第六條樣例：第二條規(guī)則與之匹配，預(yù)測為第1 類，預(yù)測j 下確。 第七條樣例：第二條規(guī)則與之匹配，預(yù)測為第l 類，預(yù)測錯誤。 所以第一條染色體的訓(xùn)練準(zhǔn)確率為：2 7 = o 2 8 5 7 ，適應(yīng)度值為：0 2 8 5 7 幸o 2 8 5 7 = 0 0 8 1 6 表2 7 聯(lián)賽選擇過程 參加聯(lián)賽個體勝者 6 ，1 1 ，1 26 4 ，7 ，8 7 1 0 ，2 ，5 l o 1 ，1 4 ，9l 3 ，1 3 ，1 3 1 3 1 5 ，1 5 ，l 1 5 2 ，4 ，77 5 ，3 ，85 1 0 ，1 3 ，l o l o 5 ，4 ，7 7 6 ，9 ，1 4 6 1 2 ，1 l ，6 “ 1 5 ，1 4 ，l l 1 5 1 2 ，l ，9 l 6 ，1 5 ，1 2 1 5 第2 章遺傳算法介紹 第五步：聯(lián)賽選擇。 聯(lián)賽選擇算子的局部搜索能力比較強(qiáng)，因而系統(tǒng)采用了該算子。操作思想：從群體 中任意選擇一定數(shù)目的個體( 稱為聯(lián)賽規(guī)模) ，其中適應(yīng)度值最高的個體保存到下一代， 這一過程反復(fù)進(jìn)行，直到保存到下一代的個體數(shù)目達(dá)到群體規(guī)模。 此時產(chǎn)生的種群對應(yīng)初始代中的染色體為：6 ，7 ，l o ，1 ，1 3 ，1 5 ，7 ，5 ，1 0 ，7 ， 6 ，1 l ，1 5 ，l ，1 5 。對于一些比較好的染色體以更高的概率被選擇到下一代，體現(xiàn)了 “適者生存 的原則。 表2 8 交叉過程 染色體對 p o i n t l lp o i i l t l 2p o i l l t 2 lp o i n t 2 2 d ld 2 l o 891 2 3 l 4 591 3 52 94 71 83 673 1 4 62 45 23 55 228 1 1 42 54 92 53 835 注：染色體從1 開始索引，變異位從0 丌始索引。 第六步：兩點(diǎn)交叉。 對經(jīng)過聯(lián)賽選擇后產(chǎn)生的種群做交叉操作，交叉過程見表2 8 ，其中p o i n t l l 和 p o i n t l 2 指第l 條染色體的兩個交叉點(diǎn)的位置，p o i n t 2 1 和p o i n t 2 2 指第2 條染色體的兩個 交叉點(diǎn)的位置，d l ( d 2 ) 表示第一( 二) 個交叉點(diǎn)到它左側(cè)第一條規(guī)則邊界的距離。 第七步：變異操作。 表2 9 列出了此次變異過程中發(fā)生變異的染色體及其發(fā)生變異的具體位置。 表2 9 變異過程 染色體123456891 01 11 31 5 變異位置 1 4 7 3 24 41 22 61 9 5 3 6 41 44 32 9 注：染色體從1 開始索引，變異位從o 開始索引。 此時初始種群中的染色體經(jīng)過了種群評價，聯(lián)賽選擇，交叉和變異四種操作，得到 一個中間種群，如下： 1 1 1 1 1 1 0 1 1 l o1 1 l 0 0 1 1 1 0 1 0il 0 0 1 1 1 1 1 0 1 0l0 1 1 1 1 1 1 1 1 0 0f1 1 1 1 1 1 1 0 1 1 0 1 l o o l l 0 0 1 l l 1 1 0 1 1 0 1 0 0 1 1i1 1 1 1 0 0 1 1 0 1 1l1 1 1 0 0 1 0 1 1 l lll l l o l l 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 ll o l l l l l l l o l 1 1 1 1 1 1 0 1 0 “i1 1 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 l o 0 0 1 1 i 河北大學(xué)t 學(xué)碩+ 學(xué)位論文 1 1 1 1 1 1 1 1 1 1 0i1 1 l o l l l l l l oi1 1 l l l l l l o l o0 1 l l l l l l l 0 0i0 1 1 1 1 1 1 1 1 1 0i1 1 l l l l 0 1 1 1 0 可以看出，此時各條染色體含有的規(guī)則數(shù)不相等。 第九步：評價中間種群。 詳細(xì)過程見上述第四步。同樣的道理，適應(yīng)度函數(shù)的計(jì)算公式為，訓(xùn)練精度的平方。 只考慮到了染色體的訓(xùn)練精度，并沒有考慮到染色體的長度( 盡管此時種群中染色體長 度不再相等，即它們含有的規(guī)則數(shù)目不再相同) 。此時中間種群的性能見表2 1 0 。比較 表2 6 和表2 1 0 ，可以看出中間種群的整體性能提高了。 表2 1 0 中間群體性能 染色體準(zhǔn)確率適應(yīng)度值 lo 5 7 1 40 3 2 6 5 2o 5 7 1 4o 3 2 6 5 30 5 7 1 40 3 2 6 5 4 o 5 7 1 4 0 - 3 2 6 5 50 5 7 1 40 3 2 6 5 60 5 7 1 40 3 2 6 5 70 5 7 1 4o 3 2 6 5 80 5 7 1 4 0 - 3 2 6 5 9o 4 2 8 60 1 8 3 7 1 0o 5 7 1 4o 3 2 6 5 1 10 5 7 1 4o 3 2 6 5 1 20 4 2 8 60 1 8 3 7 1 3o 5 7 1 4o 3 2 6 5 1 4o 7 1 4 3o 5 1 0 2 1 5o 5 7 1 4o 3 2 6 5 第十步種群替代過程。 采用精英策略，即種群替代時，保留舊代最好的染色體。 中間代最差染色體是1 1 l l l l 0 1 1 1 0l1 1 l o o l l l o l 01 0 0 1 1 1 1 1 1 1 01 0 1 0 1 1 1 0 1 l o ，準(zhǔn)確 率為o 4 2 8 6 ，適應(yīng)度值為：o 1 8 3 7 。 舊代最好染色體： l o o o l 0 0 1 1 1 0 1 1 1 1 0 1 1 0 1 l o o 1 1 1 1 1 1 1 1 0 1 0 0 i 0 1 1 1 1 1 1 1 0 1 2 第2 章遺傳算法介紹 1 1 1 1 0 1 0 0 1 1 1 0 ，準(zhǔn)確率為o 7 1 4 3 ，適應(yīng)度值為：o 5 1 0 2 。 用舊代最好的染色體替換中間代最差染色體，產(chǎn)生新一代。 如果當(dāng)前代達(dá)到了最大繁衍代數(shù)，對種群中的最好染色體進(jìn)行解碼操作，得到最優(yōu) 規(guī)則集，算法終止，否則重復(fù)第五到第十步。算法終止時得到的最好染色體為： 1 0 0 1 1 1 1 0 1 1 1io o l l “1 1 0 1 1 。它的準(zhǔn)確率為1 ，適應(yīng)度值為1 。對應(yīng)的規(guī)則集合如下： 1 ) i f ( c h j t l o o k = s u 皿y ) a n d ( t c 棚p e r a t i l r e = h 0 t o rm i l do rc 0 0 1 ) 鋤d ( h u m i d i t y = h i g h ) a l l d ( w i n d = w e a l ( o rs 吶n 曲 t h e l l p l a y l h n i s = n o 2 )i f ( o u t l o o k = r 。a i n ) a n d ( 1 伽p e 聯(lián)i t u r e = h o to rm i l do rc 0 0 1 ) 觚d ( h u m i d i t y = h i g l lo rn o 咖a 1 ) a 1 1 d ( w i n d = s 仃o n 曲 t h e np l a y l h n i s = n o 河北大學(xué)t 學(xué)碩+ 學(xué)位論文 第3 章利用遺傳算法提取符號值分類規(guī)則算法 3 1p i t t s b u 唱h 方法 p i t t s b w 曲方法采用的是標(biāo)準(zhǔn)遺傳算法的流程，一條染色體表示一組規(guī)則的析取集 合，每條規(guī)則的長度固定且相等，但染色體的長度是可變的，每條染色體含有的規(guī)則數(shù) 目不一定相等。種群中的染色體互相競爭，最后一次迭代產(chǎn)生的最優(yōu)染色體就是我們需 要的分類規(guī)則集。這種方法的代表性系統(tǒng)有三個：g a b i l 系統(tǒng)【2 卅，g i l 系統(tǒng)【l l - 1 2 1 ， g a s s i s t 系統(tǒng)【1 1 。 3 1 1g a b i l 系統(tǒng) 1 9 9 1 年d e j o n g & s p e a r s 提出了g a b i l 系統(tǒng)，在g a b i l 系統(tǒng)中，一條染色體對應(yīng) 于一組i f t h e l l 規(guī)則的析取集合。i f t h e l l 規(guī)則的二進(jìn)制編碼方法如下： 首先描述單個屬性的值約束。串的長度等于屬性的取值個數(shù)，串中每位對應(yīng)一個可 能值，若為1 ，表示屬性可以取對應(yīng)的值；取o ，表示屬性不可以取對應(yīng)的值。 多個屬性約束的合取表示為對應(yīng)位串的連接。 例如：我們有三個條件屬性a 、b 、c ，目標(biāo)屬性為d ，屬性a 的取值為a l ，a 2 ，a 3 ， 屬性b 的取值為b i ，b 2 ，屬性c 的取值為c i ，c 2 ，c 3 ，c 4 ，目標(biāo)屬性d 的取值為o 或1 。 則規(guī)則i f a = a lo ra 2a 1 1 db = b lo r b 2a n dc = c lt h e l ld = o 可表示為1 1 0 1 ll o 0 0 1 0 。 g a b i l 系統(tǒng)的選擇算子為輪盤選擇，變異算子為基本的變異算子，交叉算子有些 特殊，采用的是基于個體的交叉操作，種群中的個體任意配對，對每對染色體，隨機(jī)產(chǎn) 生一個o 到l 之問的數(shù)，如果小于交叉概率p 。，則這對染色體進(jìn)行交叉。為了適應(yīng)編碼 規(guī)則集合的位串長度可變性，要求交叉點(diǎn)在規(guī)則內(nèi)部的位置必須相同，具體操作為： 在第一個雙親串上隨機(jī)選取兩個交叉點(diǎn)。令d l ( d 2 ) 表示第一( 二) 個交