【正文】 1s3=11011 729 1s4=10000 256 1　　 假設(shè)這一輪選擇 復(fù)制操作中，種群 S2中的4個(gè)染色體都被選中 ，則得到群體： s1’=11001（ 25） ,s2’=01100（ 12）s3’=11011（ 27） ,s4’=10000（ 16） 做交叉運(yùn)算，讓 s1’與 s2’， s3’與 s4’分別交換后 三 位基因，得 s1’’ =11100（ 28） ,s2’’ =01001（ 9）s3’’ =11000（ 24） ,s4’’ =10011（ 19） 這一輪仍然不會(huì)發(fā)生變異。 于是，得第三代種群 S3： s1=11100（ 28） , s2=01001（ 9） s3=11000（ 24） , s4=10011（ 19） 第三代種群 S3中各染色體的情況 染色體 適應(yīng)度 選擇概率 積累概率 估計(jì)的選中次數(shù)s1=11100 784 2s2=01001 81 0s3=11000 576 1s4=10011 361 1 設(shè)這一輪的選擇 復(fù)制結(jié)果為： s1’=11100（ 28） ,s2’=11100（ 28）s3’=11000（ 24） ,s4’=10011（ 19） 做交叉運(yùn)算，讓 s1’與 s4’， s2’與 s3’分別交換后 兩 位基因，得 s1’’=11111（ 31） ,s2’’=11100（ 28）s3’’=11000（ 24） ,s4’’=10000（ 16） 這一輪仍然不會(huì)發(fā)生變異。 于是，得第四代種群 S4： s1=11111（ 31） , s2=11100（ 28） s3=11000（ 24） , s4=10000（ 16） 　 顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體 s1=11111。于是， 遺傳 操作 終 止，將 染色體 “ 11111” 作 為 最 終結(jié) 果 輸 出?！　∪缓?，將染色體 “ 11111” 解碼為表現(xiàn)型，即得所求的最優(yōu)解： 31。 將 31代入函數(shù) y=x2中，即得原問題的解，即函數(shù) y=x2的最大值為 961。 YYy=x2 8131924 X第一代種群及其適應(yīng)度y=x2 12162527 XY第二代種群及其適應(yīng)度y=x2 9192428 XY第三代種群及其適應(yīng)度y=x2 16242831 X第四代種群及其適應(yīng)度旅行商問題（ TSP）的遺傳算法求解實(shí)例 已知 n個(gè)城市的地理位置（ x,y），求經(jīng)過所有城市，并回到出發(fā)城市且每個(gè)城市僅經(jīng)過一次的最短距離。 這是一個(gè) NP完全問題，其計(jì)算量為城市個(gè)數(shù)的指數(shù)量級(jí) ?，F(xiàn)用遺傳算法來解決這個(gè)問題。 編碼 31578910426每條路徑每條路徑 對(duì)應(yīng)對(duì)應(yīng) 一個(gè)一個(gè) 個(gè)體，個(gè)體形式地表示為個(gè)體，個(gè)體形式地表示為R={City_No|City_No互不重復(fù)互不重復(fù) }n， n為城市數(shù)。例如對(duì)為城市數(shù)。例如對(duì)于于 n=10的的 TSP問題，對(duì)其中一個(gè)個(gè)體問題，對(duì)其中一個(gè)個(gè)體它表示一條城市路徑它表示一條城市路徑31 5 7 8 910 4 2 6其中其中 ni表示個(gè)體中第表示個(gè)體中第 i位的城市編號(hào)，位的城市編號(hào)， n11=n1。適應(yīng)值為非負(fù)，且取值越大越好。適應(yīng)值為非負(fù)，且取值越大越好。 表示所有個(gè)體的路表示所有個(gè)體的路徑長度的總和徑長度的總和適應(yīng)值函數(shù) 每個(gè)個(gè)體代表一條可能的路徑。個(gè)體每個(gè)個(gè)體代表一條可能的路徑。個(gè)體 n的適應(yīng)值為：的適應(yīng)值為：其中其中 N為種群數(shù)，為種群數(shù)， Dn為為 沿個(gè)體標(biāo)示的城市序列的所經(jīng)過的沿個(gè)體標(biāo)示的城市序列的所經(jīng)過的距離距離 :交叉 隨機(jī)地從種群中選出要交叉的 兩個(gè)不同個(gè)體 ，隨機(jī)地選取一個(gè)交叉段。交叉段中兩個(gè)個(gè)體的對(duì)應(yīng)部分通過匹配換位實(shí)現(xiàn)交叉操作。對(duì)個(gè)體 A和 B：A＝ 984|567|13210B＝ 871|4103|2965交叉段 對(duì)個(gè)體 A，對(duì)交叉段中由 B換位來的數(shù)，如 3，在 A中其它位相同的數(shù)進(jìn)行反交換，即 4換為 5， 10換為 6， 3換為 7；對(duì)個(gè)體 B，相似處理，最后得到：A， ＝ 984|4103|1326B， ＝ 871|567|2965A，＝，＝ 9 8 5 |4 10 3| 1 7 2 6 B，＝，＝ 8 3 1 |5 6 7| 2 9 10 4變異 根據(jù)變異概率 Pe，隨機(jī)地從種群中選出 要變異 的個(gè)體，隨機(jī)地在該個(gè)體上選出變異兩個(gè)位置，然后兩個(gè)位置上的城市序號(hào)進(jìn)行交換。如：A=98456713210下劃線部分為要變異的兩個(gè)位置。變異為：A`=97456813210遺傳算法結(jié)果n 計(jì)算結(jié)果表明：n n個(gè)城市的最佳路徑接近一個(gè)外圈無交叉的環(huán)路。獲取知識(shí)的遺傳算法n 1980年， Smith采用遺傳算法研制了一種分類器 系統(tǒng)，這是遺傳算法在機(jī)器學(xué)習(xí)中的重要應(yīng)用系統(tǒng)。他使用單個(gè)字符串來表示一條規(guī)則。 n 分類器系統(tǒng)的規(guī)則形式如下：n IFconditionTHENaction是當(dāng)條件（ condition）滿足時(shí)，就可能采取行動(dòng)（ action）。分類器系統(tǒng)的規(guī)則采用 固定長度表示。這便于遺傳算子的處理。分類學(xué)習(xí)系統(tǒng)的結(jié)構(gòu)檢測器 消息表遺傳算法分類器信任分配算法測試表作用器客觀環(huán)境(1) 客觀環(huán)境信息通過分類器系統(tǒng)客觀環(huán)境信息通過分類器系統(tǒng)的檢測器（的檢測器（ Detector）被編碼）被編碼成有限長的消息（成有限長的消息（ Messages））(2)然后發(fā)往消息表；消息表中的然后發(fā)往消息表；消息表中的消息觸發(fā)位串規(guī)則（稱為分類消息觸發(fā)位串規(guī)則（稱為分類器），被觸發(fā)的分類器又向消器），被觸發(fā)的分類器又向消息表發(fā)消息，這些消息又有可息表發(fā)消息，這些消息又有可能觸發(fā)其它的分類器或引發(fā)一能觸發(fā)其它的分類器或引發(fā)一個(gè)行動(dòng)。個(gè)行動(dòng)。(3)通過執(zhí)行機(jī)構(gòu)（作用器通過執(zhí)行機(jī)構(gòu)（作用器 Effector）作用于客觀環(huán)境。）作用于客觀環(huán)境。n 1.檢測器 （ Detector）n 一條消息 Mi是一個(gè)二元組，其形式如下：Mi=[xi,yi]其中： i為消息號(hào)； x為條件部分，即訓(xùn)練例子的各特征編碼， y為結(jié)論部分，即訓(xùn)練例子的類別。例如： [(10001011),(1011)]是一條由一個(gè) 8位條件和 4位結(jié)論組成的消息。n 2.消息表（ MessageList）包含當(dāng)前所有的消息（訓(xùn)練例子集）。分類學(xué)習(xí)系統(tǒng)的結(jié)構(gòu)n 3.分類器（ Classifier）n 所獲得的規(guī)則中包含通配符 ，如： 10， 1110是一致的。n 規(guī)則集越小，系統(tǒng)的時(shí)間性能當(dāng)然越好。n 一個(gè)規(guī)則 Ci是一個(gè)三元組，形式如下：Ci=[Ui,Vi,fitnessi]其中， Ui是條件部分， 表示通配符； Vi是結(jié)論部分；n fitnessi是規(guī)則 i的適應(yīng)值，它又是一個(gè)二元組，其形式如下：fitnessi=[fit1,fit2]fit1,fit2分別表示在該規(guī)則覆蓋的范圍內(nèi)，與規(guī)則結(jié)論一致和不一致的消息 個(gè)數(shù) 。分類學(xué)習(xí)系統(tǒng)的結(jié)構(gòu)n 4.測試表（ TestList）n 由所有測試?yán)咏M成。一個(gè)測試?yán)?Ti也是一個(gè)同消息形式一樣的二元組，只是它的結(jié)論部分， yi表示未確定。n 當(dāng)執(zhí)行完精練分類器規(guī)則后，其結(jié)論部分 yi就被賦值成與消息Mi完全一樣形式，即 ，變成一條新的消息。n 5.作用器（ Effector）n 將測試的判別結(jié)果轉(zhuǎn)換成具體問題的真實(shí)的輸出值，并作用于環(huán)境。 分類學(xué)習(xí)系統(tǒng)的結(jié)構(gòu) n 1.信任分配算法n 實(shí)質(zhì)對(duì)各條規(guī)則作用于環(huán)境的有效性進(jìn)行評(píng)價(jià)，而本系統(tǒng)中的環(huán)境就是訓(xùn)練子集。n 將規(guī)則與消息表中的消息逐個(gè)匹配，根據(jù)匹配的成功與否，來修改規(guī)則的適應(yīng)值，其主要步驟如下：n （ 1）初始化規(guī)則的適應(yīng)值，即： fit1?0， fit2?0。n （ 2）從消息表 [M]中取出一條消息，與工作分類器 [WC]中的規(guī)則逐個(gè)進(jìn)行比較。n （ 3） IF 條件和結(jié)論均匹配， THEN fit1?fit1+1；n （ 4） IF 條件匹配，結(jié)論不匹配， THENfit2?fit2+1；n （ 5） IF 條件不匹配， THENfitness?fitness。 返回步驟 （ 2），直到 [M]中的消息全部取完。n 2.遺傳算法（ GeicAlgorithms）n 用來產(chǎn)生新的規(guī)則。利用一種交配策略，只允許同類（規(guī)則的結(jié)論部分相同）的規(guī)則進(jìn)行交叉。n 對(duì)同一結(jié)論的規(guī)則， 只允許 其條件部分進(jìn)化。假如規(guī)則的條件和結(jié)論同時(shí)進(jìn)化，就可能引起種群不收斂的情況產(chǎn)生。n 遺傳算法的主要步驟如下：n 根據(jù)分類器（規(guī)則）的適應(yīng)值的大小，從中選出幾對(duì)分類器。分類器實(shí)力越大，被選中的概率越大。n 對(duì)選出的分類器 ，利用 GA中的遺傳算子，產(chǎn)生其 “后代 ”n 用產(chǎn)生的 “后代 ”取代分類器中適應(yīng)值小者。 （ GCLS）及其應(yīng)用n 應(yīng)用說明n 這是一個(gè)學(xué)習(xí)識(shí)別腦出血和腦血栓兩種疾病的診斷規(guī)則的應(yīng)用實(shí)例， 這個(gè)問題實(shí)際上是從大量已知患者病例（訓(xùn)練例子集）中找到這兩類病的識(shí)別規(guī)則。n 實(shí)際上只有兩種類別： ； n 為了作出判斷，應(yīng)當(dāng)考慮如下幾個(gè)方面的特征（屬性）；n （ 1） 病人的既往史 ，包括 （有 01，無 00）； （有 01，無 00）；n （ 2） 起病方式 （快