并行遺傳算法

1、并行遺傳算法及其應(yīng)用1、遺傳算法(GA)概述GA是一類基于自然選擇和遺傳學(xué)原理的有效搜索方法，它從一個種群開始，利用選擇、交叉、變異等遺傳算子對種群進(jìn)行不斷進(jìn)化，最后得到全局最優(yōu)解。生物遺傳物質(zhì)的主要載體是染色體，在GA中同樣將問題的求解表示成“染色體Chromosome”，通常是二進(jìn)制字符串表示，其本身不一定是解。首先，隨機(jī)產(chǎn)生一定數(shù)據(jù)的初始染色體，這些隨機(jī)產(chǎn)生的染色體組成一個種群(Population)，種群中染色體的數(shù)目稱為種群的大小或者種群規(guī)模。第二：用適值度函數(shù)來評價每一個染色體的優(yōu)劣，即染色體對環(huán)境的適應(yīng)程度，用來作為以后遺傳操作的依據(jù)。第三：進(jìn)行選擇(Selection),選擇過

2、程的目的是為了從當(dāng)前種群中選出優(yōu)良的染色體，通過選擇過程，產(chǎn)生一個新的種群。第四：對這個新的種群進(jìn)行交叉操作，變異操作。交叉、變異操作的目的是挖掘種群中個體的多樣性，避免有可能陷入局部解。經(jīng)過上述運(yùn)算產(chǎn)生的染色體稱為后代。最后，對新的種群(即后代)重復(fù)進(jìn)行選擇、交叉和變異操作，經(jīng)過給定次數(shù)的迭代處理以后，把最好的染色體作為優(yōu)化問題的最優(yōu)解。GA通常包含5個基本要素：1、參數(shù)編碼：GA是采用問題參數(shù)的編碼集進(jìn)行工作的，而不是采用問題參數(shù)本身，通常選擇二進(jìn)制編碼。2、初始種群設(shè)定：GA隨機(jī)產(chǎn)生一個由N個染色體組成的初始種群(Population),也可根據(jù)一定的限制條件來產(chǎn)生。種群規(guī)模是指種群中所

3、含染色體的數(shù)目。3、適值度函數(shù)的設(shè)定：適值度函數(shù)是用來區(qū)分種群中個體好壞的標(biāo)準(zhǔn)，是進(jìn)行選擇的唯一依據(jù)。目前主要通過目標(biāo)函數(shù)映射成適值度函數(shù)。4、遺傳操作設(shè)計(jì)：遺傳算子是模擬生物基因遺傳的操作，遺傳操作的任務(wù)是對種群的個體按照它們對環(huán)境的適應(yīng)的程度施加一定的算子，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過程。遺傳基本算子包括：選擇算子，交叉算子，變異算子和其他高級遺傳算子。5、控制參數(shù)設(shè)定：在GA的應(yīng)用中，要首先給定一組控制參數(shù)：種群規(guī)模，雜交率，變異率，進(jìn)化代數(shù)等。GA的優(yōu)點(diǎn)是擅長全局搜索，一般來說，對于中小規(guī)模的應(yīng)用問題，能夠在許可的范圍內(nèi)獲得滿意解，對于大規(guī)?；虺笠?guī)模的多變量求解任務(wù)則性能較差。另外，GA

4、本身不要求對優(yōu)化問題的性質(zhì)做一些深入的數(shù)學(xué)分析，從而對那些不太熟悉數(shù)學(xué)理論和算法的使用者來說，無疑是方便的。2、遺傳算法的運(yùn)行機(jī)理：對GA運(yùn)行機(jī)理的解釋有兩類：一是傳統(tǒng)的模式理論；二是1990年以后發(fā)展起來的有限狀態(tài)馬爾可夫鏈模型。（1）模式理論：由Holland創(chuàng)建，主要包括模式定理，隱并行性原理和積木塊假說三部分。模式是可行域中某些特定位取固定值的所有編碼的集合。模式理論認(rèn)為遺傳算法實(shí)質(zhì)上是模式的運(yùn)算，編碼的字母表越短，算法處理一代種群時隱含處理的模式就越多。當(dāng)算法采用二進(jìn)制編碼時，效率最高，處理規(guī)模為N的一代種群時，可同時處理O（N3）個模式。遺傳算法這種以計(jì)算少量編碼適應(yīng)度而處理大量模

5、式的性質(zhì)稱為隱并行性。模式理論還指出，目標(biāo)函數(shù)通常滿足積木塊假說，即階數(shù)高，長度長，平均適應(yīng)度高的模式可以由階數(shù)低，長度短，平均適應(yīng)度高的模式（積木塊）在遺傳算子的作用下，接合而生成。而不滿足積木塊假說的優(yōu)化問題被稱為騙問題（deceptiveproblem）。模式理論為遺傳算法構(gòu)造了一條通過在種群中不斷積累、拼接積木塊以達(dá)到全局最優(yōu)解的尋優(yōu)之路。但近十多年的研究，特別是實(shí)數(shù)編碼遺傳算法的廣泛應(yīng)用表明，上述理論與事實(shí)不符。（2）有限狀態(tài)馬爾可夫鏈模型：由于模式理論的種種缺陷，研究者開始嘗試?yán)糜邢逘顟B(tài)馬爾可夫鏈模型研究遺傳算法的運(yùn)行過程。對于遺傳算法可以解決的優(yōu)化問題，問題的可行域都是由有限個

6、點(diǎn)組成的，即便是參數(shù)可以連續(xù)取值的問題，實(shí)際上搜索空間也是以要求精度為單位的離散空間，因此遺傳算法的實(shí)際運(yùn)行過程可以用有限狀態(tài)馬爾可夫鏈的狀態(tài)轉(zhuǎn)移過程建模和描述。對于有m個可行解的目標(biāo)函數(shù)和種群規(guī)模為N的遺傳算法，N個個體共有種組合，相應(yīng)的馬爾可夫模型也有+學(xué)I個狀態(tài)。實(shí)際優(yōu)化問題的可行解數(shù)量mI川一iJ和種群規(guī)模N都十分可觀，馬爾可夫模型的狀態(tài)數(shù)幾乎為天文數(shù)字，因此利用精確的馬爾可夫模型計(jì)算種群的狀態(tài)分布是不可能的。為了換取模型的可執(zhí)行性，必須對實(shí)際模型采取近似簡化，保持算法的實(shí)際形態(tài)，通過對目標(biāo)函數(shù)建模，簡化目標(biāo)函數(shù)結(jié)構(gòu)實(shí)現(xiàn)模型的可執(zhí)行性。遺傳算法優(yōu)化的過程，可以看作算法在循環(huán)過程中不斷對

7、可行域進(jìn)行隨機(jī)抽樣，利用前面抽樣的結(jié)果對目標(biāo)點(diǎn)的概率分布進(jìn)行估計(jì)，然后根據(jù)估計(jì)出的分布推算下一次的抽樣點(diǎn)。馬爾可夫模型認(rèn)為遺傳算法是通過對搜索空間不同區(qū)域的抽樣，來估計(jì)不同區(qū)域的適應(yīng)度，進(jìn)而估計(jì)最優(yōu)解存在于不同區(qū)域的概率，以調(diào)整算法對不同區(qū)域的抽樣密度和搜索力度，進(jìn)而不斷提高對最優(yōu)解估計(jì)的準(zhǔn)確程度。可見，以鄰域結(jié)構(gòu)為依據(jù)劃分等價類的馬爾可夫模型更符合實(shí)際，對問題的抽象更能體現(xiàn)優(yōu)化問題的本質(zhì)。3、并行遺傳算法(PGA)雖然在許多領(lǐng)域成功地應(yīng)用遺傳算法，通常能在合理的時間內(nèi)找到滿意解，但隨著求解問題的復(fù)雜性及難度的增加，提高GA的運(yùn)行速度便顯得尤為突出，采用并行遺傳算法(PGA)是提高搜索效率的方

8、法之一。由于GA從種群出發(fā)，所以具有天然的并行處理特性，非常適合于在大規(guī)模并行計(jì)算機(jī)上實(shí)現(xiàn)，而大規(guī)模并行計(jì)算機(jī)的日益普及，為PGA奠定了物質(zhì)基礎(chǔ)。特別是GA中各個體適值計(jì)算可獨(dú)立進(jìn)行而彼此間無需任何通信，所以并行效率很高。實(shí)現(xiàn)PGA，不僅要把串行GA等價地變換成一種并行方案，更重要的是要將GA的結(jié)構(gòu)修改成易于并行化實(shí)現(xiàn)的形式，形成并行種群模型。并行種群模型對傳統(tǒng)GA的修改涉及到兩個方面：一是要把串行GA的單一種群分成多個子種群，分而治之；二是要控制、管理子種群之間的信息交換。不同的分治方法產(chǎn)生不同的PGA結(jié)構(gòu)。這種結(jié)構(gòu)上的差異導(dǎo)致了不同的PGA模型：全局并行模型、粗粒度模型、細(xì)粒度模型和混合模

9、型。3、1全局PGA模型該模型又稱主從PGA模型，它是串行GA的一種直接并行化方案，在計(jì)算機(jī)上以master-slave編程模式實(shí)現(xiàn)。它只有一個種群，所有個體的適應(yīng)度都根據(jù)整個種群的適應(yīng)度計(jì)算，個體之間可以任意匹配，每個個體都有機(jī)會和其他個體雜交而競爭，因而在種群上所作的選擇和匹配是全局的。對于這個模型有多種實(shí)現(xiàn)方法：第一種方法是僅僅對適值度函數(shù)計(jì)算進(jìn)行并行處理；第二種方法是對遺傳算子進(jìn)行并行處理。全局模型易于實(shí)現(xiàn)，如果計(jì)算時間主要用在評價上，這是一種非常有效的并行化方法。它最大的優(yōu)點(diǎn)是簡單，保留了串行GA的搜索行為，因而可直接應(yīng)用GA的理論來預(yù)測一個具體問題能否映射到并行GA上求解。對于適應(yīng)

10、度估值操作比其他遺傳算子計(jì)算量大的多時，它是很有效的，并且不需要專門的計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)。3、2粗粒度PGA模型該模型又稱分布式、MIMD、島模式遺傳算法模型，它是對經(jīng)典GAs結(jié)構(gòu)的擴(kuò)展。它將種群劃分為多個子種群（又稱區(qū)域），每個區(qū)域獨(dú)自運(yùn)行一個GA。此時，區(qū)域選擇取代了全局選擇，配偶取自同一區(qū)域，子代與同一區(qū)域中的親本競爭。除了基本的遺傳算子外，粗粒度模型引入了“遷移”算子，負(fù)責(zé)管理區(qū)域之間的個體交換。在粗粒度模型的研究中，要解決的重要問題是參數(shù)選擇，包括：遷移拓?fù)?、遷移率、遷移周期等。在種群劃分成子種群（區(qū)域）后，要為種群指定某種遷移拓?fù)?。遷移拓?fù)浯_定了區(qū)域之間個體的遷移路徑，遷移拓?fù)渑c特定的

11、并行機(jī)結(jié)構(gòu)有著內(nèi)在的對應(yīng)關(guān)系，大多采用類似于給定并行處理機(jī)的互連拓?fù)?。如果在順序?jì)算機(jī)上實(shí)現(xiàn)粗粒度模型，則可以考慮采用任意結(jié)構(gòu)。拓?fù)浣Y(jié)構(gòu)是影響PGA性能的重要方面，也是遷移成本的主要因素。區(qū)域之間的個體交換由兩個參數(shù)控制：遷移率和遷移周期。遷移基本上可以采用與匹配選擇和生存選擇相同的策略，遷移率常以絕對數(shù)或以子種群大小的百分比形式給出，典型的遷移率是子種群數(shù)目的10%到20%之間。遷移周期決定了個體遷移的時間間隔，一般是隔幾代（時期）遷移一次，也可以在一代之后遷移。通常，遷移率越高，則遷移周期就越長。有的采用同步遷移方式，有的采用異步遷移方式。遷移選擇負(fù)責(zé)選出遷移個體，通常選擇一個或幾個最優(yōu)個

12、體，有的采用適應(yīng)度比例或者排列比例選擇來選擇遷移個體，也有采用隨機(jī)選取和替換的。在大多數(shù)情況下,是把最差或者有限數(shù)目的最差個體替換掉.與遷移選擇類似，可采用適應(yīng)度比例或者排列比例選擇，確定被替換的個體，以便對區(qū)域內(nèi)部的較好個體產(chǎn)生選擇壓力?；趪鴥?nèi)的現(xiàn)狀，分布式PGA為國內(nèi)PGA研究的主要方向。分布式PGA作為PGA的一種形式，一般實(shí)行粗粒度及全局級并行，各子種群間的相互關(guān)系較弱，主要靠一些幾乎串行GA來加速搜索過程。采用分布式PGA求解問題的一般步驟為：（1）將一個大種群劃分為一些小的子種群，子種群的數(shù)目與硬件環(huán)境有關(guān)；（2）對這些子種群獨(dú)立的進(jìn)行串行GA操作，經(jīng)過一定周期后，從每個種群中選

13、擇一部分個體遷移到另外的子種群。對于個體遷移存在多種方法，第一種方法，在執(zhí)行遷移操作時，每次從子種群中隨機(jī)選擇一部分染色體發(fā)送出去，接收的染色體數(shù)應(yīng)該與發(fā)出的染色體相同。第二種方法，在執(zhí)行遷移操作時，首先在每個子種群內(nèi)只使用選擇而不使用其它遺傳算子繁殖一些后代，這些后代的數(shù)目與遷移數(shù)相同。然后再將這些后代的原子種群合并成一個大子種群并均勻隨即地從該子種群中選擇個體進(jìn)行遷移。這樣，待遷移后子種群的規(guī)模便又恢復(fù)到正常狀態(tài)。而當(dāng)子種群接收到從其他子種群遷移來的個體時則均勻隨即地替換掉子種群內(nèi)的個體。第三種方法，將其中一個子種群設(shè)置為中心子種群，其他子種群與中心子種群通信。中心子種群始終保持著整個種群

14、中當(dāng)前的最優(yōu)個體，其他子種群通過“引進(jìn)”中心子種群中的最優(yōu)個體來引導(dǎo)其加快收斂速度，改善個體特征。3、3細(xì)粒度PGA模型該模型又稱領(lǐng)域模型或SIMDPGA模型，對傳統(tǒng)GA作了修改。雖然細(xì)粒度模型也只有一個種群在進(jìn)化，但在種群平面網(wǎng)格細(xì)胞上，將種群劃分成了多個非常小的子種群（理想情況是每個處理單元上只有一個個體），子種群之間具有極強(qiáng)的通信能力，便于優(yōu)良解傳播到整個種群。全局選擇被領(lǐng)域選擇取代，個體適應(yīng)度的計(jì)算由局部領(lǐng)域中的個體決定，重組操作中的配偶出自同一領(lǐng)域，且子代同其同一領(lǐng)域的親本競爭空間，即選擇和重組只在網(wǎng)格中相鄰個體之間進(jìn)行。細(xì)粒度模型要解決的主要問題是領(lǐng)域結(jié)構(gòu)和選擇策略。領(lǐng)域結(jié)構(gòu)既決定

15、了種群中個體的空間位置，也確定了個體在種群中傳播的路徑。領(lǐng)域結(jié)構(gòu)主要受特定并行計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)和通信結(jié)構(gòu)影響。領(lǐng)域拓?fù)浯_定一個個體的鄰居，構(gòu)成該個體的局部領(lǐng)域。通常，只有一個拓?fù)涞闹苯宇I(lǐng)域才屬于其局部領(lǐng)域，若把某個固定步數(shù)內(nèi)所能到達(dá)的所有個體也包含在內(nèi)，則可以擴(kuò)大領(lǐng)域半徑。在確定選擇策略時，要考慮到選擇壓力的變化，而選擇壓力與領(lǐng)域結(jié)構(gòu)有關(guān)。與全局匹配選擇類似，局部匹配選擇可以采用局部適應(yīng)度比例、排列比例選擇，以及隨機(jī)行走選擇。局部生存選擇確定局部鄰域中被替換的個體，如果子代自動替換鄰域中心的那個個體，那么可以直接使用代替換作為局部生存策略。3、4混合PGA模型該模型又稱為多層并行PGA模型，它

16、結(jié)合不同PGA模型的特性，不僅染色體競爭求取最優(yōu)解，而且在GA結(jié)構(gòu)上也引入了競爭以提供更好的環(huán)境便于進(jìn)化。通常,混合PGA以層次結(jié)構(gòu)組合，上層多采用粗粒度模型，下層既可采用粗粒度模型也可采用細(xì)粒度模型?；蛘撸N群可以按照粗粒度PGA模型分裂，遷移操作可以采用細(xì)粒度PGA模型。3、5四種模型的比較就現(xiàn)有的研究結(jié)果來看，很難分出各模型的高低。在評價并行模型的差異時，有時還得深入到實(shí)現(xiàn)細(xì)節(jié)上，如問題的差異、種群大小、或者不同的局部搜索方法等。但有一個結(jié)論是肯定的：不采用全局并行模型，而采用粗粒度模型或者細(xì)粒度模型通常能獲得更好的性能。粗粒度模型與細(xì)粒度模型孰優(yōu)孰劣，尚是一個未知數(shù)。目前，以粗粒度模型

17、最為流行，因?yàn)橐皇瞧鋵?shí)現(xiàn)較容易，只需在串行GA中增加遷移子例程，在并行計(jì)算機(jī)的節(jié)點(diǎn)上各自運(yùn)行一個副本，并定期交換幾個個體即可；二是在沒有并行計(jì)算機(jī)時，也可在網(wǎng)絡(luò)或單機(jī)系統(tǒng)上模擬實(shí)現(xiàn)。雖然并行GA能有效地求解許多困難的問題，也能在不同類型的并行計(jì)算機(jī)上有效地實(shí)現(xiàn)，但仍有一些基本的問題需要解決。種群大小可能既影響大多數(shù)GA的性能，也決定GA找到解所需時間的主要因素。在PGA中，另一個重要問題是如何降低通信開銷，包括遷移率的確定，使得區(qū)域的行為象單個種群一樣；確定通信拓?fù)?，既能充分地組合優(yōu)良解，又不導(dǎo)致過多的通信開銷；能否找到一個最優(yōu)的區(qū)域數(shù)等。另外，對不同的應(yīng)用問題，混合模型難以設(shè)定基本GA的參數(shù)

18、，其節(jié)點(diǎn)的結(jié)構(gòu)是動態(tài)變化的，它比粗粒度和細(xì)粒度模型更具有一般性，算法更為復(fù)雜，實(shí)現(xiàn)代價更高。4、并行遺傳算法的評價模型：并行遺傳算法的性能主要體現(xiàn)在收斂速度和精度兩個方面，它們除了與遷移策略有關(guān)，還與一些參數(shù)選取的合理性密切相關(guān)，如遺傳代數(shù)、種群數(shù)目、種群規(guī)模、遷移率和遷移間隔。利用Amdahl定律評價并行遺傳算法，即絕對加速比（speedup）=Ts/Tp，其中，Ts為串行遺傳算法（單個處理器）的執(zhí)行時間；p為并行遺傳算法的執(zhí)行時間。Amdahl定律適用于負(fù)載固定的情況，對于并行遺傳算法而言，就是適用于總種群規(guī)模不變的情況。所以，Amdahl定律適用于主從式和細(xì)粒度模型，在適應(yīng)度評價計(jì)算量較

19、大時，主從式模型可以得到接近線性的加速比。由于細(xì)粒度模型的應(yīng)用較少，適用的SIMD并行機(jī)的可擴(kuò)展性也不突出，所以很少有人評價細(xì)粒度模型的加速比。利用Amdahl定律評價粗粒度模型時，需保持總的種群規(guī)模，即子種群數(shù)量和子種群規(guī)模成反比。這種情況下粗粒度模型的加速比接近線性，這是由于粗粒度模型的通信開銷和同步開銷都不大。5、實(shí)例：帶約束并行多機(jī)調(diào)度5、1問題描述如上圖所示。圖中節(jié)點(diǎn)間的有向邊表示工件之間的后繼或編序關(guān)系。因此，Ti-Tj表示工件Tj在完成之后才能啟動工件Ti。顯然對于n個相關(guān)工件，我們可以根據(jù)工件間的約束關(guān)系所表示成的后繼圖產(chǎn)生一符合約束條件的工件序列(a,a，a，a)(0Wan)

20、，其中a表示一個工件。例如，根據(jù)上01in-1ii圖所示的后繼圖，可產(chǎn)生工件序列(0，2，5，1，3，4，7，6，8)，按該工件序列調(diào)度滿足工件之間的約束關(guān)系。如何表示問題的目標(biāo)函數(shù)。設(shè)t(j)為機(jī)器加工工件j所需時間，tb(i,j)為機(jī)器i加工工件j的最早時刻。為了使GA算法解決問題方便，我們用x(i,j)表示工件j在機(jī)器i上是否加工，若x(i,j)=1，則表示工件j在機(jī)器i上加工；若x(i,j)=0，則表示工件j不在機(jī)器i上加工。因而x(i,j)t(j)為機(jī)器i加工工件j的實(shí)際加工時間。問題的目標(biāo)函數(shù)可表示為:minGms=minmaxfinish(0),finish(1),.,finis

21、h(i),.,finish(m-1)。其中finish(i)表示第i臺處理機(jī)加工分配的工件所需時間。finish(i)=maxx(0,a)tb(i,a)+t(a),x(1,a)tb(i,a)+00011t(a),.,x(n-1,a)tb(i,a)+t(a)。1n-1n-1n-15、2并行GA實(shí)現(xiàn)帶約束并行多機(jī)調(diào)度問題的并行GA實(shí)現(xiàn)如下：(1)產(chǎn)生一個進(jìn)程(該進(jìn)程為父進(jìn)程，在進(jìn)行串行GA的同時，用于存放和發(fā)送當(dāng)前最優(yōu)個體)；由父進(jìn)程產(chǎn)生m-1個子進(jìn)程(每個子進(jìn)程用于實(shí)現(xiàn)串行GA)；各子進(jìn)程(包括父進(jìn)程)進(jìn)行串行GA,當(dāng)子進(jìn)程中遺傳代數(shù)(ge)被10整除，子進(jìn)程發(fā)送最優(yōu)個體至父進(jìn)程；父進(jìn)程選擇當(dāng)前各子進(jìn)程中最優(yōu)個體(mol