第十五章進(jìn)化計(jì)算史忠植中科院計(jì)算所2023/1/171內(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ī)劃2023/1/17215.1概述進(jìn)化計(jì)算是通過模擬自然界中生物進(jìn)化機(jī)制進(jìn)行搜索的一種算法。2023/1/173發(fā)展歷史進(jìn)化計(jì)算的研究起源于20世紀(jì)50年代。1965年，Holland首次提出了人工遺傳操作的重要性，并把這些應(yīng)用于自然系統(tǒng)和人工系統(tǒng)中。大約在同一時(shí)期：Rechenberg和Schwefel提出了進(jìn)化策略。Fogel提出了進(jìn)化規(guī)劃。2023/1/174發(fā)展歷史

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

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

2023/1/176發(fā)展歷史1989Goldberg對(duì)遺傳算法從理論上，方法上和應(yīng)用上作了系統(tǒng)的總結(jié)。1990年，Koza提出了遺傳程序設(shè)計(jì)（GeneticProgramming）的概念。（用于搜索解決特定問題的最適計(jì)算機(jī)程序）2023/1/177遺傳算法與自然進(jìn)化的比較自然界染色體基因等位基因(allele)染色體位置(locus)基因型(genotype)表型(phenotype)遺傳算法字符串字符,特征特征值字符串位置結(jié)構(gòu)參數(shù)集,譯碼結(jié)構(gòu)2023/1/178新達(dá)爾文五進(jìn)化理論的主要論點(diǎn)個(gè)體是基本的選擇目標(biāo);隨機(jī)過程在進(jìn)化中起重大作用,遺傳變異大部分是偶然現(xiàn)象;基因型變異大部分是重組的產(chǎn)物,特別是突變;逐漸進(jìn)化可能與表型不連續(xù)有關(guān);不是所有表型變化都是自然選擇的必然結(jié)果;進(jìn)化是在適應(yīng)中變化的,形式多樣,不僅是基因的變化;選擇是概率型的,而不是決定型的。2023/1/179進(jìn)化計(jì)算的三大主流板塊Holland提出的遺傳算法(GeneticAlgorithm)。Rechenberg和Schwefel提出的進(jìn)化策略(EvolutionaryStrategies)。Fogel提出的進(jìn)化規(guī)劃(EvolutionaryProgramming)，又稱為進(jìn)化程序設(shè)計(jì)。本章將著重介紹遺傳算法，對(duì)進(jìn)化策略和進(jìn)化規(guī)劃只作簡(jiǎn)單介紹。2023/1/171015.2進(jìn)化系統(tǒng)理理論的形式式模型進(jìn)化在個(gè)體體群體中起起作用。瓦瓦鋌頓(Waddington)指出基因型型和表型之之間關(guān)系的的重要性(Waddington1974)。群體禁止異異構(gòu)環(huán)境。。但是“后后生環(huán)境””是多維空空間。表型型是基因型型和環(huán)境的的產(chǎn)物。然然后表型通通過異構(gòu)““選擇環(huán)境境"發(fā)生作作用。注意意，這種多多維選擇環(huán)環(huán)境與后生生環(huán)境空間間是不同的的。現(xiàn)在，，適應(yīng)性是是表型空間間和選擇環(huán)環(huán)境空間的的產(chǎn)物。它它經(jīng)常被取取作一維，，表示多少少子孫對(duì)下下一代作出出貢獻(xiàn)?；谶@種想想法，莫楞楞貝(Muhlenbein)和肯德曼(Kindermann)提出了一種種稱為進(jìn)化系統(tǒng)統(tǒng)理論的形形式模型(Muhlenbein1989)。。2022/12/3111進(jìn)化系統(tǒng)理理論的形式式模型進(jìn)化的主要要過程后生環(huán)境遺傳操作符符選擇環(huán)境gp2022/12/3112進(jìn)化系統(tǒng)理理論的形式式模型其中，g是基因型p是表型?；騡i的可能值稱稱為等位基基因。在門德爾(Mendel)遺傳傳學(xué)學(xué)中中，，假假設(shè)設(shè)每每個(gè)個(gè)基基因因有有有有限限數(shù)數(shù)的的等等位位基基因因。。2022/12/3113進(jìn)化系統(tǒng)統(tǒng)理論的的形式模模型這個(gè)變換換函數(shù)給給出了模模型，說說明表型型的發(fā)展展是通過過基因與環(huán)境境的交互互作用。。變換過程程是高度度非線性性的。2022/12/3114進(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)化配子子2022/12/3115門德爾爾遺傳傳學(xué)在門德德爾遺遺傳學(xué)學(xué)中，，基因因型被被詳細(xì)細(xì)模型型化，，而表表型和和環(huán)境幾幾乎被被忽略略。在在遺傳傳生態(tài)態(tài)學(xué)中恰好好相反反。進(jìn)化配配子論論是從從社會(huì)會(huì)生物物學(xué)導(dǎo)導(dǎo)出的的模型型。首先讓讓我們們討論論門德德爾遺遺傳學(xué)學(xué)的選選擇模模型。。為了了簡(jiǎn)單單起見見，我我們假假設(shè)一一個(gè)基基因具具有n等位基因a

q(ai,aj)=qi,jqi,j可以被解釋為出生率減去死亡率2022/12/3116門德爾遺傳傳學(xué)假設(shè)p’i,j是下一代表表型(ai,aj)的頻度。然然后達(dá)爾文文選擇根據(jù)選選擇方程調(diào)調(diào)整表型的的分布:是群體的平平均適應(yīng)度度。2022/12/3117門德爾遺傳傳學(xué)設(shè)pi是群體中等等位基因的的頻率。如如果pi,j=pipj那么，我們們得到在GS中的一個(gè)選選擇方程為為2022/12/3118門德德爾爾遺遺傳傳學(xué)學(xué)這個(gè)個(gè)離離散散的的選選擇擇方方程程可可以以用用連連續(xù)續(xù)方方程程近近似似:如果果qi,j=qj,i,那么么2022/12/3119門德德爾爾遺遺傳傳學(xué)學(xué)這個(gè)個(gè)方方程程很很容容易易被被證證明明:這個(gè)個(gè)結(jié)結(jié)果果稱稱作作菲菲希希爾爾(Fisher)基本本定定理理。。它它說說明明平平均均適適應(yīng)應(yīng)度度隨隨適適應(yīng)應(yīng)度度的的差差別別呈呈正正比比例例增增加加。。實(shí)實(shí)際際上上，，全全部部可可能能的的基基因因型型僅僅有有一一部部分分實(shí)實(shí)現(xiàn)現(xiàn)。。這這就就是是遺遺傳傳操操縱縱子子探探索索基基因因型型空空間間的的任任務(wù)務(wù)，，其其個(gè)個(gè)體體數(shù)數(shù)目目相相當(dāng)當(dāng)小小。。這這些些操操縱縱子子是是群群體體遺遺傳傳變變異異性性的的來來源源。。最重重要要的的操操縱縱子子是是突突變變和和重重組組。。2022/12/312015.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)表示雙親親們沒有選擇擇，加號(hào)表示示雙親有選擇擇。2022/12/312115.3達(dá)爾文進(jìn)化算算法建立原始種體體。通過突變建立立子孫。選擇：返回到步驟(1)。…2022/12/3122遺傳算法思想想來源于生物物進(jìn)化過程,它是基于于進(jìn)化過程中中的信息遺傳傳機(jī)制和優(yōu)勝勝劣汰的自然然選擇原則的的搜索算法(以字符串表表示狀態(tài)空間間)。遺傳算算法用概率搜搜索過程在該該狀態(tài)空間中中搜索，產(chǎn)生生新的樣本。。15.4遺傳算法2022/12/3123遺傳算法的特特點(diǎn)特點(diǎn)：通用魯棒次優(yōu)解、滿意意解遺傳算法能解解決的問題：：優(yōu)化NP完全NP難高度復(fù)雜的非非線性問題2022/12/3124遺傳算算法遺傳傳算算法法先先將將搜搜索索結(jié)結(jié)構(gòu)構(gòu)編編碼碼為為字字符符串串形形式式,每每個(gè)個(gè)字字符符串串結(jié)結(jié)構(gòu)構(gòu)被被稱稱為為個(gè)個(gè)體體。。然后后對(duì)對(duì)一一組組字字符符串串結(jié)結(jié)構(gòu)構(gòu)(被被稱稱為為一一個(gè)個(gè)群群體體)進(jìn)進(jìn)行行循循環(huán)環(huán)操操作作。。每每次次循循環(huán)環(huán)被被稱稱作作一一代代,包包括括一一個(gè)個(gè)保保存存字字符符串串中中較較優(yōu)優(yōu)結(jié)結(jié)構(gòu)構(gòu)的的過過程程和和一一個(gè)個(gè)有有結(jié)結(jié)構(gòu)構(gòu)的的、、隨隨機(jī)機(jī)的的字字符符串串間間的的信信息息交交換換過過程程。。類似于自自然進(jìn)化化，遺傳傳算法通通過作用用于染色色體上的的基因?qū)ふ液玫牡娜旧w體來求解解問題。。2022/12/3125遺傳算法法與自然界界相似，，遺傳算算法對(duì)求求解問題題的本身身一無所所知，它它所需要要的僅是是對(duì)算法法所產(chǎn)生生的每個(gè)個(gè)染色體體進(jìn)行評(píng)評(píng)價(jià)，并并基于適適應(yīng)值來來選擇染染色體，，使適應(yīng)應(yīng)性好的的染色體體有更多多的繁殖殖機(jī)會(huì)。。在遺傳算算法中，，位字符符串扮演演染色體體的作用用，單個(gè)個(gè)位扮演演了基因因的作用用，隨機(jī)機(jī)產(chǎn)生一一個(gè)體字字符串的的初始群群體，每每個(gè)個(gè)體體給予一一個(gè)數(shù)值值評(píng)價(jià)，，稱為適適應(yīng)度，，取消低低適應(yīng)度度的個(gè)體體，選擇擇高適應(yīng)應(yīng)度的個(gè)個(gè)體參加加操作。。常用的遺遺傳算子子有復(fù)制制、雜交交、變異異和反轉(zhuǎn)轉(zhuǎn)。2022/12/3126遺傳算法法與傳統(tǒng)統(tǒng)優(yōu)化算算法的主主要不同同遺傳算法法不是直直接作用用在參變變量集上上,而而是利用用參變量量集的某某種編碼碼;遺傳算法法不是從從單個(gè)點(diǎn)點(diǎn),而而是在群群體中從從一個(gè)點(diǎn)點(diǎn)開始搜搜索;遺傳算法法利用適適應(yīng)值信信息,無無需導(dǎo)導(dǎo)數(shù)或其其它輔助助信息;遺傳算法法利用概概率轉(zhuǎn)移移規(guī)則,而非非確定性性規(guī)則。。2022/12/3127遺傳算法的的準(zhǔn)備工作作確定表示方方案;確定適應(yīng)值值的度量;確定控制該該算法的參參數(shù)和變量量;確定怎樣指指定結(jié)果及及程序運(yùn)行行結(jié)束的標(biāo)標(biāo)準(zhǔn)。2022/12/3128基本遺傳算算法基本遺傳算算法(SimpleGeneticAlgorithm:SGA)又稱為簡(jiǎn)單單遺傳算法法，只使用用選擇算子子、交叉算算子和變異異算子這三三種基本的的遺傳算子子。其遺傳傳操作簡(jiǎn)單單、容易理理解，是其其它遺傳算算法的雛形形和基礎(chǔ)。?；具z傳算算法的構(gòu)成成要素：1、染色體體編碼方法法：首先必必須對(duì)問題題的解空間間進(jìn)行編碼碼，使之能能用遺傳算算法進(jìn)行操操作。較常常用的是二二進(jìn)制編碼碼方法，現(xiàn)現(xiàn)在使用非非二進(jìn)制編編碼的也逐逐漸增多。。2、適應(yīng)度度函數(shù)（fitnessfunction，，又稱為適應(yīng)應(yīng)值／適值值函數(shù)）用用來評(píng)價(jià)一一個(gè)染色體體的好壞。。2022/12/3129基本遺傳算算法的構(gòu)成成要素3、遺傳算算子?選擇算子(selection)：又稱為復(fù)制制算子。按按照某種策策略從父代代中挑選個(gè)個(gè)體進(jìn)入下下一代，如如使用比例例選擇、輪輪盤式選擇擇。?交叉算子(crossover)：又稱為雜交交算子。將將從群體中中選擇的兩兩個(gè)個(gè)體，，按照某種種策略使兩兩個(gè)個(gè)體相相互交換部部分染色體體，從而形形成兩個(gè)新新的個(gè)體。。如使用單單點(diǎn)一致交交叉。?變異算子(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變異操操作簡(jiǎn)單的的變異異操作作過程程如下下:每個(gè)位位置的的字符符變量量都有有一個(gè)個(gè)變異異概率率,各各位位置互互相獨(dú)獨(dú)立。。通過過隨機(jī)機(jī)過程程選擇擇發(fā)生生變異異的位位置：：產(chǎn)生一一個(gè)新新結(jié)構(gòu)構(gòu),其中是是從從對(duì)應(yīng)應(yīng)位置置的的字字符變變量的的值域域中隨隨機(jī)選選擇的的一個(gè)個(gè)取值值。可可以以同樣樣得到到。2022/12/3132反轉(zhuǎn)操操作簡(jiǎn)單反反轉(zhuǎn)操操作的的步驟驟如下下:從當(dāng)前前群體體中隨隨機(jī)選選擇一一個(gè)結(jié)結(jié)構(gòu)從中隨隨機(jī)選選擇兩兩個(gè)數(shù)數(shù)i’和j’,并定義義i=min{i',j'},j=max{i',j'};顛倒a中位置置i、j之間間的的部部分分,產(chǎn)產(chǎn)生生新新的的結(jié)結(jié)構(gòu)構(gòu)2022/12/3133基本本遺遺傳傳算算法法的的構(gòu)構(gòu)成成要要素素4、、運(yùn)運(yùn)行行參參數(shù)數(shù)N：：群體體大大小小，，即即群群體體中中包包含含的的個(gè)個(gè)體體的的數(shù)數(shù)量量。。T：遺傳算算法終終止的的進(jìn)化化代數(shù)數(shù)。Pc：交叉概概率，，一般般取為為0.4～0.99。。Pm：變異概概率，，一般般取為為0.0001～～0.1。。2022/12/3134基本遺遺傳算算法隨機(jī)產(chǎn)產(chǎn)生一一個(gè)由由固定定長(zhǎng)度度字符符串組組成的的初始始群體體;對(duì)于字字符串串群體體，迭迭代地地執(zhí)行行下述述步驟驟，直直到選選種標(biāo)標(biāo)準(zhǔn)被被滿足足為止止：計(jì)算群群體中中的每每個(gè)個(gè)個(gè)體字字符串串的適適應(yīng)值值;應(yīng)用下下述三三種操操作(至少少前兩兩種)來產(chǎn)產(chǎn)生新新的群群體:復(fù)制:把把現(xiàn)有有的個(gè)個(gè)體字字符串串復(fù)制制到新新的群群體中中。雜交:通通過遺遺傳重重組隨隨機(jī)選選擇兩兩個(gè)現(xiàn)現(xiàn)有的的子字字符串串,產(chǎn)產(chǎn)生新新的字字符串串。變異:將將現(xiàn)有有字符符串中中某一一位的的字符符隨機(jī)機(jī)變異異。把在后后代中中出現(xiàn)現(xiàn)的最最高適適應(yīng)值值的個(gè)個(gè)體字字符串串指定定為遺遺傳算算法運(yùn)運(yùn)行的的結(jié)果果。這這一結(jié)結(jié)果可可以是是問題題的解解(或或近似似解)。2022/12/3135基本遺遺傳算算法流流程圖圖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/12/3136概率地地選擇擇遺傳傳操作作根據(jù)適適應(yīng)值值選擇一個(gè)個(gè)個(gè)體體完成交交叉i:=i+1i:=i+1復(fù)制個(gè)個(gè)體p(r)選擇（接上上頁(yè)））基于適適應(yīng)值值選擇兩個(gè)個(gè)個(gè)體體把新的的兩個(gè)個(gè)孩子加到到群體體中p(c)交叉變異p(m)把新的孩子子加入到群體中中完成變異根據(jù)適應(yīng)值值選擇一個(gè)個(gè)體體把變異后個(gè)個(gè)體加入到群體體中12022/12/3137輪盤式選擇擇首先計(jì)算每每個(gè)個(gè)體i被選中的概概率然后根據(jù)概概率的大小小將將圓盤盤分為n個(gè)扇形，每每個(gè)扇形的的大小為。。選選擇時(shí)轉(zhuǎn)動(dòng)動(dòng)輪盤，參參考點(diǎn)r落到扇形i則選擇個(gè)體體i。......p1p2pir2022/12/3138單點(diǎn)點(diǎn)一一致致交交叉叉首先以概率pc從種群中隨機(jī)機(jī)地選擇兩個(gè)個(gè)個(gè)體p1、p2。在{1,2,...,l}內(nèi)隨機(jī)選擇一一個(gè)數(shù)i,作為交叉的位位置，稱為交交叉點(diǎn)。然后后將兩個(gè)個(gè)體體交叉點(diǎn)后面面的部分交換換。例如：2022/12/3139一致變異以概率pm對(duì)種群中所有有個(gè)體的每一一位進(jìn)行變異異。對(duì)于個(gè)體pi的第j位，在[0,1]的范圍圍內(nèi)隨機(jī)地生生成一個(gè)數(shù)r,如果r<pm,則對(duì)第j位取反，否則則保持第j位不變。2022/12/3140遺傳算法舉例例問題：求（1）編碼：此時(shí)取取均長(zhǎng)長(zhǎng)為5，每每個(gè)染染色體體（2））初始始群體體生成成：群群體大大小視視情況況而定定，此此處設(shè)設(shè)置為為4，，隨機(jī)機(jī)產(chǎn)生生四個(gè)個(gè)個(gè)體體：編碼：：01101，11000，01000，10011解碼：：1324819適應(yīng)度（3））適應(yīng)應(yīng)度評(píng)評(píng)價(jià)：：2022/12/3141（4））選擇擇：選選擇概概率個(gè)體：：01101，11000，01000，10011適應(yīng)度選擇概概率：選擇結(jié)結(jié)果：：01101，，11000，，11000，，10011（5））交叉叉操作作：發(fā)發(fā)生交交叉的的概率率較大大哪兩個(gè)個(gè)個(gè)體體配對(duì)對(duì)交叉叉是隨隨機(jī)的的交叉點(diǎn)點(diǎn)位置置的選選取是是隨機(jī)機(jī)的（（單點(diǎn)點(diǎn)交叉叉）2022/12/3142（6））變異異：發(fā)發(fā)生變變異的的概率率很小?。?））新群群體的的產(chǎn)生生：保留上上一代代最優(yōu)優(yōu)個(gè)體體，一一般為為10%左左右，，至少少1個(gè)個(gè)用新個(gè)個(gè)體取取代舊舊個(gè)體體，隨隨機(jī)取取代或或擇優(yōu)優(yōu)取代代。11000，11011，11001，10011（8））重復(fù)復(fù)上述述操作作：說明：：GA的終止條件件一般人為為設(shè)置；GA只能求次優(yōu)優(yōu)解或滿意意解。分析：按第第二代新群群體進(jìn)行遺遺傳操作，，若無變異異，永遠(yuǎn)也也找不到最最優(yōu)解———擇優(yōu)取代代有問題。。若隨機(jī)的將將個(gè)體01101選選入新群體體中，有可可能找到最最優(yōu)解。2022/12/314315.5遺遺傳算法法的理論基基礎(chǔ)1模式的定義義遺傳算法的的理論基礎(chǔ)礎(chǔ)是遺傳算算法的二進(jìn)進(jìn)制表達(dá)式式及模式的的含義。模模式是能對(duì)對(duì)染色體之之間的相似似性進(jìn)行解解釋的模板板。[定義1]設(shè)GA的個(gè)體,記記集合則稱為為一個(gè)個(gè)模式，其其中＊是通通配符。即模式(schema)是含有通配配符(*)的一類字字符串的的通式表表達(dá)。每每個(gè)“*”可可以取““1”或或者“0”。2022/12/3144模式舉例模式*10101110與以下兩個(gè)個(gè)字符串匹匹配：而模式*1010＊110與以下四個(gè)個(gè)字符串匹匹配：2022/12/3145模式的定義義[定義2]一個(gè)模式s的階是出現(xiàn)在模模式中的““0”和““1”的數(shù)數(shù)目，記為為o(s)。。如：模式“0****”的階階為1，模模式“10*1*””的階為3。[定義3]一個(gè)模式s的長(zhǎng)度是出現(xiàn)在模模式中第一一個(gè)確定位位置和最后后一個(gè)確定定位置之間間的距離，，記為。如：模式“01***”的長(zhǎng)長(zhǎng)度為1，，模式“0***1”的長(zhǎng)度度為3。2022/12/3146模模式定理假定在給定定的時(shí)間步步t,一個(gè)個(gè)特定的模模式s在群群體P(t)中包含含由m個(gè)代代表串，記記為m=m(s,t)。首先先，我們暫暫不考慮交交叉和變異異操作。每每個(gè)串根據(jù)據(jù)適應(yīng)值的的大小獲得得不同的復(fù)復(fù)制概率。。串i的復(fù)復(fù)制概率為為：（1)2022/12/3147模模式式定定理理則在在群群體體P(t+1)中中，，模模式式s的的代代表表串串的的數(shù)數(shù)量量的的期期望望值值為為：：其中中，，表表示示模模式式s在t時(shí)刻刻的的所所有有代代表表串串的的適適應(yīng)應(yīng)值值的的均均值值，，稱稱為為模模式式s的適適應(yīng)應(yīng)值值。。（2））2022/12/3148模模式定定理若記P(t)中中所有有個(gè)體體的適適應(yīng)值值的平平均值值為：：（3））則(2)式式可以以表示示為：：2022/12/3149模模式定定理(3)式表表明，，模式式s的的代表表串的的數(shù)目目隨時(shí)時(shí)間增增長(zhǎng)的的幅度度正比比于模模式s的適適應(yīng)值值與群群體平平均適適應(yīng)值值的比比值。。即：：適應(yīng)應(yīng)值高高于群群體平平均值值的模模式在在下一一代的的代表表串?dāng)?shù)數(shù)目將將會(huì)增增加，，而適適應(yīng)值值低于于群體體平均均值的的模式式在下下一代代的代代表串串?dāng)?shù)目目將會(huì)會(huì)減少少。假設(shè)模模式的的適應(yīng)應(yīng)值為為,其中中c是是一個(gè)個(gè)常數(shù)數(shù)，則則(3)式可可寫為為：2022/12/3150模模式式定理（4）上式表明明，在平平均適應(yīng)應(yīng)值之上上（之下下）的模模式，將將會(huì)按指指數(shù)增長(zhǎng)長(zhǎng)（衰減減）的方方式被復(fù)復(fù)制。2022/12/3151模模式式定理復(fù)制的結(jié)結(jié)果并沒沒有生成成新的模模式。因而，為為了探索索搜索空空間中的的未搜索索部分，，需要利利用交叉叉和變異異操作。。下面先探索交交叉對(duì)模式的的影響。模式s1=“*1****0”和s2=“***10**”交叉會(huì)改變模模式的一部分分，模式的長(zhǎng)長(zhǎng)度越長(zhǎng)，被被破壞的概率率越大。2022/12/3152模模式定理假定模式s在交叉后不不被破壞的的概率為ps，則：若交叉概率率為pc,則s不被破壞的的概率為2022/12/315315.5.2模式定定理（5）所以，再考慮慮交叉時(shí)，(3)式可表表示為最后，考慮變變異算子對(duì)模模式的影響。。變異算子以以概率pm隨機(jī)地改變個(gè)個(gè)體某一位的的值。只有當(dāng)當(dāng)o(s)個(gè)確定位的值值不被破壞時(shí)時(shí)，模式s才不被破壞。。2022/12/315415.5.2模式定定理模式s在變異后不被被破壞的概率率：Pm<<1,可近似地表示示為2022/12/315515.5.2模式定定理（6）因此，考慮交交叉和變異時(shí)時(shí)，(3)式式可表示為2022/12/315615.5.2模式定定理由(6)我們們得到一個(gè)重重要的定理。。[定理1]模模式定理(SchemaTheorem)適應(yīng)值在群體體適應(yīng)值之上上的、長(zhǎng)度較較短的、低階階的模式在GA的迭代中中將按指數(shù)增增長(zhǎng)方式被復(fù)復(fù)制。2022/12/315715.5.3積木塊塊假設(shè)Holland和Goldberg在模式定理理的基礎(chǔ)上提提出了“積木木塊假設(shè)”(BuildingBlockHypothesis):低階、長(zhǎng)度較較短、高于平平均適應(yīng)度的的模式(積木木塊)在遺傳傳算子的作用用下，相互結(jié)結(jié)合，能生成成高階、長(zhǎng)度度較長(zhǎng)、適應(yīng)應(yīng)度較高的模模式，并得到到全局最優(yōu)解解。2022/12/315815.5.4遺傳算算法的收斂性性分析算法的收斂性性可以定義如如下：定義：若算算法在t時(shí)刻的種群xt滿足則稱算法收斂斂到x0。關(guān)于遺傳算法法的收斂性，，Michalewicz證明了基于壓壓縮原理的收收斂性定理。。而Rudolph證明了基于Markov鏈的收斂性定定理。2022/12/315915.6遺傳算算法的的改進(jìn)進(jìn)遺傳算算法的的局限限性：：遺傳算算法得得到了了廣泛泛應(yīng)用用，但但也暴暴露了了一些些問題題，如如：遺遺傳算算法在在解決決某些些問題題時(shí)速速度較較慢；；遺傳傳算法法對(duì)編編碼方方案的的依賴賴性較較強(qiáng)，，算法法的魯魯棒性性不夠夠好等等。這些問問題主主要?dú)w歸結(jié)為為：（1））上位位(epistasis)效應(yīng)上位效效應(yīng)包包括兩兩個(gè)方方面：：多基基因性性和基基因多多效性性。2022/12/316015.6遺傳算算法的的改進(jìn)進(jìn)（2））編碼碼方案案最初使使用最最多的的是二二進(jìn)制制位串串，但但此類類編碼碼并不不適合合一些些實(shí)際際問題題。現(xiàn)現(xiàn)在人人們已已經(jīng)探探索了了許多多其它它方案案，如如浮點(diǎn)點(diǎn)表示示、樹樹形表表示等等等。。（3））積木木塊假假設(shè)積木塊塊假設(shè)設(shè)是否否成立立，是是否一一定存存在短短的、、低階階的、、高適適應(yīng)值值的積積木塊塊？若若構(gòu)成成問題題最優(yōu)優(yōu)解的的所有有低階階模式式的適適應(yīng)值值都較較低，，這是是GA很難收收斂到到最優(yōu)優(yōu)解，，此類類問題題稱為為“欺欺騙問問題””。2022/12/316115.6遺傳算法的的改進(jìn)（4）早熟熟收斂即GA收斂到一個(gè)個(gè)局部最優(yōu)優(yōu)解。Schraudolph和Belew提出“動(dòng)態(tài)態(tài)參數(shù)編碼碼”方案來來解決早熟熟收斂問題題。關(guān)于遺傳算算法的一些些改進(jìn)措施施，有興趣趣的同學(xué)可可查找相關(guān)關(guān)資料。2022/12/316215.7遺傳機(jī)器學(xué)學(xué)習(xí)

－－－分類器系系統(tǒng)機(jī)器學(xué)習(xí)是是人工智能能的一個(gè)重重要研究領(lǐng)領(lǐng)域，也是是人工智能能的一個(gè)重重要的應(yīng)用用領(lǐng)域。遺傳機(jī)器學(xué)學(xué)習(xí)(GeneticsBasedMachineLearning,GBML)時(shí)將遺傳算算法與機(jī)器器學(xué)習(xí)系統(tǒng)統(tǒng)相結(jié)合的的產(chǎn)物。2022/12/3163遺傳機(jī)器器學(xué)習(xí)系統(tǒng)的一一般框架架任務(wù)子系系統(tǒng)學(xué)習(xí)子系系統(tǒng)任務(wù)檢測(cè)測(cè)器……任務(wù)效應(yīng)應(yīng)器執(zhí)行效應(yīng)應(yīng)器執(zhí)行檢測(cè)測(cè)器2022/12/3164匹茲堡方方法和密密西根方方法遺傳機(jī)器器學(xué)習(xí)有有兩種重重要的實(shí)實(shí)現(xiàn)方法法：一種是由由匹茲堡堡(Pittsburgh)大學(xué)的的DeJong和他他的學(xué)生生Smith提提出的。。該方法法用整個(gè)個(gè)規(guī)則集集合表示示一個(gè)個(gè)個(gè)體，GAs維維護(hù)一個(gè)個(gè)包含一一定數(shù)目目的候選選規(guī)則集集的種群群。這種種方法稱稱為匹茲茲堡方法法。2022/12/3165匹茲堡方方法和密密西根方方法另一種方方法是由由密西根根(Michigan)大學(xué)學(xué)的Holland和和他的學(xué)學(xué)生Reitman提提出的。。該方法法每個(gè)個(gè)個(gè)體表示示一條規(guī)規(guī)則，而而整個(gè)種種群就是是規(guī)則集集。這種種方法稱稱為密西西根方法法。Holland提出的的分類器器系統(tǒng)采采用的是是密西根根方法。。2022/12/3166分類器系系統(tǒng)Holland和他的同同事提出出了一種種分類器器系統(tǒng)的的認(rèn)知模模型,其其中的規(guī)規(guī)則不是是規(guī)則集集,而而是遺傳傳算法操操縱的內(nèi)內(nèi)部實(shí)體體。圖11.3給出出了分類類器系統(tǒng)統(tǒng)的一般般結(jié)構(gòu),從分分類器系系統(tǒng)看學(xué)學(xué)習(xí),它它由三三層動(dòng)作作構(gòu)成,即執(zhí)行行子系統(tǒng)統(tǒng)、信用用賦值子子系統(tǒng)和和發(fā)現(xiàn)子子系統(tǒng)。。2022/12/3167分類器系系統(tǒng)發(fā)現(xiàn)[遺傳算法]信用賦值[桶鏈]執(zhí)行[分類器系統(tǒng)]消息來自輸入接口支付消息送出輸出接口（目標(biāo)）來自內(nèi)部監(jiān)控器的消息圖11.3分類器系統(tǒng)的一般結(jié)構(gòu)2022/12/3168分類器器系統(tǒng)統(tǒng)執(zhí)行子子系統(tǒng)統(tǒng)處在在最低低層,直直接與與環(huán)境境進(jìn)行行交互互。它它與專家系系統(tǒng)相相同,由產(chǎn)產(chǎn)生式式規(guī)則則構(gòu)成成。但但是,它它們是是消息息傳送送,高度平平行。。這類類規(guī)則則稱作作分類類器。。分類器器系統(tǒng)統(tǒng)中的的學(xué)習(xí)習(xí),要要求求環(huán)境境提供供反饋饋,確確認(rèn)認(rèn)所希希望的狀態(tài)態(tài)是否否達(dá)到到。系系統(tǒng)將將評(píng)價(jià)價(jià)這些些規(guī)則則的有有效性性,這這些些活動(dòng)動(dòng)常常稱稱作信信用賦賦值。。有些些特定定算法法專門門用來來實(shí)現(xiàn)現(xiàn)信用用賦值值,例如,桶桶鏈算算法。。最后一一層是是發(fā)現(xiàn)現(xiàn)子系系統(tǒng),該該系統(tǒng)統(tǒng)必須須產(chǎn)生生新的的規(guī)則則,取取代代當(dāng)前前用處處不大大的規(guī)規(guī)則。。通過過系統(tǒng)統(tǒng)累積積的經(jīng)經(jīng)驗(yàn)產(chǎn)產(chǎn)生規(guī)規(guī)則。。系統(tǒng)統(tǒng)根據(jù)據(jù)適應(yīng)應(yīng)值,2022/12/3169分類器器系統(tǒng)統(tǒng)分類器器系統(tǒng)統(tǒng)是平平行執(zhí)執(zhí)行、、消息息傳遞遞和基基于規(guī)規(guī)則的的系統(tǒng)統(tǒng)。在在簡(jiǎn)單單的方方案中中,消消息采采用規(guī)規(guī)定的的字母母,全全部部為固固定長(zhǎng)長(zhǎng)度。。全部部規(guī)則則采用用條件件/動(dòng)動(dòng)作形形式。。每個(gè)個(gè)條件件規(guī)定定必須須滿足足的信信息,每每個(gè)動(dòng)動(dòng)作規(guī)規(guī)定當(dāng)當(dāng)條件件滿足足時(shí)所所發(fā)送送的消消息。。為了方方便,假假設(shè)消消息采采用長(zhǎng)長(zhǎng)度為為l的二進(jìn)進(jìn)制字字符串串記錄錄,字字符符采用用子集集{1,0,#}。2022/12/3170規(guī)則與與消息息產(chǎn)生式式規(guī)則則：IF<條件>THEN<動(dòng)作>約定：：條件件的長(zhǎng)長(zhǎng)度是是固定定的，，用二二進(jìn)制制數(shù)表表示。。定義：：IfIfsj=#,thenmjcanbeeither1or0.2022/12/3171規(guī)則與與消息息滿足要要求的的全部部消息息構(gòu)成成子集集,即即每每個(gè)子子集是是在消消息空空間的的一個(gè)個(gè)超平平面。。分類類器系系統(tǒng)是是由一一組分分類器器{C1,C2,…,CN}、一個(gè)消消息表表、輸輸入接接口、、輸出出接口口構(gòu)成成。每每部分分的主主要功功能如如下:(1)輸輸入入接接口口將將當(dāng)當(dāng)前前環(huán)環(huán)境境狀狀態(tài)態(tài)翻翻譯譯成成標(biāo)標(biāo)準(zhǔn)準(zhǔn)消消息息。。(2)分分類類器器根根據(jù)據(jù)規(guī)規(guī)則則,規(guī)規(guī)定定系系統(tǒng)統(tǒng)處處理理消消息息的的過過程程。。(3)消消息息表表包包含含當(dāng)當(dāng)前前全全部部消消息息。。(4)輸出接口口將結(jié)果果消息翻翻譯成效效應(yīng)器動(dòng)動(dòng)作,修改環(huán)境境狀態(tài)。。2022/12/3172分類器系系統(tǒng)的基基本結(jié)構(gòu)構(gòu)分類器消息表(a)全部消息息進(jìn)行條條件測(cè)試試條件消息規(guī)約輸出接口送到環(huán)境輸入接口來自環(huán)境(a)(b)(b)選中分類器器產(chǎn)生新消消息2022/12/3173分類器基本本算法將輸入接口口全部消息息放入消息息表。將消息表中中的全部消消息與全部部分類器所所有條件比比較,記記錄所有匹匹配。滿足分類器器條件部分分的每組匹匹配,將將其動(dòng)作部部分所規(guī)定定的消息送送到新的消消息表。用新的消息息表取代消消息表中的的全部消息息。將消息表中中的消息翻翻譯成輸出出接口的要要求,產(chǎn)產(chǎn)生系統(tǒng)當(dāng)當(dāng)前的輸出出。返回到步驟驟(1)。。2022/12/3174簡(jiǎn)單的視覺分分類器系統(tǒng)視覺向量視野運(yùn)動(dòng)向量對(duì)象檢測(cè)器11110…消息2022/12/3175性質(zhì)檢測(cè)器規(guī)規(guī)定的值1，如果移動(dòng)動(dòng)對(duì)象0，其它(0,0)，，如果對(duì)象在在視野的中間間(1,0)，，如果對(duì)象在在中心的左邊邊(0,1)，，如果對(duì)象在在中心的右邊邊1，如果系統(tǒng)統(tǒng)是對(duì)象的近近鄰0，其它1，如果對(duì)象象很大0，其它1，如果對(duì)象象是狹長(zhǎng)的0，其它2022/12/3176規(guī)則表示規(guī)則：IF如果有“捕食食(prey)””(small,moving,nonstripedobject),處于視野中間間(centered),非鄰近(nonadjacent),THEN迅速移向?qū)ο笙?ALIGN),(FAST).可以表示為：：ALIGN,FAST.2022/12/3177網(wǎng)絡(luò)圖[MOVING][SMALL][NOTSTRIPED][NEAR][FAR]01001[ALERT]10001[TARGET]11001[PORSUE]11010[APPROACH]11011[FLEE]11100[FREEZE]10010[DANGER]2022/12/3178網(wǎng)絡(luò)絡(luò)圖圖的的規(guī)規(guī)則則表表示示MOVING和ALERT之間間的的箭箭頭頭：：00#############1/01001###########SMALL，，NOTSTRIPEDandALERT到TARGET的箭箭頭頭：：00########00####，，01001###########/10001###########2022/12/3179學(xué)習(xí)習(xí)機(jī)機(jī)制制分類類器器系系統(tǒng)統(tǒng)使使用用兩兩個(gè)個(gè)學(xué)學(xué)習(xí)習(xí)機(jī)機(jī)制制，，桶鏈鏈(bucketbrigade)算法法。。基基于于對(duì)對(duì)系系統(tǒng)統(tǒng)的的貢貢獻(xiàn)獻(xiàn),對(duì)對(duì)現(xiàn)現(xiàn)有有規(guī)規(guī)則則分分配配一一個(gè)個(gè)信信用用值值。。規(guī)則則發(fā)發(fā)現(xiàn)現(xiàn)算算法法。。這這包包括括遺遺傳傳算算法法，，該該算算法法可可產(chǎn)產(chǎn)生生新新規(guī)規(guī)則則，，用用于于改改善善系系統(tǒng)統(tǒng)的的知知識(shí)識(shí)庫(kù)庫(kù)。。2022/12/318015.8桶鏈鏈算算法法桶鏈鏈(bucketbrigade)算法法基基于于對(duì)對(duì)系系統(tǒng)統(tǒng)的的貢貢獻(xiàn)獻(xiàn),對(duì)對(duì)現(xiàn)現(xiàn)有有規(guī)規(guī)則則分分配配一一個(gè)個(gè)信信用用值值。。主主要要解解決決多多條條規(guī)規(guī)則則同同時(shí)時(shí)要要求求被被激激活活時(shí)時(shí)的的競(jìng)競(jìng)爭(zhēng)爭(zhēng)問問題題。。例如如：：下下面面的的情情況況下下應(yīng)應(yīng)該該選選擇擇哪哪條條規(guī)規(guī)則則。。0111→→01##：：0000→##00：：0001→00#0：：11002022/12/3181主要問問題引入信信用值值后的的兩個(gè)個(gè)問題題：當(dāng)多條條規(guī)則則同時(shí)時(shí)要求求被激激活時(shí)時(shí)，如如何解解決競(jìng)競(jìng)爭(zhēng)問問題對(duì)一規(guī)規(guī)則被被激活活產(chǎn)生生過作作用的的那些些規(guī)則則如何何分配配信用用2022/12/3182桶鏈算算法為解決決上述述兩個(gè)個(gè)問題題，引引入拍拍賣行行和票票據(jù)交交易所所：當(dāng)有多多個(gè)分分類器器獲得得匹配配時(shí)，，每個(gè)個(gè)分類類器要要出一一個(gè)與與其強(qiáng)強(qiáng)度成成正比比的叫叫價(jià)B叫價(jià)高高的分分類器器被激激活并并允許許發(fā)送送消息息，同同時(shí)通通過票票據(jù)交交易所所,將將其叫叫價(jià)B提供給給激活活的分分類器器。如此繼繼續(xù)下下去，，一條條規(guī)則則可通通過消消費(fèi)者者獲利利（增增加了了強(qiáng)度度），，通過過規(guī)則則的不不斷激激活形形成一一條消消費(fèi)者者鏈，，直至至最終終消費(fèi)費(fèi)者（（達(dá)到到目標(biāo)標(biāo)）直直接從從環(huán)境境中得得到補(bǔ)補(bǔ)償。。若鏈中一條條規(guī)則導(dǎo)致致錯(cuò)誤結(jié)論論，則序列列上該規(guī)則則的強(qiáng)度將將減弱，并并且沿著序序列回溯，，從而產(chǎn)生生新的消費(fèi)費(fèi)者鏈2022/12/3183舉例環(huán)境0111，，強(qiáng)度為為0，叫叫價(jià)系數(shù)數(shù)為0.1。索引號(hào)分分類器器強(qiáng)強(qiáng)度101##：0000 200200#0：1000 200311##：1000 2004##00：0001 2002022/12/3184第一步分類器強(qiáng)強(qiáng)度消消息匹匹配叫叫價(jià)01##：0000200E2000#0：100020011##：1000200##00：00012002022/12/3185第二步分類器強(qiáng)強(qiáng)度消消息匹匹配配叫叫價(jià)價(jià)01##：：0000180000000#0：：100020012011##：：1000200##00：：0001200120兩條規(guī)則同時(shí)時(shí)激活2022/12/3186第三步分類器強(qiáng)強(qiáng)度消消息匹匹配配叫叫價(jià)價(jià)01##：：000022000#0：11##：：1000200220##00：2022/12/3187第四步分類器強(qiáng)強(qiáng)度消消息匹匹配配叫叫價(jià)價(jià)01##：：000022000#0：：100021811##：##00：：00011623162022/12/3188第五步分類器強(qiáng)強(qiáng)度消消息匹匹配叫叫價(jià)強(qiáng)強(qiáng)度01##：000022022000#0：100021821811##：1000196196規(guī)則則4達(dá)達(dá)到到目目標(biāo)標(biāo)獲獲得得補(bǔ)補(bǔ)償償60。。2022/12/3189投標(biāo)標(biāo)改改變變分分類類器器的的強(qiáng)強(qiáng)度度在時(shí)時(shí)間間t滿足足C送去去消消息息的的分分類器器對(duì)在在t-1作用的的分分類類器投投標(biāo)標(biāo)在時(shí)時(shí)間間t對(duì)分分類類器器C的支支持持2022/12/3190分類器中中的遺傳傳算法遺傳算法法可產(chǎn)生生新規(guī)則則，用于于改善系系統(tǒng)的知知識(shí)庫(kù)。?？梢栽谌N情況況下應(yīng)用用GA：引入一個(gè)個(gè)參數(shù)T（時(shí)間間隔隔），用用于控制制何時(shí)使使用GA。特殊情況況時(shí)（如如消息的的條件都都不能匹匹配）使使用GA。系統(tǒng)的性性能太差差。2022/12/3191算法步驟t=0，隨機(jī)生成集合合Bt，|Bt|=M（大小）；計(jì)算Bt中全體分類器器的平均強(qiáng)度度Vt，對(duì)每個(gè)分類器器賦予一個(gè)標(biāo)標(biāo)準(zhǔn)強(qiáng)度St(Cj)/Vt；給Bt中的每個(gè)分分類器Cj賦予一個(gè)與與其標(biāo)準(zhǔn)強(qiáng)強(qiáng)度成正比比的概率，，并根據(jù)Bt中的概率分分布，從Bt中選取n個(gè)分類器，，n<<M；；對(duì)每個(gè)分類類器應(yīng)用交交叉算子，，生成2n個(gè)分類器；；將Bt中的2n個(gè)強(qiáng)度最低低的分類器器用新生成成的2n個(gè)取代；t=t+1，轉(zhuǎn)(2)。。2022/12/3192算法說明算法中S0(Cj)是預(yù)知的；；實(shí)現(xiàn)時(shí)考慮慮結(jié)束條件件；該算法是經(jīng)經(jīng)典GA的變種，其其中沒有變變異算子；；新分類器的的強(qiáng)度是由由舊分類器器的強(qiáng)度決決定的。2022/12/3193分類器強(qiáng)度度調(diào)整算法法將與與所所選選動(dòng)動(dòng)作作相相同同的的分分類類器器形形成成子子集集[M]，，稱作作動(dòng)動(dòng)作作集集[A]。。將不不在在[M]中的的其其它它分分類類器器放放在在集集合合NOT[A]中。。在[A]中的的全全部部分分類類器器強(qiáng)強(qiáng)度度減減少少一一個(gè)個(gè)分分?jǐn)?shù)數(shù)e。。如果果系系統(tǒng)統(tǒng)決決策策正正確確，，則則將將贏贏利利量量R分配給[A]的強(qiáng)度;如果系統(tǒng)決策策錯(cuò)誤，則將將贏利量R'(其中0≤R'≤R)分配給[A]的強(qiáng)度，從[A]的強(qiáng)度減少一一個(gè)分?jǐn)?shù)p。至少R'和p中的一個(gè)為0。從NOT[A]中的強(qiáng)度減去去一個(gè)分?jǐn)?shù)t。2022/12/319415.9規(guī)則發(fā)現(xiàn)系統(tǒng)統(tǒng)在規(guī)則發(fā)現(xiàn)系系統(tǒng)中,學(xué)學(xué)習(xí)經(jīng)常是首首先評(píng)價(jià)系統(tǒng)統(tǒng)現(xiàn)有的規(guī)則則質(zhì)量,然然后進(jìn)行修改改。Grefenstette研制了一種規(guī)規(guī)則發(fā)現(xiàn)系統(tǒng)統(tǒng)RUDI。問題求解級(jí)由由簡(jiǎn)化的分類類器系統(tǒng)組成成。學(xué)習(xí)級(jí)是是對(duì)知識(shí)結(jié)構(gòu)構(gòu)群體進(jìn)行遺遺傳算法操作作,每一個(gè)表示為為一組規(guī)則表表。知識(shí)結(jié)構(gòu)構(gòu)的整個(gè)行為為控制這些結(jié)結(jié)構(gòu)的復(fù)制。。在RUDI中,信用賦賦值方法贏利利共享規(guī)劃(Profit-SharingPlan,簡(jiǎn)稱PSP)和桶鏈算法(BBA)對(duì)每個(gè)規(guī)則提提供互補(bǔ)的效效用信息。根根據(jù)期望的外外部獎(jiǎng)勵(lì),PSP-強(qiáng)度對(duì)規(guī)則效效用提供更精精確的評(píng)估。。當(dāng)問題求解解時(shí)它被用作作沖突消解。。與此相反,BBA-強(qiáng)度表示規(guī)則則之間的動(dòng)態(tài)態(tài)相關(guān)性,規(guī)規(guī)則點(diǎn)火依依次會(huì)聚到相相似水平。這這種測(cè)度可以以用作一組協(xié)協(xié)作規(guī)則的聚聚類。2022/12/3195規(guī)則發(fā)現(xiàn)系統(tǒng)統(tǒng)Grefenstette提出一種強(qiáng)度度修改方案稱稱作嬴利共享享規(guī)劃PSP。在這種方案中中問題求解劃劃分成情節(jié),按所接受受的外部獎(jiǎng)勵(lì)勵(lì)區(qū)分。如果果任何步情節(jié)節(jié)在投標(biāo)競(jìng)爭(zhēng)爭(zhēng)中獲勝,則則認(rèn)為該規(guī)規(guī)則在該情節(jié)節(jié)活動(dòng)。在情情節(jié)t,PSP修改每個(gè)活動(dòng)動(dòng)規(guī)則Ri的強(qiáng)度Si(t)如下:Si(t+1)=Si(t)-bSi(t)+bp(t),其中,p(t)稱作在情節(jié)結(jié)結(jié)束時(shí)所獲得得的外部獎(jiǎng)勵(lì)勵(lì),即當(dāng)獲獲得外部獎(jiǎng)勵(lì)勵(lì),從每個(gè)活活動(dòng)規(guī)則搜集集投標(biāo),每每個(gè)活動(dòng)規(guī)則則給出一部分分外部獎(jiǎng)勵(lì)。。考慮PSP對(duì)給定規(guī)則Ri的影響,它它按照方程得到:2022/12/3196規(guī)則發(fā)現(xiàn)系統(tǒng)統(tǒng)其中,t的范圍是在該該情節(jié)規(guī)則Ri是活動(dòng)的,即即Si(t)基本上外部獎(jiǎng)獎(jiǎng)勵(lì)的權(quán)值平平均p(t),(1-b)作為指數(shù)衰減減因子。如果果