《神經(jīng)網(wǎng)絡(luò)控制》課件第8章

第8章神經(jīng)控制中的遺傳進(jìn)化訓(xùn)練8.1生物的遺傳與進(jìn)化8.2遺傳算法概述8.3遺傳算法中的模式定理8.4遺傳算法中的編碼操作8.5遺傳算法中的適應(yīng)度函數(shù)8.6遺傳算法與優(yōu)化解8.7遺傳算法與預(yù)測控制8.8遺傳算法與神經(jīng)網(wǎng)絡(luò)8.9神經(jīng)網(wǎng)絡(luò)的遺傳進(jìn)化訓(xùn)練8.10小結(jié)習(xí)題與思考題

8.1生物的遺傳與進(jìn)化

按照時(shí)下流行的觀點(diǎn)，在距今約150億年前，宇宙是由一個(gè)半徑為3mm的球內(nèi)炙熱而又稠密的物質(zhì)與能量經(jīng)過“大爆炸”而形成的。茫茫宇宙、無邊無際，用當(dāng)代最為先進(jìn)的手段觀測，能察知宇宙間的星系約有800～1250億個(gè)。而每一個(gè)星系中大約有1000億個(gè)類似于太陽的恒星。悠悠歲月，無始無終，太陽系八大行星之一的地球年齡已有46億年。具有生命特征的生物在地球上出現(xiàn)、進(jìn)化與發(fā)展，距今約有36億年。這種進(jìn)化的直接結(jié)果是在200～500萬年前出現(xiàn)了人類。人類大腦的發(fā)展已歷經(jīng)50萬年，而人類有記載的文明史約有5000年，人們依靠科學(xué)技術(shù)，享受高質(zhì)量生活水平的歷史約200年左右，瓦特(JamesWatt，1736—1819)發(fā)明蒸汽機(jī)是現(xiàn)代人類文明開始的標(biāo)志。

今天，當(dāng)人們環(huán)顧浩渺宇宙空間及生物發(fā)展進(jìn)化的36億年時(shí)間長河時(shí)，雖然迄今為止人類還未解開生命如何起源，還未求證宇宙中億萬星球上是否還有其他生命，但是生物有36億年的遺傳進(jìn)化發(fā)展史，還是給了人們無數(shù)有益的啟示。8.1.1生物進(jìn)化論的基本觀點(diǎn)

19世紀(jì)以來，人們有意識(shí)地通過生物觀察、選擇實(shí)驗(yàn)、雜交育種等，對生物的遺傳、進(jìn)化、發(fā)展進(jìn)行了有效的探討，逐步形成了“生物進(jìn)化論”這門學(xué)科。

1859年，英國生物學(xué)家達(dá)爾文(C．R．Darwin)發(fā)表《物種起源》一書，提出了物競天演、適者生存、優(yōu)勝劣汰的生物進(jìn)化論學(xué)說，闡明了生物發(fā)展以自然選擇為基礎(chǔ)。達(dá)爾文的生物進(jìn)化論具有劃時(shí)代的意義。

1866年，奧地利植物學(xué)家蒙得爾(G．Mendel)在系統(tǒng)總結(jié)及概括前人實(shí)驗(yàn)的基礎(chǔ)上，發(fā)表了論文《植物雜種實(shí)驗(yàn)》，開創(chuàng)了實(shí)驗(yàn)遺傳學(xué)。此后，H．deVries提出了突變論。W．L．Johannse提出了基因概念、純系理論。20世紀(jì)初，T．H．Morgen通過對遺傳學(xué)和細(xì)胞學(xué)的研究建立了基因理論。1952年，A．D．Hershey在實(shí)驗(yàn)的基礎(chǔ)上，成功地證明了DNA(脫氧核糖核酸，DesoxyribonucleicAcid)是遺傳物質(zhì)。今天，檢測DNA已經(jīng)成為親子鑒定的科學(xué)手段。

生物進(jìn)化論的基本觀點(diǎn)是：生物的發(fā)展與進(jìn)化有三種主要形態(tài)，這就是遺傳、變異和選擇。

自然界中的生命千姿百態(tài)，地球上的幾百萬種生物相互扶持、相互依存、相互成鏈。千奇百怪的各種生物在數(shù)十億年的進(jìn)化中，適應(yīng)環(huán)境，繁衍后代，頑強(qiáng)地生存下來。在人與自然和諧相處中不難發(fā)現(xiàn)這一點(diǎn)。各種生物進(jìn)化的方法和結(jié)果雖然不相同，但是仍然可以找到生物在進(jìn)化過程中的共同點(diǎn)，這些共同點(diǎn)表現(xiàn)在如下幾個(gè)方面：

(１)染色體(Chromosome)具有遺傳功能，遺傳功能的最小操作單位是基因(Gene)，DNA是遺傳物質(zhì)。對DNA的檢測與鑒定，就是測定子女系中是否有父母親的遺傳物質(zhì)，這是實(shí)現(xiàn)生物親子鑒定的科學(xué)依據(jù)。

(２)染色體是信息的載體，它把父輩的信息傳遞給子輩。生物進(jìn)化發(fā)生在信息載體(染色體)上，而不是發(fā)生在被編碼的生物個(gè)體上。例如有人做過砍老鼠尾巴試驗(yàn)，人為連續(xù)地砍掉若干老鼠的尾巴，但它們新生出的老鼠照樣有尾巴。這個(gè)實(shí)驗(yàn)明確告訴人們，什么東西會(huì)遺傳，什么東西不會(huì)遺傳。

(３)對于染色體最小遺傳功能操作單位基因，可使用人為手段給予重構(gòu)，形成轉(zhuǎn)基因產(chǎn)品或產(chǎn)生新的動(dòng)植物品種。近代遺傳工程的兩大任務(wù)是：對基因破譯并重構(gòu)。

(４)染色體具有變異功能，這種變異往往會(huì)突變，突變的結(jié)果是子代染色體不同于母代。變異功能帶來兩個(gè)結(jié)果：

一是生物能在進(jìn)化的廣大可能空間中，快速有效地選擇繁衍后代的形式，適應(yīng)復(fù)雜惡劣的生存空間；二是長期(幾十億年)的變異，原始生命歷經(jīng)大約1×1017s(約36×108年)的進(jìn)化過程，形成千奇百怪、形態(tài)各異、有不同生存本領(lǐng)的動(dòng)植物。

(５)染色體具有選擇功能。這個(gè)染色體和那個(gè)染色體復(fù)制的機(jī)會(huì)并不均等，對于不同編碼個(gè)體的染色體而言，成功適應(yīng)環(huán)境的染色體存在更多機(jī)會(huì)復(fù)制，能孕育出更有優(yōu)勢的后代。例如某些病毒或細(xì)菌，就能復(fù)制產(chǎn)生有抗藥性的后代，致使曾經(jīng)殺菌能力極強(qiáng)的青霉素療效減退，而那些無力抵抗青霉素的病毒個(gè)體或細(xì)菌個(gè)體被消滅。

(６)染色體的傳遞無記憶功能，導(dǎo)致生物的進(jìn)化無法記憶。這一進(jìn)化原則有三層含義：

①一代生物是否進(jìn)化與上一代生物是否進(jìn)化之間沒有聯(lián)系；②上一代生物的進(jìn)化不會(huì)把記憶留給下一代，否則，今天的人類不僅能夠記住500萬年以前人類是如何產(chǎn)生的，還能記得36億年前具有生命特征的生物是如何產(chǎn)生的；

③無論哪一代生物，進(jìn)化的原則是那一代生物根據(jù)生存環(huán)境來獲取更好的生存機(jī)會(huì)和繁殖條件。8.1.2進(jìn)化計(jì)算

進(jìn)化計(jì)算(EvolutionaryComputation)是20世紀(jì)60年代興起的一門學(xué)科，它的研究內(nèi)容是仿照生物進(jìn)化過程，按照優(yōu)勝劣汰的自然選擇，探討優(yōu)化的規(guī)律與方法。

優(yōu)化問題是數(shù)學(xué)中的一個(gè)重要研究分支?，F(xiàn)代控制理論中的一個(gè)重要議題，就是在眾多系統(tǒng)解中尋求一個(gè)最優(yōu)解。進(jìn)化計(jì)算的提出，給優(yōu)化問題求解提供了一種用傳統(tǒng)方法較難求解的新方法。

進(jìn)化計(jì)算有三種不同的計(jì)算法，它們是遺傳算法(GeneticAlgorithm)、進(jìn)化規(guī)劃(EvolutionaryProgramming)和進(jìn)化策略(EvolutionaryStrategy)。１．遺傳算法(ＧＡ)

遺傳算法是一種模擬生物遺傳理論建立起來的自適應(yīng)、概率性迭代搜索算法，突出“適者生存、不適者淘汰”的競爭機(jī)制。

遺傳算法的解題思路是從一組隨機(jī)產(chǎn)生的初始解開始，沿著某一確定的方向搜索。這一組隨機(jī)產(chǎn)生的初始解統(tǒng)稱為“種解”，種解中的每一個(gè)個(gè)體，也就是每一個(gè)初始解都被稱為“染色體”。在搜索中對每一個(gè)染色體適應(yīng)環(huán)境的程度隨時(shí)做出評價(jià)，以判斷染色體的優(yōu)劣。適應(yīng)能力強(qiáng)的染色體被選擇的幾率大；適應(yīng)能力弱的染色體被選擇的幾率小。被選擇的染色體及時(shí)進(jìn)入下一代，通過交叉、變異等遺傳操作，形成新的染色體。這樣經(jīng)過若干代以后，算法最終收斂于最好的染色體，該染色體就是所求問題的最優(yōu)解。

遺傳算法求解問題的流程如圖8-1所示。圖8-1遺傳算法求解流程圖遺傳算法運(yùn)算過程歸納如下：

①隨機(jī)產(chǎn)生初始種群Ｍ(t)。

②用適應(yīng)度函數(shù)u(ｍ)評價(jià)Ｍ(t)中每個(gè)染色體ｍ，評價(jià)方法是計(jì)算每個(gè)染色體ｍ的適應(yīng)度函數(shù)u(ｍ)，不同的染色體有不同的計(jì)算結(jié)果。

③通過選擇、變異產(chǎn)生新的染色體進(jìn)入下一代，染色體被選中的概率ｐ(ｍ)與該染色體的適應(yīng)度函數(shù)u(ｍ)成正比：ｐ(ｍ)∝u(ｍ)。

④按概率大小由遺傳算子進(jìn)行選擇，產(chǎn)生新的染色體形成新的種群Ｍ(t＋１)。

⑤重復(fù)②～④，直至完成事先預(yù)定的要進(jìn)化的代數(shù)。

2．進(jìn)化規(guī)劃(eＰ)

進(jìn)化規(guī)劃是一種模擬生物自然進(jìn)化的自上而下的優(yōu)化設(shè)計(jì)方法。在自然界，每種動(dòng)植物，從低等生物到高等智能生物，都要迎接生存的挑戰(zhàn)，包括適應(yīng)嚴(yán)酷的環(huán)境、尋求足夠的食物、爭取安全的場所、有效地繁衍后代。這種對環(huán)境的響應(yīng)就是一種“規(guī)劃行為”。

進(jìn)化規(guī)劃討論的主要議題如下：

(１)生物進(jìn)化是否成功要以整體行為作為衡量標(biāo)準(zhǔn)，不能以個(gè)別染色體是否成功為衡量標(biāo)準(zhǔn)，也不能從個(gè)別組成是否好壞來衡量整體。

(２)生物進(jìn)化首要考慮的問題是對環(huán)境行為如何做出響應(yīng)，而不必考慮這個(gè)響應(yīng)是如何產(chǎn)生的。

(３)進(jìn)化規(guī)劃實(shí)質(zhì)上是一個(gè)不斷變異、不斷再生的迭代過程，迭代是對進(jìn)化過程的一種模擬。染色體作為一個(gè)個(gè)體，在不斷變異、不斷再生并優(yōu)化的進(jìn)程中，要從種群全局

角度去處理。因此，進(jìn)化規(guī)劃重點(diǎn)討論的問題不是染色體的變異和選擇，而是種群的變異和選擇。進(jìn)化規(guī)劃的規(guī)則是：自上而下考慮整體的全局優(yōu)化。

例如一曲音樂中，一個(gè)音符的優(yōu)化要服從整個(gè)樂曲的要求。一個(gè)阿拉伯?dāng)?shù)字的價(jià)值不在它自身，而在它位于一個(gè)數(shù)的哪個(gè)位置上。

進(jìn)化規(guī)劃的運(yùn)行規(guī)則是：自上而下考慮整體的全局優(yōu)化。３．進(jìn)化策略(eＳ)

進(jìn)化策略是在1973年由德國數(shù)學(xué)家IngoRechenberg提出的。隨后由HansPaulSchwefel發(fā)展并用于數(shù)字優(yōu)化。

進(jìn)化策略的含義是：

生物在長達(dá)36億年的漫長進(jìn)化歲月中，能夠?qū)⑼瓿蛇M(jìn)化所使用的方法等價(jià)成一個(gè)機(jī)智優(yōu)化過程，這個(gè)過程中存在一個(gè)進(jìn)化策略的理論。既然是“策略”，事實(shí)上就是生物從結(jié)構(gòu)

及演化兩個(gè)方面如何得到優(yōu)化。

進(jìn)化策略理論的最基本觀點(diǎn)如下：

(1)進(jìn)化過程優(yōu)化了生物；

(2)進(jìn)化自身是一個(gè)生物過程；

(3)進(jìn)化必定將“進(jìn)化”自身優(yōu)化。

進(jìn)化過程不僅對染色體的生存隨時(shí)做出應(yīng)有的貢獻(xiàn)，而且更為重要的，是在若干代染色體的變異中選擇較好的遺傳策略，目的是為了更好地適應(yīng)環(huán)境。

只有講究策略，生物的進(jìn)化過程才能形成優(yōu)化過程。

４．進(jìn)化計(jì)算的評價(jià)

無論是GA、EP，還是ES，它們都是圍繞“優(yōu)勝劣汰”的自然法則求解工程技術(shù)中的優(yōu)化問題，它們的區(qū)別在于實(shí)施方法與步驟不同。表8-1列出了三種計(jì)算法的不同之處。

研究進(jìn)化計(jì)算的意義，不僅僅在于思考３０多億年來生物從原始到高級(jí)智能的變異過程，也不僅僅在于思考一種全新的優(yōu)化模型和優(yōu)化方法，更為重要的是認(rèn)識(shí)在智能仿生

過程中自然界賦予生命的哲理和游戲規(guī)則，為人類進(jìn)一步改造大自然，與大自然和諧相處提供科學(xué)的思維方法。對進(jìn)化計(jì)算提出以下一些評價(jià)：

(１)進(jìn)化計(jì)算的目的是求優(yōu)化解，因此在工程技術(shù)中適用面廣、移植性強(qiáng)。進(jìn)化計(jì)算所遇到的遺傳、交叉、變異操作，都是針對染色體編碼序列中的基因進(jìn)行的，而工程技

術(shù)中的計(jì)算都可以轉(zhuǎn)化成編碼序列模型來表示。

(２)進(jìn)化計(jì)算是一種并行處理的運(yùn)算，源自并行處理種群中各種染色體的變異，以及并行處理染色體中各基因組成成分的相關(guān)碼元。并行處理功能使它對復(fù)雜優(yōu)化問題有較

快的求解速度。

(３)進(jìn)化計(jì)算中涉及到的適應(yīng)度函數(shù)僅與優(yōu)化問題相聯(lián)系，對適應(yīng)度函數(shù)自身的限制較少，這就對適應(yīng)度函數(shù)的選擇提供了較寬的范圍，例如甚至不要求連續(xù)、可導(dǎo)等作為約束條件。

(４)遺傳操作(如選擇、交叉或變異)都是按概率在解空間進(jìn)行有目標(biāo)、有方向的啟發(fā)式搜索，既不同于盲目的窮舉，也不同于隨機(jī)查詢。

(５)選擇操作通過粗調(diào)與微調(diào)有機(jī)結(jié)合進(jìn)行，交叉操作是在足夠大的范圍內(nèi)進(jìn)行信息重組，變異操作則是通過基因突變實(shí)現(xiàn)優(yōu)化。這些操作能有效避開求解空間的局部極小

點(diǎn)，以較快速度達(dá)到全局最優(yōu)解。

(6)進(jìn)化計(jì)算存在著三個(gè)問題：

第一個(gè)問題是進(jìn)化計(jì)算是一門由人類創(chuàng)立的技術(shù)，是人們頭腦中對生物進(jìn)化過程的模擬思考，它不同于生物的實(shí)際進(jìn)化過程——一種客觀存在的歷史發(fā)展。兩者本質(zhì)的區(qū)別決定了進(jìn)化計(jì)算總會(huì)有誤差。

第二個(gè)問題是按概率進(jìn)行操作的進(jìn)化計(jì)算優(yōu)化算法，不能保證100％找到全局最優(yōu)化解。能100%找到全局最優(yōu)化解的只能用其它方法,例如窮舉法(TryAll

Possibilities)。就目前已知的事實(shí)，肯定能找到全局最優(yōu)解的唯一算法是窮舉法。

第三個(gè)問題是進(jìn)化計(jì)算不是求解最優(yōu)的首選，只要能使用線性規(guī)劃、動(dòng)態(tài)規(guī)劃、擬牛頓法等傳統(tǒng)方法，就不要使用進(jìn)化計(jì)算。

8.2遺傳算法概述

8.2.1遺傳算法中遇到的基本術(shù)語

染色體(Chromosome)：生物遺傳、繁殖的基本單位，又稱個(gè)體。

種群(Population)：多個(gè)染色體的集合，染色體與染色體之間存在生命特征的有機(jī)聯(lián)結(jié)。進(jìn)化之初的最原始種群稱為初始種群?；?Gene)：遺傳、繁殖的最小單位，多個(gè)基因按一定的排列方式組成染色體。

編碼(Coding)：將搜索空間的解映射到遺傳空間時(shí)，解的按序組合稱為編碼。例如依次走訪８個(gè)城市，從城市３開始，訪問順序?yàn)?→6→8→1→2→5→4→7，可以用編碼36812547表示走訪路線。

適應(yīng)度(Fitness)：適應(yīng)度函數(shù)的簡稱，解的目標(biāo)函數(shù)值，能衡量染色體的好壞。8.2.2遺傳算法的運(yùn)算特征

１．遺傳算法的特點(diǎn)

(１)遺傳算法是對解集合的編碼進(jìn)行運(yùn)算，而不是對解集合進(jìn)行運(yùn)算。

(２)遺傳算法的搜索開始于解的一個(gè)種群，而不是其中的個(gè)別解。

(３)遺傳算法只用適應(yīng)度評價(jià)解的優(yōu)劣。

(４)搜索方法用的是概率搜索，而不是路徑搜索。２．遺傳算法的基本操作

遺傳算法的基本操作有三種：選擇、交叉和變異。

１)選擇(Selection)

所謂選擇，是指從種群中按一定的標(biāo)準(zhǔn)選定適應(yīng)做親本的染色體。選擇的目的是為了將適應(yīng)的染色體交配后復(fù)制出子代。

選擇的方法較多，常用的有適應(yīng)度概率法、排序法、期望值法等多種，其中又以適應(yīng)度概率法最為簡潔有效，下面舉例介紹。適應(yīng)度概率法通過計(jì)算染色體被選中的概率來完成選擇。設(shè)種群中染色體i的適應(yīng)度函數(shù)為fi，種群中共有N個(gè)染色體，染色體i被選中做親本的概率pi為：式中，k的取值可為正整數(shù)。例如N＝10，k＝1，2，3，按上式計(jì)算得到概率pi如表8-2所示。從k＝１，２，３的概率取值能觀測到：

(1)適應(yīng)度函數(shù)fi越大，被選中的概率越大；

(2)k值越大，適應(yīng)度高的染色體概率越大；

(3)概率一旦確定，概率大的染色體有更多的機(jī)會(huì)參加交配，復(fù)制的遺傳因子能在種群中擴(kuò)大。

2)交叉(Crossover)

交叉又稱重組(Recombination)，其含義為兩個(gè)染色體的基因進(jìn)行互換產(chǎn)生新的后代。交叉的方式有單點(diǎn)交叉、雙點(diǎn)交叉、按序交叉和位置交叉等。

(1)單點(diǎn)交叉(Onepoint)：單點(diǎn)交叉是指在染色體中隨機(jī)取某一基因位，從此位開始互換兩父本后面的序列，產(chǎn)生兩個(gè)子代，如表8-3所示，該表從a4、b4開始交換。

(2)雙點(diǎn)交叉(Doublepoint)：雙點(diǎn)交叉是指在染色體中隨機(jī)選取兩個(gè)基因位，交換選取兩位之間的基因位置，如表8-4所示，該表將a2~a6與b2~b6交換。

(3)按序交叉(Orderbased):按序交叉是按照一定次序生成子代的交叉操作。有兩個(gè)父本分別為父本1、父本2，它

們有相同的基因，但排序次序不同。將父本在兩個(gè)交叉點(diǎn)間的部分復(fù)制，成為子代的一部分，如：可得子代1的一部分，子代1余下的4個(gè)基因應(yīng)當(dāng)從父本余下基因中去選擇。從父本2中去掉a5a7a2和a9a1a4，從a3開始轉(zhuǎn)至父本2的第1個(gè)基因a6繼續(xù)。即子代1余下的4個(gè)基因?yàn)閍3a6a8a10同理，子代2的10個(gè)基因?yàn)?/p>

子代2a9a1a4

a5a7a2

a6a10a8a3

由此形成的結(jié)果如表8-5所示。

(4)位置交叉(Positionbased)：設(shè)有兩個(gè)父本分別為父本1、父本2，子代1的生成方法是：

在父本1中隨機(jī)選幾個(gè)位置的基因，子代1的位置繼承父代1的相同位置基因，如：子代1余下的位置從父本2中的基因選取，但要從父本2中去掉85462，余下的按從左到右的順序取出，即

還余1、3、7、10、9，填入得

子代2按此辦理，由此形成的結(jié)果如表8-6所示。

與選擇操作相比較，交叉操作能使基因排序變化更加靈活，實(shí)現(xiàn)真正意義上的人為重組，適于大范圍操作。

3)變異(Mutation)

變異是使染色體中的基因按照概率的變化進(jìn)行重新排列。以二進(jìn)制編碼方式為例，所謂變異就是將基因值取反，將“0”變“1”，將“1”變“0”。由于變值的范圍有限，搜索范圍小

于交叉操作。

現(xiàn)以解決TSP組和優(yōu)化問題為例，設(shè)父本的基因?yàn)?23456789，變異操作的種類較多，現(xiàn)列舉其中的三種：

(1)SWAP為對調(diào)兩個(gè)基因的位置；

(2)RAR為在新位置插入基因；

(3)Inversion為將一段基因逆轉(zhuǎn)。

表8-7就是變異操作的一個(gè)例子。8.2.3遺傳算法中的概率計(jì)算公式

在對父本的基因進(jìn)行選擇、交叉或變異的相關(guān)操作時(shí)，基因被復(fù)制的幾率就是概率，概率越大，選做親本的機(jī)會(huì)就會(huì)越多。為了計(jì)算不同操作情況下的概率，先做出如下一些

假設(shè)：

設(shè)表征基因組模式用一串二進(jìn)制位(比特，bit)表示，其中每一位的取值用“０”、“１”或“*”表示，“*”指該位或者是０、或者是１。例如一個(gè)基因組模式的二進(jìn)制序列為

1*0*01

表示它們4種可能取值：該序列的長度為6，序列長度常用L表示，基因模式常用H表示。在一個(gè)二進(jìn)制序列中，經(jīng)常要截取其中某些位。截取確定基因位置的長度用d表示，d又稱為直徑。例如基因組模式二進(jìn)制序列

1*0*01取第4～6位*01，其直徑d=3。設(shè)f為待優(yōu)化的函數(shù)，定義在長度為L的二進(jìn)制序列上，函數(shù)f又稱為適應(yīng)度函數(shù)，簡稱適應(yīng)度。

選擇、交叉或變異等遺傳基本操作，都是對兩個(gè)或兩個(gè)以上的父本進(jìn)行操作，生成若干不同的子代。一般情況下，每一個(gè)父本用一個(gè)二進(jìn)制序列表示，考慮N個(gè)序列的操作。

從N個(gè)序列x1、x2、…、xN中選中xj為親本序列的概率為上式表明，適應(yīng)度函數(shù)大的序列被選中的概率大。

如果用f表示種群所有序列適應(yīng)度的平均值，即則概率公式為

8.3遺傳算法中的模式定理

遺傳算法是模擬生物進(jìn)化過程這一自然界運(yùn)動(dòng)規(guī)律的計(jì)算方法，由于進(jìn)化過程的時(shí)間有數(shù)十億年，使得模擬算法本身自然、直接且又樸素。它沒有嚴(yán)密的數(shù)學(xué)推導(dǎo)作為理論基

礎(chǔ)，總是圍繞著選擇、交叉、變異等基本操作進(jìn)行。截至目前為止，尚無足夠的基礎(chǔ)理論來闡明遺傳算法的運(yùn)算特征。而其它計(jì)算算法，則需要嚴(yán)密的數(shù)學(xué)推導(dǎo)作為理論基礎(chǔ)。

目前有幾種描述遺傳算法運(yùn)算特征的方法，如“模式定理”、“基因塊假設(shè)”、“Walsh模式變換”等幾種，其中以“模式定理”較為成熟。8.3.1模式定義和模式的階

模式定理最早由Holland提出，后經(jīng)許多人不斷完善，現(xiàn)已成為遺傳算法最成熟的理論。模式定理的主要內(nèi)涵是解釋染色體編碼結(jié)構(gòu)在進(jìn)化過程中的應(yīng)用。

1.搜索空間的規(guī)模

設(shè)物體空間或搜索空間為Ω，在此空間內(nèi)包含所有可能的染色體編碼，設(shè)染色體采用k進(jìn)制編碼，染色體長度為L，則搜索空間的規(guī)模為kL。

例如對種群

f(x)=xsin(100x)－0.1

編碼，x的取值范圍［0，0.1］，函數(shù)圖形如圖8-2所示。圖8-2f(x)=xsin(100x)－0.1對f(x)采用二進(jìn)制編碼，k=2。選用8位二進(jìn)制數(shù)表示染色體，染色體長度L=8。搜索空間規(guī)模kL=256。

在整個(gè)搜索空間內(nèi)隨機(jī)選擇若干個(gè)染色體，組成一個(gè)初始種群P，初始種群P內(nèi)所含有的染色體個(gè)數(shù)要有足夠的數(shù)量，目前尚無現(xiàn)成的公式計(jì)算P中所需要的染色體的精確數(shù)

量。

本例假設(shè)選擇4個(gè)染色體，用Si(i=1，2，3，4)表示：

S1=00101010

S2=00101110

S3=01101010

S4=01101110將每個(gè)染色體轉(zhuǎn)化成種群f(x)的自變量x表示，考慮到

S=00000000→x=0.0000

S=11111111→x=0.1000

x的取值精確到小數(shù)點(diǎn)后4位，有一般地，已知Si(二進(jìn)制數(shù)染色體表示)求xi(十進(jìn)制數(shù)染色體表示)的公式如下：式中，(Si)10是Si的十進(jìn)制數(shù)值，b是xi的上限取值，a是xi的下限取值。

當(dāng)染色體用十進(jìn)制數(shù)書寫時(shí)，便于進(jìn)一步處理數(shù)據(jù)。

2.基因模式的定義

基因模式是用于描述染色體集合的模板。該模板之所以被命名為基因模式而不叫染色體模式，是因?yàn)榧象w內(nèi)在某些確定的位置上有相同的基因，而進(jìn)行運(yùn)算時(shí)又以基因?yàn)閱挝贿M(jìn)行。

基因模式常用H表示。

基因模式H是與染色體等長的k進(jìn)制串。

與染色體串不同的是，基因模式的各位表示方法有兩種：一種是k個(gè)字符，如五進(jìn)制串，每一位允許有0，1，2，3，4；另一種是“*”，用于表示某一位上的非確定數(shù)。通常，用k個(gè)字符表示的位稱為“確定位”，用“*”字符表示的位稱為“非確定位”?！?”又稱為通配符。以二進(jìn)制基因?yàn)槔?，設(shè)基因模式由4位組成:

a3

a2

a1

a0

1*01

顯然，a3

a1

a0為確定位，a2為非確定位。因此對染色體而言，每個(gè)位置允許有三種不同的字符：0、1和*。

一般地，對用k進(jìn)制數(shù)表示的染色體，每個(gè)位置將允許有k+1個(gè)不同的字符，長度為L的染色體編碼組成的基因模式共有(k+1)L個(gè)。例如長度為8位的二進(jìn)制染色體共有(2+1)8=6561個(gè)基因模式。

通配符“*”不是一個(gè)真正的基因。在二進(jìn)制染色體中，“*”既可以為0，也可以為1，是一個(gè)單獨(dú)的符號(hào)。設(shè)存在一個(gè)基因模式：

H=0*101*10

以下有4個(gè)染色體與此基因模式匹配，它們組成了搜索空間的一個(gè)子集，分別是

S1=00101010

S2=00101110

S3=01101010

S4=01101110可見基因模式H和染色體子集之間的關(guān)系為：H中的“**”分別用“00”、“01”、“10”、“11”取代。由此可知，8位二進(jìn)制串********代表了所有染色體串；而僅由“０”、“１”組成的８位二進(jìn)制串，如

１1０1１１００

僅代表一個(gè)染色體串的基因模式。０*101*10就有4個(gè)染色體串與之相配。

一般地，基因模式中的“*”個(gè)數(shù)決定了與基因模式相匹配的染色體個(gè)數(shù)。設(shè)“*”的個(gè)數(shù)有n個(gè)，k進(jìn)制染色體串將有kn個(gè)與之相匹配。另一方面,每一個(gè)長度為8位的二進(jìn)制染色體串，能夠匹配28個(gè)基因模式,例如染色體11010010可匹配的28個(gè)基因模式為每一個(gè)長度為L的k進(jìn)制染色體串，能匹配kL個(gè)基因模式。長度為L的k進(jìn)制染色體編碼空間的基因模式數(shù)共有(k+1)L個(gè)。設(shè)由此形成的種群大小為P，則可能存在從kL到P·kL種不同的基因模式。

定義基因模式的意義在于：能夠把搜索空間上的染色體進(jìn)行結(jié)構(gòu)化分類?？紤]到每一個(gè)基因模式隱含一個(gè)基因子集，染色體之間的內(nèi)在聯(lián)系事實(shí)上是基因模式的聯(lián)系。對染色體的遺傳算法操作，實(shí)質(zhì)上成了對基因模式的運(yùn)算。

3.模式的階

基因模式H中確定位的個(gè)數(shù)，稱為模式的階，用O(H)表示。例如模式1*1****0的階為3，記為O(H)＝3。又如

H1=0101*0**

則

O(H)=5

基因模式

H=********

可表示整個(gè)搜索空間Ω，

Ω=********則

O(Ω)=0

一個(gè)基因模式的階越大，確定位越多，所能代表染色體串的個(gè)數(shù)就越少，與之匹配的染色體子集元素就越少。

定義“模式的階”的意義在于：用于計(jì)算變異中模式的存活率。

4.基因模式的定義長度

基因模式中第一個(gè)確定位到最后一個(gè)確定位之間的間隔，稱為基因模式的定義長度，用δ(H)表示。定義長度又稱為模式的距。

例如，“定義長度”用于計(jì)算基因模式交叉時(shí)的存活率。

以上分別給“模式的階”及“定義長度”做了定義，這兩個(gè)概念的引入有利于探討基因模式在遺傳操作過程中的變化情況。8.3.2模式定理(Schema)

20世紀(jì)60年代，美國Michigan大學(xué)的Holland教授在他的著作《AdaptationinNaturalandArtificialSystems》中創(chuàng)建了遺傳算法，該算法是一種基于二進(jìn)制表達(dá)的搜索算法。算

法的基本概要是：種群中的染色體通過信息交換重新組合新的染色體串；根據(jù)評價(jià)條件，按照概率選擇適應(yīng)能力強(qiáng)的染色體串進(jìn)入下一代；經(jīng)過多代進(jìn)化后，種群最終將穩(wěn)定在適

應(yīng)性最好的染色體串上。由Holland提出的模式定理概括了搜索過程。定理表述為：在三個(gè)遺傳算子的作用下，平均適應(yīng)度高、模式的階低、定義長度短的模式，其個(gè)數(shù)在遺傳算法的進(jìn)化中按幾何級(jí)數(shù)增長。

遺傳算法的進(jìn)化過程是一種迭代過程，通過種群中的迭代算法，品質(zhì)優(yōu)秀的基因模式得以重組，高質(zhì)量的染色體得以產(chǎn)生。

定理中表述的三個(gè)遺傳算子分別是選擇、交叉、變異。模式定理揭示了平均適應(yīng)度、模式的階、定義長度與迭代進(jìn)程之間的聯(lián)系。

1.選擇算子

選擇算子在搜索空間內(nèi)不會(huì)產(chǎn)生新的染色體串，但適應(yīng)度高的染色體串被選中的概率大，品質(zhì)優(yōu)良模式的數(shù)量將增多，選擇算子的功能就是在種群中復(fù)制質(zhì)量優(yōu)良的模式。

設(shè)種群P內(nèi)有N個(gè)染色體，且每個(gè)染色體串的長度為L；

m(H，t)表示第t代種群P中與模式H匹配的串?dāng)?shù)；對于第t代種群P中與模式H匹配的染色體串，用f(H，t)表示所有這些染色體串的平均適應(yīng)度(又稱平均適應(yīng)值)；J為種群的平均適應(yīng)度。

設(shè)種群關(guān)系仍用f(x)=xsin(100x)－0.1，種群規(guī)模P=20，串長L=8，假定第t代種群由如下染色體串組成：

S1=11010110

S2=00111111→f(x2)=0.117562

S3=10100101

S4=10010001

S5=01001000

S6=01100100

S7=01000111

S8=00110100→f(x8)=0.109392

S9=10011110

S10=01111100→f(x10)=0.064463

S11=10111101→f(x11)=0.182725

S12=10100000

S13=01100001

S14=00110111→f(x14)=0.108649

S15=01011011

S16=10111000→f(x16)=0.142433

S17=11000010

S18=11000011

S19=10010000

S20=01100110其中，f(xi)仍由函數(shù)曲線確定，為各xi的適應(yīng)度，xi的計(jì)算與上節(jié)相同?？疾烊齻€(gè)模式：

H1=**

1

1****

H2=****

**1

1

H3=

0***1*0

0

與模式H1匹配的有S2、S8、S10、S11、Ｓ14、S16，則

m(H1，t)=6

模式H1的階

O(H1，t)=2

定義長度

δ(H1)=1同理，

m(H2，t)=5(與H2匹配的有S2、S7、S1４、S15、S18)

O(H２，t)=2

δ(H２)=1

m(H３，t)=２(與H３匹配的有S５、S１０)

O(H３，t)=４

δ(H３)=７

一般地，若t代種群中與模式匹配的染色體串有ｐ個(gè)：St1，Ｓt２，…，Ｓtｐ，則平均適應(yīng)度為染色體串Si被選中的概率為式中，f(Si)是染色體Si的適應(yīng)度；N是種群P所含的染色體串?dāng)?shù)；fsum(Si)是種群P的總適應(yīng)度。種群的平均適應(yīng)度為由于選擇操作是種群的N個(gè)染色體放入選擇池，每一個(gè)與模式Ｈ匹配的染色體串進(jìn)入下一代的概率為f(H，t)/f(t)，其中，f(t)是種群在t代所有染色體適應(yīng)度之和。交配后第t＋１代模式Ｈ的數(shù)量為

上式表明：

(1)種群中染色體串生長的數(shù)量是模式適應(yīng)度與種群平均適應(yīng)度之比。

(2)模式適應(yīng)度高于種群平均適應(yīng)度，該模式Ｈ的數(shù)量將增加，或者下一代中所匹配的染色體串?dāng)?shù)會(huì)增加；模式適應(yīng)度低于種群平均適應(yīng)度，該模式Ｈ的數(shù)量將減少，或者下一代中所匹配的染色體串?dāng)?shù)會(huì)減少；接近于種群平均適應(yīng)度的模式，數(shù)量在下一代中保持不變或基本不變。

(3)種群中的任何一種模式都按此規(guī)律變化，這一性質(zhì)稱為遺傳算法隱含的并行性。

(4)考察模式適應(yīng)度高于種群平均適應(yīng)度的相對變化，設(shè)a為常數(shù)，令代入到m(H，t)中，有從t＝0開始，有

m(H，t)＝m(H，０)(a＋１)t

a＞０，模式的適應(yīng)度高于平均水平，在下一代中所匹配的染色體串?dāng)?shù)將按幾何級(jí)數(shù)增加(或按指數(shù)規(guī)律增長)；

a＜０，模式的適應(yīng)度低于平均水平，在下一代中所匹配的染色體串?dāng)?shù)將按幾何級(jí)數(shù)減少(或按指數(shù)規(guī)律減少)。

(5)把討論結(jié)果用于本節(jié)用例。對H1而言，在t代有6個(gè)染色體與之匹配，該模式的適應(yīng)度為種群的平均適應(yīng)度為模式H1的適應(yīng)度與種群平均適應(yīng)度之比為結(jié)果表明，模式H1高于平均值，在下一代中與模式H1匹配的染色體串?dāng)?shù)將按幾何級(jí)數(shù)增加。如果計(jì)算出來的比值結(jié)果小于１，則表示與該模式匹配的染色體串?dāng)?shù)將按幾何級(jí)數(shù)減少。

2.交叉算子

交叉運(yùn)算將破壞原有的染色體模式，產(chǎn)生新的染色體模式，破壞概率與定義長度成正比，以下例說明。

設(shè)種群P中的染色體為

基因位1234

5678

S

=1101

0000

同時(shí)與下面兩個(gè)模式匹配：

H4

=

1

1**

****

H5

=

1

1**

**0

0假設(shè)交叉位置S=4，則交叉后子代中仍有一個(gè)染色體串與模式H4匹配，模式H4得以存活，而模式H5被破壞，H5的始端“11”與末端“00”分別置于不同的后代上。

模式的死亡概率pd(H)和存活概率ps(H)與模式的定義長度δ(H)及基因點(diǎn)位置有關(guān)。

設(shè)模式H4、H5的定義長度分別為δ(H4)、δ(H5)：

δ(H4)=1

δ(H5)=7

對于單點(diǎn)交叉，可以作為斷點(diǎn)的位置有L－1個(gè)，某一位置能被選為斷點(diǎn)的可能性為，那么模式H的死亡概率為模式H的存活概率為用于模式H4和H5，則死亡概率為存活概率為可見模式H4得以生存，模式H5被淘汰。

交叉運(yùn)算中只有部分染色體串參加，因此還有一個(gè)指標(biāo)稱為交叉率，常用pc表示，其大小為參加交叉的染色體串?dāng)?shù)與全部染色體之比。在引進(jìn)交叉率pc以后，一個(gè)模式的實(shí)際

存活概率公式修改為

設(shè)pc=0.7，H4和H5的實(shí)際存活率將分別為說明H5仍有存活機(jī)會(huì)，其原因是所有的染色體沒有全部參加交叉。

現(xiàn)在考察交叉位置發(fā)生在一個(gè)模式的固定位置之間，結(jié)果表明該模式仍有存活機(jī)會(huì)。例如有下面兩個(gè)染色體：

基因位1234

5678

S1=

1110

1001

S2=

1100

1000

當(dāng)交叉位置發(fā)生在第2、3、4、5、6、7基因位前，模式H5仍能存活。相應(yīng)的染色體串如下：

交叉位置在第2基因位前：11001000；

交叉位置在第3基因位前：11001000；交叉位置在第4基因位前：11101000；

交叉位置在第5基因位前：11101000；

交叉位置在第6基因位前：11101000；

交叉位置在第7基因位前：11001000。

考慮到上述可能性較小，模式存活概率公式可修改成

綜合選擇與交叉兩種運(yùn)算，模式復(fù)制增長方程式為上式表明，經(jīng)過選擇與交叉產(chǎn)生下一代模式的數(shù)量，與上一代的數(shù)量、定義長度、模式適應(yīng)度、存活概率有關(guān)。m(H，t)越多，f(H)越大，δ(H)越小，下一代模式數(shù)量越多。

3.變異算子

變異操作按變異概率pm隨機(jī)改變一個(gè)染色體串上的某一位，例如對二進(jìn)制編碼，將0變?yōu)?，或?qū)?變?yōu)?。

若變異概率為pm，則1－pm為不被改變的概率，或稱為保持概率。

要想模式經(jīng)過變異后還能存活，條件是該模式上所有固定位保持不變。以染色體S5為例，設(shè)

S5=11001000

它與

H3=11****00相匹配。如果變異后要求H3不變，那么只能是H3中所有固定位保持不變。H3存活的概率可寫成該式可寫成一般式：式中，1－pm就是保持概率，O(H)是模式的階。通常pm<<1，上式能近似寫成

ps(H)≈1－pmO(H)設(shè)

H1

=*1

1*****

H2

=

1

1******

H3

=

1

1****0

0

則

ps(H1)=1－pmO(H1)=1－0.005×2=0.99

ps(H2)=1－pmO(H2)=1－0.005×2=0.99

ps(H3)=1－pmO(H3)=1－0.005×4=0.98

綜合選擇、交叉和變異算子，模式H復(fù)制后增加的數(shù)量為上述不等式是模式H復(fù)制后增長數(shù)量的方程式，它是在適應(yīng)度函數(shù)為正的前提下導(dǎo)出的。模式匹配的染色體串?dāng)?shù)是增加還是減少，也能由上述不等式預(yù)測。如果選用的適應(yīng)度函數(shù)不能保證全為正值，需要進(jìn)行映射操作，確保映射后的適應(yīng)度數(shù)值為正。

本節(jié)小結(jié)如下：

(1)模式的平均適應(yīng)度是決定模式增減的主要因素；

(2)選擇算子不能產(chǎn)生新的模式，交叉算子和變異算子通過結(jié)構(gòu)化方式利用隨機(jī)交換基因位產(chǎn)生新的模式；

(3)模式的定義長度用于描述交叉算子對模式生存的影響，定義長度短的模式容易生存；

(4)模式的階用于描述變異算子對模式生存的影響，低階的模式容易生存；

(5)模式定理闡明了遺傳算法的運(yùn)行機(jī)理，通過短的、低階的模式交叉或變異進(jìn)行空間搜索，在種群中迭加運(yùn)算，讓高品質(zhì)的模式得以組合，最終獲得高質(zhì)量的染色體，完成

優(yōu)化過程。

8.4遺傳算法中的編碼操作

所謂編碼是一種轉(zhuǎn)換操作，將問題空間中的解變量轉(zhuǎn)換成遺傳空間中的染色體，這些染色體由基因按一定排列方式組成。這個(gè)轉(zhuǎn)換過程就是編碼。以染色體為一串二進(jìn)制數(shù)為例，基因就是其中的二進(jìn)制位，編碼就是將實(shí)際問題的解轉(zhuǎn)變成一定規(guī)律的二進(jìn)制串。

解碼是編碼的逆操作，表述成將染色體的編碼映射到問題空間的操作。8.4.1遺傳算法設(shè)計(jì)流程

遺傳算法面對兩個(gè)空間：一個(gè)是問題空間，或稱解空間，在此空間內(nèi)完成對解的評價(jià)與選擇；另一個(gè)是遺傳空間，或稱編碼空間，在此空間內(nèi)對染色體實(shí)施遺傳運(yùn)算。

討論遺傳算法設(shè)計(jì)流程的意義在于如何利用遺傳算法達(dá)到實(shí)際需要的精度。算法本身沒有任何物理意義，它僅僅只是一種數(shù)學(xué)表達(dá)，那么在書寫數(shù)學(xué)表達(dá)式的時(shí)候，必然存

在三個(gè)問題需要解決：

(1)如何選擇合適的編碼方式；

(2)如何確定適應(yīng)度函數(shù)、概率、遺傳算子及相關(guān)參數(shù)；

(3)如何將求解問題轉(zhuǎn)化成算法所能接受的模型。8.4.2遺傳算法中的編碼規(guī)則

編碼方案需要達(dá)到兩個(gè)目的：必須完備和完全對立。

(1)必須完備：問題空間中的所有點(diǎn)均為候選解，都必須作為遺傳空間中的點(diǎn)來表現(xiàn)，缺一不可。遺傳空間的這些點(diǎn)就是染色體。

(2)完全對立：遺傳空間中的染色體能對應(yīng)所有問題空間中的候選解，且染色體與候選解能一一對應(yīng)。

為了達(dá)到編碼的目的，還需要具體的編碼規(guī)則，因?yàn)槟苓_(dá)到上述目的的所有編碼設(shè)計(jì)不一定能有效地提高搜索效率，而在迭代過程中速度緩慢的搜索，在實(shí)時(shí)生產(chǎn)環(huán)節(jié)中沒有任何用處。為此，經(jīng)DeJong提出，具有可操作性的兩條編碼規(guī)則如下：基因塊有意義:編碼生成、距短、階低。

使用最小字符集:編碼采用最小字符集，求解問題能易于表示與描述，目前所用的最小字符集當(dāng)屬二進(jìn)制數(shù)，它只有“0”、“1”兩個(gè)字符。

使用二進(jìn)制編碼，有利于在計(jì)算機(jī)上操作運(yùn)行。

編碼技術(shù)有多種，這里僅介紹一維染色體和二維染色體的編碼技術(shù)。8.4.3一維染色體的編碼方法

當(dāng)問題空間的候選解轉(zhuǎn)換到遺傳空間形成染色體后，若染色體呈一維排列展現(xiàn)基因鏈，這種編碼方法稱為一維染色體編碼。常見的這種編碼技術(shù)有二進(jìn)制編碼、灰碼編碼和浮點(diǎn)編碼等。

1.二進(jìn)制編碼

二進(jìn)制編碼的主要任務(wù)是將問題空間的候選解轉(zhuǎn)換成遺傳空間的二進(jìn)制字符串。轉(zhuǎn)換時(shí)需要用到如下已知條件：

(1)初始種群在問題空間中的分布情況；

(2)變量的取值范圍；

(3)種群函數(shù)的精確程度。

轉(zhuǎn)換需要根據(jù)變量取值空間計(jì)算二進(jìn)制串的長度。

至于染色體的個(gè)數(shù)如何選擇，目前尚無確定的方法。例如初始種群函數(shù)為

f(x)=20+x+10sin(4x)+8cos(3x)

要確定在x=[0，10]區(qū)間的最大值，要求精確到小數(shù)點(diǎn)后6位。

其函數(shù)圖形如圖8-3所示。圖8-3初始種群分布f(x)=20+x+10sin(4x)+8cos(3x)考慮到區(qū)間長10，按精度要求，至少將取值空間分成

10×1000000

|←6個(gè)0→|

份，設(shè)二進(jìn)制染色體v的串長度為m，應(yīng)有：

2m－1＜10000000≤2m－1

不難確定

m=24

染色體可供選擇的范圍如下：

位23～16

15～8

7～0

最小00

00

00H

最大FF

FF

FFH選染色體個(gè)數(shù)5個(gè)(選少了，可能不包括最大解在內(nèi))，如：

V1

=4

E

8

3

E

0

H

V2

=4

E

7

8

0

A

H

V3

=D

8

5

8

3

6

H

V4

=1

E

6

9

4

E

H

V5

=3

A

7

B

E

6

H

經(jīng)過計(jì)算，可將染色體二進(jìn)制數(shù)轉(zhuǎn)換成實(shí)數(shù)變量。計(jì)算公式為式中，v=v1，v2，v3，v4，v5的十進(jìn)制數(shù)；［a，b］是x的取值區(qū)間。由此算得

x1=3.067608

x2=1.815192

x3=7.825960

x4=1.187943

x5=0.756131

二進(jìn)制編碼的優(yōu)點(diǎn)如下：

以最小字符集的編碼原則為出發(fā)點(diǎn)。

代碼簡單，便于交叉、變異操作。

便于使用模式定理進(jìn)行分析與預(yù)測。二進(jìn)制編碼的缺點(diǎn)如下：

編碼數(shù)字不能直觀反映所求問題的模擬量特征。

染色體長度直接與問題空間解的精度有關(guān)。如果長度較短，二進(jìn)制數(shù)的位數(shù)較少，無法反映所求問題的精確度；如果長度較長，二進(jìn)制數(shù)的位數(shù)較多，搜索空間必然增大，搜索的時(shí)間增長，搜索的難度也將增大。

相鄰二進(jìn)制編碼之間可能存在較大的Hamming距離，致使算子的搜索效率降低。這一問題有時(shí)稱為Hamming懸崖。例如4與5的二進(jìn)制數(shù)分別為0100與0101，相鄰兩變量的Hamming距離為2，表示問題空間兩個(gè)近點(diǎn)在遺傳空間內(nèi)有較大的Hamming距離。

2.灰碼編碼

灰碼編碼的結(jié)果也是一個(gè)二進(jìn)制串，通過將二進(jìn)制編碼進(jìn)行一次轉(zhuǎn)換而獲得。由于實(shí)行了一種有效的轉(zhuǎn)換，從而避免了問題空間兩個(gè)近點(diǎn)在遺傳空間內(nèi)有較大Hamming距離這

一缺陷，使得問題空間的兩個(gè)近點(diǎn)在遺傳空間內(nèi)，也相互靠近。

設(shè)二進(jìn)制編碼結(jié)果為b0b1b2…bn-1，相應(yīng)的灰碼二進(jìn)制串為a0

a1

a2…an－1，轉(zhuǎn)換公式為式中，運(yùn)算符號(hào)為模2加法。

反之，有從灰碼轉(zhuǎn)換成二進(jìn)制碼的轉(zhuǎn)換公式表8-8列出了二進(jìn)制編碼和灰碼編碼的一一對應(yīng)關(guān)系?？疾焓M(jìn)制數(shù)0～15的灰碼編碼，不難發(fā)現(xiàn)相鄰兩碼的二進(jìn)制數(shù)串中，僅有1位發(fā)生變化，如從7→8，灰碼改變?yōu)閺?100→1100，僅第一位改變。而在二進(jìn)制碼中，從

0111→1000，4位均發(fā)生了改變。由此可知，在問題空間相鄰的兩個(gè)點(diǎn)(如7和8)，在遺傳空間內(nèi)僅a0位發(fā)生了改變。參數(shù)值增加一步，相應(yīng)代碼僅改變一位。

3.浮點(diǎn)編碼

浮點(diǎn)編碼是由灰碼編碼轉(zhuǎn)換而來的一種編碼方法，它的編碼來源與灰碼編碼相同，僅采取小數(shù)點(diǎn)浮動(dòng)的方式。當(dāng)采用浮點(diǎn)編碼時(shí)，每一個(gè)染色體串都可以編碼成一個(gè)與解向量

等長度的浮點(diǎn)數(shù)向量。

這樣一來，在執(zhí)行算法的時(shí)候，遺傳空間就是問題空間，染色體串自身反映了待求問題的規(guī)律。因此當(dāng)遺傳空間不是問題空間的時(shí)候，采用浮點(diǎn)編碼能縮短遺傳空間與問題空間之間的差距。浮點(diǎn)編碼的編碼方法如下：

(1)已知初始種群的函數(shù)分布f(x)；

(2)在自變量x的取值區(qū)域內(nèi)均勻隨機(jī)產(chǎn)生若干個(gè)浮點(diǎn)數(shù)，長度應(yīng)滿足一定的精度要求；

(3)計(jì)算種群及各個(gè)染色體的適應(yīng)度；

(4)將隨機(jī)產(chǎn)生的浮點(diǎn)數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)。

浮點(diǎn)編碼有如下優(yōu)點(diǎn)：

(1)精度與編碼本身無關(guān)，僅取決于所用機(jī)器，顯得比二進(jìn)制靈活、方便；

(2)浮點(diǎn)數(shù)表示數(shù)的范圍比定點(diǎn)數(shù)廣,從而表達(dá)區(qū)域大;

(3)設(shè)計(jì)封閉動(dòng)態(tài)的遺傳算子及處理非常規(guī)約束都比較容易。8.4.4二維染色體編碼

在現(xiàn)實(shí)生活中，許多系統(tǒng)的解本身不是一維解，常以二維或多維的形式出現(xiàn)，這時(shí)應(yīng)采用二維或多維染色體編碼。

以圖像識(shí)別為例，系統(tǒng)就是以二維矩陣的形式記載一幅圖像。圖8-4繪出了用黑白10×10像素表示英文字母“A”的圖形，為編碼方便，設(shè)黑色像素為1，白色像素為0。圖8-410×10像素表示“A”像素劃分得越細(xì)，圖像越清晰，例如100×100像素表示的圖，遠(yuǎn)比10×10像素的圖清晰度要高得多。

A的二維染色體編碼為

A=

8.5遺傳算法中的適應(yīng)度函數(shù)

適應(yīng)度函數(shù)在遺傳算法中有兩個(gè)功能：評價(jià)染色體和做運(yùn)算的選擇依據(jù)。

適應(yīng)度函數(shù)之所以有如此功能，是因?yàn)榘凑丈镞M(jìn)化優(yōu)勝劣汰的原則，遺傳算法總朝向適應(yīng)值增加的方向進(jìn)化，目標(biāo)函數(shù)的優(yōu)化方向總與適應(yīng)度函數(shù)增加的方向相同。

為了理論上分析問題方便起見，應(yīng)使適應(yīng)度函數(shù)非負(fù)。若適應(yīng)度函數(shù)值為負(fù)，需要進(jìn)行適宜的轉(zhuǎn)換。

本節(jié)討論兩個(gè)問題：

(1)目標(biāo)函數(shù)與適應(yīng)度的轉(zhuǎn)換；

(2)適應(yīng)度函數(shù)如何標(biāo)定。8.5.1將目標(biāo)函數(shù)轉(zhuǎn)換成適應(yīng)度函數(shù)

針對“將目標(biāo)函數(shù)轉(zhuǎn)換成適應(yīng)度函數(shù)”這一問題，可歸結(jié)為兩種不同情況：

(1)目標(biāo)函數(shù)本身就是求最大值；

(2)目標(biāo)函數(shù)為求最小值。

如果目標(biāo)函數(shù)本身就是求最大值，適應(yīng)度函數(shù)可直接寫出。例如求目標(biāo)函

f(x)=xsin(10x)x∈［0，5］

的最大值，適應(yīng)度函數(shù)直接寫成

fit(x)=f(x)=xsin(10x)為保證適應(yīng)度函數(shù)非負(fù)，可加上一個(gè)較大的數(shù)，如

fit(x)=f(x)+6=xsin(10x)+6

一般有

fit(x)=f(x)+c

其中，c為正數(shù)。

目標(biāo)函數(shù)為求最小值，可將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)，公式是

fit(x)=c－f(x)

如果目標(biāo)函數(shù)f(x)為負(fù)，也可以用下式轉(zhuǎn)換：例如求函數(shù)

f(x)=x2+1－1≤x≤1

的最小值，適應(yīng)度函數(shù)可設(shè)計(jì)成

fit(x)1=2－f(x)=1－x28.5.2標(biāo)定適應(yīng)度函數(shù)

對適應(yīng)度函數(shù)進(jìn)行標(biāo)定的意義在于讓染色體適應(yīng)值之間在進(jìn)化過程中既保持一定差異，又避免差異過大。

生物進(jìn)化過程中沒有差異是不可能進(jìn)化的?！安町愡^大”將使進(jìn)化過程夭折，因?yàn)樵谶z傳算法的初始階段，當(dāng)種群規(guī)模較小，且某些染色體的適應(yīng)度過強(qiáng)時(shí)，由于它或它們遠(yuǎn)比

其它染色體的適應(yīng)值高，那么這種染色體被選中的概率就非常大，它或它們將很快充斥整個(gè)種群，導(dǎo)致遺傳算法極快收斂但陷入局部極小點(diǎn)，所得的解未必是最優(yōu)解。由此可見，在進(jìn)化的初始階段應(yīng)避免差異過大，適當(dāng)限制較高適應(yīng)值染色體的過快繁殖。在進(jìn)化后期，情況恰好相反，種群中絕大多數(shù)染色體都有較高的適應(yīng)值，或種群的平均適應(yīng)值與最大適應(yīng)值已接近，使得其中品質(zhì)優(yōu)秀的染色體失去了競爭力，無法從眾多的染色體中脫穎而出。顯然此時(shí)應(yīng)盡量突出染色體之間的差異。

遺傳算法要考慮到進(jìn)化初期和后期對染色體差異不同的要求。

8.6遺傳算法與優(yōu)化解

現(xiàn)以求旅行商(TSP)最短路徑來說明遺傳算法的應(yīng)用。

TSP問題描述為：旅行商在幾個(gè)城市旅行，令L為旅行商巡回閉合路徑，旅行商從一個(gè)城市出發(fā)，一個(gè)一個(gè)城市路過，每個(gè)城市只經(jīng)過一次，最終回到出發(fā)城市。顯然，TSP問題就是要求解Lmin。8.6.1適應(yīng)度函數(shù)的確定

為解題方便計(jì)，把幾個(gè)城市的旅行過程用ai的數(shù)字序列表示：

ai∈Z+

其中，1≤i≤n，i從1到n的取值表示巡回的次序。

設(shè)進(jìn)化到了第n代用t表示，t將意味著種群進(jìn)化到了第t代。第t代的種群為

pt=(a1t，a2t，…，ant)

t=0時(shí)表示種群為初始種群，用p0表示：

p0=(a10，a20，…，an0)初始種群的性能將直接對算法產(chǎn)生影響，例如初始種群的物種多樣性，往往直接影響算法的收斂快慢及尋優(yōu)結(jié)果。

用f表示求解問題的適應(yīng)度函數(shù)，設(shè)計(jì)適應(yīng)度函數(shù)應(yīng)考慮如下因素：

①選擇每個(gè)巡回路徑個(gè)體之和L的倒數(shù)，問題變成求解1/Lmin的最大值；

②也可以使期望路徑長度減去巡回路徑長度之差為最??；

③進(jìn)化初期要防止差異過大，避免某些染色體繁殖能力過強(qiáng)，因適應(yīng)值過高陷入局部極小點(diǎn)；④進(jìn)化后期要防止差異過小，使算法陷入緩慢進(jìn)化，致使優(yōu)秀的染色體在相對均勻的隨機(jī)選擇中無法脫穎而出。

結(jié)論是：在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)要注意，各個(gè)體入選父本的概率不應(yīng)當(dāng)與目標(biāo)函數(shù)成正比，僅僅與種群中目標(biāo)函數(shù)值的降序排列有關(guān)。

通常按種群線性分級(jí)策略進(jìn)行計(jì)算。8.6.2線性分級(jí)策略

適應(yīng)度函數(shù)的計(jì)算策略如下：

(1)首先將個(gè)體按目標(biāo)函數(shù)值的優(yōu)劣排隊(duì)，設(shè)N為種群規(guī)模，排隊(duì)為

F1≥F2≥…≥FN

(2)把N個(gè)染色體按排序結(jié)果分成m類，每類有k個(gè)染色體：

(3)給每類個(gè)體賦予公差b1＜b2＜…＜bm，則第i個(gè)染色體的適應(yīng)度為以n=10為例，有10個(gè)城市供旅行，取N=20(適當(dāng)增多為好)，m=3，k=int(20/3)=6，b1=1，b2=3，b3=6。隨機(jī)產(chǎn)生一組初始種群后，每個(gè)染色體的函數(shù)值及適應(yīng)度可計(jì)算出來，如表8-9所示。從初始種群中選擇幾個(gè)個(gè)體作父本，采用輪轉(zhuǎn)選擇法選擇個(gè)體，方法如下：

將區(qū)間［0，1］劃分成s個(gè)小區(qū)間，劃分依據(jù)是種群個(gè)體的適應(yīng)度占總適應(yīng)度的百分比，用δ表示：式中，k=1，2，…，s；s是種群的個(gè)數(shù)。選中個(gè)體的方法隨機(jī)進(jìn)行，在單位區(qū)間內(nèi)用均勻隨機(jī)變量產(chǎn)生試驗(yàn)值，落在哪個(gè)小區(qū)間內(nèi)，那個(gè)小區(qū)間內(nèi)的個(gè)體將被選中。當(dāng)個(gè)體過于集中在某些小區(qū)內(nèi)時(shí)，陷入局部極值的可能性較大，為了避免這一情況出現(xiàn)，種群規(guī)模越大越好。但過大的種群規(guī)模，將增大計(jì)算工作量。實(shí)踐證實(shí)，n個(gè)城市的

種群規(guī)模宜在n～2n之間確定。8.6.3算法流程

算法流程如下：

初始化，確定種群規(guī)模s、交叉概率p0，變異頻率pm

隨機(jī)產(chǎn)生初始種群P0

0→t

while未結(jié)束

do0→新種群pL+1的個(gè)體數(shù)

fori=1tos

dof(ai′)→fi

max(fi)對應(yīng)的個(gè)體→當(dāng)前最優(yōu)解

whilek＜s

do從

pL中選擇雙親(用親本代選擇)

ifpc＞Random［0，1］

then使用交叉操作產(chǎn)生子代

ifpm＞Random［0，1］

then使用變異操作改變子代

將生成的子代存入pt+1

k+1→k

endwhile

t+1→t

endwhile

輸出當(dāng)前最優(yōu)解

8.7遺傳算法與預(yù)測控制

預(yù)測控制是利用當(dāng)前控制量及系統(tǒng)輸出量，對系統(tǒng)下一時(shí)刻的運(yùn)行實(shí)施優(yōu)化的一種控制方式，既然是預(yù)測，未來的控制效果只能推斷，遺傳算法起因于生物的進(jìn)化，恰好在已知過去發(fā)展的基礎(chǔ)上推知未來的發(fā)展趨勢，顯然，遺傳算法用于預(yù)測控制，有其獨(dú)特的優(yōu)勢。

從計(jì)算方法的角度觀察，預(yù)測是一種離散優(yōu)化的計(jì)算方法。

由于對未來的無知，預(yù)測控制需要在線求解一個(gè)系列的方程組，用數(shù)學(xué)式子表述成求解有約束非線性規(guī)劃：

minJ=J［Ui，Yi］式中，J是目標(biāo)函數(shù)，Ui和Yi分別是優(yōu)化域上的控制序列和輸出序列，且

Ui∈E

Yi∈Ω

yi+k=f[yi+k－1，ui+k－1]

Ui={ui，ui+1，…，ui+p－1}

Yi={yi+1，yi+2，…，yi+p}

目標(biāo)函數(shù)J表達(dá)了優(yōu)化區(qū)間內(nèi)的控制變量及輸出變量的性能指標(biāo)，ui和yi分別是Ui和Yi的元素，f[·]表示對象的預(yù)測模型,Ω是輸出序列的約束條件，E是控制序列的約束條件。有約束非線性規(guī)劃體現(xiàn)在：性能指標(biāo)、預(yù)測模型和約束條件可以是線性的，但通常是非線性的。

預(yù)測模型如果是比較復(fù)雜的非線性結(jié)構(gòu)，就無法直接用控制量求出輸出的解析表示，只能通過懲罰函數(shù)將模型約束引入到目標(biāo)函數(shù)中，把控制量和輸出量當(dāng)做優(yōu)化變量求解。考慮到約束個(gè)數(shù)與優(yōu)化長度有關(guān)，優(yōu)化規(guī)模將被擴(kuò)大。

在用遺傳算法求解優(yōu)化問題時(shí)，首先要解決編碼問題。如果優(yōu)化問題位于多維連續(xù)性空間內(nèi)，碼長就顯得較大，不利于編程計(jì)算。為此，本例提供了兩層浮點(diǎn)遺傳算法，這是一種改進(jìn)了的遺傳算法。兩層浮點(diǎn)遺傳算法的基本思路是產(chǎn)生多個(gè)有相同數(shù)目的種群，它們分別具有不同的初始條件和操作參數(shù)。每個(gè)種群各自獨(dú)立完成一定數(shù)量的遺傳計(jì)算，種群內(nèi)使用浮點(diǎn)方式處

理多維連續(xù)優(yōu)化，然后實(shí)施種群間的遺傳運(yùn)算。

優(yōu)化時(shí)域上的控制變量是求解問題的優(yōu)化值，每當(dāng)產(chǎn)生一個(gè)控制序列，便能獲得一個(gè)相應(yīng)的輸出序列。每個(gè)控制序列事實(shí)上形成了遺傳算法中的染色體，控制量必然存在一個(gè)

上限及下限，即

ui∈［umin，umax］

上下限區(qū)間形成了遺傳算法的搜索空間。對于遺傳算法中的適應(yīng)度函數(shù)，處理依據(jù)如下：

遺傳算法的進(jìn)展方向總是使優(yōu)化過程向適應(yīng)度增加的方向。如果是極小化，應(yīng)當(dāng)使控制輸入量作用下的性能指標(biāo)減小，則相應(yīng)個(gè)體的適應(yīng)度增大。約束越限的處理方法是使用懲罰函數(shù)，越限越嚴(yán)重，適應(yīng)度越小。當(dāng)前約束宜緊，后續(xù)約束宜松。

預(yù)測控制遺傳算法在線求解最優(yōu)的步驟如下：

(1)隨機(jī)產(chǎn)生N×n組控制序列形成初始種群。

(2)計(jì)算各種群內(nèi)個(gè)體適應(yīng)度，計(jì)算的參數(shù)有：

①根據(jù)預(yù)測模型及控制序列，計(jì)算被控對象的響應(yīng)；

②根據(jù)控制序列和響應(yīng)，計(jì)算性能指標(biāo)；③計(jì)算控制序列和響應(yīng)是否滿足約束條件；

④根據(jù)性能指標(biāo)和約束條件計(jì)算適應(yīng)度。

(3)檢查適應(yīng)度是否滿足要求，若滿足要求則結(jié)束計(jì)算過程，若不滿足則轉(zhuǎn)(2)，繼續(xù)遺傳操作。

考慮的預(yù)測控制目標(biāo)為預(yù)測控制對象為

y1k=0.6y1(k－1)+sin(y2(k－1))+u1(k－1)u2(k－1)

y2k=0.7y1(k－1)+0.5y2(k－1)+0.6y1(k－1)u1(k－1)+u2(k－1)約束條件是

|u1k|≤1

|u2k|≤1

|y1k|≤2

|y2k|≤2

式中，k=1，2，…，p，初始條件是

y10=y20=0

本例預(yù)測控制是一個(gè)雙輸入雙輸出非線性過程，希望輸出能跟蹤設(shè)定值。遺傳算法所用初始值設(shè)定如下：

種群個(gè)體數(shù)為100，分成10×10組，預(yù)估步數(shù)p=3，交叉概率p=取0.7～1之間的隨機(jī)數(shù)，變異概率pm取0～0.1之間的隨機(jī)數(shù)，例如pc=0.9，pm=0.05，適應(yīng)值函數(shù)選擇為f=0.75x。

仿真計(jì)算70個(gè)采樣周期，每隔10個(gè)采樣周期就改變一次設(shè)定值，用以考察算法的跟蹤效果。可取的設(shè)定值[y1set，y2set]分別有：

[1，1]，[0.5，1]，[0.5，1.5]，[0，1.5]，[1，0.5]仿真中用兩層遺傳算法和普通浮點(diǎn)遺傳算法分別計(jì)算50次的平均最優(yōu)適應(yīng)值，將適應(yīng)值與相應(yīng)進(jìn)化代數(shù)之間的關(guān)系繪制成曲線，如圖8-5所示。從進(jìn)化過程圖可以看到，兩層遺傳算法的尋優(yōu)率高一些，尤其在種群個(gè)體小的時(shí)候更為明顯。圖8-5進(jìn)化過程在兩層遺傳算法直接優(yōu)化作用下，能夠獲得兩條曲線，一條是控制作用u隨時(shí)間的變化曲線，另一條是輸出響應(yīng)y隨時(shí)間的變化曲線，兩條曲線分別如圖8-6和圖8-7所示。從

圖中可以看到，控制量能夠按照下列變化及時(shí)得到調(diào)整：

一個(gè)變化是設(shè)定值的變化；另一個(gè)變化是被控對象結(jié)構(gòu)參數(shù)的變化。

仿真結(jié)果表明，用遺傳算法實(shí)施預(yù)測控制具有策劃簡單、計(jì)算效率高的優(yōu)點(diǎn)，對于實(shí)際工業(yè)過程的復(fù)雜性與適時(shí)性要求，遺傳算法是一種較好的選擇。圖8-6控制作用曲線圖8-7輸出響應(yīng)曲線

8.8遺傳算法與神經(jīng)網(wǎng)絡(luò)

物流網(wǎng)絡(luò)中的配送中心，是貨物從產(chǎn)生企業(yè)到批發(fā)零售商之間的中轉(zhuǎn)站，是集中或分散貨物，使貨物流轉(zhuǎn)的中間存儲(chǔ)倉庫?？紤]到配送中心所處的地理位置，交通便利條件、

運(yùn)費(fèi)成本低廉等因素，貨物周轉(zhuǎn)過程中存在一個(gè)配送中心選址的問題。

本節(jié)試圖用遺傳算法與神經(jīng)網(wǎng)絡(luò)求解此類問題的最優(yōu)解。

選用的神經(jīng)網(wǎng)絡(luò)模型為Hopfield模型。該模型在求解組合優(yōu)化問題方面有明顯的優(yōu)勢。設(shè)物流網(wǎng)絡(luò)中心有n個(gè)用戶s1，s2，…，sn。選其中k個(gè)確定各自配送范圍，使配送費(fèi)用最小，由此確定的數(shù)學(xué)模型為

式中，

表示配送中心si到用戶j處所需單位運(yùn)輸費(fèi)用；表示si到用戶j處的配送量；

表示設(shè)置配送中心所需固定費(fèi)用及管理費(fèi)用；dj是用戶j的需求數(shù)量；是配送中心si的容量；Z是配送總費(fèi)用，minZ是使Z為最小，是算法求解的最終目標(biāo)。

上述三個(gè)式子中，第一個(gè)是目標(biāo)管理，使經(jīng)費(fèi)為最小，第二、三個(gè)是約束條件，表示配送網(wǎng)絡(luò)的總供給往往不等于總的需求，但不宜差別過大，否則將造成積壓與浪費(fèi)。為此可考慮設(shè)置一個(gè)虛擬用戶，設(shè)為第n+1個(gè)用戶，存在一個(gè)虛擬配送中心sk+1。好處是相應(yīng)數(shù)學(xué)模型可全部使用等號(hào)：運(yùn)費(fèi)

需求量

存儲(chǔ)容量

用等號(hào)書寫的目的，在于將約束條件不等式改寫成約束條件等式，但對總費(fèi)用目標(biāo)函數(shù)沒有任何影響。

現(xiàn)構(gòu)造Hopfield能量函數(shù)(用E表示)，令式中，A為目標(biāo)系數(shù)，B、C為懲罰項(xiàng)系數(shù)。有了能量函數(shù)，遺傳算法可按以下步驟進(jìn)行：第一步，產(chǎn)生初始種群。對于n個(gè)用戶的物流網(wǎng)絡(luò)，使用n位二進(jìn)制位串表示不同的染色體個(gè)體。例如第i位的值，為0表示該用戶未被選中成為配送中心；為1就表示該位地址是配送中心選中的地址。隨機(jī)產(chǎn)生L個(gè)染色體Gi(i=1，2，…，L)，每個(gè)染色體彼此并不相同。

第二步，判斷停止進(jìn)化。

對染色體Gi組成的種群求最小配送費(fèi)用Zi，取Gi的適應(yīng)度函數(shù)fi反映了Gi在優(yōu)勝劣汰過程中的優(yōu)劣程度。判斷迭代的代數(shù)是否達(dá)到要求的代數(shù)。如果不是，繼續(xù)往下執(zhí)行；如果是，停止進(jìn)化，選擇性能好的染色體作為結(jié)果。第三步，優(yōu)勝劣汰。

將種群中L個(gè)染色體的適應(yīng)度按從大到小的順序排列。排在最前面的S個(gè)染色體性能優(yōu)越，各產(chǎn)生兩個(gè)子代。排在中間的染色體將產(chǎn)生一個(gè)染色體。排在最后面的S個(gè)染色體性能最差，將被淘汰。

第四步，交叉變異。

選擇交換率Lc=0.6L，Lc個(gè)染色體隨機(jī)產(chǎn)生且在種群中均勻分布。將Lc個(gè)染色體交叉：對選中的Gi、Gj，隨機(jī)取兩點(diǎn)交換元素，產(chǎn)生兩個(gè)新的子代，檢查新子代值為1的位數(shù)，如果它與初始種群中染色體值為1的位數(shù)不相等，則看誰大誰小，進(jìn)行不同的變異操作。若前者大后者小，將差值中為1的位置0，反之將為0的位置1，同時(shí)返回第二步?，F(xiàn)有物流配送網(wǎng)絡(luò)實(shí)例如下。設(shè)12個(gè)需求點(diǎn)的距離列于表8-10中，題目要求從中選擇3個(gè)作為配送中心地址。各配送中心的容量假設(shè)均為13個(gè)單位。從第1點(diǎn)到第12點(diǎn)設(shè)置成配送中心的費(fèi)用各不相同，經(jīng)過預(yù)測算，相對費(fèi)用分別為15、21、13、10、15、10、10、10、10、24、10、10。用遺傳算法確定的配送方案如表8-11所示，其優(yōu)化配送中心為2、6、10，最終綜合費(fèi)用為177。

使用常規(guī)優(yōu)化方法進(jìn)行迭代，算得的配送中心為4、