機(jī)器學(xué)習(xí)：遺傳算法(編輯修改稿)
2024-08-28 15:04 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ：陶曉鵬 15 Gabil系統(tǒng) ? Dejong et Gabil系統(tǒng)：遺傳算法在概念學(xué)習(xí)方面的應(yīng)用 ? 學(xué)習(xí)以命題規(guī)則的析取集合表示的布爾概念 ? 在對(duì)幾個(gè)概念學(xué)習(xí)問(wèn)題的實(shí)驗(yàn)中發(fā)現(xiàn)，在泛化精度方面 Gabil與其他學(xué)習(xí)算法大體相當(dāng) ? Gabil使用的算法就是表 91描述的典型算法 機(jī)器學(xué)習(xí) 遺傳算法 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 16 Gabil系統(tǒng)（ 2） ? Gabil的具體實(shí)現(xiàn) – 表示：每個(gè)假設(shè)對(duì)應(yīng)一個(gè)命題規(guī)則的析取集，按照 – 遺傳算子： ? 變異：使用表 92中的標(biāo)準(zhǔn)變異算子 ? 交叉：表 92中的兩點(diǎn)交叉算子的一個(gè)擴(kuò)展，這種方法保證了產(chǎn)生的位串表示的規(guī)則集是良定義的 – 適應(yīng)度函數(shù)：每個(gè)規(guī)則集的適應(yīng)度是根據(jù)它在訓(xùn)練數(shù)據(jù)上的分類(lèi)精度計(jì)算的， Fitness(h)=(correct(h))2 機(jī)器學(xué)習(xí) 遺傳算法 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 17 Gabil系統(tǒng)的擴(kuò)展 ? 增加兩個(gè)新算子 – AddAlternative，它泛化對(duì)某個(gè)特定屬性的約束，方法是把這個(gè)屬性對(duì)應(yīng)的子串中的一個(gè) 0改為 1，使用概率為 – DropCondition，把一個(gè)特定屬性的所有位都替換為1，使用概率為 ? 兩種使用新算子的方法 – 對(duì)每一代群體中的每個(gè)假設(shè)以同樣的概率應(yīng)用 – 對(duì)假設(shè)的位串進(jìn)行擴(kuò)展，使其包含另外兩位以決定是否可以對(duì)該假設(shè)應(yīng)用這兩個(gè)新算子 機(jī)器學(xué)習(xí) 遺傳算法 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 18 假設(shè)空間搜索 ? 遺傳算法采用一種隨機(jī)化的柱狀搜索來(lái)尋找最大適應(yīng)度的假設(shè)，與前面章節(jié)的搜索算法有很大不同 – 梯度下降搜索從一個(gè)假設(shè)平滑移動(dòng)到另一個(gè)非常相似的假設(shè) – 遺傳算法的移動(dòng)可能非常突然，使用和雙親根本不同的后代替換雙親假設(shè) – 遺傳算法的搜索不太可能像梯度下降方法那樣陷入局部最小值的問(wèn)題 ? 遺傳算法應(yīng)用中的一個(gè)難題：擁擠問(wèn)題 – 擁擠：群體中某個(gè)體適應(yīng)度大大高于其他個(gè)體，因此它迅速繁殖，以至于此個(gè)體和與它相似的個(gè)體占據(jù)了群體的絕大部分 – 擁擠降低了群體的多樣性，從而減慢了進(jìn)化的進(jìn)程 機(jī)器學(xué)習(xí) 遺傳算法 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 19 假設(shè)空間搜索（ 2） ? 降低擁擠的策略 – 使用錦標(biāo)賽選擇或排序選擇，而不用適應(yīng)度比例輪盤(pán)賭選擇 – 適應(yīng)度共享，根據(jù)群體中與某個(gè)體相似的個(gè)體數(shù)量，減小該個(gè)體的適應(yīng)度 – 對(duì)可重組生成后代的個(gè)體種類(lèi)進(jìn)行限制，比如受到生物進(jìn)化的啟示 ? 通過(guò)只允許最相似的個(gè)體重組，可以在群體中促成相似的個(gè)體聚類(lèi)，形成亞種 ? 按空間分布個(gè)體，只允許相鄰的個(gè)體重組 機(jī)器學(xué)習(xí) 遺傳算法 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 20 群體進(jìn)化和模式理論 ? 模式理論（ Holland1975）提供了一種用數(shù)學(xué)方法刻畫(huà)遺傳算法中群體進(jìn)化的過(guò)程 ? 模式是由若干 0、 1和 *組成的任意串， *表示任意符號(hào) ? 模式理論根據(jù)每個(gè)模式的實(shí)例數(shù)量來(lái)刻畫(huà)遺傳算法中群體的進(jìn)化 – 令 m(s,t)表示群體中的模式 s在時(shí)間 t的實(shí)例數(shù)量 – 模式理論根據(jù) m(s,t)和模式、群體及其他屬性來(lái)描述m(s,t+1)的期望值 機(jī)器學(xué)習(xí) 遺傳算法 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 21 群體進(jìn)化和模式理論（ 2） ? 遺傳算法中群體的進(jìn)化依賴(lài)于幾個(gè)步驟，即選擇、重組和變異。 –符號(hào)表示： ? f(h)表示位串個(gè)體 h的適應(yīng)度 ? n為群體中個(gè)體的總數(shù)量 ? 表示在時(shí)間 t群體中所有個(gè)體的平均適應(yīng)度 ? 表示在時(shí)間 t群體中模式 s的實(shí)例的平均適應(yīng)度 ? 表示個(gè)體 h既是模式 s的一個(gè)代表，又是時(shí)間 t群體的一個(gè)成員 )(tf),(? tsutpsh ?? 機(jī)器學(xué)習(xí) 遺傳算法 作者： Mitchell 譯者：曾華軍等 講者：陶曉鵬 22 群體進(jìn)化和模式理論（ 3） – E(m(s,t+1))的推導(dǎo)，僅考慮選擇的情況 – 式子 ，在 t+1代中，模式 s的實(shí)例期望數(shù)量與這個(gè)模式的實(shí)例在時(shí)間 t內(nèi)的平均適應(yīng)度成正比，與群體的所有成員的平均適應(yīng)度成
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1