并行遺傳算法

1、并行遺傳算法PGAs1介紹遺傳算法是一類基于自然選擇和遺傳學(xué)原理的有效搜索方法，許多領(lǐng)域成功地應(yīng)用遺傳算法得到了問題的滿意解。雖然SGA 通常能在合理的時(shí)間內(nèi)找到滿意解，但隨著求解問題的復(fù)雜性及難度的增加，提高遺傳算法的運(yùn)行速度便 顯得尤為突出。2并行群體模型對(duì)SGA的修改要把串行SGA 的單一群體分成多個(gè)子群體并分而治之要控制、管理子群體之間的信息交換3PGA的四種基本模型主從式模型細(xì)粒度模型粗粒度模型混合模型4主從式模型主從式模型是遺傳算法的直接并行化方案, 不改變遺傳算法的基本結(jié)構(gòu)特點(diǎn), 它只有一個(gè)群體, 選擇、交叉和變異等全局操作由主節(jié)點(diǎn)機(jī)(或主處理器) 串行進(jìn)行, 而適應(yīng)度的評(píng)價(jià)和計(jì)

2、算由各從節(jié)點(diǎn)機(jī)(或從處理器) 并行執(zhí)行。5主從式模型優(yōu)缺點(diǎn)此模型易于實(shí)現(xiàn), 是一個(gè)非常有效的并行化方法。可以直接應(yīng)用SGA 的理論結(jié)果。經(jīng)常會(huì)出現(xiàn)主、從節(jié)點(diǎn)機(jī)負(fù)荷忙閑不均勻的情況。存在通信瓶頸和通信延遲問題。6細(xì)粒度模型細(xì)粒度模型又稱作鄰域模型, 在整個(gè)進(jìn)化過程中雖然保持一個(gè)群體, 但要求子群體的劃分要非常細(xì)小, 最理想狀態(tài)是每個(gè)節(jié)點(diǎn)機(jī)(或處理器) 只有一個(gè)個(gè)體, 要求各節(jié)點(diǎn)機(jī)具有極強(qiáng)的通信能力, 對(duì)于每個(gè)染色體, 選擇和交叉操作都只在所處的節(jié)點(diǎn)機(jī)及其鄰域中進(jìn)行。 由于整個(gè)進(jìn)行過程中, 不需要或者需要很少的全局操作, 因此充分發(fā)揮了并行特性。7細(xì)粒度模型通常情況下, 對(duì)于較小的群體中, 應(yīng)采用

3、大范圍的拓?fù)? 而對(duì)于較大的群體中, 多采用具有4 個(gè)或8 個(gè)通信鄰域的方格超環(huán)面網(wǎng)格。具體采用哪種鄰域拓?fù)漭^好目前尚無定論, Shapiro B 等通過對(duì)8 個(gè)最優(yōu)近鄰域, 4 個(gè)最近鄰域在距離r 內(nèi)的全部鄰域進(jìn)行實(shí)驗(yàn), 發(fā)現(xiàn)當(dāng)r 2時(shí), 結(jié)果最差, 4 個(gè)鄰域模式優(yōu)于8 個(gè)鄰域模式。采用什么樣的鄰域結(jié)構(gòu)是需要解決的主要問題之一！8粗粒度模型粗粒度模型又被稱作分布式模型或孤島模型,是適應(yīng)性最強(qiáng)和應(yīng)用最廣的遺傳算法的并行模型。它將群體依照節(jié)點(diǎn)機(jī)(或處理器) 的個(gè)數(shù)分成若干個(gè)子群體, 各個(gè)子群體在各自的節(jié)點(diǎn)機(jī)(或處理器) 上并發(fā)獨(dú)自運(yùn)行遺傳算法, 每經(jīng)過一定的進(jìn)化代, 各個(gè)子群體間將交換若干個(gè)個(gè)

4、體。9粗粒度模型何時(shí)交換個(gè)體, 交換哪些個(gè)體, 采用什么方式交換是關(guān)鍵問題。如何確定遷移規(guī)模、遷移策略和遷移拓?fù)涞葐栴}。10粗粒度模型遷移規(guī)模遷移規(guī)模由兩個(gè)重要參數(shù)來控制: 遷移周期和遷移率。遷移規(guī)模由兩個(gè)重要參數(shù)來控制: 遷移周期和遷移率。遷移周期決定了各子群體間的遷移間隔, 在通常情況下, 遷移間隔是固定的, 每隔幾代遷移一次, 并且遷移率越高, 遷移周期越長。遷移率過大會(huì)破壞子群體的多樣性, 致使多個(gè)搜索進(jìn)程集中到相同的區(qū)域。遷移率過小, 將使子群體不能充分利用其它子群體的信息。典型的遷移率是子群體10% 到20% 之間。11粗粒度模型遷移策略遷移基本上可以采用與匹配選擇和生存選擇相同的

5、策略, 雖然區(qū)域選擇更偏向區(qū)域內(nèi)部較好的個(gè)體, 但在實(shí)際的遷移選擇和替換中, 也可以采用其它標(biāo)準(zhǔn)。12粗粒度模型遷移拓?fù)溥w移拓?fù)浯_定了子群體之間個(gè)體的遷移路徑,目前遷移拓?fù)浯蠖喽疾捎昧祟愃平o定并行機(jī)的互聯(lián)拓?fù)? 如完全隔離、單向環(huán)、雙向環(huán)、超立方體和網(wǎng)格等。遷移拓?fù)涫怯绊慞GA 性能的重要方面, 也是遷移成本的主要因素。13混合模型混合模型是近些年快速發(fā)展起來的模型結(jié)構(gòu),主要是通過把前面三種基本模型混合形成層次結(jié)構(gòu)。目前混合模型組合關(guān)系主要有三種: 粗粒度-細(xì)粒度、粗粒度-粗粒度和粗粒度-主從式。14模型比較主從式模型, 由于僅適用計(jì)算時(shí)間主要集中在適應(yīng)度評(píng)估的問題, 因此適用的范圍受到了極大的限制。細(xì)粒度模型, 是采用大范圍的鄰域模型, 還是采用小范圍直徑也有爭(zhēng)議, 特別是由于對(duì)節(jié)點(diǎn)機(jī)的數(shù)量和通信能力要求很高, 所以細(xì)粒度模型的應(yīng)用范圍也不廣。粗粒度模型, 雖然還需深入研究, 但由于通信開銷較小, 可獲得接近線性的加速比, 而且非常適合運(yùn)行在通信帶寬較低的集群系統(tǒng)上