遺傳進化算法課件

第5章遺傳進化算法基本概念、基本原理、基本算法第5章遺傳進化算法基本概念、基本原理、基本算法達爾文的生物進化論與遺傳算法遺傳—生命之特征或性狀的傳承染色體（chromosome)DNA(deoxyribonucleicacid)RNA(ribonucleicacid)

雙螺旋結(jié)構(gòu)基因(gene)

四進制編碼（A,T,C,G)

復制(reproduction)

交叉(crossover)

變異(mutation)達爾文的生物進化論與遺傳算法遺傳—生命之特征或性狀的傳承達爾文的生物進化論與遺傳算法進化—“物競天擇，優(yōu)勝劣汰，適者生存”遺傳信息（基因）寓于染色體，染色體決定生物特征，特征決定對環(huán)境的適應度。遺傳與進化之過程均發(fā)生在DNA之上。遺傳通過繁殖完成，繁殖由基因復制實現(xiàn)，復制的基本方式是交叉重組。交叉與變異產(chǎn)生新的物種，變異是物種進化的保證。適應度決定物種的存活，適應性強者遺傳機會更大。競爭是物種進化的促進劑。有競爭就有選擇，自然選擇是進化的基本規(guī)律達爾文的生物進化論與遺傳算法進化—“物競天擇，優(yōu)勝劣遺傳進化算法的基本概念編碼、個體與種群(encoding,individualandpopulation)適應度函數(shù)(fitnessfunction)選擇算子(selectionoperator)交叉算子(crossoveroperator)變異算子(mutationoperator)遺傳進化算法的基本概念編碼、個體與種群(encoding,遺傳編碼(geneticencoding)二進制編碼灰度編碼可拼接/可分解編碼實數(shù)編碼可變精度實數(shù)編碼符號編碼混亂編碼混合編碼遺傳編碼(geneticencoding)二進制編碼編碼(encoding)與解碼(decoding)式中A所表示的有限字符串稱為優(yōu)化變量X的遺傳（染色體）編碼，記為

,A中的字符稱為基因，字符所有可能的取值稱為等位基因，L稱為編碼長度；X稱為A的解碼，記為。編碼的重要性：1）基因的排列決定遺傳操作的作用方式；

2）決定搜索的難度與復雜性；

3）決定問題求解的精度。編碼(encoding)與解碼(decoding)式中A所個體空間與種群空間一個問題可行解的遺傳編碼稱為個體，或者說一群染色體的組合稱為個體設表示等位基因，為給定的編碼長度，則所有基因可能排列成的編碼構(gòu)成整個個體空間對任何正整數(shù)m，乘積稱為m階種群空間，其中的元素稱為m階種群個體空間中的一群個體稱為一個種群個體空間與種群空間一個問題可行解的遺傳編碼稱為個體，或者說一與編碼相關(guān)的定義1）編碼格式e是從HL到的一個映射，且對任何，存在唯一與之對應的解碼；2）當且僅當任何唯一對應一個個體A，則稱編碼格式是正則的；3）如果一個L編碼和一個K編碼的拼接有意義且是一個L+K碼，則稱其為是可拼接的；反之則稱之為是可分解的

設個體空間為：其可行解空間為：與編碼相關(guān)的定義1）編碼格式e是從HL到的一二進制編碼二進制編碼：以字符0和1為等位基因的定長字符串編碼。對實數(shù)xi給定編碼精度，取mi

為滿足的最小整數(shù)，則mi

長的0-1字符串唯一對應實數(shù)xi

，定義為：設且二進制編碼二進制編碼：以字符0和1為等位基因的定長字符串編碼二進制編碼示例Xi的

二進制編碼個體：

0000000000000000000000000010.0009767…………00010001000101.088043811111111111118.0001497設

則mi=13，從中任選n個個體可構(gòu)成一個種群,任選m次就可構(gòu)成m個種群二進制編碼示例Xi的二進制編碼個體：設則mi=13二進制編碼的優(yōu)缺點優(yōu)點：二進制編碼簡明、通用、易于各種進化操作。缺點：不具備正則性，可能破壞可行解空間的拓撲連續(xù)性。

對于高維、連續(xù)優(yōu)化問題存在離散化誤差，高精度要求將產(chǎn)生很長的編碼；不便于表達反映所求問題的特定知識。例如:在整數(shù)集[0,10]中的數(shù)7和8最鄰近，但它們的二進制編碼0111和1000的海明距離為4，最遠.海明距離：兩染色體編碼所有相應位置中取不同數(shù)值的位置數(shù)二進制編碼的優(yōu)缺點優(yōu)點：二進制編碼簡明、通用、易于各種進化操灰度編碼假定已有二進制編碼：其修正（灰度）編碼：兩者相互轉(zhuǎn)換公式：即：其中表示異或運算，即：灰度編碼假定已有二進制編碼：二進制與灰度編碼轉(zhuǎn)換示例二進制編碼0111(7),1000(8),1011(11),1100(12),前兩個編碼的海明距離為4,后兩個編碼海明距離為3.其相應灰度編碼為0

0

11,1011,1001,1101,顯然前后兩個編碼的海明距離均為1,新編碼保持了原空間的連續(xù)性.其灰度變換計算:其逆變換計算:二進制與灰度編碼轉(zhuǎn)換示例二進制編碼0111(7),個基因，和分別表示第表示染色體，這里表示染色體的第個基因解空間的上限和下限。實數(shù)與二進制的混合編碼設個基因，和分別表示第表示染色體，這里表示染色體的第個基因解空采用混合編碼產(chǎn)生初始種群的算法如下：隨機產(chǎn)生一個隨機數(shù)，實數(shù)與二進制的混合編碼

；(2),重復N次，就產(chǎn)生一個染色體(3)重復步驟(1)、(2)M次，就產(chǎn)生一個包含M個染色體的初始種群。采用混合編碼產(chǎn)生初始種群的算法如下：實數(shù)與二進制的混合編碼；適應度函數(shù)(fitnessfunction)1）對應某種生物群體在給定環(huán)境下的適應性度量；2）優(yōu)化變量X對應生物群體中的個體；3）遺傳進化對應于實現(xiàn)該優(yōu)化過程的演化過程。

適應度函數(shù)是評價群體中個體好壞的標準，是模擬自然選擇的唯一依據(jù)。從而適應度函數(shù)選取的優(yōu)劣直接影響遺傳算法的收斂速度及能否找到最優(yōu)解。適應度函數(shù)(fitnessfunction)1）對應某種生適應度函數(shù)的設計原則早熟現(xiàn)象：遺傳算法運行初期階段，群體中或許會出現(xiàn)適應度極好的個體，最終這些個體可能會充斥整個群體，使用于產(chǎn)生新個體作用較大的交叉操作失去作用，從而使得群體的多樣性降低，遺傳算法提前收斂到某個局部最優(yōu)解。適應度函數(shù)的選取應盡量的避免早熟現(xiàn)象，即縮小適應度較高的個體與其他個體適應度之間的差異，限制其復制數(shù)量以維護群體的多樣性

適應度函數(shù)的設計原則早熟現(xiàn)象：遺傳算法運行初期階段，群體中或適應度函數(shù)的設計原則退化現(xiàn)象：遺傳算法運行后期階段，群體越來越集中，個體之間的差異減小，相互之間的競爭力也隨即減弱。這必然造成個體被選擇到下一代中的概率接近，使進化過程失去競爭力，退化為隨機選擇過程。適應度函數(shù)的選取應該克服這種退化現(xiàn)象，使算法在運行后期階段能夠擴大最佳個體適應度與其它個體適應度之間的差異，提高個體之間的競爭性。適應度函數(shù)的設計原則退化現(xiàn)象：遺傳算法運行后期階段，群體越來適應度函數(shù)的常用變換線性尺度變換乘冪尺度變換指數(shù)尺度變換適應度函數(shù)的常用變換線性尺度變換適應度函數(shù)設計舉例

設計一個分段的非線性變換的適應度函數(shù)這里,表示變換過后的適應度函數(shù)；表示種群的適應度比例值、、和均為常數(shù)。其中的主要作用一方面用于保證恒為正，另一方面調(diào)控不同個體被選擇的概率；為冪指數(shù)，可在1-1.2之間選擇；、為0-1的實數(shù)，是不同函數(shù)的切換條件。適應度函數(shù)設計舉例設計一個分段的非線性變換的適應度函數(shù)選擇算子(selectionoperator)模擬“優(yōu)勝劣汰、適者生存”自然進化原理決定父代種群中個體以多大可能被選中遺傳到下一代的進化操作。選擇原則：1）依據(jù)適應度評價；

2）選擇最優(yōu)個體；

3）避免無效搜索；

4）快速搜索到最優(yōu)解。定義：選擇算子S是一個隨機映射，它滿足：

選擇算子(selectionoperator)模擬“優(yōu)勝選擇算子(selectionoperator)比例選擇（輪盤賭選擇）變尺度比例選擇杰出者選擇期望生存數(shù)選擇確定式采樣選擇排序選擇Boltzmann局部退火選擇種群偏差度選擇排除算子選擇基于正交表的選擇選擇算子(selectionoperator)比例選擇（比例選擇比例選擇輪盤賭選擇（RouletteWheelSelection）

每一個染色體適應度函數(shù)值決定其在輪盤上面積的大小。此面積大小與輪盤總面積的比率就染色體被挑選至下一代之概率，也就是在輪盤上任意取n點，面積比率較大者，選擇并復制至交叉池（MatingPool）的個體數(shù)相對較多。P1P2PNPN-1輪盤賭選擇（RouletteWheelSelection輪盤賭選擇示例設有四個染色體Cl＝l，C2＝4，C3＝10，C4＝15，其適應度函數(shù)（FitnessFunction）為F（X）＝X，相應之適應函數(shù)值為f1＝1，f2＝4，f3＝10，f4＝15，占據(jù)輪盤的面積，Pcl＝1/30＝0.03，Pc2＝4/30＝0.13，

Pc3＝10/30＝0.33，Pc4＝15/30＝0.51，其中Cl與C2所占比率較小，可能在下一代被C3及C4所取代。輪盤賭選擇示例設有四個染色體Cl＝l，C2＝4，C3＝10，交叉算子

(crossoveroperator)定義：模擬生物的自然進化過程中，兩個同源染色體通過交配重組形成新染色體，產(chǎn)生新個體和物種的進化操作，稱為交叉算子。交叉操作步驟：1.從種群個體中分別任意選取兩個個體組成母體對。2.對任一母體對獨立重復實施交叉操作生成子代個體。交叉算子(crossoveroperator)定義：模擬交叉算子

(crossoveroperator)單點交叉多點交叉均勻交叉洗牌交叉部分匹配交叉順序交叉循環(huán)交叉交叉算子(crossoveroperator)單點交叉單點交叉在母體個體變量排序中任選一交叉點，并以該點為分界相互交換交叉點后的變量，形成新的子代個體。例如：母個體對：

10111001010100011110

子代個體對：

10110111100100100101單點交叉在母體個體變量排序中任選一交叉點，并以該點為分界相互順序交叉兩個母體交叉時，通過選擇母體1的一部分，并保留母體2中相應碼位的相對順序，而生成子個體。順序交叉操作能保留母體的排列并融合不同排列的有序結(jié)構(gòu)單元。母個體對：

123456789452187693

子代個體對的兩個交叉點之間的中間段保持不變：

XXX|4567|XXXXX|1876|XX

子個體1由2的排序93-452-1876中去掉中間段4567獲得

21

8|4567|93

子個體2由1的排序89-1234-567之間去掉中間段1876獲得

34

5|1876|9

2

順序交叉兩個母體交叉時，通過選擇母體1的一部分，并保留母體2可變精度的交叉在實數(shù)編碼的兩個母體交叉時，首先選擇一個交換點，然后將母體兩個染色體交叉點右邊的部分交換，接著再計算交換點的線性組合，這樣產(chǎn)生兩個新的子代個體。即：

母體對：子代個體對：其中：

分別表示第個基因解空間的上限和下限，是一個隨機數(shù)，

新的基因由隨機變量和產(chǎn)生，由于在不同的代中，它的值是不同的，所以基因取值精度就可以擴展。可變精度的交叉在實數(shù)編碼的兩個母體交叉時，首先選擇一個交換點變異算子(mutationoperator)定義：模擬種群內(nèi)部分個體染色體中基因發(fā)生突變，產(chǎn)生新的個體和物種的進化操作，稱為變異（突變）算子。變異的作用是可以恢復一些在遺傳進化過程中丟失的部分基因，增加種群內(nèi)個體的多樣性，避免進化的早熟和局部收斂。操作步驟：

1）在母體經(jīng)過交叉產(chǎn)生的子代個體中按一定（極小的）概率挑選出少量的個體；

2）對挑選出的個體中的部分基因，按一定的方式進行變異，產(chǎn)生新的物種。變異算子(mutationoperator)定義：模擬種變異算子(mutationoperator)點變異均勻變異正態(tài)變異非一致變異大規(guī)模反饋式突變變異算子(mutationoperator)點變異二進制編碼的點變異按某一概率獨立地改變個體的某幾位基因的進化操作變異前的個體

110010111011

變異后的個體

111111110010

種群中選擇進行變異的個體的概率一般很小大約0.01-0.001,因此對優(yōu)秀的個體的影響較小.

二進制編碼的點變異按某一概率獨立地改變個體的某幾位基因的進化實數(shù)編碼的高精細變異變異時，單個染色體的兩個基因被隨機地選擇進行凸組合的變異。假設染色體:

的第i個基因和第k個基因被選擇進行變異，變異生成新的染色體為:

其中，兩個基因分別為：這里為隨機數(shù)，。這種變異方式的目的就是為了增強變異的精細調(diào)節(jié)能力。實數(shù)編碼的高精細變異變異時，單個染色體的兩個基因被隨機地選擇大規(guī)模反饋式突變采用輪盤賭選擇和最優(yōu)個體保存策略，隨著進化的進行，某些好的個體產(chǎn)生的后代越來越多，整個種群適應度也越來越高，這時種群中基因的多樣性變得越來越差,以至于進化進行非常緩慢甚至完全停滯，種群陷入早熟。大規(guī)模反饋式突變,就是用隨機生成的新的個體代替通過突變被消滅的個體，可以大大提高種群的多樣性，同時保持了種群大小的穩(wěn)定。假設通過反饋式突變的產(chǎn)生的新的染色體的數(shù)目為L，那么就利用混合編碼的方式隨機產(chǎn)生L個新的染色體，代替種群中原來適應度值排在最后的L個染色體。大規(guī)模反饋式突變采用輪盤賭選擇和最優(yōu)個體保存策略，隨著進化的Step1.（編碼與初始化）確定種群規(guī)模，交叉與變異概率，初始種群隨機生成；Step2.（個體評價）估計種群中各個體的適應度；Step3.（種群進化）

3.1選擇（母體）

3.2交叉依交叉概率形成中間個體；

3.3變異對中間個體依變異概率執(zhí)行變異，形成候選個體；

3.4選擇（子代）從候選個體中依適應度選擇合適個體組成新種群；Step4.（終止校驗）滿足終止準則，輸出最優(yōu)解，否則繼續(xù)轉(zhuǎn)步3。標準遺傳進化算法的基本運算過程(Holland1969,DeJong1975,Goldberg1989)Step1.（編碼與初始化）確定種群規(guī)模，交叉與變異概率，初計算的典型執(zhí)行技巧研究：搜索機理研究：收斂性理論研究：復雜性理論研究；有效性理論研究。遺傳進化算法的基本理論研究在原始的遺傳算法中存在著早熟收斂、收斂速度慢、計算效率低、精度不高、搜索能力弱、容易陷入局部最優(yōu)等問題，因此展開如下眾多基本理論研究。計算的典型執(zhí)行技巧研究：遺傳進化算法的基本理論研究在原始的遺遺傳計算的典型執(zhí)行技巧適應值共享策略并行（群體分組、搜索空間分解）實現(xiàn)策略混合（神經(jīng)網(wǎng)絡、梯度下降、列表尋優(yōu)、貪婪變換）策略自適應（穩(wěn)態(tài)、動態(tài)、混合編碼、選擇）策略；遺傳計算的典型執(zhí)行技巧適應值共享策略杰出者選擇遺傳算法Step1.（初始化）確定交叉與變異概率，初始種群隨機生成,置t=0；

Step2.（個體評價）估計種群中各個體的適應度；Step3.（種群進化）

3.1獨立從當前種群中選擇出(N-1)對母體

3.2依交叉概率對(N-1)對母體進行交叉運算,形成(N-1)對中間個體；

3.3對(N-1)個中間個體依變異概率執(zhí)行變異，形成t+1代種群的前

(N-1)候選個體；

3.4從候選個體中依適應度選擇一個最優(yōu)個體,并令t+1代種群的第N個個體Step4.（終止校驗）滿足終止準則，輸出最優(yōu)解，否則繼續(xù)轉(zhuǎn)步3。杰出者選擇遺傳算法Step1.（初始化）確定交叉與變異概率，結(jié)合神經(jīng)網(wǎng)絡的混合遺傳算法(1)對于一類組合優(yōu)化問題已知H0pfield神經(jīng)網(wǎng)絡,收斂的穩(wěn)定態(tài)對應該問題的局部最優(yōu)解結(jié)合神經(jīng)網(wǎng)絡的混合遺傳算法(1)對于一類組合優(yōu)化問題結(jié)合神經(jīng)網(wǎng)絡的混合遺傳算法(2)Step1(初始化)隨機生成初始種群,指定交叉和變異概率及終止規(guī)則,設t=0并定義適應度函數(shù)Step2(種群進化)2.1依初始種群的適應度從初始種群中選擇N對母體;2.2對所選出的每一對母體執(zhí)行交叉運算,生成N個中間個體;2.3對交叉生成的中間個體執(zhí)行變異,生成N個候選個體;2.4依每一個候選個體為初始態(tài)激活Hopfield神經(jīng)網(wǎng)絡,產(chǎn)生出N個局部最優(yōu)態(tài),并構(gòu)成新一代種群;Step3(終止校驗)如滿足終止準則,停止計算并輸出最佳個體得到近似全局最優(yōu)解.結(jié)合神經(jīng)網(wǎng)絡的混合遺傳算法(2)Step1(初始化)隨機生成第5章遺傳進化算法基本概念、基本原理、基本算法第5章遺傳進化算法基本概念、基本原理、基本算法達爾文的生物進化論與遺傳算法遺傳—生命之特征或性狀的傳承染色體（chromosome)DNA(deoxyribonucleicacid)RNA(ribonucleicacid)

雙螺旋結(jié)構(gòu)基因(gene)

四進制編碼（A,T,C,G)

復制(reproduction)

交叉(crossover)

變異(mutation)達爾文的生物進化論與遺傳算法遺傳—生命之特征或性狀的傳承達爾文的生物進化論與遺傳算法進化—“物競天擇，優(yōu)勝劣汰，適者生存”遺傳信息（基因）寓于染色體，染色體決定生物特征，特征決定對環(huán)境的適應度。遺傳與進化之過程均發(fā)生在DNA之上。遺傳通過繁殖完成，繁殖由基因復制實現(xiàn)，復制的基本方式是交叉重組。交叉與變異產(chǎn)生新的物種，變異是物種進化的保證。適應度決定物種的存活，適應性強者遺傳機會更大。競爭是物種進化的促進劑。有競爭就有選擇，自然選擇是進化的基本規(guī)律達爾文的生物進化論與遺傳算法進化—“物競天擇，優(yōu)勝劣遺傳進化算法的基本概念編碼、個體與種群(encoding,individualandpopulation)適應度函數(shù)(fitnessfunction)選擇算子(selectionoperator)交叉算子(crossoveroperator)變異算子(mutationoperator)遺傳進化算法的基本概念編碼、個體與種群(encoding,遺傳編碼(geneticencoding)二進制編碼灰度編碼可拼接/可分解編碼實數(shù)編碼可變精度實數(shù)編碼符號編碼混亂編碼混合編碼遺傳編碼(geneticencoding)二進制編碼編碼(encoding)與解碼(decoding)式中A所表示的有限字符串稱為優(yōu)化變量X的遺傳（染色體）編碼，記為

,A中的字符稱為基因，字符所有可能的取值稱為等位基因，L稱為編碼長度；X稱為A的解碼，記為。編碼的重要性：1）基因的排列決定遺傳操作的作用方式；

2）決定搜索的難度與復雜性；

3）決定問題求解的精度。編碼(encoding)與解碼(decoding)式中A所個體空間與種群空間一個問題可行解的遺傳編碼稱為個體，或者說一群染色體的組合稱為個體設表示等位基因，為給定的編碼長度，則所有基因可能排列成的編碼構(gòu)成整個個體空間對任何正整數(shù)m，乘積稱為m階種群空間，其中的元素稱為m階種群個體空間中的一群個體稱為一個種群個體空間與種群空間一個問題可行解的遺傳編碼稱為個體，或者說一與編碼相關(guān)的定義1）編碼格式e是從HL到的一個映射，且對任何，存在唯一與之對應的解碼；2）當且僅當任何唯一對應一個個體A，則稱編碼格式是正則的；3）如果一個L編碼和一個K編碼的拼接有意義且是一個L+K碼，則稱其為是可拼接的；反之則稱之為是可分解的

設個體空間為：其可行解空間為：與編碼相關(guān)的定義1）編碼格式e是從HL到的一二進制編碼二進制編碼：以字符0和1為等位基因的定長字符串編碼。對實數(shù)xi給定編碼精度，取mi

為滿足的最小整數(shù)，則mi

長的0-1字符串唯一對應實數(shù)xi

，定義為：設且二進制編碼二進制編碼：以字符0和1為等位基因的定長字符串編碼二進制編碼示例Xi的

二進制編碼個體：

0000000000000000000000000010.0009767…………00010001000101.088043811111111111118.0001497設

則mi=13，從中任選n個個體可構(gòu)成一個種群,任選m次就可構(gòu)成m個種群二進制編碼示例Xi的二進制編碼個體：設則mi=13二進制編碼的優(yōu)缺點優(yōu)點：二進制編碼簡明、通用、易于各種進化操作。缺點：不具備正則性，可能破壞可行解空間的拓撲連續(xù)性。

對于高維、連續(xù)優(yōu)化問題存在離散化誤差，高精度要求將產(chǎn)生很長的編碼；不便于表達反映所求問題的特定知識。例如:在整數(shù)集[0,10]中的數(shù)7和8最鄰近，但它們的二進制編碼0111和1000的海明距離為4，最遠.海明距離：兩染色體編碼所有相應位置中取不同數(shù)值的位置數(shù)二進制編碼的優(yōu)缺點優(yōu)點：二進制編碼簡明、通用、易于各種進化操灰度編碼假定已有二進制編碼：其修正（灰度）編碼：兩者相互轉(zhuǎn)換公式：即：其中表示異或運算，即：灰度編碼假定已有二進制編碼：二進制與灰度編碼轉(zhuǎn)換示例二進制編碼0111(7),1000(8),1011(11),1100(12),前兩個編碼的海明距離為4,后兩個編碼海明距離為3.其相應灰度編碼為0

0

11,1011,1001,1101,顯然前后兩個編碼的海明距離均為1,新編碼保持了原空間的連續(xù)性.其灰度變換計算:其逆變換計算:二進制與灰度編碼轉(zhuǎn)換示例二進制編碼0111(7),個基因，和分別表示第表示染色體，這里表示染色體的第個基因解空間的上限和下限。實數(shù)與二進制的混合編碼設個基因，和分別表示第表示染色體，這里表示染色體的第個基因解空采用混合編碼產(chǎn)生初始種群的算法如下：隨機產(chǎn)生一個隨機數(shù)，實數(shù)與二進制的混合編碼

；(2),重復N次，就產(chǎn)生一個染色體(3)重復步驟(1)、(2)M次，就產(chǎn)生一個包含M個染色體的初始種群。采用混合編碼產(chǎn)生初始種群的算法如下：實數(shù)與二進制的混合編碼；適應度函數(shù)(fitnessfunction)1）對應某種生物群體在給定環(huán)境下的適應性度量；2）優(yōu)化變量X對應生物群體中的個體；3）遺傳進化對應于實現(xiàn)該優(yōu)化過程的演化過程。

適應度函數(shù)是評價群體中個體好壞的標準，是模擬自然選擇的唯一依據(jù)。從而適應度函數(shù)選取的優(yōu)劣直接影響遺傳算法的收斂速度及能否找到最優(yōu)解。適應度函數(shù)(fitnessfunction)1）對應某種生適應度函數(shù)的設計原則早熟現(xiàn)象：遺傳算法運行初期階段，群體中或許會出現(xiàn)適應度極好的個體，最終這些個體可能會充斥整個群體，使用于產(chǎn)生新個體作用較大的交叉操作失去作用，從而使得群體的多樣性降低，遺傳算法提前收斂到某個局部最優(yōu)解。適應度函數(shù)的選取應盡量的避免早熟現(xiàn)象，即縮小適應度較高的個體與其他個體適應度之間的差異，限制其復制數(shù)量以維護群體的多樣性

適應度函數(shù)的設計原則早熟現(xiàn)象：遺傳算法運行初期階段，群體中或適應度函數(shù)的設計原則退化現(xiàn)象：遺傳算法運行后期階段，群體越來越集中，個體之間的差異減小，相互之間的競爭力也隨即減弱。這必然造成個體被選擇到下一代中的概率接近，使進化過程失去競爭力，退化為隨機選擇過程。適應度函數(shù)的選取應該克服這種退化現(xiàn)象，使算法在運行后期階段能夠擴大最佳個體適應度與其它個體適應度之間的差異，提高個體之間的競爭性。適應度函數(shù)的設計原則退化現(xiàn)象：遺傳算法運行后期階段，群體越來適應度函數(shù)的常用變換線性尺度變換乘冪尺度變換指數(shù)尺度變換適應度函數(shù)的常用變換線性尺度變換適應度函數(shù)設計舉例

設計一個分段的非線性變換的適應度函數(shù)這里,表示變換過后的適應度函數(shù)；表示種群的適應度比例值、、和均為常數(shù)。其中的主要作用一方面用于保證恒為正，另一方面調(diào)控不同個體被選擇的概率；為冪指數(shù)，可在1-1.2之間選擇；、為0-1的實數(shù)，是不同函數(shù)的切換條件。適應度函數(shù)設計舉例設計一個分段的非線性變換的適應度函數(shù)選擇算子(selectionoperator)模擬“優(yōu)勝劣汰、適者生存”自然進化原理決定父代種群中個體以多大可能被選中遺傳到下一代的進化操作。選擇原則：1）依據(jù)適應度評價；

2）選擇最優(yōu)個體；

3）避免無效搜索；

4）快速搜索到最優(yōu)解。定義：選擇算子S是一個隨機映射，它滿足：

選擇算子(selectionoperator)模擬“優(yōu)勝選擇算子(selectionoperator)比例選擇（輪盤賭選擇）變尺度比例選擇杰出者選擇期望生存數(shù)選擇確定式采樣選擇排序選擇Boltzmann局部退火選擇種群偏差度選擇排除算子選擇基于正交表的選擇選擇算子(selectionoperator)比例選擇（比例選擇比例選擇輪盤賭選擇（RouletteWheelSelection）

每一個染色體適應度函數(shù)值決定其在輪盤上面積的大小。此面積大小與輪盤總面積的比率就染色體被挑選至下一代之概率，也就是在輪盤上任意取n點，面積比率較大者，選擇并復制至交叉池（MatingPool）的個體數(shù)相對較多。P1P2PNPN-1輪盤賭選擇（RouletteWheelSelection輪盤賭選擇示例設有四個染色體Cl＝l，C2＝4，C3＝10，C4＝15，其適應度函數(shù)（FitnessFunction）為F（X）＝X，相應之適應函數(shù)值為f1＝1，f2＝4，f3＝10，f4＝15，占據(jù)輪盤的面積，Pcl＝1/30＝0.03，Pc2＝4/30＝0.13，

Pc3＝10/30＝0.33，Pc4＝15/30＝0.51，其中Cl與C2所占比率較小，可能在下一代被C3及C4所取代。輪盤賭選擇示例設有四個染色體Cl＝l，C2＝4，C3＝10，交叉算子

(crossoveroperator)定義：模擬生物的自然進化過程中，兩個同源染色體通過交配重組形成新染色體，產(chǎn)生新個體和物種的進化操作，稱為交叉算子。交叉操作步驟：1.從種群個體中分別任意選取兩個個體組成母體對。2.對任一母體對獨立重復實施交叉操作生成子代個體。交叉算子(crossoveroperator)定義：模擬交叉算子

(crossoveroperator)單點交叉多點交叉均勻交叉洗牌交叉部分匹配交叉順序交叉循環(huán)交叉交叉算子(crossoveroperator)單點交叉單點交叉在母體個體變量排序中任選一交叉點，并以該點為分界相互交換交叉點后的變量，形成新的子代個體。例如：母個體對：

10111001010100011110

子代個體對：

10110111100100100101單點交叉在母體個體變量排序中任選一交叉點，并以該點為分界相互順序交叉兩個母體交叉時，通過選擇母體1的一部分，并保留母體2中相應碼位的相對順序，而生成子個體。順序交叉操作能保留母體的排列并融合不同排列的有序結(jié)構(gòu)單元。母個體對：

123456789452187693

子代個體對的兩個交叉點之間的中間段保持不變：

XXX|4567|XXXXX|1876|XX

子個體1由2的排序93-452-1876中去掉中間段4567獲得

21

8|4567|93

子個體2由1的排序89-1234-567之間去掉中間段1876獲得

34

5|1876|9

2

順序交叉兩個母體交叉時，通過選擇母體1的一部分，并保留母體2可變精度的交叉在實數(shù)編碼的兩個母體交叉時，首先選擇一個交換點，然后將母體兩個染色體交叉點右邊的部分交換，接著再計算交換點的線性組合，這樣產(chǎn)生兩個新的子代個體。即：

母體對：子代個體對：其中：

分別表示第個基因解空間的上限和下限，是一個隨機數(shù)，

新的基因由隨機變量和產(chǎn)生，由于在不同的代中，它的值是不同的，所以基因取值精度就可以擴展。可變精度的交叉在實數(shù)編碼的兩個母體交叉時，首先選擇一個交換點變異算子(mutationoperator)定義：模擬種群內(nèi)部分個體染色體中基因發(fā)生突變，產(chǎn)生新的個體和物種的進化操作，稱為變異（突變）算子。變異的作用是可以恢復一些在遺傳進化過程中丟失的部分基因，增加種群內(nèi)個體的多樣性，避免進化的早熟和局部收斂。操作步驟：

1）在母體經(jīng)過交叉產(chǎn)生的子代個體中按一定（極小的）概率挑選出少量的個體；

2）對挑選出的個體中的部分基因，按一定的方式進行變異，產(chǎn)生新的物種。變異算子(mutationoperator)定義：模擬種變異算子(mutationoperator)點變異均勻變異正態(tài)變異非一致變異大規(guī)模反饋式突變變異算子(mutationoperator)點變異二進制編碼的點變異按某一概率獨立地改變個體的某幾位基因的進化操作變異前的個體

110010111011

變異后的個體

111111110010

種群中選擇進行變異的個體的概率一般很小大約0.01-0.001,因此對優(yōu)秀的個體的影響較小.

二進制編碼的點變異按某一概率獨立地改變個體的某幾位基因的進化實數(shù)編碼的高精細變異變異時，單個染色體的兩個基因被隨機地選擇進行凸組合的變異。假設染色體:

的第i個基因和第k個基因被選擇進行變異，變異生成新的染色體為:

其中，兩個基因分別為：這里為隨機數(shù)，。這種變異方式的目的就是為了增強變異的精細調(diào)節(jié)能力。實數(shù)編碼的高精細變異變異時，單個染色體的兩個基