第9章遺傳算法

1、第9章 遺傳算法動機 算法 實現(xiàn)wGenetic Algorithm （GA）w受生物進(jìn)化啟發(fā)的學(xué)習(xí)算法w搜索特點： 不是從簡單到復(fù)雜的搜索 不是從一般到特殊的搜索 是從當(dāng)前最佳假設(shè)經(jīng)過變異和重組來尋求更好假設(shè)w當(dāng)前群體(Population)：當(dāng)前使用的一組假設(shè)w使用目前適應(yīng)度最高的假設(shè)的后代替換群體的某個部分9.1 動機GA算法的合理性w在生物系統(tǒng)中，進(jìn)化被認(rèn)為是一種成功的自適應(yīng)方法，且具有很好的健壯性wGA搜索的假設(shè)空間中，假設(shè)的各個部分相互作用，每一部分對總的假設(shè)適應(yīng)度難以建模wGA算法易于并行化，費用低廉w進(jìn)化計算(Evolutionary Computation)： 遺傳算法 遺傳

2、編程 鮑德溫效應(yīng)遺傳算法w算法目標(biāo)：搜索候選假設(shè)空間并確定最佳假設(shè)w什么是最佳假設(shè)？ 使適應(yīng)度(fitness)最優(yōu)的假設(shè)w什么是適應(yīng)度？ 為需解決的問題預(yù)先定義的數(shù)字度量遺傳算法w算法實現(xiàn)的細(xì)節(jié)各有不同w都具有共同的結(jié)構(gòu)：算法迭代更新一個假設(shè)池w假設(shè)池稱為群體w通過適應(yīng)度函數(shù)的評估，從當(dāng)前群體中用概率的方法選取合適的個體w一部分保持原樣進(jìn)入下一代群體，另一部分使用交叉和變異的方法產(chǎn)生新個體遺傳算法原型GA群體PFitnessThresh假設(shè)數(shù)量p交叉率r變異率mP中適應(yīng)度最高的假設(shè)Random維持一個有p個假設(shè)組成的群體后繼群體Ps通過根據(jù)假設(shè)的適應(yīng)度用概率的方法選擇個體和加入新的假設(shè)形成新

3、假設(shè)得到的兩種途徑：對最高適應(yīng)度假設(shè)用交叉算子；通過創(chuàng)建部分假設(shè)的單點變異遺傳算法w競爭：一個假設(shè)被選入下一個群體的概率與它自己的適應(yīng)度成正比w繁殖：交叉操作產(chǎn)生新個體w變異：隨機選位取反9.2.1 表示假設(shè)w規(guī)則的前件和后件 IF 前件 THEN 后件w規(guī)則的編碼：位串w避免無意義的位串： 采用合適的編碼方式來避免 賦予極低的適應(yīng)度函數(shù)值9.2.2 遺傳算子w算子(Operator)：用來對群體中的成員進(jìn)行重組和變異，以決定后代w交叉算子(Crossover Operator)：從雙親中復(fù)制選定位產(chǎn)生兩個新的后代w變異算子(Mutation Operator)：隨機選位取反w人類的遺傳是如何

4、進(jìn)行交叉和變異的？9.2.3 適應(yīng)度函數(shù)和假設(shè)選擇w適應(yīng)度函數(shù)(Fitness)：以概率方法選擇下一代群體的準(zhǔn)則w選擇方案： 輪盤賭選擇：適應(yīng)度大小 錦標(biāo)賽選擇：適應(yīng)度高則按照概率p被選 排序選擇：按照適應(yīng)度排序，每個排序位置有確定的被選概率p9.3 舉例/xJava/GA/遺傳與進(jìn)化模擬草原與吃貨w環(huán)境：空地、草塊、墻w吃貨（eater）：吃最多的草具有內(nèi)部狀態(tài)每次做一個移動的決定：w向前1格、向后1格w左轉(zhuǎn)1格、右轉(zhuǎn)1格草原與吃貨w環(huán)境：空地、草塊、墻w吃貨（eater）：吃最多的草具有內(nèi)部狀態(tài)每次做一個移動的決定w規(guī)則（基因、染色體）：狀態(tài)改變、轉(zhuǎn)向 映射 原狀態(tài)、視野共有64條規(guī)則適者生存w每年底算賬，計算下年吃貨名額w本年吃的越多，則獲得后代的幾率和數(shù)量越多w本年吃的太少，則基本不可能有后代w得到后代的操作：遺傳（copy）變異（mutation）交叉（crossover）9.5 遺傳編程程序表示舉例9.6 進(jìn)化和學(xué)習(xí)模型w生物個體的適應(yīng)能力改善與物種進(jìn)化的關(guān)系w拉馬克進(jìn)化 個別生物的生存經(jīng)驗直接影響其后代的遺傳結(jié)構(gòu) 有利于提高計算機遺傳算法的效率w鮑德溫效應(yīng) 如果一個物種在一個變化的環(huán)境中進(jìn)化，那么進(jìn)化的壓力會選擇有學(xué)習(xí)能力