GA遺傳算法專題知識培訓(xùn)課件

GA遺傳算法專題知識遺傳算法與模擬退火算法一樣是為解決組合優(yōu)化問題而提出！

人工智能在信息處理和解決組合爆炸方面遇到的困難越來越明顯迫使尋求一種適合于大規(guī)模問題并具有自組織、自適應(yīng)、自學(xué)習(xí)能力的算法，基于生活進(jìn)化論的遺傳算法被提出！2GA遺傳算法專題知識遺傳算法遺傳算法簡稱GA（GeneticAlgorithms）是1962年由美國Michigan大學(xué)的Holland教授提出的模擬自然界遺傳機(jī)制和生物進(jìn)化論而成的一種并行隨機(jī)搜索最優(yōu)化方法。遺傳算法是以達(dá)爾文的自然選擇學(xué)說（適者生存）以及Mendel遺傳學(xué)說（基因遺傳原理）為基礎(chǔ)發(fā)展起來的。算法思路：GA將問題的求解表示成“染色體”的適者生存過程，通過“染色體”群的一代代不斷進(jìn)化，包括復(fù)制、交叉、變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個(gè)體，從而求得問題的最優(yōu)解或滿意解。特點(diǎn)：隱含并行性和全局解空間搜索GA的應(yīng)用領(lǐng)域：機(jī)器學(xué)習(xí)、模式識別、圖像處理、神經(jīng)網(wǎng)絡(luò)、優(yōu)化控制、組合優(yōu)化等3GA遺傳算法專題知識遺傳算法中的自然法則自然選擇學(xué)說包括以下三個(gè)方面：（1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個(gè)特征，物種才能穩(wěn)定存在。（2）變異：親代和子代之間以及子代的不同個(gè)體之間的差異，稱為變異。變異是隨機(jī)發(fā)生的，變異的選擇和積累是生命多樣性的根源。（3）生存斗爭和適者生存：具有適應(yīng)性變異的個(gè)體被保留下來，不具有適應(yīng)性變異的個(gè)體被淘汰，通過一代代的生存環(huán)境的選擇作用，性狀逐漸逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。Mendel遺傳學(xué)說遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個(gè)基因有特殊的位置并控制某種特殊性質(zhì)。所以，每個(gè)基因產(chǎn)生的個(gè)體對環(huán)境具有某種適應(yīng)性。4GA遺傳算法專題知識遺傳算法中的自然法則遺傳算法將“優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入優(yōu)化參數(shù)形成的編碼串聯(lián)群體中，按所選擇的適應(yīng)度函數(shù)并通過遺傳中的復(fù)制、交叉及變異對個(gè)體進(jìn)行篩選，使適應(yīng)度高的個(gè)體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的條件。遺傳算法的算法簡單，可并行處理，并能得到全局最優(yōu)解。5GA遺傳算法專題知識遺傳算法中的相關(guān)概念遺傳算法用到各種進(jìn)化和遺傳學(xué)得概念。以下是一些主要的概念：(1)串(String)：它是個(gè)體(Individual)的形式，在算法中為二進(jìn)制串，并且對應(yīng)于遺傳學(xué)中的染色體(Chromosome).(2)群體(Population):個(gè)體的集合稱為群體，串是群體的元素。(3)群體規(guī)模(PopulationSize)：在群體中個(gè)體的數(shù)量稱為群體規(guī)模，又稱群體的大小。(4)基因(Gene):基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S=1011，則其中1,0,1,1這四個(gè)元素分別稱為基因，它們的值稱為等位基因。(5)基因位置(GenePosition):一個(gè)基因在串中的位置稱為基因位置，有時(shí)也簡稱基因位?；蛭恢糜纱淖筮呄蛴矣?jì)算，例如在串S=1011中,0的基因位是3.基因位置對應(yīng)于遺傳學(xué)中的地點(diǎn)(Locus).(6)適應(yīng)度(Fitness)：表示某一個(gè)體對于環(huán)境的適應(yīng)程度。圖1解空間與生物空間的對應(yīng)6GA遺傳算法專題知識遺傳算法的基本流程遺傳算法是一類隨機(jī)優(yōu)化算法，但它不是簡單的隨機(jī)比較搜索，而是通過對染色體的評價(jià)和對染色體中基因的作用，有效地利用已有的信息來指導(dǎo)搜索有希望改善優(yōu)化質(zhì)量的狀態(tài)。該算法包括5個(gè)基本要素：變量編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)和參數(shù)設(shè)定。（1）編碼通過編碼將解空間的數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。編碼一般有二進(jìn)制編碼和實(shí)數(shù)編碼。對于問題解X，X=（x1，x2，…，xn），二進(jìn)制編碼是把X用0,1串表示，而實(shí)數(shù)編碼是把X用一向量表示，即X=（x1，x2，…，xn），xi是實(shí)數(shù)。編碼設(shè)計(jì)應(yīng)適合要解決的問題，應(yīng)考慮完全性、封閉性、可擴(kuò)展性和復(fù)雜性等。完全性是指分布在所有問題域的解都可能被構(gòu)造出來；封閉性是指每個(gè)基因編碼對應(yīng)一個(gè)可接受的個(gè)體，不產(chǎn)生無效的個(gè)體；可擴(kuò)展性是指對于具體問題，要考慮編碼形式與大小影響下的解碼時(shí)間；復(fù)雜性是指整體考慮基因型的結(jié)構(gòu)復(fù)雜性、解碼復(fù)雜性、計(jì)算復(fù)雜性等。

(2)初始群體的生成在遺傳算法處理流程中，繼編碼設(shè)計(jì)后的任務(wù)是初始群體的生成，并以此為起點(diǎn)一代代進(jìn)化直到滿足某種進(jìn)化停止準(zhǔn)則終止進(jìn)化過程，初始群體也稱為進(jìn)化的初始代，即第一代。初始群體的個(gè)體一般可采用隨機(jī)產(chǎn)生，一般群體可表示為Z={Xi|Xi=（xi1,xi2,…..xin）}，i=1,2,…N}，即Xi是染色體或個(gè)體，xi是基因或位。若是實(shí)數(shù)編碼，則xi

7GA遺傳算法專題知識遺傳算法的基本流程（3）適應(yīng)度函數(shù)適應(yīng)度函數(shù)設(shè)計(jì)是模擬自然選擇，進(jìn)行遺傳進(jìn)化操作的基礎(chǔ)，它的評估是遺傳操作的依據(jù)。適應(yīng)度函數(shù)值即適應(yīng)度。由于下面定義的選擇概率以適應(yīng)度為基礎(chǔ)，因此適應(yīng)度是非負(fù)的。方法一：對于求目標(biāo)函數(shù)最大值的優(yōu)化問題，變換方法為：

其中，Cmin為一個(gè)適當(dāng)?shù)叵鄬Ρ容^小的數(shù)，它可用下面方法之一來選取：

?預(yù)先指定的一個(gè)較小的數(shù)。

?進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。

?當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。

方法二：對于求目標(biāo)函數(shù)最小值的優(yōu)化問題，變換方法為：其中，Cmax是一個(gè)適當(dāng)?shù)叵鄬Ρ容^大的數(shù)，它可用下面幾種方法求得：

?預(yù)先指定的一個(gè)較大的數(shù)。

?進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。

?當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值。F(X)=f(X)+Cminiff(X)+Cmin>00

iff(X)+Cmin≤0F(X)=Cmax-f(X)

iff(X)Cmax0

iff(X)

Cmax8GA遺傳算法專題知識遺傳算法的基本流程從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)的個(gè)體的操作稱為選擇。它是建立在群體中個(gè)體適應(yīng)值的基礎(chǔ)上的，其目的是把優(yōu)勝的個(gè)體遺傳到下一代，選擇操作的實(shí)現(xiàn)是根據(jù)適應(yīng)度大小按照某種策略從父代中挑選個(gè)體進(jìn)入中間群體。選擇算子設(shè)計(jì)依賴選擇概率，個(gè)體Xi選擇概率定義為其中fi是群體中第i個(gè)個(gè)體的適應(yīng)值，N是群體的規(guī)模。當(dāng)reli越大時(shí)，個(gè)體Xi被選擇遺傳（復(fù)制）到下一代的可能性越大。目前常用的遺傳選擇算子主要有以下幾種：（1）基于賭輪法的選擇算子(2)期望值方法9GA遺傳算法專題知識遺傳算法的基本流程A、基于賭輪法的選擇算子賭輪法是指根據(jù)個(gè)體被選擇概率大小確定相應(yīng)個(gè)體是否被遺傳（復(fù)制）到下一代，其比較判別過程采用了輪盤賭的思想。設(shè)種群有n個(gè)個(gè)體X1，X2，…，Xn，Xi的選擇概率P（Xi），每個(gè)個(gè)體對應(yīng)P（Xi）表示為賭輪上的某個(gè)區(qū)域，按個(gè)體數(shù)n轉(zhuǎn)動賭輪n次，根據(jù)賭輪停止點(diǎn)區(qū)域?qū)?yīng)的個(gè)體進(jìn)行選擇，個(gè)體對應(yīng)賭輪區(qū)域越大被選擇的機(jī)會越大，計(jì)算個(gè)體被選擇的數(shù)量，這些個(gè)體將按選擇的數(shù)量被復(fù)制。在計(jì)算機(jī)輔助實(shí)現(xiàn)過程中，模擬賭輪一般采用以下方法：根據(jù)個(gè)體的排序，按選擇概率P（Xi）計(jì)算累積概率

，則Pi（Xi）=qi-qi-1，產(chǎn)生n個(gè)隨機(jī)數(shù)rk，對每一個(gè)隨機(jī)數(shù)，判斷其落在那個(gè)概率區(qū)間內(nèi)，則復(fù)制相應(yīng)的Xi，可以得到選擇復(fù)制后的n個(gè)新一代個(gè)體。可以看到適應(yīng)值越大的染色體被選中（復(fù)制）的概率也越大。B、期望值方法把每一個(gè)體的適應(yīng)度與平均適應(yīng)度進(jìn)行比較，以確定該個(gè)體在下一代的復(fù)制數(shù)，即每個(gè)個(gè)體在下一代生存的期望數(shù)目為Ni=round(p(xi)*N)可以看到適應(yīng)值越大的染色體被選中（復(fù)制）的數(shù)目也越多。，其中round(x)表示與x距離最小的整數(shù)。10GA遺傳算法專題知識遺傳算法的基本流程（4）遺傳操作設(shè)計(jì)交叉算子變異算子A、交叉算子交叉是把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以重組而生成新個(gè)體的操作。交叉的作用，是使新的群體中的個(gè)體具有多樣性，擴(kuò)大解的搜索空間，使個(gè)體對應(yīng)的解逐步逼近局部最優(yōu)解。交叉算子設(shè)計(jì)一般要考慮三個(gè)問題：（1）交叉概率Pc的確定（2）在Pc<1的情況下，判別兩個(gè)個(gè)體是否要交叉。（3）對交叉的個(gè)體采用何種形式交叉。在n個(gè)個(gè)體組成的種群和給定交叉概率Pc的條件下，需要交叉的個(gè)體數(shù)為m=nXPc，每代交叉時(shí)，隨機(jī)抽取個(gè)體Xi和Xj，產(chǎn)生（0,1）區(qū)間的隨機(jī)數(shù)r，如果r<Pc,則表示Xi和Xj要交叉，否則不交叉，這樣判別直至需要交叉?zhèn)€體數(shù)為m時(shí)停止。11GA遺傳算法專題知識遺傳算法的基本流程常見的交叉形式有以下幾種：（1）單點(diǎn)交叉單點(diǎn)交叉右腳簡單交叉，具體操作是：在個(gè)體基因串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)。實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新個(gè)體。當(dāng)基因鏈碼的長度為n時(shí)，可能有n-1個(gè)交叉點(diǎn)位置。單點(diǎn)交叉算子的具體計(jì)算過程如下：

Ⅰ.對群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對。若群體大小為M，則共有[M/2]對相互配對的個(gè)體組。

Ⅱ.每一對相互配對的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)。若染色體的長度為l

，則共有(l-1)個(gè)可能的交叉點(diǎn)位置。

Ⅲ.對每一對相互配對的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。

單點(diǎn)交叉運(yùn)算的示例如下所示:A；1011011100A’：1011011111B：0001110011B’：000111000012GA遺傳算法專題知識遺傳算法的基本流程常見的交叉形式：（2）兩點(diǎn)交叉

與單點(diǎn)交叉相似，只是需要設(shè)置兩個(gè)交叉點(diǎn)，然后兩個(gè)染色體相互交換兩點(diǎn)之間的部分，從而生成兩

個(gè)新染色體。一個(gè)兩點(diǎn)交叉的說明如下：父輩個(gè)體：aaa|aaaa|aaaaaa|bbbb|aaa父輩個(gè)體：bbb|bbbb|bbbbbb|aaaa|bbb（3）均勻交叉均勻交叉則是依概率交換兩個(gè)父輩個(gè)體基因串的每一位。其過程是：先隨機(jī)的產(chǎn)生一個(gè)與父輩個(gè)體基因串具有同樣長度的二進(jìn)制串，其中0表示不交換，1表示交換。這個(gè)二進(jìn)制串稱為交叉模板；然后根據(jù)該模板對兩個(gè)父輩基因串進(jìn)行交叉，得到的兩個(gè)新基因串即為后代新個(gè)體。例如：父輩個(gè)體1：110010111000父輩個(gè)體2：101011101011模板：001101011100后代個(gè)體1：111011101000后代個(gè)體2：100010111011均勻交叉在交換位時(shí)不考慮其所在位置，破壞模式的概率較大。但另一方面它能搜索到一些前面基于點(diǎn)的交叉方法無法搜索到的模式。13GA遺傳算法專題知識遺傳算法的基本流程B、變異算子變異是對群體中的個(gè)體的某些基因值得變動。變異的作用是使種群中的某些個(gè)體的基因（位）產(chǎn)生突變引入原種群不含有的基因，形成的新個(gè)體與其他的個(gè)體有所不同。與交叉算子的作用是使對應(yīng)解逐步逼近局部最優(yōu)解相比，變異算子的作用是使個(gè)體對應(yīng)的解逐步逼近全局最優(yōu)解。變異算子設(shè)計(jì)也要考慮三個(gè)問題：（1）變異概率Pm的確定。（2）在Pm<1的情況下，判別個(gè)體的某基因是否要變異。（3）對需變異的基因采用何種形式變異。若種群有n個(gè)個(gè)體，且每一個(gè)個(gè)體都有N個(gè)基因，給定的變異概率為Pm，則需要變異的基因數(shù)為M=nXNXPm，每代變異時(shí)，隨機(jī)抽取個(gè)體Xi及某一基因，產(chǎn)生（0,1）區(qū)間的隨機(jī)數(shù)r，如果r<Pc,則表示要變異，，否則不變異，這樣判別直至需要變異的基因數(shù)為M時(shí)停止，一般地，一個(gè)個(gè)體變異的基因數(shù)控制為最多一個(gè)是較合理的。14GA遺傳算法專題知識遺傳算法的基本流程常用的變異形式：（1）基本變異算子基本變異算子是針對二值基因鏈碼而言。其具體操作是：對群體中基因鏈碼隨機(jī)挑選C個(gè)基因位置并對這些基因位置的基因值以變異概率P取反，即0變成1,1變成0。當(dāng)C=1時(shí)，表示一個(gè)基因值取反?；疚蛔儺愡\(yùn)算的示例如下所示：

A：1010101010A’：1010001010

（2）均勻變異算子該變異方法是針對實(shí)數(shù)編碼方式的。設(shè)v=（v1,v2,...,vm）是群體中體，Z=(z1,z2,…,zm)是變異產(chǎn)生的后代。均勻性變異則是先在個(gè)體v中隨機(jī)的選擇一個(gè)分量vk，然后，在一個(gè)定義的區(qū)間[ak,bk]中均勻隨機(jī)取一個(gè)數(shù)Vk1代替vk以得到Z，即Z=（v1,v2,…,vk1,…,vm）。（3）自適應(yīng)變異算子該算子與基本變異算子的操作相似，兩者之間的區(qū)別就是使用自適應(yīng)變異算子時(shí)變異率不是固定不變而是隨著群體中個(gè)體多樣性的程度自適應(yīng)調(diào)整。基本位變異變異點(diǎn)15GA遺傳算法專題知識基本遺傳算法的運(yùn)行參數(shù)M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20~100；G：遺傳算法的終止進(jìn)化代數(shù)，一般取為100~500；Pc：交叉概率，一般取為0.4~0.99；也可以采取辦法：在指定交叉形式下，若有Pc0，使進(jìn)化代數(shù)最小達(dá)到終止條件，則交叉概率Pc0最優(yōu)。Pm：變異概率，一般取為0.01~0.001。也可以采取辦法：在指定變異形式下，若有Pm0，使進(jìn)化代數(shù)最小達(dá)到終止條件，則變異概率Pm0最優(yōu)。遺傳算法的基本流程16GA遺傳算法專題知識1、復(fù)制操作通常采用比例復(fù)制，即復(fù)制概率正比于個(gè)體的適配值，如此意味著適配值高的個(gè)體在下一代中復(fù)制自身的概率大，從而提高了種群的平均適配值。2、交叉操作通過交換兩個(gè)父代個(gè)體的部分信息構(gòu)成后代個(gè)體，使得后代繼承父代的有效模式，從而有助于產(chǎn)生優(yōu)良個(gè)體3、變異操作通過隨機(jī)改變個(gè)體中某些基因二產(chǎn)生新個(gè)體，有助于增加種群的多樣性，避免過早收斂遺傳算法的基本流程遺傳操作總結(jié)17GA遺傳算法專題知識遺傳算法的流程圖開始Gen=0編碼隨機(jī)產(chǎn)生M個(gè)初始個(gè)體滿足終止條件?計(jì)算群體中各個(gè)體適應(yīng)度從左至右依次執(zhí)行遺傳算子j=0j=0j=0根據(jù)適應(yīng)度選擇復(fù)制個(gè)體選擇兩個(gè)交叉?zhèn)€體選擇個(gè)體變異點(diǎn)執(zhí)行變異執(zhí)行交叉執(zhí)行復(fù)制將復(fù)制的個(gè)體添入新群體中將交叉后的兩個(gè)新個(gè)體添入新群體中將變異后的個(gè)體添入新群體中j=j+1j=j+2j=j+1

j=M?

j=pc·M?

j=pm·L·M?Gen=Gen+1輸出結(jié)果終止YNYYYNNNpcpm18GA遺傳算法專題知識遺傳算法偽代碼ALOGRITHMGA(i):Begin

t:=0;InitializeP(t);P(t)={X1(t),X2(t),…,Xn(t)}EvaluateP(t);

f(P(t))={f(X1(t)),f(X2(t)),…,f(Xn(t))}while(notterminationcondition)do{Create

BP(t);//繁殖池

PC(t)=crossover{BP(t)};Pm(t)=mutation{BP(t)};Evaluate[PC(t)]

and[Pm(t)]

;P(t+1)=select[PC(t)∪Pm(t)∪Q];

t:=t+1printXbest,f(Xbest);}printXbest,f(Xbest);End19GA遺傳算法專題知識標(biāo)準(zhǔn)遺傳算法的理論基礎(chǔ)模式定理和隱含并行性是holland為解釋基于二進(jìn)制編碼的標(biāo)準(zhǔn)遺傳算法(SGA)的功效而建立的，是最早對遺傳算法全局收斂性作定性分析的理論基礎(chǔ)，它說明了適配值高、長度短、階數(shù)低的圖式在后代中至少以指數(shù)增長包含該圖式的個(gè)體數(shù)。（1）模式定義基于三值字符集{0，1，*}所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似性的0、1字符串集的字符串稱作模式。例：以長度為5的串為例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即{00001,10001}；又如模式*1**0描述了所有在位置2為“1”及位置5為“0”的字符串，即{01000,01010,01100,01110,11000,11010,11100,11110}；而模式01010描述了只有一個(gè)串的集合，即{01010}。模式的概念提供了一種簡單的用于描述在某些位置上具有結(jié)構(gòu)相似性的0、1字符串集合的方法。

引入模式概念，使不同串之間通過模式而相互聯(lián)系。通過分析模式在遺傳操作下的變化，可以了解什么性質(zhì)被延續(xù)，什么性質(zhì)被丟棄。從而把握遺傳算法的實(shí)質(zhì)。（2）模式階定義模式H中確定位置的個(gè)數(shù)稱作該模式的模式階（SchemaOrder），記作O(H).例：模式011*1*的階數(shù)為4，而模式0*****的階數(shù)為1當(dāng)一個(gè)模式的階越高時(shí)，其所代表的集合中的個(gè)體數(shù)就越少，因而確定性越高。但是，模式階并不能反映模式的所有性質(zhì)。需要再引入定義距概念20GA遺傳算法專題知識標(biāo)準(zhǔn)遺傳算法的理論基礎(chǔ)（3）模式定義距的定義模式H中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱作該模式的定義距，記作例：模式011*1*的定義距為4，而模式0*****的定義距為0。

模式定理設(shè)H是任一個(gè)模式，P(g)={x1(g),x2(g),…,xn(g)}是第g代群體，xi(g)(i=1,2,…,n)是該群體中所有個(gè)體，S(H，g)表示在群體P(g)中與模式H相匹配的個(gè)體的集合，m(H,g)表示集合S(H,g)中的個(gè)體的數(shù)目，f(H,g)表示S(H,g)中個(gè)體的平均適應(yīng)度。P(g)中個(gè)體的平均適應(yīng)度為21GA遺傳算法專題知識標(biāo)準(zhǔn)遺傳算法的理論基礎(chǔ)模式定理：設(shè)遺傳算法的交叉概率和變異概率分別為Pc和Pm，l為個(gè)體基因鏈碼的長度，則有模式定理反映了子代個(gè)體模式數(shù)目與父代個(gè)體適應(yīng)度以及交叉、變異過程的關(guān)系：（1）子代個(gè)體模式數(shù)目依賴父代個(gè)體適應(yīng)度的關(guān)系假設(shè)一代中群體大小為n，且群體中的個(gè)體兩兩互不相同，則S(H,g)中所有個(gè)體被選擇的總概率為因而在第g+1代中模式H的樣本數(shù)m(H,g+1)為可見模式的增長或減少依賴于模式的平均適應(yīng)度與群體平均適應(yīng)度之比，那些平均適應(yīng)度高于群體平均適應(yīng)度的模式將在下一代中得以增長；而那些平均適應(yīng)度低于群體平均適應(yīng)度的模式將在下一代中減少。22GA遺傳算法專題知識標(biāo)準(zhǔn)遺傳算法的理論基礎(chǔ)（2）子代個(gè)體模式數(shù)目依賴父代個(gè)體交叉作用的關(guān)系對于模式H來說，只有當(dāng)交叉點(diǎn)落在定義距之外才能使該模式生存。在簡單交叉（單點(diǎn)交叉）下H被破壞的概率。小于等于表示：因?yàn)殡m然有時(shí)交叉點(diǎn)落在定義距之內(nèi)，但當(dāng)用于交叉的雙親的基因鏈碼在模式H的確定位置上相同時(shí)，所生成的后代個(gè)體仍具有模式H。由于交叉概率為Pc，因此，H生存的概率為這樣，在考慮了選擇和交叉算子之后，有23GA遺傳算法專題知識標(biāo)準(zhǔn)遺傳算法的理論基礎(chǔ)（3）子代個(gè)體模式數(shù)目依賴父代個(gè)體變異作用的關(guān)系模式在變異操作中的變化：由于個(gè)體基因鏈碼在某一位置發(fā)生改變的概率為Pm，則該個(gè)體該位置不變的概率為1-Pm。而模式H在變異算子作用下若要不受破壞，則其中所有的確定位置必須保持不變，因此模式H保持不變的概率為。當(dāng)Pm《1時(shí)，模式H在變異算子作用下的生存概率為

綜上所述，模式H在選擇、交叉和變異的共同作用下，其后代個(gè)體的數(shù)目為忽略可以得到如果存在常數(shù)c>0,使得可以記為當(dāng)

綜上所述，得到結(jié)論：在選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模在后代中將以指數(shù)級增長。24GA遺傳算法專題知識標(biāo)準(zhǔn)遺傳算法的理論基礎(chǔ)積木塊假設(shè)定義：具有低階，短的定義長度以及高適應(yīng)值的模式稱為積木塊。積木塊假設(shè)：低階、短的定義長度以及高適應(yīng)值的模式（積木塊）在遺傳算子作用下，相互結(jié)合，能夠生成高階、長定義長度、高平均適應(yīng)值得模式，可最終生成全局最優(yōu)解。模式定理保證了較優(yōu)的模式樣本數(shù)按指數(shù)增長，從而滿足了尋找最優(yōu)解的必要條件，而積木塊假設(shè)，則指出了遺傳算法具備尋找全局最優(yōu)解的能力。不過，上述結(jié)論并沒有得到理論證明，所以仍然被遺憾地稱為假設(shè)而不是定理，盡管有大量的實(shí)踐證據(jù)支持這一假設(shè)。（只是定性認(rèn)為，但很可能遺傳算法并不是全局收斂的，稍微改進(jìn)后的遺傳算法才是收斂的）隱含并行性模式定理認(rèn)為遺傳算法實(shí)質(zhì)上是模式的運(yùn)算，編碼的字母表越短，算法處理一代種群時(shí)隱含處理的模式就越多。當(dāng)算法采用二進(jìn)制編碼時(shí)，效率最高，處理規(guī)模為N的一代種群時(shí)，可同時(shí)處理o(N^3)個(gè)模式。遺傳算法這種以計(jì)算少量編碼適應(yīng)度而處理大量模式的性質(zhì)稱為隱并行性。25GA遺傳算法專題知識接下來我們用定理來證明遺傳算法的收斂性！26GA遺傳算法專題知識遺傳算法收斂性27GA遺傳算法專題知識遺傳算法收斂性28GA遺傳算法專題知識遺傳算法收斂性29GA遺傳算法專題知識遺傳算法收斂性30GA遺傳算法專題知識遺傳算法收斂性31GA遺傳算法專題知識(1)GA對問題參數(shù)編碼成“染色體”后進(jìn)行進(jìn)化操作，而不是針對參數(shù)本身，這使得GA不受函數(shù)約束條件的限制，如連續(xù)性、可導(dǎo)性個(gè)體。(2)GA的搜索過程是從問題解的一個(gè)集合開始，而不是從單個(gè)開始，具有隱含并行搜索特性，從而大大減小了陷入局部極小的可能。(3)GA使用的遺傳操作均是隨機(jī)操作，同時(shí)GA根據(jù)個(gè)體的適配值信息進(jìn)行搜索，無需其他信息，如導(dǎo)數(shù)信息等(4)GA具有全局搜索能力，最善于搜索復(fù)雜問題和非線性問題。GA相比于傳統(tǒng)優(yōu)化算法，具有以下的特點(diǎn)GA算法的優(yōu)越性(1)算法進(jìn)行全空間并行搜索，并將搜索重點(diǎn)集中于性能高的部分，從而能夠提高效率且不易陷入局部極小。(2)算法具有固有的并行性，通過對種群的遺傳處理可處理大量的模式，并且容易并行實(shí)現(xiàn)。遺傳算法的特點(diǎn)與優(yōu)點(diǎn)32GA遺傳算法專題知識例子1利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。

y=x2

31

XY34GA遺傳算法專題知識

分析

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問題。那么，［0,31］中的點(diǎn)x就是個(gè)體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(gè)(解)空間。這樣,只要能給出個(gè)體x的適當(dāng)染色體編碼,該問題就可以用遺傳算法來解決。35GA遺傳算法專題知識

解

(1)

設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應(yīng)度函數(shù),

取適應(yīng)度函數(shù)：f(x)=x2

(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體出現(xiàn)為止。

36GA遺傳算法專題知識

首先計(jì)算種群S1中各個(gè)體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)

的適應(yīng)度f(si)

容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=36137GA遺傳算法專題知識再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.3138GA遺傳算法專題知識●賭輪選擇法s40.31s20.49s10.14s30.06

賭輪選擇示意39GA遺傳算法專題知識

在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計(jì)算公式為40GA遺傳算法專題知識選擇-復(fù)制

設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù)如下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.00141GA遺傳算法專題知識于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。設(shè)s1’與s2’配對，s3’與s4’配對。分別交換后兩位基因，得新染色體：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

42GA遺傳算法專題知識變異設(shè)變異率pm=0.001。這樣，群體S1中共有

5×4×0.001=0.02位基因可以變異。

0.02位顯然不足1位，所以本輪遺傳操作不做變異。

于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）43GA遺傳算法專題知識

第二代種群S2中各染色體的情況

染色體適應(yīng)度選擇概率積累概率估計(jì)的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.00144GA遺傳算法專題知識

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體