高級人工智能之進(jìn)化理論

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

1967年，Bagley在他的論論文中首首次提出出了遺傳傳算法這這一術(shù)語語，并討討論了遺遺傳算法法在自動動博弈中中的應(yīng)用用。1970年，Cavicchio把遺傳算算法應(yīng)用用于模式式識別中中。第一一個把遺遺傳算法法應(yīng)用于于函數(shù)優(yōu)優(yōu)化的是是Hollstien。2020-01-155史忠植高高級級人工智智能發(fā)展歷史史1975年是遺遺傳算法法研究的的歷史上上十分重重要的一一年。這這一年，，Holland出版了他他的著名名專著《《自然系系統(tǒng)和人人工系統(tǒng)統(tǒng)的適應(yīng)應(yīng)性》該書系統(tǒng)統(tǒng)地闡述述了遺傳傳算法的的基本理理論和方方法，并并提出了了對遺傳傳算法的的理論研研究和發(fā)發(fā)展極為為重要的的模式理理論（schematatheory）），該理論首首次確認(rèn)認(rèn)了結(jié)構(gòu)構(gòu)重組遺遺傳操作作對于獲獲得隱并并行性的的重要性性。同年，DeJong完成了他他的重要要論文《《遺傳自自適應(yīng)系系統(tǒng)的行行為分析析》。他他在該論論文中所所做的研研究工作作可看作作是遺傳傳算法發(fā)發(fā)展過程程中的一一個里程程碑，這這是因為為他把Holland的模式理理論與他他的計算算使用結(jié)結(jié)合起來來。2020-01-156史忠植高高級級人工智智能發(fā)展歷史史1989Goldberg對遺傳算算法從理理論上，，方法上上和應(yīng)用用上作了了系統(tǒng)的的總結(jié)。1990年，Koza提出了遺遺傳程序序設(shè)計（（GeneticProgramming）的概念。。（用于于搜索解解決特定定問題的的最適計計算機(jī)程程序）2020-01-157史忠植高高級級人工智智能遺傳算法法與自然然進(jìn)化的的比較自然界染色體基因等位基因因(allele))染色體位位置(locus)基因型((genotype)表型(phenotype))遺傳算法法字符串字符,特特征特征值字符串位位置結(jié)構(gòu)參數(shù)集,,譯碼結(jié)結(jié)構(gòu)2020-01-158史忠植高高級級人工智智能新達(dá)爾文文五進(jìn)化化理論的的主要論論點個體是基基本的選選擇目標(biāo)標(biāo);隨機(jī)過程程在進(jìn)化化中起重重大作用用,遺遺傳變異異大部分分是偶然然現(xiàn)象;;基因型變變異大部部分是重重組的產(chǎn)產(chǎn)物,特特別是是突變;;逐漸進(jìn)化化可能與與表型不不連續(xù)有有關(guān);不是所有有表型變變化都是是自然選選擇的必必然結(jié)果果;進(jìn)化是在在適應(yīng)中中變化的的,形形式多樣樣,不不僅是基基因的變變化;選擇是概概率型的的,而而不是是決定型型的。2020-01-159史忠植高高級級人工智智能進(jìn)化計算算的三大主流流板塊Holland提出的遺遺傳算法法(GeneticAlgorithm)。。Rechenberg和Schwefel提出的進(jìn)進(jìn)化策略略(EvolutionaryStrategies)。。Fogel提出的進(jìn)進(jìn)化規(guī)劃劃(EvolutionaryProgramming)，又稱稱為進(jìn)化化程序設(shè)設(shè)計。本章將著著重介紹紹遺傳算算法，對對進(jìn)化策略略和進(jìn)化化規(guī)劃只作簡單單介紹。。2020-01-1510史忠植高高級級人工智智能15.2進(jìn)化系統(tǒng)統(tǒng)理論的的形式模模型進(jìn)化在個個體群體體中起作作用。瓦瓦鋌頓((Waddington)指出基因因型和表表型之間間關(guān)系的的重要性性(Waddington1974)。群體禁止止異構(gòu)環(huán)環(huán)境。但但是“后后生環(huán)境境”是多多維空間間。表型型是基因因型和環(huán)環(huán)境的產(chǎn)產(chǎn)物。然然后表型型通過異異構(gòu)“選選擇環(huán)境境"發(fā)生生作用。。注意，，這種多多維選擇擇環(huán)境與與后生環(huán)環(huán)境空間間是不同同的?，F(xiàn)現(xiàn)在，適適應(yīng)性是是表型空空間和選選擇環(huán)境境空間的的產(chǎn)物。。它經(jīng)常常被取作作一維，，表示多多少子孫孫對下一代作作出貢獻(xiàn)獻(xiàn)?；谶@種種想法，，莫楞貝貝(Muhlenbein)和肯德曼曼(Kindermann)提出了一一種稱為進(jìn)化系系統(tǒng)理論論的形式式模型((Muhlenbein1989)。2020-01-1511史忠植高高級級人工智智能進(jìn)化系統(tǒng)統(tǒng)理論的的形式模模型進(jìn)化的主主要過程程后生環(huán)境境遺傳操作作符選擇環(huán)境境gp2020-01-1512史忠植高高級級人工智智能進(jìn)化系統(tǒng)統(tǒng)理論的的形式模模型其中，g是基因型型p是表型。?；騡i的可能值值稱為等等位基因因。在門德爾爾(Mendel))遺傳學(xué)中中，假設(shè)設(shè)每個基基因有有有限數(shù)的的等位基基因。2020-01-1513史忠植高高級級人工智智能進(jìn)化系統(tǒng)統(tǒng)理論的的形式模模型這個變換換函數(shù)給給出了模模型，說說明表型型的發(fā)展展是通過過基因與環(huán)境境的交互互作用。。變換過程程是高度度非線性性的。2020-01-1514史忠植高高級級人工智智能進(jìn)化系統(tǒng)統(tǒng)理論的的形式模模型質(zhì)量函數(shù)數(shù)q給出了具具體選擇擇環(huán)境ESi下表型的的質(zhì)量，，其定義如如下：質(zhì)量定義義適應(yīng)度度，用于于達(dá)爾文文選擇。。至今已已有三種種具體范范例的通通用模型型，即門德爾遺遺傳學(xué)遺傳生態(tài)態(tài)學(xué)進(jìn)化配子子2020-01-1515史忠植高高級級人工智智能門德爾遺遺傳學(xué)在門德爾爾遺傳學(xué)學(xué)中，基基因型被被詳細(xì)模模型化，，而表型型和環(huán)境幾乎乎被忽略略。在遺遺傳生態(tài)態(tài)學(xué)中恰好相相反。進(jìn)化配子子論是從從社會生生物學(xué)導(dǎo)導(dǎo)出的模模型。首先讓我我們討論論門德爾爾遺傳學(xué)學(xué)的選擇擇模型。。為了簡簡單起見見，我們們假設(shè)一一個基因因具有n等位基因因a1,…,an。二倍基因因型以元元組(ai,aj)為特征。。我們們定義pi,j為總?cè)后w體中基因因型(ai,aj)的頻度。。假設(shè)基基因型與與表型相相等。質(zhì)質(zhì)量函數(shù)數(shù)給每個個表型賦值。。q(ai,aj)=qi,jqi,j可以被解解釋為出出生率減減去死亡亡率2020-01-1516史忠植高高級級人工智智能門德爾遺遺傳學(xué)假設(shè)p’i,j是下一代代表型((ai,aj)的頻度。。然后達(dá)達(dá)爾文選擇根據(jù)據(jù)選擇方方程調(diào)整整表型的的分布::是群體的的平均適適應(yīng)度。。2020-01-1517史忠植高高級級人工智智能門德爾遺遺傳學(xué)設(shè)pi是群體中中等位基基因的頻頻率。如如果pi,j=pipj那么，我我們得到到在GS中的一個個選擇方方程為2020-01-1518史忠植高高級級人工智智能門德爾遺遺傳學(xué)這個離散散的選擇擇方程可可以用連連續(xù)方程程近似::如果qi,j=qj,i,那么2020-01-1519史忠植高高級級人工智智能門德爾遺遺傳學(xué)這個方程程很容易易被證明明:這個結(jié)果果稱作菲菲希爾((Fisher))基本定理理。它說說明平均均適應(yīng)度度隨適應(yīng)應(yīng)度的差差別呈正正比例增增加。實實際上，，全部可可能的基基因型僅僅有一部部分實現(xiàn)現(xiàn)。這就就是遺傳傳操縱子子探索基基因型空空間的任任務(wù)，其其個體數(shù)數(shù)目相當(dāng)當(dāng)小。這這些操縱縱子是群群體遺傳傳變異性性的來源源。最重要的的操縱子子是突變變和重組組。2020-01-1520史忠植高高級級人工智智能15.3達(dá)爾文進(jìn)進(jìn)化算法法根據(jù)定量量遺傳學(xué)學(xué)，達(dá)爾爾文進(jìn)化化算法采采用簡單單的突變//選擇動動力學(xué)。。達(dá)爾文算算法的一一般形式式可以描描述如下下：是一代的的雙親數(shù)數(shù)目，為子孫數(shù)數(shù)目。整數(shù)稱作“混混雜”數(shù)數(shù)。如果兩個個雙親混混合他們們的基因因，則=2。。僅是最好的的個體才才允許產(chǎn)產(chǎn)生子孫孫。逗號表示示雙親們沒沒有選擇擇，加號號表示雙雙親有選選擇。2020-01-1521史忠植高高級級人工智智能15.3達(dá)爾文進(jìn)進(jìn)化算法法建立原始始種體。。通過突變變建立子子孫。選擇：返回到步步驟(1)?！?020-01-1522史忠植高高級級人工智智能遺傳算法法思想來來源于生生物進(jìn)化化過程,,它是是基于進(jìn)進(jìn)化過程程中的信信息遺傳傳機(jī)制和和優(yōu)勝劣劣汰的自自然選擇擇原則的的搜索算算法(以以字符串串表示狀狀態(tài)空間間)。遺遺傳算法法用概率率搜索過過程在該該狀態(tài)空空間中搜搜索，產(chǎn)產(chǎn)生新的的樣本。。15.4遺傳算法法2020-01-1523史忠植高高級級人工智智能遺傳算法法的特點點特點：通用魯棒次優(yōu)解、、滿意解解遺傳算法法能解決決的問題題：優(yōu)化NP完全NP難高度復(fù)雜雜的非線線性問題題2020-01-1524史忠植高高級級人工智智能遺傳算法法遺傳算法法先將搜搜索結(jié)構(gòu)構(gòu)編碼為為字符串串形式,,每個個字符串串結(jié)構(gòu)被被稱為個個體。然后對一一組字符符串結(jié)構(gòu)構(gòu)(被稱稱為一個個群體))進(jìn)行循循環(huán)操作作。每次次循環(huán)被被稱作一一代,包包括一個個保存字字符串中中較優(yōu)結(jié)結(jié)構(gòu)的過過程和一一個有結(jié)結(jié)構(gòu)的、、隨機(jī)的的字符串串間的信信息交換換過程。。類似于自自然進(jìn)化化，遺傳傳算法通通過作用用于染色色體上的的基因?qū)ふ液玫牡娜旧w體來求解解問題。。2020-01-1525史忠植高高級級人工智智能遺傳算法法與自然界界相似，，遺傳算算法對求求解問題題的本身身一無所所知，它它所需要要的僅是是對算法法所產(chǎn)生生的每個個染色體體進(jìn)行評評價，并并基于適適應(yīng)值來來選擇染染色體，，使適應(yīng)應(yīng)性好的的染色體體有更多多的繁殖殖機(jī)會。。在遺傳算算法中，，位字符符串扮演演染色體體的作用用，單個個位扮演演了基因因的作用用，隨機(jī)機(jī)產(chǎn)生一一個體字字符串的的初始群群體，每每個個體體給予一一個數(shù)值值評價，，稱為適適應(yīng)度，，取消低低適應(yīng)度度的個體體，選擇擇高適應(yīng)應(yīng)度的個個體參加加操作。。常用的遺遺傳算子子有復(fù)制制、雜交交、變異異和反轉(zhuǎn)轉(zhuǎn)。2020-01-1526史忠植高高級級人工智智能遺傳算法法與傳統(tǒng)統(tǒng)優(yōu)化算算法的主主要不同同遺傳算法法不是直直接作用用在參變變量集上上,而而是利用用參變量量集的某某種編碼碼;遺傳算法法不是從從單個點點,而而是在群群體中從從一個點點開始搜搜索;遺傳算法法利用適適應(yīng)值信信息,無無需導(dǎo)導(dǎo)數(shù)或其其它輔助助信息;;遺傳算法法利用概概率轉(zhuǎn)移移規(guī)則,,而非非確定性性規(guī)則。。2020-01-1527史忠植高高級級人工智智能遺傳算法法的準(zhǔn)備備工作確定表示示方案;;確定適應(yīng)應(yīng)值的度度量;確定控制制該算法法的參數(shù)數(shù)和變量量;確定怎樣樣指定結(jié)結(jié)果及程程序運行行結(jié)束的的標(biāo)準(zhǔn)。。2020-01-1528史忠植高高級級人工智智能基本遺傳傳算法基本遺傳傳算法((SimpleGeneticAlgorithm::SGA)又稱為簡簡單遺傳傳算法，，只使用用選擇算算子、交交叉算子子和變異異算子這這三種基基本的遺遺傳算子子。其遺遺傳操作作簡單、、容易理理解，是是其它遺遺傳算法法的雛形形和基礎(chǔ)礎(chǔ)?；具z傳傳算法的的構(gòu)成要要素：1、染色色體編碼碼方法：：首先必必須對問問題的解解空間進(jìn)進(jìn)行編碼碼，使之之能用遺遺傳算法法進(jìn)行操操作。較較常用的的是二進(jìn)進(jìn)制編碼碼方法，，現(xiàn)在使使用非二二進(jìn)制編編碼的也也逐漸增增多。2、適應(yīng)應(yīng)度函數(shù)數(shù)（fitnessfunction，又稱為適適應(yīng)值／／適值函函數(shù)）用用來評價價一個染染色體的的好壞。。2020-01-1529史忠植高高級級人工智智能基本遺傳傳算法的的構(gòu)成要要素3、遺傳傳算子?選擇算子子(selection))：又稱為復(fù)復(fù)制算子子。按照照某種策策略從父父代中挑挑選個體體進(jìn)入下下一代，，如使用用比例選選擇、輪輪盤式選選擇。?交叉算子子(crossover))：又稱為雜雜交算子子。將從從群體中中選擇的的兩個個個體，按按照某種種策略使使兩個個個體相互互交換部部分染色色體，從從而形成成兩個新新的個體體。如使使用單點點一致交交叉。?變異算子子(mutation)：：按照一定定的概率率（一般般較?。淖冏?nèi)旧w體中某些些基因的的值。2020-01-1530史忠植高高級級人工智智能雜交操作作舉例10220201[NoOffspring]]Pt.ofinterchange[Crossover][Parents][Offspring]]1110####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#2020-01-1531史忠植高高級級人工智智能變異操作作簡單的變變異操作作過程如如下:每個位置置的字符符變量都都有一個個變異概概率,各各位置置互相獨獨立。通通過隨機(jī)機(jī)過程選選擇發(fā)生生變異的的位置：：產(chǎn)生一個個新結(jié)構(gòu)構(gòu),其中是是從對對應(yīng)位置置的的字字符變量量的值域域中隨機(jī)機(jī)選擇的的一個取取值。可可以同樣樣得到。。2020-01-1532史忠植高高級級人工智智能反轉(zhuǎn)操作作簡單反轉(zhuǎn)轉(zhuǎn)操作的的步驟如如下:從當(dāng)前群群體中隨隨機(jī)選擇擇一個結(jié)結(jié)構(gòu)從中隨機(jī)機(jī)選擇兩兩個數(shù)i’和j’,并定義i=min{i'',j''},j=max{{i',,j'}};顛倒a中位置i、j之間的部部分,產(chǎn)產(chǎn)生新新的結(jié)構(gòu)構(gòu)2020-01-1533史忠植高高級級人工智智能基本遺傳傳算法的的構(gòu)成要要素4、運行行參數(shù)N：群體大小小，即群群體中包包含的個個體的數(shù)數(shù)量。T：遺傳算法法終止的的進(jìn)化代代數(shù)。Pc：交叉概率率，一般般取為0.4～0..99。。Pm：變異概率率，一般般取為0.0001～0..1。。2020-01-1534史忠植高高級級人工智智能基本遺傳傳算法隨機(jī)產(chǎn)生生一個由由固定長長度字符符串組成成的初始始群體;;對于字符符串群體體，迭代代地執(zhí)行行下述步步驟，直直到選種種標(biāo)準(zhǔn)被被滿足為為止：計算群體體中的每每個個體體字符串串的適應(yīng)應(yīng)值;應(yīng)用下述述三種操操作(至至少前兩兩種)來來產(chǎn)生新新的群體體:復(fù)制:把把現(xiàn)有有的個體體字符串串復(fù)制到到新的群群體中。。雜交:通通過遺遺傳重組組隨機(jī)選選擇兩個個現(xiàn)有的的子字符符串,產(chǎn)產(chǎn)生生新的字字符串。。變異:將將現(xiàn)有有字符串串中某一一位的字字符隨機(jī)機(jī)變異。。把在后代代中出現(xiàn)現(xiàn)的最高高適應(yīng)值值的個體體字符串串指定為為遺傳算算法運行行的結(jié)果果。這一一結(jié)果可可以是問問題的解解(或近近似解))。2020-01-1535史忠植高高級級人工智智能基本遺傳傳算法流流程圖GEN=0概率地選擇遺傳操作隨機(jī)創(chuàng)建初始群體計算群體中每個個體的適應(yīng)值i:=0顯示結(jié)果結(jié)束GEN:=GEN+1是是否（轉(zhuǎn)下頁）i=N?GEN=M？12020-01-1536史忠植高高級級人工智智能概率地選選擇遺傳傳操作根據(jù)適應(yīng)應(yīng)值選擇一個個個體完成交叉叉i:=i+1i:=i+1復(fù)制個體體p(r))選擇（接上頁頁）基于適應(yīng)應(yīng)值選擇兩個個個體把新的兩兩個孩子加到群群體中p(c))交叉變異p(m))把新的孩孩子加入到群體體中完成變異異根據(jù)適應(yīng)應(yīng)值選擇一個個個體把變異后后個體加入到群群體中12020-01-1537史忠植高高級級人工智智能輪盤式選選擇首先計算算每個個個體i被選中的的概率然后根據(jù)據(jù)概率的的大小將將將圓盤盤分為n個扇形，，每個扇扇形的大大小為。。選選擇時轉(zhuǎn)轉(zhuǎn)動輪盤盤，參考考點r落到扇形形i則選擇個個體i。......p1p2pir2020-01-1538史忠植高高級級人工智智能單點一致致交叉首先以概概率pc從種群中中隨機(jī)地地選擇兩兩個個體體p1、p2。在{1,2,.....,,l}內(nèi)隨機(jī)選選擇一個個數(shù)i,作為交叉叉的位置置，稱為為交叉點點。然后后將兩個個個體交交叉點后后面的部部分交換換。例如：01101011000110011001110001100111001011002020-01-1539史忠植高高級級人工智智能一致變異異以概率pm對種群中中所有個個體的每每一位進(jìn)進(jìn)行變異異。對于個體體pi的第j位，在[[0,1]的范范圍內(nèi)隨隨機(jī)地生生成一個個數(shù)r,如果r<pm,則對第j位取反，，否則保保持第j位不變。。2020-01-1540史忠植高高級級人工智智能遺傳算法法舉例問題：求求（1）編碼：此時取均均長為5，每個個染色體體（2）初初始群體體生成：：群體大大小視情情況而定定，此處處設(shè)置為為4，隨隨機(jī)產(chǎn)生生四個個個體：編碼：01101，，11000，，01000，，10011解碼：1324819適應(yīng)度：：16957664361（3）適適應(yīng)度評評價：2020-01-1541史忠植高高級級人工智智能（4）選選擇：選選擇概率率個體：01101，，11000，，01000，，10011適應(yīng)度：：16957664361選擇概率率：0..140..490..060.31選擇結(jié)果果：01101，11000，11000，10011（5）交交叉操作作：發(fā)生生交叉的的概率較較大哪兩個個個體配對對交叉是是隨機(jī)的的交叉點位位置的選選取是隨隨機(jī)的（（單點交交叉）01101011001100011011110001100110011100002020-01-1542史忠植高高級級人工智智能（6）變變異：發(fā)發(fā)生變異異的概率率很?。?）新新群體的的產(chǎn)生：：保留上一一代最優(yōu)優(yōu)個體，，一般為為10%%左右，，至少1個用新個體體取代舊舊個體，，隨機(jī)取取代或擇擇優(yōu)取代代。11000，11011，11001，10011（8）重重復(fù)上述述操作：：說明：GA的終止條條件一般般人為設(shè)設(shè)置；GA只能求次次優(yōu)解或或滿意解解。分析：按按第二代代新群體體進(jìn)行遺遺傳操作作，若無無變異，，永遠(yuǎn)也也找不到到最優(yōu)解解——擇擇優(yōu)取代代有問題題。若隨機(jī)的的將個體體01101選選入新群群體中，，有可能能找到最最優(yōu)解。。2020-01-1543史忠植高高級級人工智智能15.5遺傳傳算法的的理論基基礎(chǔ)15.5..1模式的定定義遺傳算法法的理論論基礎(chǔ)是是遺傳算算法的二二進(jìn)制表表達(dá)式及及模式的的含義。。模式是是能對染染色體之之間的相相似性進(jìn)進(jìn)行解釋釋的模板板。[定義1]設(shè)設(shè)GA的個體,,記集合合則稱為為一一個模式式，其中中＊是通通配符。。即模式((schema))是含有通通配符(*)的一類字字符串的的通式表表達(dá)。每每個“*”可可以取““1”或或者“0”。2020-01-1544史忠植高高級級人工智智能模式舉例例模式*10101110與以下兩兩個字符符串匹配配：010101110110101110而模式*1010＊110與以下四四個字符符串匹配配：0101001100101011101101001101101011102020-01-1545史忠植高高級級人工智智能模式的定定義[定義2]一一個模式s的階是出現(xiàn)在在模式中中的“0”和““1”的的數(shù)目，，記為o(s))。如：模式式“0*****””的階為為1，模模式“10*1*”的的階為3。[定義3]一一個模式s的長度是出現(xiàn)在在模式中中第一個個確定位位置和最最后一個個確定位位置之間間的距離離，記為為。如：模式式“01****””的長度度為1，，模式““0****1””的長度度為3。。2020-01-1546史忠植高高級級人工智智能15.5.2模模式式定理假定在給給定的時時間步t,一個個特定的的模式s在群體體P(t)中包包含由m個代表表串，記記為m==m(s,t))。首先先，我們們暫不考考慮交叉叉和變異異操作。。每個串串根據(jù)適適應(yīng)值的的大小獲獲得不同同的復(fù)制制概率。。串i的的復(fù)制概概率為：：（1)2020-01-1547史忠植高高級級人工智智能15.5.2模模式式定理則在群體體P(t+1))中，模模式s的的代表串串的數(shù)量量的期望望值為：：其中，表表示示模式s在t時刻的所所有代表表串的適適應(yīng)值的的均值，，稱為模模式s的適應(yīng)值值。（2）2020-01-1548史忠植高高級級人工智智能15.5.2模模式式定理若記P((t)中中所有個個體的適適應(yīng)值的的平均值值為：（3）則(2))式可以以表示為為：2020-01-1549史忠植高高級級人工智智能15.5.2模模式式定理(3)式式表明，，模式s的代表表串的數(shù)數(shù)目隨時時間增長長的幅度度正比于于模式s的適應(yīng)應(yīng)值與群群體平均均適應(yīng)值值的比值值。即：：適應(yīng)值值高于群群體平均均值的模模式在下下一代的的代表串串?dāng)?shù)目將將會增加加，而適適應(yīng)值低低于群體體平均值值的模式式在下一一代的代代表串?dāng)?shù)數(shù)目將會會減少。。假設(shè)模式式的適應(yīng)應(yīng)值為,,其其中c是是一個常常數(shù)，則則(3)式可可寫為：：2020-01-1550史忠植高高級級人工智智能15.5.2模模式式定理（4）上式表明明，在平平均適應(yīng)應(yīng)值之上上（之下下）的模模式，將將會按指指數(shù)增長長（衰減減）的方方式被復(fù)復(fù)制。2020-01-1551史忠植高高級級人工智智能15.5.2模模式式定理復(fù)制的結(jié)結(jié)果并沒沒有生成成新的模模式。因而，為為了探索索搜索空空間中的的未搜索索部分，，需要利利用交叉叉和變異異操作。。下面先探探索交叉叉對模式式的影響響。模式s1=““*1******0”和s2=““****10***”交叉會改改變模式式的一部部分，模模式的長長度越長長，被破破壞的概概率越大大。2020-01-1552史忠植高高級級人工智智能15.5.2模模式式定理假定模式式s在交叉后后不被破破壞的概概率為ps，則：若交叉概概率為pc,則s不被破壞壞的概率率為2020-01-1553史忠植高高級級人工智智能15.5.2模模式式定理（5）所以，再再考慮交交叉時，，(3))式可表表示為最后，考考慮變異異算子對對模式的的影響。。變異算算子以概概率pm隨機(jī)地改改變個體體某一位位的值。。只有當(dāng)當(dāng)o(s))個確定位位的值不不被破壞壞時，模模式s才不被破破壞。2020-01-1554史忠植高高級級人工智智能15.5.2模模式式定理模式s在變異后后不被破破壞的概概率：Pm<<1,,可近似地地表示為為2020-01-1555史忠植高高級級人工智智能15.5.2模模式式定理（6）因此，考考慮交叉叉和變異異時，((3)式式可表示示為2020-01-1556史忠植高高級級人工智智能15.5.2模模式式定理由(6))我們得得到一個個重要的的定理。。[定理1]模模式定理理(SchemaTheorem)適應(yīng)值在在群體適適應(yīng)值之之上的、、長度較較短的、、低階的的模式在在GA的的迭代中中將按指指數(shù)增長長方式被被復(fù)制。。2020-01-1557史忠植高高級級人工智智能15.5.3積積木木塊假設(shè)設(shè)Holland和Goldberg在模式式定理的的基礎(chǔ)上上提出了了“積木木塊假設(shè)設(shè)”(BuildingBlockHypothesis):低階、長長度較短短、高于于平均適適應(yīng)度的的模式((積木塊塊)在遺遺傳算子子的作用用下，相相互結(jié)合合，能生生成高階階、長度度較長、、適應(yīng)度度較高的的模式，，并得到到全局最最優(yōu)解。。2020-01-1558史忠植高高級級人工智智能15.5.4遺遺傳傳算法的的收斂性性分析算法的收收斂性可可以定義義如下：：定義：若若算法法在t時刻的種種群xt滿足則稱算法法收斂到到x0。關(guān)于遺傳傳算法的的收斂性性，Michalewicz證明了基基于壓縮縮原理的的收斂性性定理。。而Rudolph證明了基基于Markov鏈的收斂斂性定理理。2020-01-1559史忠植高高級級人工智智能15.6遺傳算法法的改進(jìn)進(jìn)遺傳算法法的局限限性：遺傳算法法得到了了廣泛應(yīng)應(yīng)用，但但也暴露露了一些些問題，，如：遺遺傳算法法在解決決某些問問題時速速度較慢慢；遺傳傳算法對對編碼方方案的依依賴性較較強，算算法的魯魯棒性不不夠好等等。這些問題題主要歸歸結(jié)為：：（1）上上位(epistasis))效應(yīng)上位效應(yīng)應(yīng)包括兩兩個方面面：多基基因性和和基因多多效性。。2020-01-1560史忠植高高級級人工智智能15.6遺傳算法法的改進(jìn)進(jìn)（2）編編碼方案案最初使用用最多的的是二進(jìn)進(jìn)制位串串，但此此類編碼碼并不適適合一些些實際問問題。現(xiàn)現(xiàn)在人們們已經(jīng)探探索了許許多其它它方案，，如浮點點表示、、樹形表表示等等等。（3）積積木塊假假設(shè)積木塊假假設(shè)是否否成立，，是否一一定存在在短的、、低階的的、高適適應(yīng)值的的積木塊塊？若構(gòu)構(gòu)成問題題最優(yōu)解解的所有有低階模模式的適適應(yīng)值都都較低，，這是GA很難收斂斂到最優(yōu)優(yōu)解，此此類問題題稱為““欺騙問問題”。。2020-01-1561史忠植高高級級人工智智能15.6遺傳算法法的改進(jìn)進(jìn)（4）早早熟收斂斂即GA收斂到一一個局部部最優(yōu)解解。Schraudolph和Belew提出“動動態(tài)參數(shù)數(shù)編碼””方案來來解決早早熟收斂斂問題。。關(guān)于遺傳傳算法的的一些改改進(jìn)措施施，有興興趣的同同學(xué)可查查找相關(guān)關(guān)資料。。2020-01-1562史忠植高高級級人工智智能15.7遺傳機(jī)器器學(xué)習(xí)－－－分分類器系系統(tǒng)機(jī)器學(xué)習(xí)習(xí)是人工工智能的的一個重重要研究究領(lǐng)域，，也是人人工智能能的一個個重要的的應(yīng)用領(lǐng)領(lǐng)域。遺傳機(jī)器器學(xué)習(xí)((GeneticsBasedMachineLearning,GBML)時將遺傳傳算法與與機(jī)器學(xué)學(xué)習(xí)系統(tǒng)統(tǒng)相結(jié)合合的產(chǎn)物物。2020-01-1563史忠植高高級級人工智智能遺傳機(jī)器器學(xué)習(xí)系統(tǒng)的一一般框架架任務(wù)子系系統(tǒng)學(xué)習(xí)子系系統(tǒng)任務(wù)檢測測器……任務(wù)效應(yīng)應(yīng)器執(zhí)行效應(yīng)應(yīng)器執(zhí)行檢測測器2020-01-1564史忠植高高級級人工智智能匹茲堡方方法和密密西根方方法遺傳機(jī)器器學(xué)習(xí)有有兩種重重要的實實現(xiàn)方法法：一種是由由匹茲堡堡(Pittsburgh))大學(xué)的的DeJong和他他的學(xué)生生Smith提提出的。。該方法法用整個個規(guī)則集集合表示示一個個個體，GAs維維護(hù)一個個包含一一定數(shù)目目的候選選規(guī)則集集的種群群。這種種方法稱稱為匹茲茲堡方法法。2020-01-1565史忠植高高級級人工智智能匹茲堡方方法和密密西根方方法另一種方方法是由由密西根根(Michigan)大學(xué)學(xué)的Holland和和他的學(xué)學(xué)生Reitman提提出的。。該方法法每個個個體表示示一條規(guī)規(guī)則，而而整個種種群就是是規(guī)則集集。這種種方法稱稱為密西西根方法法。Holland提出的的分類器器系統(tǒng)采采用的是是密西根根方法。。2020-01-1566史忠植高高級級人工智智能分類器系系統(tǒng)Holland和他的同同事提出出了一種種分類器器系統(tǒng)的的認(rèn)知模模型,其其中的規(guī)規(guī)則不是是規(guī)則集集,而而是遺傳傳算法操操縱的內(nèi)內(nèi)部實體體。圖11..3給出出了分類類器系統(tǒng)統(tǒng)的一般般結(jié)構(gòu),,從分分類器系系統(tǒng)看學(xué)學(xué)習(xí),它它由三三層動作作構(gòu)成,,即執(zhí)行子子系統(tǒng)、、信用賦賦值子系系統(tǒng)和發(fā)發(fā)現(xiàn)子系系統(tǒng)。2020-01-1567史忠植高高級級人工智智能分類器系系統(tǒng)發(fā)現(xiàn)[遺傳算法]信用賦值[桶鏈]執(zhí)行[分類器系統(tǒng)]消息來自輸入接口支付消息送出輸出接口（目標(biāo)）來自內(nèi)部監(jiān)控器的消息圖11.3分類器系統(tǒng)的一般結(jié)構(gòu)2020-01-1568史忠植高高級級人工智智能分類器系系統(tǒng)執(zhí)行子系系統(tǒng)處在在最低層層,直直接與環(huán)環(huán)境進(jìn)行行交互。。它與專家系統(tǒng)統(tǒng)相同,,由產(chǎn)生生式規(guī)則則構(gòu)成。。但是,,它們們是消息息傳送,,高度平行行。這類類規(guī)則稱稱作分類類器。分類器系系統(tǒng)中的的學(xué)習(xí),,要求求環(huán)境提提供反饋饋,確確認(rèn)所希希望的狀態(tài)是是否達(dá)到到。系統(tǒng)統(tǒng)將評價價這些規(guī)規(guī)則的有有效性,,這些些活動常常稱作作信用賦賦值。有有些特定定算法專專門用來來實現(xiàn)信信用賦值值,例如,桶桶鏈算算法。最后一層層是發(fā)現(xiàn)現(xiàn)子系統(tǒng)統(tǒng),該該系統(tǒng)必必須產(chǎn)生生新的規(guī)規(guī)則,取取代當(dāng)當(dāng)前用處處不大的的規(guī)則。。通過系系統(tǒng)累積積的經(jīng)驗驗產(chǎn)生規(guī)規(guī)則。系系統(tǒng)根據(jù)據(jù)適應(yīng)值值,使使用遺傳傳算法選選擇、重組和取取代規(guī)則則。2020-01-1569史忠植高高級級人工智智能分類器系系統(tǒng)分類器系系統(tǒng)是平平行執(zhí)行行、消息息傳遞和和基于規(guī)規(guī)則的系系統(tǒng)。在在簡單的的方案中中,消息息采用規(guī)規(guī)定的字字母,全全部為為固定長長度。全全部規(guī)則則采用條條件/動動作形式式。每個個條件規(guī)規(guī)定必須須滿足的的信息,,每個個動作規(guī)規(guī)定當(dāng)條條件滿足足時所發(fā)發(fā)送的消消息。為了方便便,假假設(shè)消息息采用長長度為l的二進(jìn)制制字符串串記錄,,字符符采用子子集{1,0,##}。2020-01-1570史忠植高高級級人工智智能規(guī)則與消消息產(chǎn)生式規(guī)規(guī)則：IF<<條件>THEN<動作>約定：條條件的長長度是固固定的，，用二進(jìn)進(jìn)制數(shù)表表示。定義：Ifsj=1orsj=0,,thenmj=sjIfsj=#,,thenmjcanbeeither1or0.2020-01-1571史忠植高高級級人工智智能規(guī)則與消消息滿足要求求的全部部消息構(gòu)構(gòu)成子集集,即即每個子子集是在在消息空空間的一一個超平平面。分分類器系系統(tǒng)是由由一組分分類器{C1,C2,…,CN}、一個消息息表、輸輸入接口口、輸出出接口構(gòu)構(gòu)成。每每部分的的主要功功能如下下:

(1)輸輸入接接口將當(dāng)當(dāng)前環(huán)境境狀態(tài)翻翻譯成標(biāo)標(biāo)準(zhǔn)消息息。(2)分分類器器根據(jù)規(guī)規(guī)則,規(guī)規(guī)定系系統(tǒng)處理理消息的的過程。。(3)消消息表表包含當(dāng)當(dāng)前全部部消息。。(4)輸出接口口將結(jié)果果消息翻翻譯成效效應(yīng)器動動作,修改環(huán)境境狀態(tài)。。2020-01-1572史忠植高高級級人工智智能分類器系系統(tǒng)的基基本結(jié)構(gòu)構(gòu)分類器消息表(a)全部消息息進(jìn)行條條件測試試條件消息規(guī)約約輸出接口口送到環(huán)境境輸入接口口來自環(huán)境境(a)(b)(b)選中分類類器產(chǎn)生生新消息息2020-01-1573史忠植高高級級人工智智能分類器基基本算法法將輸入接接口全部部消息放放入消息息表。將消息表表中的全全部消息息與全部部分類器器所有條條件比較較,記記錄所有有匹配。。滿足分類類器條件件部分的的每組匹匹配,將將其動動作部分分所規(guī)定定的消息息送到新新的消息息表。用新的消消息表取取代消息息表中的的全部消消息。將消息表表中的消消息翻譯譯成輸出出接口的的要求,,產(chǎn)生生系統(tǒng)當(dāng)當(dāng)前的輸輸出。返回到步步驟(1)。2020-01-1574史忠植高高級級人工智智能簡單的視視覺分類類器系統(tǒng)統(tǒng)視覺向量視野運動向量對象檢測器11110…消息2020-01-1575史忠植高高級級人工智智能性質(zhì)檢測測器規(guī)定定的值1，如果果移動對對象0，其它它(0,0)，如如果對象象在視野野的中間間(1,0)，如如果對象象在中心心的左邊邊(0,1)，如如果對象象在中心心的右邊邊1，如果果系統(tǒng)是是對象的的近鄰0，其它它1，如果果對象很很大0，其它它1，如果果對象是是狹長的的0，其它它2020-01-1576史忠植高高級級人工智智能規(guī)則表示示規(guī)則：IF如果有““捕食((prey)”((small,,moving,nonstripedobject),,處于視野野中間((centered),,非鄰近((nonadjacent),,THEN迅速移向向?qū)ο?(ALIGN),,(FAST).可以表示示為：00############000001//0100000000000000,,ALIGN,FAST.2020-01-1577史忠植高高級級人工智智能網(wǎng)絡(luò)圖[MOVING]][SMALL][NOTSTRIPED][NEAR][FAR]]01001[ALERT]10001[TARGET]]11001[PORSUE]]11010[APPROACH]11011[FLEE]11100[FREEZE]]10010[DANGER]]2020-01-1578史忠植高高級級人工智智能網(wǎng)絡(luò)圖的的規(guī)則表表示MOVING和ALERT之間的箭箭頭：00#################1/01001##############SMALL，NOTSTRIPEDandALERT到TARGET的箭頭：：00###########00######，01001##############//10001###############2020-01-1579史忠植高高級級人工智智能學(xué)習(xí)機(jī)制制分類器系系統(tǒng)使用用兩個學(xué)學(xué)習(xí)機(jī)制制，桶鏈(bucketbrigade)算法。基基于對系系統(tǒng)的貢貢獻(xiàn),對對現(xiàn)有有規(guī)則分分配一個個信用值值。規(guī)則發(fā)現(xiàn)現(xiàn)算法。。這包括括遺傳算算法，該該算法可可產(chǎn)生新新規(guī)則，，用于改改善系統(tǒng)統(tǒng)的知識識庫。2020-01-1580史忠植高高級級人工智智能15.8桶鏈算法法桶鏈(bucketbrigade)算法基于于對系統(tǒng)統(tǒng)的貢獻(xiàn)獻(xiàn),對對現(xiàn)有規(guī)規(guī)則分配配一個信信用值。。主要解解決多條條規(guī)則同同時要求求被激活活時的競競爭問題題。例如：下下面的情情況下應(yīng)應(yīng)該選擇擇哪條規(guī)規(guī)則。0111→01###：0000→###00：：0001→00##0：：11002020-01-1581史忠植高高級級人工智智能主要問題題引入信用用值后的的兩個問問題：當(dāng)多條規(guī)規(guī)則同時時要求被被激活時時，如何何解決競競爭問題題對一規(guī)則則被激活活產(chǎn)生過過作用的的那些規(guī)規(guī)則如何何分配信信用2020-01-1582史忠植高高級級人工智智能桶鏈算法法為解決上上述兩個個問題，，引入拍拍賣行和和票據(jù)交交易所：：當(dāng)有多個個分類器器獲得匹匹配時，，每個分分類器要要出一個個與其強強度成正正比的叫叫價B叫價高的的分類器器被激活活并允許許發(fā)送消消息，同同時通過過票據(jù)交交易所,,將其叫叫價B提供給激激活的分分類器。。如此繼續(xù)續(xù)下去，，一條規(guī)規(guī)則可通通過消費費者獲利利（增加加了強度度），通通過規(guī)則則的不斷斷激活形形成一條條消費者者鏈，直直至最終終消費者者（達(dá)到到目標(biāo)））直接從從環(huán)境中中得到補補償。若鏈中一一條規(guī)則則導(dǎo)致錯錯誤結(jié)論論，則序序列上該該規(guī)則的的強度將將減弱，，并且沿沿著序列列回溯，，從而產(chǎn)產(chǎn)生新的的消費者者鏈2020-01-1583史忠植高高級級人工智智能舉例環(huán)境0111，，強度為為0，叫叫價系數(shù)數(shù)為0..1。索引號分分類器器強強度101###：0000 200200#0：1000 200311###：1000 2004###00：0001 2002020-01-1584史忠植高高級級人工智智能第一步分類器強強度消消息匹匹配叫叫價01###：0000200E2000#0：100020011###：1000200##00：00012002020-01-1585史忠植高高級級人工智智能第二步分類器強強度消消息匹匹配叫叫價01###：0000180000000#0：100020012011###：1000200##00：0001200120兩條規(guī)則則同時激激活2020-01-1586史忠植高高級級人工智智能第三步分類器強強度消消息匹匹配叫叫價01###：000022000#0：1000180110011###：1000200220##00：000118000012182020-01-1587史忠植高高級級人工智智能第四步分類器強強度消消息匹匹配叫叫價01###：000022000#0：100021811###：10001801000##00：00011623162020-01-1588史忠植高高級級人工智智能第五步分類器強強度消消息匹匹配配叫叫價強強度01###：000022022000#0：100021821811###：1000196196##00：00011460001206規(guī)則4達(dá)達(dá)到目標(biāo)標(biāo)獲得補補償60。2020-01-1589史忠植高高級級人工智智能投標(biāo)改變變分類器器的強度度在時間t滿足C送去消息息的分類器對在t-1作用的分類類器投標(biāo)在時間t對分類器器C的支持2020-01-1590史忠植高高級級人工智智能分類器中中的遺傳傳算法遺傳算法法可產(chǎn)生生新規(guī)則則，用于于改善系系統(tǒng)的知知識庫。?？梢栽谌N情況況下應(yīng)用用GA：引入一個個參數(shù)T（時間間隔隔），用用于控制制何時使使用GA。特殊情況況時（如如消息的的條件都都不能匹匹配）使使用GA。系統(tǒng)的性性能太差差。2020-01-1591史忠植高高級級人工智智能算法步驟驟t=0，，隨機(jī)生成成集合Bt，||Bt||=M（（大?。?；計算Bt中全體分分類器的的平均強強度Vt，對每個分分類器賦賦予一個個標(biāo)準(zhǔn)強強度St(Cj)//Vt；；給Bt中的每個個分類器器Cj賦予一個個與其標(biāo)標(biāo)準(zhǔn)強度度成正比比的概率率，并根根據(jù)Bt中的概率率分布，，從Bt中選取n個分類器器，n<<M；對每個分分類器應(yīng)應(yīng)用交叉叉算子，，生成2n個分類器器；將Bt中的2n個強度最最低的分分類器用用新生成成的2n個取代；；t=t++1，轉(zhuǎn)(2))。2020-01-1592史忠植高高級級人工智智能算法說明明算法中S0(Cj)是預(yù)知的的；實現(xiàn)時考考慮結(jié)束束條件；；該算法是是經(jīng)典GA的變種，，其中沒沒有變異異算子；；新分類器器的強度度是由舊舊分類器器的強度度決定的的。2020-01-1593史忠植高高級級人工智智能分類器強強度調(diào)整整算法將與所選選動作相相同的分分類器形形成子集集[M]，稱作動作作集[[A]。將不在[[M]中的其它它分類器器放在集集合NOT[[A]中。在[A]中的全部部分類器器強度減減少一個個分?jǐn)?shù)e。如果系統(tǒng)統(tǒng)決策正正確，則則將贏利利量R分配給[[A]的強度;;如果系統(tǒng)統(tǒng)決策錯錯誤，則則將贏利利量R'(其中0≤R'≤R)分配給[[A]的強度，，從[A]的強度減減少一個個分?jǐn)?shù)p。至少R'和p中的一個個為0。。從NOT[[A]中的強度度減去一一個分?jǐn)?shù)數(shù)t。2020-01-1594史忠植高高級級人工智智能15.9規(guī)則發(fā)現(xiàn)現(xiàn)系統(tǒng)在規(guī)則發(fā)發(fā)現(xiàn)系統(tǒng)統(tǒng)中,學(xué)學(xué)習(xí)經(jīng)經(jīng)常是首首先評價價系統(tǒng)現(xiàn)現(xiàn)有的規(guī)規(guī)則質(zhì)量量,然然后進(jìn)行行修改。。Grefenstette研制了一一種規(guī)則則發(fā)現(xiàn)系系統(tǒng)RUDI。問題求解解級由簡簡化的分分類器系系統(tǒng)組成成。學(xué)習(xí)習(xí)級是對對知識結(jié)結(jié)構(gòu)群體體進(jìn)行遺遺傳算法法操作,每一個表表示為一一組規(guī)則則表。知知識結(jié)構(gòu)構(gòu)的整個個行為控控制這些些結(jié)構(gòu)的的復(fù)制。。在RUDI中,信信用賦值值方法贏贏利共享享規(guī)劃((Profit--SharingPlan,簡稱PSP))和桶鏈算算法(BBA))對每個規(guī)規(guī)則提供供互補的的效用信信息。根根據(jù)期望望的外部部獎勵,,PSP--強度對規(guī)規(guī)則效用用提供更更精確的的評估。。當(dāng)問題題求解時時它被用用作沖突突消解。。與此相相反,BBA--強度表示示規(guī)則之之間的動動態(tài)相關(guān)關(guān)性,規(guī)規(guī)則點點火依次次會聚到相似水水平。這這種測度度可以用用作一組組協(xié)作規(guī)規(guī)則的聚聚類。2020-01-1595史忠植高高級級人工智智能規(guī)則發(fā)現(xiàn)現(xiàn)系統(tǒng)Grefenstette提出一種種強度修修改方案案稱作嬴嬴利共享享規(guī)劃PSP。。在這種方方案中問問題求解解劃分成成情節(jié),,按所所接受的的外部獎獎勵區(qū)分分。如果果任何步步情節(jié)在在投標(biāo)競競爭中獲獲勝,則則認(rèn)為為該規(guī)則則在該情情節(jié)活動動。在情情節(jié)t,PSP修改每個個活動規(guī)規(guī)則Ri的強度Si(t)如下:

Si(t+1))=Si(t)-bSi((t)+bp(t),其中,p(t))稱作在情情節(jié)結(jié)束束時所獲獲得的外外部獎勵勵,即即當(dāng)獲得得外部獎獎勵,從從每個活活動規(guī)則則搜集投投標(biāo),每每個活活動規(guī)則則給出一一部分外外部獎勵勵。考慮慮PSP對給定規(guī)規(guī)則Ri的影響,,它按按照方程程得到:2020