并行遺傳算法

1、,數(shù)據(jù)挖掘原理與SPSS Clementine應(yīng)用寶典 元昌安 主編　 鄧　松　李文敬　劉海濤　編著 電子工業(yè)出版社,第十三章 遺傳算法,本章內(nèi)容,1. 遺傳算法概述,2. 基本遺傳算法,3. 改進(jìn)遺傳算法,4. 基于遺傳算法的數(shù)據(jù)挖掘,5. 基因表達(dá)式編程,遺傳算法概述-模式定理,模式定理是遺傳算法的理論基礎(chǔ)，它的定義如下：模式定理(Sc

2、hema theorem)：在遺傳算子選擇，交叉和變異的作用下，具有低階，短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中將得以指數(shù)級增長。,遺傳算法概述-積木塊假設(shè),具有低階，短定義距及高適應(yīng)度的模式稱作積木塊(Building block)。積木塊假設(shè)(building block hypothesis)是指低階，短距，高平均適應(yīng)度的模式(積木塊)在遺傳算子作用下，相互結(jié)合，能生成高階，長距，高平均適應(yīng)度模式，可最終生成全

3、局最優(yōu)解。,遺傳算法概述-隱并行性,具有高階，長定義距的模式在交叉算子和變異算子作用下遭到破壞，盡管遺傳算法實際上只對幾個串個體進(jìn)行運算，但遺傳算法仍然隱含處理了大量的模式，命名這一性質(zhì)為隱并行性。,,遺傳算法概述-基本操作,遺傳操作包含三個基本遺傳算子(Genetic operator)：選擇(Selection)從群體中選擇優(yōu)勝個體，淘汰劣質(zhì)個體的操作叫選擇。選擇算子有時又稱為再生算子(Reproduction opera

4、tor)。交叉(Crossover)所謂交叉又是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。變異(Mutation) 變異算子的基本內(nèi)容是對群體中個體串的某些基因座上的基因值作變動。,編碼方式是個體表示問題，即對于給定的問題，選擇或設(shè)計一個適當(dāng)?shù)幕虮硎臼?，?3-1比較了目前已有的遺傳算法(GA)的編碼策略的具體分析。,基本遺傳算法-流程,基本遺傳算法(SGA)只使用選擇操作、交叉操作以及變異操作三種基本

5、遺傳操作，SGA的遺傳操作過程簡單，容易理解，且是其它復(fù)雜遺傳算法的基礎(chǔ)，它在給各種遺傳算法提供基本框架的同時，也具有一定的應(yīng)用價值。,,改進(jìn)遺傳算法,,改進(jìn)遺傳算法主要研究內(nèi)容包括：分層遺傳算法；自適應(yīng)遺傳算法；小生境遺傳算法；并行遺傳算法；混合遺傳算法。,分層遺傳算法-基本思想,,分層遺傳算法-關(guān)鍵問題,,各個子種群的確定 各個子種群確定方式同SGA方式相同。遺傳操作設(shè)計 初步遺傳操作得到的結(jié)果就

6、是遺傳異算法初始層，而每一個都是可以是被下一層遺傳操作處理對象。,分層遺傳算法-流程,,,自適應(yīng)遺傳算法,,,小生境遺傳算法,,,小生境技術(shù)就是將每一代個體劃分為若干類，每個類中選出若干適應(yīng)度較大的個體作為一個類的優(yōu)秀代表組成一個種群，再在種群中以及不同種群之間通過雜交、變異產(chǎn)生新一代個體群，同時采用預(yù)選擇(preselection)機制或排擠(crowding)機制或分享(Sharing)機制完成選擇操作。,并行遺傳算法

7、-實現(xiàn)方案,,,全局型-主從式模型(master-slave model)獨立型-粗粒度模型(coarse-grained model)分散型-細(xì)粒度模型(fine-grained model),并行遺傳算法-遷移策略,,,一傳多 每個處理器對應(yīng)有若干個相鄰處理器，每個處理器產(chǎn)生新一代個體后，都將自己最好的一個個體傳送給其所有相鄰處理器，并且接受來自相鄰處理器的最好的個體，將這些個體與自己的個體同時考慮，淘汰適應(yīng)度差的個體。一

8、傳一 考慮到染色體的多樣性，每個處理器都將自己最好的個體僅傳給與之相鄰的一個處理器，同時增加兩個參數(shù):(1)處理器之間通訊的頻率;(2)每次傳送給最好個體的數(shù)目。,混合遺傳算法-基本框架,,,混合遺傳算法(Hybrid Genetic Algorithm)，是提高遺傳算法運行效率和求解質(zhì)量的一個有效手段，可在保持算法一定通用性的基礎(chǔ)上提高算法的效率，基本框架如下所示：,,基于遺傳算法的數(shù)據(jù)挖掘,,,基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘

9、 基于遺傳算法的聚類算法 基于遺傳算法的分類算法 基于模糊遺傳算法的建模,,基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘,,,基于遺傳算法的關(guān)聯(lián)規(guī)則挖掘的過程如下：,,基于遺傳算法的聚類算法,,,基于遺傳算法的聚類算法描述如下：,,基于模糊遺傳算法的建模,,,基于模糊的遺傳算法描述如下：,,基于遺傳算法的分類算法,,,基于遺傳算法的分類算法描述如下：,,基因表達(dá)式編程-算法描述,,,基因表達(dá)式編程的基本算法描述如下：,,基因表達(dá)式編程-遺傳操

10、作,,,基因表達(dá)式編程的主要遺傳操作有：選擇操作(Selection變異操作(Mutation)插串操作(Transposition) GEP中插串操作分為三種：（1）IS插串（Insertion Sequence Transposition,）；（2）RIS插串（root Insertion Sequence Transposition）；（3）基因插串（Gene Transposition）。重組操作(Recombin