機器學習遺傳算法

1機器學習第9章遺傳算法2概述遺傳算法是一種大致基于模擬進化的學習方法假設(shè)通常被描述為二進制位串，也可以是符號表達式或計算機程序搜索合適的假設(shè)從若干初始假設(shè)的群體或集合開始當前群體的成員通過模擬生物進化的方式來產(chǎn)生下一代群體，比如隨機變異和交叉每一步，根據(jù)給定的適應度評估當前群體中的假設(shè)，而后使用概率方法選出適應度最高的假設(shè)作為產(chǎn)生下一代的種子遺傳算法已被成功用于多種學習任務和最優(yōu)化問題中，比如學習機器人控制的規(guī)則集和優(yōu)化人工神經(jīng)網(wǎng)絡的拓撲結(jié)構(gòu)和學習參數(shù)本章主要介紹了基于位串描述假設(shè)的遺傳算法和基于計算機程序描述假設(shè)的遺傳編程3動機遺傳算法（GA）是一種受生物進化啟發(fā)的學習方法，它不再是從一般到特殊或從簡單到復雜地搜索假設(shè)，而是通過變異和重組當前已知的最好假設(shè)來生成后續(xù)的假設(shè)每一步，更新被稱為當前群體的一組假設(shè)，方法是使用當前適應度最高的假設(shè)的后代替代群體的某個部分這個過程形成了假設(shè)的生成測試的柱狀搜索，其中若干個最佳當前假設(shè)的變體最有可能在下一步被考慮4動機（2）遺傳算法的普及和發(fā)展得益于下面的因素在生物系統(tǒng)中，進化被認為是一種成功的自適應方法，具有很好的健壯性遺傳算法搜索的假設(shè)空間中，假設(shè)的各個部分相互作用，每一部分對總的假設(shè)適應度的影響難以建模遺傳算法易于并行化本章內(nèi)容安排描述了遺傳算法，舉例演示了它的用法，分析了它搜索的空間的特性描述了遺傳算法的一個變體：遺傳編程，這個方法中，整個計算機程序向著某個適應度準則進化介紹了一些有關(guān)生物進化的課題（遺傳算法和遺傳編程是進化計算領(lǐng)域中的兩種普遍方法），比如鮑德溫效應，它描述了個體的學習能力與整個群體進化速度之間的相互作用5遺傳算法遺傳算法研究的問題是搜索候選假設(shè)空間并確定最佳假設(shè)最佳假設(shè)被定義為使適應度最優(yōu)的假設(shè)適應度是為當前問題預先定義的數(shù)字度量，比如：如果學習任務是在給定一個未知函數(shù)的輸入輸出訓練樣例后逼近這個函數(shù)，適應度可被定義為假設(shè)在訓練數(shù)據(jù)上的精度如果是學習下國際象棋的策略，適應度可被定義為該個體在當前群體中與其他個體對弈的獲勝率6遺傳算法（2）遺傳算法具有以下的共同結(jié)構(gòu)：算法迭代更新一個假設(shè)池，這個假設(shè)池稱為群體在每一次迭代中，根據(jù)適應度評估群體中的所有成員，然后用概率方法選取適應度最高的個體產(chǎn)生新一代群體在被選中的個體中，一部分保持原樣地進入下一代群體，其他被用作產(chǎn)生后代個體的基礎(chǔ)，其中應用交叉和變異這樣的遺傳方法7表9-1遺傳算法原型GA(Fitness,Fitness_threshold,p,r,m)Fitness：適應度評分函數(shù)Fitness_threshold：指定終止判據(jù)的閾值p：群體中包含的假設(shè)數(shù)量r：每一步中通過交叉取代群體成員的比例m：變異率初始化群體：P隨機產(chǎn)生的p個假設(shè)評估：對于P中每個假設(shè)h，計算Fitness(h)當<Fitness_threshold，產(chǎn)生新一代PS，做：選擇：用概率方法選擇P的(1-r)p個成員加入PS，概率公式是交叉：按概率從P中選擇rp/2對假設(shè)，對于每對假設(shè)<h1,h2>，應用交叉算子產(chǎn)生兩個后代，把所有的后代加入PS變異：使用均勻的概率從PS中選擇m%的成員，應用變異算子更新：PPS評估：對于P中每個h計算Fitness(h)從P中返回適應度最高的假設(shè)8遺傳算法（3）算法的每一次迭代以3種方式產(chǎn)生新一代群體直接從當前群體中選擇在選中的個體中進行交叉操作在新群體上進行變異操作遺傳算法執(zhí)行一種隨機的、并行柱狀的搜索，根據(jù)適應度函數(shù)發(fā)現(xiàn)好的假設(shè)9表示假設(shè)遺傳算法中的假設(shè)常常被表示成二進制位串，這便于用變異和交叉遺傳算子來操作把if-then規(guī)則編碼成位串首先使用位串描述單個屬性的值約束比如考慮屬性O(shè)utlook，它的值可以取以下3個中的任一個：Sunny、Overcast、Rain，因此一個明顯的方法是使用一個長度為3的位串，每位對應一個可能值，若某位為1，表示這個屬性可以取對應的值多個屬性約束的合取可以很容易地表示為對應位串的連接整個規(guī)則表示可以通過把描述規(guī)則前件和后件的位串連接起來10表示假設(shè)（2）位串的特點表示規(guī)則的位串對假設(shè)空間中的每個屬性有一個子串，即使該屬性不被規(guī)則的前件約束。得到一個固定長度的規(guī)則位串表示，其中特定位置的子串描述對應特定屬性的約束規(guī)則集的表示：單個規(guī)則的位串表示連接起來有必要讓每個句法合法的位串表示一個有意義的假設(shè)假設(shè)也可以用符號描述來表示，而不是位串，比如計算機程序11遺傳算子遺傳算法使用一系列算子來決定后代，算子對當前群體中選定的成員進行重組表9-1列出了用來操作位串的典型遺傳算法算子，它們是生物進化中的遺傳過程的理想化形式最常見的算子是交叉和變異交叉：從兩個雙親串中通過復制選定位產(chǎn)生兩個新的后代，每個后代的第i位是從它的某個雙親的第i位復制來的雙親中的哪一個在第i位起作用，由另一個稱為交叉掩碼的位串決定：單點交叉：前n位來自第一個雙親，余下的位來自第二個雙親兩點交叉：用一個雙親的中間片斷替換第二個雙親的中間片斷均勻交叉：合并了從兩個雙親以均勻概率抽取的位12遺傳算子（2）變異：從單一雙親產(chǎn)生后代，對位串產(chǎn)生隨機的小變化，方法是選取一個位，然后取反變異經(jīng)常是在應用交叉之后其他算子使規(guī)則特化的算子直接泛化13適應度函數(shù)和假設(shè)選擇適應度函數(shù)定義了候選假設(shè)的排序準則如果學習任務是分類的規(guī)則，那么適應度函數(shù)中會有一項用來評價每個規(guī)則對訓練樣例集合的分類精度，也可包含其他的準則，比如規(guī)則的復雜度和一般性選擇假設(shè)的概率計算方法適應度比例選擇（或稱輪盤賭選擇），選擇某假設(shè)的概率是通過這個假設(shè)的適應度與當前群體中其他成員的適應度的比值得到的錦標賽選擇，先從當前群體中隨機選取兩個假設(shè)，再按照事先定義的概率p選擇適應度較高的假設(shè)，按照概率1-p選擇適應度較低的假設(shè)排序選擇，當前群體中的假設(shè)按適應度排序，某假設(shè)的概率與它在排序列表中的位置成比例，而不是與適應度成比例14舉例遺傳算法可以被看作是通用的最優(yōu)化方法，它搜索一個巨大的候選假設(shè)空間，根據(jù)適應度函數(shù)查找表現(xiàn)最好的假設(shè)遺傳算法盡管不能保證發(fā)現(xiàn)最優(yōu)的假設(shè)，但一般能夠發(fā)現(xiàn)具有較高適應度的假設(shè)遺傳算法的廣泛應用電路布線任務調(diào)度函數(shù)逼近選取人工神經(jīng)網(wǎng)絡的拓撲結(jié)構(gòu)15Gabil系統(tǒng)Dejongetal.1993的Gabil系統(tǒng)：遺傳算法在概念學習方面的應用學習以命題規(guī)則的析取集合表示的布爾概念在對幾個概念學習問題的實驗中發(fā)現(xiàn)，在泛化精度方面Gabil與其他學習算法大體相當Gabil使用的算法就是表9-1描述的典型算法16Gabil系統(tǒng)（2）Gabil的具體實現(xiàn)表示：每個假設(shè)對應一個命題規(guī)則的析取集，按照節(jié)描述的方法編碼遺傳算子：變異：使用表9-2中的標準變異算子交叉：表9-2中的兩點交叉算子的一個擴展，這種方法保證了產(chǎn)生的位串表示的規(guī)則集是良定義的適應度函數(shù)：每個規(guī)則集的適應度是根據(jù)它在訓練數(shù)據(jù)上的分類精度計算的，F(xiàn)itness(h)=(correct(h))217Gabil系統(tǒng)的擴展增加兩個新算子AddAlternative，它泛化對某個特定屬性的約束，方法是把這個屬性對應的子串中的一個0改為1，使用概率為0.01DropCondition，把一個特定屬性的所有位都替換為1，使用概率為0.60兩種使用新算子的方法對每一代群體中的每個假設(shè)以同樣的概率應用對假設(shè)的位串進行擴展，使其包含另外兩位以決定是否可以對該假設(shè)應用這兩個新算子18假設(shè)空間搜索遺傳算法采用一種隨機化的柱狀搜索來尋找最大適應度的假設(shè)，與前面章節(jié)的搜索算法有很大不同梯度下降搜索從一個假設(shè)平滑移動到另一個非常相似的假設(shè)遺傳算法的移動可能非常突然，使用和雙親根本不同的后代替換雙親假設(shè)遺傳算法的搜索不太可能像梯度下降方法那樣陷入局部最小值的問題遺傳算法應用中的一個難題：擁擠問題擁擠：群體中某個體適應度大大高于其他個體，因此它迅速繁殖，以至于此個體和與它相似的個體占據(jù)了群體的絕大部分擁擠降低了群體的多樣性，從而減慢了進化的進程19假設(shè)空間搜索（2）降低擁擠的策略使用錦標賽選擇或排序選擇，而不用適應度比例輪盤賭選擇適應度共享，根據(jù)群體中與某個體相似的個體數(shù)量，減小該個體的適應度對可重組生成后代的個體種類進行限制，比如受到生物進化的啟示通過只允許最相似的個體重組，可以在群體中促成相似的個體聚類，形成亞種按空間分布個體，只允許相鄰的個體重組20群體進化和模式理論模式理論（Holland1975）提供了一種用數(shù)學方法刻畫遺傳算法中群體進化的過程模式是由若干0、1和*組成的任意串，*表示任意符號模式理論根據(jù)每個模式的實例數(shù)量來刻畫遺傳算法中群體的進化令m(s,t)表示群體中的模式s在時間t的實例數(shù)量模式理論根據(jù)m(s,t)和模式、群體及其他屬性來描述m(s,t+1)的期望值21群體進化和模式理論（2）遺傳算法中群體的進化依賴于幾個步驟，即選擇、重組和變異。符號表示：f(h)表示位串個體h的適應度n為群體中個體的總數(shù)量表示在時間t群體中所有個體的平均適應度表示在時間t群體中模式s的實例的平均適應度表示個體h既是模式s的一個代表，又是時間t群體的一個成員22群體進化和模式理論（3）E(m(s,t+1))的推導，僅考慮選擇的情況式子9.3表明，在t+1代中，模式s的實例期望數(shù)量與這個模式的實例在時間t內(nèi)的平均適應度成正比，與群體的所有成員的平均適應度成反比，適應度高的模式的影響力會隨著時間增加23群體進化和模式理論（4）同時考慮交叉和變異，僅考慮單點交叉和可能造成的負面影響 最左一項描述了選擇步的影響，中間一項描述了單點交叉算子的影響，最后一項描述了代表模式s的任意個體在應用了變異算子后還代表s的概率模式理論不完備的是：無法考慮交叉和變異的正面影響其他一些新的理論分析：基于馬爾可夫鏈模型和統(tǒng)計力學模型24遺傳編程遺傳編程是進化計算的一種形式，其中進化群體中的個體是計算機程序而不是位串遺傳編程中的程序一般被表示為程序的解析樹，每個函數(shù)調(diào)用被表示為樹的一個節(jié)點，函數(shù)的參數(shù)通過它的子節(jié)點給出遺傳編程算法維護多個個體組成的群體，在每一步迭代中，它使用選擇、交叉、變異產(chǎn)生新一代個體群體中某個體程序的適應度一般通過在訓練數(shù)據(jù)上執(zhí)行這個程序來決定交叉操作：在一個雙親程序中隨機選擇一個子樹，然后用另一個雙親的子樹替代這個子樹25遺傳編程舉例學習堆砌圖9-3所示的子塊的算法（Koza1992）開發(fā)一個通用的算法來把字塊堆疊成單個棧，拼出單詞，無論這些字塊初始的結(jié)構(gòu)如何可執(zhí)行的動作是每次只允許移動一個字塊，棧中最上面的字塊可以被移到桌面上，或者桌面上的字塊移到棧頂原子函數(shù)包含3個端點參數(shù)CS，當前棧，即棧頂字塊的名字，?？諘r為FTB，最上面的正確字塊，即該字塊和它以下的字塊均為正確順序的字塊NN，下一個所需字塊，即為了拼成單詞“universal”，棧內(nèi)緊鄰TB之上的所需字塊的名字，當不再需要時為F26遺傳編程舉例（2）原子函數(shù)MSx：移動到棧，如果字塊x在桌面上，把x移動到棧頂，并且返回T；否則什么也不做，返回FMTx：移動到桌面，如果字塊x是在棧中某個位置，把棧頂?shù)淖謮K移動到桌面，并且返回T；否則返回FEQxy：如果x等于y，返回T；否則FNOTx：如果x=F，返回T；否則FDUxy：反復執(zhí)行表達式x直到表達式y(tǒng)返回TKoza提供了166個訓練問題，表示不同的初始字塊結(jié)構(gòu)，任意給定程序的適應度就是它解決的訓練問題的數(shù)量群體被初始化為300個隨機程序的集合，經(jīng)過10代后，系統(tǒng)發(fā)現(xiàn)了下面的程序解決所有的166個問題

(EQ(DU(MTCS)(NOTCS))(DU(MSNN)(NOTNN)))27遺傳編程說明遺傳編程把遺傳算法擴展到對完整的計算機程序的進化盡管遺傳算法要搜索巨大的假設(shè)空間，但已經(jīng)證實相當數(shù)量的應用中遺傳編程產(chǎn)生了很好的結(jié)果遺傳編程在更復雜的任務中的應用電子濾波電路的設(shè)計蛋白質(zhì)分子片斷的分析在大多數(shù)情況下，表示方法的選擇和適應度函數(shù)的選擇對遺傳編程的性能是至關(guān)重要的，一個活躍的研究領(lǐng)域是自動發(fā)現(xiàn)和合并子程序，改善最初的原子函數(shù)集合，從而允許系統(tǒng)動態(tài)地改變用以構(gòu)建個體的原子28進化和學習模型有關(guān)進化系統(tǒng)的一個有趣問題：單一個體生命期間的學習與整個物種較長時期內(nèi)由進化促成的學習，它們的關(guān)系是什么？拉馬克進化拉馬克在19世紀末提出，多代的進化直接受到個別生物體在它們生命期間的經(jīng)驗的影響目前的科學證據(jù)不支持拉馬克模型但近來的計算機研究表明，拉馬克過程有時可以提高計算機遺傳算法的效率29進化和學習模型（2）鮑德溫效應通過個體學習改變進化進程的機制基于以下現(xiàn)象如果一個物種在一個變化的環(huán)境中進化，那么進化的壓力會支持有學習能力的個體，這種學習能力可以使個體在其生命期間執(zhí)行一種小的局部搜索，以最大化它的適應度，相反，不學習的個體的適應度完全取決于它的遺傳結(jié)構(gòu)，會處于相對劣勢具備學習能力的個體可以通過學習克服遺傳代碼中的“丟失的”或“并非最優(yōu)的”特性，從而支持更加多樣化的基因池，然后促進適應性更加快速地進化提供了一種間接的機制，使個體的學習可以正面影響進化速度30進化和學習模型（3）人們一直努力開發(fā)研究鮑德溫效應的計算模型Hinton&Nowlan1987對一個簡單神經(jīng)網(wǎng)絡的群體進行試驗在一個網(wǎng)絡個體的“生命期”間，它的一些權(quán)值是固定的，而其他權(quán)是可被訓練的在群體進化初期的各代中，具有很多可訓練權(quán)值的個體占據(jù)較大的比例隨著進化的進行，群體向著遺傳給定權(quán)值和較少依賴個體學習權(quán)值的方向進化，正確的固定權(quán)值的數(shù)量趨于增長31并行遺傳算法遺傳算法很自然地適合并行實現(xiàn)粗粒度并行方法把群體細分成相對獨立的個體群，稱為類屬，然后為每個類屬分配一個不同的計算節(jié)點，在每個節(jié)點進行標準的GA搜索類屬之間的通信和交叉發(fā)生的頻率與類屬內(nèi)相比較低，類屬之間的交換通過遷移來進行，也就是某些個體從一個類屬復制或交換到其他類屬這個過程模擬了以下的生物進化方式，即自然界中異體受精可能發(fā)生在分離的物種子群體之間這種方法的一個好處是減少了非并行GA經(jīng)常碰到的擁擠問題細粒度并行方法給每個個體分配一個處理器，然