遺傳算法的定義、設(shè)計、流程和實際應(yīng)用

1、遺傳算法的定義、設(shè)計、流程和實際應(yīng)用1了解遺傳算法的研究背景，熟練掌握遺傳算法的思想來源和設(shè)計流程，掌握遺傳算法的參數(shù)設(shè)計和影響作用，并能理解遺傳算法的改進和實際應(yīng)用。1自然選擇和優(yōu)勝劣汰的進化規(guī)律。2遺傳信息的重組3 遺傳算法是模仿生物遺傳學(xué) 和自然選擇機理，通過人工方式構(gòu)造的一類優(yōu)化搜索算法，是對生物進化過程進行的一種數(shù)學(xué)仿真，是進化計算的一種重要的形式。遺傳算法與傳統(tǒng)數(shù)學(xué)模型截然不同，它為那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題找出了一個解決方法。同時，遺傳算法借鑒了生物科學(xué)中的某些知識，從而體現(xiàn)了人工智能這一交叉學(xué)科的特點?；籼m德(Holland) 于1975年在他的著作“Adaptation

2、in Natural and Artificial Systems中首次提出遺傳算法。遺傳算法簡介4遺傳算法簡介5遺傳算法研究內(nèi)容6遺傳算法研究內(nèi)容7遺傳算法原理遺傳算法通過模擬自然界中生物的遺傳進化過程，對優(yōu)化問題的最優(yōu)解進行搜索。算法維護一個代表問題潛在解的群體， 通過對群體的進化，搜索問題的最優(yōu)解，算法中引入了類似自然進化過程中的選擇、交叉、變異等算子。遺傳算法搜索全局最優(yōu)解的過程是一個不斷迭代的過程(每一次迭代相當于生物進化中的一次循環(huán)) ，直到滿足算法的終止條件為止。8遺傳算法原理在遺傳算法中，問題的每個有效解被稱為一個“染色體 (chromosome)” ，也稱為“串”，對應(yīng)于群體

3、中的每個生物個體( individual） 。 染色體的具體形式是一個使用特定編碼方式生成的編碼串，編碼串中的每一個編碼單元稱為基因(gene) 遺傳算法通過比較適應(yīng)值(fitness value) 區(qū)分染色體的優(yōu)劣，適應(yīng)值越大的染色體越優(yōu)秀。 評估函數(shù)( evaluation function) 用來計算并確定染色體對應(yīng)的適應(yīng)值。9遺傳算法原理選擇算子(selection) 按照一定的規(guī)則對群體的染色體進行選擇，得到父代種群。一般情況下，越優(yōu)秀的染色體被選中的次數(shù)越多。交叉算子(crossover) 作用于每兩個成功交配的父代染色體，染色體交換各自的部分基因，產(chǎn)生兩個子代染色體。子代染色體取

4、代父代染色體進入新種群，而沒有交配的染色體則直接進入新種群。變異算子(mutation) 使新種群進行小概率的變異。染色體發(fā)生變異的基因改變數(shù)值，得到新的染色體。經(jīng)過變異的新種群替代原有群體進入下一次進化。10遺傳算法原理11 遺傳算法類似于自然進化，通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題 。遺傳算法對求解問題的本身一無所知，它所需要的僅僅是對算法所產(chǎn)生的每個染色體進行評價，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機會。 在遺傳算法中，通過隨機方式產(chǎn)生若干個所求解問題的數(shù)字編碼，即染色體，形成初始種群；通過適應(yīng)度函數(shù)給每個個體一個數(shù)值評價，淘汰低適應(yīng)度的個體，選擇高適

5、應(yīng)度的個體參加遺傳操作，經(jīng)過遺傳操作后的個體集合形成下一代新的種群。再對這個新種群進行下一輪進化。這就是遺傳算法的基本原理。遺傳算法原理12遺傳算法原理Holland 給出了著名的模式定理 (Schema Theory) ，為遺傳算法提供了理論支持。模式(schema) 是指群體中編碼的某些位置具有相似結(jié)構(gòu)的染色體集合。 假設(shè)染色體的編碼是由 0 或 1 組成的二進制符號序列， 模式 01*0 則表示以 01 開頭且以 0 結(jié)尾的編碼串對應(yīng)的染色體的集合，即 010000， 010010， 010100， 010110，011000 ， 011010 ，0 11100 ， 011110 。13

6、遺傳算法原理模式的階(schema order) : 模式中具有確定取值的基因個數(shù)。 如模式 01*0 的階為 3模式的定義長度(schemad defining length) 是指模式中第一個具有確定取值的基因到最后一個具有確定取值的基因的距離， 例如模式 01*0的定義長度為5 而模式*1*的定義長度為 014遺傳算法原理Holland 的模式定理提出，遺傳算法的實質(zhì)是通過選擇、交叉、變異的遺傳算子對模式進行搜索。低階、定義長度較小且平均適應(yīng)值高于群體平均適應(yīng)值的模式在群體中的比例將呈指數(shù)級增長。隨著進化的不斷進行，較優(yōu)染色體的個數(shù)將快速增加。模式定理證明了遺傳算法尋求全局最優(yōu)解的可能性

7、，但不能保證算法一定能找到全局最優(yōu)解。15遺傳算法原理積木塊假設(shè) (Building Block Hypothesi s) ，對模式定理做了補充，說明遺傳算法具有能夠找到全局最優(yōu)解的能力。積木塊(building block) 是指低階、定義長度較小且平均適應(yīng)值高于群體平均適應(yīng)值的模式。積木塊假設(shè)認為在遺傳算法運行過程中，積木塊在遺傳算子的影響下能夠相互結(jié)合，產(chǎn)生新的更加優(yōu)秀的積木塊，最終接近全局最優(yōu)解。16遺傳算法的流程 GA的算法在解空間中取一群點，作為遺傳開始的第一代。每個點用一個編碼數(shù)字串表示，其優(yōu)劣程度用一個目標函數(shù)適應(yīng)度函數(shù)(fitness function)來衡量。染色體的編碼;

8、群體的初始化;適應(yīng)值評價;種群選擇;種群交叉;種群變異;算法流程17遺傳算法的流程 1. 染色體的編碼 許多應(yīng)用問題的結(jié)構(gòu)很復(fù)雜，我們希望找到一種既簡單又不影響算法性能的編碼方式。將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫做編碼；相反的，將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫做解碼或譯碼。 關(guān)于確定遺傳算法染色體編碼方式的兩條指導(dǎo)原則：有意義積木塊編碼原則和最小字符集編碼原則，倡導(dǎo)算法使用的編碼方案應(yīng)易于產(chǎn)生低階且定義長度較短的模式，在能夠自然描述所求問題的前提下使用最小編碼字符集 18遺傳算法的流程 1. 二進制編碼方法 二進制編碼方法產(chǎn)生的染色體是一個二進制符號序列，染色體的每一個基因只

9、能取值 0 或 1 。 假定問題定義的有效解取值空間為 Umin，Umax , 其中 D為有效解的變量維數(shù)，使用 L 位二進制符號串表示解的一維變量 ，則我們可以得到如表 4. 2 所示的編碼方式:19 假設(shè)Umin，Umax 為0, 63 ，采用 6 位二進制符號串進行編碼，則某個二進制符號串 010101 代表了數(shù)值 21 L 位二進制編碼的精度為: 二進制編碼的最大缺點是長度較大，當要求采用較高的精度或表示較大范圍的數(shù)時，必須通過增加 L 來達到要求。20浮點數(shù)編碼方法中，每個染色體用某一范圍內(nèi)的一個浮點數(shù)來表示，染色體的編碼長度等于問題定義的解的變量個數(shù)，染色體的每一個基因等于解的每一

10、維變量。 待求解問題的一個有效解為 則該解對應(yīng)的染色體編碼為因為這種編碼方法使用的是變量的真實值，所以浮點數(shù)編碼方法也叫做真值編碼方法。對于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題，用浮點數(shù)編碼來表示個體時將會有一些益處。 2. 浮點數(shù)編碼方法21格雷碼(Gray)是將二進制編碼通過以下變換得到的碼：設(shè)二進碼(1 2 n)對應(yīng)的格雷碼為(r1 r2 rn),則從二進碼到格雷碼的轉(zhuǎn)換為：從格雷碼到二進碼的轉(zhuǎn)換為: 其連續(xù)的兩個整數(shù)所對應(yīng)的編碼值之間只有一個碼位是不相同的，其余碼位都完全相同。例如十進制數(shù)7和8的二進制編碼分別為0111和1000，而格雷碼分別為0100和1100 。22練習(xí)：分別寫

11、出十進制數(shù)17和40的二進制編碼和格雷碼23 符號編碼方法是指個體染色體編碼串中的基因值取自一個無數(shù)值含義而只有代碼含義的符號集。這個符號集可以是一個字母表，如A,B,C,D,；也可以是一個數(shù)字序號表，如1,2,3,4,5,；還可以是一個代碼表，如x1,x2,x3,x4,x5,，等等。遺傳算法的流程 2. 群體的初始化遺傳算法在給定的初始群體中進行迭代搜索采用生成隨機數(shù)的方法，對染色體的每一維變量進行初始化賦值初始化染色體時必須滿足優(yōu)化問題對有效解的定義。在算法的開始得到一個平均適應(yīng)值相對較高的初始群體再進行進化來提高算法的求解性能243. 適應(yīng)值評價：用于評估各個染色體的適應(yīng)值，區(qū)分優(yōu)劣為了

12、體現(xiàn)染色體的適應(yīng)能力，引入了對每一個染色體都能進行度量的函數(shù)，叫做適應(yīng)度函數(shù) (fitness function)。通過計算適應(yīng)度函數(shù)值 來決定染色體的優(yōu)劣程度，它體現(xiàn)了自然進化中的優(yōu)勝劣汰原則。在遺傳算法中，規(guī)定適應(yīng)值越大的染色體越優(yōu)。適應(yīng)度函數(shù)要求能有效地反映每一個染色體的適應(yīng)能力。若一個染色體與問題的最優(yōu)解染色體之間的差距較小，則對應(yīng)的適應(yīng)度函數(shù)值就會較大。25評估函數(shù)常常根據(jù)問題的優(yōu)化目標 來確定，例如求解函數(shù)優(yōu)化問題時，問題定義的目標函數(shù)可以作為評估函數(shù)的原型。對于一些求解最大值的數(shù)值優(yōu)化問題，我們可以直接套用問題定義的函數(shù)表達式。但是對于其他優(yōu)化問題，問題定義的目標函數(shù)表達式必須經(jīng)

13、過一定的變換。例如TSP的目標是路徑總長度為最短，路徑總長度變換后就可作為TSP問題的適應(yīng)度函數(shù)： d(j, j+1)表示兩城市間的距離(路徑長度)。26 遺傳操作：遺傳算法的遺傳操作主要有三種：選擇(selection)、交叉(crossover)、變異(mutation)。 4. 選擇算子： 選擇操作也叫做復(fù)制(reproduction)操作，根據(jù)個體的適應(yīng)度函數(shù)值所度量的優(yōu)劣程度決定它在下一代是被淘汰還是被遺傳。 一般地，適應(yīng)度較大(優(yōu)良)的個體有較大的存在機會，而適應(yīng)度較小(低劣)的個體繼續(xù)存在的機會也較小。簡單遺傳算法采用賭輪選擇機制.27根據(jù)每個染色體的適應(yīng)值得到群體中所有染色體的

14、適應(yīng)值總和。計算每個染色體適應(yīng)值與群體適應(yīng)值總和的比 Pi 假設(shè)一個具有 N 個扇區(qū)的輪盤，每個扇區(qū)對應(yīng)群體中的一個染色體，扇區(qū)的大小與對應(yīng)染色體的 Pi 值成正比。2829 5. 交叉算子：交叉操作的簡單方式是: 按交叉概率Pc 選擇出兩個父代個體P1和P2，將兩者的部分基因（碼值）進行交換。交叉概率的Pc 一般取值為：之間。隨機數(shù) Random(0, 1) 小于 Pc ，則表示該染色體可進行交叉操作隨機產(chǎn)生一個有效的交配位置，父代染色體交換位于該交配位置后的所有基因30 編碼長度為8，產(chǎn)生一個在17之間的隨機數(shù)k，假如現(xiàn)在產(chǎn)生的是5, 將P1和P2的后3位基因交換：P1的高5位與P2的低三

15、位組成數(shù)串10001001, 這就是P1和P2的一個子代個體Q1 ；P2的高5位與P1的低3位組成數(shù)串11011110, 這就是P1和P2的另一個子代Q2個體。交換過程如圖所示31單點交叉運算的偽代碼:procedure: One-cut Point Crossoverinput: pC, parent Pk, k=1, 2, ., popSizeoutput: offspring Ckbegin for k= 1 to popSize / popSize: population size if pc random 0, 1 / pC: the probability of crossover

16、 i 0; j 0; repeat i random 1, popSize; j random 1, popSize; until (ij ) p random 2, L-1;/ p: the cut position, L: the length of chromosome Ci Pi 1: p-1 / Pj p: L; Cj Pj 1: p-1 / Pi p: L ; end end output offspring Ck;end326. 變異算子：變異操作的簡單方式就是改變碼串中某個位置上的數(shù)碼變異概率的Pm 一般取值為：之間。隨機數(shù) Random(0, 1) 小于 Pm ，則表示該染色

17、體可進行變異操作隨機產(chǎn)生一個有效的變異位置，染色體上位于該位置的基因發(fā)生改變33二進制編碼表示的每個位置的數(shù)碼只有0和1兩種可能，二進制編碼的簡單變異操作是將0與1互換：0變異為1，1變異為0。設(shè)有如下二進制編碼：碼長為8，隨機產(chǎn)生一個18之間的數(shù)k，假如現(xiàn)在k=5，對第5位(從右到左)進行變異操作，將原來的0變?yōu)?，得到如下數(shù)碼串：浮點數(shù)編碼形式的染色體若某基因發(fā)生變異，則可采用隨機數(shù)方法隨機產(chǎn)生一個滿足問題定義的數(shù)值 取代該基因現(xiàn)有的值。34procedure: Mutationinput: pM, parent Pk, k=1, 2, ., popSizeoutput: offsprin

18、g Ckbegin for k= 1 to popSize / popSize: population size for j =1 to L / L: the length of chromosome if pM random 0, 1 / pM: the probability of mutation Pk j =1- Pk j ; / p: the cut position Ck Pk 1: j-1 / Pk j / Pk j+1: L ; end end end output offspring Ck ;end變異運算的偽代碼:357. 算法流程：一般遺傳算法的主要步驟如下Step 1

19、初始化規(guī)模為 N 的群體，其中染色體每個基因的值采用隨機數(shù)產(chǎn)生器生成并滿足問題定義的范圍。當前進化代數(shù) Generation = 0 。Step 2 用評估函數(shù)對群體中所有染色體進行評價，分別計算每個染色體的適應(yīng)值, 保存適應(yīng)值最大的染色體 BestStep 3 采用輪盤賭選擇運算對群體的染色體進行選擇操作，產(chǎn)生規(guī)模同樣為 N 的種群。Step 4 按照概率 Pc 從種群中選擇染色體進行交叉運算。兩兩父代染色體交換部分基因，產(chǎn)生兩個新的子代染色體，子代染色體取代父代染色體進入新種群。沒有進行交叉的染色體直接復(fù)制進入新種群。36Step 5 按照概率 Pm對新種群中染色體的基因進行變異操作。發(fā)生

20、變異的基因數(shù)值發(fā)生改變。變異后的染色體取代原有染色體進入新群體，未發(fā)生變異的染色體直接進入新群體。Step 6 變異后的新群體取代原有群體，重新計算群體中各個染色體的適應(yīng)值。倘若群體的最大適應(yīng)值大于 Best 的適應(yīng)值， 則以該最大適應(yīng)值對應(yīng)的染色體替代 Best ，即更新最大適應(yīng)值大于 Best 。Step 7 當前進化代數(shù) Generation 加 l 。 如果 Generation 超過規(guī)定的最大進化代數(shù)或 Best 達到規(guī)定的誤差要求，算法結(jié)束 ，Best 可表示問題的一個解; 否則返回 Step 33738輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。算法的停止條件最簡單的

21、有如下兩種： 完成了預(yù)先給定的進化代數(shù)則停止； 種群中的最優(yōu)個體在連續(xù)若干代沒有改進或平均適應(yīng)度在連續(xù)若干代基本沒有改進時停止。39Initialsolutionsstart1100101010101110111000110110011100110001encodingchromosome110010101010111011101100101110101110101000110110010011001001crossovermutation110010111010111010100011001001solutions candidatesdecodingfitness computatione

22、valuationroulette wheelselectiontermination condition?YNbest solutionstop newpopulationGen, M. & R. Cheng: Genetic Algorithms and Engineering Design, John Wiley, New York, 1997.offspringoffspringt 0 P(t)CC(t)CM(t)P(t) + C(t)40遺傳算法的特點遺傳算法是一種基于空間搜索的算法，它通過自然選擇、遺傳、變異等操作以及達爾文的適者生存的理論，模擬自然進化過程來尋找所求問題的答案。因

23、此，遺傳算法的求解過程也可看做是最優(yōu)化過程。遺傳算法并不能保證所得到的是最佳答案，但通過一定的方法，可以將誤差控制在容許的范圍內(nèi)。遺傳算法具有以下特點： (1)遺傳算法是對參數(shù)集合的編碼而非針對參數(shù)本身進行進化； (2)遺傳算法是從問題解的編碼組開始而非從單個解開始搜索；41 (3)遺傳算法利用目標函數(shù)的適應(yīng)度值這一信息而非利用導(dǎo)數(shù)或其他輔助信息來指導(dǎo)搜索； (4)遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進行隨機操作。 遺傳算法利用簡單的編碼技術(shù)和繁殖機制來表現(xiàn)復(fù)雜的現(xiàn)象，從而解決非常困難的問題。它不受搜索空間的限制性假設(shè)的約束，不必要求諸如連續(xù)性，導(dǎo)數(shù)存在和單峰等假設(shè)，能從離散

24、的、多極值的、含有噪音的高維問題中以很大的概率找到全局最優(yōu)解。由于它固有的并行性，遺傳算法非常適用于大規(guī)模并行計算，已在優(yōu)化、機器學(xué)習(xí)和并行處理等領(lǐng)域得到了越來越廣泛的應(yīng)用。424445464748495051 Example of Genetic Algorithm for Unconstrained Numerical Optimization (Michalewicz, 1996)51遺傳算法的收斂性作為一種搜索算法，遺傳算法通過對編碼、適應(yīng)度函數(shù)、選擇、交叉和變異等操作的正確設(shè)計和適當運行，能夠?qū)崿F(xiàn)兼顧全局搜索和局部搜索 的所謂均衡搜索，實現(xiàn)原理如圖所示。遺傳算法雖然能夠?qū)崿F(xiàn)均衡搜索，

25、并且可以對許多復(fù)雜問題求得滿意解。但是，遺傳算法的全局優(yōu)化收斂性的理論分析尚未完全解決，標準遺傳算法并不保證全局最優(yōu)收斂，而只能在一定約束條件下，實現(xiàn)全局最優(yōu)收斂52 遺傳算法收效性的定義 遺傳算法是一種隨機搜索算法，可以從不同的角度定義它的收斂性。 (1) 漸進收斂 與其他一些隨機搜索算法(如模擬退火算法)的不同之處在于，遺傳算法維持了一個具有一定數(shù)目個體的種群。 所以，在定義算法收斂性時就存在兩種思路：一種是針對整個種群進行定義，另一種是針對個體進行定義。53 米哈萊威茲(Michalewicz)給出了針對整個種群的一種漸進收斂的定義，將所有可能的種群所組成的集合視為一個狀態(tài)空間X，算法在

26、第 t 代 (t 時刻) 的種群為 xt 于是，可對算法的收斂性定義如下： 若算法在 t 時刻的種群滿足： Lim xt = x0，x0X 則稱算法收斂到x0。 經(jīng)典的遺傳算法由于存在隨機性，而不具有漸近收斂的性質(zhì)。 54 (2) 概率收斂 由于遺傳算法具有隨機性，而且在利用遺傳算法求解問題時，往往并不知道適應(yīng)度函數(shù)的最大值究竟是多少，因此，當最優(yōu)個體出現(xiàn)時，算法仍有可能繼續(xù)進行。 但是在實際應(yīng)用中，總是希望算法收斂時能夠得到最優(yōu)解。因此，在定義其收斂性時應(yīng)當考察在隨機因素作用下算法收斂到最優(yōu)解的能力。魯?shù)婪?Rudolph)給出了一種針對個體的收斂性定義。55 設(shè) Zt 為 t 時刻種群中所

27、包含的個體的適應(yīng)度的最大值，f*為適應(yīng)度函數(shù) f(x) 在所有可能的個體所組成的集合X中所取的最大值。若 Zt 滿足： Lim P Zt=f* = 1 則稱算法收斂到最優(yōu)解。 魯?shù)婪蛲ㄟ^馬爾可夫(Markov)鏈方法證明，在這個定義下，經(jīng)典遺傳算法不會收斂到最優(yōu)解。但是若在遺傳算法中保留每一代的最佳個體，則算法將收斂到最優(yōu)解。56 在遺傳算法的處理過程中每個環(huán)節(jié)都有可能導(dǎo)入產(chǎn)生未成熟收斂的因素，具體表現(xiàn)為：在進化初始階段，生成了具有較高適應(yīng)度的個體X.在基于適應(yīng)度比例的選擇下，其他個體被淘汰，大部分個體與X一致。相同的兩個個體實行交叉，從而未能生成新個體。通過變異或逆轉(zhuǎn)所生成的個體適應(yīng)度高但數(shù)

28、量少，所以被淘汰的概率很大。群體中大部分個體都處于與X一致的狀態(tài)。 (3) 未成熟收斂 未成熟收斂是遺傳算法中不可忽視的現(xiàn)象，它主要表現(xiàn)在以下兩個方面：群體中所有的個體都陷于同一極值而停止進化；接近最優(yōu)解的個體總是被淘汰，進化過程不收斂57 針對上述情況，需要在編碼、適應(yīng)度函數(shù)和遺傳操作等設(shè)計中考慮抑制未成熟收斂的對策。這些對策包括：(1)提高變異概率。在進化初始階段，它可以加強遺傳算法的隨機搜索能力。(2)調(diào)整選擇概率。可以把選擇概率本身也作為個體來進行優(yōu)化，這就是所謂元遺傳算法(meta GA)。(3)合適定標。對適應(yīng)度函數(shù)定標。58 (4)維持群體中個體的多樣性 增加群體規(guī)模，但要考慮計

29、算量增加的因素； 實施局部化，把群體分割成若干子群體，每個子群體獨立地進行選擇操作，這樣可使因出現(xiàn)不適當個體而產(chǎn)生未成熟收斂的現(xiàn)象局部化； 實施單一化，把相同個體單一化，即不允許群體中有若干個相同個體出現(xiàn)； 增大配對個體距離，配對選擇一般是隨機進行的，其中缺少對個體間相似度的判斷，因此有可能使交叉結(jié)果未能產(chǎn)生新個體。59 群體規(guī)模 N 影響算法的搜索能力和運行效率。若 N 設(shè)置較大，一次進化所覆蓋的模式較多，可以保證群體的多樣性，從而提高算法的搜索能力，但是由于群體中染色體的個數(shù)較多，勢必增加算法的計算量，降低算法的運行效率。若 N 設(shè)置較小，雖然降低了計算量，但是同時降低了每次進化中群體包含

30、更多較好染色體的能力。N 的設(shè)置一般為 20100 。遺傳算法的參數(shù)設(shè)置60 染色體的長度 L影響算法的計算量和交叉變異操作的效果。L 的設(shè)置跟優(yōu)化問題密切相關(guān)，一般由問題定義的解的形式和選擇的編碼方法決定。對于二進制編碼方法，染色體的長度 L 根據(jù)解的取值范圍和規(guī)定精度要求選擇大小。對于浮點數(shù)編碼方法，染色體的長度 L 跟問題定義的解空間維數(shù) D 相同。除了染色體長度一定的編碼方法，Goldberg 等人還提出了一種變長度染色體遺傳算法 Messy GA ，其染色體的長度并不是固定的。61 基因的取值范圍 R R 視采用的染色體編碼方案而定。對于二進制編碼方法 ， R= 0 ，1 對于浮點數(shù)

31、編碼方法 ， R 與優(yōu)化問題定義的解每一維變量的取值范圍相同 。62交叉概率 Pc 決定了進化過程中，種群參加交叉運算的染色體的平均數(shù)目 Pc N。Pc的取值范圍一般為 0.40. 99 也可采用自適應(yīng)的方法調(diào)整算法運行過程中的 Pc 值63變異概率 Pm 增加群體進化的多樣性，決定了進化過程中群體發(fā)生變異的基因平均個數(shù)。Pm的值不宜過大。 因為變異對己找到的較優(yōu)解具有一定的破壞作用，如果Pm 的值太大，可能會導(dǎo)致算法目前所處的較好的搜索狀態(tài)倒退回原來較差的情況。Pm的取值一般為 0. 0010.1 也可采用自適應(yīng)的方法調(diào)整算法運行過程中的 Pm值64適應(yīng)值評價 影響算法對種群的選擇，恰當?shù)脑u

32、估函數(shù)應(yīng)該能夠?qū)θ旧w的優(yōu)劣做出合適的區(qū)分，保證選擇機制的有效性，從而提高群體的進化能力。評估函數(shù)的設(shè)置同優(yōu)化問題的求解目標有關(guān)。評估函數(shù)應(yīng)滿足較優(yōu)染色體的適應(yīng)值較大的規(guī)定。為了更好地提高選擇的效能，可以對評估函數(shù)做出一定的修正。目前主要的評估函數(shù)修正方法有:線性變換乘冪變換指數(shù)變換等65終止條件 決定算法何時停止運行，輸出找到的最優(yōu)解。采用何種終止條件，跟具體問題的應(yīng)用有關(guān)。可以使算法在達到最大進化代數(shù)時停止，最大進化代數(shù)一般可設(shè)置為 1001000 ，根據(jù)具體問題可對該建議值作相應(yīng)的修改。也可以通過考察找到的當前最優(yōu)解的情況來控制算法的停止。 例如，當目前進化過程算法找到的最優(yōu)解達到一定的

33、誤差要求，則算法可以停止。 誤差范圍的設(shè)置同樣跟具體的優(yōu)化問題相關(guān)?；蛘呤撬惴ㄔ诔掷m(xù)很長的一段進化時間內(nèi)所找到的最優(yōu)解沒有得到改善時 ， 算法可以停止。66混合遺傳算法 提高遺傳算法求解問題的能力。并行模擬退火遺傳算法(Parallel Simulated Annealing and Genetic Algorithms , PSAGA) 貪婪遺傳算法(Greedy Genetic Algorithm, GGA) 遺傳比率切割算法(Genetic Ratio-Cut Algorithm, GRCA) 遺傳爬山法(Geneti c Hillclimbing Algorithm ， GHA)引人局

34、部改善操作的混合遺傳算法免疫遺傳算法(lmmune Genetic Algorithm, IGA) 67并行遺傳算法算法從整體的流程上看仍然是串行的，但是算法運行過程中對每個染色體的處理卻是具有潛在的并行性。標準型并行方法(Standard Parallel Approach) 沒有根本改變遺傳算法整體上的串行計算結(jié)構(gòu)，只是在算法的某些操作中引入并行計算技術(shù)，這些操作包括適應(yīng)值計算、選擇操作、交叉操作、變異操作等分解型并行方法(Decomposition Parallel Approach) 將整個群體分解成幾個子群體，各個子群體分配到不同的計算資源上分別獨立地使用原有的遺傳算法進行進化6869分解型并行方法這種思想更貼近于自然界的生物進化系統(tǒng)。由于地域的限制，分布在不同地域的同一種生物的進化過程是不相同的，最終導(dǎo)致出現(xiàn)各種不同的物種。不同物種適應(yīng)環(huán)境的能力不盡相同。同樣地，獨立進行進化的各個子群體在各個階段的進化程度也是不同的。70分解型并行方法要求每隔一定的進化代數(shù)需要對各個子群體的進化結(jié)果信息進行交換。在分解型并行遺傳算法中，各個子群體的信息交換是一個重要的操作。 對于子群體之間如何交換進化信息，