1、1,第十二章 進(jìn)化計(jì)算與遺傳算法,徐從富 浙江大學(xué)人工智能研究所 2003年11月,2,本章主要參考文獻(xiàn)： 1 陳國良, 王煦法 等. 遺傳算法及其應(yīng)用. 人民郵電出版社, 1996. 2 王正志, 薄濤. 進(jìn)化計(jì)算. 國防科技大學(xué)出版社, 2000. 3 張穎, 劉艷秋. 軟計(jì)算方法. 科學(xué)出版社, 2002. pp69-108. 4 史忠植. 高級人工智能. 科學(xué)出版社, 1998. pp249-270. 5 史忠植. 知識發(fā)現(xiàn). 清華大學(xué)出版社, 2002. pp265-294. 6 Mitchell, T. M.著, 曾華軍等譯. 機(jī)器學(xué)習(xí). 機(jī)械工業(yè)出版社, 2003. pp179-

2、196. 7 賀前華, 韋崗, 陸以勤. 基因算法研究進(jìn)展. 電子學(xué)報(bào), 1998, 26(10): 118-122, 103.,3,內(nèi)容,12.1 概述 12.2 進(jìn)化系統(tǒng)理論的形式模型 12.3 達(dá)爾文進(jìn)化算法 12.4 分類器系統(tǒng) 12.5 桶鏈算法 12.6 遺傳算法 12.7 并行遺傳算法 12.8 分類器系統(tǒng)Boole 12.9 規(guī)則發(fā)現(xiàn)系統(tǒng) 12.10 進(jìn)化策略 12.11 進(jìn)化程序設(shè)計(jì),4,12.1 概述,12.1.1 背景 人們對很多高度非線性問題的內(nèi)部機(jī)理還很不清楚： 智能模擬 非線性優(yōu)化 圖像識別，等等。 要解決上述問題，就需要一些具有自組織、自適應(yīng)能力的大規(guī)模并行算法，

3、模擬生物或自然現(xiàn)象就成為AI中的一種自然而又重要的研究方向。因此產(chǎn)生了如下新方法： 人工神經(jīng)網(wǎng)絡(luò) 遺傳算法、進(jìn)化計(jì)算，等等。,5,生物進(jìn)化的主要特點(diǎn)： 進(jìn)化的結(jié)果非常復(fù)雜 進(jìn)化的過程非常簡單：繁殖、變異、競爭、選擇 基于自然選擇的軟件設(shè)計(jì)方法解決傳統(tǒng)方法中存在的如下最大障礙：需要事先描述問題的全部特點(diǎn)，并說明針對問題的特點(diǎn)，程序應(yīng)采取的措施。 利用進(jìn)化機(jī)理，人們可以“培育”程序，去解決那些結(jié)構(gòu)尚不清楚的問題。,12.1.1 背景（續(xù)）,6,遺傳算法和進(jìn)化計(jì)算的基本思想：來源于生物進(jìn)化過程, 它是基于進(jìn)化過程中的信息遺傳機(jī)制和優(yōu)勝劣汰的自然選擇原則的搜索算法（以字符串表示狀態(tài)空間）。遺傳算法用概

4、率搜索過程在該狀態(tài)空間中搜索，產(chǎn)生新的樣本。 遺傳算法和進(jìn)化計(jì)算是一種通用的問題求解方法，它采用某種編碼技術(shù)來表示各種復(fù)雜的結(jié)構(gòu)，并將每個(gè)編碼稱為一個(gè)個(gè)體。算法維持一個(gè)一定數(shù)目的編碼集合，稱為種群，并通過對種群中的每個(gè)個(gè)體進(jìn)行某些遺傳操作（如變異、交叉、選擇等）來模擬進(jìn)化過程，最終獲得一些具有較高性能指標(biāo)的編碼。,12.1.3 基本思想,7,發(fā)展歷史,遺傳算法的發(fā)展歷史： 1965年，Holland首次提出了人工遺傳操作的重要性，并把這些應(yīng)用于自然系統(tǒng)和人工系統(tǒng)中。 1967年，Bagley在他的論文中首次提出了遺傳算法（Genetic Algorithm，簡稱GA）這一術(shù)語，并討論了遺傳算法

5、在自動(dòng)博弈中的應(yīng)用。 1970年，Cavicchio把遺傳算法應(yīng)用于模式識別中。第一個(gè)把遺傳算法應(yīng)用于函數(shù)優(yōu)化的是Hollstien。,8,發(fā)展歷史（續(xù)）,1975年是遺傳算法研究的歷史上十分重要的一年。這一年，Holland出版了他的著名專著“Adaptation in Natural and Artificial Systems”(自然和人工系統(tǒng)的自適應(yīng)性)該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極為重要的模式理論（Schemata Theory），該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性。 同年，DeJong完成了他的重要論文“An A

6、nalysis of the Behavior of a Class of Genetic Adaptive Systems”(遺傳自適應(yīng)系統(tǒng)的行為分析)。他在該論文中所做的研究工作可看作是遺傳算法發(fā)展過程中的一個(gè)里程碑，這是因?yàn)樗袶olland的模式理論與他自己的實(shí)驗(yàn)結(jié)合起來。,9,發(fā)展歷史（續(xù)）,1988年Mayr提出新達(dá)爾文進(jìn)化理論。 1989年Goldberg對遺傳算法從理論、方法和應(yīng)用上作了系統(tǒng)的總結(jié).,10,特 點(diǎn),特點(diǎn)： 通用 魯棒 次優(yōu)解、滿意解 遺傳算法能解決的問題： 優(yōu)化 NP完全問題 NP難解問題 高度復(fù)雜的非線性問題,11,進(jìn)化計(jì)算和遺傳算法的主要應(yīng)用領(lǐng)域：,12,遺

7、傳算法與自然進(jìn)化的比較,自然界,染色體,基因,等位基因(allele),染色體位置(locus),基因型(genotype),表型(phenotype),遺傳算法,字符串,字符，特征,特征值,字符串位置,結(jié)構(gòu),參數(shù)集，譯碼結(jié)構(gòu),13,面向執(zhí)行的學(xué)習(xí)系統(tǒng),任務(wù)子系統(tǒng),學(xué)習(xí)子系統(tǒng),任務(wù)檢測器,任務(wù)效應(yīng)器,執(zhí)行效應(yīng)器,執(zhí)行檢測器,14,新達(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)中變化的, 形式多樣, 不

8、僅是基因的變化; 選擇是概率型的, 而不是決定型的。,15,12.2 進(jìn)化系統(tǒng)理論的形式模型,進(jìn)化在個(gè)體群體中起作用。1974年Waddington指出基因型和表型之間關(guān)系的重要性。群體禁止異構(gòu)環(huán)境。但是“后成環(huán)境”是多維空間。表型是基因型和環(huán)境的產(chǎn)物。然后表型通過異構(gòu)“選擇環(huán)境”發(fā)生作用。 【注】：這種多維選擇環(huán)境與后成環(huán)境空間是不同的?，F(xiàn)在，適應(yīng)性是表型空間和選擇環(huán)境空間的產(chǎn)物。它經(jīng)常被取作一維，表示多少子孫對下一代作出貢獻(xiàn)。 基于上述思想，1989年Muhlenbein和Kindermann提出了一種稱為進(jìn)化系統(tǒng)理論的形式模型。,16,進(jìn)化系統(tǒng)理論的形式模型,進(jìn)化的主要過程,后生環(huán)境,遺

9、傳操作符,選擇環(huán)境,g,p,17,進(jìn)化系統(tǒng)理論的形式模型,其中，g 是基因型 p 是表型 基因gi的可能值稱為等位基因。 在門德爾(Mendel)遺傳學(xué)中，假設(shè)每個(gè)基因有有限個(gè)等位基因。,18,進(jìn)化系統(tǒng)理論的形式模型,這個(gè)變換函數(shù)給出了模型，說明表型的發(fā)展是通過基因與環(huán)境的交互作用而實(shí)現(xiàn)的。 變換過程是高度非線性的。,19,進(jìn)化系統(tǒng)理論的形式模型,質(zhì)量函數(shù)q給出了具體選擇環(huán)境ESi下表型的質(zhì)量， 其定義如下：,質(zhì)量函數(shù)定義適應(yīng)度，用于達(dá)爾文選擇。目前主要有三種通用模型，即 門德爾遺傳學(xué) 遺傳生態(tài)學(xué) 進(jìn)化配子,20,門德爾遺傳學(xué),在門德爾遺傳學(xué)中，基因型被詳細(xì)模型化，而表型和環(huán)境幾乎被忽略；在遺

10、傳生態(tài)學(xué)中恰好相反；進(jìn)化配子論是從社會(huì)生物學(xué)導(dǎo)出的模型。,首先，討論門德爾遺傳學(xué)的選擇模型。為簡單起見，假設(shè)一個(gè)基因具有n個(gè)等位基因a1,an。二倍基因型以元組(ai, aj)為特征。定義pi,j為總?cè)后w中基因型(ai, aj)的頻度。假設(shè)基因型與表型相等。質(zhì)量函數(shù)給每個(gè)表型賦值。 q (ai, aj) = qi,j qi,j可被解釋為出生率減去死亡率。,21,門德爾遺傳學(xué),假設(shè) pi,j是下一代表型(ai, aj)的頻度。然后達(dá)爾文選擇根據(jù)選擇方程調(diào)整表型的分布:,其中，Q是群體的平均適應(yīng)度。,22,門德爾遺傳學(xué),設(shè) pi 是群體中等位基因的頻率。如果 pi,j = pi pj 那么，可得基

11、因型空間GS中的一個(gè)選擇方程為：,23,門德爾遺傳學(xué),這個(gè)離散的選擇方程可以用連續(xù)方程近似:,如果 qi,j = qj,i, 那么這個(gè)離散的選擇方程可以用連續(xù)方程近似:,24,門德爾遺傳學(xué),這個(gè)方程很容易被證明:,這個(gè)結(jié)果稱作Fisher基本定理。它說明平均適應(yīng)度隨適應(yīng)度的差別呈正比例增加。實(shí)際上，全部可能的基因型僅有一部分實(shí)現(xiàn)。這就是遺傳操縱子探索基因型空間的任務(wù)，其個(gè)體數(shù)目相當(dāng)小。這些操縱子是群體遺傳變異性的來源。最重要的操縱子是突變和重組。,25,12.3 達(dá)爾文進(jìn)化算法,根據(jù)定量遺傳學(xué)，達(dá)爾文進(jìn)化算法采用簡單的突變/選擇動(dòng)力學(xué)。達(dá)爾文算法的一般形式可以描述如下：,其中， ：是一代的雙親

12、數(shù)目， ：為子孫數(shù)目， ：稱作“混雜”數(shù)，若雙親混合其基因，則 = 2。 【注】：僅當(dāng)是最好的個(gè)體才允許產(chǎn)生子孫。 逗號“,”表示雙親們沒有選擇，加號“+”表 示雙親有選擇。,26,12.3 達(dá)爾文進(jìn)化算法,建立原始種體。 通過突變建立子孫。 選擇： 返回到步驟(1)。,27,12.4 分類器系統(tǒng),Holland和他的同事提出了一種分類器系統(tǒng)的認(rèn)知模型,其中的規(guī)則不是規(guī)則集, 而是遺傳算法操縱的內(nèi)部實(shí)體。 下圖給出了分類器系統(tǒng)的一般結(jié)構(gòu), 它由三層動(dòng)作構(gòu)成,即執(zhí)行子系統(tǒng)、信用賦值子系統(tǒng)和發(fā)現(xiàn)子系統(tǒng)。,28,分類器系統(tǒng),（1）執(zhí)行子系統(tǒng)處在最低層, 直接與環(huán)境進(jìn)行交互。它與專家系統(tǒng)相同,由產(chǎn)生式

13、規(guī)則構(gòu)成。但是, 它們是通過消息傳送,高度并行工作。這類規(guī)則稱作分類器。 （2）分類器系統(tǒng)中的學(xué)習(xí), 要求環(huán)境提供反饋, 確認(rèn)所希望的狀態(tài)是否達(dá)到。系統(tǒng)將評價(jià)這些規(guī)則的有效性, 這些活動(dòng) 常常稱作信用賦值。有些特定算法專門用來實(shí)現(xiàn)信用賦值, 例如, 桶鏈算法。 （3）最后一層是發(fā)現(xiàn)子系統(tǒng), 該系統(tǒng)必須產(chǎn)生新的規(guī)則, 取代當(dāng)前用處不大的規(guī)則。通過系統(tǒng)累積的經(jīng)驗(yàn)產(chǎn)生規(guī)則。系 統(tǒng)根據(jù)適應(yīng)值, 使用遺傳算法選擇、重組和取代規(guī)則。,29,分類器系統(tǒng),分類器系統(tǒng)的一般結(jié)構(gòu),發(fā)現(xiàn),遺傳算法,信用賦值,桶鏈,執(zhí)行,分類器系統(tǒng),消息來自 輸入接口,支付,消息送出 輸出接口,（目標(biāo)）,來自內(nèi)部監(jiān)控器的消息,30,

14、分類器系統(tǒng),分類器系統(tǒng)是平行執(zhí)行、消息傳遞和基于規(guī)則的系統(tǒng)。 在簡單的方案中,消息采用規(guī)定的字母, 全部為固定長度。 全部規(guī)則采用條件/動(dòng)作形式。每個(gè)條件規(guī)定必須滿足的 信息, 每個(gè)動(dòng)作規(guī)定當(dāng)條件滿足時(shí)所發(fā)送的消息。 為了方便, 假設(shè)消息采用長度為l的二進(jìn)制字符串 記錄, 字符采用子集1, 0, #。,31,規(guī)則與消息,產(chǎn)生式規(guī)則：IF THEN 約定：條件的長度是固定的，用二進(jìn)制數(shù)表示。 定義：,If sj = 1 or sj = 0, then mj = sj If sj = #, then mj can be either 1 or 0.,32,規(guī)則與消息,滿足要求的全部消息構(gòu)成子集,

15、即每個(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)處理消息的過程。 (3) 消息表包含當(dāng)前全部消息。 (4) 輸出接口將結(jié)果消息翻譯成效應(yīng)器動(dòng)作, 修改環(huán)境狀態(tài)。,33,分類器系統(tǒng)的基本結(jié)構(gòu),分類器,消息表,(a)全部消息進(jìn)行條件測試,條件,消息規(guī)約,輸出接口,送到環(huán)境,輸入接口,來自環(huán)境,(a),(b),(b)選中分類器產(chǎn)生新消息,34,分類器基本算法,將輸入接口全部消息放入消息表。 將消息表中的全部消息與全部分類器所

16、有條件比較, 記錄所有匹配。 滿足分類器條件部分的每組匹配, 將其動(dòng)作部分所規(guī)定的消息送到新的消息表。 用新的消息表取代消息表中的全部消息。 將消息表中的消息翻譯成輸出接口的要求, 產(chǎn)生系統(tǒng)當(dāng)前的輸出。 返回到步驟(1)。,35,簡單的視覺分類器系統(tǒng),36,性質(zhì)檢測器規(guī)定的值,1，如果移動(dòng)對象,0，其它,(0,0)，如果對象在視野的中間,(1,0)，如果對象在中心的左邊,(0,1)，如果對象在中心的右邊,1，如果系統(tǒng)是對象的近鄰,0，其它,1，如果對象很大,0，其它,1，如果對象是狹長的,0，其它,37,規(guī)則表示,規(guī)則： IF 如果有“捕食(prey)”(small, moving,nonst

17、riped object), 處于視野中間(centered), 非鄰近 (nonadjacent), THEN 迅速移向?qū)ο?(ALIGN), (FAST). 可以表示為： 00#000001 / 0100000000000000, ALIGN, FAST.,38,網(wǎng)絡(luò)圖,MOVING,SMALL,NOT STRPED,NEAR,FAR,01001 ALERT,10001 TARGET,11001 PORSUE,11010 APPROACH,11011 FLEE,11100 FREEZE,10010 DANGER,39,網(wǎng)絡(luò)圖的規(guī)則表示,MOVING和ALERT之間的箭頭： 00#1/010

18、01# SMALL，NOT STRIPED and ALERT到TARGET的箭頭： 00#00#，01001#/ 10001#,40,學(xué)習(xí)機(jī)制,分類器系統(tǒng)使用兩個(gè)學(xué)習(xí)機(jī)制， 桶鏈(bucket brigade) 算法。基于對系統(tǒng)的貢獻(xiàn), 對現(xiàn)有規(guī)則分配一個(gè)信用值。 規(guī)則發(fā)現(xiàn)算法。這包括遺傳算法，該算法可產(chǎn)生新規(guī)則，用于改善系統(tǒng)的知識庫。,41,12.5 桶鏈算法,桶鏈(bucket brigade) 算法基于對系統(tǒng)的貢獻(xiàn), 對現(xiàn)有規(guī)則分配一個(gè)信用值。主要解決多條規(guī)則同時(shí)要求被激活時(shí)的競爭問題。 例如：下面的情況下應(yīng)該選擇哪條規(guī)則。,011101# #：0000,# #00：0001 00#

19、0：1100,42,主要問題,引入信用值后的兩個(gè)問題： 當(dāng)多條規(guī)則同時(shí)要求被激活時(shí)，如何解決競爭問題 對一規(guī)則被激活產(chǎn)生過作用的那些規(guī)則如何分配信用,43,桶鏈算法,為解決上述兩個(gè)問題，引入拍賣行和票據(jù)交易所： 當(dāng)有多個(gè)分類器獲得匹配時(shí)，每個(gè)分類器要出一個(gè)與其強(qiáng)度成正比的叫價(jià)B 叫價(jià)高的分類器被激活并允許發(fā)送消息，同時(shí)通過票據(jù)交易所,將其叫價(jià)B提供給激活的分類器。 如此繼續(xù)下去，一條規(guī)則可通過消費(fèi)者獲利（增加了強(qiáng)度），通過規(guī)則的不斷激活形成一條消費(fèi)者鏈，直至最終消費(fèi)者（達(dá)到目標(biāo)）直接從環(huán)境中得到補(bǔ)償。 若鏈中一條規(guī)則導(dǎo)致錯(cuò)誤結(jié)論，則序列上該規(guī)則的強(qiáng)度將減弱，并且沿著序列回溯，從而產(chǎn)生新的消費(fèi)者

20、鏈,44,舉例,環(huán)境0111，強(qiáng)度為0，叫價(jià)系數(shù)為0.1。 索引號分類器強(qiáng)度 101# #：0000200 200# 0：1000200 311# #：1000200 4# #00：0001200,45,第一步,分類器 強(qiáng)度 消息 匹配 叫價(jià) 01# #：0000 200 E 20 00# 0：1000 200 11# #：1000 200 # #00：0001 200,46,第二步,分類器 強(qiáng)度 消息 匹配 叫價(jià) 01# #：0000 180 0000 00# 0：1000 200 1 20 11# #：1000 200 # #00：0001 200 1 20 兩條規(guī)則同時(shí)激活,47,第三步

21、,分類器 強(qiáng)度 消息 匹配 叫價(jià) 01# #：0000 220 00# 0：1000 180 1100 11# #：1000 200 2 20 # #00：0001 180 0001 2 18,48,第四步,分類器 強(qiáng)度 消息 匹配 叫價(jià) 01# #：0000 220 00# 0：1000 218 11# #：1000 180 1000 # #00：0001 162 3 16,49,第五步,分類器 強(qiáng)度 消息 匹配 叫價(jià) 強(qiáng)度 01# #：0000 220 220 00# 0：1000 218 218 11# #：1000 196 196 # #00：0001 146 0001 206 規(guī)則4

22、達(dá)到目標(biāo)獲得補(bǔ)償60。,50,投標(biāo)改變分類器的強(qiáng)度,在時(shí)間t滿足C 送去消息的分 類器,對在t-1作 用的分類 器投標(biāo),在時(shí)間t對分類器C的支持,51,分類器中的遺傳算法,遺傳算法可產(chǎn)生新規(guī)則，用于改善系統(tǒng)的知識庫。 可以在三種情況下應(yīng)用GA： 引入一個(gè)參數(shù)T（時(shí)間間隔），用于控制何時(shí)使用GA。 特殊情況時(shí)（如消息的條件都不能匹配）使用GA。 系統(tǒng)的性能太差。,52,算法步驟,t=0，隨機(jī)生成集合Bt，|Bt|=M（大小）； 計(jì)算Bt中全體分類器的平均強(qiáng)度Vt，對每個(gè)分類器賦予一個(gè)標(biāo)準(zhǔn)強(qiáng)度St(Cj)/Vt； 給Bt中的每個(gè)分類器Cj賦予一個(gè)與其標(biāo)準(zhǔn)強(qiáng)度成正比的概率，并根據(jù)Bt中的概率分布，從

23、Bt中選取n個(gè)分類器，nM； 對每個(gè)分類器應(yīng)用交叉算子，生成2n個(gè)分類器； 將Bt中的2n個(gè)強(qiáng)度最低的分類器用新生成的2n個(gè)取代； t=t+1，轉(zhuǎn)(2)。,53,算法說明,算法中S0(Cj)是預(yù)知的； 實(shí)現(xiàn)時(shí)考慮結(jié)束條件； 該算法是經(jīng)典GA的變種，其中沒有變異算子； 新分類器的強(qiáng)度是由舊分類器的強(qiáng)度決定的。,54,12.6 遺傳算法,遺傳算法先將搜索結(jié)構(gòu)編碼為字符串形式, 每個(gè)字符串結(jié)構(gòu)被稱為個(gè)體。 然后對一組字符串結(jié)構(gòu)(被稱為一個(gè)群體)進(jìn)行循環(huán)操作。每次循環(huán)被稱作一代,包括一個(gè)保存字符串中較優(yōu)結(jié)構(gòu)的過程和一個(gè)有結(jié)構(gòu)的、隨機(jī)的字符串間的信息交換過程。 類似于自然進(jìn)化，遺傳算法通過作用于染色體上

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

25、傳算法利用適應(yīng)值信息, 無需導(dǎo)數(shù)或其它輔助信息; 遺傳算法利用概率轉(zhuǎn)移規(guī)則, 而非確定性規(guī)則。,57,遺傳算法的準(zhǔn)備工作,確定表示方案; 確定適應(yīng)值的度量; 確定控制該算法的參數(shù)和變量; 確定怎樣指定結(jié)果及程序運(yùn)行結(jié)束的標(biāo)準(zhǔn)。,58,基本的遺傳算法,隨機(jī)產(chǎn)生一個(gè)由固定長度字符串組成的初始群體; 對于字符串群體，迭代地執(zhí)行下述步驟，直到選種標(biāo)準(zhǔn)被滿足為止： 計(jì)算群體中的每個(gè)個(gè)體字符串的適應(yīng)值; 應(yīng)用下述三種操作(至少前兩種)來產(chǎn)生新的群體: 復(fù)制: 把現(xiàn)有的個(gè)體字符串復(fù)制到新的群體中。 雜交: 通過遺傳重組隨機(jī)選擇兩個(gè)現(xiàn)有的子字符串, 產(chǎn)生新的字符串。 變異: 將現(xiàn)有字符串中某一位的字符隨機(jī)變異

26、。 把在后代中出現(xiàn)的最高適應(yīng)值的個(gè)體字符串指定為遺傳算法運(yùn)行的結(jié)果。這一結(jié)果可以是問題的解(或近似解)。,59,基本遺傳算法的流程圖,GEN=0,概率地選擇遺傳操作,隨機(jī)創(chuàng)建初始群體,是否滿足選中標(biāo)準(zhǔn)？,計(jì)算群體中每個(gè)個(gè)體的適應(yīng)值,i:=0,i:=M,指定結(jié)果,結(jié)束,GEN:=GEN+1,是,是,否,（轉(zhuǎn)下頁）,60,概率地選擇遺傳操作,根據(jù)適應(yīng)值選 擇一個(gè)個(gè)體,完成雜交,i:=i+1,i:=i+1,完成繁殖,p(r)繁殖,（接上頁）,基于適應(yīng)值選 擇兩個(gè)個(gè)體,把新的兩個(gè)孩 子加到群體中,p(c)雜交,變異p(m),把新的孩子加 入到群體中,完成變異,根據(jù)適應(yīng)值選 擇一個(gè)個(gè)體,把變異后個(gè)體 加

27、入到群體中,61,表示模式,所謂模式就是一個(gè)相同的構(gòu)形, 它描述的是一個(gè)串的子集, 這個(gè)集合中的串之間在某些位上相同。 模式的復(fù)制生長方程： 這表明, 一個(gè)特定的模式按照其平均適應(yīng)值與群體的平均適應(yīng)值之間的比率生長。,62,雜交操作,雜交操作是個(gè)有結(jié)構(gòu)、隨機(jī)的字符串間信息交換過程。 簡單的雜交操作分為三步 從當(dāng)前群體B(t)中選擇兩個(gè)結(jié)構(gòu)： 隨機(jī)選擇一個(gè)整數(shù) 交換a和a中位置x左邊的元素, 產(chǎn)生兩個(gè)新的結(jié)構(gòu)：,63,具有強(qiáng)度的遺傳算法,在t = 0時(shí)隨機(jī)產(chǎn)生M字符串的群體B(t)。計(jì)算群體B(t)中字符串的平均強(qiáng)度 v(t), 給群體B(t)中的每個(gè)字符串賦以規(guī)范值 S(Cj, t)/v(t)

28、。 對群體B(t)中的每個(gè)字符串賦與一個(gè)概率值, 其值與規(guī)范值成正比。然后, 使用概率分布, 從B(t)中選擇n對字符串, nM, 并且將它們復(fù)制。 對每對復(fù)制字符串進(jìn)行雜交操作, 形成2n個(gè)新的字符串。 用步驟(3)中生成的2n個(gè)新的字符串取代群體B(t)中2n個(gè)強(qiáng)度最低的字符串。 時(shí)間 t 變?yōu)?t + 1, 返回步驟(1)。,64,雜交操作舉例,1,0,2,2,0,2,0,1,No Offspring,Pt. of interchange Crossover,Parents,Offspring,1110#0#,1#0111#,0001#11#,010#1000,#00#11,0#01#1

29、0#,#100100,100#0111,6,17,1,1110#11#,0001#0#,0001#11#,#00#11,#00#11,0#01#10#,000#0111,1#01#10#,65,變異操作,簡單的變異操作過程如下: 每個(gè)位置的字符變量都有一個(gè)變異概率, 各位置互相獨(dú)立。通過隨機(jī)過程選擇發(fā)生變異的位置： 產(chǎn)生一個(gè)新結(jié)構(gòu) , 其中 是從對應(yīng)位置 的字符變量的值域中隨機(jī)選擇的一個(gè)取值。 可以同樣得到。,66,反轉(zhuǎ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)

30、生新的結(jié)構(gòu),67,遺傳算法舉例,問題：求 （1）編碼： 此時(shí)取均長為5，每個(gè)染色體 （2）初始群體生成：群體大小視情況而定，此處設(shè)置為4，隨機(jī)產(chǎn)生四個(gè)個(gè)體： 編碼： 01101，11000，01000，10011 解碼： 13 24 8 19 適應(yīng)度： 169 576 64 361 （3）適應(yīng)度評價(jià)：,68,（4）選擇：選擇概率 個(gè)體： 01101，11000，01000，10011 適應(yīng)度： 169 576 64 361 選擇概率：0.14 0.49 0.06 0.31 選擇結(jié)果：01101，11000，11000，10011 （5）交叉操作：發(fā)生交叉的概率較大 哪兩個(gè)個(gè)體配對交叉是隨機(jī)的

31、交叉點(diǎn)位置的選取是隨機(jī)的（單點(diǎn)交叉） 0110 1 01100 11 000 11011 1100 0 11001 10 011 10000,69,（6）變異：發(fā)生變異的概率很小 （7）新群體的產(chǎn)生： 保留上一代最優(yōu)個(gè)體，一般為10%左右，至少1個(gè) 用新個(gè)體取代舊個(gè)體，隨機(jī)取代或擇優(yōu)取代。 11000，11011，11001，10011 （8）重復(fù)上述操作： 說明：GA的終止條件一般人為設(shè)置； GA只能求次優(yōu)解或滿意解。 分析：按第二代新群體進(jìn)行遺傳操作，若無變異，永遠(yuǎn)也找不到最優(yōu)解擇優(yōu)取代有問題。 若隨機(jī)的將個(gè)體01101選入新群體中，有可能找到最優(yōu)解。,70,12.7 并行遺傳算法,基于離

32、散門德爾模型的遺傳算法由六部分組成： 對給定問題求解的染色體表示； 求解的原始物種； 起環(huán)境作用的品質(zhì)函數(shù)； 可以生成子孫的個(gè)體的選擇過程； 一種遺傳操縱子，如變異、重組； 控制算法本身的參數(shù)。,71,并行遺傳算法,并行遺傳算法： 給定具有不同開始表型的N個(gè)個(gè)體； 每個(gè)個(gè)體計(jì)算局部最大； 選擇在“近鄰”中選擇配對； 用重組和突變創(chuàng)建子孫； 返回步驟2。,72,12.8 分類器系統(tǒng)Boole,Wilson 于1987年開發(fā)了一個(gè)布爾問題的分類器系統(tǒng) Boole(Wilson 1987)。一個(gè)布爾函數(shù)變量L 是從長度為L的字符串到 0, 1的映射。學(xué)習(xí)函數(shù)意味獲得對任何輸入字符串能給出正確輸出0

33、或 1的能力。,73,分類器強(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。,74,Boole的遺傳算法,根據(jù)P中分類器的強(qiáng)度，通過概率選擇第一個(gè)分類器 。 根據(jù)概率 , 與步驟(1)相同，選擇分類器 ，并對 和 進(jìn)行雜交；從結(jié)果中選擇一個(gè)作為子孫，另一個(gè)被拋棄。 如果步驟 (2) 未完成，則

34、復(fù)制 形成子孫。 對子孫應(yīng)用變異操作，以概率 改變每個(gè)分類的等位基因。 如果通過雜交生成子孫，每個(gè)父母的強(qiáng)度減少三分之一，子孫的初始強(qiáng)度等于父母減少的總和；否則減少 的一半，而子孫的初始強(qiáng)度等于減少的量。 將子孫加到P中。 根據(jù)P中分類器強(qiáng)度的概率分布，刪除最小的一個(gè)分類器。,75,12.9 規(guī)則發(fā)現(xiàn)系統(tǒng),在規(guī)則發(fā)現(xiàn)系統(tǒng)中, 學(xué)習(xí)經(jīng)常是首先評價(jià)系統(tǒng)現(xiàn)有的規(guī)則質(zhì)量, 然后進(jìn)行修改。Grefenstette 研制了一種規(guī)則發(fā)現(xiàn)系統(tǒng)RUDI。 問題求解級由簡化的分類器系統(tǒng)組成。學(xué)習(xí)級是對知識結(jié)構(gòu)群 體進(jìn)行遺傳算法操作, 每一個(gè)表示為一組規(guī)則表。知識結(jié)構(gòu)的整 個(gè)行為控制這些結(jié)構(gòu)的復(fù)制。 在RUDI中,

35、 信用賦值方法贏利共享規(guī)劃(Profit-Sharing Plan, 簡稱PSP) 和桶鏈算法(BBA) 對每個(gè)規(guī)則提供互補(bǔ)的效用信息。 根據(jù)期望的外部獎(jiǎng)勵(lì), PSP-強(qiáng)度對規(guī)則效用提供更精確的評估。 當(dāng)問題求解時(shí)它被用作沖突消解。與此相反, BBA-強(qiáng)度表示規(guī)則 之間的動(dòng)態(tài)相關(guān)性, 規(guī)則點(diǎn)火依次會(huì)聚到相似水平。這種測度可 以用作一組協(xié)作規(guī)則的聚類。,76,規(guī)則發(fā)現(xiàn)系統(tǒng),Grefenstette 提出一種強(qiáng)度修改方案稱作嬴利共享規(guī)劃PSP。 在這種方案中問題求解劃分成情節(jié), 按所接受的外部獎(jiǎng)勵(lì)區(qū)分。 如果任何步情節(jié)在投標(biāo)競爭中獲勝, 則認(rèn)為該規(guī)則在該情節(jié)活動(dòng)。 在情節(jié)t, PSP 修改每個(gè)活動(dòng)

36、規(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 對給定規(guī)則Ri 的影響, 它按照方程得到:,77,規(guī)則發(fā)現(xiàn)系統(tǒng),其中, t 的范圍是在該情節(jié)規(guī)則 Ri 是活動(dòng)的, 即Si(t) 基本上 外部獎(jiǎng)勵(lì)的權(quán)值平均p(t), (1 - b) 作為指數(shù)衰減因子。如果 b 足夠小,那么 S(t) 具有 p(t) 的平均值。如果外部獎(jiǎng)勵(lì) p(t) 是常數(shù),p*, 那么Si 收斂到一個(gè)平衡值 Si*:,78,規(guī)則發(fā)現(xiàn)系統(tǒng),在常