高級人工智能之進化理論

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

1967年，Bagley在他的論文中首次提出了遺傳算法這一術語，并討論了遺傳算法在自動博弈中的應用。1970年，Cavicchio把遺傳算法應用于模式識別中。第一個把遺傳算法應用于函數(shù)優(yōu)化的是Hollstien。

2023/1/175發(fā)展歷史1975年是遺傳算法研究的歷史上十分重要的一年。這一年，Holland出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的適應性》該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極為重要的模式理論（schematatheory），該理論首次確認了結構重組遺傳操作對于獲得隱并行性的重要性。同年，DeJong完成了他的重要論文《遺傳自適應系統(tǒng)的行為分析》。他在該論文中所做的研究工作可看作是遺傳算法發(fā)展過程中的一個里程碑，這是因為他把Holland的模式理論與他的計算使用結合起來。

2023/1/176發(fā)展歷史1989Goldberg對遺傳算法從理論上，方法上和應用上作了系統(tǒng)的總結。1990年，Koza提出了遺傳程序設計（GeneticProgramming）的概念。（用于搜索解決特定問題的最適計算機程序）2023/1/177遺傳算法與自然進化的比較自然界染色體基因等位基因(allele)染色體位置(locus)基因型(genotype)表型(phenotype)遺傳算法字符串字符,特征特征值字符串位置結構參數(shù)集,譯碼結構2023/1/178新達爾文五進化理論的主要論點個體是基本的選擇目標;隨機過程在進化中起重大作用,遺傳變異大部分是偶然現(xiàn)象;基因型變異大部分是重組的產(chǎn)物,特別是突變;逐漸進化可能與表型不連續(xù)有關;不是所有表型變化都是自然選擇的必然結果;進化是在適應中變化的,形式多樣,不僅是基因的變化;選擇是概率型的,而不是決定型的。2023/1/179進化計算的三大主流板塊Holland提出的遺傳算法(GeneticAlgorithm)。Rechenberg和Schwefel提出的進化策略(EvolutionaryStrategies)。Fogel提出的進化規(guī)劃(EvolutionaryProgramming)，又稱為進化程序設計。本章將著重介紹遺傳算法，對進化策略和進化規(guī)劃只作簡單介紹。2023/1/171015.2進化系統(tǒng)統(tǒng)理論的的形式模模型進化在個個體群體體中起作作用。瓦瓦鋌頓(Waddington)指出基因因型和表表型之間間關系的的重要性性(Waddington1974)。群體禁止止異構環(huán)環(huán)境。但但是“后后生環(huán)境境”是多多維空間間。表型型是基因因型和環(huán)環(huán)境的產(chǎn)產(chǎn)物。然然后表型型通過異異構“選選擇環(huán)境境"發(fā)生生作用。。注意，，這種多多維選擇擇環(huán)境與與后生環(huán)環(huán)境空間間是不同同的?，F(xiàn)現(xiàn)在，適適應性是是表型空空間和選選擇環(huán)境境空間的的產(chǎn)物。。它經(jīng)常常被取作作一維，，表示多多少子孫孫對下一一代作出出貢獻。?；谶@種種想法，，莫楞貝貝(Muhlenbein)和肯德曼曼(Kindermann)提出了一一種稱為進化系系統(tǒng)理論論的形式式模型(Muhlenbein1989)。2022/12/3111進化系統(tǒng)統(tǒng)理論的的形式模模型進化的主主要過程程后生環(huán)境境遺傳操作作符選擇環(huán)境境gp2022/12/3112進化系統(tǒng)統(tǒng)理論的的形式模模型其中，g是基因型型p是表型。。基因gi的可能值值稱為等等位基因因。在門德爾爾(Mendel)遺傳學中中，假設設每個基基因有有有限數(shù)的的等位基基因。2022/12/3113進化系統(tǒng)統(tǒng)理論的的形式模模型這個變換換函數(shù)給給出了模模型，說說明表型型的發(fā)展展是通過過基因與環(huán)境境的交互互作用。。變換過程程是高度度非線性性的。2022/12/3114進化系統(tǒng)統(tǒng)理論的的形式模模型質(zhì)量函數(shù)數(shù)q給出了具具體選擇擇環(huán)境ESi下表型的的質(zhì)量，，其定義如如下：質(zhì)量定義義適應度度，用于于達爾文文選擇。。至今已已有三種種具體范范例的通通用模型型，即門德爾遺遺傳學遺傳生態(tài)態(tài)學進化配子子2022/12/3115門德爾遺傳學學在門德爾遺傳傳學中，基因因型被詳細模模型化，而表表型和環(huán)境幾乎被忽忽略。在遺傳傳生態(tài)學中恰好相反。。進化配子論是是從社會生物物學導出的模模型。首先讓我們討討論門德爾遺遺傳學的選擇擇模型。為了了簡單起見，，我們假設一一個基因具有有n等位基因a1,…,an。二倍基因型以以元組(ai,aj)為特征。我我們定義pi,j為總群體中基基因型(ai,aj)的頻度。假設設基因型與表表型相等。質(zhì)質(zhì)量函數(shù)給每每個表型賦值。q(ai,aj)=qi,jqi,j可以被解釋為為出生率減去去死亡率2022/12/3116門德爾遺傳學學假設p’i,j是下一代表型型(ai,aj)的頻度。然后后達爾文選擇根據(jù)選擇擇方程調(diào)整表表型的分布:是群體的平均均適應度。2022/12/3117門德爾遺傳學學設pi是群體中等位位基因的頻率率。如果pi,j=pipj那么，我們得得到在GS中的一個選擇擇方程為2022/12/3118門德爾遺傳學學這個離散的選選擇方程可以以用連續(xù)方程程近似:如果qi,j=qj,i,那么2022/12/3119門德爾遺傳傳學這個方程很很容易被證證明:這個結果稱稱作菲希爾爾(Fisher)基本定理。。它說明平平均適應度度隨適應度度的差別呈呈正比例增增加。實際際上，全部部可能的基基因型僅有有一部分實實現(xiàn)。這就就是遺傳操操縱子探索索基因型空空間的任務務，其個體體數(shù)目相當當小。這些些操縱子是是群體遺傳傳變異性的的來源。最重要的操操縱子是突突變和重組組。2022/12/312015.3達爾文進化化算法根據(jù)定量遺遺傳學，達達爾文進化化算法采用用簡單的突變/選選擇動力學學。達爾文算法法的一般形形式可以描描述如下：：是一代的雙雙親數(shù)目，，為子孫數(shù)目目。整數(shù)稱作“混雜雜”數(shù)。如果兩個雙雙親混合他他們的基因因，則=2。僅是最好的個個體才允許許產(chǎn)生子孫孫。逗號表示雙雙親們沒有有選擇，加加號表示雙雙親有選擇擇。2022/12/312115.3達爾文進化化算法建立原始種種體。通過突變建建立子孫。。選擇：返回到步驟驟(1)。?！?022/12/3122遺傳算法思思想來源于于生物進化化過程,它它是基于于進化過程程中的信息息遺傳機制制和優(yōu)勝劣劣汰的自然然選擇原則則的搜索算算法(以字字符串表示示狀態(tài)空間間)。遺傳傳算法用概概率搜索過過程在該狀狀態(tài)空間中中搜索，產(chǎn)產(chǎn)生新的樣樣本。15.4遺傳算法2022/12/3123遺傳算法的的特點特點：通用魯棒次優(yōu)解、滿滿意解遺傳算法能能解決的問問題：優(yōu)化NP完全NP難高度復雜的的非線性問問題2022/12/3124遺傳傳算算法法遺傳傳算算法法先先將將搜搜索索結結構構編編碼碼為為字字符符串串形形式式,每每個個字字符符串串結結構構被被稱稱為為個個體體。。然后后對對一一組組字字符符串串結結構構(被被稱稱為為一一個個群群體體)進進行行循循環(huán)環(huán)操操作作。。每每次次循循環(huán)環(huán)被被稱稱作作一一代代,包包括括一一個個保保存存字字符符串串中中較較優(yōu)優(yōu)結結構構的的過過程程和和一一個個有有結結構構的的、、隨隨機機的的字字符符串串間間的的信信息息交交換換過過程程。。類似似于于自自然然進進化化，，遺遺傳傳算算法法通通過過作作用用于于染染色色體體上上的的基基因因?qū)ふ艺液煤玫牡娜救旧w體來來求求解解問問題題。。2022/12/3125遺傳算法與自然界相似似，遺傳算法法對求解問題題的本身一無無所知，它所所需要的僅是是對算法所產(chǎn)產(chǎn)生的每個染染色體進行評評價，并基于于適應值來選選擇染色體，，使適應性好好的染色體有有更多的繁殖殖機會。在遺傳算法中中，位字符串串扮演染色體體的作用，單單個位扮演了了基因的作用用，隨機產(chǎn)生生一個體字符符串的初始群群體，每個個個體給予一個個數(shù)值評價，，稱為適應度度，取消低適適應度的個體體，選擇高適適應度的個體體參加操作。。常用的遺傳算算子有復制、、雜交、變異異和反轉。2022/12/3126遺傳算法與傳傳統(tǒng)優(yōu)化算法法的主要不同同遺傳算法不是是直接作用在在參變量集上上,而是利利用參變量集集的某種編碼碼;遺傳算法不是是從單個點,而是在群群體中從一個個點開始搜索索;遺傳算法利用用適應值信息息,無需導導數(shù)或其它輔輔助信息;遺傳算法利用用概率轉移規(guī)規(guī)則,而非非確定性規(guī)則則。2022/12/3127遺傳算法的準準備工作確定表示方案案;確定適應值的的度量;確定控制該算算法的參數(shù)和和變量;確定怎樣指定定結果及程序序運行結束的的標準。2022/12/3128基本遺傳算法法基本遺傳算法法(SimpleGeneticAlgorithm:SGA)又稱為簡單遺遺傳算法，只只使用選擇算算子、交叉算算子和變異算算子這三種基基本的遺傳算算子。其遺傳傳操作簡單、、容易理解，，是其它遺傳傳算法的雛形形和基礎?；具z傳算法法的構成要素素：1、染色體編編碼方法：首首先必須對問問題的解空間間進行編碼，，使之能用遺遺傳算法進行行操作。較常常用的是二進進制編碼方法法，現(xiàn)在使用用非二進制編編碼的也逐漸漸增多。2、適應度函函數(shù)（fitnessfunction，又稱為適應值值／適值函數(shù)數(shù)）用來評價價一個染色體體的好壞。2022/12/3129基本遺遺傳算算法的的構成成要素素3、遺遺傳算算子?選擇算算子(selection)：：又稱為為復制制算子子。按按照某某種策策略從從父代代中挑挑選個個體進進入下下一代代，如如使用用比例例選擇擇、輪輪盤式式選擇擇。?交叉算算子(crossover)：：又稱為為雜交交算子子。將將從群群體中中選擇擇的兩兩個個個體，，按照照某種種策略略使兩兩個個個體相相互交交換部部分染染色體體，從從而形形成兩兩個新新的個個體。。如使使用單單點一一致交交叉。。?變異算算子(mutation)：按照一一定的的概率率（一一般較較?。母淖?nèi)救旧w體中某某些基基因的的值。。2022/12/3130雜交操操作舉舉例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#2022/12/3131變異操作作簡單的變變異操作作過程如如下:每個位置置的字符符變量都都有一個個變異概概率,各各位置置互相獨獨立。通通過隨機機過程選選擇發(fā)生生變異的的位置：：產(chǎn)生一個新新結構,其中是是從從對應位置置的的字符變變量的值域域中隨機選選擇的一個個取值?？煽梢砸酝瑯拥玫降?。2022/12/3132反轉轉操操作作簡單單反反轉轉操操作作的的步步驟驟如如下下:從當當前前群群體體中中隨隨機機選選擇擇一一個個結結構構從中中隨隨機機選選擇擇兩兩個個數(shù)數(shù)i’’和j’’,并定定義義i=min{i',j'},j=max{i',j'};顛倒倒a中位位置置i、、j之間間的的部部分分,產(chǎn)產(chǎn)生生新新的的結結構構2022/12/3133基本本遺遺傳傳算算法法的的構構成成要要素素4、、運運行行參參數(shù)數(shù)N：：群體體大大小小，，即即群群體體中中包包含含的的個個體體的的數(shù)數(shù)量量。。T：：遺傳傳算算法法終終止止的的進進化化代代數(shù)數(shù)。。Pc：交叉叉概概率率，，一一般般取取為為0.4～～0.99。。Pm：變異異概概率率，，一一般般取取為為0.0001～～0.1。。2022/12/3134基本遺傳算法法隨機產(chǎn)生一個個由固定長度度字符串組成成的初始群體體;對于字符串群群體，迭代地地執(zhí)行下述步步驟，直到選選種標準被滿滿足為止：計算群體中的的每個個體字字符串的適應應值;應用下述三種種操作(至少少前兩種)來來產(chǎn)生新的群群體:復制:把現(xiàn)現(xiàn)有的個體字字符串復制到到新的群體中中。雜交:通過過遺傳重組隨隨機選擇兩個個現(xiàn)有的子字字符串,產(chǎn)產(chǎn)生新的字字符串。變異:將現(xiàn)現(xiàn)有字符串中中某一位的字字符隨機變異異。把在后代中出出現(xiàn)的最高適適應值的個體體字符串指定定為遺傳算法法運行的結果果。這一結果果可以是問題題的解(或近近似解)。2022/12/3135基本遺傳算法法流程圖GEN=0概率地選擇遺傳操作隨機創(chuàng)建初始群體計算群體中每個個體的適應值i:=0顯示結果結束GEN:=GEN+1是是否（轉下頁）i=N?GEN=M？12022/12/3136概率地地選擇擇遺傳傳操作作根據(jù)適適應值值選擇一個個個體體完成交交叉i:=i+1i:=i+1復制個個體p(r)選擇（接上上頁））基于適適應值值選擇兩個個個體體把新的的兩個個孩子加到到群體體中p(c)交叉變異p(m)把新的的孩子子加入到群群體中中完成變變異根據(jù)適適應值值選擇一個個個體體把變異異后個個體加入到到群體體中12022/12/3137輪盤盤式式選選擇擇首先先計計算算每每個個個個體體i被選選中中的的概概率率然后后根根據(jù)據(jù)概概率率的的大大小小將將將將圓圓盤盤分分為為n個扇扇形形，，每每個個扇扇形形的的大大小小為為。。選選擇擇時時轉轉動動輪輪盤盤，，參參考考點點r落到扇形形i則選擇個個體i。......p1p2pir2022/12/3138單點一致致交叉首先以概概率pc從種群中中隨機地地選擇兩兩個個體體p1、p2。在{1,2,...,l}內(nèi)隨機選選擇一個個數(shù)i,作為交叉叉的位置置，稱為為交叉點點。然后后將兩個個個體交交叉點后后面的部部分交換換。例如：2022/12/3139一致變異以概率pm對種群中所有有個體的每一一位進行變異異。對于個體pi的第j位，在[0,1]的范圍圍內(nèi)隨機地生生成一個數(shù)r,如果r<pm,則對第j位取反，否則則保持第j位不變。2022/12/3140遺傳算法舉例例問題：求（1）編碼：此時取均長為為5，每個染染色體（2）初始群群體生成：群群體大小視情情況而定，此此處設置為4，隨機產(chǎn)生生四個個體：：編碼：01101，11000，，01000，10011解碼：1324819（3）適應度度評價：2022/12/3141（4）選擇：：選擇概率個體：01101，11000，，01000，10011選擇結果：01101，，11000，11000，10011（5）交叉操操作：發(fā)生交交叉的概率較較大哪兩個個體配配對交叉是隨隨機的交叉點位置的的選取是隨機機的（單點交交叉）2022/12/3142（6）變異：：發(fā)生變異的的概率很小（7）新群體體的產(chǎn)生：保留上一代最最優(yōu)個體，一一般為10%左右，至少少1個用新個體取代代舊個體，隨隨機取代或擇擇優(yōu)取代。11000，，11011，11001，10011（8）重復上上述操作：說明：GA的終止條件一一般人為設置置；GA只能求次優(yōu)解解或滿意解。。分析：按第二二代新群體進進行遺傳操作作，若無變異異，永遠也找找不到最優(yōu)解解——擇優(yōu)取取代有問題。。若隨機的將個個體01101選入新群群體中，有可可能找到最優(yōu)優(yōu)解。2022/12/314315.5遺遺傳算法的理理論基礎1模式的定義遺傳算法的理理論基礎是遺遺傳算法的二二進制表達式式及模式的含含義。模式是是能對染色體體之間的相似似性進行解釋釋的模板。[定義1]設設GA的個體,記集合則稱為為一一個模式，其其中＊是通配配符。即模式(schema)是含有通配符符(*)的一類字符串串的通式表達達。每個“*”可以取取“1”或者者“0”。2022/12/3144模式舉例模式*10101110與以下兩個個字符串匹匹配：而模式*1010＊110與以下四個個字符串匹匹配：2022/12/3145模式式的的定定義義[定定義義2]一一個個模式式s的階階是出出現(xiàn)現(xiàn)在在模模式式中中的的““0””和和““1””的的數(shù)數(shù)目目，，記記為為o(s)。。如：：模模式式“0****””的的階階為為1，，模模式式““10*1*””的的階階為為3。。[定定義義3]一一個個模式式s的長長度度是出出現(xiàn)現(xiàn)在在模模式式中中第第一一個個確確定定位位置置和和最最后后一一個個確確定定位位置置之之間間的的距距離離，，記記為為。如：：模模式式“01***””的的長長度度為為1，，模模式式““0***1””的的長長度度為為3。。2022/12/3146模模式式定理假定在給給定的時時間步t,一個個特定的的模式s在群體體P(t)中包包含由m個代表表串，記記為m=m(s,t)。首先先，我們們暫不考考慮交叉叉和變異異操作。。每個串串根據(jù)適適應值的的大小獲獲得不同同的復制制概率。。串i的的復制概概率為：：（1)2022/12/3147模模式式定理則在群體體P(t+1)中，模模式s的的代表串串的數(shù)量量的期望望值為：：其中，表表示示模式s在t時刻的所所有代表表串的適適應值的的均值，，稱為模模式s的適應值值。（2）2022/12/3148模模式定定理若記P(t)中中所有有個體體的適適應值值的平平均值值為：：（3））則(2)式式可以以表示示為：：2022/12/3149模模式定定理(3)式表表明，，模式式s的的代表表串的的數(shù)目目隨時時間增增長的的幅度度正比比于模模式s的適適應值值與群群體平平均適適應值值的比比值。。即：：適應應值高高于群群體平平均值值的模模式在在下一一代的的代表表串數(shù)數(shù)目將將會增增加，，而適適應值值低于于群體體平均均值的的模式式在下下一代代的代代表串串數(shù)目目將會會減少少。假設模模式的的適應應值為為,其中中c是是一個個常數(shù)數(shù)，則則(3)式可可寫為為：2022/12/3150模模式定定理（4））上式表表明，，在平平均適適應值值之上上（之之下））的模模式，，將會會按指指數(shù)增增長（（衰減減）的的方式式被復復制。。2022/12/3151模模式定定理復制的的結果果并沒沒有生生成新新的模模式。因而，，為了了探索索搜索索空間間中的的未搜搜索部部分，，需要要利用用交叉叉和變變異操操作。。下面先先探索索交叉叉對模模式的的影響響。模式s1=“*1****0”和s2=“***10**”交叉會會改變變模式式的一一部分分，模模式的的長度度越長長，被被破壞壞的概概率越越大。。2022/12/3152模模式定理假定模式s在交叉后不不被破壞的的概率為ps，則：若交叉概率率為pc,則s不被破壞的的概率為2022/12/3153模模式定理（5）所以，再考考慮交叉時時，(3)式可表示示為最后，考慮慮變異算子子對模式的的影響。變變異算子以以概率pm隨機地改變變個體某一一位的值。。只有當o(s)個確定位的的值不被破破壞時，模模式s才不被破壞壞。2022/12/315415.5.2模式定定理模式s在變異后不被被破壞的概率率：Pm<<1,可近似地表示示為2022/12/315515.5.2模式定定理（6）因此，考慮交交叉和變異時時，(3)式式可表示為2022/12/3156模模式式定定理理由(6)我我們們得得到到一一個個重重要要的的定定理理。。[定定理理1]模模式式定定理理(SchemaTheorem)適應應值值在在群群體體適適應應值值之之上上的的、、長長度度較較短短的的、、低低階階的的模模式式在在GA的的迭迭代代中中將將按按指指數(shù)數(shù)增增長長方方式式被被復復制制。。2022/12/3157積積木塊塊假設設Holland和Goldberg在在模式式定理理的基基礎上上提出出了““積木木塊假假設””(BuildingBlockHypothesis):低階、、長度度較短短、高高于平平均適適應度度的模模式(積木木塊)在遺遺傳算算子的的作用用下，，相互互結合合，能能生成成高階階、長長度較較長、、適應應度較較高的的模式式，并并得到到全局局最優(yōu)優(yōu)解。。2022/12/3158遺遺傳傳算法的的收斂性性分析算法的收收斂性可可以定義義如下：：定義：若若算法法在t時刻的種種群xt滿足則稱算法法收斂到到x0。關于遺傳傳算法的的收斂性性，Michalewicz證明了基基于壓縮縮原理的的收斂性性定理。。而Rudolph證明了基基于Markov鏈的收斂斂性定理理。2022/12/315915.6遺傳算法的改改進遺傳算法的局局限性：遺傳算法得到到了廣泛應用用，但也暴露露了一些問題題，如：遺傳傳算法在解決決某些問題時時速度較慢；；遺傳算法對對編碼方案的的依賴性較強強，算法的魯魯棒性不夠好好等。這些問題主要要歸結為：（1）上位(epistasis)效應上位效應包括括兩個方面：：多基因性和和基因多效性性。2022/12/316015.6遺傳算法的的改進（2）編碼碼方案最初使用最最多的是二二進制位串串，但此類類編碼并不不適合一些些實際問題題?，F(xiàn)在人人們已經(jīng)探探索了許多多其它方案案，如浮點點表示、樹樹形表示等等等。（3）積木木塊假設積木塊假設設是否成立立，是否一一定存在短短的、低階階的、高適適應值的積積木塊？若若構成問題題最優(yōu)解的的所有低階階模式的適適應值都較較低，這是是GA很難收斂到到最優(yōu)解，，此類問題題稱為“欺欺騙問題””。2022/12/316115.6遺傳算法法的改進進（4）早早熟收斂斂即GA收斂到一一個局部部最優(yōu)解解。Schraudolph和Belew提出“動動態(tài)參數(shù)數(shù)編碼””方案來來解決早早熟收斂斂問題。。關于遺傳傳算法的的一些改改進措施施，有興興趣的同同學可查查找相關關資料。。2022/12/316215.7遺傳機機器學學習－－－－分類類器系系統(tǒng)機器學學習是是人工工智能能的一一個重重要研研究領領域，，也是是人工工智能能的一一個重重要的的應用用領域域。遺傳機機器學學習(GeneticsBasedMachineLearning,GBML)時將遺遺傳算算法與與機器器學習習系統(tǒng)統(tǒng)相結結合的的產(chǎn)物物。2022/12/3163遺傳機器學學習系統(tǒng)的一般般框架任務子系統(tǒng)統(tǒng)學習子系統(tǒng)統(tǒng)任務檢測器器……任務效應器器執(zhí)行效應器器執(zhí)行檢測器器2022/12/3164匹茲堡方方法和密密西根方方法遺傳機器器學習有有兩種重重要的實實現(xiàn)方法法：一種是由由匹茲堡堡(Pittsburgh)大學的的DeJong和他他的學生生Smith提提出的。。該方法法用整個個規(guī)則集集合表示示一個個個體，GAs維維護一個個包含一一定數(shù)目目的候選選規(guī)則集集的種群群。這種種方法稱稱為匹茲茲堡方法法。2022/12/3165匹茲堡方方法和密密西根方方法另一種方方法是由由密西根根(Michigan)大學學的Holland和和他的學學生Reitman提提出的。。該方法法每個個個體表示示一條規(guī)規(guī)則，而而整個種種群就是是規(guī)則集集。這種種方法稱稱為密西西根方法法。Holland提出的的分類器器系統(tǒng)采采用的是是密西根根方法。。2022/12/3166分類器系系統(tǒng)Holland和他的同同事提出出了一種種分類器器系統(tǒng)的的認知模模型,其其中的規(guī)規(guī)則不是是規(guī)則集集,而而是遺傳傳算法操操縱的內(nèi)內(nèi)部實體體。圖11.3給出出了分類類器系統(tǒng)統(tǒng)的一般般結構,從分分類器系系統(tǒng)看學學習,它它由三三層動作作構成,即執(zhí)行行子系統(tǒng)統(tǒng)、信用用賦值子子系統(tǒng)和和發(fā)現(xiàn)子子系統(tǒng)。。2022/12/3167分類器系統(tǒng)發(fā)現(xiàn)[遺傳算法]信用賦值[桶鏈]執(zhí)行[分類器系統(tǒng)]消息來自輸入接口支付消息送出輸出接口（目標）來自內(nèi)部監(jiān)控器的消息圖11.3分類器系統(tǒng)的一般結構2022/12/3168分類器系統(tǒng)執(zhí)行子系統(tǒng)處處在最低層,直接與環(huán)環(huán)境進行交互互。它與專家系統(tǒng)相同同,由產(chǎn)生式式規(guī)則構成。。但是,它它們是消息傳傳送,高度平行。這這類規(guī)則稱作作分類器。分類器系統(tǒng)中中的學習,要要求環(huán)境提提供反饋,確確認所希望望的狀態(tài)是否達達到。系統(tǒng)將將評價這些規(guī)規(guī)則的有效性性,這些活活動常常稱作信用用賦值。有些些特定算法專專門用來實現(xiàn)現(xiàn)信用賦值,例如,桶鏈鏈算法。最后一層是發(fā)發(fā)現(xiàn)子系統(tǒng),該系統(tǒng)必必須產(chǎn)生新的的規(guī)則,取取代當前用處處不大的規(guī)則則。通過系統(tǒng)統(tǒng)累積的經(jīng)驗驗產(chǎn)生規(guī)則。。系統(tǒng)根據(jù)適適應值,使使用遺傳算法法選擇、重組和取代規(guī)規(guī)則。2022/12/3169分類器系統(tǒng)分類器系統(tǒng)是是平行執(zhí)行、、消息傳遞和和基于規(guī)則的的系統(tǒng)。在簡簡單的方案中中,消息采用用規(guī)定的字母母,全部為為固定長度。。全部規(guī)則采采用條件/動動作形式。每每個條件規(guī)定定必須滿足的的信息,每每個動作規(guī)定定當條件滿足足時所發(fā)送的的消息。為了方方便,假假設消消息采采用長長度為為l的二進進制字字符串串記錄錄,字字符符采用用子集集{1,0,#}。2022/12/3170規(guī)則與與消息息產(chǎn)生式式規(guī)則則：IF<條件>THEN<動作>約定：：條件件的長長度是是固定定的，，用二二進制制數(shù)表表示。。定義：：Ifsj=1orsj=0,thenmj=sjIf2022/12/3171規(guī)則則與與消消息息滿足足要要求求的的全全部部消消息息構構成成子子集集,即即每每個個子子集集是是在在消消息息空空間間的的一一個個超超平平面面。。分分類類器器系系統(tǒng)統(tǒng)是是由由一{C1,C2,…,CN}、一個消息表、輸入接口、輸出接口構成。每部分的主要功能如下:

(1)輸入接口將當前環(huán)境狀態(tài)翻譯成標準消息。

(2)分類器根據(jù)規(guī)則,規(guī)定系統(tǒng)處理消息的過程。

(3)消息表包含當前全部消息。

(4)輸出接口將結果消息翻譯成效應器動作,修改環(huán)境狀態(tài)。2022/12/3172分類類器器系系統(tǒng)統(tǒng)的的基基本本結結構構分類類器器消息表(a)全部消息息進行條條件測試試條件消息規(guī)約約輸出接口口送到環(huán)境境輸入接口口來自環(huán)境境(a)(b)(b)選中分類類器產(chǎn)生生新消息息2022/12/3173分類器基基本算法法將輸入接接口全部部消息放放入消息息表。將消息表表中的全全部消息息與全部部分類器器所有條條件比較較,記記錄所有有匹配。。滿足分類類器條件件部分的的每組匹匹配,將將其動動作部分分所規(guī)定定的消息息送到新新的消息息表。用新的消消息表取取代消息息表中的的全部消消息。將消息表表中的消消息翻譯譯成輸出出接口的的要求,產(chǎn)生生系統(tǒng)當當前的輸輸出。返回到步步驟(1)。2022/12/3174簡單的的視覺覺分類類器系系統(tǒng)視覺向量視野運動向量對象檢測器11110…消息2022/12/3175性質(zhì)檢檢測器器規(guī)定定的值值1，如如果移移動對對象0，其其它(0,0)，如如果對對象在在視野野的中中間(1,0)，如如果對對象在在中心心的左左邊(0,1)，如如果對對象在在中心心的右右邊1，如如果系系統(tǒng)是是對象象的近近鄰0，其其它1，如如果對對象很很大0，其其它1，如如果對對象是是狹長長的0，其其它2022/12/3176規(guī)則表示規(guī)則：IF如果有“捕捕食(prey)”(small,moving,nonstripedobject),處于視野中中間(centered),非鄰近(nonadjacent),THEN迅速移向?qū)ο?ALIGN),(FAST).可以表示為為：ALIGN,FAST.2022/12/3177網(wǎng)絡圖[MOVING][SMALL][NOTSTRIPED][NEAR][FAR]01001[ALERT]10001[TARGET]11001[PORSUE]11010[APPROACH]11011[FLEE]11100[FREEZE]10010[DANGER]2022/12/3178網(wǎng)絡圖的規(guī)規(guī)則表示MOVING和ALERT之間的箭頭頭：00#############1/01001###########SMALL，NOTSTRIPEDandALERT到TARGET的箭頭：00########00####，，01001###########/10001###########2022/12/3179學習機制分類器系統(tǒng)統(tǒng)使用兩個個學習機制制，桶鏈(bucketbrigade)算法?；谟趯ο到y(tǒng)的的貢獻,對對現(xiàn)有規(guī)規(guī)則分配一一個信用值值。規(guī)則發(fā)現(xiàn)算算法。這包包括遺傳算算法，該算算法可產(chǎn)生生新規(guī)則，，用于改善善系統(tǒng)的知知識庫。2022/12/318015.8桶鏈算法桶鏈(bucketbrigade)算法基于對對系統(tǒng)的貢貢獻,對對現(xiàn)有規(guī)則則分配一個個信用值。。主要解決決多條規(guī)則則同時要求求被激活時時的競爭問問題。例如：下面面的情況下下應該選擇擇哪條規(guī)則則。0111→→01##：0000→##00：0001→00#0：11002022/12/3181主要要問問題題引入入信信用用值值后后的的兩兩個個問問題題：：當多多條條規(guī)規(guī)則則同同時時要要求求被被激激活活時時，，如如何何解解決決競競爭爭問問題題對一一規(guī)規(guī)則則被被激激活活產(chǎn)產(chǎn)生生過過作作用用的的那那些些規(guī)規(guī)則則如如何何分分配配信信用用2022/12/3182桶鏈鏈算算法法為解解決決上上述述兩兩個個問問題題，，引引入入拍拍賣賣行行和和票票據(jù)據(jù)交交易易所所：：當有有多多個個分分類類器器獲獲得得匹匹配配時時，，每每個個分分類類器器要要出出一一個個與與其其強強度度成成正正比比的的叫叫價價B叫價價高高的的分分類類器器被被激激活活并并允允許許發(fā)發(fā)送送消消息息，，同同時時通通過過票票據(jù)據(jù)交交易易所所,將將其其叫叫價價B提供供給給激激活活的的分分類類器器。。如此此繼繼續(xù)續(xù)下下去去，，一一條條規(guī)規(guī)則則可可通通過過消消費費者者獲獲利利（（增增加加了了強強度度）），，通通過過規(guī)規(guī)則則的的不不斷斷激激活活形形成成一一條條消消費費者者鏈鏈，，直直至至最最終終消消費費者者（（達達到到目目標標））直直接接從從環(huán)環(huán)境境中中得得到到補補償償。。若鏈鏈中中一一條條規(guī)規(guī)則則導導致致錯錯誤誤結結論論，，則則序序列列上上該該規(guī)規(guī)則則的的強強度度將將減減弱弱，，并并且且沿沿著著序序列列回回溯溯，，從從而而產(chǎn)產(chǎn)生生新新的的消消費費者者鏈鏈2022/12/3183舉例環(huán)境0111，強度為0，叫價系數(shù)數(shù)為0.1。。索引號 分類類器 強度度1 01##：0000 2002 00#0：1000 2003 11##：1000 2004 ##00：0001 2002022/12/3184第一步分類器強強度消消息匹匹配配叫叫價價01##：：0000200E2000#0：：100020011##：：1000200##00：：00012002022/12/3185第二步分類器強強度消消息匹匹配配叫叫價價01##：：0000180000000#0：：100020012011##：：1000200##00：：0001200120兩條規(guī)則同時時激活2022/12/3186第三步步分類器器強強度度消消息息匹匹配叫叫價01##：000022011##：10002002202022/12/3187第四步步分類器器強強度度消消息息匹匹配叫叫價01##：000022000#0：1000218##00：00011623162022/12/3188第五步分類器強強度度消消息匹匹配叫叫價強強度度01##：000022022000#0：100021821811##：1000196196規(guī)則4達到到目標獲得得補償60。2022/12/3189投標改變分分類器的強強度在時間t滿足C送去消息的的分類器對在t-1作用的分類器投標在時間t對分類器C的支持2022/12/3190分類器中的的遺傳算法法遺傳算法可可產(chǎn)生新規(guī)規(guī)則，用于于改善系統(tǒng)統(tǒng)的知識庫庫?？梢栽谌N種情況下應應用GA：引入一個參參數(shù)T（時間間隔）），用于控控制何時使使用GA。特殊情況時時（如消息息的條件都都不能匹配配）使用GA。系統(tǒng)的性能能太差。2022/12/3191算法步驟驟t=0，，隨機生成成集合Bt，|Bt|=M（（大?。?；；計算Bt中全體分分類器的的平均強強度Vt，對每個分分類器賦賦予一個個標準強強度St(Cj)/Vt；；給Bt中的每個個分類器器Cj賦予一個個與其標標準強度度成正比比的概率率，并根根據(jù)Bt中的概率率分布，，從Bt中選取n個分類器器，n<<M；對每個分分類器應應用交叉叉算子，，生成2n個分類器器；將Bt中的2n個強度最最低的分分類器用用新生成成的2n個取代；；t=t+1，轉(2)。2022/12/3192算法說明明算法中S0(Cj)是預知的的；實現(xiàn)時考考慮結束束條件；；該算法是是經(jīng)典GA的變種，，其中沒沒有變異異算子；；新分類器器的強度度是由舊舊分類器器的強度度決定的的。2022/12/3193分類器強強度調(diào)整整算法將與所選選動作相相同的分分類器形形成子集集[M]，稱作動作作集[A]。將不在[M]中的其它它分類器器放在集集合NOT[A]中。在[A]中的全部部分類器器強度減減少一個個分數(shù)e。如果系統(tǒng)統(tǒng)決策正正確，則則將贏利利量R分配給[A]的強度;如果系統(tǒng)統(tǒng)決策錯錯誤，則則將贏利利量R'(其中0≤R'≤R)分配給[A]的強度，，從[A]的強度減減少一個個分數(shù)p。至少R'和p中的一個個為0。。從NOT[A]中的強度度減去一一個分數(shù)數(shù)t。2022/12/319415.9規(guī)則發(fā)現(xiàn)系系統(tǒng)在規(guī)則發(fā)現(xiàn)現(xiàn)系統(tǒng)中,學習經(jīng)經(jīng)常是首先先評價系統(tǒng)統(tǒng)現(xiàn)有的規(guī)規(guī)則質(zhì)量,然后進進行修改。。Grefenstette研制了一種種規(guī)則發(fā)現(xiàn)現(xiàn)系統(tǒng)RUDI。。問題求解級級由簡化的的分類器系系統(tǒng)組成。。學習級是是對知識結結構群體進進行遺傳算算法操作,每一個表示示為一組規(guī)規(guī)則表。知知識結構的的整個行為為控制這些些結構的復復制。在RUDI中,信用用賦值方法法贏利共享享規(guī)劃(Profit-SharingPlan,簡稱PSP)和桶鏈算法法(BBA)對每個規(guī)則則提供互補補的效用信信息。根據(jù)據(jù)期望的外外部獎勵,PSP-強度對規(guī)則則效用提供供更精確的的評估。當當問題求解解時它被用用作沖突消消解。與此此相反,BBA-強度表示規(guī)規(guī)則之間的的動態(tài)相關關性,規(guī)規(guī)則點火依依次會聚到到相似水平平。這種測測度可以用用作一組協(xié)協(xié)作規(guī)則的的聚類。2022/12/3195規(guī)則發(fā)現(xiàn)系系統(tǒng)Grefenstette提出一種強強度修改方方案稱作嬴嬴利共享規(guī)規(guī)劃PSP。在這種方案案中問題求求解劃分成成情節(jié),按按所接受受的外部獎獎勵區(qū)分。。如果任何何步情節(jié)在在投標競爭爭中獲勝,則認為為該規(guī)則在在該情節(jié)活活動。在情情節(jié)t,PSP修改每個活活動規(guī)則Ri的強度Si(t)如下:Si(t+1)=Si(t)-bSi(t)+bp(t),其中,p(t)稱作在情節(jié)節(jié)結束時所所獲得的外外部獎勵,即當獲獲得外部獎獎勵,從每每個活動規(guī)規(guī)則搜集投投標,每每個活動規(guī)規(guī)則給出一一部分外部部獎勵?？伎紤]PSP對給定規(guī)則Ri的影響,它它按照方程得到:2022/12/3196規(guī)則發(fā)現(xiàn)系統(tǒng)統(tǒng)其中,t的范圍圍是在在該情情節(jié)規(guī)規(guī)則Ri是活動動的,即即Si(t)基本上上外部部獎勵勵的權權值平平均p(t),(1-b)作為指指數(shù)衰衰減因因子。。如果果b足夠小小,那那么S(t)具有p(t)的平均均值。。如果果外部部獎勵勵p(t)是常數(shù)數(shù),p*,那么Si收斂到到一個個平衡衡值Si*:2022/12/3197規(guī)則發(fā)發(fā)現(xiàn)系系統(tǒng)在常數(shù)數(shù)贏利利下,PSP將以下下列速速率減減少誤誤差Ei(t)=p*-Si(t)強度每每次改改變,以因子子b減少當當前強強度與與平衡衡強度度之差差。2022/12/3198規(guī)則發(fā)發(fā)現(xiàn)系系統(tǒng)我們看看出,獎獎勵相相當是是常數(shù)數(shù)情況況下,在在PSP下每個個規(guī)則則強度度很快快收斂斂到一一個平平衡強強度,可可以預預測情情節(jié)結結束時時將接接收的的獎勵勵水平平。PSP的一種種可能能的限限制是是它取取決于于這種