高級人工智能

第十三章

進化計算

EvolutionaryComputation2023/10/23史忠植高級人工智能2內容13.1概述13.2進化系統理論的形式模型13.3達爾文進化算法13.4遺傳算法13.5遺傳算法的理論基礎13.6遺傳算法的改進13.7遺傳機器學習—分類器系統13.8桶鏈算法13.9規則發現系統13.10進化策略13.11進化規劃2023/10/23史忠植高級人工智能313.1概述進化計算是通過模擬自然界中生物進化機制進行搜索的一種算法。2023/10/23史忠植高級人工智能4發展歷史進化計算的研究起源于20世紀50年代。1965年，Holland首次提出了人工遺傳操作的重要性，并把這些應用于自然系統和人工系統中。大約在同一時期：Rechenberg和Schwefel提出了進化策略。Fogel提出了進化規劃。2023/10/23史忠植高級人工智能5發展歷史

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

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

2023/10/23史忠植高級人工智能7發展歷史1989Goldberg對遺傳算法從理論上，方法上和應用上作了系統的總結。1990年，Koza提出了遺傳規劃（GeneticProgramming）的概念。（用于搜索解決特定問題的最適計算機程序）2023/10/23史忠植高級人工智能8遺傳算法與自然進化的比較自然界染色體基因等位基因(allele)染色體位置(locus)基因型(genotype)表型(phenotype)遺傳算法字符串字符,特征特征值字符串位置結構參數集,譯碼結構2023/10/23史忠植高級人工智能9新達爾文進化理論的主要論點個體是基本的選擇目標;隨機過程在進化中起重大作用,遺傳變異大部分是偶然現象;基因型變異大部分是重組的產物,特別是突變;逐漸進化可能與表型不連續有關;不是所有表型變化都是自然選擇的必然結果;進化是在適應中變化的,形式多樣,不僅是基因的變化;選擇是概率型的,而不是決定型的。2023/10/23史忠植高級人工智能10進化計算的三大主流板塊Holland提出的遺傳算法(GeneticAlgorithm)。Rechenberg和Schwefel提出的進化策略(EvolutionaryStrategies)。Fogel提出的進化規劃(EvolutionaryProgramming)，又稱為進化程序設計。本章將著重介紹遺傳算法，對進化策略和進化規劃只作簡單介紹。2023/10/23史忠植高級人工智能1113.2進化系統理論的形式模型進化在個體群體中起作用。瓦鋌頓(Waddington)指出基因型和表型之間關系的重要性(Waddington1974)。群體禁止異構環境。但是“后生環境”是多維空間。表型是基因型和環境的產物。然后表型通過異構“選擇環境"發生作用。注意，這種多維選擇環境與后生環境空間是不同的。現在，適應性是表型空間和選擇環境空間的產物。它經常被取作一維，表示多少子孫對下一代作出貢獻。基于這種想法，莫楞貝(Muhlenbein)和肯德曼(Kindermann)提出了一種稱為進化系統理論的形式模型(Muhlenbein1989)。2023/10/23史忠植高級人工智能12

進化系統理論的形式模型進化的主要過程后生環境遺傳操作符選擇環境gp2023/10/23史忠植高級人工智能13進化系統理論的形式模型其中，g是基因型

p是表型。基因gi的可能值稱為等位基因。在門德爾(Mendel)遺傳學中，假設每個基因有有限數的等位基因。2023/10/23史忠植高級人工智能14進化系統理論的形式模型這個變換函數給出了模型，說明表型的發展是通過基因與環境的交互作用。變換過程是高度非線性的。2023/10/23史忠植高級人工智能15進化系統理論的形式模型質量函數q給出了具體選擇環境ESi下表型的質量，其定義如下：質量定義適應度，用于達爾文選擇。至今已有三種具體范例的通用模型，即

門德爾遺傳學

遺傳生態學

進化配子2023/10/23史忠植高級人工智能16

門德爾遺傳學在門德爾遺傳學中，基因型被詳細模型化，而表型和環境幾乎被忽略。在遺傳生態學中恰好相反。進化配子論是從社會生物學導出的模型。首先讓我們討論門德爾遺傳學的選擇模型。為了簡單起見，我們假設一個基因具有n等位基因a1,…,an。二倍基因型以元組(ai,aj)為特征。我們定義pi,j

為總群體中基因型(ai,aj)的頻度。假設基因型與表型相等。質量函數給每個表型賦值。

q(ai,aj)=qi,jqi,j可以被解釋為出生率減去死亡率2023/10/23史忠植高級人工智能17

門德爾遺傳學假設p’i,j是下一代表型(ai,aj)的頻度。然后達爾文選擇根據選擇方程調整表型的分布:是群體的平均適應度。2023/10/23史忠植高級人工智能18

門德爾遺傳學設

pi

是群體中等位基因的頻率。如果

pi,j=pipj那么，我們得到在

GS中的一個選擇方程為

2023/10/23史忠植高級人工智能19

門德爾遺傳學這個離散的選擇方程可以用連續方程近似:

如果qi,j=qj,i,那么2023/10/23史忠植高級人工智能20

門德爾遺傳學這個方程很容易被證明:這個結果稱作菲希爾(Fisher)基本定理。它說明平均適應度隨適應度的差別呈正比例增加。實際上，全部可能的基因型僅有一部分實現。這就是遺傳操縱子探索基因型空間的任務，其個體數目相當小。這些操縱子是群體遺傳變異性的來源。最重要的操縱子是突變和重組。2023/10/23史忠植高級人工智能2113.3達爾文進化算法根據定量遺傳學，達爾文進化算法采用簡單的突變/選擇動力學。達爾文算法的一般形式可以描述如下：

是一代的雙親數目，為子孫數目。整數

稱作“混雜”數。如果兩個雙親混合他們的基因，則=2。僅

是最好的個體才允許產生子孫。逗號表示雙親們沒有選擇，加號表示雙親有選擇。

2023/10/23史忠植高級人工智能2213.3達爾文進化算法建立原始種體。通過突變建立子孫。選擇：返回到步驟(1)。…2023/10/23史忠植高級人工智能23 遺傳算法思想來源于生物進化過程,它是基于進化過程中的信息遺傳機制和優勝劣汰的自然選擇原則的搜索算法(以字符串表示狀態空間)。遺傳算法用概率搜索過程在該狀態空間中搜索，產生新的樣本。13.4遺傳算法2023/10/23史忠植高級人工智能24遺傳算法的特點特點：通用魯棒次優解、滿意解遺傳算法能解決的問題：優化NP完全NP難高度復雜的非線性問題2023/10/23史忠植高級人工智能25遺傳算法遺傳算法先將搜索結構編碼為字符串形式,每個字符串結構被稱為個體。然后對一組字符串結構(被稱為一個群體)進行循環操作。每次循環被稱作一代,包括一個保存字符串中較優結構的過程和一個有結構的、隨機的字符串間的信息交換過程。類似于自然進化，遺傳算法通過作用于染色體上的基因尋找好的染色體來求解問題。2023/10/23史忠植高級人工智能26

遺傳算法與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產生的每個染色體進行評價，并基于適應值來選擇染色體，使適應性好的染色體有更多的繁殖機會。在遺傳算法中，位字符串扮演染色體的作用，單個位扮演了基因的作用，隨機產生一個體字符串的初始群體，每個個體給予一個數值評價，稱為適應度，取消低適應度的個體，選擇高適應度的個體參加操作。常用的遺傳算子有復制、雜交、變異和反轉。2023/10/23史忠植高級人工智能27遺傳算法與傳統優化算法的主要不同遺傳算法不是直接作用在參變量集上,而是利用參變量集的某種編碼;遺傳算法不是從單個點,而是在群體中從一個點開始搜索;遺傳算法利用適應值信息,無需導數或其它輔助信息;遺傳算法利用概率轉移規則,而非確定性規則。2023/10/23史忠植高級人工智能28遺傳算法的準備工作確定表示方案;確定適應值的度量;確定控制該算法的參數和變量;確定怎樣指定結果及程序運行結束的標準。2023/10/23史忠植高級人工智能29基本遺傳算法基本遺傳算法(SimpleGeneticAlgorithm:SGA)又稱為簡單遺傳算法，只使用選擇算子、交叉算子和變異算子這三種基本的遺傳算子。其遺傳操作簡單、容易理解，是其它遺傳算法的雛形和基礎。基本遺傳算法的構成要素：1、染色體編碼方法：首先必須對問題的解空間進行編碼，使之能用遺傳算法進行操作。較常用的是二進制編碼方法，現在使用非二進制編碼的也逐漸增多。2、適應度函數（fitnessfunction，又稱為適應值／適值函數）用來評價一個染色體的好壞。2023/10/23史忠植高級人工智能30基本遺傳算法的構成要素3、遺傳算子?選擇算子(selection)：又稱為復制算子。按照某種策略從父代中挑選個體進入下一代，如使用比例選擇、輪盤式選擇。?交叉算子(crossover)：又稱為雜交算子。將從群體中選擇的兩個個體，按照某種策略使兩個個體相互交換部分染色體，從而形成兩個新的個體。如使用單點一致交叉。?變異算子(mutation)：按照一定的概率（一般較小），改變染色體中某些基因的值。2023/10/23史忠植高級人工智能31雜交操作舉例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#2023/10/23史忠植高級人工智能32變異操作簡單的變異操作過程如下:每個位置的字符變量都有一個變異概率,各位置互相獨立。通過隨機過程選擇發生變異的位置：產生一個新結構,其中是從對應位置的字符變量的值域中隨機選擇的一個取值。可以同樣得到。2023/10/23史忠植高級人工智能33反轉操作簡單反轉操作的步驟如下:從當前群體中隨機選擇一個結構從中隨機選擇兩個數i’和j’,并定義i=min{i',j'},j=max{i',j'};顛倒a中位置i、j之間的部分,產生新的結構2023/10/23史忠植高級人工智能34基本遺傳算法的構成要素4、運行參數N：群體大小，即群體中包含的個體的數量。T：遺傳算法終止的進化代數。Pc：交叉概率，一般取為0.4～0.99。Pm：變異概率，一般取為0.0001～0.1。2023/10/23史忠植高級人工智能35基本遺傳算法隨機產生一個由固定長度字符串組成的初始群體;對于字符串群體，迭代地執行下述步驟，直到選種標準被滿足為止：計算群體中的每個個體字符串的適應值;應用下述三種操作(至少前兩種)來產生新的群體:復制:把現有的個體字符串復制到新的群體中。雜交:通過遺傳重組隨機選擇兩個現有的子字符串,產生新的字符串。變異:將現有字符串中某一位的字符隨機變異。把在后代中出現的最高適應值的個體字符串指定為遺傳算法運行的結果。這一結果可以是問題的解(或近似解)。2023/10/23史忠植高級人工智能36基本遺傳算法流程圖GEN=0概率地選擇遺傳操作隨機創建初始群體計算群體中每個個體的適應值i:=0顯示結果結束GEN:=GEN+1是是否（轉下頁）i=N?GEN=M？12023/10/23史忠植高級人工智能37概率地選擇遺傳操作根據適應值選擇一個個體完成交叉i:=i+1i:=i+1復制個體p(r)選擇（接上頁）基于適應值選擇兩個個體把新的兩個孩子加到群體中p(c)交叉變異p(m)把新的孩子加入到群體中完成變異根據適應值選擇一個個體把變異后個體加入到群體中12023/10/23史忠植高級人工智能38輪盤式選擇首先計算每個個體i被選中的概率然后根據概率的大小將將圓盤分為n個扇形，每個扇形的大小為。選擇時轉動輪盤，參考點r落到扇形i則選擇個體i。......p1p2pir2023/10/23史忠植高級人工智能39單點一致交叉首先以概率pc從種群中隨機地選擇兩個個體p1、p2。在{1,2,...,l}內隨機選擇一個數i,作為交叉的位置，稱為交叉點。然后將兩個個體交叉點后面的部分交換。例如：

01101011000110011001110001100111001011002023/10/23史忠植高級人工智能40一致變異以概率pm對種群中所有個體的每一位進行變異。對于個體pi的第j位，在[0,1]的范圍內隨機地生成一個數r,如果r<pm,則對第j位取反，否則保持第j位不變。2023/10/23史忠植高級人工智能41遺傳算法舉例問題：求（1）編碼：

此時取均長為5，每個染色體（2）初始群體生成：群體大小視情況而定，此處設置為4，隨機產生四個個體：編碼：01101，11000，01000，10011解碼：1324819適應度：16957664361（3）適應度評價：2023/10/23史忠植高級人工智能42（4）選擇：選擇概率個體：01101，11000，01000，10011適應度：16957664361選擇概率：0.140.490.060.31選擇結果：01101，11000，11000，10011（5）交叉操作：發生交叉的概率較大哪兩個個體配對交叉是隨機的交叉點位置的選取是隨機的（單點交叉）0110101100110001101111000110011001110000遺傳算法舉例2023/10/23史忠植高級人工智能43（6）變異：發生變異的概率很小（7）新群體的產生：保留上一代最優個體，一般為10%左右，至少1個用新個體取代舊個體，隨機取代或擇優取代。11000，11011，11001，10011（8）重復上述操作：說明：GA的終止條件一般人為設置；

GA只能求次優解或滿意解。分析：按第二代新群體進行遺傳操作，若無變異，永遠也找不到最優解——擇優取代有問題。若隨機的將個體01101選入新群體中，有可能找到最優解。遺傳算法舉例2023/10/23史忠植高級人工智能4413.5遺傳算法的理論基礎13.5.1模式的定義遺傳算法的理論基礎是遺傳算法的二進制表達式及模式的含義。模式是能對染色體之間的相似性進行解釋的模板。[定義1]設GA的個體,記集合則稱為一個模式，其中＊是通配符。即模式(schema)是含有通配符(*)的一類字符串的通式表達。每個“*”可以取“1”或者“0”。2023/10/23史忠植高級人工智能45模式舉例模式*10101110與以下兩個字符串匹配：010101110110101110而模式*1010＊110與以下四個字符串匹配：0101001100101011101101001101101011102023/10/23史忠植高級人工智能46模式的定義[定義2]一個模式s的階是出現在模式中的“0”和“1”的數目，記為o(s)。如：模式“0****”的階為1，模式“10*1*”的階為3。[定義3]一個模式s的長度是出現在模式中第一個確定位置和最后一個確定位置之間的距離，記為。如：模式“01***”的長度為1，模式“0***1”的長度為3。2023/10/23史忠植高級人工智能47

模式定理假定在給定的時間步t,一個特定的模式s在群體P(t)中包含由m個代表串，記為m=m(s,t)。首先，我們暫不考慮交叉和變異操作。每個串根據適應值的大小獲得不同的復制概率。串i的復制概率為：（1)2023/10/23史忠植高級人工智能48

模式定理則在群體P(t+1)中，模式s的代表串的數量的期望值為：其中，表示模式s在t時刻的所有代表串的適應值的均值，稱為模式s的適應值。（2）2023/10/23史忠植高級人工智能49

模式定理若記P(t)中所有個體的適應值的平均值為：（3）則(2)式可以表示為：2023/10/23史忠植高級人工智能50

模式定理(3)式表明，模式s的代表串的數目隨時間增長的幅度正比于模式s的適應值與群體平均適應值的比值。即：適應值高于群體平均值的模式在下一代的代表串數目將會增加，而適應值低于群體平均值的模式在下一代的代表串數目將會減少。假設模式的適應值為,其中c是一個常數，則(3)式可寫為：2023/10/23史忠植高級人工智能51

模式定理（4）上式表明，在平均適應值之上（之下）的模式，將會按指數增長（衰減）的方式被復制。2023/10/23史忠植高級人工智能52

模式定理復制的結果并沒有生成新的模式。因而，為了探索搜索空間中的未搜索部分，需要利用交叉和變異操作。下面先探索交叉對模式的影響。模式s1=“*1****0”和s2=“***10**”交叉會改變模式的一部分，模式的長度越長，被破壞的概率越大。2023/10/23史忠植高級人工智能53

模式定理假定模式s在交叉后不被破壞的概率為ps，則：若交叉概率為pc,則s不被破壞的概率為2023/10/23史忠植高級人工智能54模式定理（5）所以，再考慮交叉時，(3)式可表示為最后，考慮變異算子對模式的影響。變異算子以概率pm隨機地改變個體某一位的值。只有當o(s)個確定位的值不被破壞時，模式s才不被破壞。2023/10/23史忠植高級人工智能55模式定理模式s在變異后不被破壞的概率：Pm<<1,可近似地表示為2023/10/23史忠植高級人工智能56模式定理（6）因此，考慮交叉和變異時，(3)式可表示為2023/10/23史忠植高級人工智能57模式定理由(6)我們得到一個重要的定理。[定理1]模式定理(SchemaTheorem)適應值在群體適應值之上的、長度較短的、低階的模式在GA的迭代中將按指數增長方式被復制。2023/10/23史忠植高級人工智能58積木塊假設Holland和Goldberg在模式定理的基礎上提出了“積木塊假設”(BuildingBlockHypothesis):低階、長度較短、高于平均適應度的模式(積木塊)在遺傳算子的作用下，相互結合，能生成高階、長度較長、適應度較高的模式，并得到全局最優解。2023/10/23史忠植高級人工智能59遺傳算法的收斂性分析算法的收斂性可以定義如下：定義：若算法在t時刻的種群xt滿足則稱算法收斂到x0。關于遺傳算法的收斂性，Michalewicz證明了基于壓縮原理的收斂性定理。而Rudolph證明了基于Markov鏈的收斂性定理。2023/10/23史忠植高級人工智能60

遺傳算法的改進遺傳算法的局限性：遺傳算法得到了廣泛應用，但也暴露了一些問題，如：遺傳算法在解決某些問題時速度較慢；遺傳算法對編碼方案的依賴性較強，算法的魯棒性不夠好等。這些問題主要歸結為：（1）上位(epistasis)效應上位效應包括兩個方面：多基因性和基因多效性。2023/10/23史忠植高級人工智能61

遺傳算法的改進（2）編碼方案最初使用最多的是二進制位串，但此類編碼并不適合一些實際問題。現在人們已經探索了許多其它方案，如浮點表示、樹形表示等等。（3）積木塊假設積木塊假設是否成立，是否一定存在短的、低階的、高適應值的積木塊？若構成問題最優解的所有低階模式的適應值都較低，這是GA很難收斂到最優解，此類問題稱為“欺騙問題”。2023/10/23史忠植高級人工智能62

遺傳算法的改進（4）早熟收斂即GA收斂到一個局部最優解。Schraudolph和Belew提出“動態參數編碼”方案來解決早熟收斂問題。關于遺傳算法的一些改進措施，有興趣的同學可查找相關資料。2023/10/23史忠植高級人工智能63

遺傳機器學習－分類器系統機器學習是人工智能的一個重要研究領域，也是人工智能的一個重要的應用領域。遺傳機器學習(GeneticsBasedMachineLearning,GBML)時將遺傳算法與機器學習系統相結合的產物。2023/10/23史忠植高級人工智能64遺傳機器學習系統的一般框架任務子系統學習子系統任務檢測器……任務效應器執行效應器執行檢測器2023/10/23史忠植高級人工智能65匹茲堡方法和密西根方法遺傳機器學習有兩種重要的實現方法：一種是由匹茲堡(Pittsburgh)大學的DeJong和他的學生Smith提出的。該方法用整個規則集合表示一個個體，GAs維護一個包含一定數目的候選規則集的種群。這種方法稱為匹茲堡方法。2023/10/23史忠植高級人工智能66匹茲堡方法和密西根方法另一種方法是由密西根(Michigan)大學的Holland和他的學生Reitman提出的。該方法每個個體表示一條規則，而整個種群就是規則集。這種方法稱為密西根方法。Holland提出的分類器系統采用的是密西根方法。2023/10/23史忠植高級人工智能67分類器系統Holland和他的同事提出了一種分類器系統的認知模型,其中的規則不是規則集,而是遺傳算法操縱的內部實體。圖11.3給出了分類器系統的一般結構,從分類器系統看學習,它由三層動作構成,即執行子系統、信用賦值子系統和發現子系統。2023/10/23史忠植高級人工智能68

分類器系統發現[遺傳算法]信用賦值[桶鏈]執行[分類器系統]消息來自輸入接口支付消息送出輸出接口（目標）來自內部監控器的消息圖11.3分類器系統的一般結構2023/10/23史忠植高級人工智能69分類器系統

執行子系統處在最低層,直接與環境進行交互。它與專家系統相同,由產生式規則構成。但是,它們是消息傳送,高度平行。這類規則稱作分類器。

分類器系統中的學習,要求環境提供反饋,確認所希望的狀態是否達到。系統將評價這些規則的有效性,這些活動常常稱作信用賦值。有些特定算法專門用來實現信用賦值,例如,桶鏈算法。

最后一層是發現子系統,該系統必須產生新的規則,取代當前用處不大的規則。通過系統累積的經驗產生規則。系統根據適應值,使用遺傳算法選擇、重組和取代規則。2023/10/23史忠植高級人工智能70分類器系統分類器系統是平行執行、消息傳遞和基于規則的系統。在簡單的方案中,消息采用規定的字母,全部為固定長度。全部規則采用條件/動作形式。每個條件規定必須滿足的信息,每個動作規定當條件滿足時所發送的消息。為了方便,假設消息采用長度為l的二進制字符串記錄,字符采用子集{1,0,#}。2023/10/23史忠植高級人工智能71規則與消息產生式規則：IF<條件>THEN<動作>約定：條件的長度是固定的，用二進制數表示。定義：Ifsj=1orsj=0,thenmj=sjIfsj=#,thenmjcanbeeither1or0.2023/10/23史忠植高級人工智能72規則與消息滿足要求的全部消息構成子集,即每個子集是在消息空間的一個超平面。分類器系統是由一組分類器{C1,C2,…,CN}、一個消息表、輸入接口、輸出接口構成。每部分的主要功能如下:

(1)輸入接口將當前環境狀態翻譯成標準消息。

(2)分類器根據規則,規定系統處理消息的過程。

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

(4)輸出接口將結果消息翻譯成效應器動作,修改環境狀態。2023/10/23史忠植高級人工智能73分類器系統的基本結構分類器消息表(a)全部消息進行條件測試條件消息規約輸出接口送到環境輸入接口來自環境(a)(b)(b)選中分類器產生新消息2023/10/23史忠植高級人工智能74分類器基本算法將輸入接口全部消息放入消息表。將消息表中的全部消息與全部分類器所有條件比較,記錄所有匹配。滿足分類器條件部分的每組匹配,將其動作部分所規定的消息送到新的消息表。用新的消息表取代消息表中的全部消息。將消息表中的消息翻譯成輸出接口的要求,產生系統當前的輸出。返回到步驟(1)。2023/10/23史忠植高級人工智能75簡單的視覺分類器系統視覺向量視野運動向量對象檢測器11110…消息2023/10/23史忠植高級人工智能76性質檢測器規定的值1，如果移動對象0，其它(0,0)，如果對象在視野的中間(1,0)，如果對象在中心的左邊(0,1)，如果對象在中心的右邊1，如果系統是對象的近鄰0，其它1，如果對象很大0，其它1，如果對象是狹長的0，其它2023/10/23史忠植高級人工智能77規則表示規則：IF如果有“捕食(prey)”(small,moving,nonstripedobject),處于視野中間(centered),非鄰近(nonadjacent),THEN迅速移向對象(ALIGN),(FAST).可以表示為：00#########000001/0100000000000000,ALIGN,FAST.2023/10/23史忠植高級人工智能78網絡圖[MOVING][SMALL][NOTSTRIPED][NEAR][FAR]01001[ALERT]10001[TARGET]11001[PORSUE]11010[APPROACH]11011[FLEE]11100[FREEZE]10010[DANGER]2023/10/23史忠植高級人工智能79網絡圖的規則表示MOVING和ALERT之間的箭頭：00#############1/01001###########SMALL，NOTSTRIPEDandALERT到TARGET的箭頭：00########00####，01001###########/10001###########2023/10/23史忠植高級人工智能80學習機制分類器系統使用兩個學習機制，桶鏈(bucketbrigade)算法。基于對系統的貢獻,對現有規則分配一個信用值。規則發現算法。這包括遺傳算法，該算法可產生新規則，用于改善系統的知識庫。2023/10/23史忠植高級人工智能81

桶鏈算法桶鏈(bucketbrigade)算法基于對系統的貢獻,對現有規則分配一個信用值。主要解決多條規則同時要求被激活時的競爭問題。例如：下面的情況下應該選擇哪條規則。0111→01##：0000→##00：0001→00#0：11002023/10/23史忠植高級人工智能82主要問題引入信用值后的兩個問題：當多條規則同時要求被激活時，如何解決競爭問題對一規則被激活產生過作用的那些規則如何分配信用2023/10/23史忠植高級人工智能83桶鏈算法為解決上述兩個問題，引入拍賣行和票據交易所：當有多個分類器獲得匹配時，每個分類器要出一個與其強度成正比的叫價B叫價高的分類器被激活并允許發送消息，同時通過票據交易所,將其叫價B提供給激活的分類器。如此繼續下去，一條規則可通過消費者獲利（增加了強度），通過規則的不斷激活形成一條消費者鏈，直至最終消費者（達到目標）直接從環境中得到補償。若鏈中一條規則導致錯誤結論，則序列上該規則的強度將減弱，并且沿著序列回溯，從而產生新的消費者鏈2023/10/23史忠植高級人工智能84舉例環境0111，強度為0，叫價系數為0.1。索引號 分類器 強度1 01##：0000 2002 00#0：1000 2003 11##：1000 2004 ##00：0001 2002023/10/23史忠植高級人工智能85第一步分類器 強度消息匹配叫價01##：0000200E2000#0：100020011##：1000200##00：00012002023/10/23史忠植高級人工智能86第二步分類器 強度消息匹配叫價01##：0000180000000#0：100020012011##：1000200##00：0001200120兩條規則同時激活2023/10/23史忠植高級人工智能87第三步分類器 強度消息匹配叫價01##：000022000#0：1000180110011##：1000200220##00：000118000012182023/10/23史忠植高級人工智能88第四步分類器 強度消息匹配叫價01##：000022000#0：100021811##：10001801000##00：00011623162023/10/23史忠植高級人工智能89第五步分類器 強度消息匹配叫價強度01##：000022022000#0：100021821811##：1000196196##00：00011460001206規則4達到目標獲得補償60。2023/10/23史忠植高級人工智能90投標改變分類器的強度在時間t滿足C送去消息的分類器對在t-1作用的分類器投標在時間t對分類器C的支持2023/10/23史忠植高級人工智能91分類器中的遺傳算法遺傳算法可產生新規則，用于改善系統的知識庫。可以在三種情況下應用GA：引入一個參數T（時間間隔），用于控制何時使用GA。特殊情況時（如消息的條件都不能匹配）使用GA。系統的性能太差。2023/10/23史忠植高級人工智能92算法步驟t=0，隨機生成集合Bt，|Bt|=M（大小）；計算Bt中全體分類器的平均強度Vt，對每個分類器賦予一個標準強度St(Cj)/Vt；給Bt中的每個分類器Cj賦予一個與其標準強度成正比的概率，并根據Bt中的概率分布，從Bt中選取n個分類器，n<<M；對每個分類器應用交叉算子，生成2n個分類器；將Bt中的2n個強度最低的分類器用新生成的2n個取代；t=t+1，轉(2)。2023/10/23史忠植高級人工智能93算法說明算法中S0(Cj)是預知的；實現時考慮結束條件；該算法是經典GA的變種，其中沒有變異算子；新分類器的強度是由舊分類器的強度決定的。2023/10/23史忠植高級人工智能94分類器強度調整算法將與所選動作相同的分類器形成子集[M]，稱作動作集[A]。將不在[M]中的其它分類器放在集合NOT[A]中。在[A]中的全部分類器強度減少一個分數e。如果系統決策正確，則將贏利量R分配給[A]的強度;如果系統決策錯誤，則將贏利量R'(其中0≤R'≤R)分配給[A]的強度，從[A]的強度減少一個分數p。至少R'和p中的一個為0。從NOT[A]中的強度減去一個分數t。2023/10/23史忠植高級人工智能95

規則發現系統在規則發現系統中,學習經常是首先評價系統現有的規則質量,然后進行修改。Grefenstette研制了一種規則發現系統RUDI。問題求解級由簡化的分類器系統組成。學習級是對知識結構群體進行遺傳算法操作,每一個表示為一組規則表。知識結構的整個行為控制這些結構的復制。在RUDI中,信用賦值方法贏利共享規劃(Profit-SharingPlan,簡稱PSP)和桶鏈算法(BBA)對每個規則提供互補的效用信息。根據期望的外部獎勵,PSP-強度對規則效用提供更精確的評估。當問題求解時它被用作沖突消解。與此相反,BBA-強度表示規則之間的動態相關性,規則點火依次會聚到相似水平。這種測度可以用作一組協作規則的聚類。

2023/10/23史忠植高級人工智能96

規則發現系統

Grefenstette提出一種強度修改方案稱作嬴利共享規劃PSP。在這種方案中問題求解劃分成情節,按所接受的外部獎勵區分。如果任何步情節在投標競爭中獲勝,則認為該規則在該情節活動。在情節t,PSP修改每個活動規則Ri的強度Si(t)如下:

Si(t+1)=Si(t)-bS