并行遺傳算法.ppt

1、并行遺傳算法,并行實驗室,遺傳的基本概念,遺傳算法（genetic algorithms,簡稱GA）是J.Holland于1975年受生物進化論的啟發(fā)而提出來的。GA是基于“適者生存”的一種高度并行、隨機和自適應(yīng)的優(yōu)化算法，它將問題的求解表示成“染色體”適者生存的過程，通過“染色體”群的一代代不斷進化，包括復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個體，從而求得問題的最優(yōu)解或滿意解。 優(yōu)點：隱含并行性 全局解空間搜索能力,遺傳與算法的對應(yīng),遺傳算法通過模擬自然界優(yōu)勝劣汰的進化現(xiàn)象，將搜索空間映射為遺傳空間，把可能的解編碼成一個向量（即染色體），向量的每個元素稱為基因，然后通過不斷計算各

2、染色體的適應(yīng)度值，選擇最好的染色體，獲得最優(yōu)解。,遺傳算法的基本步驟,確定決策變量及各種約束條件，即確定個體的表現(xiàn)型X和問題的解空間； 建立優(yōu)化模型，即確定目標函數(shù)的類型； 確定表示可行解的染色體編碼方案，即確定出個體的基因型X及遺傳算法的搜索空間； 確定編碼方法，即確定出由基因型X到個體表現(xiàn)型X的對應(yīng)關(guān)系或轉(zhuǎn)換方法； 確定個體適應(yīng)度的量化評價方法，即確定由目標函數(shù)值f(x)到個體適應(yīng)度F(x)的變換規(guī)則； 設(shè)計遺傳算子，即確定出選擇、交叉、變異的具體操作方法； 確定遺傳算法的有關(guān)運行參數(shù)，即確定遺傳算法的Pc,Pm等參數(shù)。,特點,遺傳算法以決策變量的編碼作為運算對象； 遺傳算法直接以目標函數(shù)

3、值作為搜索信息，它使用由目標函數(shù)值變換得到的適應(yīng)度函數(shù)值作為下一步搜索方向和范圍的判斷標準； 遺傳算法同時使用多個搜索點的搜索信息。它是從很多個體所組成的一個初始群體開始最優(yōu)解的搜索，而不是從單一的個體開始搜索。這樣可以避免一些不必要的搜索，其實內(nèi)在包含了算法的隱含并行性； 遺傳算法屬于非確定性的概率算法。正是由于它的不確定和概率性，導(dǎo)致算法找到的解只能夠是相對最優(yōu)解。,遺傳算法的實現(xiàn),確定問題的編碼方案 確定適配值函數(shù) 設(shè)計遺傳算子 算法參數(shù)選擇，主要包括種群數(shù)目、交叉與變異概率、進化代數(shù)等。 確定算法的終止條件。,編碼,編碼就是將問題的解用一種計算機可以識別的碼來表示，將問題空間的狀態(tài)空間

4、與GA的碼空間相對應(yīng)。GA的優(yōu)化過程是在一定編碼機制對應(yīng)的碼空間上進行的，因此編碼的選擇是影響算法性能與效率的重要因素。 編碼方式：二進制編碼方法 格雷碼編碼方法 浮點數(shù)編碼方法 通常所采用的編碼方式是二進制編碼。,二進制編碼方法,二進制編碼所構(gòu)成的個體基因是一個經(jīng)過編碼的符號串，二進制編碼符號串的長度和問題的精度有關(guān)。假設(shè)問題的參數(shù)取值范圍是Umin,Umax,使用長度為L的二進制編碼符號串表示該參數(shù)，則能產(chǎn)生2L種不同的編碼。 若參數(shù)的編碼的對應(yīng)關(guān)系如下： 000000000000=0Umin 000000000001=1 Umin+ 111111111111= 2L-1 Umax 二進制

5、的編碼精度為： 設(shè)每個個體的編碼為： 對應(yīng)的解碼公式：,適配值函數(shù),適配值函數(shù)用于對個體進行評價，是優(yōu)化過程發(fā)展的依據(jù)。 在簡單問題的優(yōu)化時，通?？梢詫⒛繕撕瘮?shù)直接變換成適配值函數(shù)，譬如將個體X的適配值f(x)定義為M-c(x)或eac(x),其中M為一足夠大正數(shù)，c(x)為個體的目標值，a0。在復(fù)雜問題的優(yōu)化時，往往需要構(gòu)造合適的評價函數(shù)，適應(yīng)GA進行優(yōu)化。,算法參數(shù)選擇,種群的數(shù)目：影響算法優(yōu)化性能和效率。種群太小導(dǎo)致采樣點數(shù)目不足，算法性能低；而種群數(shù)目太大又會增加計算量，導(dǎo)致收斂時間過長。所以在設(shè)計算法時應(yīng)該針對具體問題選擇適宜的種群數(shù)目； 交叉概率：用于控制交叉操作的頻率。概率太大，

6、種群中串的更新很快，會使高適配值的個體很快被破壞掉；概率太小，交叉操作很少進行，會使搜索停止不前； 變異概率：增加種群多樣性?；诙M制編碼的GA中，一個非常小的變異率就會改變整個種群的基因。變異概率必須取一個適當(dāng)?shù)闹?，太小不會產(chǎn)生新個體，太大又會使GA完全的隨機搜索； 總結(jié)：遺傳算法參數(shù)的選擇是非常重要的，同時也非常復(fù)雜，參數(shù)選取需要按照問題的實際大小來進行選擇。,選擇算子選取,選擇的定義：從群體中選擇優(yōu)秀的個體，淘汰劣質(zhì)個體的操作。 選擇算子的作用：將優(yōu)化的解直接遺傳到下一代，或通過配對交叉的方式遺傳到下一代。 常用選擇算子：適應(yīng)度比例法，也叫賭輪法或蒙特卡羅法。 選擇執(zhí)行過程： 1)計算

7、出群體中所有個體適應(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)度越高，被選中的概率越高。,算法終止條件,在實際中算法是不允許無止境的發(fā)展下去的，而且對通常問題的最優(yōu)解具有不確定性，因此需要一個條件來終止算法的進程。目前最常用的終止條件是事先給定一個最大進化步數(shù)，或者判斷最佳優(yōu)化值是否連續(xù)且經(jīng)過若干步后都沒有變化等。,隱含并行性,設(shè)為一小正數(shù)，L (l-1

8、)+1,N=2l,2，則遺傳算法一次處理的存活概率不小于1- 且定義長度不大于L的模式數(shù)位O（N3）. 遺傳算法表面上僅對每代的N個個體作處理，但實際上并行處理了大約O（N3）個模式，并且無額外的存儲，這正是遺傳算法具有高校搜索能力的原因，這就是遺傳算法的隱含并行。,并行遺傳算法,傳統(tǒng)的遺傳算法出現(xiàn)的問題： 局部搜索性能較差，對某些分布變化緩慢，面對大型計算問題速度難以達到要求 并行遺傳算法提出： 在遺傳算法并行運算的基礎(chǔ)上，通過多種群并行進化和引入遷移算子進行進行種群之間的信息交流，實現(xiàn)多種群的協(xié)同進化。通過人工選擇系數(shù)對每個種群最優(yōu)化個體保存，通過對協(xié)調(diào)種群間的信息交換策略得到最好的進化效

9、果。 遺傳算法的并行化實現(xiàn)就是將進化過程劃分到不同的計算節(jié)點上，進行分布式進化，并通過一定的種群間信息交換策略實現(xiàn)優(yōu)良基因的轉(zhuǎ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é)點上群體進化的局部特性，有效回避了普通遺傳算

10、法早熟現(xiàn)象。 目前比較常用的類型是分解型并行方法，按照不同的組織結(jié)構(gòu)，它又可以分為下面三種不同的類型： 主從式并行計算 粗粒度并行計算 細粒度并行計算,主從式并行計算,在這種并行方式中，一個主過程調(diào)節(jié)若干個仆過程。其中主過程控制選擇、交叉和變異，仆過程僅執(zhí)行適配值的計算。 缺點：1、各仆過程計算適應(yīng)度值的時間存在明顯差異時，將會照成整個系統(tǒng)長時間的等待；2、整個系統(tǒng)可靠性較差，對主過程狀況的依賴性較大。 偽代碼： Begin (1)產(chǎn)生一個初始群體 (2)while running do (2.1)for =1 to s do 計算個體i的適應(yīng)度值(并行部分) （2.2）選擇、交叉、變異操作，

11、產(chǎn)生子代 （2.3）子代取代父代，形成新一代個體 End while End,粗粒度并行算法,在自然界中，物種的群體系由一些子群體構(gòu)成。在處理器比較少的情況下，可以將群體分為若干個子群體，每個子群體包含一些個體，每個群體分配一個處理器，讓它們互相獨立的并行執(zhí)行進化，每經(jīng)過一定的間隔（即若干個進化帶），就把最佳個體遷移到相鄰的子群體中。 算法代碼： Begin (1)產(chǎn)生一個初始群體并將它劃分為p個子群體 (2)for 1 to p do /*P表示處理器個數(shù)，也是子群體的個數(shù) (2.1)初始化 (2.2)評估第一代子群體的適應(yīng)度 (2.3)while condition to (2.3.1)f

12、or J=1 to H(generations)do a、選擇父代 b、交叉操作 c、子代變異 d、子代取代父代形成新一代子群體 e、評估子代的適應(yīng)度 end for (2.3.2)選擇要遷移出去的個體 (2.3.3)do step a and b in parallel /*這里發(fā)送和接收進程是并發(fā)執(zhí)行的 a、發(fā)送要遷出的個體 b、接手遷入的個體 end while end for end,細粒度并行算法,如果并行系統(tǒng)中有足夠多的處理器，那么系統(tǒng)可以為每個個體分配一個處理器，讓它們相互獨立的并行執(zhí)行進程，這樣就能獲得并行遺傳算法的最大可能的并發(fā)性。 代碼： Begin (1)產(chǎn)生一個初始群體并將它分配到P=N個處理器上； (2)For=1 to