并行遺傳算法

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

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

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

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

5、式的性質(zhì)稱為隱并行性。模式理論還指出，目標(biāo)函數(shù)通常滿足積木塊假說，即階數(shù)高，長(zhǎng)度長(zhǎng)，平均適應(yīng)度高的模式可以由階數(shù)低，長(zhǎng)度短，平均適應(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)行過程。對(duì)于遺傳算法可以解決的優(yōu)化問題，問題的可行域都是由有限個(gè)

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

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

8、法之一。由于GA從種群出發(fā)，所以具有天然的并行處理特性，非常適合于在大規(guī)模并行計(jì)算機(jī)上實(shí)現(xiàn)，而大規(guī)模并行計(jì)算機(jī)的日益普及，為PGA奠定了物質(zhì)基礎(chǔ)。特別是GA中各個(gè)體適值計(jì)算可獨(dú)立進(jìn)行而彼此間無需任何通信，所以并行效率很高。實(shí)現(xiàn)PGA，不僅要把串行GA等價(jià)地變換成一種并行方案，更重要的是要將GA的結(jié)構(gòu)修改成易于并行化實(shí)現(xiàn)的形式，形成并行種群模型。并行種群模型對(duì)傳統(tǒng)GA的修改涉及到兩個(gè)方面：一是要把串行GA的單一種群分成多個(gè)子種群，分而治之；二是要控制、管理子種群之間的信息交換。不同的分治方法產(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)。它只有一個(gè)種群，所有個(gè)體的適應(yīng)度都根據(jù)整個(gè)種群的適應(yīng)度計(jì)算，個(gè)體之間可以任意匹配，每個(gè)個(gè)體都有機(jī)會(huì)和其他個(gè)體雜交而競(jìng)爭(zhēng)，因而在種群上所作的選擇和匹配是全局的。對(duì)于這個(gè)模型有多種實(shí)現(xiàn)方法：第一種方法是僅僅對(duì)適值度函數(shù)計(jì)算進(jìn)行并行處理；第二種方法是對(duì)遺傳算子進(jìn)行并行處理。全局模型易于實(shí)現(xiàn)，如果計(jì)算時(shí)間主要用在評(píng)價(jià)上，這是一種非常有效的并行化方法。它最大的優(yōu)點(diǎn)是簡(jiǎn)單，保留了串行GA的搜索行為，因而可直接應(yīng)用GA的理論來預(yù)測(cè)一個(gè)具體問題能否映射到并行GA上求解。對(duì)于適應(yīng)

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

11、并行機(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%之間。遷移周期決定了個(gè)體遷移的時(shí)間間隔，一般是隔幾代（時(shí)期）遷移一次，也可以在一代之后遷移。通常，遷移率越高，則遷移周期就越長(zhǎng)。有的采用同步遷移方式，有的采用異步遷移方式。遷移選擇負(fù)責(zé)選出遷移個(gè)體，通常選擇一個(gè)或幾個(gè)最優(yōu)個(gè)

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

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

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

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

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

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

18、，其節(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/Tp，其中，Ts為串行遺傳算法（單個(gè)處理器）的執(zhí)行時(shí)間；p為并行遺傳算法的執(zhí)行時(shí)間。Amdahl定律適用于負(fù)載固定的情況，對(duì)于并行遺傳算法而言，就是適用于總種群規(guī)模不變的情況。所以，Amdahl定律適用于主從式和細(xì)粒度模型，在適應(yīng)度評(píng)價(jià)計(jì)算量較

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

20、，其中a表示一個(gè)工件。例如，根據(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所需時(shí)間，tb(i,j)為機(jī)器i加工工件j的最早時(shí)刻。為了使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í)際加工時(shí)間。問題的目標(biāo)函數(shù)可表示為:minGms=minmaxfinish(0),finish(1),.,finis

21、h(i),.,finish(m-1)。其中finish(i)表示第i臺(tái)處理機(jī)加工分配的工件所需時(shí)間。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)生一個(gè)進(jìn)程(該進(jìn)程為父進(jìn)程，在進(jìn)行串行GA的同時(shí)，用于存放和發(fā)送當(dāng)前最優(yōu)個(gè)體)；由父進(jìn)程產(chǎn)生m-1個(gè)子進(jìn)程(每個(gè)子進(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)個(gè)體至父進(jìn)程；父進(jìn)程選擇當(dāng)前各子進(jìn)程中最優(yōu)個(gè)體(mol