【文章內(nèi)容簡介】 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本思想 ? 變異 (mutation):對群體 P(t)中的每一個個體，以某一概率 (稱為變異概率，mutation rate)改變某一個或一些基因座上基因值為其它的等位基因。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 特點 ? 以決策變量的編碼作為運算對象 ? 以目標(biāo)函數(shù)值作為搜索信息 ? 同時進行解空間的多點搜索 ? 使用概率搜索技術(shù) 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 算法實現(xiàn)關(guān)鍵 ? 染色體編碼 ? 群體的初始化 ? 適應(yīng)值評價 ? 選擇種群（輪盤賭） ? 種群交配 ? 種群變異 ? 算法流程 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 基本遺傳算法（ Simple Geic Algorithms,簡稱 SGA）是一種統(tǒng)一的最基本的遺傳算法，它只使用選擇、交叉、變異這三種基本遺傳算子，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個基本框架，同時也具有一定的應(yīng)用價值。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑴ 基本遺傳算法的構(gòu)成要素 ? ① 染色體編碼方法?；具z傳算法使用固定長度的二進制符號串來表示群體中的個體，其等位基因是由二值符號集 {0， 1}所組成的。初始群體中各個個體的基因值可用均勻分布的隨機數(shù)來生成。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑴ 基本遺傳算法的構(gòu)成要素 ? ② 個體適應(yīng)度評價 。 基本遺傳算法按與個體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個個體遺傳到下一代群體中的機會多少 。 為正確計算這個概率 ， 這里要求所有個體的適應(yīng)度必須為正數(shù)或零 。 ? ③遺傳算子?；具z傳算法使用下述三種遺傳算子：選擇運算使用比例選擇算子，交叉運算使用單點交叉算子，變異運算使用基本位變異算子或均勻變異算子。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑴ 基本遺傳算法的構(gòu)成要素 ④基本遺傳算法的運行參數(shù)?；具z傳算法有下述 4個運行參數(shù)需要提前設(shè)定：群體大小 M，即群體中所含個體數(shù)目，一般取為 20~100；遺傳運算的終止進化代數(shù) T，一般取為 100~500； 交叉概率 Pc，一般取為 ~； 變異概率 Pm，一般取為 ~。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑵ 基本遺傳算法的實現(xiàn) ① 個體適應(yīng)度評價 ? 在遺傳算法中，以個體適應(yīng)度的大小來確定該個體被遺傳到下一代群體中的概率。個體適應(yīng)度越大，該個體被遺傳到下一代的概率也越大；反之，個體的適應(yīng)度越小，該個體被遺傳到下一代的概率也越小。基本遺傳算法使用比例選擇算子來確定群體中各個個體遺傳到下一代群體中的數(shù)量。為正確計算不同情況下各個個體的遺傳概率，要求所有個體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑵ 基本遺傳算法的實現(xiàn) ②比例選擇算子 ? 比例選擇實際上是一種有退還隨機選擇 ,也叫做賭盤 (Roulette Wheel)選擇 ,因為這種選擇方式與賭博中的賭盤操作原理非常相似 。 ? 比例選擇算子的具體執(zhí)行過程是：先計算出群體中所有個體的適應(yīng)度之和；其次計算出每個個體的相對適應(yīng)度的大小，此值即為各個個體被遺傳到下一代群體中的概率；最后再使用模擬賭盤操作（即 0到 1之間的隨機數(shù)）來確定各個個體被選中的次數(shù)。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑵ 基本遺傳算法的實現(xiàn) ③單點交叉算子 ? 單點交叉算子是最常用和最基本的交叉操作算子。單點交叉算子的具體執(zhí)行過程如下：對群體中的個體進行兩兩隨機配對；對每一對相互配對的個體，隨機設(shè)置某一基因座之后的位置為交叉點；對每一對相互配對的個體，依設(shè)定的交叉概率 在其交叉點處相互交換兩個個體的部分染色體，從而產(chǎn)生出兩個新個體。 cp第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑵ 基本遺傳算法的實現(xiàn) ④ 基本位變異算子 ? 基本位變異算子的具體執(zhí)行過程為：對個體的每一個基因座，依變異概率 指定其為變異點；對每一個指定的變異點，對其基因值做取反運算或用其他等位基因值來代替，從而產(chǎn)生出一個新的個體。 mp第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑶ 遺傳算法的應(yīng)用步驟 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架 。 對于具體問題 ， 可按下述步驟來構(gòu)造： ? ①確定決策變量及其各種約束條件，即確定出個體的表現(xiàn)型 X和問題的解空間； ? ②建立優(yōu)化模型，即描述出目標(biāo)函數(shù)的類型及其數(shù)學(xué)描述形式或量化方法； 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑶ 遺傳算法的應(yīng)用步驟 ? ③ 確定表示可行解的染色體編碼方法 ， 即確定出個體的基因型 X及遺傳算法的搜索空間； ? ④ 確定解碼方法 ， 即確定出由個體基因型 X到個體表現(xiàn)型 X的對應(yīng)關(guān)系或轉(zhuǎn)換方法； ? ⑤確定個體適應(yīng)度的量化評價方法，即確定出由目標(biāo)函數(shù)值 到個體適應(yīng)度的轉(zhuǎn)換規(guī)則； )(Xf第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑶ 遺傳算法的應(yīng)用步驟 ? ⑥ 設(shè)計遺傳算子 ， 即確定出選擇運算 、 交叉運算 、 變異運算等遺傳算子的具體操作方法； ? ⑦確定遺傳算法的有關(guān)運行參數(shù)。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 應(yīng)用 ? 組合優(yōu)化 ? 生產(chǎn)調(diào)度問題 ? 自動控制 ? 機器人學(xué) ? 圖象處理 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 免疫遺傳算法 基于免疫的改進遺傳算法，是免疫原理與傳統(tǒng)遺傳算法的結(jié)合。 算法的核心在于免疫算子的構(gòu)造，而免疫算子又是通過接種疫苗和免疫選擇兩個步驟完成的。 在理論上，免疫算法是概率 1收斂的。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十三、免疫算法 免疫算法流程圖 初始抗體生成 抗原識別 抗體促進和抑制 滿足終止條件？ 群體更新 結(jié)束 親和力計算 記憶細(xì)胞分化 Y N 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十三、免疫算法 免疫算法七要素 ? 識別抗原 – 將目標(biāo)函數(shù)和約束作為抗原 ? 生成初始化的抗體 – 隨機生成 N個抗體 ? 計算親和度 – 抗體和抗原的親和度 – 抗體和抗體的親和度 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十三、免疫算法 免疫算法七要素 ? 記憶細(xì)胞分化 – 與抗原有最大親和度的抗體加入記憶細(xì)胞 ? 抗體促進和抑制 – 促進高親和度的個體 ,消除低期望值的抗體 ? 產(chǎn)生新的抗體 – 選擇兩個抗體做變異和交叉 ,得到新的抗體 ? 結(jié)束條件 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十三、免疫算法 常用免疫算法 ? 負(fù)選擇算法 – 依靠 T細(xì)胞表面的受體，識別非自體，并消滅非自體（注：受體與所有的自體均不匹配） ? 克隆選擇算法 – 只關(guān)注抗原和抗體的親和度對 B細(xì)胞的復(fù)制的影響，而不考慮抗體之間的親和度 免疫系統(tǒng) 免疫算法 抗原 要解決的問題 抗體 最佳解向量 抗原識別 問題識別 從記憶細(xì)胞產(chǎn)生抗體 聯(lián)想過去的成功 淋巴細(xì)胞分化 優(yōu)良解 (記憶 )的保持 細(xì)胞抑制 剩余候選解的消除 抗體增加 (細(xì)胞克隆 ) 利用遺傳算子產(chǎn)生新抗體 免疫系統(tǒng)與一般免疫算法之間的比較 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十四、模擬退火算法 (Simulated Annealing) 基本思想 (1)是基于 Monte Carlo迭代求解策略的一種隨機尋優(yōu)算法，源于物理退火原理；類似物理退火讓固體粒子收斂到一個能量最低狀態(tài)的過程，實現(xiàn)算法最終收斂到最優(yōu)解的目的。 (2)結(jié)合爬山法和隨機行走 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十四、模擬退火算法 (Simulated Annealing) 基本思想 (3) 結(jié)合概率突跳特性在解空間中隨機尋找目標(biāo)函數(shù)的全局最優(yōu)解。 (4)首先生成一個隨機解 ,然后對其進行擾動 (在同一溫度下進行多次擾動 ),對擾動后得到的解進行評估與替換 ,溫度逐漸下將形成多代。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十四、模擬退火算法 (