遺傳算法講義3_slides.doc

第三章 遺傳算法的高級實現(xiàn)技術(shù)3.1 二倍體與顯性操作算子3.1.1 二倍體結(jié)構(gòu)的生物基礎(chǔ)生物學(xué)中，二倍體是指含有二個同源基因組(染色體)的個體。二倍體是由兩個同源染色體構(gòu)成的，其中的每一個染色體都含有相同功能的基因信息。二倍體結(jié)構(gòu)中各個基因有顯性基因和隱性基因之分，這二類基因使個體所呈現(xiàn)出的表現(xiàn)型由下述規(guī)則來決定（顯性規(guī)則）：在每個基因座上，當(dāng)兩個同源染色體其中之一的基因是顯性時，則該基因所對應(yīng)的性狀表現(xiàn)為顯性；而僅當(dāng)兩個同源染色體中對應(yīng)基因皆為隱性時，該基因所對應(yīng)的性狀才表現(xiàn)為隱性。顯性基因在純合子(AA)或雜合子(A或a)情況下均能被表現(xiàn)出，而隱性基因只能在純合子(aa)的情況下才能被表現(xiàn)出。二倍體的二個重要特性：1）二倍體的記憶能力，它使得生物能夠記憶以前經(jīng)歷過的環(huán)境及變化，使得生物的遺傳進化過程能夠快速地適應(yīng)環(huán)境的變化。這個特點在遺傳算法中的應(yīng)用意義就在于，使用二倍體結(jié)構(gòu)的遺傳算法能夠解決動態(tài)環(huán)境下的復(fù)雜系統(tǒng)優(yōu)化問題，而常規(guī)的遺傳算法卻不能很好地應(yīng)用于動態(tài)環(huán)境，它難于跟蹤環(huán)境的動態(tài)變化過程。2）顯性操作的魯律性，它使得即使隨機選擇了適應(yīng)度不高的個體，而在顯性操作的作用下，能夠用其另一同源染色體對其進行校正，從而避免這個有害選擇所帶來的不利之處。這個特點應(yīng)用于遺傳算法中，能有利于提高遺傳算法的運算效率維護好的搜索群體。3.1.2 二倍體結(jié)構(gòu)在遺傳算法中的實現(xiàn)方案Hollstien提出了二倍體與顯性操作的雙基因座顯性映射方法：每個二進制基因用兩個基因來描述，一個稱為函數(shù)基因，取通常含義的0或1值；另一個稱為修飾基因，取值為M或m，其中M表示顯性基因，m表示隱性基因。隨后，Hollstien將這種映射關(guān)系簡化為單基因座顯性映射方法。Holland對這種單基因座的顯性映射描述方法進行了改進。在這個單基因座顯性映射方法中，描述基因的字符集為0, 1, 10，其中10為隱性的1，1為顯性的1。雙基因座顯性映射方法 單基因座顯性映射方法使用雙倍體的遺傳算法的算法結(jié)構(gòu)與基本遺傳算法的算法結(jié)構(gòu)相類似，但也有些差別，其不同之處在于：(1)顯性性狀也能進化，所以同源染色體之間也需進行交叉操作。(2)變異操作需要考慮隱性性狀；(3)對個體進行交叉、變異運算之后，要進行顯性操作。使用雙倍體的遺傳算法可描述如下：算法DiploidyGA 初始化，并設(shè)置進化代數(shù)計數(shù)器初值：t=1。 隨機產(chǎn)生具有二倍體結(jié)構(gòu)的初始群體P(0)。 對初始群體P(0)進行顯性操作。 評價初始群體P(0)中各個個體的適應(yīng)度。 交叉操作：P(t)crossoverp(t)。由每兩個隨機配對的二倍體個體進行交又操作時，共可產(chǎn)生四個單倍體個體。 變異操作：P(t)mutationp(t)。在對群體中的各個個體進行變異操作時，需要考慮隱性基因的作用。 對群體P(t)進行顯性操作。 評價群體P(t)中各個個體的適應(yīng)度。 個體選擇、復(fù)制操作： 終止條件判斷。若不滿足終止條件，則: tt+1，轉(zhuǎn)到第步，繼續(xù)進行進化操作過程；若滿足終止條件則輸出當(dāng)前最優(yōu)個體，算法結(jié)束。3.2 變長度染色體遺傳算法在生物的進化過程中，其染色體的長度并不是固定不變的，而是隨著進化過程也在慢慢地變化著。在遺傳算法的實際應(yīng)用中有時為簡要地描述問題的解，也需要使用不同長度的編碼串。結(jié)點1和結(jié)點6之間的連通路線，可用以下二種方法來描述：(1)用二進制編碼來表示各個結(jié)點是否在連通路線上，其中l(wèi)表示在連通路線上，0表示不在連通路線上。此時可使用等長度的編碼串來表示連通路線，如：PATH1：1 1 0 0 1 1PATH2：1 1 1 1 1 1(2)用連通路線所經(jīng)過結(jié)點的順序排列來表示該條連通路線，如：PATH1：1256PATH2：123456該方法使用的就是變長度的染色體編碼方法。Goldberg等提出的MessyGA(簡稱MGA)是一種典型的變長度染色體遺傳算法。3.2.1 變長度染色體遺傳算法的編碼與解碼（MessyGA）編碼將常規(guī)遺傳算法的染色體編碼串中各基因座位置及相應(yīng)基因值組成一個二元組，把這個二元組按一定順序排列起來，就組成了變長度染色體的一種通用染色體編碼方式。一般它可表示為:ik是所描述約基因在原常規(guī)染色體中的基因座編號，vk為對應(yīng)的基因值。對于所需求解的問題，若使用常規(guī)遺傳算法時的染色體長度固定為l，各基因值取自集合V，則有例如，若常規(guī)遺傳算法中一個個體的基因型是：X：10010l其染色體長度為l6。使用變長度染色體編碼，該個體就可表示為：Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)在這種變長度染色體遺傳算法中，允許染色體的長度可長可短。如：Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0)Xm：(1，1)(3，0)(5，0)(6，1)前者稱為過剩指定，后者稱為缺省指定。而當(dāng)個體的所有基因都能在編碼串中得到唯一的描述時，這種描述稱為正常指定。解碼對變長度染色體進行解碼處理時，在正常指定情況下，將變長度染色體遺傳算法中的個體基因型轉(zhuǎn)換為常規(guī)遺傳算法中的個體基因型時不會有什么問題，而在過剩指定或缺省指定時，就會產(chǎn)生描述過剩或描述不足的問題，此時可按下述規(guī)則來進行解碼處理：(1)描述過剩時的解碼方法。此時，常規(guī)遺傳算法中的一個基因座可能在變長度染色體中同時有幾個對應(yīng)的二元組，規(guī)定取最左邊的二元組來進行解碼。例如，對于變長度染色體遺傳算法中的個體Xm：(1，1)(2，0)(3，0)(4，1)(5，0)(6，1)(3，1)(1，0)它在常規(guī)遺傳算法中所對應(yīng)的個體為：X：100101(2)描述不足時的解碼方法。此時，常規(guī)遺傳算法中有些基因座上的基因值未被在變長度染色體中明確地指定，這時可規(guī)定它們?nèi)∧骋豁椣仍O(shè)定的標準值(或缺省值)。例如，對于變長度染色體遺傳算法中的個體Xm：(1，1)(3，0)(5，0)(6，1)若取缺省值為0的話，則它在常規(guī)遺傳算法中所對應(yīng)的個體為：X：1000013.2.2 切斷算子與拼接算子變長度染色體遺傳算法除了使用常規(guī)遺傳算法中的選擇算子和變異算子之外，不再使用通用的交叉算子。而代之以使用下述的切斷算子和拼接算子，以它們作為產(chǎn)生新個體的主要遺傳算子。1切斷算子(Cut operator)切斷算子以某一預(yù)先指定的概率，在變長度染色體中隨機選擇一個基因座，在該處將個體的基因型切斷，使之成為二個個體的基因型。2拼接算子(Splice operator)拼按算子以某一預(yù)先指定的概率，將二個個體的基因型連接在一起，使它們合并為一個個體的基因型。3.2.3 變長度染色體遺傳算法的算法結(jié)構(gòu)變長度染色體遺傳算法的算法結(jié)構(gòu)可描述如下：算法MessyGA 初始化。隨機產(chǎn)生M個染色體，長度全部為k的個體，以它們作為變長度遺傳算法的初始個體集合P(0)，其中k為根據(jù)問題的不同而設(shè)定的一個參數(shù)，并且k l。 適應(yīng)廢評價。對變長度的染色體進行解碼處理后，評價或計算各個個體的適應(yīng)度。 基本處理階段。對群體P(t)施加選擇算子，以保留適應(yīng)度較高的個體。 并列處理階段。對群體P(t)施加變異算子、切斷算子和拼接算子，以生成新的個體。 重復(fù)第步，直到滿足終止條件為止。3.3 小生境遺傳算法在自然界，“人以群分，物以類聚”是一個司空見慣的現(xiàn)象。生物總是傾向于與自己特征、性狀相類似的生物(同類)生活在一起，一般總是與同類交配繁衍后代。這種正選型交配方式在生物遺傳進化過程中是有其積極的作用的。生物學(xué)上，小生境(niche)是指特定環(huán)境中一種組織(organism)的功能，而把有共同特性的組織稱作物種(species)。為了理解分類及小生境技術(shù)在遺傳優(yōu)化中的作用，我們先考察一下基本遺傳算法在單變量多峰函數(shù)優(yōu)化方面的搜索特性。等峰的單變量多極值點函數(shù) 變峰的單變量多極值點函數(shù)我們以均勻分布的隨機方式產(chǎn)生初始群體，則在算法的開始階段，各個體分布在一個相對較寬的函數(shù)定義域中；對于等峰的單變量多極值點函數(shù)，隨著遺傳優(yōu)化過程的進行，群體開始爬山，并逐步集中到一個山峰上。而對于變峰的單變量多極值點函數(shù)，基本遺傳算法的優(yōu)化結(jié)果將使群體集中到最高的一個山峰上。而在實際應(yīng)用中，我們有時需要了解問題空間內(nèi)其它山峰的情況，顯然，基本遺傳算法不能滿足這一性能要求。另外，基本遺傳算法采取的是一種隨機交配方式；而在生物界，交配則不完全是隨機的，至少有性別、區(qū)域以及物種類別等方面因素的制約。從遺傳算法角度來看，雖然隨機交配方式增強了開劈新的、可能是有用的搜索空間的能力，但由于缺乏對可能的交配效果(子代的質(zhì)量)方面的考慮，也會帶來交配的有效性以及優(yōu)化效率不太理想等方面的問題。為了解決這些問題，在遺傳算法中引入小生境技術(shù)已被一些實驗研究證實是種有效的嘗試。1基于預(yù)選擇機制的小生境技術(shù)1970年，Cavicchio率先在遺傳算法中引入了基于預(yù)選擇機制的小生境技術(shù)。只有在子串的適應(yīng)度超過其父串的情況下，子串才能替換其父串，進入下一代群體。由于這種方式趨向于替換與其本身相似的個體(父與子之間的性狀遺傳)，因而能夠較好地維持群體的分布特性。Cavicchio聲稱使用這種方法可以在群體規(guī)模相對較小的情況下維持較高的群體分布特性。2基于排擠機制的小生境技術(shù)1975年，De Jong一般化了Cavicchio的預(yù)選擇機制，提出了一種稱作排擠(crowding)機制的小生境技術(shù)。使用了群體的代間覆蓋方式，依據(jù)相似性替換群體中的個體。具體算法實現(xiàn)步驟如下：(1) 初始化;（建立初始群體，確定遺傳參數(shù)，設(shè)定排擠因子CF）(2) 計算個體的適應(yīng)度；(3) 遺傳操作(選擇、交叉和變異)；(4) 從當(dāng)前群體中隨機選取群體規(guī)模的1CF個個體組成排擠因子成員；(5) 比較新產(chǎn)生的個體與排擠因子成員之間的相似性；(6) 用新產(chǎn)生的個體去替換排擠因子成員中最相似的個體，形成新的當(dāng)前群體；(7) 如未滿足算法終止條件則返回第(2)步，否則算法終止。在優(yōu)化的初始階段，由于群體中個體間的相似性相差不大，個體的更新替換呈隨機選擇特性；隨著遺傳優(yōu)化的進展，群體中的個體逐步被分類，形成若干個小生境，此時，基于個體相似性的替換技術(shù)可在一定程度上維持群體的分布持性，并為更進一步的分類和小生境的形成騰出空間。De Jong曾將這一技術(shù)應(yīng)用到多峰函數(shù)的遺傳優(yōu)化上，獲得了比較滿意的效果。3基于共享(sharing)機制的小生境技術(shù)1987年，Goldberg和Richardson提出了一種基于共享(sharing)機制的小生境技術(shù)。定義了共享函數(shù)(sharing function)，用來確定每個個體在群體中的共享度。一個個體的共享度等于該個體與群體內(nèi)的各個其它個體之間的共享函數(shù)值的總和。共享函數(shù)是關(guān)于兩個體之間的關(guān)系密切程度(基因型的相似性或表現(xiàn)型的相似性)的函數(shù)，當(dāng)個體間關(guān)系比較密切時，共享函數(shù)值較大，反之，則共享函數(shù)值較小。設(shè)dij表示個體i和個體j之間的關(guān)系密切程度，S為共享函數(shù)，Si表示個體i在群體中的共享度，則有：在計算了各個體的共享度后，個體的適應(yīng)度f(i)依據(jù)下式調(diào)整為fs(i)：顯然，這種機制限制了群體內(nèi)某一特殊“物種”的無控制的增長。圖3.7圖3.10顯示了引入基于共享機制的小生境技術(shù)的遺傳算法(GA)與基本遺傳(sGA)算法在多峰函數(shù)優(yōu)化方面的搜索特性差異。SGA優(yōu)化等峰單變量多極 基于小生境GA優(yōu)化等峰單變量值點函數(shù)的解群分布趨勢 多極值點函數(shù)的解群分布趨勢SGA優(yōu)化變峰單變量多極 基于小生境GA優(yōu)化變峰單變量值點函數(shù)的解群分布趨勢 多極值點函數(shù)的解群分布趨勢3.4 混合遺傳算法3.4.1 混合遺傳算法的思想應(yīng)用實踐表明，在遺傳算法的應(yīng)用中也會出現(xiàn)一些不盡人意的問題，這些問題中最主要的是它容易產(chǎn)生早熟現(xiàn)象、局部尋優(yōu)能力較差等。另外，遺傳算法也無法避免多次搜索同一個可行解，這也是影響遺傳算法運行效率的一個因素。另一方面，梯度法、爬山法、模擬退火算法、列表尋優(yōu)法等一些優(yōu)化算法卻具有很強的局部搜索能力，而另一些含有與問題相關(guān)知識的啟發(fā)式算法的運行效率也比較高。在遺傳算法的搜索過程中融合這些優(yōu)化方法的思想、構(gòu)成一種混合遺傳算法(Hybrid Genetic Algorithm)是提高遺傳算法運行效率和求解質(zhì)量的一個有效手段。一種基本的混合遺傳算法構(gòu)成框架。由可以看出這種混合遺傳算法是在標準遺傳算法中融合了局部搜索算法的思想，其特點主要體現(xiàn)在以下二個方面：(1)引入了局部搜索過程?；谌后w中各個個體所對應(yīng)的表現(xiàn)型，進行局部搜索，從而找出各個個體在目前的環(huán)境下所對應(yīng)的局部最優(yōu)解，以便達到改善群體總體性能的目的。(2)增加了編碼變換操作過程。對局部搜索過程所得到的局部最優(yōu)解，再通過編碼過程將它們變換為新的個體，以便能夠以一個性能較優(yōu)的新群體為基礎(chǔ)來進行下一代的遺傳進化操作?；旌线z傳算法的基本構(gòu)成原則在構(gòu)成混合遺傳算法時，De Jong提出了下面的三條基本原則：(1)盡量采用原有算法的編碼。這樣就便于利用原有算法的相關(guān)知識，也便于實現(xiàn)混合遺傳算法。(2)利用原有算法的優(yōu)點。這樣就可保證由混合遺傳算法所求到的解的質(zhì)量不會低于由原有算法所求到的解的質(zhì)量。(3)改進遺傳算子。設(shè)計能適應(yīng)新的編碼方式的遺傳算子，并在遺傳算子中溶入與問題相關(guān)的啟發(fā)式知識，這樣就可使得混合遺傳算法既能夠保持遺傳算法的全局尋優(yōu)特點，又能夠提高其運行效率。3.4.2 模擬退火算法在金屬熱加工工藝中，退火是指將金屬材料加熱到某一高溫狀態(tài)，然后讓其慢慢冷卻下來這樣一個金屬熱處理過程。從統(tǒng)計熱力學(xué)的觀點來說，隨著溫度的降低，物質(zhì)的能量將逐漸趨近于一個較低的狀態(tài)，并最終達到某種平衡。模擬退火算法(Simulated Annealing)就是基于金屬退火的機理而建立起的一種全局最優(yōu)化方法，它能夠以隨機搜索技術(shù)從概率的意義上找出目標函數(shù)的全局最小點。模擬退火算法的構(gòu)成要素如下：1搜索空間搜索空間也稱為狀態(tài)空間，它由可行解的集合所組成，其中一個狀態(tài)x就代表一個可行解。2能量函數(shù)E(x)能量函數(shù)也就是需要進行優(yōu)化計算的目標函數(shù)所求的最優(yōu)解。3狀態(tài)轉(zhuǎn)移規(guī)則P狀態(tài)轉(zhuǎn)移規(guī)則是指從一個狀態(tài)xold(一個可行解)向另一個狀態(tài)xnew(另一個可行解)的轉(zhuǎn)移概率，它與當(dāng)前的溫度參數(shù)T有關(guān)。4冷卻進度表T(t)冷卻進度表是指從某一高溫狀態(tài)To向低溫狀態(tài)冷卻時的降溫管理表。假設(shè)時刻t的溫度用T(t)來表示，則經(jīng)典模擬退火算法的降溫方式為：而快速模擬退火算法的降溫方式為：這兩種方式都能夠使得模擬退火算法收斂于全局最小點。另外，在實際應(yīng)用中，為計算簡便起見，也可用下式來進行溫度管理：式中，k為略小于1.0的系數(shù)。假設(shè)圖所示為某一能量函數(shù)的描述圖形。如果搜索過程陷入局部最優(yōu)點A，若要使搜索過程脫離這個局部員優(yōu)點而到達C點，則必須使系統(tǒng)至少要具有B點所對應(yīng)的能量。亦即，這里必須允許能量函數(shù)值可以一時增大。假設(shè)在狀態(tài)xold時，系統(tǒng)受到某種擾動而可能會使其狀態(tài)變?yōu)閤new。與此相對應(yīng)，系統(tǒng)的能量也可能會從E(xold)變成E(xnew)，系統(tǒng)由狀態(tài)xold變?yōu)闋顟B(tài)xnew的接受概率可由下面的Meteopolis規(guī)則來確定：上式的含義是：當(dāng)新狀態(tài)使系統(tǒng)的能量函數(shù)值減少時，系統(tǒng)一定接受這個新的狀態(tài)；而當(dāng)新狀態(tài)使系統(tǒng)的能量函數(shù)值增加時，系統(tǒng)也以某一概率接受這個新的狀態(tài)。固定溫度參數(shù)T，反復(fù)進行狀態(tài)轉(zhuǎn)移過程，接收概率p(x)將服從Gibbs分布：式中，Z是使概率值正規(guī)化的系數(shù)。由上式可見，隨著溫度參數(shù)T的減小，接收概率也逐漸減小，即能量函數(shù)增大的可能性也逐漸減小，最后系統(tǒng)會收斂于某一能量最小的狀態(tài)，該狀態(tài)就可作為目標函數(shù)的全局最小值。模擬退火算法可描述如下：算法Simulated Annealing 隨機產(chǎn)生一個初始最優(yōu)點，以它作為當(dāng)前最優(yōu)點，并計算目標函數(shù)值。 設(shè)置初始溫度：T=To。 設(shè)置循環(huán)計數(shù)器初值：t=1。 對當(dāng)前最優(yōu)點作一隨機變動,產(chǎn)生一新的最優(yōu)點。計算新的目標函數(shù)值，并計算目標函數(shù)值的增量D。 如果D0，則接受該新產(chǎn)生的最優(yōu)點為當(dāng)前員優(yōu)點； 如果D0，則以概率p = exp(-D/T)接受該新產(chǎn)生的愚優(yōu)點為當(dāng)前最優(yōu)點。 如果t終止步效，則：t=t+1，轉(zhuǎn)向第步。 如果未到達冷卻狀態(tài)，則：T=T(t)轉(zhuǎn)向第步； 如果已到達冷卻狀態(tài)，則：輸出當(dāng)前最優(yōu)點，計算結(jié)束。3.4.3 遺傳模擬退火算法遺傳模擬退火算法是將遺傳算法與模擬退火算法相結(jié)合而構(gòu)成的一種優(yōu)化算法。遺傳算法的局部搜索能力較差、但把握搜索過程總體的能力較強；而模擬退火算法具有較強的局部搜索能力，并能使搜索過程避免陷入局部最優(yōu)解，但模擬退火算法卻對整個搜索空間的狀況了解不多，不便于使搜索過程進入最有希望的搜索區(qū)域。如果將遺傳算法與模擬退火算法相結(jié)合，互相取長補短，則有可能開發(fā)出性能優(yōu)良的新的全局搜索算法，這就是遺傳模擬退火算法的基本思想。與基本遺傳算法的總體運行過程相類似，遺傳模擬退火算法也是從一組隨機產(chǎn)生的初始解(初始群體)開始全局最優(yōu)解的搜索過程，它先通過選擇、交叉、變異等遺傳操作來產(chǎn)生一組新的個體，然后再獨立地對所產(chǎn)生出的各個個體進行模擬退火過程，以其結(jié)果作為下一代群體中的個體。這個運行過程反復(fù)迭代地進行，直到滿足某個終止條件為