第8章神經控制中的遺傳進化訓練8.1生物的遺傳與進化8.2遺傳算法概述8.3遺傳算法中的模式定理8.4遺傳算法中的編碼操作8.5遺傳算法中的適應度函數8.6遺傳算法與優化解8.7遺傳算法與預測控制8.8遺傳算法與神經網絡8.9神經網絡的遺傳進化訓練8.10小結習題與思考題

8.1生物的遺傳與進化

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

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

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

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

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

生物進化論的基本觀點是：生物的發展與進化有三種主要形態，這就是遺傳、變異和選擇。

自然界中的生命千姿百態，地球上的幾百萬種生物相互扶持、相互依存、相互成鏈。千奇百怪的各種生物在數十億年的進化中，適應環境，繁衍后代，頑強地生存下來。在人與自然和諧相處中不難發現這一點。各種生物進化的方法和結果雖然不相同，但是仍然可以找到生物在進化過程中的共同點，這些共同點表現在如下幾個方面：

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

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

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

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

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

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

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

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

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

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

優化問題是數學中的一個重要研究分支。現代控制理論中的一個重要議題，就是在眾多系統解中尋求一個最優解。進化計算的提出，給優化問題求解提供了一種用傳統方法較難求解的新方法。

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

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

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

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

①隨機產生初始種群Ｍ(t)。

②用適應度函數u(ｍ)評價Ｍ(t)中每個染色體ｍ，評價方法是計算每個染色體ｍ的適應度函數u(ｍ)，不同的染色體有不同的計算結果。

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

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

⑤重復②～④，直至完成事先預定的要進化的代數。

2．進化規劃(eＰ)

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

進化規劃討論的主要議題如下：

(１)生物進化是否成功要以整體行為作為衡量標準，不能以個別染色體是否成功為衡量標準，也不能從個別組成是否好壞來衡量整體。

(２)生物進化首要考慮的問題是對環境行為如何做出響應，而不必考慮這個響應是如何產生的。

(３)進化規劃實質上是一個不斷變異、不斷再生的迭代過程，迭代是對進化過程的一種模擬。染色體作為一個個體，在不斷變異、不斷再生并優化的進程中，要從種群全局

角度去處理。因此，進化規劃重點討論的問題不是染色體的變異和選擇，而是種群的變異和選擇。進化規劃的規則是：自上而下考慮整體的全局優化。

例如一曲音樂中，一個音符的優化要服從整個樂曲的要求。一個阿拉伯數字的價值不在它自身，而在它位于一個數的哪個位置上。

進化規劃的運行規則是：自上而下考慮整體的全局優化。３．進化策略(eＳ)

進化策略是在1973年由德國數學家IngoRechenberg提出的。隨后由HansPaulSchwefel發展并用于數字優化。

進化策略的含義是：

生物在長達36億年的漫長進化歲月中，能夠將完成進化所使用的方法等價成一個機智優化過程，這個過程中存在一個進化策略的理論。既然是“策略”，事實上就是生物從結構

及演化兩個方面如何得到優化。

進化策略理論的最基本觀點如下：

(1)進化過程優化了生物；

(2)進化自身是一個生物過程；

(3)進化必定將“進化”自身優化。

進化過程不僅對染色體的生存隨時做出應有的貢獻，而且更為重要的，是在若干代染色體的變異中選擇較好的遺傳策略，目的是為了更好地適應環境。

只有講究策略，生物的進化過程才能形成優化過程。

４．進化計算的評價

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

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

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

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

術中的計算都可以轉化成編碼序列模型來表示。

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

快的求解速度。

(３)進化計算中涉及到的適應度函數僅與優化問題相聯系，對適應度函數自身的限制較少，這就對適應度函數的選擇提供了較寬的范圍，例如甚至不要求連續、可導等作為約束條件。

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

(５)選擇操作通過粗調與微調有機結合進行，交叉操作是在足夠大的范圍內進行信息重組，變異操作則是通過基因突變實現優化。這些操作能有效避開求解空間的局部極小

點，以較快速度達到全局最優解。

(6)進化計算存在著三個問題：

第一個問題是進化計算是一門由人類創立的技術，是人們頭腦中對生物進化過程的模擬思考，它不同于生物的實際進化過程——一種客觀存在的歷史發展。兩者本質的區別決定了進化計算總會有誤差。

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

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

第三個問題是進化計算不是求解最優的首選，只要能使用線性規劃、動態規劃、擬牛頓法等傳統方法，就不要使用進化計算。

8.2遺傳算法概述

8.2.1遺傳算法中遇到的基本術語

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

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

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

適應度(Fitness)：適應度函數的簡稱，解的目標函數值，能衡量染色體的好壞。8.2.2遺傳算法的運算特征

１．遺傳算法的特點

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

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

(３)遺傳算法只用適應度評價解的優劣。

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

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

１)選擇(Selection)

所謂選擇，是指從種群中按一定的標準選定適應做親本的染色體。選擇的目的是為了將適應的染色體交配后復制出子代。

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

(1)適應度函數fi越大，被選中的概率越大；

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

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

2)交叉(Crossover)

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

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

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

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

們有相同的基因，但排序次序不同。將父本在兩個交叉點間的部分復制，成為子代的一部分，如：可得子代1的一部分，子代1余下的4個基因應當從父本余下基因中去選擇。從父本2中去掉a5a7a2和a9a1a4，從a3開始轉至父本2的第1個基因a6繼續。即子代1余下的4個基因為a3a6a8a10同理，子代2的10個基因為

子代2a9a1a4

a5a7a2

a6a10a8a3

由此形成的結果如表8-5所示。

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

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

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

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

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

3)變異(Mutation)

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

于交叉操作。

現以解決TSP組和優化問題為例，設父本的基因為123456789，變異操作的種類較多，現列舉其中的三種：

(1)SWAP為對調兩個基因的位置；

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

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

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

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

假設：

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

1*0*01

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

1*0*01取第4～6位*01，其直徑d=3。設f為待優化的函數，定義在長度為L的二進制序列上，函數f又稱為適應度函數，簡稱適應度。

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

從N個序列x1、x2、…、xN中選中xj為親本序列的概率為上式表明，適應度函數大的序列被選中的概率大。

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

8.3遺傳算法中的模式定理

遺傳算法是模擬生物進化過程這一自然界運動規律的計算方法，由于進化過程的時間有數十億年，使得模擬算法本身自然、直接且又樸素。它沒有嚴密的數學推導作為理論基

礎，總是圍繞著選擇、交叉、變異等基本操作進行。截至目前為止，尚無足夠的基礎理論來闡明遺傳算法的運算特征。而其它計算算法，則需要嚴密的數學推導作為理論基礎。

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

模式定理最早由Holland提出，后經許多人不斷完善，現已成為遺傳算法最成熟的理論。模式定理的主要內涵是解釋染色體編碼結構在進化過程中的應用。

1.搜索空間的規模

設物體空間或搜索空間為Ω，在此空間內包含所有可能的染色體編碼，設染色體采用k進制編碼，染色體長度為L，則搜索空間的規模為kL。

例如對種群

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

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

在整個搜索空間內隨機選擇若干個染色體，組成一個初始種群P，初始種群P內所含有的染色體個數要有足夠的數量，目前尚無現成的公式計算P中所需要的染色體的精確數

量。

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

S1=00101010

S2=00101110

S3=01101010

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

S=00000000→x=0.0000

S=11111111→x=0.1000

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

當染色體用十進制數書寫時，便于進一步處理數據。

2.基因模式的定義

基因模式是用于描述染色體集合的模板。該模板之所以被命名為基因模式而不叫染色體模式，是因為集合體內在某些確定的位置上有相同的基因，而進行運算時又以基因為單位進行。

基因模式常用H表示。

基因模式H是與染色體等長的k進制串。

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

a3

a2

a1

a0

1*01

顯然，a3

a1

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

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

通配符“*”不是一個真正的基因。在二進制染色體中，“*”既可以為0，也可以為1，是一個單獨的符號。設存在一個基因模式：

H=0*101*10

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

S1=00101010

S2=00101110

S3=01101010

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

１1０1１１００

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

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

定義基因模式的意義在于：能夠把搜索空間上的染色體進行結構化分類。考慮到每一個基因模式隱含一個基因子集，染色體之間的內在聯系事實上是基因模式的聯系。對染色體的遺傳算法操作，實質上成了對基因模式的運算。

3.模式的階

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

H1=0101*0**

則

O(H)=5

基因模式

H=********

可表示整個搜索空間Ω，

Ω=********則

O(Ω)=0

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

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

4.基因模式的定義長度

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

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

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

20世紀60年代，美國Michigan大學的Holland教授在他的著作《AdaptationinNaturalandArtificialSystems》中創建了遺傳算法，該算法是一種基于二進制表達的搜索算法。算

法的基本概要是：種群中的染色體通過信息交換重新組合新的染色體串；根據評價條件，按照概率選擇適應能力強的染色體串進入下一代；經過多代進化后，種群最終將穩定在適

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

遺傳算法的進化過程是一種迭代過程，通過種群中的迭代算法，品質優秀的基因模式得以重組，高質量的染色體得以產生。

定理中表述的三個遺傳算子分別是選擇、交叉、變異。模式定理揭示了平均適應度、模式的階、定義長度與迭代進程之間的聯系。

1.選擇算子

選擇算子在搜索空間內不會產生新的染色體串，但適應度高的染色體串被選中的概率大，品質優良模式的數量將增多，選擇算子的功能就是在種群中復制質量優良的模式。

設種群P內有N個染色體，且每個染色體串的長度為L；

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

設種群關系仍用f(x)=xsin(100x)－0.1，種群規模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)仍由函數曲線確定，為各xi的適應度，xi的計算與上節相同。考察三個模式：

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代種群中與模式匹配的染色體串有ｐ個：St1，Ｓt２，…，Ｓtｐ，則平均適應度為染色體串Si被選中的概率為式中，f(Si)是染色體Si的適應度；N是種群P所含的染色體串數；fsum(Si)是種群P的總適應度。種群的平均適應度為由于選擇操作是種群的N個染色體放入選擇池，每一個與模式Ｈ匹配的染色體串進入下一代的概率為f(H，t)/f(t)，其中，f(t)是種群在t代所有染色體適應度之和。交配后第t＋１代模式Ｈ的數量為

上式表明：

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

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

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

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

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

a＞０，模式的適應度高于平均水平，在下一代中所匹配的染色體串數將按幾何級數增加(或按指數規律增長)；

a＜０，模式的適應度低于平均水平，在下一代中所匹配的染色體串數將按幾何級數減少(或按指數規律減少)。

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

2.交叉算子

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

設種群P中的染色體為

基因位1234

5678

S

=1101

0000

同時與下面兩個模式匹配：

H4

=

1

1**

****

H5

=

1

1**

**0

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

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

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

δ(H4)=1

δ(H5)=7

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

交叉運算中只有部分染色體串參加，因此還有一個指標稱為交叉率，常用pc表示，其大小為參加交叉的染色體串數與全部染色體之比。在引進交叉率pc以后，一個模式的實際

存活概率公式修改為

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

現在考察交叉位置發生在一個模式的固定位置之間，結果表明該模式仍有存活機會。例如有下面兩個染色體：

基因位1234

5678

S1=

1110

1001

S2=

1100

1000

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

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

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

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

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

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

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

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

3.變異算子

變異操作按變異概率pm隨機改變一個染色體串上的某一位，例如對二進制編碼，將0變為1，或將1變為0。

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

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

S5=11001000

它與

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

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

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復制后增加的數量為上述不等式是模式H復制后增長數量的方程式，它是在適應度函數為正的前提下導出的。模式匹配的染色體串數是增加還是減少，也能由上述不等式預測。如果選用的適應度函數不能保證全為正值，需要進行映射操作，確保映射后的適應度數值為正。

本節小結如下：

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

(2)選擇算子不能產生新的模式，交叉算子和變異算子通過結構化方式利用隨機交換基因位產生新的模式；

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

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

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

優化過程。

8.4遺傳算法中的編碼操作

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

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

遺傳算法面對兩個空間：一個是問題空間，或稱解空間，在此空間內完成對解的評價與選擇；另一個是遺傳空間，或稱編碼空間，在此空間內對染色體實施遺傳運算。

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

在三個問題需要解決：

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

(2)如何確定適應度函數、概率、遺傳算子及相關參數；

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

編碼方案需要達到兩個目的：必須完備和完全對立。

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

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

為了達到編碼的目的，還需要具體的編碼規則，因為能達到上述目的的所有編碼設計不一定能有效地提高搜索效率，而在迭代過程中速度緩慢的搜索，在實時生產環節中沒有任何用處。為此，經DeJong提出，具有可操作性的兩條編碼規則如下：基因塊有意義:編碼生成、距短、階低。

使用最小字符集:編碼采用最小字符集，求解問題能易于表示與描述，目前所用的最小字符集當屬二進制數，它只有“0”、“1”兩個字符。

使用二進制編碼，有利于在計算機上操作運行。

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

當問題空間的候選解轉換到遺傳空間形成染色體后，若染色體呈一維排列展現基因鏈，這種編碼方法稱為一維染色體編碼。常見的這種編碼技術有二進制編碼、灰碼編碼和浮點編碼等。

1.二進制編碼

二進制編碼的主要任務是將問題空間的候選解轉換成遺傳空間的二進制字符串。轉換時需要用到如下已知條件：

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

(2)變量的取值范圍；

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

轉換需要根據變量取值空間計算二進制串的長度。

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

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

要確定在x=[0，10]區間的最大值，要求精確到小數點后6位。

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

10×1000000

|←6個0→|

份，設二進制染色體v的串長度為m，應有：

2m－1＜10000000≤2m－1

不難確定

m=24

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

位23～16

15～8

7～0

最小00

00

00H

最大FF

FF

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

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

經過計算，可將染色體二進制數轉換成實數變量。計算公式為式中，v=v1，v2，v3，v4，v5的十進制數；［a，b］是x的取值區間。由此算得

x1=3.067608

x2=1.815192

x3=7.825960

x4=1.187943

x5=0.756131

二進制編碼的優點如下：

以最小字符集的編碼原則為出發點。

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

便于使用模式定理進行分析與預測。二進制編碼的缺點如下：

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

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

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

2.灰碼編碼

灰碼編碼的結果也是一個二進制串，通過將二進制編碼進行一次轉換而獲得。由于實行了一種有效的轉換，從而避免了問題空間兩個近點在遺傳空間內有較大Hamming距離這

一缺陷，使得問題空間的兩個近點在遺傳空間內，也相互靠近。

設二進制編碼結果為b0b1b2…bn-1，相應的灰碼二進制串為a0

a1

a2…an－1，轉換公式為式中，運算符號為模2加法。

反之，有從灰碼轉換成二進制碼的轉換公式表8-8列出了二進制編碼和灰碼編碼的一一對應關系。考察十進制數0～15的灰碼編碼，不難發現相鄰兩碼的二進制數串中，僅有1位發生變化，如從7→8，灰碼改變為從0100→1100，僅第一位改變。而在二進制碼中，從

0111→1000，4位均發生了改變。由此可知，在問題空間相鄰的兩個點(如7和8)，在遺傳空間內僅a0位發生了改變。參數值增加一步，相應代碼僅改變一位。

3.浮點編碼

浮點編碼是由灰碼編碼轉換而來的一種編碼方法，它的編碼來源與灰碼編碼相同，僅采取小數點浮動的方式。當采用浮點編碼時，每一個染色體串都可以編碼成一個與解向量

等長度的浮點數向量。

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

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

(2)在自變量x的取值區域內均勻隨機產生若干個浮點數，長度應滿足一定的精度要求；

(3)計算種群及各個染色體的適應度；

(4)將隨機產生的浮點數轉化為二進制數。

浮點編碼有如下優點：

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

(2)浮點數表示數的范圍比定點數廣,從而表達區域大;

(3)設計封閉動態的遺傳算子及處理非常規約束都比較容易。8.4.4二維染色體編碼

在現實生活中，許多系統的解本身不是一維解，常以二維或多維的形式出現，這時應采用二維或多維染色體編碼。

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

A的二維染色體編碼為

A=

8.5遺傳算法中的適應度函數

適應度函數在遺傳算法中有兩個功能：評價染色體和做運算的選擇依據。

適應度函數之所以有如此功能，是因為按照生物進化優勝劣汰的原則，遺傳算法總朝向適應值增加的方向進化，目標函數的優化方向總與適應度函數增加的方向相同。

為了理論上分析問題方便起見，應使適應度函數非負。若適應度函數值為負，需要進行適宜的轉換。

本節討論兩個問題：

(1)目標函數與適應度的轉換；

(2)適應度函數如何標定。8.5.1將目標函數轉換成適應度函數

針對“將目標函數轉換成適應度函數”這一問題，可歸結為兩種不同情況：

(1)目標函數本身就是求最大值；

(2)目標函數為求最小值。

如果目標函數本身就是求最大值，適應度函數可直接寫出。例如求目標函

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

的最大值，適應度函數直接寫成

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

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

一般有

fit(x)=f(x)+c

其中，c為正數。

目標函數為求最小值，可將目標函數映射成適應度函數，公式是

fit(x)=c－f(x)

如果目標函數f(x)為負，也可以用下式轉換：例如求函數

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

的最小值，適應度函數可設計成

fit(x)1=2－f(x)=1－x28.5.2標定適應度函數

對適應度函數進行標定的意義在于讓染色體適應值之間在進化過程中既保持一定差異，又避免差異過大。

生物進化過程中沒有差異是不可能進化的。“差異過大”將使進化過程夭折，因為在遺傳算法的初始階段，當種群規模較小，且某些染色體的適應度過強時，由于它或它們遠比

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

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

8.6遺傳算法與優化解

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

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

為解題方便計，把幾個城市的旅行過程用ai的數字序列表示：

ai∈Z+

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

設進化到了第n代用t表示，t將意味著種群進化到了第t代。第t代的種群為

pt=(a1t，a2t，…，ant)

t=0時表示種群為初始種群，用p0表示：

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

用f表示求解問題的適應度函數，設計適應度函數應考慮如下因素：

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

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

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

結論是：在設計適應度函數時要注意，各個體入選父本的概率不應當與目標函數成正比，僅僅與種群中目標函數值的降序排列有關。

通常按種群線性分級策略進行計算。8.6.2線性分級策略

適應度函數的計算策略如下：

(1)首先將個體按目標函數值的優劣排隊，設N為種群規模，排隊為

F1≥F2≥…≥FN

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

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

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

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

算法流程如下：

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

隨機產生初始種群P0

0→t

while未結束

do0→新種群pL+1的個體數

fori=1tos

dof(ai′)→fi

max(fi)對應的個體→當前最優解

whilek＜s

do從

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

ifpc＞Random［0，1］

then使用交叉操作產生子代

ifpm＞Random［0，1］

then使用變異操作改變子代

將生成的子代存入pt+1

k+1→k

endwhile

t+1→t

endwhile

輸出當前最優解

8.7遺傳算法與預測控制

預測控制是利用當前控制量及系統輸出量，對系統下一時刻的運行實施優化的一種控制方式，既然是預測，未來的控制效果只能推斷，遺傳算法起因于生物的進化，恰好在已知過去發展的基礎上推知未來的發展趨勢，顯然，遺傳算法用于預測控制，有其獨特的優勢。

從計算方法的角度觀察，預測是一種離散優化的計算方法。

由于對未來的無知，預測控制需要在線求解一個系列的方程組，用數學式子表述成求解有約束非線性規劃：

minJ=J［Ui，Yi］式中，J是目標函數，Ui和Yi分別是優化域上的控制序列和輸出序列，且

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}

目標函數J表達了優化區間內的控制變量及輸出變量的性能指標，ui和yi分別是Ui和Yi的元素，f[·]表示對象的預測模型,Ω是輸出序列的約束條件，E是控制序列的約束條件。有約束非線性規劃體現在：性能指標、預測模型和約束條件可以是線性的，但通常是非線性的。

預測模型如果是比較復雜的非線性結構，就無法直接用控制量求出輸出的解析表示，只能通過懲罰函數將模型約束引入到目標函數中，把控制量和輸出量當做優化變量求解。考慮到約束個數與優化長度有關，優化規模將被擴大。

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

理多維連續優化，然后實施種群間的遺傳運算。

優化時域上的控制變量是求解問題的優化值，每當產生一個控制序列，便能獲得一個相應的輸出序列。每個控制序列事實上形成了遺傳算法中的染色體，控制量必然存在一個

上限及下限，即

ui∈［umin，umax］

上下限區間形成了遺傳算法的搜索空間。對于遺傳算法中的適應度函數，處理依據如下：

遺傳算法的進展方向總是使優化過程向適應度增加的方向。如果是極小化，應當使控制輸入量作用下的性能指標減小，則相應個體的適應度增大。約束越限的處理方法是使用懲罰函數，越限越嚴重，適應度越小。當前約束宜緊，后續約束宜松。

預測控制遺傳算法在線求解最優的步驟如下：

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

(2)計算各種群內個體適應度，計算的參數有：

①根據預測模型及控制序列，計算被控對象的響應；

②根據控制序列和響應，計算性能指標；③計算控制序列和響應是否滿足約束條件；

④根據性能指標和約束條件計算適應度。

(3)檢查適應度是否滿足要求，若滿足要求則結束計算過程，若不滿足則轉(2)，繼續遺傳操作。

考慮的預測控制目標為預測控制對象為

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

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

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

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

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

圖中可以看到，控制量能夠按照下列變化及時得到調整：

一個變化是設定值的變化；另一個變化是被控對象結構參數的變化。

仿真結果表明，用遺傳算法實施預測控制具有策劃簡單、計算效率高的優點，對于實際工業過程的復雜性與適時性要求，遺傳算法是一種較好的選擇。圖8-6控制作用曲線圖8-7輸出響應曲線

8.8遺傳算法與神經網絡

物流網絡中的配送中心，是貨物從產生企業到批發零售商之間的中轉站，是集中或分散貨物，使貨物流轉的中間存儲倉庫。考慮到配送中心所處的地理位置，交通便利條件、

運費成本低廉等因素，貨物周轉過程中存在一個配送中心選址的問題。

本節試圖用遺傳算法與神經網絡求解此類問題的最優解。

選用的神經網絡模型為Hopfield模型。該模型在求解組合優化問題方面有明顯的優勢。設物流網絡中心有n個用戶s1，s2，…，sn。選其中k個確定各自配送范圍，使配送費用最小，由此確定的數學模型為

式中，

表示配送中心si到用戶j處所需單位運輸費用；表示si到用戶j處的配送量；

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

上述三個式子中，第一個是目標管理，使經費為最小，第二、三個是約束條件，表示配送網絡的總供給往往不等于總的需求，但不宜差別過大，否則將造成積壓與浪費。為此可考慮設置一個虛擬用戶，設為第n+1個用戶，存在一個虛擬配送中心sk+1。好處是相應數學模型可全部使用等號：運費

需求量

存儲容量

用等號書寫的目的，在于將約束條件不等式改寫成約束條件等式，但對總費用目標函數沒有任何影響。

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

第二步，判斷停止進化。

對染色體Gi組成的種群求最小配送費用Zi，取Gi的適應度函數fi反映了Gi在優勝劣汰過程中的優劣程度。判斷迭代的代數是否達到要求的代數。如果不是，繼續往下執行；如果是，停止進化，選擇性能好的染色體作為結果。第三步，優勝劣汰。

將種群中L個染色體的適應度按從大到小的順序排列。排在最前面的S個染色體性能優越，各產生兩個子代。排在中間的染色體將產生一個染色體。排在最后面的S個染色體性能最差，將被淘汰。

第四步，交叉變異。

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

使用常規優化方法進行迭代，算得的配送中心為4、