基于遺傳算法的特征選擇.ppt

基于遺傳算法的特征選擇 WhatWhyHow 回答什么是遺傳算法 什么是特征選擇 遺傳算法是模擬進化論 搜索優(yōu)化問題最優(yōu)解的一種算法 它采用群體搜索策略 一代一代逐步進化 直到收斂到問題的最優(yōu)解 群體是個體的集合 個體模擬一個問題的一個解 關(guān)鍵問題 個體如何表示 方法 問題編碼如何產(chǎn)生下一代 方法 遺傳操作如何評價種群的質(zhì)量 方法 適應度函數(shù) What 什么是特征選擇 就是從一個特征集合中選擇一個最優(yōu)子集 遺傳算法流程圖 How 1 問題編碼對于特征選擇問題 問題編碼很簡單 采用0 1編碼即可 任何一個n元0 1串 都表示問題的一個解 2 如何產(chǎn)生下一代通過選擇 交叉 變異三種遺傳操作產(chǎn)生下一代 前兩種操作每一次都要用的 而第三種則不一定 但沒有規(guī)則 選擇是用來選擇交叉的父本 交叉 模擬有性繁殖 產(chǎn)生新的個體 變異是某一位的變異 3 如何評價種群的質(zhì)量適應度函數(shù)設(shè)計 對于特征選擇問題可采用如下的類別可分離性準則 設(shè)計適應度函數(shù) 適應度函數(shù)為 需要注意的是這種適應度函數(shù) 只適用于連續(xù)值數(shù)據(jù)庫的情況 下面如何計算 Iris數(shù)據(jù)庫 選擇的特征子集應使類內(nèi)散度盡可能小 而使類間散度盡可能大 設(shè)xk i 和xl j 分別為 i類和 j類中的D維特征向量 xk i xk j 為這兩個向量間的距離 則類間平均距離為 其中 Pi和Pj為先驗概率 通常采用歐氏距離 JD稱為各類之間的平均平方距離 定義類均值向量為和總均值向量分別為 和 定義類間散度矩陣Sb的估計為 定義類內(nèi)散度矩陣Sw的估計為 其中 i為類協(xié)方差矩陣 其他需要說明的問題還有 Q1初始種群的產(chǎn)生主要涉及到 1 群體的規(guī)模N 2 初始化種群 種群的規(guī)模N越大 種群的多樣性越好 GA陷入局部極小的可能性越小 但N太大 計算量會很大 收斂速度也會降低 N太小 GA搜索的空間被限制在一個較小的范圍內(nèi) 可能導致早熟 應根據(jù)問題的維數(shù)和難度來設(shè)定N 一般地 維數(shù)和難度越高 N應越大 建議N一般取為幾十到幾百之間 初始化種群一般用隨機化方法產(chǎn)生 a 選擇 Selection 算子依據(jù)每個染色體的適應值大小 適應值越大 被選中的概率就越大 其子孫在下一代產(chǎn)生的個數(shù)就越多 選擇操作是建立在群體中個體的適應值評估基礎(chǔ)上的 目前常用的選擇算子有賭輪選擇方法 保留最佳個體選擇法 期望值選擇方法等 a 1 賭輪方法 準備步 S1 按如下公式計算種群中每個個體xi被選擇的概率 E3 選擇步 根據(jù)選擇概率 將圓盤形的賭輪分成N個扇形 第i個扇形的中心角為2 pi 在進行選擇時 可以假想隨機轉(zhuǎn)到一下賭輪 若參照點落入第r個扇形內(nèi) 則選擇xr 這樣重復選擇N次即可 上述方法可用如下計算機方法模擬 將 0 1 區(qū)間分成長度為p1 p2 pN的小區(qū)間 按均勻分布在 0 1 中產(chǎn)生一個隨機數(shù) 這個數(shù)屬于哪個小區(qū)間 就選出對應的個體 如此重復N次即可 具體步驟如下 賭輪方法選擇步驟STEP1 按公式 E4 計算累加概率 STEP2 重復以下兩步N次STEP2 1 產(chǎn)生 0 1 中的一個隨機數(shù)r STEP2 2 若r q1 則選擇x1 否則 若qi 1 r qi 則選擇xi a 2 保留最佳個體選擇方法將到目前為止 得到的M個最佳個體直接保留到下一代種群中 其余N M個個體可按其他方法選擇產(chǎn)生 a 3 期望值選擇方法在賭輪選擇方法中 當種群規(guī)模不大時 產(chǎn)生的隨機數(shù)可能并不能代表其隨機變量的真正分布情況 這樣 在選擇時 可能適應度值大的個體被淘汰 而適應度值小的個體反而被選上 為了克服這種缺點 提出了期望值方法 期望值方法選擇步驟STEP1 按下式計算每個個體在下一代生存的期望個數(shù) E5 STEP2 若某個個體被選擇 則Mi Mi 0 5 否則 Mi Mi 1 STEP3 將第i個個體復制 Mi 份 小數(shù)部分作為選擇的概率 再參加選擇 看第i個個體是否能再次被選中 STEP4 一旦一個個體的生存期望個數(shù)降低到小于等于0 則該個體不再參加選擇 被淘汰 b 交叉 Crossover 算子以概率pc選擇參與交叉的個體 并將選出的個體兩兩配對 每一對用單點交叉或兩點交叉產(chǎn)生兩個后代 如有兩個用二進制編碼的個體A和B 交叉前后為 A a1a2a3 a4a5A a1a2a3 b4b5B b1b2b3 b4b5B b1b2b3 a4a5 父代 子代 c 變異 Mutation 算子變異增加了遺傳算法找到接近最優(yōu)解的能力 變異就是以很小的概率pm 隨機地改變字符串某個位置上的值 把某一位的內(nèi)容進行變異 在二進制編碼中 就是將某位0變成1 1變成0 如 110010的第四位變異