機(jī)器學(xué)習(xí)

1、2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,1,機(jī)器學(xué)習(xí),第9章 遺傳算法,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,2,概述,遺傳算法是一種大致基于模擬進(jìn)化的學(xué)習(xí)方法假設(shè)通常被描述為二進(jìn)制位串，也可以是符號表達(dá)式或計(jì)算機(jī)程序搜索合適的假設(shè)從若干初始假設(shè)的群體或集合開始當(dāng)前群體的成員通過模擬生物進(jìn)化的方式來產(chǎn)生下一代群體，比如

2、隨機(jī)變異和交叉每一步，根據(jù)給定的適應(yīng)度評估當(dāng)前群體中的假設(shè)，而后使用概率方法選出適應(yīng)度最高的假設(shè)作為產(chǎn)生下一代的種子遺傳算法已被成功用于多種學(xué)習(xí)任務(wù)和最優(yōu)化問題中，比如學(xué)習(xí)機(jī)器人控制的規(guī)則集和優(yōu)化人工神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和學(xué)習(xí)參數(shù)本章主要介紹了基于位串描述假設(shè)的遺傳算法和基于計(jì)算機(jī)程序描述假設(shè)的遺傳編程,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,3,動(dòng)機(jī),遺傳算法（GA）是一種受

3、生物進(jìn)化啟發(fā)的學(xué)習(xí)方法，它不再是從一般到特殊或從簡單到復(fù)雜地搜索假設(shè)，而是通過變異和重組當(dāng)前已知的最好假設(shè)來生成后續(xù)的假設(shè)每一步，更新被稱為當(dāng)前群體的一組假設(shè)，方法是使用當(dāng)前適應(yīng)度最高的假設(shè)的后代替代群體的某個(gè)部分這個(gè)過程形成了假設(shè)的生成測試的柱狀搜索，其中若干個(gè)最佳當(dāng)前假設(shè)的變體最有可能在下一步被考慮,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,4,動(dòng)機(jī)（2）,遺傳算法的普及和發(fā)

4、展得益于下面的因素在生物系統(tǒng)中，進(jìn)化被認(rèn)為是一種成功的自適應(yīng)方法，具有很好的健壯性遺傳算法搜索的假設(shè)空間中，假設(shè)的各個(gè)部分相互作用，每一部分對總的假設(shè)適應(yīng)度的影響難以建模遺傳算法易于并行化本章內(nèi)容安排描述了遺傳算法，舉例演示了它的用法，分析了它搜索的空間的特性描述了遺傳算法的一個(gè)變體：遺傳編程，這個(gè)方法中，整個(gè)計(jì)算機(jī)程序向著某個(gè)適應(yīng)度準(zhǔn)則進(jìn)化介紹了一些有關(guān)生物進(jìn)化的課題（遺傳算法和遺傳編程是進(jìn)化計(jì)算領(lǐng)域中的兩種普遍方法），

5、比如鮑德溫效應(yīng)，它描述了個(gè)體的學(xué)習(xí)能力與整個(gè)群體進(jìn)化速度之間的相互作用,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,5,遺傳算法,遺傳算法研究的問題是搜索候選假設(shè)空間并確定最佳假設(shè)最佳假設(shè)被定義為使適應(yīng)度最優(yōu)的假設(shè)適應(yīng)度是為當(dāng)前問題預(yù)先定義的數(shù)字度量，比如：如果學(xué)習(xí)任務(wù)是在給定一個(gè)未知函數(shù)的輸入輸出訓(xùn)練樣例后逼近這個(gè)函數(shù)，適應(yīng)度可被定義為假設(shè)在訓(xùn)練數(shù)據(jù)上的精度如果是學(xué)習(xí)下國際象

6、棋的策略，適應(yīng)度可被定義為該個(gè)體在當(dāng)前群體中與其他個(gè)體對弈的獲勝率,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,6,遺傳算法（2）,遺傳算法具有以下的共同結(jié)構(gòu)：算法迭代更新一個(gè)假設(shè)池，這個(gè)假設(shè)池稱為群體在每一次迭代中，根據(jù)適應(yīng)度評估群體中的所有成員，然后用概率方法選取適應(yīng)度最高的個(gè)體產(chǎn)生新一代群體在被選中的個(gè)體中，一部分保持原樣地進(jìn)入下一代群體，其他被用作產(chǎn)生后代個(gè)體的基礎(chǔ)，其中

7、應(yīng)用交叉和變異這樣的遺傳方法,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,7,表9-1 遺傳算法原型,GA(Fitness, Fitness_threshold, p, r, m)Fitness：適應(yīng)度評分函數(shù)Fitness_threshold：指定終止判據(jù)的閾值p：群體中包含的假設(shè)數(shù)量r：每一步中通過交叉取代群體成員的比例m：變異率初始化群體：P?隨機(jī)產(chǎn)生的p個(gè)假設(shè)評估

8、：對于P中每個(gè)假設(shè)h，計(jì)算Fitness(h)當(dāng) ，應(yīng)用交叉算子產(chǎn)生兩個(gè)后代，把所有的后代加入PS變異：使用均勻的概率從PS中選擇m%的成員，應(yīng)用變異算子更新：P?PS評估：對于P中每個(gè)h計(jì)算Fitness(h)從P中返回適應(yīng)度最高的假設(shè),2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,8,遺傳算法（3）,算法的每一次迭代以3種方式產(chǎn)生新一

9、代群體直接從當(dāng)前群體中選擇在選中的個(gè)體中進(jìn)行交叉操作在新群體上進(jìn)行變異操作遺傳算法執(zhí)行一種隨機(jī)的、并行柱狀的搜索，根據(jù)適應(yīng)度函數(shù)發(fā)現(xiàn)好的假設(shè),2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,9,表示假設(shè),遺傳算法中的假設(shè)常常被表示成二進(jìn)制位串，這便于用變異和交叉遺傳算子來操作把if-then規(guī)則編碼成位串首先使用位串描述單個(gè)屬性的值約束比如考慮屬性O(shè)utlook，它的值可以取

10、以下3個(gè)中的任一個(gè)：Sunny、Overcast、Rain，因此一個(gè)明顯的方法是使用一個(gè)長度為3的位串，每位對應(yīng)一個(gè)可能值，若某位為1，表示這個(gè)屬性可以取對應(yīng)的值多個(gè)屬性約束的合取可以很容易地表示為對應(yīng)位串的連接整個(gè)規(guī)則表示可以通過把描述規(guī)則前件和后件的位串連接起來,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,10,表示假設(shè)（2）,位串的特點(diǎn)表示規(guī)則的位串對假設(shè)空間中的每個(gè)屬性有

11、一個(gè)子串，即使該屬性不被規(guī)則的前件約束。得到一個(gè)固定長度的規(guī)則位串表示，其中特定位置的子串描述對應(yīng)特定屬性的約束規(guī)則集的表示：單個(gè)規(guī)則的位串表示連接起來有必要讓每個(gè)句法合法的位串表示一個(gè)有意義的假設(shè)假設(shè)也可以用符號描述來表示，而不是位串，比如計(jì)算機(jī)程序,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,11,遺傳算子,遺傳算法使用一系列算子來決定后代，算子對當(dāng)前群體中選定的成員進(jìn)行重

12、組表9-1列出了用來操作位串的典型遺傳算法算子，它們是生物進(jìn)化中的遺傳過程的理想化形式最常見的算子是交叉和變異交叉：從兩個(gè)雙親串中通過復(fù)制選定位產(chǎn)生兩個(gè)新的后代，每個(gè)后代的第i位是從它的某個(gè)雙親的第i位復(fù)制來的雙親中的哪一個(gè)在第i位起作用，由另一個(gè)稱為交叉掩碼的位串決定：單點(diǎn)交叉：前n位來自第一個(gè)雙親，余下的位來自第二個(gè)雙親兩點(diǎn)交叉：用一個(gè)雙親的中間片斷替換第二個(gè)雙親的中間片斷均勻交叉：合并了從兩個(gè)雙親以均勻概率抽取的位

13、,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,12,遺傳算子（2）,變異：從單一雙親產(chǎn)生后代，對位串產(chǎn)生隨機(jī)的小變化，方法是選取一個(gè)位，然后取反變異經(jīng)常是在應(yīng)用交叉之后其他算子使規(guī)則特化的算子直接泛化,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,13,適應(yīng)度函數(shù)和假設(shè)選擇,適應(yīng)度函數(shù)定義了候選假設(shè)的排序準(zhǔn)則如果學(xué)習(xí)任務(wù)是分

14、類的規(guī)則，那么適應(yīng)度函數(shù)中會(huì)有一項(xiàng)用來評價(jià)每個(gè)規(guī)則對訓(xùn)練樣例集合的分類精度，也可包含其他的準(zhǔn)則，比如規(guī)則的復(fù)雜度和一般性選擇假設(shè)的概率計(jì)算方法適應(yīng)度比例選擇（或稱輪盤賭選擇），選擇某假設(shè)的概率是通過這個(gè)假設(shè)的適應(yīng)度與當(dāng)前群體中其他成員的適應(yīng)度的比值得到的錦標(biāo)賽選擇，先從當(dāng)前群體中隨機(jī)選取兩個(gè)假設(shè)，再按照事先定義的概率p選擇適應(yīng)度較高的假設(shè)，按照概率1-p選擇適應(yīng)度較低的假設(shè)排序選擇，當(dāng)前群體中的假設(shè)按適應(yīng)度排序，某假設(shè)的概率與它

15、在排序列表中的位置成比例，而不是與適應(yīng)度成比例,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,14,舉例,遺傳算法可以被看作是通用的最優(yōu)化方法，它搜索一個(gè)巨大的候選假設(shè)空間，根據(jù)適應(yīng)度函數(shù)查找表現(xiàn)最好的假設(shè)遺傳算法盡管不能保證發(fā)現(xiàn)最優(yōu)的假設(shè)，但一般能夠發(fā)現(xiàn)具有較高適應(yīng)度的假設(shè)遺傳算法的廣泛應(yīng)用電路布線任務(wù)調(diào)度函數(shù)逼近選取人工神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),2003.12.18,機(jī)器學(xué)習(xí)-

16、遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,15,Gabil系統(tǒng),Dejong et al.1993的Gabil系統(tǒng)：遺傳算法在概念學(xué)習(xí)方面的應(yīng)用學(xué)習(xí)以命題規(guī)則的析取集合表示的布爾概念在對幾個(gè)概念學(xué)習(xí)問題的實(shí)驗(yàn)中發(fā)現(xiàn)，在泛化精度方面Gabil與其他學(xué)習(xí)算法大體相當(dāng)Gabil使用的算法就是表9-1描述的典型算法,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,16,

17、Gabil系統(tǒng)（2）,Gabil的具體實(shí)現(xiàn)表示：每個(gè)假設(shè)對應(yīng)一個(gè)命題規(guī)則的析取集，按照9.2.1節(jié)描述的方法編碼遺傳算子：變異：使用表9-2中的標(biāo)準(zhǔn)變異算子交叉：表9-2中的兩點(diǎn)交叉算子的一個(gè)擴(kuò)展，這種方法保證了產(chǎn)生的位串表示的規(guī)則集是良定義的適應(yīng)度函數(shù)：每個(gè)規(guī)則集的適應(yīng)度是根據(jù)它在訓(xùn)練數(shù)據(jù)上的分類精度計(jì)算的，F(xiàn)itness(h)=(correct(h))2,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯

18、者：曾華軍等 講者：陶曉鵬,17,Gabil系統(tǒng)的擴(kuò)展,增加兩個(gè)新算子AddAlternative，它泛化對某個(gè)特定屬性的約束，方法是把這個(gè)屬性對應(yīng)的子串中的一個(gè)0改為1，使用概率為0.01DropCondition，把一個(gè)特定屬性的所有位都替換為1，使用概率為0.60兩種使用新算子的方法對每一代群體中的每個(gè)假設(shè)以同樣的概率應(yīng)用對假設(shè)的位串進(jìn)行擴(kuò)展，使其包含另外兩位以決定是否可以對該假設(shè)應(yīng)用這兩個(gè)新算子,2003.12.18,

19、機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,18,假設(shè)空間搜索,遺傳算法采用一種隨機(jī)化的柱狀搜索來尋找最大適應(yīng)度的假設(shè)，與前面章節(jié)的搜索算法有很大不同梯度下降搜索從一個(gè)假設(shè)平滑移動(dòng)到另一個(gè)非常相似的假設(shè)遺傳算法的移動(dòng)可能非常突然，使用和雙親根本不同的后代替換雙親假設(shè)遺傳算法的搜索不太可能像梯度下降方法那樣陷入局部最小值的問題遺傳算法應(yīng)用中的一個(gè)難題：擁擠問題擁擠：群體中某個(gè)體適應(yīng)度大大高于其他個(gè)體

20、，因此它迅速繁殖，以至于此個(gè)體和與它相似的個(gè)體占據(jù)了群體的絕大部分擁擠降低了群體的多樣性，從而減慢了進(jìn)化的進(jìn)程,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,19,假設(shè)空間搜索（2）,降低擁擠的策略使用錦標(biāo)賽選擇或排序選擇，而不用適應(yīng)度比例輪盤賭選擇適應(yīng)度共享，根據(jù)群體中與某個(gè)體相似的個(gè)體數(shù)量，減小該個(gè)體的適應(yīng)度對可重組生成后代的個(gè)體種類進(jìn)行限制，比如受到生物進(jìn)化的啟示通過只允

21、許最相似的個(gè)體重組，可以在群體中促成相似的個(gè)體聚類，形成亞種按空間分布個(gè)體，只允許相鄰的個(gè)體重組,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,20,群體進(jìn)化和模式理論,模式理論（Holland1975）提供了一種用數(shù)學(xué)方法刻畫遺傳算法中群體進(jìn)化的過程模式是由若干0、1和*組成的任意串，*表示任意符號模式理論根據(jù)每個(gè)模式的實(shí)例數(shù)量來刻畫遺傳算法中群體的進(jìn)化令m(s,t)表示群體中

22、的模式s在時(shí)間t的實(shí)例數(shù)量模式理論根據(jù)m(s,t)和模式、群體及其他屬性來描述m(s,t+1)的期望值,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,21,群體進(jìn)化和模式理論（2）,遺傳算法中群體的進(jìn)化依賴于幾個(gè)步驟，即選擇、重組和變異。符號表示：f(h)表示位串個(gè)體h的適應(yīng)度n為群體中個(gè)體的總數(shù)量 表示在時(shí)間t群體中所有個(gè)體的平均適應(yīng)度 表示在時(shí)間t群體

23、中模式s的實(shí)例的平均適應(yīng)度 表示個(gè)體h既是模式s的一個(gè)代表，又是時(shí)間t群體的一個(gè)成員,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,22,群體進(jìn)化和模式理論（3）,E(m(s,t+1))的推導(dǎo)，僅考慮選擇的情況式子9.3表明，在t+1代中，模式s的實(shí)例期望數(shù)量與這個(gè)模式的實(shí)例在時(shí)間t內(nèi)的平均適應(yīng)度成正比，與群體的所有成員的平均適應(yīng)度成反比，適應(yīng)度高的模式

24、的影響力會(huì)隨著時(shí)間增加,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,23,群體進(jìn)化和模式理論（4）,同時(shí)考慮交叉和變異，僅考慮單點(diǎn)交叉和可能造成的負(fù)面影響最左一項(xiàng)描述了選擇步的影響，中間一項(xiàng)描述了單點(diǎn)交叉算子的影響，最后一項(xiàng)描述了代表模式s的任意個(gè)體在應(yīng)用了變異算子后還代表s的概率模式理論不完備的是：無法考慮交叉和變異的正面影響其他一些新的理論分析：基于馬爾可夫鏈模型和統(tǒng)計(jì)力

25、學(xué)模型,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,24,遺傳編程,遺傳編程是進(jìn)化計(jì)算的一種形式，其中進(jìn)化群體中的個(gè)體是計(jì)算機(jī)程序而不是位串遺傳編程中的程序一般被表示為程序的解析樹，每個(gè)函數(shù)調(diào)用被表示為樹的一個(gè)節(jié)點(diǎn)，函數(shù)的參數(shù)通過它的子節(jié)點(diǎn)給出遺傳編程算法維護(hù)多個(gè)個(gè)體組成的群體，在每一步迭代中，它使用選擇、交叉、變異產(chǎn)生新一代個(gè)體群體中某個(gè)體程序的適應(yīng)度一般通過在訓(xùn)練數(shù)據(jù)上執(zhí)行這

26、個(gè)程序來決定交叉操作：在一個(gè)雙親程序中隨機(jī)選擇一個(gè)子樹，然后用另一個(gè)雙親的子樹替代這個(gè)子樹,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,25,遺傳編程舉例,學(xué)習(xí)堆砌圖9-3所示的子塊的算法（ Koza1992）開發(fā)一個(gè)通用的算法來把字塊堆疊成單個(gè)棧，拼出單詞，無論這些字塊初始的結(jié)構(gòu)如何可執(zhí)行的動(dòng)作是每次只允許移動(dòng)一個(gè)字塊，棧中最上面的字塊可以被移到桌面上，或者桌面上的字塊移到棧頂

27、原子函數(shù)包含3個(gè)端點(diǎn)參數(shù)CS，當(dāng)前棧，即棧頂字塊的名字，棧空時(shí)為FTB，最上面的正確字塊，即該字塊和它以下的字塊均為正確順序的字塊NN，下一個(gè)所需字塊，即為了拼成單詞“universal”，棧內(nèi)緊鄰TB之上的所需字塊的名字，當(dāng)不再需要時(shí)為F,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,26,遺傳編程舉例（2）,原子函數(shù)MS x：移動(dòng)到棧，如果字塊x在桌面上，把x移動(dòng)到棧頂，并

28、且返回T；否則什么也不做，返回FMT x：移動(dòng)到桌面，如果字塊x是在棧中某個(gè)位置，把棧頂?shù)淖謮K移動(dòng)到桌面，并且返回T；否則返回FEQ x y：如果x等于y，返回T；否則FNOT x：如果x=F，返回T；否則FDU x y：反復(fù)執(zhí)行表達(dá)式x直到表達(dá)式y(tǒng)返回TKoza提供了166個(gè)訓(xùn)練問題，表示不同的初始字塊結(jié)構(gòu)，任意給定程序的適應(yīng)度就是它解決的訓(xùn)練問題的數(shù)量群體被初始化為300個(gè)隨機(jī)程序的集合，經(jīng)過10代后，系統(tǒng)發(fā)現(xiàn)了下面的程

29、序解決所有的166個(gè)問題(EQ (DU (MT CS) (NOT CS)) (DU (MS NN) (NOT NN))),2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,27,遺傳編程說明,遺傳編程把遺傳算法擴(kuò)展到對完整的計(jì)算機(jī)程序的進(jìn)化盡管遺傳算法要搜索巨大的假設(shè)空間，但已經(jīng)證實(shí)相當(dāng)數(shù)量的應(yīng)用中遺傳編程產(chǎn)生了很好的結(jié)果遺傳編程在更復(fù)雜的任務(wù)中的應(yīng)用電子濾波電路的設(shè)計(jì)蛋白質(zhì)分子

30、片斷的分析在大多數(shù)情況下，表示方法的選擇和適應(yīng)度函數(shù)的選擇對遺傳編程的性能是至關(guān)重要的，一個(gè)活躍的研究領(lǐng)域是自動(dòng)發(fā)現(xiàn)和合并子程序，改善最初的原子函數(shù)集合，從而允許系統(tǒng)動(dòng)態(tài)地改變用以構(gòu)建個(gè)體的原子,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,28,進(jìn)化和學(xué)習(xí)模型,有關(guān)進(jìn)化系統(tǒng)的一個(gè)有趣問題：單一個(gè)體生命期間的學(xué)習(xí)與整個(gè)物種較長時(shí)期內(nèi)由進(jìn)化促成的學(xué)習(xí)，它們的關(guān)系是什么？拉馬克進(jìn)化拉馬

31、克在19世紀(jì)末提出，多代的進(jìn)化直接受到個(gè)別生物體在它們生命期間的經(jīng)驗(yàn)的影響目前的科學(xué)證據(jù)不支持拉馬克模型但近來的計(jì)算機(jī)研究表明，拉馬克過程有時(shí)可以提高計(jì)算機(jī)遺傳算法的效率,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,29,進(jìn)化和學(xué)習(xí)模型（2）,鮑德溫效應(yīng)通過個(gè)體學(xué)習(xí)改變進(jìn)化進(jìn)程的機(jī)制基于以下現(xiàn)象如果一個(gè)物種在一個(gè)變化的環(huán)境中進(jìn)化，那么進(jìn)化的壓力會(huì)支持有學(xué)習(xí)能力的個(gè)體，這種學(xué)習(xí)

32、能力可以使個(gè)體在其生命期間執(zhí)行一種小的局部搜索，以最大化它的適應(yīng)度，相反，不學(xué)習(xí)的個(gè)體的適應(yīng)度完全取決于它的遺傳結(jié)構(gòu)，會(huì)處于相對劣勢具備學(xué)習(xí)能力的個(gè)體可以通過學(xué)習(xí)克服遺傳代碼中的“丟失的”或“并非最優(yōu)的”特性，從而支持更加多樣化的基因池，然后促進(jìn)適應(yīng)性更加快速地進(jìn)化提供了一種間接的機(jī)制，使個(gè)體的學(xué)習(xí)可以正面影響進(jìn)化速度,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,30,進(jìn)化和學(xué)習(xí)模

33、型（3）,人們一直努力開發(fā)研究鮑德溫效應(yīng)的計(jì)算模型Hinton & Nowlan1987對一個(gè)簡單神經(jīng)網(wǎng)絡(luò)的群體進(jìn)行試驗(yàn)在一個(gè)網(wǎng)絡(luò)個(gè)體的“生命期”間，它的一些權(quán)值是固定的，而其他權(quán)是可被訓(xùn)練的在群體進(jìn)化初期的各代中，具有很多可訓(xùn)練權(quán)值的個(gè)體占據(jù)較大的比例隨著進(jìn)化的進(jìn)行，群體向著遺傳給定權(quán)值和較少依賴個(gè)體學(xué)習(xí)權(quán)值的方向進(jìn)化，正確的固定權(quán)值的數(shù)量趨于增長,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者

34、：曾華軍等 講者：陶曉鵬,31,并行遺傳算法,遺傳算法很自然地適合并行實(shí)現(xiàn)粗粒度并行方法把群體細(xì)分成相對獨(dú)立的個(gè)體群，稱為類屬，然后為每個(gè)類屬分配一個(gè)不同的計(jì)算節(jié)點(diǎn)，在每個(gè)節(jié)點(diǎn)進(jìn)行標(biāo)準(zhǔn)的GA搜索類屬之間的通信和交叉發(fā)生的頻率與類屬內(nèi)相比較低，類屬之間的交換通過遷移來進(jìn)行，也就是某些個(gè)體從一個(gè)類屬復(fù)制或交換到其他類屬這個(gè)過程模擬了以下的生物進(jìn)化方式，即自然界中異體受精可能發(fā)生在分離的物種子群體之間這種方法的一個(gè)好處是減少了非并行

35、GA經(jīng)常碰到的擁擠問題細(xì)粒度并行方法給每個(gè)個(gè)體分配一個(gè)處理器，然后相鄰的個(gè)體間發(fā)生重組,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,32,小結(jié),遺傳算法用一種隨機(jī)化的并行爬山搜索來發(fā)現(xiàn)使預(yù)先定義的適應(yīng)度函數(shù)最優(yōu)的假設(shè)遺傳算法基于對生物進(jìn)化的模擬，維護(hù)一個(gè)由競爭假設(shè)組成的多樣化群體，在每一次迭代中，選出群體中適應(yīng)度最高的成員來產(chǎn)生后代，替代群體中適應(yīng)度最差的成員遺傳算法闡明了如何

36、把學(xué)習(xí)過程看成最優(yōu)化過程的一個(gè)特例，學(xué)習(xí)任務(wù)就是根據(jù)預(yù)先定義的適應(yīng)度函數(shù)發(fā)現(xiàn)最優(yōu)假設(shè)遺傳編程是遺傳算法的變體，在遺傳編程中，被操作的假設(shè)是計(jì)算機(jī)程序而不是位串,2003.12.18,機(jī)器學(xué)習(xí)-遺傳算法 作者：Mitchell 譯者：曾華軍等 講者：陶曉鵬,33,補(bǔ)充讀物,在計(jì)算機(jī)科學(xué)發(fā)展的早期，人們就開始探索基于進(jìn)化的計(jì)算方法（ Box1957、Bledsoe1964）Rechenberg1965,1973、Schwefel1975

37、,1977,1995開發(fā)的進(jìn)化策略用來優(yōu)化工程設(shè)計(jì)中的數(shù)字參數(shù)Folgel & Owens & Walsh1966開發(fā)了進(jìn)化編程，作為進(jìn)化有限狀態(tài)機(jī)的一種方法Koza1992介紹了遺傳編程，把遺傳算法的搜索策略應(yīng)用到由計(jì)算機(jī)程序組成的假設(shè)中K. Dejong和他的學(xué)生開發(fā)了使用GA學(xué)習(xí)規(guī)則集的方法，每個(gè)規(guī)則集是競爭假設(shè)組成的群體的一個(gè)成員Holland和他的學(xué)生設(shè)定每個(gè)規(guī)則是群體的一個(gè)成員，群體本身是一個(gè)規(guī)則集,