并行遺傳算法

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ù)級(jí)增長(zhǎng)。,遺傳算法概述-積木塊假設(shè),具有低階，短定義距及高適應(yīng)度的模式稱(chēng)作積木塊(Building block)。積木塊假設(shè)(building block hypothesis)是指低階，短距，高平均適應(yīng)度的模式(積木塊)在遺傳算子作用下，相互結(jié)合，能生成高階，長(zhǎng)距，高平均適應(yīng)度模式，可最終生成全

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

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

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

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

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

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

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

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