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

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

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

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

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

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

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

(2.1)初始化

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

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

b、交叉操作

c、子代變異

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

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

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

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

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

b、接手遷入的個體

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