[計(jì)算機(jī)]ch9現(xiàn)代數(shù)據(jù)挖掘技術(shù)--遺傳算法(已修改)
2024-10-31 03:41 本頁(yè)面
【正文】 遺傳算法 （ Geic Algorithm， 簡(jiǎn)稱 GA） 是一種概率搜索算法 ， 它通過(guò)模擬自然界生物進(jìn)化機(jī)制 ， 根據(jù)優(yōu)勝劣汰的生物進(jìn)化原則 ， 能夠在較大的參數(shù)空間中較快地搜索到問(wèn)題的最優(yōu)解 。 它尤其適用于處理傳統(tǒng)搜索方法中難以解決的復(fù)雜和非線性問(wèn)題 。 不僅避免了局部?jī)?yōu)化算法的缺陷 ， 而且可以利用固有知識(shí)縮小搜索空間 ， 避免其它全局優(yōu)化算法產(chǎn)生搜索的組合爆炸 。 遺傳算法以其簡(jiǎn)單通用 、 魯棒性強(qiáng) 、 適用于并行處理等特點(diǎn) ， 廣泛應(yīng)用于組合優(yōu)化 、 機(jī)器學(xué)習(xí) 、 規(guī)劃設(shè)計(jì) 、 人工生命等領(lǐng)域 。 遺傳算法 ? 達(dá)爾文的 “ 適者生存 ” 理論 、 繼承的信息由基因攜帶 、 多個(gè)基因組成了染色體 、 基因座 、 等位基因 、 基因型和表現(xiàn)型 ? 染色體對(duì)應(yīng)的是一系列符號(hào)序列 ， 通常用 0、 1的位串表示 ? 進(jìn)行生物的遺傳進(jìn)化 。 在這一過(guò)程中包括三種演化操作：在父代基因群中的雙親選擇操作 、 兩個(gè)父代雙親產(chǎn)生子代基因的交叉操作和在子代基因群體中的變異操作 。 ? 兩種數(shù)據(jù)轉(zhuǎn)換：從表現(xiàn)型到基因型的轉(zhuǎn)換 ， 另一種是從基因型到表現(xiàn)型的轉(zhuǎn)換 ? 遺傳算法實(shí)質(zhì)上是一種繁衍 、 檢測(cè)和評(píng)價(jià)的迭代算法 ? 最大優(yōu)點(diǎn)是問(wèn)題的最優(yōu)解與初始條件無(wú)關(guān) ， 而且搜索最優(yōu)解的能力極強(qiáng) 遺傳算法可定義為一個(gè) 8元組： GA = (C, E, P0, M, ?, ?, ?, T) 式中 ， C— 個(gè)體的編碼方法； E— 個(gè)體適應(yīng)值評(píng)價(jià)函數(shù)； P0— 初始種群； M— 群體大??； ?— 選擇算子； ?— 交叉算子； ?— 變異算子； T— 遺傳算法終止條件 。 初始化種群 編碼為染色體 種群 計(jì)算各染色體的適應(yīng)值 遺傳操作 (選擇、交叉、變異 ) 種群 停機(jī)條件滿足？ 種群 ← 種群 N Y 結(jié) 束 圖 遺傳算法的工作原理示意圖 )1( ?tP)(tP遺傳算法的關(guān)鍵技術(shù)包括： ? 編碼問(wèn)題； ? 初始種群的產(chǎn)生； ? 確定適應(yīng)值函數(shù)； ? 選擇遺傳操作算子； ? 停機(jī)條件。 ? 編碼問(wèn)題 ? 編碼是應(yīng)用遺傳算法時(shí)要解決的首要問(wèn)題，也是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵步驟。由于遺傳算法不能直接處理解空間的解數(shù)據(jù)，因此必須通過(guò)編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。編碼方法在很大程度上決定了如何進(jìn)行群體的遺傳進(jìn)化運(yùn)算以及遺傳進(jìn)化的效率。由于不同的編碼方法具有不同的特點(diǎn)，為了提高遺傳算法的效率，應(yīng)根據(jù)不同的情況采用不同的編碼方式。主要的編碼方法有二進(jìn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1