并行遺傳算法

并行遺傳算法及其應(yīng)用1、遺傳算法(GA)概述GA是一類基于自然選擇和遺傳學(xué)原理的有效搜索方法，它從一個(gè)種群開(kāi)GA中同樣將問(wèn)題的求解表Chromosom”e，通常是二進(jìn)制字符串表示，其本身不一定是Population(Selection)，選擇過(guò)程的目的是為了從當(dāng)前種群中選出優(yōu)良的染色體，通過(guò)選擇過(guò)程，產(chǎn)生一個(gè)新的種群。第四：對(duì)這個(gè)新的種群進(jìn)行交叉操作，變異操作。交叉、變異操作的目的是挖掘種群中個(gè)體的多樣性，避免有可能陷入局部解。經(jīng)過(guò)上述運(yùn)算產(chǎn)生的染色體稱為后代。最后，對(duì)新的種群(即后代)重復(fù)進(jìn)行選擇、交叉和變異操作，經(jīng)過(guò)給定次數(shù)的迭代處理以后，把最好的染色體作為優(yōu)化問(wèn)題的最優(yōu)解。GA51GA是采用問(wèn)題參數(shù)的編碼集2、初始種GANPopulation)，45GAGA性能較差。另外，GA本身不要求對(duì)優(yōu)化問(wèn)題的性質(zhì)做一些深入的數(shù)學(xué)分析，從而對(duì)那些不太熟悉數(shù)學(xué)理論和算法的使用者來(lái)說(shuō)，無(wú)疑是方便的。2、遺傳算法的運(yùn)行機(jī)理：GA1990Holland創(chuàng)建，主要包括模式定理，隱并行性原理和積木塊假說(shuō)三部分。模式是可行域中某些特定位取固定值的所有編碼的集合。模式理論認(rèn)為遺傳算法實(shí)質(zhì)上是模式的運(yùn)算，編碼的字母表越短，算法處理一代種群時(shí)隱含處理的模式就越多。當(dāng)算法采用二進(jìn)制編碼時(shí)，效率最高，處理規(guī)模為 N的一代種群時(shí)，可同時(shí)處理（N3）個(gè)模式。遺傳算法這種以計(jì)算少量編碼適常滿足積木塊假說(shuō)，即階數(shù)高，長(zhǎng)度長(zhǎng)，平均適應(yīng)度高的模式可以由階數(shù)（）（deceptiveproblem）碼遺傳算法的廣泛應(yīng)用表明，上述理論與事實(shí)不符。有限狀態(tài)馬爾可夫鏈模型：由于模式理論的種種缺陷，研究者開(kāi)始嘗試?yán)糜邢逘顟B(tài)馬爾可夫鏈模型研究遺傳算法的運(yùn)行過(guò)程。對(duì)于遺傳算可以解決的優(yōu)化問(wèn)題，問(wèn)題的可行域都是由有限個(gè)點(diǎn)組成的，即便是參數(shù)可以連續(xù)取值的問(wèn)題，實(shí)際上搜索空間也是以要求精度為單位的離散空間，因此遺傳算法的實(shí)際運(yùn)行過(guò)程可以用有限狀態(tài)馬爾可夫鏈的狀態(tài)轉(zhuǎn)移過(guò)程建模和描述。對(duì)于有m個(gè)可行解的目標(biāo)函數(shù)和種群規(guī)模為N的遺傳算法，N個(gè)個(gè)體共有 種組合，相應(yīng)的馬爾可夫模型也有個(gè)狀態(tài)。實(shí)際優(yōu)化問(wèn)題的可行解數(shù)量m和種群規(guī)模N都十分可觀，馬爾可夫模型的狀態(tài)數(shù)幾乎為天文數(shù)字，因此利用精確的馬爾可夫模型計(jì)算種群的狀態(tài)分布是不可能的。為了換取模型的可執(zhí)行度?？梢?jiàn)，以鄰域結(jié)構(gòu)為依據(jù)劃分等價(jià)類的馬爾可夫模型更符合實(shí)際，對(duì)問(wèn)題的抽象更能體現(xiàn)優(yōu)化問(wèn)題的本質(zhì)。3、并行遺傳算法（PGA）雖然在許多領(lǐng)域成功地應(yīng)用遺傳算法，通常能在合理的時(shí)間內(nèi)找到滿意GA的運(yùn)行速度便顯得尤（PGA）GAPGA奠定了物質(zhì)基礎(chǔ)。特GAPGAGAGAGAGA的單一種群PGAPGA3、1PGA模型PGAGA的一種直接并行化方案，在計(jì)算master-slave編程模式實(shí)現(xiàn)。它只有一個(gè)種群，所有個(gè)體的適應(yīng)度計(jì)算時(shí)間主要用在評(píng)價(jià)上，這是一種非常有效的并行化方法。GAGAGA上求解。對(duì)于適應(yīng)度估值操32PGA模型MIMDGAs結(jié)（）GA在種群劃分成子種群（區(qū)）后，要為種群指定某種遷移拓?fù)?。遷移拓?fù)浯_定了區(qū)域之間個(gè)體的遷移路徑，遷移拓?fù)渑c特定的并行機(jī)結(jié)構(gòu)有著內(nèi)在的對(duì)應(yīng)關(guān)系，大多采用類似于給定并行處理機(jī)的互連拓?fù)洹Ｈ绻陧樞蛴?jì)算機(jī)上實(shí)現(xiàn)粗粒度模型，則可以考慮采用任意結(jié)構(gòu)。拓?fù)浣Y(jié)構(gòu)是影響PGA性的重要方面，也是遷移成本的主要因素。區(qū)域之間的個(gè)體交換由兩個(gè)參數(shù)控制：遷移率和遷移周期。遷移基本上可以采用與匹配選擇和生存選擇相同的策略，遷移率常以絕對(duì)數(shù)或以子種群大小的百分比形式給出，典型的遷移率是子種群數(shù)目的 10%到20%之（時(shí)期）遷移一次，也可以在一代之后遷移。通常，遷移率越高，則遷移周期就越長(zhǎng)。有的采用同步遷移方式，有的采用異步遷移方式。遷移選擇負(fù)責(zé)選出遷移個(gè)體，通常選擇一個(gè)或幾個(gè)最優(yōu)個(gè)體，有的采用適應(yīng)度比例或者排列比例選擇來(lái)選擇遷移個(gè)體，也有采用隨機(jī)選取和替換的。在大多數(shù)情況下,是把最差或者有限數(shù)目的最差個(gè)體替換掉.與遷移選擇類似，可采用適應(yīng)度比例或者排列比例選擇，確定被替換的個(gè)體，以便對(duì)區(qū)域內(nèi)部的較好個(gè)體產(chǎn)生選擇壓力。PGAPGAPGAPGAGAPGA（1）數(shù)目與硬件環(huán)境有關(guān)；（ 2）對(duì)GA法，在執(zhí)行遷移操作時(shí)，每次從子種群中隨機(jī)選擇一部分染色體發(fā)送出3、3PGA模型SIMDPGAGA作了修改。雖然細(xì)粒（），構(gòu)和選擇策略。體，那么可以直接使用代替換作為局部生存策略。3、4PGA模型PGAPGA模型的特性，不僅染GA結(jié)構(gòu)上也引入了競(jìng)爭(zhēng)以提供更好的環(huán)境便于進(jìn)化。通常，混合PGAPGA模PGA模型。3、5四種模型的比較就現(xiàn)有的研究結(jié)果來(lái)看，很難分出各模型的高低。在評(píng)價(jià)并行模型的差異時(shí)，有時(shí)還得深入到實(shí)現(xiàn)細(xì)節(jié)上，如問(wèn)題的差異、種群大小、或者不同的局部搜索方法等。但有一個(gè)結(jié)論是肯定的：不采用全局并行模型，而采用粗粒度模型或者細(xì)粒度模型通常能獲得更好的性能。粗粒度模型與細(xì)粒度模型孰優(yōu)孰劣，尚是一個(gè)未知數(shù)。目前，以粗粒度模型最為流行，因?yàn)橐皇瞧鋵?shí)現(xiàn)較容易，只需在串行GA中增GA能有效地求解許多困難的問(wèn)題，也能在不同類型的并行計(jì)算機(jī)上GAGAPGA中，另一個(gè)重要一樣；確定通信拓?fù)?，既能充分地組合優(yōu)良解，又不導(dǎo)致過(guò)多的通信開(kāi)銷；能否找到一個(gè)最優(yōu)的區(qū)域數(shù)等。GA的參數(shù)，其節(jié)點(diǎn)的結(jié)構(gòu)是動(dòng)態(tài)變化的，它比粗粒度和細(xì)粒度模型更具有一般性，算法更為復(fù)雜，實(shí)現(xiàn)代價(jià)更高。4、并行遺傳算法的評(píng)價(jià)模型：并行遺傳算法的性能主要體現(xiàn)在收斂速度和精度兩個(gè)方面，它們除了與遷移策略有關(guān)，還與一些參數(shù)選取的合理性密切相關(guān)，如遺傳代數(shù)、種群數(shù)目、種群規(guī)模、遷移率和遷移間隔。利用Amdahl定律評(píng)價(jià)并行遺傳算法，即絕對(duì)加速比(speedup)=Ts/TpTs(的執(zhí)行時(shí)間；Tp為并行AmdahlAmdahl定律適用SIMDAmdahl5、實(shí)例：帶約束并行多機(jī)調(diào)度相關(guān)工件表示成一個(gè)后繼圖，如上圖所示。圖中節(jié)點(diǎn)間的有向邊表示工件之間的后繼或編序關(guān)系。因此，Ti→Tj表示工件Tj在完成之后才能啟動(dòng)工件Ti。顯然對(duì)于n個(gè)相關(guān)工件，我們可以根據(jù)工件間的約束關(guān)系所表示aa，?a，?a)0 1 i n-1(0≤a<n)其中a可產(chǎn)i i生工件序列(0，2，5，1，3，4，7，6，8)，按該工件序列調(diào)度滿足工件之間的約束關(guān)系。(2)t(j)j所需時(shí)間，tb(i,j)為機(jī)器i加工工件j的最早時(shí)刻。為了使GA算法解決問(wèn)題方x(i,j)jix(i,j)=1jix(i,j)0j不在ix(i,jt(j)ij的實(shí)際加工時(shí)間。問(wèn)題的目標(biāo)函數(shù)可表示為:minGms=min{max[finish(0),finish(1),...,finish(i),...,finish(m1)finish(i)i臺(tái)處理機(jī)加工分配的工件所需時(shí)間。finish(i)=max{x(0,a )[tb(i,a )+0 05、5、1問(wèn)題描述最小化完工時(shí)間的帶約束并行多n個(gè)相關(guān)的工件，mm一個(gè)最小調(diào)度，即確定每臺(tái)機(jī)器上加工的工件算法關(guān)鍵在于：(1)n個(gè)0 1t(a)],...,x(n-1,a1

)+1)[tb(i,a)+t(a)]}。n-1 n-15、2GA實(shí)現(xiàn)GA實(shí)現(xiàn)如下：GAm1GA)；GA(ge)被10(molist)，發(fā)送給各子進(jìn)程；molist替換各子進(jìn)程當(dāng)前代種群中適應(yīng)值最低個(gè)體；gegmax(gmax)(7)步，否則轉(zhuǎn)第(3)步；(7)算法終止。6NP完全問(wèn)題，因此，精確參考文獻(xiàn)：1、ZdeněkKonfrst.ParallelGeneticAlgorithms:ComputingTrends,AplicationsandPerspectives.Proceedingsofthe18thInternationalParallelandDistributedProecessingSymposium,2004.2、郭彤城,慕春棣.并行遺傳算法的新進(jìn)展.系統(tǒng)工程理論與實(shí)踐,2002.3、曾國(guó)蓀,丁春玲.并行遺傳算法分析.計(jì)算機(jī)工程,200