遺傳算法講義3_slides.doc

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