高級(jí)人工智能15進(jìn)化計(jì)算

1、2022/7/111第十五章 進(jìn)化計(jì)算 2022/7/112內(nèi) 容15.1 概述15.2 進(jìn)化系統(tǒng)理論的形式模型15.3 達(dá)爾文進(jìn)化算法15.4 遺傳算法15.5 遺傳算法的理論基礎(chǔ)15.6 遺傳算法的改進(jìn)15.7 遺傳機(jī)器學(xué)習(xí)分類器系統(tǒng)15.8 桶鏈算法15.9 規(guī)則發(fā)現(xiàn)系統(tǒng)15.10 進(jìn)化策略15.11 進(jìn)化規(guī)劃2022/7/11315.1 概述 進(jìn)化計(jì)算是通過(guò)模擬自然界中生物進(jìn)化機(jī)制進(jìn)行搜索的一種算法。2022/7/114發(fā)展歷史進(jìn)化計(jì)算的研究起源于20世紀(jì)50年代。1965年，Holland首次提出了人工遺傳操作的重要性，并把這些應(yīng)用于自然系統(tǒng)和人工系統(tǒng)中。大約在同一時(shí)期：Rechen

2、berg和Schwefel提出了進(jìn)化策略。Fogel提出了進(jìn)化規(guī)劃。2022/7/115發(fā)展歷史 1967年，Bagley在他的論文中首次提出了遺傳算法這一術(shù)語(yǔ)，并討論了遺傳算法在自動(dòng)博弈中的應(yīng)用。1970年，Cavicchio把遺傳算法應(yīng)用于模式識(shí)別中。第一個(gè)把遺傳算法應(yīng)用于函數(shù)優(yōu)化的是Hollstien。 2022/7/116發(fā)展歷史1975年是遺傳算法研究的歷史上十分重要的一年。這一年，Holland出版了他的著名專著自然系統(tǒng)和人工系統(tǒng)的適應(yīng)性該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對(duì)遺傳算法的理論研究和發(fā)展極為重要的模式理論（schemata theory），該理論首次確認(rèn)了

3、結(jié)構(gòu)重組遺傳操作對(duì)于獲得隱并行性的重要性。同年，DeJong完成了他的重要論文遺傳自適應(yīng)系統(tǒng)的行為分析。他在該論文中所做的研究工作可看作是遺傳算法發(fā)展過(guò)程中的一個(gè)里程碑，這是因?yàn)樗袶olland的模式理論與他的計(jì)算使用結(jié)合起來(lái)。 2022/7/117發(fā)展歷史1989 Goldberg對(duì)遺傳算法從理論上，方法上和應(yīng)用上作了系統(tǒng)的總結(jié)。1990年，Koza提出了遺傳程序設(shè)計(jì)（Genetic Programming）的概念。（用于搜索解決特定問(wèn)題的最適計(jì)算機(jī)程序）2022/7/118遺傳算法與自然進(jìn)化的比較自然界染色體基因等位基因(allele)染色體位置(locus)基因型(genotype)表

4、型(phenotype)遺傳算法字符串字符,特征特征值字符串位置結(jié)構(gòu)參數(shù)集,譯碼結(jié)構(gòu)2022/7/119新達(dá)爾文五進(jìn)化理論的主要論點(diǎn)個(gè)體是基本的選擇目標(biāo);隨機(jī)過(guò)程在進(jìn)化中起重大作用, 遺傳變異大部分是偶然現(xiàn)象;基因型變異大部分是重組的產(chǎn)物, 特別是突變;逐漸進(jìn)化可能與表型不連續(xù)有關(guān);不是所有表型變化都是自然選擇的必然結(jié)果;進(jìn)化是在適應(yīng)中變化的, 形式多樣, 不僅是基因的變化;選擇是概率型的, 而不是決定型的。2022/7/1110進(jìn)化計(jì)算的三大主流板塊Holland提出的遺傳算法(Genetic Algorithm)。Rechenberg和Schwefel提出的進(jìn)化策略(Evolutionar

5、y Strategies)。Fogel提出的進(jìn)化規(guī)劃(Evolutionary Programming)，又稱為進(jìn)化程序設(shè)計(jì)。本章將著重介紹遺傳算法，對(duì)進(jìn)化策略和進(jìn)化規(guī)劃只作簡(jiǎn)單介紹。2022/7/111115.2 進(jìn)化系統(tǒng)理論的形式模型 進(jìn)化在個(gè)體群體中起作用。瓦鋌頓(Waddington)指出基因型和表型之間關(guān)系的重要性(Waddington 1974)。群體禁止異構(gòu)環(huán)境。但是“后生環(huán)境”是多維空間。表型是基因型和環(huán)境的產(chǎn)物。然后表型通過(guò)異構(gòu)“選擇環(huán)境發(fā)生作用。注意，這種多維選擇環(huán)境與后生環(huán)境空間是不同的?，F(xiàn)在，適應(yīng)性是表型空間和選擇環(huán)境空間的產(chǎn)物。它經(jīng)常被取作一維，表示多少子孫對(duì)下一代作

6、出貢獻(xiàn)。 基于這種想法，莫楞貝(Muhlenbein) 和肯德曼(Kindermann)提出了一種稱為進(jìn)化系統(tǒng)理論的形式模型(Muhlenbein 1989)。 2022/7/1112 進(jìn)化系統(tǒng)理論的形式模型進(jìn)化的主要過(guò)程后生環(huán)境遺傳操作符選擇環(huán)境gp2022/7/1113進(jìn)化系統(tǒng)理論的形式模型 其中，g 是基因型 p 是表型。 基因gi的可能值稱為等位基因。在門德爾(Mendel)遺傳學(xué)中，假設(shè)每個(gè)基因有有限數(shù)的等位基因。2022/7/1114進(jìn)化系統(tǒng)理論的形式模型這個(gè)變換函數(shù)給出了模型，說(shuō)明表型的發(fā)展是通過(guò)基因與環(huán)境的交互作用。變換過(guò)程是高度非線性的。2022/7/1115進(jìn)化系統(tǒng)理論的形

7、式模型質(zhì)量函數(shù)q給出了具體選擇環(huán)境ESi下表型的質(zhì)量，其定義如下：質(zhì)量定義適應(yīng)度，用于達(dá)爾文選擇。至今已有三種具體范例的通用模型，即 門德爾遺傳學(xué) 遺傳生態(tài)學(xué) 進(jìn)化配子2022/7/1116 門德爾遺傳學(xué)在門德爾遺傳學(xué)中，基因型被詳細(xì)模型化，而表型和環(huán)境幾乎被忽略。在遺傳生態(tài)學(xué)中恰好相反。進(jìn)化配子論是從社會(huì)生物學(xué)導(dǎo)出的模型。 首先讓我們討論門德爾遺傳學(xué)的選擇模型。為了簡(jiǎn)單起見，我們假設(shè)一個(gè)基因具有n 等位基因a1,an。 二倍基因型以元組(ai,aj)為特征。 我們定義 pi,j 為總?cè)后w中基因型(ai,aj) 的頻度。假設(shè)基因型與表型相等。質(zhì)量函數(shù)給每個(gè)表型賦值。 q(ai,aj) = qi

8、,j qi,j 可以被解釋為出生率減去死亡率 2022/7/1117 門德爾遺傳學(xué)假設(shè) pi,j是下一代表型(ai,aj) 的頻度。然后達(dá)爾文選擇根據(jù)選擇方程調(diào)整表型的分布: 是群體的平均適應(yīng)度。2022/7/1118 門德爾遺傳學(xué)設(shè) pi 是群體中等位基因的頻率。如果 pi,j = pi pj那么，我們得到在 GS中的一個(gè)選擇方程為 2022/7/1119 門德爾遺傳學(xué)這個(gè)離散的選擇方程可以用連續(xù)方程近似: 如果 qi,j = qj,i, 那么2022/7/1120 門德爾遺傳學(xué)這個(gè)方程很容易被證明:這個(gè)結(jié)果稱作菲希爾(Fisher)基本定理。它說(shuō)明平均適應(yīng)度隨適應(yīng)度的差別呈正比例增加。實(shí)際

9、上，全部可能的基因型僅有一部分實(shí)現(xiàn)。這就是遺傳操縱子探索基因型空間的任務(wù)，其個(gè)體數(shù)目相當(dāng)小。這些操縱子是群體遺傳變異性的來(lái)源。最重要的操縱子是突變和重組。2022/7/112115.3 達(dá)爾文進(jìn)化算法根據(jù)定量遺傳學(xué)，達(dá)爾文進(jìn)化算法采用簡(jiǎn)單的突變/選擇動(dòng)力學(xué)。達(dá)爾文算法的一般形式可以描述如下： 是一代的雙親數(shù)目， 為子孫數(shù)目。整數(shù) 稱作“混雜”數(shù)。如果兩個(gè)雙親混合他們的基因，則 = 2。僅 是最好的個(gè)體才允許產(chǎn)生子孫。逗號(hào)表示雙親們沒(méi)有選擇，加號(hào)表示雙親有選擇。 2022/7/112215.3 達(dá)爾文進(jìn)化算法建立原始種體。通過(guò)突變建立子孫。選擇：返回到步驟(1)。2022/7/1123 遺傳算法

10、思想來(lái)源于生物進(jìn)化過(guò)程, 它是基于進(jìn)化過(guò)程中的信息遺傳機(jī)制和優(yōu)勝劣汰的自然選擇原則的搜索算法(以字符串表示狀態(tài)空間)。遺傳算法用概率搜索過(guò)程在該狀態(tài)空間中搜索，產(chǎn)生新的樣本。15.4 遺傳算法2022/7/1124遺傳算法的特點(diǎn)特點(diǎn)：通用魯棒次優(yōu)解、滿意解遺傳算法能解決的問(wèn)題：優(yōu)化NP完全NP難高度復(fù)雜的非線性問(wèn)題2022/7/1125遺傳算法遺傳算法先將搜索結(jié)構(gòu)編碼為字符串形式, 每個(gè)字符串結(jié)構(gòu)被稱為個(gè)體。然后對(duì)一組字符串結(jié)構(gòu)(被稱為一個(gè)群體)進(jìn)行循環(huán)操作。每次循環(huán)被稱作一代,包括一個(gè)保存字符串中較優(yōu)結(jié)構(gòu)的過(guò)程和一個(gè)有結(jié)構(gòu)的、隨機(jī)的字符串間的信息交換過(guò)程。類似于自然進(jìn)化，遺傳算法通過(guò)作用于染

11、色體上的基因?qū)ふ液玫娜旧w來(lái)求解問(wèn)題。2022/7/1126 遺傳算法與自然界相似，遺傳算法對(duì)求解問(wèn)題的本身一無(wú)所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)值來(lái)選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)。在遺傳算法中，位字符串扮演染色體的作用，單個(gè)位扮演了基因的作用，隨機(jī)產(chǎn)生一個(gè)體字符串的初始群體，每個(gè)個(gè)體給予一個(gè)數(shù)值評(píng)價(jià)，稱為適應(yīng)度，取消低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加操作。常用的遺傳算子有復(fù)制、雜交、變異和反轉(zhuǎn)。2022/7/1127遺傳算法與傳統(tǒng)優(yōu)化算法的主要不同遺傳算法不是直接作用在參變量集上, 而是利用參變量集的某種編碼;遺傳算法不是從單個(gè)點(diǎn), 而是在群

12、體中從一個(gè)點(diǎn)開始搜索;遺傳算法利用適應(yīng)值信息, 無(wú)需導(dǎo)數(shù)或其它輔助信息;遺傳算法利用概率轉(zhuǎn)移規(guī)則, 而非確定性規(guī)則。2022/7/1128遺傳算法的準(zhǔn)備工作確定表示方案;確定適應(yīng)值的度量;確定控制該算法的參數(shù)和變量;確定怎樣指定結(jié)果及程序運(yùn)行結(jié)束的標(biāo)準(zhǔn)。2022/7/1129基本遺傳算法基本遺傳算法(Simple Genetic Algorithm:SGA)又稱為簡(jiǎn)單遺傳算法，只使用選擇算子、交叉算子和變異算子這三種基本的遺傳算子。其遺傳操作簡(jiǎn)單、容易理解，是其它遺傳算法的雛形和基礎(chǔ)?；具z傳算法的構(gòu)成要素：1、染色體編碼方法：首先必須對(duì)問(wèn)題的解空間進(jìn)行編碼，使之能用遺傳算法進(jìn)行操作。較常用的

13、是二進(jìn)制編碼方法，現(xiàn)在使用非二進(jìn)制編碼的也逐漸增多。2、適應(yīng)度函數(shù)（fitness function，又稱為適應(yīng)值適值函數(shù)）用來(lái)評(píng)價(jià)一個(gè)染色體的好壞。2022/7/1130基本遺傳算法的構(gòu)成要素3、遺傳算子 選擇算子(selection) ：又稱為復(fù)制算子。按照某種策略從父代中挑選個(gè)體進(jìn)入下一代，如使用比例選擇、輪盤式選擇。 交叉算子(crossover)：又稱為雜交算子。將從群體中選擇的兩個(gè)個(gè)體，按照某種策略使兩個(gè)個(gè)體相互交換部分染色體，從而形成兩個(gè)新的個(gè)體。如使用單點(diǎn)一致交叉。 變異算子(mutation)：按照一定的概率（一般較?。?，改變?nèi)旧w中某些基因的值。2022/7/1131雜交操

14、作舉例10220201No OffspringPt. of interchangeCrossoverParentsOffspring1110#0#1#0111#0001#11#010#1000#00#110#01#10#100100100#011161711110#11#0001#0#0001#11#00#11#00#110#01#10#000#01111#01#10#2022/7/1132變異操作簡(jiǎn)單的變異操作過(guò)程如下:每個(gè)位置的字符變量都有一個(gè)變異概率, 各位置互相獨(dú)立。通過(guò)隨機(jī)過(guò)程選擇發(fā)生變異的位置：產(chǎn)生一個(gè)新結(jié)構(gòu) , 其中 是從對(duì)應(yīng)位置 的字符變量的值域中隨機(jī)選擇的一個(gè)取值。 可以同樣

15、得到。2022/7/1133反轉(zhuǎn)操作簡(jiǎn)單反轉(zhuǎn)操作的步驟如下:從當(dāng)前群體中隨機(jī)選擇一個(gè)結(jié)構(gòu)從中隨機(jī)選擇兩個(gè)數(shù)i和j, 并定義 i = mini,j, j=maxi,j;顛倒a中位置i、j之間的部分, 產(chǎn)生新的結(jié)構(gòu)2022/7/1134基本遺傳算法的構(gòu)成要素4、運(yùn)行參數(shù)N：群體大小，即群體中包含的個(gè)體的數(shù)量。T：遺傳算法終止的進(jìn)化代數(shù)。Pc：交叉概率，一般取為 0.40.99。Pm：變異概率，一般取為 0.00010.1 。2022/7/1135基本遺傳算法隨機(jī)產(chǎn)生一個(gè)由固定長(zhǎng)度字符串組成的初始群體;對(duì)于字符串群體，迭代地執(zhí)行下述步驟，直到選種標(biāo)準(zhǔn)被滿足為止：計(jì)算群體中的每個(gè)個(gè)體字符串的適應(yīng)值;應(yīng)

16、用下述三種操作(至少前兩種)來(lái)產(chǎn)生新的群體:復(fù)制: 把現(xiàn)有的個(gè)體字符串復(fù)制到新的群體中。雜交: 通過(guò)遺傳重組隨機(jī)選擇兩個(gè)現(xiàn)有的子字符串, 產(chǎn)生新的字符串。變異: 將現(xiàn)有字符串中某一位的字符隨機(jī)變異。把在后代中出現(xiàn)的最高適應(yīng)值的個(gè)體字符串指定為遺傳算法運(yùn)行的結(jié)果。這一結(jié)果可以是問(wèn)題的解(或近似解)。2022/7/1136基本遺傳算法流程圖GEN=0概率地選擇遺傳操作隨機(jī)創(chuàng)建初始群體計(jì)算群體中每個(gè)個(gè)體的適應(yīng)值i:=0顯示結(jié)果結(jié)束GEN:=GEN+1是是否（轉(zhuǎn)下頁(yè)）i=N?GEN=M？12022/7/1137概率地選擇遺傳操作根據(jù)適應(yīng)值選擇一個(gè)個(gè)體完成交叉i:=i+1i:=i+1復(fù)制個(gè)體p(r)選擇

17、（接上頁(yè)）基于適應(yīng)值選擇兩個(gè)個(gè)體把新的兩個(gè)孩子加到群體中p(c)交叉變異p(m)把新的孩子加入到群體中完成變異根據(jù)適應(yīng)值選擇一個(gè)個(gè)體把變異后個(gè)體加入到群體中12022/7/1138輪盤式選擇首先計(jì)算每個(gè)個(gè)體 i 被選中的概率然后根據(jù)概率的大小將將圓盤分為 n個(gè)扇形，每個(gè)扇形的大小為 。選擇時(shí)轉(zhuǎn)動(dòng)輪盤，參考點(diǎn)r落到扇形i則選擇個(gè)體i 。.p1p2pir2022/7/1139單點(diǎn)一致交叉首先以概率pc從種群中隨機(jī)地選擇兩個(gè)個(gè)體p1、p2。在1, 2, . . . ,l內(nèi)隨機(jī)選擇一個(gè)數(shù)i,作為交叉的位置，稱為交叉點(diǎn)。然后將兩個(gè)個(gè)體交叉點(diǎn)后面的部分交換。例如： 0110 101100 0110 011

18、001 1100 011001 1100 1011002022/7/1140一致變異以概率pm對(duì)種群中所有個(gè)體的每一位進(jìn)行變異。對(duì)于個(gè)體pi的第j位，在0,1的范圍內(nèi)隨機(jī)地生成一個(gè)數(shù)r, 如果 r pm , 則對(duì)第j位取反，否則保持第j位不變。2022/7/1141遺傳算法舉例問(wèn)題：求（1）編碼： 此時(shí)取均長(zhǎng)為5，每個(gè)染色體（2）初始群體生成：群體大小視情況而定，此處設(shè)置為4，隨機(jī)產(chǎn)生四個(gè)個(gè)體： 編碼： 01101，11000，01000，10011 解碼： 13 24 8 19 適應(yīng)度： （3）適應(yīng)度評(píng)價(jià)：2022/7/1142（4）選擇：選擇概率 個(gè)體： 01101，11000，01000

19、，10011 適應(yīng)度： 選擇概率：0.14 0.49 0.06 0.31選擇結(jié)果：01101，11000，11000，10011（5）交叉操作：發(fā)生交叉的概率較大 哪兩個(gè)個(gè)體配對(duì)交叉是隨機(jī)的 交叉點(diǎn)位置的選取是隨機(jī)的（單點(diǎn)交叉） 0110 1 01100 11 000 11 011 1100 0 11001 10 011 10 0002022/7/1143（6）變異：發(fā)生變異的概率很?。?）新群體的產(chǎn)生： 保留上一代最優(yōu)個(gè)體，一般為10%左右，至少1個(gè) 用新個(gè)體取代舊個(gè)體，隨機(jī)取代或擇優(yōu)取代。 11000，11011，11001，10011（8）重復(fù)上述操作：說(shuō)明：GA的終止條件一般人為設(shè)置；

20、 GA只能求次優(yōu)解或滿意解。分析：按第二代新群體進(jìn)行遺傳操作，若無(wú)變異，永遠(yuǎn)也找不到最優(yōu)解擇優(yōu)取代有問(wèn)題。 若隨機(jī)的將個(gè)體01101選入新群體中，有可能找到最優(yōu)解。2022/7/114415.5 遺傳算法的理論基礎(chǔ)15.5.1 模式的定義遺傳算法的理論基礎(chǔ)是遺傳算法的二進(jìn)制表達(dá)式及模式的含義。模式是能對(duì)染色體之間的相似性進(jìn)行解釋的模板。定義1 設(shè)GA的個(gè)體 ,記集合則稱 為一個(gè)模式，其中是通配符。即模式(schema)是含有通配符(*)的一類字符串的通式表達(dá)。每個(gè)“*”可以取“1”或者“0”。2022/7/1145模式舉例模式 *10101110與以下兩個(gè)字符串匹配：010101110 110

21、101110而模式 *1010110與以下四個(gè)字符串匹配：010100110 010101110110100110 1101011102022/7/1146模式的定義定義2 一個(gè)模式s的階是出現(xiàn)在模式中的“0”和“1”的數(shù)目，記為o(s)。如：模式“0*”的階為1，模式“10*1*”的階為3。定義3 一個(gè)模式s的長(zhǎng)度是出現(xiàn)在模式中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離，記為 。如：模式“01*”的長(zhǎng)度為1，模式“0*1”的長(zhǎng)度為3。2022/7/114715.5.2 模式定理假定在給定的時(shí)間步t,一個(gè)特定的模式s在群體P(t)中包含由m個(gè)代表串，記為m=m(s,t)。首先，我們暫不考慮交叉

22、和變異操作。每個(gè)串根據(jù)適應(yīng)值的大小獲得不同的復(fù)制概率。串i的復(fù)制概率為：（1)2022/7/114815.5.2 模式定理則在群體P(t+1)中，模式s的代表串的數(shù)量的期望值為：其中， 表示模式s在t時(shí)刻的所有代表串的適應(yīng)值的均值，稱為模式s的適應(yīng)值。（2）2022/7/114915.5.2 模式定理若記P(t)中所有個(gè)體的適應(yīng)值的平均值為：（3）則(2)式可以表示為：2022/7/115015.5.2 模式定理(3)式表明，模式s的代表串的數(shù)目隨時(shí)間增長(zhǎng)的幅度正比于模式s的適應(yīng)值與群體平均適應(yīng)值的比值。即：適應(yīng)值高于群體平均值的模式在下一代的代表串?dāng)?shù)目將會(huì)增加，而適應(yīng)值低于群體平均值的模式在

23、下一代的代表串?dāng)?shù)目將會(huì)減少。假設(shè)模式的適應(yīng)值為 ,其中c是一個(gè)常數(shù)，則 (3)式可寫為：2022/7/115115.5.2 模式定理（4）上式表明，在平均適應(yīng)值之上（之下）的模式，將會(huì)按指數(shù)增長(zhǎng)（衰減）的方式被復(fù)制。2022/7/115215.5.2 模式定理復(fù)制的結(jié)果并沒(méi)有生成新的模式。因而，為了探索搜索空間中的未搜索部分，需要利用交叉和變異操作。下面先探索交叉對(duì)模式的影響。模式s1=“*1*0”和s2=“*10*”交叉會(huì)改變模式的一部分，模式的長(zhǎng)度越長(zhǎng)，被破壞的概率越大。2022/7/115315.5.2 模式定理假定模式s在交叉后不被破壞的概率為ps，則：若交叉概率為pc,則s不被破壞的

24、概率為2022/7/115415.5.2 模式定理（5）所以，再考慮交叉時(shí)，(3)式可表示為最后，考慮變異算子對(duì)模式的影響。變異算子以概率pm隨機(jī)地改變個(gè)體某一位的值。只有當(dāng)o(s)個(gè)確定位的值不被破壞時(shí)，模式s才不被破壞。2022/7/115515.5.2 模式定理模式s在變異后不被破壞的概率：Pm1,可近似地表示為2022/7/115615.5.2 模式定理（6）因此，考慮交叉和變異時(shí)，(3)式可表示為2022/7/115715.5.2 模式定理由(6)我們得到一個(gè)重要的定理。定理1 模式定理(Schema Theorem)適應(yīng)值在群體適應(yīng)值之上的、長(zhǎng)度較短的、低階的模式在GA的迭代中將按

25、指數(shù)增長(zhǎng)方式被復(fù)制。2022/7/115815.5.3 積木塊假設(shè)Holland和Goldberg在模式定理的基礎(chǔ)上提出了“積木塊假設(shè)”(Building Block Hypothesis):低階、長(zhǎng)度較短、高于平均適應(yīng)度的模式(積木塊)在遺傳算子的作用下，相互結(jié)合，能生成高階、長(zhǎng)度較長(zhǎng)、適應(yīng)度較高的模式，并得到全局最優(yōu)解。2022/7/115915.5.4 遺傳算法的收斂性分析算法的收斂性可以定義如下：定義： 若算法在t時(shí)刻的種群xt滿足則稱算法收斂到x0。關(guān)于遺傳算法的收斂性，Michalewicz證明了基于壓縮原理的收斂性定理。而Rudolph證明了基于Markov鏈的收斂性定理。202

26、2/7/116015.6 遺傳算法的改進(jìn)遺傳算法的局限性：遺傳算法得到了廣泛應(yīng)用，但也暴露了一些問(wèn)題，如：遺傳算法在解決某些問(wèn)題時(shí)速度較慢；遺傳算法對(duì)編碼方案的依賴性較強(qiáng)，算法的魯棒性不夠好等。這些問(wèn)題主要?dú)w結(jié)為：（1）上位(epistasis)效應(yīng)上位效應(yīng)包括兩個(gè)方面：多基因性和基因多效性。2022/7/116115.6 遺傳算法的改進(jìn)（2）編碼方案最初使用最多的是二進(jìn)制位串，但此類編碼并不適合一些實(shí)際問(wèn)題?，F(xiàn)在人們已經(jīng)探索了許多其它方案，如浮點(diǎn)表示、樹形表示等等。（3）積木塊假設(shè)積木塊假設(shè)是否成立，是否一定存在短的、低階的、高適應(yīng)值的積木塊？若構(gòu)成問(wèn)題最優(yōu)解的所有低階模式的適應(yīng)值都較低，這

27、是GA很難收斂到最優(yōu)解，此類問(wèn)題稱為“欺騙問(wèn)題”。2022/7/116215.6 遺傳算法的改進(jìn)（4）早熟收斂即GA收斂到一個(gè)局部最優(yōu)解。Schraudolph和Belew提出“動(dòng)態(tài)參數(shù)編碼”方案來(lái)解決早熟收斂問(wèn)題。關(guān)于遺傳算法的一些改進(jìn)措施，有興趣的同學(xué)可查找相關(guān)資料。2022/7/116315.7 遺傳機(jī)器學(xué)習(xí)分類器系統(tǒng)機(jī)器學(xué)習(xí)是人工智能的一個(gè)重要研究領(lǐng)域，也是人工智能的一個(gè)重要的應(yīng)用領(lǐng)域。遺傳機(jī)器學(xué)習(xí)(Genetics Based Machine Learning, GBML)時(shí)將遺傳算法與機(jī)器學(xué)習(xí)系統(tǒng)相結(jié)合的產(chǎn)物。2022/7/1164遺傳機(jī)器學(xué)習(xí)系統(tǒng)的一般框架任務(wù)子系統(tǒng)學(xué)習(xí)子系統(tǒng)任務(wù)

28、檢測(cè)器任務(wù)效應(yīng)器執(zhí)行效應(yīng)器執(zhí)行檢測(cè)器2022/7/1165匹茲堡方法和密西根方法遺傳機(jī)器學(xué)習(xí)有兩種重要的實(shí)現(xiàn)方法：一種是由匹茲堡(Pittsburgh)大學(xué)的De Jong和他的學(xué)生Smith提出的。該方法用整個(gè)規(guī)則集合表示一個(gè)個(gè)體，GAs維護(hù)一個(gè)包含一定數(shù)目的候選規(guī)則集的種群。這種方法稱為匹茲堡方法。2022/7/1166匹茲堡方法和密西根方法另一種方法是由密西根(Michigan)大學(xué)的Holland和他的學(xué)生Reitman提出的。該方法每個(gè)個(gè)體表示一條規(guī)則，而整個(gè)種群就是規(guī)則集。這種方法稱為密西根方法。Holland提出的分類器系統(tǒng)采用的是密西根方法。2022/7/1167分類器系統(tǒng)Ho

29、lland和他的同事提出了一種分類器系統(tǒng)的認(rèn)知模型,其中的規(guī)則不是規(guī)則集, 而是遺傳算法操縱的內(nèi)部實(shí)體。圖11.3給出了分類器系統(tǒng)的一般結(jié)構(gòu), 從分類器系統(tǒng)看學(xué)習(xí), 它由三層動(dòng)作構(gòu)成,即執(zhí)行子系統(tǒng)、信用賦值子系統(tǒng)和發(fā)現(xiàn)子系統(tǒng)。2022/7/1168 分類器系統(tǒng)發(fā)現(xiàn)遺傳算法信用賦值桶鏈執(zhí)行分類器系統(tǒng)消息來(lái)自輸入接口支付消息送出輸出接口（目標(biāo)）來(lái)自內(nèi)部監(jiān)控器的消息圖 11.3 分類器系統(tǒng)的一般結(jié)構(gòu)2022/7/1169 分類器系統(tǒng) 執(zhí)行子系統(tǒng)處在最低層, 直接與環(huán)境進(jìn)行交互。它與專家系統(tǒng)相同,由產(chǎn)生式規(guī)則構(gòu)成。但是, 它們是消息傳送,高度平行。這類規(guī)則稱作分類器。 分類器系統(tǒng)中的學(xué)習(xí), 要求環(huán)境提

30、供反饋, 確認(rèn)所希望的狀態(tài)是否達(dá)到。系統(tǒng)將評(píng)價(jià)這些規(guī)則的有效性, 這些活動(dòng)常常稱作信用賦值。有些特定算法專門用來(lái)實(shí)現(xiàn)信用賦值, 例如, 桶鏈算法。 最后一層是發(fā)現(xiàn)子系統(tǒng), 該系統(tǒng)必須產(chǎn)生新的規(guī)則, 取代當(dāng)前用處不大的規(guī)則。通過(guò)系統(tǒng)累積的經(jīng)驗(yàn)產(chǎn)生規(guī)則。系統(tǒng)根據(jù)適應(yīng)值, 使用遺傳算法選擇、重組和取代規(guī)則。2022/7/1170 分類器系統(tǒng) 分類器系統(tǒng)是平行執(zhí)行、消息傳遞和基于規(guī)則的系統(tǒng)。在簡(jiǎn)單的方案中,消息采用規(guī)定的字母, 全部為固定長(zhǎng)度。全部規(guī)則采用條件/動(dòng)作形式。每個(gè)條件規(guī)定必須滿足的信息, 每個(gè)動(dòng)作規(guī)定當(dāng)條件滿足時(shí)所發(fā)送的消息。 為了方便, 假設(shè)消息采用長(zhǎng)度為l的二進(jìn)制字符串記錄, 字符采用

31、子集1, 0, #。2022/7/1171規(guī)則與消息產(chǎn)生式規(guī)則：IF THEN 約定：條件的長(zhǎng)度是固定的，用二進(jìn)制數(shù)表示。定義： If sj = 1 or sj = 0, then mj = sj If sj = #, then mj can be either 1 or 0. 2022/7/1172規(guī)則與消息 滿足要求的全部消息構(gòu)成子集, 即每個(gè)子集是在消息空間的一個(gè)超平面。分類器系統(tǒng)是由一組分類器 C1, C2, CN、一個(gè)消息表、輸入接口、輸出接口構(gòu)成。每部分的主要功能如下: (1) 輸入接口將當(dāng)前環(huán)境狀態(tài)翻譯成標(biāo)準(zhǔn)消息。(2) 分類器根據(jù)規(guī)則, 規(guī)定系統(tǒng)處理消息的過(guò)程。(3) 消息表包

32、含當(dāng)前全部消息。(4) 輸出接口將結(jié)果消息翻譯成效應(yīng)器動(dòng)作, 修改環(huán)境狀態(tài)。2022/7/1173分類器系統(tǒng)的基本結(jié)構(gòu)分類器消息表(a)全部消息進(jìn)行條件測(cè)試條件消息規(guī)約輸出接口送到環(huán)境輸入接口來(lái)自環(huán)境(a)(b)(b)選中分類器產(chǎn)生新消息2022/7/1174分類器基本算法將輸入接口全部消息放入消息表。將消息表中的全部消息與全部分類器所有條件比較, 記錄所有匹配。滿足分類器條件部分的每組匹配, 將其動(dòng)作部分所規(guī)定的消息送到新的消息表。用新的消息表取代消息表中的全部消息。將消息表中的消息翻譯成輸出接口的要求, 產(chǎn)生系統(tǒng)當(dāng)前的輸出。返回到步驟(1)。2022/7/1175簡(jiǎn)單的視覺(jué)分類器系統(tǒng)視覺(jué)向

33、量視野運(yùn)動(dòng)向量對(duì)象檢測(cè)器11110消息2022/7/1176性質(zhì)檢測(cè)器規(guī)定的值1，如果移動(dòng)對(duì)象0，其它(0,0)，如果對(duì)象在視野的中間(1,0)，如果對(duì)象在中心的左邊(0,1)，如果對(duì)象在中心的右邊1，如果系統(tǒng)是對(duì)象的近鄰0，其它1，如果對(duì)象很大0，其它1，如果對(duì)象是狹長(zhǎng)的0，其它2022/7/1177規(guī)則表示規(guī)則：IF 如果有“捕食(prey)”(small, moving,nonstriped object), 處于視野中間(centered), 非鄰近 (nonadjacent),THEN 迅速移向?qū)ο?(ALIGN), (FAST).可以表示為：00#000001 / 01000000

34、00000000, ALIGN, FAST.2022/7/1178網(wǎng)絡(luò)圖MOVINGSMALLNOT STRIPEDNEARFAR01001ALERT10001TARGET11001PORSUE11010APPROACH11011FLEE11100FREEZE10010DANGER2022/7/1179網(wǎng)絡(luò)圖的規(guī)則表示MOVING和ALERT之間的箭頭：00#1/01001#SMALL，NOT STRIPED and ALERT到TARGET的箭頭：00#00#，01001#/10001#2022/7/1180學(xué)習(xí)機(jī)制分類器系統(tǒng)使用兩個(gè)學(xué)習(xí)機(jī)制，桶鏈(bucket brigade) 算法?；?/p>

35、對(duì)系統(tǒng)的貢獻(xiàn), 對(duì)現(xiàn)有規(guī)則分配一個(gè)信用值。規(guī)則發(fā)現(xiàn)算法。這包括遺傳算法，該算法可產(chǎn)生新規(guī)則，用于改善系統(tǒng)的知識(shí)庫(kù)。2022/7/118115.8 桶鏈算法 桶鏈(bucket brigade) 算法基于對(duì)系統(tǒng)的貢獻(xiàn), 對(duì)現(xiàn)有規(guī)則分配一個(gè)信用值。主要解決多條規(guī)則同時(shí)要求被激活時(shí)的競(jìng)爭(zhēng)問(wèn)題。 例如：下面的情況下應(yīng)該選擇哪條規(guī)則。011101# #：0000# #00：000100# 0：11002022/7/1182主要問(wèn)題引入信用值后的兩個(gè)問(wèn)題：當(dāng)多條規(guī)則同時(shí)要求被激活時(shí)，如何解決競(jìng)爭(zhēng)問(wèn)題對(duì)一規(guī)則被激活產(chǎn)生過(guò)作用的那些規(guī)則如何分配信用2022/7/1183桶鏈算法為解決上述兩個(gè)問(wèn)題，引入拍賣行和

36、票據(jù)交易所：當(dāng)有多個(gè)分類器獲得匹配時(shí)，每個(gè)分類器要出一個(gè)與其強(qiáng)度成正比的叫價(jià)B叫價(jià)高的分類器被激活并允許發(fā)送消息，同時(shí)通過(guò)票據(jù)交易所,將其叫價(jià)B提供給激活的分類器。如此繼續(xù)下去，一條規(guī)則可通過(guò)消費(fèi)者獲利（增加了強(qiáng)度），通過(guò)規(guī)則的不斷激活形成一條消費(fèi)者鏈，直至最終消費(fèi)者（達(dá)到目標(biāo)）直接從環(huán)境中得到補(bǔ)償。若鏈中一條規(guī)則導(dǎo)致錯(cuò)誤結(jié)論，則序列上該規(guī)則的強(qiáng)度將減弱，并且沿著序列回溯，從而產(chǎn)生新的消費(fèi)者鏈2022/7/1184舉例環(huán)境0111，強(qiáng)度為0，叫價(jià)系數(shù)為0.1。索引號(hào)分類器強(qiáng)度 101# #：0000200 200# 0：1000200 311# #：1000200 4# #00：0001200

37、2022/7/1185第一步分類器 強(qiáng)度 消息 匹配 叫價(jià)01# #：0000 200 E 2000# 0：1000 20011# #：1000 200# #00：0001 2002022/7/1186第二步分類器 強(qiáng)度 消息 匹配 叫價(jià)01# #：0000 180 000000# 0：1000 200 1 2011# #：1000 200# #00：0001 200 1 20兩條規(guī)則同時(shí)激活2022/7/1187第三步分類器 強(qiáng)度 消息 匹配 叫價(jià)01# #：0000 22000# 0：1000 180 110011# #：1000 200 2 20# #00：0001 180 0001 2

38、 182022/7/1188第四步分類器 強(qiáng)度 消息 匹配 叫價(jià)01# #：0000 22000# 0：1000 21811# #：1000 180 1000# #00：0001 162 3 162022/7/1189第五步分類器 強(qiáng)度 消息 匹配 叫價(jià) 強(qiáng)度01# #：0000 220 22000# 0：1000 218 21811# #：1000 196 196# #00：0001 146 0001 206規(guī)則4達(dá)到目標(biāo)獲得補(bǔ)償60。2022/7/1190投標(biāo)改變分類器的強(qiáng)度在時(shí)間t滿足C送去消息的分類器對(duì)在t-1作用的分類器投標(biāo)在時(shí)間t對(duì)分類器C的支持2022/7/1191分類器中的遺傳

39、算法遺傳算法可產(chǎn)生新規(guī)則，用于改善系統(tǒng)的知識(shí)庫(kù)。可以在三種情況下應(yīng)用GA：引入一個(gè)參數(shù)T（時(shí)間間隔），用于控制何時(shí)使用GA。特殊情況時(shí)（如消息的條件都不能匹配）使用GA。系統(tǒng)的性能太差。2022/7/1192算法步驟t=0，隨機(jī)生成集合Bt，|Bt|=M（大?。?；計(jì)算Bt中全體分類器的平均強(qiáng)度Vt，對(duì)每個(gè)分類器賦予一個(gè)標(biāo)準(zhǔn)強(qiáng)度St(Cj)/Vt；給Bt中的每個(gè)分類器Cj賦予一個(gè)與其標(biāo)準(zhǔn)強(qiáng)度成正比的概率，并根據(jù)Bt中的概率分布，從Bt中選取n個(gè)分類器，nM；對(duì)每個(gè)分類器應(yīng)用交叉算子，生成2n個(gè)分類器；將Bt中的2n個(gè)強(qiáng)度最低的分類器用新生成的2n個(gè)取代；t=t+1，轉(zhuǎn)(2)。2022/7/119

40、3算法說(shuō)明算法中S0(Cj)是預(yù)知的；實(shí)現(xiàn)時(shí)考慮結(jié)束條件；該算法是經(jīng)典GA的變種，其中沒(méi)有變異算子；新分類器的強(qiáng)度是由舊分類器的強(qiáng)度決定的。2022/7/1194分類器強(qiáng)度調(diào)整算法將與所選動(dòng)作相同的分類器形成子集 M，稱作動(dòng)作集 A。將不在 M中的其它分類器放在集合 NOTA中。在A中的全部分類器強(qiáng)度減少一個(gè)分?jǐn)?shù)e。如果系統(tǒng)決策正確，則將贏利量R分配給A的強(qiáng)度;如果系統(tǒng)決策錯(cuò)誤，則將贏利量R(其中0RR)分配給 A的強(qiáng)度，從A的強(qiáng)度減少一個(gè)分?jǐn)?shù)p。至少R和p中的一個(gè)為0。從 NOTA中的強(qiáng)度減去一個(gè)分?jǐn)?shù)t。2022/7/119515.9 規(guī)則發(fā)現(xiàn)系統(tǒng) 在規(guī)則發(fā)現(xiàn)系統(tǒng)中, 學(xué)習(xí)經(jīng)常是首先評(píng)價(jià)系統(tǒng)

41、現(xiàn)有的規(guī)則質(zhì)量, 然后進(jìn)行修改。Grefenstette 研制了一種規(guī)則發(fā)現(xiàn)系統(tǒng)RUDI。問(wèn)題求解級(jí)由簡(jiǎn)化的分類器系統(tǒng)組成。學(xué)習(xí)級(jí)是對(duì)知識(shí)結(jié)構(gòu)群體進(jìn)行遺傳算法操作, 每一個(gè)表示為一組規(guī)則表。知識(shí)結(jié)構(gòu)的整個(gè)行為控制這些結(jié)構(gòu)的復(fù)制。 在RUDI中, 信用賦值方法贏利共享規(guī)劃(Profit-Sharing Plan,簡(jiǎn)稱PSP) 和桶鏈算法(BBA) 對(duì)每個(gè)規(guī)則提供互補(bǔ)的效用信息。根據(jù)期望的外部獎(jiǎng)勵(lì), PSP-強(qiáng)度對(duì)規(guī)則效用提供更精確的評(píng)估。當(dāng)問(wèn)題求解時(shí)它被用作沖突消解。與此相反, BBA-強(qiáng)度表示規(guī)則之間的動(dòng)態(tài)相關(guān)性, 規(guī)則點(diǎn)火依次會(huì)聚到相似水平。這種測(cè)度可以用作一組協(xié)作規(guī)則的聚類。 2022/7/1196 規(guī)則發(fā)現(xiàn)系統(tǒng) Grefenstette 提出一種強(qiáng)度修改方案稱作嬴利共享規(guī)劃PSP。在這種方案中問(wèn)題求解劃分成情節(jié), 按所接受的外部獎(jiǎng)勵(lì)區(qū)分。如果任何步情節(jié)在投標(biāo)競(jìng)爭(zhēng)中獲勝, 則認(rèn)為該規(guī)則在該情節(jié)活動(dòng)。在情節(jié)t, PSP 修改每個(gè)活動(dòng)規(guī)則Ri的強(qiáng)度 Si(t) 如下: Si(t + 1) = Si(t) -bSi(t) + bp(t), 其中, p(t) 稱作在情節(jié)結(jié)束時(shí)所獲得的外部獎(jiǎng)勵(lì), 即當(dāng)獲得外部獎(jiǎng)勵(lì),從每個(gè)活動(dòng)規(guī)則搜集投標(biāo), 每個(gè)活動(dòng)規(guī)則給出一部分外部獎(jiǎng)勵(lì)?？紤]PSP 對(duì)給定規(guī)則Ri 的影響, 它按照方程得到:2