遺傳算法講義3_slides.doc

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