并行遺傳算法

并行遺傳算法第一頁(yè)，共十九頁(yè)，2022年，8月28日遺傳的基本概念遺傳算法（geneticalgorithms,簡(jiǎn)稱GA）是J.Holland于1975年受生物進(jìn)化論的啟發(fā)而提出來(lái)的。GA是基于“適者生存”的一種高度并行、隨機(jī)和自適應(yīng)的優(yōu)化算法，它將問(wèn)題的求解表示成“染色體”適者生存的過(guò)程，通過(guò)“染色體”群的一代代不斷進(jìn)化，包括復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個(gè)體，從而求得問(wèn)題的最優(yōu)解或滿意解。優(yōu)點(diǎn)：隱含并行性全局解空間搜索能力第二頁(yè)，共十九頁(yè)，2022年，8月28日遺傳與算法的對(duì)應(yīng)遺傳算法通過(guò)模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，將搜索空間映射為遺傳空間，把可能的解編碼成一個(gè)向量（即染色體），向量的每個(gè)元素稱為基因，然后通過(guò)不斷計(jì)算各染色體的適應(yīng)度值，選擇最好的染色體，獲得最優(yōu)解。第三頁(yè)，共十九頁(yè)，2022年，8月28日遺傳算法的基本步驟確定決策變量及各種約束條件，即確定個(gè)體的表現(xiàn)型X和問(wèn)題的解空間；建立優(yōu)化模型，即確定目標(biāo)函數(shù)的類(lèi)型；確定表示可行解的染色體編碼方案，即確定出個(gè)體的基因型X及遺傳算法的搜索空間；確定編碼方法，即確定出由基因型X到個(gè)體表現(xiàn)型X的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換方法；確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定由目標(biāo)函數(shù)值f(x)到個(gè)體適應(yīng)度F(x)的變換規(guī)則；設(shè)計(jì)遺傳算子，即確定出選擇、交叉、變異的具體操作方法；確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定遺傳算法的Pc,Pm等參數(shù)。第四頁(yè)，共十九頁(yè)，2022年，8月28日特點(diǎn)遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象；遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息，它使用由目標(biāo)函數(shù)值變換得到的適應(yīng)度函數(shù)值作為下一步搜索方向和范圍的判斷標(biāo)準(zhǔn)；遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息。它是從很多個(gè)體所組成的一個(gè)初始群體開(kāi)始最優(yōu)解的搜索，而不是從單一的個(gè)體開(kāi)始搜索。這樣可以避免一些不必要的搜索，其實(shí)內(nèi)在包含了算法的隱含并行性；遺傳算法屬于非確定性的概率算法。正是由于它的不確定和概率性，導(dǎo)致算法找到的解只能夠是相對(duì)最優(yōu)解。第五頁(yè)，共十九頁(yè)，2022年，8月28日遺傳算法的實(shí)現(xiàn)確定問(wèn)題的編碼方案確定適配值函數(shù)設(shè)計(jì)遺傳算子算法參數(shù)選擇，主要包括種群數(shù)目、交叉與變異概率、進(jìn)化代數(shù)等。確定算法的終止條件。第六頁(yè)，共十九頁(yè)，2022年，8月28日編碼編碼就是將問(wèn)題的解用一種計(jì)算機(jī)可以識(shí)別的碼來(lái)表示，將問(wèn)題空間的狀態(tài)空間與GA的碼空間相對(duì)應(yīng)。GA的優(yōu)化過(guò)程是在一定編碼機(jī)制對(duì)應(yīng)的碼空間上進(jìn)行的，因此編碼的選擇是影響算法性能與效率的重要因素。編碼方式：二進(jìn)制編碼方法格雷碼編碼方法浮點(diǎn)數(shù)編碼方法通常所采用的編碼方式是二進(jìn)制編碼。第七頁(yè)，共十九頁(yè)，2022年，8月28日二進(jìn)制編碼方法二進(jìn)制編碼所構(gòu)成的個(gè)體基因是一個(gè)經(jīng)過(guò)編碼的符號(hào)串，二進(jìn)制編碼符號(hào)串的長(zhǎng)度和問(wèn)題的精度有關(guān)。假設(shè)問(wèn)題的參數(shù)取值范圍是[Umin,Umax],使用長(zhǎng)度為L(zhǎng)的二進(jìn)制編碼符號(hào)串表示該參數(shù)，則能產(chǎn)生2L種不同的編碼。若參數(shù)的編碼的對(duì)應(yīng)關(guān)系如下：

000000…000000=0→Umin000000…000001=1→Umin+δ111111…111111=2L-1→Umax二進(jìn)制的編碼精度為：設(shè)每個(gè)個(gè)體的編碼為：對(duì)應(yīng)的解碼公式：第八頁(yè)，共十九頁(yè)，2022年，8月28日適配值函數(shù)適配值函數(shù)用于對(duì)個(gè)體進(jìn)行評(píng)價(jià)，是優(yōu)化過(guò)程發(fā)展的依據(jù)。在簡(jiǎn)單問(wèn)題的優(yōu)化時(shí)，通?？梢詫⒛繕?biāo)函數(shù)直接變換成適配值函數(shù)，譬如將個(gè)體X的適配值f(x)定義為M-c(x)或eac(x),其中M為一足夠大正數(shù)，c(x)為個(gè)體的目標(biāo)值，a>0。在復(fù)雜問(wèn)題的優(yōu)化時(shí)，往往需要構(gòu)造合適的評(píng)價(jià)函數(shù)，適應(yīng)GA進(jìn)行優(yōu)化。第九頁(yè)，共十九頁(yè)，2022年，8月28日算法參數(shù)選擇種群的數(shù)目：影響算法優(yōu)化性能和效率。種群太小導(dǎo)致采樣點(diǎn)數(shù)目不足，算法性能低；而種群數(shù)目太大又會(huì)增加計(jì)算量，導(dǎo)致收斂時(shí)間過(guò)長(zhǎng)。所以在設(shè)計(jì)算法時(shí)應(yīng)該針對(duì)具體問(wèn)題選擇適宜的種群數(shù)目；交叉概率：用于控制交叉操作的頻率。概率太大，種群中串的更新很快，會(huì)使高適配值的個(gè)體很快被破壞掉；概率太小，交叉操作很少進(jìn)行，會(huì)使搜索停止不前；變異概率：增加種群多樣性?；诙M(jìn)制編碼的GA中，一個(gè)非常小的變異率就會(huì)改變整個(gè)種群的基因。變異概率必須取一個(gè)適當(dāng)?shù)闹担〔粫?huì)產(chǎn)生新個(gè)體，太大又會(huì)使GA完全的隨機(jī)搜索；總結(jié)：遺傳算法參數(shù)的選擇是非常重要的，同時(shí)也非常復(fù)雜，參數(shù)選取需要按照問(wèn)題的實(shí)際大小來(lái)進(jìn)行選擇。第十頁(yè)，共十九頁(yè)，2022年，8月28日選擇算子選取選擇的定義：從群體中選擇優(yōu)秀的個(gè)體，淘汰劣質(zhì)個(gè)體的操作。選擇算子的作用：將優(yōu)化的解直接遺傳到下一代，或通過(guò)配對(duì)交叉的方式遺傳到下一代。常用選擇算子：適應(yīng)度比例法，也叫賭輪法或蒙特卡羅法。選擇執(zhí)行過(guò)程：

1)計(jì)算出群體中所有個(gè)體適應(yīng)度的總值；

2)計(jì)算每個(gè)個(gè)體相對(duì)適應(yīng)度，即個(gè)體遺傳到下一代的概率；

3)使用模擬賭輪操作(srand(0,1))來(lái)確定各個(gè)個(gè)體被選中的次數(shù)。假設(shè)群體的大小為n，其中個(gè)體i的適應(yīng)度值為fi，個(gè)體i被選擇的概率pi表示為Pi反映了個(gè)體i的適應(yīng)度在整個(gè)群體的個(gè)體適應(yīng)度總和中所占的比例。適應(yīng)度越高，被選中的概率越高。第十一頁(yè)，共十九頁(yè)，2022年，8月28日算法終止條件在實(shí)際中算法是不允許無(wú)止境的發(fā)展下去的，而且對(duì)通常問(wèn)題的最優(yōu)解具有不確定性，因此需要一個(gè)條件來(lái)終止算法的進(jìn)程。目前最常用的終止條件是事先給定一個(gè)最大進(jìn)化步數(shù)，或者判斷最佳優(yōu)化值是否連續(xù)且經(jīng)過(guò)若干步后都沒(méi)有變化等。第十二頁(yè)，共十九頁(yè)，2022年，8月28日隱含并行性設(shè)ε為一小正數(shù)，L<ε(l-1)+1,N=2l,2，則遺傳算法一次處理的存活概率不小于1-

ε且定義長(zhǎng)度不大于L的模式數(shù)位O（N3）.遺傳算法表面上僅對(duì)每代的N個(gè)個(gè)體作處理，但實(shí)際上并行處理了大約O（N3）個(gè)模式，并且無(wú)額外的存儲(chǔ)，這正是遺傳算法具有高校搜索能力的原因，這就是遺傳算法的隱含并行。第十三頁(yè)，共十九頁(yè)，2022年，8月28日并行遺傳算法傳統(tǒng)的遺傳算法出現(xiàn)的問(wèn)題：局部搜索性能較差，對(duì)某些分布變化緩慢，面對(duì)大型計(jì)算問(wèn)題速度難以達(dá)到要求并行遺傳算法提出：在遺傳算法并行運(yùn)算的基礎(chǔ)上，通過(guò)多種群并行進(jìn)化和引入遷移算子進(jìn)行進(jìn)行種群之間的信息交流，實(shí)現(xiàn)多種群的協(xié)同進(jìn)化。通過(guò)人工選擇系數(shù)對(duì)每個(gè)種群最優(yōu)化個(gè)體保存，通過(guò)對(duì)協(xié)調(diào)種群間的信息交換策略得到最好的進(jìn)化效果。遺傳算法的并行化實(shí)現(xiàn)就是將進(jìn)化過(guò)程劃分到不同的計(jì)算節(jié)點(diǎn)上，進(jìn)行分布式進(jìn)化，并通過(guò)一定的種群間信息交換策略實(shí)現(xiàn)優(yōu)良基因的轉(zhuǎn)換。第十四頁(yè)，共十九頁(yè)，2022年，8月28日并行遺傳算法的分類(lèi)標(biāo)準(zhǔn)型并行方法：未改變串行遺傳算法的基本特點(diǎn)，在一個(gè)總體的環(huán)境中實(shí)現(xiàn)進(jìn)化運(yùn)算，它需要使用一個(gè)統(tǒng)一的群體。實(shí)現(xiàn)時(shí)需要一個(gè)全局存儲(chǔ)器和一個(gè)統(tǒng)一的控制機(jī)構(gòu)來(lái)協(xié)調(diào)群體的遺傳進(jìn)化過(guò)程及群體之間的通信過(guò)程。缺點(diǎn)：運(yùn)行速率低。分解型并行方法：將整個(gè)群體分解為幾個(gè)子群體，各子群體彼此分配在不同的節(jié)點(diǎn)上，各自運(yùn)行自身節(jié)點(diǎn)上的遺傳算法，在適當(dāng)?shù)臅r(shí)候各節(jié)點(diǎn)之間交換信息。這種實(shí)現(xiàn)方法比較符合個(gè)體自然進(jìn)化的過(guò)程，保存了各節(jié)點(diǎn)上群體進(jìn)化的局部特性，有效回避了普通遺傳算法早熟現(xiàn)象。目前比較常用的類(lèi)型是分解型并行方法，按照不同的組織結(jié)構(gòu)，它又可以分為下面三種不同的類(lèi)型：主從式并行計(jì)算粗粒度并行計(jì)算細(xì)粒度并行計(jì)算第十五頁(yè)，共十九頁(yè)，2022年，8月28日主從式并行計(jì)算在這種并行方式中，一個(gè)主過(guò)程調(diào)節(jié)若干個(gè)仆過(guò)程。其中主過(guò)程控制選擇、交叉和變異，仆過(guò)程僅執(zhí)行適配值的計(jì)算。缺點(diǎn)：1、各仆過(guò)程計(jì)算適應(yīng)度值的時(shí)間存在明顯差異時(shí)，將會(huì)照成整個(gè)系統(tǒng)長(zhǎng)時(shí)間的等待；2、整個(gè)系統(tǒng)可靠性較差，對(duì)主過(guò)程狀況的依賴性較大。偽代碼：Begin(1)產(chǎn)生一個(gè)初始群體(2)whilerunningdo(2.1)for=1tosdo

計(jì)算個(gè)體i的適應(yīng)度值(并行部分)（2.2）選擇、交叉、變異操作，產(chǎn)生子代（2.3）子代取代父代，形成新一代個(gè)體EndwhileEnd第十六頁(yè)，共十九頁(yè)，2022年，8月28日粗粒度并行算法在自然界中，物種的群體系由一些子群體構(gòu)成。在處理器比較少的情況下，可以將群體分為若干個(gè)子群體，每個(gè)子群體包含一些個(gè)體，每個(gè)群體分配一個(gè)處理器，讓它們互相獨(dú)立的并行執(zhí)行進(jìn)化，每經(jīng)過(guò)一定的間隔（即若干個(gè)進(jìn)化帶），就把最佳個(gè)體遷移到相鄰的子群體中。算法代碼：Begin(1)產(chǎn)生一個(gè)初始群體并將它劃分為p個(gè)子群體(2)for1topdo/*P表示處理器個(gè)數(shù)，也是子群體的個(gè)數(shù)

(2.1)初始化

(2.2)評(píng)估第一代子群體的適應(yīng)度

(2.3)whileconditionto (2.3.1)forJ=1toH(generations)do a、選擇父代

b、交叉操作

c、子代變異

d、子代取代父代形成新一代子群體

e、評(píng)估子代的適應(yīng)度

endfor (2.3.2)選擇要遷移出去的個(gè)體

(2.3.3)dostepaandbinparallel/*這里發(fā)送和接收進(jìn)程是并發(fā)執(zhí)行的

a、發(fā)送要遷出的個(gè)體

b、接手遷入的個(gè)體

endwhile endfor end第十七頁(yè)，共十九頁(yè)，2022年，8月28日細(xì)粒度并行算法如果并行系統(tǒng)中有足夠多的處理器，那么系統(tǒng)可以為每個(gè)個(gè)體分配一個(gè)處理器，讓它們相互獨(dú)立的并行執(zhí)行進(jìn)程，這樣就能獲得并行遺傳算法的最大可能的并發(fā)性。代碼：Begin(1)產(chǎn)生一個(gè)初始群體并將它分配到P=N個(gè)處理器上；(2)For=1toNdo whilerunningdo (2.1)