【導(dǎo)讀】機(jī)制進(jìn)行搜索的一種算法。進(jìn)化計(jì)算的研究起源于20世紀(jì)50年代。1965年，Holland首次提出了人工遺傳操作。大約在同一時(shí)期：。Rechenberg和Schwefel提出了進(jìn)化策略。Fogel提出了進(jìn)化規(guī)劃。1967年，Bagley在他的論文中首次提出了。自動(dòng)博弈中的應(yīng)用。1970年，Cavicchio把遺傳算法應(yīng)用于模式。第一個(gè)把遺傳算法應(yīng)用于函數(shù)優(yōu)。1975年是遺傳算法研究的歷史上十分重要的一年。同年，DeJong完成了他的重要論文《遺傳自適應(yīng)系統(tǒng)。他在該論文中所做的研究工作可看作。Holland的模式理論與他的計(jì)算使用結(jié)合起來。1989Goldberg對(duì)遺傳算法從理論上，方法上。（用于搜索解決特定。1)個(gè)體是基本的選擇目標(biāo);3)基因型變異大部分是重組的產(chǎn)物,特別是突變;4)逐漸進(jìn)化可能與表型不連續(xù)有關(guān);7)選擇是概率型的,而不是決定型的。Programming)，又稱為進(jìn)化程序設(shè)計(jì)。本章將著重介紹遺傳算法，對(duì)進(jìn)化策略和進(jìn)化規(guī)。群體禁止異構(gòu)環(huán)境。子孫對(duì)下一代作出貢獻(xiàn)。基因gi的可能值稱為等位基因。變換過程是高度非線性的。是群體的平均適應(yīng)度。設(shè)pi是群體中等位基因的頻率。

　　

【正文】 叫價(jià) 01 ： 0000 220 00 0： 1000 218 11 ： 1000 180 1000 00： 0001 162 3 16 2020/11/4 史忠植 高級(jí)人工智能 89 第五步 分類器 強(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達(dá)到目標(biāo)獲得補(bǔ)償 60。 2020/11/4 史忠植 高級(jí)人工智能 90 投標(biāo)改變分類器的強(qiáng)度 在時(shí)間 t滿足 C 送去消息的分 類器 ),(),(),()1( 3211 tCBtCBtCBCV ????1C1C1C),( 1 tCB),( 2 tCB),( 3 tCB對(duì)在 t1作 用的分類 器投標(biāo) 在時(shí)間 t對(duì)分類器 C的支持 2020/11/4 史忠植 高級(jí)人工智能 91 分類器中的遺傳算法 遺傳算法可產(chǎn)生新規(guī)則，用于改善系統(tǒng)的知識(shí)庫。 可以在三種情況下應(yīng)用 GA： 1) 引入一個(gè)參數(shù) T（ 時(shí)間間隔），用于控制何時(shí)使用 GA。 2) 特殊情況時(shí)（如消息的條件都不能匹配）使用 GA。 3) 系統(tǒng)的性能太差。 2020/11/4 史忠植 高級(jí)人工智能 92 算法步驟 1) t=0， 隨機(jī)生成集合 Bt， |Bt|=M（ 大?。?； 2) 計(jì)算 Bt中全體分類器的平均強(qiáng)度 Vt， 對(duì)每個(gè)分類器賦予一個(gè)標(biāo)準(zhǔn)強(qiáng)度 St(Cj)/Vt； 3) 給 Bt中的每個(gè)分類器 Cj賦予一個(gè)與其標(biāo)準(zhǔn)強(qiáng)度成正比的概率，并根據(jù) Bt中的概率分布，從 Bt中選取 n個(gè)分類器， nM； 4) 對(duì)每個(gè)分類器應(yīng)用交叉算子，生成 2n個(gè)分類器； 5) 將 Bt中的 2n個(gè)強(qiáng)度最低的分類器用新生成的 2n個(gè)取代； 6) t=t+1， 轉(zhuǎn) (2)。 2020/11/4 史忠植 高級(jí)人工智能 93 算法說明 1) 算法中 S0(Cj)是預(yù)知的； 2) 實(shí)現(xiàn)時(shí)考慮結(jié)束條件； 3) 該算法是經(jīng)典 GA的變種，其中沒有變異算子； 4) 新分類器的強(qiáng)度是由舊分類器的強(qiáng)度決定的。 2020/11/4 史忠植 高級(jí)人工智能 94 分類器強(qiáng)度調(diào)整算法 1) 將與所選動(dòng)作相同的分類器形成子集 [M]， 稱作動(dòng)作集 [A]。將不在 [M]中的其它分類器放在集合 NOT[A]中。 2) 在 [A]中的全部分類器強(qiáng)度減少一個(gè)分?jǐn)?shù) e。 3) 如果系統(tǒng)決策正確，則將贏利量 R分配給 [A]的強(qiáng)度 。 4) 如果系統(tǒng)決策錯(cuò)誤，則將贏利量 R39。(其中 0≤R39。≤R)分配給 [A]的強(qiáng)度，從 [A]的強(qiáng)度減少一個(gè)分?jǐn)?shù) p。 至少 R39。和 p中的一個(gè)為 0。 5) 從 NOT[A]中的強(qiáng)度減去一個(gè)分?jǐn)?shù) t。 2020/11/4 史忠植 高級(jí)人工智能 95 規(guī)則發(fā)現(xiàn)系統(tǒng) 在規(guī)則發(fā)現(xiàn)系統(tǒng)中 , 學(xué)習(xí)經(jīng)常是首先評(píng)價(jià)系統(tǒng)現(xiàn)有的規(guī)則質(zhì)量 , 然后進(jìn)行修改。 Grefenstette 研制了一種規(guī)則發(fā)現(xiàn)系統(tǒng) RUDI。 問題求解級(jí)由簡化的分類器系統(tǒng)組成。學(xué)習(xí)級(jí)是對(duì)知識(shí)結(jié)構(gòu)群體進(jìn)行遺傳算法操作 , 每一個(gè)表示為一組規(guī)則表。知識(shí)結(jié)構(gòu)的整個(gè)行為控制這些結(jié)構(gòu)的復(fù)制。 在 RUDI中 , 信用賦值方法贏利共享規(guī)劃 (ProfitSharing Plan,簡稱 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)相關(guān)性 , 規(guī)則點(diǎn)火依次會(huì)聚到相似水平。這種測(cè)度可以用作一組協(xié)作規(guī)則的聚類。 2020/11/4 史忠植 高級(jí)人工智能 96 規(guī)則發(fā)現(xiàn)系統(tǒng) Grefenstette 提出一種強(qiáng)度修改方案稱作嬴利共享規(guī)劃 PSP。在這種方案中問題求解劃分成情節(jié) , 按所接受的外部獎(jiǎng)勵(lì)區(qū)分。如果任何步情節(jié)在投標(biāo)競(jìng)爭(zhēng)中獲勝 , 則認(rèn)為該規(guī)則在該情節(jié)活動(dòng)。在情節(jié) t, PSP 修改每個(gè)活動(dòng)規(guī)則 Ri的強(qiáng)度 Si(t) 如下 : )1()()0()1()(1???????? ipbibSbtS ittiiti 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 對(duì)給定規(guī)則 Ri 的影響 , 它按照方程得到 : 2020/11/4 史忠植 高級(jí)人工智能 97 規(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*: )1()()0()1()(1???????? ipbibSbtSittiiti**1* ])()0()1[(l i m ppbibSbSittiitti ????????? ?2020/11/4 史忠植 高級(jí)人工智能 98 規(guī)則發(fā)現(xiàn)系統(tǒng) 在常數(shù)贏利下 , PSP 將以下列速率減少誤差 Ei(t) = p* Si(t) )())(()1()()()1(*tbEtSpbtStStEtEEiiiiiii????????????強(qiáng)度每次改變 , 以因子 b減少當(dāng)前強(qiáng)度與平衡強(qiáng)度之差。 2020/11/4 史忠植 高級(jí)人工智能 99 規(guī)則發(fā)現(xiàn)系統(tǒng) 我們看出 , 獎(jiǎng)勵(lì)相當(dāng)是常數(shù)情況下 , 在 PSP下每個(gè)規(guī)則強(qiáng)度很快收斂到一個(gè)平衡強(qiáng)度 , 可以預(yù)測(cè)情節(jié)結(jié)束時(shí)將接收的獎(jiǎng)勵(lì)水平。 PSP的一種可能的限制是它取決于這種前提 , 成功外部獎(jiǎng)勵(lì)區(qū)分的情節(jié)所對(duì)應(yīng)的合適區(qū)間 , 在這個(gè)區(qū)間里進(jìn)行信用賦值。情節(jié)的選擇非常重要。 2020/11/4 史忠植 高級(jí)人工智能 100 規(guī)則發(fā)現(xiàn)系統(tǒng) 在桶鏈算法 BBA中 , 是基于規(guī)則之間單獨(dú)處理的 , 可以避免有關(guān)情 節(jié)的假設(shè)。假設(shè)規(guī)則 Ri 在 tau 步點(diǎn)火 , 規(guī)則 Rj 在 tau + 1 點(diǎn)火 , 那么 BBA 按照下面公式修改規(guī)則 Ri的強(qiáng)度 Si: )()()()1( tttt jiii bSbSSS ????第一個(gè)改變意味 BBA 在給定的情節(jié)修改規(guī)則強(qiáng)度多于一次 。 第二個(gè)改變導(dǎo)致 PSP與 BBA基本的不同 。 PSP強(qiáng)度預(yù)測(cè)所期望的情節(jié)結(jié)束獲得的外部獎(jiǎng)勵(lì)是在規(guī)則點(diǎn)火 , BBA的強(qiáng)度預(yù)測(cè)所期望的內(nèi)部獎(jiǎng)勵(lì)是在規(guī)則的下一步 。 2020/11/4 史忠植 高級(jí)人工智能 101 規(guī)則發(fā)現(xiàn)系統(tǒng) RUDI的控制結(jié)構(gòu) 問題求解 BBA/PSP 遺傳算法 任務(wù) 執(zhí)行 強(qiáng)度 新規(guī)則 信用 獎(jiǎng)勵(lì) 2020/11/4 史忠植 高級(jí)人工智能 102 PSP與 BBA比較 A1RC3RE6RHB2RD4RF6RI5RG7RJ獎(jiǎng)勵(lì)： 1000 0 300 初始狀態(tài) 結(jié)束狀態(tài) 2020/11/4 史忠植 高級(jí)人工智能 103 不同的強(qiáng)度修改方案 規(guī)則 PSP強(qiáng)度 BBA強(qiáng)度 1R3R6R2R4R5R7R1000 648 299 567 1000 645 4 644 300 300 999 531 300 300 2020/11/4 史忠植 高級(jí)人工智能 104 進(jìn)化策略 進(jìn)化策略模仿自然進(jìn)化原理作為一種求解參數(shù)優(yōu)化問題的方法。最簡單的實(shí)現(xiàn)方法如下 : (1) 定義的問題是尋找 n維的實(shí)數(shù)向量 x, 它使函數(shù) (2) 雙親向量的初始群體從每維可行范圍內(nèi)隨機(jī)選擇。 (3) 子孫向量的創(chuàng)建是從每個(gè)雙親向量加上零均方差高斯隨機(jī)變量。 (4) 根據(jù)最小誤差選擇向量為下一代新的雙親。 (5) 向量的標(biāo)準(zhǔn)偏差保持不變 , 或者沒有可用的計(jì)算方法 , 那么處理結(jié)束。 RRxF n ?:)(2020/11/4 史忠植 高級(jí)人工智能 105 進(jìn)化規(guī)劃 進(jìn)化規(guī)劃 (evolutionary programming， 又譯為進(jìn)化程序設(shè)計(jì) )的過程 , 可理解為從所有可能的計(jì)算機(jī)程序形成的空間中 , 搜索有高的適應(yīng)值的計(jì)算機(jī)程序個(gè)體，在進(jìn)化程序設(shè)計(jì)中，幾百或幾千個(gè)計(jì)算機(jī)程序參與遺傳進(jìn)化。 2020/11/4 史忠植 高級(jí)人工智能 106 進(jìn)化規(guī)劃步驟 1. 產(chǎn)生出初始群體 , 它由關(guān)于問題 (計(jì)算機(jī)程序 )的函數(shù)隨機(jī)組合而成。 2. 迭代完成下述子步驟，直至滿足選種標(biāo)準(zhǔn)為止 : 1) 執(zhí)行群體中的每個(gè)程序，根據(jù)它解決問題的能力，給它指定一個(gè)適應(yīng)值 2) 應(yīng)用變異等操作創(chuàng)造新的計(jì)算機(jī)程序群體?；谶m應(yīng)值根據(jù)概率從群體中選出一個(gè)計(jì)算機(jī)程序個(gè)體，然后用合適的操作作用于該計(jì)算機(jī)程序個(gè)體。 把現(xiàn)有的計(jì)算機(jī)程序復(fù)制到新的群體中。通過遺傳隨機(jī)重組兩個(gè)現(xiàn)有的程序 , 創(chuàng)造出新的計(jì)算機(jī)程序個(gè)體。 3. 在后代中適應(yīng)值最高的計(jì)算機(jī)程序個(gè)體被指定為進(jìn)化程序設(shè)計(jì)的結(jié)果。這一結(jié)果可能是問題的解或近似解。 2020/11/4 史忠植 高級(jí)人工智能 107 Questions?