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

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