遺傳算法并行化的研究doc

1、遺傳算法并行化的研究學號：SC02011036 姓名：黃鑫摘要 本文是針對遺傳算法并行化進行了研究，首先簡要給出了基本遺傳算法的形式化描述，然后做了并行性的分析，詳細介紹了遺傳算法的結(jié)構(gòu)化并行模型：步進模型，島嶼模型，鄰接模型，最后指出了進一步要研究的課題。關(guān)鍵詞 ：遺傳算法，并行計算，結(jié)構(gòu)化GA1 引言遺傳算法（GA）是根據(jù)達爾文進化論“優(yōu)勝劣汰，適者生存”的一種啟發(fā)式搜索算法。采用選擇，交叉，變異等基本變化算子在解空間同時進行多點搜索，本身固有并行性。隨著大規(guī)模并行機的迅速發(fā)展，將并行機的高速性與遺傳算法并行性結(jié)合起來，從而促進遺傳算法的發(fā)展。然而，僅僅將基本遺傳算法硬件并行化伴隨著大量通

2、訊開銷等問題，從而必須對標準GA的進行改進，使得并行遺傳算法不單單是遺傳算法硬件并行實現(xiàn)，更重要的是結(jié)構(gòu)化的遺傳算法。本文首先給出了GA形式化描述，對基本GA的可并行性做出分析，然后給出了并行GA的模型，最后指出了并行遺傳算法還需要解決的問題。2 基本遺傳算法在這里我們不對遺傳算法做過多的介紹，只是給出基本遺傳算法的形式化描述：begin(1) initialization(1.1) 產(chǎn)生一個初始群體(1.2) 評估第一代整個群體的適應(yīng)度值（2）while running do(2.1) 選擇父代(2.2) 交叉操作(2.3) 子代變異(2.4) 評估子代的適應(yīng)度(2.5) 子代取代父代，形成

3、新的一帶個體endwhileend3 遺傳算法的并行性分析從第一節(jié)對遺傳算法的描述，我們可以看出基本遺傳算法模型是一個反復(fù)迭代的進化計算過程，通過對一組表示候選解的個體進行評價、選擇、交叉、變異等操作，來產(chǎn)生新一代的個體(候選解)，這個迭代過程直到滿足某種結(jié)束條件為止。對應(yīng)于基本遺傳算法的運行過程，為實現(xiàn)其并行化要求，可以從下面四種并行性方面著手對其進行改進和發(fā)展。并行性：個體適應(yīng)度評價的并行性。個體適應(yīng)度的評價在遺傳算法中占用的運行時間比較大。通過對適應(yīng)度并行計算方法的研究，可提高個體適應(yīng)度評價的計算效率。并行性：整個群體各個個體適應(yīng)度評價的并行性。群體中各個個體適應(yīng)度的評價過程無相互依賴關(guān)

4、系，這樣各個個體適應(yīng)度的評價或計算過程就可以相互獨立、相互并行地在不同的處理機上同時進行。并行性：子代群體產(chǎn)生過程的并行性。從父代群體中產(chǎn)生下一代群體所需進行的選擇、交叉、變異等遺傳操作可以獨立并行地進行。并行性：基于群體分組的并行性。群體中的單個或一組個體的進化過程可以相互獨立地進行，在適當?shù)臅r候，它們再以適當?shù)姆绞浇粨Q信息。即不同個體或不同組個體的進化過程是同時進行的。在上述四種并行方式中，前三種方式并未從總體上改變簡單遺傳算法的特點，第四種并行方式卻對簡單遺傳算法的結(jié)構(gòu)有較大的改變，并且這種方式也最自然，在并行機或局域網(wǎng)環(huán)境下實現(xiàn)起來也最簡單，所以受到了人們較大的重視。目前已開發(fā)出的并行

5、遺傳算法基本上都是基于上述四種并行機制或其組合來實現(xiàn)的。4 遺傳算法的并行化為提高遺傳算法的運算速度、改善其性能，人們在并行機或局域網(wǎng)環(huán)境下開發(fā)出了一些并行遺傳算法。概括起來，這些方法大體可分為如下兩類：1標準并行方法；2分解型并行方法。41標準并行方法(standard parallel approach)這類方法并不改變簡單遺傳算法的基本結(jié)構(gòu)特點，即群體中的全部都在統(tǒng)一的環(huán)境中進化。其基本出發(fā)點是從局部的角度開發(fā)個體進化的并行性。在應(yīng)用遺傳算法進行優(yōu)化計算時，各個個體的適應(yīng)度計算、選擇、變異等操作是可以相互獨立進行的。這樣，利用共享存貯器結(jié)構(gòu)的并行機，就可對群體的進化過程進行并行計算以達到

6、提高遺傳算法運行速度的目的。這類方法在適應(yīng)度計算量較大的場合是比較有效的，上一節(jié)所介紹的前三種并行性都可以通過這類方法來實現(xiàn)。但另一方面，由于并行機之間通信等的限制，選擇、交叉、變異等遺傳操作的對象集中在一個處理機上較為方便，所以這類方法的應(yīng)用受到一些限制，在有些場合應(yīng)用效果不太明顯。42分解型并行方法(decomposition parallel approach)這種方法是將整個群體劃分為幾個子群體，各個子群體分配在各自的處理機或局域網(wǎng)工作站上獨立地進行簡單遺傳算法的進化操作，在適當?shù)臅r候各個子群體之間相互交換一些信息。其基本出發(fā)點是從全局的角度開發(fā)群體進化的并行性。這種方法改變了簡單遺傳

7、算法的基本特點，各子群體獨立地進行進化，而不是全部群體采用同一機制進化。它是實現(xiàn)上述第4種并行性的方法，并且是一個簡單常用、易于實現(xiàn)的方法。這種方法不僅能夠提高遺傳算法的運算速度，而且由于保持了各處理機上子群體進化的局部特性，還能夠有效地回避遺傳算法的早熟現(xiàn)象。構(gòu)造這種并行遺傳算法時，需要考慮下述幾個主要問題:.子群體劃分方式1.整個群體均勻地分配到各個處理機的方式(是粗粒度分配，還是細粒度分配?)。.交換信息方式參加信息交換的對象(哪幾個處理機之間可以交換信息?)；交換信息的內(nèi)容(是隨機交換，還是擇優(yōu)交換?)；交換時間或頻率(何時交換?)；交換信息量(交換幾個個體?)。據(jù)對這幾個問題的不同處

8、理，構(gòu)成了不同類型的群體交換模型，亦即形成了不同的并行遺傳算法。步進模型(stepping-stonemodel)這個模型的各個子群體中所含個體的數(shù)量多于1，各個子群體在其處理機上并行獨立地運行簡單遺傳算法，子群體之間的信息交換只能是在地理上的鄰接處理機之間進行。該模型由于對處理機之間的通信要求不高，所以實現(xiàn)起來比較簡單。圖1為步進模型的示例。圖1步進模型島嶼模型(island model)這個模型也叫做粗粒度并行遺傳算法(coarse-grainedPGA)。該模型每個處理機上子群體所含個體的數(shù)量多于1，各個子群體在其各自的處理機上并行獨立地運行簡單遺傳算法，并且隨機的時間間隔、在隨機選擇的

9、處理機之間交換個體信息。這種模型適用于MIMD機器，如基于Transputer的多處理機系統(tǒng)。圖2島嶼模型現(xiàn)在我們給出島嶼模型的形式化語言描述begin(1) 產(chǎn)生一個初始群體并將它劃分成p個子群體(2) for i=1 to par-do (2.1)初始化 （2.2）評估第一代子群體的適應(yīng)度 （2.3）while running do (a) select parents(b) reproduce(c) mutate offspring(d) replace parents(e) evaluate sub-population(a) send emigrants(b) receive imm

10、igrantsendwhieendfor end鄰接模型(neighborhood model)這個模型也叫做細粒度并行遺傳算法(fine-grainedPGA)。該模型中每個處理機上只分配一個個體，即子群體只由一個個體組成，每個子群體只和與其海明距離為1的“鄰接”子群體相互交換信息。由該模型的特點可知，即使群體中某一個體的適合度較高，其作用也僅僅是逐步地才能到其鄰近的個體，所以它能夠有效地維持群體的多樣性，有效地抑制早熟現(xiàn)象。這種模型適用于SIMD系統(tǒng)，如陣列式多處理器系統(tǒng)或連接機。鄰接單元圖3 鄰接模型5 展望 盡管并行GA的研究已經(jīng)取得了很大進步，在一些實際的應(yīng)用問題上達到了良好的效果。然而，還有大量的前沿方向需要我們進一步去研究。例如，如何處理動態(tài)函數(shù)優(yōu)化問題，并行GA的理論研究，并行GA的主要參數(shù)對結(jié)果的影響，并行GA的收斂性如何，并行GA與其他優(yōu)化算法的比較，所有這些都要我們今后去解決?？偟膩碚f，并行GA有著良好的發(fā)展和應(yīng)用前景。參考文獻1陳國良，王熙法，莊鎮(zhèn)泉