AI6章計算智能課件

第5章計算智能計算智能是信息科學、生命科學、認知科學等不同學科相互交叉的產物。它主要借鑒仿生學的思想，基于人們對生物體智能機理的認識，采用數(shù)值計算的方法去模擬和實現(xiàn)人類的智能。計算智能的主要研究領域包括：神經計算、進化計算、模糊計算、免疫計算、DNA計算和人工生命等。本章主要討論神經計算、進化計算和模糊計算問題。

5.1概述5.2神經計算5.3進化計算5.4模糊計算1第5章計算智能5.1概述15.1概述

5.1.1什么是計算智能5.1.2計算智能的產生與發(fā)展5.1.3計算智能與人工智能的關系25.1概述5.1.1什么是計算智能25.1.1什么是計算智能計算智能（ComputationalIntelligence，CI）目前還沒有一個統(tǒng)一的的定義，使用較多的是美國科學家貝慈德克（J.C.Bezdek）從計算智能系統(tǒng)角度所給出的定義:如果一個系統(tǒng)僅處理低層的數(shù)值數(shù)據，含有模式識別部件，沒有使用人工智能意義上的知識，且具有計算適應性、計算容錯力、接近人的計算速度和近似于人的誤差率這4個特性，則它是計算智能的。從學科范疇看，計算智能是在神經網絡（NeuralNetworks,NN）、進化計算（EvolutionaryComputation,EC）及模糊系統(tǒng)（FuzzySystem,FS）這3個領域發(fā)展相對成熟的基礎上形成的一個統(tǒng)一的學科概念。

35.1.1什么是計算智能計算智能（Computat

神經網絡是一種對人類智能的結構模擬方法，它是通過對大量人工神經元的廣泛并行互聯(lián)，構造人工神經網絡系統(tǒng)去模擬生物神經系統(tǒng)的智能機理的。進化計算是一種對人類智能的演化模擬方法，它是通過對生物遺傳和演化過程的認識，用進化算法去模擬人類智能的進化規(guī)律的。模糊計算是一種對人類智能的邏輯模擬方法，它是通過對人類處理模糊現(xiàn)象的認知能力的認識，用模糊邏輯去模擬人類的智能行為的。從貝慈德克對計算智能的定義和上述計算智能學科范疇的分析，可以看出以下2點：第一，計算智能是借鑒仿生學的思想，基于生物神經系統(tǒng)的結構、進化和認知對自然智能進行模擬的。第二，計算智能是一種以模型（計算模型、數(shù)學模型）為基礎，以分布、并行計算為特征的自然智能模擬方法。

4神經網絡是一種對人類智能的結構模擬方法，它是通過對大5.1.2計算智能的產生與發(fā)展

1992年，貝慈德克在《ApproximateReasoning》學報上首次提出了“計算智能”的概念。1994年6月底到7月初，IEEE在美國佛羅里達州的奧蘭多市召開了首屆國際計算智能大會(簡稱WCCI’94)。會議第一次將神經網絡、進化計算和模糊系統(tǒng)這三個領域合并在一起，形成了“計算智能”這個統(tǒng)一的學科范疇。在此之后，WCCI大會就成了IEEE的一個系列性學術會議，每4年舉辦一次。1998年5月，在美國阿拉斯加州的安克雷奇市又召開了第2屆計算智能國際會議WCCI’98。2002年5月，I在美國州夏威夷州首府火奴魯魯市又召開了第3屆計算智能國際會議WCCI’02。此外，IEEE還出版了一些與計算智能有關的刊物。目前，計算智能的發(fā)展得到了國內外眾多的學術組織和研究機構的高度重視，并已成為智能科學技術一個重要的研究領域。55.1.2計算智能的產生與發(fā)展1992年，貝慈德5.1.3計算智能與人工智能的關系目前，對計算智能與人工智能的關系有2種不同觀點，一種點認為計算智能是人工智能的一個子集，另一種觀點認為計算智能和人工智能是不同的范疇。第一種觀點的代表人物是貝慈德克。他把智能（Intelligence，I）和神經網絡（NeuralNetwork，NN）都分為計算的（Computational，C）、人工的（Artificial，A）和生物的（Biological,B）3個層次，并以模式識別（PR）為例，給出了下圖所示的智能的層次結構。在該圖中，底層是計算智能（CI），它通過數(shù)值計算來實現(xiàn)，其基礎是CNN；中間層是人工智能（AI），它通過人造的符號系統(tǒng)實現(xiàn)，其基礎是ANN；頂層是生物智能（BI），它通過生物神經系統(tǒng)來實現(xiàn)，其基礎是BNN。按照貝慈德克的觀點，CNN是指按生物激勵模型構造的NN，ANN是指CNN+知識，BNN是指人腦，即ANN包含了CNN，BNN又包含了ANN。對智能也一樣，貝慈德克認為AI包含了CI，BI又包含了AI，即計算智能是人工智能的一個子集。65.1.3計算智能與人工智能的關系目前，對計算智能CNNCPRCIANNAPRAIBNNBPRBI人類知識(+)傳感輸入知識(+)傳感數(shù)據計算(+)傳感器B~生物的A~符號的C~數(shù)值的復雜性復雜性輸入層次貝慈德克的智能的3個層次7CNNCPRCIANNAPRAIBNNBPRBI人類知識知識第二種觀點是大多數(shù)學者所持有的觀點，其代表人物是艾伯哈特（R.C.Eberhart）。他們認為：雖然人工智能與計算智能之間有重合，但計算智能是一個全新的學科領域，無論是生物智能還是機器智能，計算智能都是其最核心的部分，而人工智能則是外層。事實上，CI和傳統(tǒng)的AI只是智能的兩個不同層次，各自都有自身的優(yōu)勢和局限性，相互之間只應該互補，而不能取代。大量實踐證明，只有把AI和CI很好地結合起來，才能更好地模擬人類智能，才是智能科學技術發(fā)展的正確方向。8第二種觀點是大多數(shù)學者所持有的觀點，其代表人物是艾5.2神經計算神經計算或叫神經網絡，是計算智能的重要基礎和核心，也是計算智能乃至智能科學技術的一個重要研究領域。本節(jié)的主要內容包括：5.1.1神經計算基礎5.1.2人工神經網絡的互連結構5.1.3人工神經網絡的典型模型至于基于神經網絡的連接學習機制放到第7章學習部分討論。95.2神經計算神經計算或叫神經網絡，是計算智能5.2.1神經計算基礎1.生物神經系統(tǒng)簡介生物神經系統(tǒng)是人工神經網絡的基礎。人工神經網絡是對人腦神經系統(tǒng)的簡化、抽象和模擬，具有人腦功能的許多基本特征。為方便對神經網絡的進一步討論，下面先介紹：(1)生物神經元的結構(2)生物神經元的功能(3)人腦神經系統(tǒng)的聯(lián)結機制105.2.1神經計算基礎生物神經系統(tǒng)是人工神經網絡的(1)生物神經元的結構神經末梢突觸軸突樹突細胞核細胞體它由細胞體(Soma)、軸突(Axon)和樹突(Dendrite)三個主要部分組成

細胞體由細胞核、細胞質和細胞膜等組成，其直徑大約為0.5-100μm大小不等。細胞體是神經元的主體，用于處理由樹突接受的其它神經元傳來的信號,其內部是細胞核，外部是細胞膜，細胞膜的外面是許多向外延伸出的纖維。

11(1)生物神經元的結構神經末梢突觸軸突樹突細胞核細胞體它由軸突是由細胞體向外延伸出的所有纖維中最長的一條分枝，用來向外傳遞神經元產生的輸出電信號。每個神經元都有一條軸突，其最大長度可達1m以上。在軸突的末端形成了許多很細的分枝，這些分支叫神經末梢。每一條神經末梢可以與其它神經元形成功能性接觸，該接觸部位稱為突觸。所謂功能性接觸，是指非永久性的接觸，這正是神經元之間傳遞信息的奧秘之處樹突是指由細胞體向外延伸的除軸突以外的其它所有分支。樹突的長度一般較短，但數(shù)量很多，它是神經元的輸入端，用于接受從其它神經元的突觸傳來的信號。12軸突是由細胞體向外延伸出的所有纖維中最長的一條分枝，(2)生物神經元的功能

根據神經生理學的研究，生物神經元的2個主要功能是:神經元的興奮與抑制，神經元內神經沖動的傳導。①神經元的抑制與興奮抑制狀態(tài)是指神經元在沒有產生沖動時的工作狀態(tài)。興奮狀態(tài)是指神經元產生沖動時的工作狀態(tài)。通常情況下，神經元膜電位約為-70毫伏，膜內為負，膜外為正，處于抑制狀態(tài)。當神經元受到外部刺激時，其膜電位隨之發(fā)生變化，即膜內電位上升、膜外電位下降，當膜內外的電位差大于閾值電位（約+40毫伏）時，神經元產生沖動而進入興奮狀態(tài)。說明:神經元每次沖動的持續(xù)時間大約1毫秒左右，在此期間即使刺激強度再增加也不會引起沖動強度的增加。神經元每次沖動結束后，都會重新回到抑制狀態(tài)。如果神經元受到的刺激作用不能使細胞膜內外的電位差大于閾值電位，則神經元不會產生沖動，將仍處于抑制狀態(tài)。②神經元內神經沖動的傳導神經沖動在神經元內的傳導是一種電傳導過程，神經沖動沿神經纖維傳導的速度卻在3.2---320km/s之間，且其傳導速度與纖維的粗細、髓鞘的有無有一定關系。一般來說，有髓鞘的纖維的傳導速度較快，而無髓鞘的纖維的傳導速度較慢。13(2)生物神經元的功能根據神經生理學的研究，生物(3)人腦神經系統(tǒng)的聯(lián)結機制

①人腦神經系統(tǒng)的聯(lián)結規(guī)模人腦大約由1011--1012個神經元所組成，其中每個神經元大約有3＊104個突觸。小腦中的每個神經元大約有105個突觸，并且每個突觸都可以與別的神經元的一個樹突相連。人腦神經系統(tǒng)就是由這些巨量的生物神經元經廣泛并行互連所形成的一個高度并行性、非常復雜的神經網絡系統(tǒng)。②人腦神經系統(tǒng)的分布功能人腦神經系的記憶和處理功能是有機的結合在一起的，每個神經元既具有存儲功能，同時又具有處理能力。從結構上看，人腦神經系統(tǒng)又是一種分布式系統(tǒng)統(tǒng)。人們通過對腦損壞病人所做的神經生理學研究，沒有發(fā)現(xiàn)大腦中的哪一部分可以決定其余所有各部分的活動，也沒有發(fā)現(xiàn)在大腦中存在有用于驅動和管理整個智能處理過程的任何中央控制部分。即，人類大腦的各個部分是協(xié)同工作、相互影響的。在大腦中，不僅知識的存儲是分散的，而且其控制和決策也是分散的。

14(3)人腦神經系統(tǒng)的聯(lián)結機制①人腦神經系統(tǒng)的聯(lián)人工神經網絡是由大量的人工神經元經廣泛互聯(lián)所形成的一種人工網絡系統(tǒng)，用以模擬人類神經系統(tǒng)的結構和功能。(1)人工神經元的結構(2)常用的人工神經元模型

5.2.1神經計算基礎2.人工神經網絡簡介15人工神經網絡是由大量的人工神經元經廣泛互聯(lián)所形成的一人工神經元的結構θ…x1x2xnw1w2wny人工神經元是對生物神經元的抽象與模擬下圖是一個MP神經元模型

1943年，心理學家麥克洛奇(W.McMulloch)和數(shù)理邏輯學家皮茨(W.Pitts)根據生物神經元的功能和結構，提出了一個將神經元看作二進制閾值元件的簡單模型，即MP模型。圖中的x1,x2,…,xn表示某一神經元的n個輸入；wi表示第i個輸入的連接強度，稱為連接權值；θ為神經元的閾值；y為神經元的輸出。可見，人工神經元是一個具有多輸入，單輸出的非線性器件。其輸入為,輸出為其中，f稱為神經元功能函數(shù)（或作用函數(shù)，激活函數(shù)）。16人工神經元的結構θ…x1x2xnw1w2wny人工神經元是對常用的人工神經元模型根據功能函數(shù)的不同，可得到不同的神經元模型。常用模型包括：閾值型(Threshold)θf(θ)1這種模型的神經元沒有內部狀態(tài)，作用函數(shù)f是一個階躍函數(shù)，他表示激活值σ和輸出之間的關系。這是一種連續(xù)的神經元模型，其輸入輸出特性常用指數(shù)、對數(shù)或雙曲正切等S型函數(shù)表示。它反映的是神經元的飽和特性.分段線性強飽和型(LinearSaturation)S型(Sibmoid)子閾累積型(SubthresholdSummation)也是一個非線性函數(shù)，當產生的激活值超過T值時，該神經元被激活產生個反響。在線性范圍內，系統(tǒng)的反響是線性的。T1這種模型又稱為偽線性，其輸入/輸出之間在一定范圍內滿足線性關系，一直延續(xù)到輸出為最大值1為止。但當達到最大值后，輸出就不再增。17常用的人工神經元模型根據功能函數(shù)的不同，可得到不同的神經元模5.2.2人工神經網絡的互聯(lián)結構人工神經網絡的互連結構（或稱拓撲結構）是指單個神經元之間的連接模式，它是構造神經網絡的基礎，也是神經網絡誘發(fā)偏差的主要來源。從互連結構的角度：前饋網絡反饋網絡單層前饋網絡

多層前饋網絡

單層反饋網絡多層反饋網絡僅含輸入層和輸出層，且只有輸出層的神經元是可計算節(jié)點

除擁有輸入、輸出層外，還至少含有一個、或更多個隱含層的前向網絡

指不擁有隱含層的反饋網絡

指擁有隱含層的反饋網絡

可含有反饋聯(lián)結只包含前向聯(lián)結

185.2.2人工神經網絡的互聯(lián)結構人工神經網絡的互連結包括單層前饋網絡和多層前饋網絡。單層前饋網絡是指那種只擁有單層計算節(jié)點的前向網絡。它僅含有輸入層和輸出層，且只有輸出層的神經元是可計算節(jié)點，如下圖所示其中，輸入向量為X=(x1,x2,…,xn)；輸出向量為Y=(y1,y2,…,ym)；輸入層各個輸入到相應神經元的連接權值分別是wij，i=1,2,..,n，j=1,2,..,m?！瓁1X2X3xny1Y2ym權值wij輸出層輸入層圖5.8單層前饋網絡結構5.2.2人工神經網絡的互聯(lián)結構1.前饋網絡(1/3)19包括單層前饋網絡和多層前饋網絡?！瓁1X2X3xn若假設各神經元的閾值分別是θj，j=1,2,…,m，則各神經元的輸出yj,j=1,2,..,m分別為：其中，由所有連接權值wij構成的連接權值矩陣W為：

在實際應用中，該矩陣是通過大量的訓練示例學習而形成的。5.2.2人工神經網絡的互聯(lián)結構1.前饋網絡(2/3)20若假設各神經元的閾值分別是θj，j=1,2,…,m，多層前饋網絡是指那種除擁有輸入、輸出層外，還至少含有一個、或更多個隱含層的前饋網絡。隱含層是指由那些既不屬于輸入層又不屬于輸出層的神經元所構成的處理層,也被稱為中間層。隱含層的作用是通過對輸入層信號的加權處理，將其轉移成更能被輸出層接受的形式。

多層前饋網絡的輸入層的輸出向量是第一隱含層的輸入信號，而第一隱含層的輸出則是第二隱含層的輸入信號，以此類推，直到輸出層。多層前饋網絡的典型代表是BP網絡。x1X2Xny1Ym隱含層輸出層輸入層圖5.9多層前饋網絡結構………權值權值5.2.2人工神經網絡的互聯(lián)結構1.前饋網絡(3/3)21多層前饋網絡是指那種除擁有輸入、輸出層外，還至少含5.2.2人工神經網絡的互聯(lián)結構2.反饋網絡

反饋網絡是指允許采用反饋聯(lián)結方式所形成的神經網絡。所謂反饋聯(lián)結方式是指一個神經元的輸出可以被反饋至同層或前層的神經元。

反饋網絡和前向網絡不同：

前向網絡屬于非循環(huán)連接模式，它的每個神經元的輸入都沒有包含該神經元先前的輸出，因此不具有“短期記憶”的性質。

反饋網絡則不同，它的每個神經元的輸入都有可能包含有該神經元先前輸出的反饋信息，即一個神經元的輸出是由該神經元當前的輸入和先前的輸出這兩者來決定的，這就有點類似于人類的短期記憶的性質。反饋網絡的典型例子是后面將要介紹的Hopfield網絡225.2.2人工神經網絡的互聯(lián)結構反饋網絡是指允許人工神經網絡的模型是指對網絡結構、聯(lián)結權值和學習能力的總括。常用的網絡模型已有數(shù)十種。例如：傳統(tǒng)的感知機模型，具有誤差反向傳播功能的反向傳播網絡模型，采用多變量插值的徑向基函數(shù)網絡模型，建立在統(tǒng)計學習理論基礎上的支撐向量機網絡模型，采用反饋聯(lián)接方式的反饋網絡模型，基于模擬退火算法的隨機網絡模型。本小節(jié)主要討論感知機（Perceptron）模型反向傳播（BP）模型反饋網絡（Hopfield）模型

3.2.3人工神經網絡的典型模型

23人工神經網絡的模型是指對網絡結構、聯(lián)結權值和學習能感知器是美國學者羅森勃拉特（Rosenblatt）于1957年為研究大腦的存儲、學習和認知過程而提出的一類具有自學習能力的神經網絡模型，其拓撲結構是一種分層前向網絡。它包括：單層感知器多層感知器3.2.3人工神經網絡的典型模型1.感知器模型(1/10)24感知器是美國學者羅森勃拉特（Rosenblatt）于1(1)單層感知器單層感知器是一種只具有單層可調節(jié)連接權值神經元的前向網絡，這些神經元構成了單層感知器的輸出層，是感知器的可計算節(jié)點。在單層感知器中，每個可計算節(jié)點都是一個線性閾值神經元。當輸入信息的加權和大于或等于閾值時，輸出為1，否則輸出為0或-1。單層感知器的輸出層的每個神經元都只有一個輸出，且該輸出僅與本神經元的輸入及聯(lián)接權值有關，而與其他神經元無關。3.2.3人工神經網絡的典型模型1.感知器模型(2/10)25(1)單層感知器3.2.3人工神經網絡的典型模型25單層感知器的結構如下圖…x1x2xn…y1ym輸入層輸出層權值wij輸入向量為X=(x1,x2,…,xn)；輸出向量為Y=(y1,y2,…,ym)；輸入層各個輸入到相應神經元的連接權值分別是wij，i=1,2,..,n，j=1,2,..,m。

若假設各神經元的閾值分別是θj，j=1,2,…,m，則各神經元的輸出yj,j=1,2,..,m分別為其中，由所有連接權值wji構成的連接權值矩陣W為：在實際應用中，該矩陣是通過大量的訓練示例學習而形成的26單層感知器的結構如下圖…x1x2xn…y1ym輸入層輸出層權使用感知器的主要目的是為了對外部輸入進行分類。羅森勃拉特已經證明，如果外部輸入是線性可分的（指存在一個超平面可以將它們分開），則單層感知器一定能夠把它劃分為兩類。其判別超平面由如下判別式確定：

作為例子，下面討論用單個感知器實現(xiàn)邏輯運算的問題。事實上，單層感知器可以很好地實現(xiàn)“與”、“或”、“非”運算，但卻不能解決“異或”問題。

3.2.3人工神經網絡的典型模型1.感知器模型(4/10)27使用感知器的主要目的是為了對外部輸入進行分類。羅森例5.1“與”運算（x1∧x2）(0,0)(1,1)(0,1)(1,0)圖5.10與運算問題圖示輸入輸出超平面閾值條件x1x2x1∧x2w1*x1+w2*x2-θ=0000w1*0+w2*0-θ＜0θ＞0010w1*0+w2*1

-θ＜0θ＞w2100w1*1+w2*0-θ＜0θ＞w1

111w1*1+w2*1-θ≥0θ≤w1+w2

可以證明此表有解，例如取w1=1，w2=1，θ=1.5，其分類結果如右圖所示。其中，輸出為1的用實心圓，輸出為0的用空心圓。后面約定相同。3.2.3人工神經網絡的典型模型1.感知器模型(5/10)28例5.1“與”運算（x1∧x2）(0,0)(1,1)(0,例5.2“或”運算（x1∨x2）輸入輸出超平面閾值條件x1x2x1∨x2w1*x1+w2*x2-θ=0000w1*0+w2*0-θ＜0θ＞0011w1*0+w2*1

-θ≥0θ≤w2101w1*1+w2*0-θ≥0θ≤w1

111w1*1+w2*1-θ≥0θ≤w1+w2

此表也有解，例如取w1=1，w2=1，θ=0.5，其分類結果如右圖所示。(0,1)(0,0)(1,0)圖5.11與運算問題圖示(1,1)3.2.3人工神經網絡的典型模型1.感知器模型(6/10)29例5.2“或”運算（x1∨x2）輸入輸出超平面閾值條件x1例5.3“非”運算（?x1）輸入輸出超平面閾值條件x1?x1w1*x1-θ=001w1*0-θ≥0θ≤010w1*1

–θ<0θ>w1此表也有解，例如取w1=-1，θ=-0.5，其分類結果如右圖所示。圖5.12非運算問題圖示013.2.3人工神經網絡的典型模型1.感知器模型(7/10)30例5.3“非”運算（?x1）輸入輸出超平面閾值條件x1?x例5.4“異或”運算（x1XORx2）輸入輸出超平面閾值條件x1x2X1XORx2w1*x1+w2*x2-θ=0000w1*0+w2*0-θ＜0θ＞0011w1*0+w2*1-θ≥0θ≤w2101w1*1+w2*0-θ≥0θ≤w1

110w1*1+w2*1-θ<0θ>w1+w2

此表無解，即無法找到滿足條件的w1、w2和θ，如右圖所示。因為異或問題是一個非線性可分問題，需要用多層感知器來解決。(0,1)(0,0)(1,0)圖5.13異或運算問題圖示(1,1)3.2.3人工神經網絡的典型模型1.感知器模型(8/10)31例5.4“異或”運算（x1XORx2）輸入輸出超平面閾(2)多層感知器多層感知器是通過在單層感知器的輸入、輸出層之間加入一層或多層處理單元所構成的。其拓撲結構與圖5.9所示的多層前向網絡相似，差別也在于其計算節(jié)點的連接權值是可變的。多層感知器的輸入與輸出之間是一種高度非線性的映射關系，如圖5.9所示的多層前向網絡，若采用多層感知器模型，則該網絡就是一個從n維歐氏空間到m維歐氏空間的非線性映射。因此，多層感知器可以實現(xiàn)非線性可分問題的分類。例如，對“異或”運算，用圖5.14所示的多層感知器即可解決。3.2.3人工神經網絡的典型模型1.感知器模型(9/10)32(2)多層感知器3.2.3人工神經網絡的典型模型x11y=x1

XORx2x1X2x121-1111-1輸入層隱層輸出層權值權值圖5.14“異或”問題的多層感知器閾值0.5閾值-1.5閾值1.5(0,1)(0,0)(1,0)圖5.15異或問題的解決(1,1)在圖5.14中，隱層神經元x11所確定的直線方程為它可以識別一個半平面。隱層神經元x12所確定的直線方程為它也可以識別一個半平面。輸出層神經元所確定的直線方程為它相當于對隱層神經元x11和x12的輸出作“邏輯與”運算，因此可識別由隱層已識別的兩個半平面的交集所構成的一個凸多邊形，如圖5.15所示。

33x11y=x1XORx2x1X2x121-1111-1輸

誤差反向傳播(ErrorBackPropagation)網絡通常簡稱為BP(BackPropagation)網絡，是由美國加州大學的魯梅爾哈特和麥克萊蘭在研究并行分布式信息處理方法，探索人類認知微結構的過程中，于1985年提出的一種網絡模型。BP網絡的網絡拓撲結構是多層前向網絡，如圖5.16所示。在BP網絡中，同層節(jié)點之間不存在相互連接，層與層之間多采用全互連方式，且各層的連接權值可調。BP網絡實現(xiàn)了明斯基的多層網絡的設想，是當今神經網絡模型中使用最廣泛的一種。y1y2ymx1x2xn輸出層隱含層輸入層權可調權可調………圖5.16一個多層BP網絡的結構3.2.3人工神經網絡的典型模型2.BP網絡模型(1/2)34誤差反向傳播(ErrorBackPropagat

對BP網絡需說明以下兩點：第一，BP網絡的每個處理單元均為非線性輸入/輸出關系，其作用函數(shù)通常采用的是可微的Sigmoid函數(shù)，如：第二，BP網絡的學習過程是由工作信號的正向傳播和誤差信號的反向傳播組成的。所謂正向傳播，是指輸入模式經隱層到輸出層，最后形成輸出模式；所謂誤差反向傳播，是指從輸出層開始逐層將誤差傳到輸入層，并修改各層聯(lián)接權值，使誤差信號為最小的過程。3.2.3人工神經網絡的典型模型2.BP網絡模型(2/2)35對BP網絡需說明以下兩點：3.2.3人工神經網絡的典

Hopfield網絡是由美國加州工學院物理學家霍普菲爾特1982年提出來的一種單層全互連的對稱反饋網絡模型。它可分為離散Hopfield網絡和連續(xù)Hopfield網絡，限于篇幅，本書重點討論離散Hopfield網絡。離散Hopfield網絡的結構離散Hopfield網絡是在非線性動力學的基礎上由若干基本神經元構成的一種單層全互連網絡，其任意神經元之間均有連接，并且是一種對稱連接結構。一個典型的離散Hopfidld網絡結構如圖5-17所示。離散Hopfield網絡模型是一個離散時間系統(tǒng)，每個神經元只有0和1（或-1和1）兩種狀態(tài)，任意神經元i和j之間的連接權值為wij。由于神經元之間為對稱連接，且神經元自身無連接，因此有

由該連接權值所構成的連接矩陣是一個零對角的對稱矩陣。3.2.3人工神經網絡的典型模型2.Hopfield網絡模型(1/2)36Hopfield網絡是由美國加州工學院物理學家霍普菲爾圖5?17離散Hopfield網絡的結構ymY2Y1x1……x2xn輸入層輸出層在Hopfidld網絡中，雖然神經元自身無連接，但由于每個神經元都與其他神經元相連，即每個神經元的輸出都將通過突觸連接權值傳遞給別的神經元，同時每個神經元又都接受其他神經元傳來的信息，這樣對每個神經元來說，其輸出經過其他神經元后又有可能反饋給自己，因此Hopfidld網絡是一種反饋神經網絡

3.2.3人工神經網絡的典型模型2.Hopfield網絡模型(2/2)37圖5?17離散Hopfield網絡的結構ymY2Y1x1

進化計算（EvolutionaryComputation,EC）是在達爾文（Darwin）的進化論和孟德爾（Mendel）的遺傳變異理論的基礎上產生的一種在基因和種群層次上模擬自然界生物進化過程與機制的問題求解技術。它主要包括遺傳算法（GeneticAlgorithm，GA）進化策略（EvolutionaryStrategy,ES）進化規(guī)劃（EvolutionaryProgramming,EP）遺傳規(guī)劃（GeneticProgramming,GP）四大分支。其中，第一個分支是進化計算中最初形成的一種具有普遍影響的模擬進化優(yōu)化算法。因此我們主要討論遺傳算法。5.3進化計算38進化計算（EvolutionaryComputat進化計算是一種模擬自然界生物進化過程與機制進行問題求解的自組織、自適應的隨機搜索技術。它以達爾文進化論的“物竟天擇、適者生存”作為算法的進化規(guī)則，并結合孟德爾的遺傳變異理論，將生物進化過程中的繁殖（Reproduction）變異（Mutation）競爭（Competition）選擇（Selection）引入到了算法中。5.3.1進化計算概述1.進化計算及其生物學基礎(1/3)(1)什么是進化計算39進化計算是一種模擬自然界生物進化過程與機制進行問題求(2)進化計算的生物學基礎

自然界生物進化過程是進化計算的生物學基礎，它主要包括遺傳(Heredity)、變異(Mutation)和進化(Evolution)理論。①遺傳理論

遺傳是指父代（或親代）利用遺傳基因將自身的基因信息傳遞給下一代（或子代），使子代能夠繼承其父代的特征或性狀的這種生命現(xiàn)象。正是由于遺傳的作用，自然界才能有穩(wěn)定的物種。在自然界，構成生物基本結構與功能的單位是細胞（Cell）。細胞中含有一種包含著所有遺傳信息的復雜而又微小的絲狀化合物，人們稱其為染色體（Chromosome）。在染色體中，遺傳信息由基因（Gene）所組成，基因決定著生物的性狀，是遺傳的基本單位。染色體的形狀是一種雙螺旋結構，構成染色體的主要物質叫做脫氧核糖核酸(DNA)，每個基因都在DNA長鏈中占有一定的位置。一個細胞中的所有染色體所攜帶的遺傳信息的全體稱為一個基因組(Genome)。細胞在分裂過程中，其遺傳物質DNA通過復制轉移到新生細胞中，從而實現(xiàn)了生物的遺傳功能。5.3.1進化計算概述1.進化計算及其生物學基礎(2/3)40(2)進化計算的生物學基礎5.3.1進化計算概②變異理論

變異是指子代和父代之間，以及子代的各個不同個體之間產生差異的現(xiàn)象。變異是生物進化過程中發(fā)生的一種隨機現(xiàn)象，是一種不可逆過程，在生物多樣性方面具有不可替代的作用。引起變異的主要原因有以下兩種：雜交，是指有性生殖生物在繁殖下一代時兩個同源染色體之間的交配重組，即兩個染色體在某一相同處的DNA被切斷后再進行交配重組，形成兩個新的染色體。復制差錯，是指在細胞復制過程中因DNA上某些基因結構的隨機改變而產生出新的染色體。③進化論

進化是指在生物延續(xù)生存過程中，逐漸適應其生存環(huán)境，使得其品質不斷得到改良的這種生命現(xiàn)象。遺傳和變異是生物進化的兩種基本現(xiàn)象，優(yōu)勝劣汰、適者生存是生物進化的基本規(guī)律。達爾文的自然選擇學說認為：在生物進化中，一種基因有可能發(fā)生變異而產生出另一種新的生物基因。這種新基因將依據其與生存環(huán)境的適應性而決定其增殖能力。一般情況下，適應性強的基因會不斷增多，而適應性差的基因則會逐漸減少。通過這種自然選擇，物種將逐漸向適應于生存環(huán)境的方向進化，甚至會演變成為另一個新的物種，而那些不適應于環(huán)境的物種將會逐漸被淘汰。5.3.1進化計算概述1.進化計算及其生物學基礎(3/3)41②變異理論5.3.1進化計算概述41

進化計算自20世紀50年代以來，其發(fā)展過程大致可分為三個階段。①萌芽階段這一階段是從20世紀50年代后期到70年代中期。20世紀50年代后期，一些生物學家在研究如何用計算機模擬生物遺傳系統(tǒng)中，產生了遺傳算法的基本思想，并于1962年由美國密執(zhí)安（Michigan）大學霍蘭德（Holland）提出。1965年德國數(shù)學家雷切伯格（Rechenberg）等人提出了一種只有單個個體參與進化，并且僅有變異這一種進化操作的進化策略。同年，美國學者弗格爾（Fogel）提出了一種具有多個個體和僅有變異一種進化操作的進化規(guī)劃。1969年美國密執(zhí)安（Michigan）大學的霍蘭德（Holland）提出了系統(tǒng)本身和外部環(huán)境相互協(xié)調的遺傳算法。至此，進化計算的三大分支基本形成。②成長階段這一階段是從20世紀70年代中期到80年代后期。1975年，霍蘭德出版專著《自然和人工系統(tǒng)的適應性（AdaptationinNaturalandArtificialSystem）》，全面介紹了遺傳算法。同年，德國學者施韋費爾（Schwefel）在其博士論文中提出了一種由多個個體組成的群體參與進化的，并且包括了變異和重組這兩種進化操作的進化策略。1989年，霍蘭德的學生戈爾德伯格（Goldberg）博士出版專著《遺傳算法----搜索、優(yōu)化及機器學習（GeneticAlgorithm----inSearchOptimizationandMachineLearning）》，使遺傳算法得到了普及與推廣。5.3.1進化計算概述2.進化計算的產生與發(fā)展(1/2)42進化計算自20世紀50年代以來，其發(fā)展過程大致可分③發(fā)展階段

這一階段是從20世紀90年代至今。1989年，美國斯坦福（Stanford）大學的科扎（Koza）提出了遺傳規(guī)劃的新概念，并于1992年出版了專著《遺傳規(guī)劃----應用自然選擇法則的計算機程序設計（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection）》該書全面介紹了遺傳規(guī)劃的基本原理及應用實例，標志著遺傳規(guī)劃作為計算智能的一個分支已基本形成。進入20世紀90年代以來，進化計算得到了眾多研究機構和學者的高度重視，新的研究成果不斷出現(xiàn)、應用領域不斷擴大。目前，進化計算已成為人工智能領域的又一個新的研究熱點。

5.3.1進化計算概述2.進化計算的產生與發(fā)展(2/2)43③發(fā)展階段5.3.1進化計算概述43進化計算盡管有多個重要分支，并且不同分支的編碼方案、選擇策略和進化操作也有可能不同，但它們卻有著共同的進化框架。若假設P為種群(Population，或稱為群體)，t為進化代數(shù)，P(t)為第t代種群,則進化計算的基本結構可粗略描述如下：{確定編碼形式并生成搜索空間；初始化各個進化參數(shù)，并設置進化代數(shù)t=0；初始化種群P(0);對初始種群進行評價（即適應度計算）；while（不滿足終止條件）do{t=t+1;利用選擇操作從P(t-1)代中選出P(t)代群體；對P(t)代種群執(zhí)行進化操作；對執(zhí)行完進化操作后的種群進行評價（即適應度計算）；}}可以看出，上述基本結構包含了生物進化中所必需的選擇操作、進化操作和適應度評價等過程。5.3.1進化計算概述3.進化計算的基本結構44進化計算盡管有多個重要分支，并且不同分支的編碼方案遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個體，并通過雜交、變異來產生新一代種群，如此逐代進化，直到滿足目標為止。遺傳算法所涉及到的基本概念主要有以下幾個：

種群（Population）：種群是指用遺傳算法求解問題時，初始給定的多個解的集合。遺傳算法的求解過程是從這個子集開始的。

個體（Individual）：個體是指種群中的單個元素，它通常由一個用于描述其基本遺傳結構的數(shù)據結構來表示。例如，可以用0、1組成的長度為l的串來表示個體。

染色體（Chromos）：染色體是指對個體進行編碼后所得到的編碼串。染色體中的每1位稱為基因，染色體上由若干個基因構成的一個有效信息段稱為基因組。

適應度（Fitness）函數(shù)：適應度函數(shù)是一種用來對種群中各個個體的環(huán)境適應性進行度量的函數(shù)。其函數(shù)值是遺傳算法實現(xiàn)優(yōu)勝劣汰的主要依據

遺傳操作（GeneticOperator）：遺傳操作是指作用于種群而產生新的種群的操作。標準的遺傳操作包括以下3種基本形式：

選擇（Selection）

交叉（Crosssover）

變異（Mutation）5.3.2遺傳算法1.遺傳算法的基本概念45遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者

遺傳算法主要由染色體編碼、初始種群設定、適應度函數(shù)設定、遺傳操作設計等幾大部分所組成，其算法主要內容和基本步驟可描述如下：

(1)選擇編碼策略，將問題搜索空間中每個可能的點用相應的編碼策略表示出來，即形成染色體；(2)定義遺傳策略，包括種群規(guī)模N，交叉、變異方法，以及選擇概率Pr、交叉概率Pc、變異概率Pm等遺傳參數(shù)；(3)令t=0，隨機選擇N個染色體初始化種群P(0)；(4)定義適應度函數(shù)f（f>0）；(5)計算P(t)中每個染色體的適應值；(6)t=t+1；(7)運用選擇算子，從P(t-1)中得到P(t)；(8)對P(t)中的每個染色體，按概率Pc參與交叉；(9)對染色體中的基因，以概率Pm參與變異運算；(10)判斷群體性能是否滿足預先設定的終止標準，若不滿足則返回(5)。5.3.2遺傳算法2.遺傳算法的基本結構(1/2)46遺傳算法主要由染色體編碼、初始種群設定、適應度函數(shù)計算種群中各個個體的適應度，并進行評價滿足終止條件嗎？終止選擇交叉變異Y圖5-18基本遺傳算法的算法流程圖編碼和生成初始種群N選擇其算法流程如圖5-18所示。5.3.2遺傳算法2.遺傳算法的基本結構(2/2)47計算種群中各個個體的適應度，并進行評價滿足終止條件嗎？終止選常用的遺傳編碼算法有霍蘭德二進制碼、格雷碼（GrayCode）、實數(shù)編碼和字符編碼等。

(1)二進制編碼（Binaryencoding）

二進制編碼是將原問題的結構變換為染色體的位串結構。在二進制編碼中，首先要確定二進制字符串的長度l，該長度與變量的定義域和所求問題的計算精度有關。例5.5

假設變量x的定義域為[5，10]，要求的計算精度為10-5，則需要將[5，10]至少分為600000個等長小區(qū)間，每個小區(qū)間用一個二進制串表示。于是，串長至少等于20，原因是：524288=219<600000<220=1048576這樣，對應于區(qū)間[5，10]內滿足精度要求的每個值x，都可用一個20位編碼的二進制串<b19,b18,…,b0>來表示。

二進制編碼存在的主要缺點是漢明（Hamming）懸崖。例如，7和8的二進制數(shù)分別為0111和1000，當算法從7改進到8時，就必須改變所有的位。

5.3.2遺傳算法3.遺傳編碼(1/3)48常用的遺傳編碼算法有霍蘭德二進制碼、格雷碼（Gray5.3.2遺傳算法3.遺傳編碼(2/3)(2)格雷編碼（Grayencoding）

格雷編碼是對二進制編碼進行變換后所得到的一種編碼方法。這種編碼方法要求兩個連續(xù)整數(shù)的編碼之間只能有一個碼位不同，其余碼位都是完全相同的。它有效地解決了漢明懸崖問題，其基本原理如下：設有二進制串b1,b2,…,bn，對應的格雷串為a1,a2,…,an，則從二進制編碼到格雷編碼的變換為：其中，⊕表示模2加法。而從一個格雷串到二進制串的變換為：例5.6

十進制數(shù)7和8的二進制編碼分別為0111和1000，而其格雷編碼分別為0100和1100。495.3.2遺傳算法(2)格雷編碼（Grayen

(3)實數(shù)編碼（Realencoding）

實數(shù)編碼是將每個個體的染色體都用某一范圍的一個實數(shù)（浮點數(shù)）來表示，其編碼長度等于該問題變量的個數(shù)。這種編碼方法是將問題的解空間映射到實數(shù)空間上，然后在實數(shù)空間上進行遺傳操作。由于實數(shù)編碼使用的是變量的真實值，因此這種編碼方法也叫做真值編碼方法。實數(shù)編碼適應于那種多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題。

5.3.2遺傳算法3.遺傳編碼(3/3)50(3)實數(shù)編碼（Realencoding）5.

適應度函數(shù)是一個用于對個體的適應性進行度量的函數(shù)。通常，一個個體的適應度值越大，它被遺傳到下一代種群中的概率也就越大。(1)常用的適應度函數(shù)

在遺傳算法中，有許多計算適應度的方法，其中最常用的適應度函數(shù)有以下兩種：①原始適應度函數(shù)它是直接將待求解問題的目標函數(shù)f(x)定義為遺傳算法的適應度函數(shù)。例如，在求解極值問題時，f(x)即為x的原始適應度函數(shù)。采用原始適應度函數(shù)的優(yōu)點是能夠直接反映出待求解問題的最初求解目標，其缺點是有可能出現(xiàn)適應度值為負的情況。

5.3.2遺傳算法4.適應度函數(shù)(1/4)51適應度函數(shù)是一個用于對個體的適應性進行度量的函數(shù)。②標準適應度函數(shù)在遺傳算法中，一般要求適應度函數(shù)非負，并其適應度值越大越好。這就往往需要對原始適應函數(shù)進行某種變換，將其轉換為標準的度量方式，以滿足進化操作的要求，這樣所得到的適應度函數(shù)被稱為標準適應度函數(shù)fNormal(x)。極小化問題對極小化問題，其標準適應度函數(shù)可定義為其中，fmax(x)是原始適應函數(shù)f(x)的一個上界。如果fmax(x)未知，則可用當前代或到目前為止各演化代中的f(x)的最大值來代替。可見，fmax(x)是會隨著進化代數(shù)的增加而不斷變化的。

5.3.2遺傳算法4.適應度函數(shù)(2/4)52②標準適應度函數(shù)5.3.2遺傳算法52極大化問題對極大化問題，其標準適應度函數(shù)可定義為其中，fmin(x)是原始適應函數(shù)f(x)的一個下界。如果fmin(x)未知，則可用當前代或到目前為止各演化代中的f(x)的最小值來代替。

5.3.2遺傳算法4.適應度函數(shù)(3/4)53極大化問題5.3.2遺傳算法53(2)適應度函數(shù)的加速變換在某些情況下，適應度函數(shù)在極值附近的變化可能會非常小，以至于不同個體的適應值非常接近，使得難以區(qū)分出哪個染色體更占優(yōu)勢。對此，最好能定義新的適應度函數(shù)，使該適應度函數(shù)既與問題的目標函數(shù)具有相同的變化趨勢，又有更快的變化速度。適應度函數(shù)的加速變換有兩種基本方法①線性加速適應度函數(shù)的定義如下：

f’(x)=αf(x)+β其中，f(x)是加速轉換前的適應度函數(shù)；f’(x)是加速轉換后的適應度函數(shù)；α和β是轉換系數(shù)。②非線性加速冪函數(shù)變換方法

f’(x)=f(x)k指數(shù)變換方法

f’(x)=exp(-βf(x))5.3.2遺傳算法4.適應度函數(shù)(4/4)54(2)適應度函數(shù)的加速變換5.3.2遺傳算法54

遺傳算法中的基本遺傳操作包括選擇、交叉和變異3種，而每種操作又包括多種不同的方法，下面分別對它們進行介紹。(1).選擇操作

選擇（Selection）操作是指根據選擇概率按某種策略從當前種群中挑選出一定數(shù)目的個體，使它們能夠有更多的機會被遺傳到下一代中。常用的選擇策略可分為比例選擇、排序選擇和競技選擇三種類型。①比例選擇

比例選擇方法（ProportionalModel）的基本思想是：各個個體被選中的概率與其適應度大小成正比。常用的比例選擇策略包括輪盤賭選擇繁殖池選擇5.3.2遺傳算法5.基本遺傳操作(1/11)55遺傳算法中的基本遺傳操作包括選擇、交叉和變異3種，而②輪盤賭選擇

輪盤賭選擇法又被稱為轉盤賭選擇法或輪盤選擇法。在這種方法中，個體被選中的概率取決于該個體的相對適應度。而相對適應度的定義為：其中，P(xi)是個體xi的相對適應度，即個體xi被選中的概率；f(xi)是個體xi的原始適應度；是種群的累加適應度。輪盤賭選擇算法的基本思想是：根據每個個體的選擇概率P(xi)將一個圓盤分成N個扇區(qū)，其中第i個扇區(qū)的中心角為：并再設立一個固定指針。當進行選擇時，可以假想轉動圓盤，若圓盤靜止時指針指向第i個扇區(qū)，則選擇個體i。其物理意義如圖5-19所示。

5.3.2遺傳算法5.基本遺傳操作(2/11)56②輪盤賭選擇5.3.2遺傳算法56P(x1)P(x2)P(xN)……P(xi)2πp(xi)圖5-19輪盤賭選擇從統(tǒng)計角度看，個體的適應度值越大，其對應的扇區(qū)的面積越大，被選中的可能性也越大。這種方法有點類似于發(fā)放獎品使用的輪盤，并帶有某種賭博的意思，因此亦被稱為輪盤賭選擇。5.3.2遺傳算法5.基本遺傳操作(3/11)57P(x1)P(x2)P(xN)……P(xi)圖5-19輪盤

(2)交叉操作

交叉（Crossover）操作是指按照某種方式對選擇的父代個體的染色體的部分基因進行交配重組，從而形成新的個體。交配重組是自然界中生物遺傳進化的一個主要環(huán)節(jié)，也是遺傳算法中產生新的個體的最主要方法。根據個體編碼方法的不同，遺傳算法中的交叉操作可分為二進制交叉和實值交叉兩種類型。①二進制交叉

二進制交叉（BinaryValuedCrossover）是指二進制編碼情況下所采用的交叉操作，它主要包括單點交叉、兩點交叉、多點交叉和均勻交叉等方法。5.3.2遺傳算法5.基本遺傳操作(4/11)58(2)交叉操作5.3.2遺傳算法58單點交叉

單點交叉也稱簡單交叉，它是先在兩個父代個體的編碼串中隨機設定一個交叉點，然后對這兩個父代個體交叉點前面或后面部分的基因進行交換，并生成子代中的兩個新的個體。假設兩個父代的個體串分別是：X=x1x2…xkxk+1…xnY=y1y2…ykyk+1…yn隨機選擇第k位為交叉點，若采用對交叉點后面的基因進行交換的方法，但點交叉是將X中的xk+1到xn部分與Y中的yk+1到y(tǒng)n部分進行交叉，交叉后生成的兩個新的個體是：X’=x1x2…xk

yk+1…yn

Y’=y1y2…yk

xk+1…xn

例5.7

設有兩個父代的個體串A=001101

和B=110010

，若隨機交叉點為4，則交叉后生成的兩個新的個體是：A’=001110

B’=110001

5.3.2遺傳算法5.基本遺傳操作(5/11)59單點交叉5.3.2遺傳算法59兩點交叉

兩點交叉是指先在兩個父代個體的編碼串中隨機設定兩個交叉點，然后再按這兩個交叉點進行部分基因交換，生成子代中的兩個新的個體。假設兩個父代的個體串分別是：X=x1x2…xi…xj…xnY=y1y2…yi…yj…,yn隨機設定第i、j位為兩個交叉點（其中i<j<n），兩點交叉是將X中的xi+1到xj部分與Y中的yi+1到y(tǒng)j部分進行交換，交叉后生成的兩個新的個體是：X’=x1x2…xi

yi+1…yjxj+1…xn

Y’=y1y2…yi

xi+1…xjyj+1…yn

例5.8

設有兩個父代的個體串A=001101和B=110010，若隨機交叉點為3和5，則交叉后的兩個新的個體是：A’=001011B’=1101005.3.2遺傳算法5.基本遺傳操作(6/11)60兩點交叉5.3.2遺傳算法60多點交叉多點交是指先隨機生成多個交叉點，然后再按這些交叉點分段地進行部分基因交換，生成子代中的兩個新的個體。假設交叉點個數(shù)為m，則可將個體串劃分為m+1個分段，其劃分方法是：當m為偶數(shù)時，對全部交叉點依次進行兩兩配對，構成m/2個交叉段。當m為奇數(shù)時，對前(m-1)個交叉點依次進行兩兩配對，構成(m-1)/2個交叉段，而第m個交叉點則按單點交叉方法構成一個交叉段。下面以m=3為例進行討論。假設兩個父代的個體串分別是X=x1x2…xi…xj…xk…xn和Y=y1y2…yi…yj…yk…yn，隨機設定第i、j、k位為三個交叉點（其中i<j<k<n），則將構成兩個交叉段。交叉后生成的兩個新的個體是：X’=x1x2…xiyi+1…yj

xj+1…xk

yk+1

…yn

Y’=y1y2…yi

xi+1…xjyj+1…yk

xk+1…xn

例5.9

設有兩個父代的個體串A=001101和B=110010，若隨機交叉點為1、3和5，則交叉后的兩個新的個體是：A’=010100

B’=101011

5.3.2遺傳算法5.基本遺傳操作(7/11)61多點交叉5.3.2遺傳算法61均勻交叉均勻交叉（UniformCrossover）是先隨機生成一個與父串具有相同長度，并被稱為交叉模版（或交叉掩碼）的二進制串，然后再利用該模版對兩個父串進行交叉，即將模版中1對應的位進行交換，而0對應的位不交換，依此生成子代中的兩個新的個體。事實上，這種方法對父串中的每一位都是以相同的概率隨機進行交叉的。例5.10

設有兩個父代的個體串A=001101和B=110010，若隨機生成的模版T=010011，則交叉后的兩個新的個體是A’=011010和B’=100101。即A：001101B：110010T：010011A’：01111

0

B’：10000

15.3.2遺傳算法5.基本遺傳操作(8/11)62均勻交叉5.3.2遺傳算法62

實值交叉實值交叉是在實數(shù)編碼情況下所采用的交叉操作，主要包括離散交叉和算術交叉，下面主要討論離散交叉（部分離散交叉和整體離散交叉）。部分離散交叉是先在兩個父代個體的編碼向量中隨機選擇一部分分量，然后對這部分分量進行交換，生成子代中的兩個新的個體。整體交叉則是對兩個父代個體的編碼向量中的所有分量，都以1/2的概率進行交換，從而生成子代中的兩個新的個體。以部分離散交叉為例，假設兩個父代個體的n維實向量分別是X=x1x2…xi…xk…xn和Y=y1y2…yi…yk…yn，若隨機選擇對第k個分量以后的所有分量進行交換，則生成的兩個新的個體向量是：X’=x1x2…xk

yk+1…ynY’=y1y2…yk

xk+1…xn例5.11

設有兩個父代個體向量A=201619321826和B=362538122130，若隨機選擇對第3個分量以后的所有分量進行交叉，則交叉后兩個新的個體向量是：A’=20161912

21

30B’=36253832

18

26

5.3.2遺傳算法5.基本遺傳操作(9/11)63實值交叉5.3.2遺傳算法63

(3)變異操作

變異（Mutation）是指對選中個體的染色體中的某些基因進行變動，以形成新的個體。變異也是生物遺傳和自然進化中的一種基本現(xiàn)象，它可增強種群的多樣性。遺傳算法中的變異操作增加了算法的局部隨機搜索能力，從而可以維持種群的多樣性。根據個體編碼方式的不同，變異操作可分為二進制變異和實值變異兩種類型。①二進制變異當個體的染色體采用二進制編碼表示時，其變異操作應采用二進制變異方法。該變異方法是先隨機地產生一個變異位，然后將該變異位置上的基因值由“0”變?yōu)椤?”，或由“1”變?yōu)椤?”，產生一個新的個體。例5.12設變異前的個體為A=001101，若隨機產生的變異位置是2，則該個體的第2位由“0”變?yōu)椤?”。變異后的新的個體是A’=011101。5.3.2遺傳算法5.基本遺傳操作(10/11)64(3)變異操作5.3.2遺傳算法64

②實值變異當個體的染色體采用實數(shù)編碼表示時，其變異操作應采用實值變異方法。該方法是用另外一個在規(guī)定范圍內的隨機實數(shù)去替換原變異位置上的基因值，產生一個新的個體。最常用的實值變異操作有:基于位置的變異方法該方法是先隨機地產生兩個變異位置，然后將第二個變異位置上的基因移動到第一個變異位置的前面。例5.13

設選中的個體向量C=201619122130，若隨機產生的兩個變異位置分別時2和4，則變異后的新的個體向量是：C’=201216192130基于次序的變異該方法是先隨機地產生兩個變異位置，然后交換這兩個變異位置上的基因。例5.14

設選中的個體向量D=201216192130，若隨機產生的兩個變異位置分別時2和4，則變異后的新的個體向量是：D’=2019161221305.3.2遺傳算法5.基本遺傳操作(11/11)65②實值變異5.3.2遺傳算法65例5.15

用遺傳算法求函數(shù)

f(x)=x2的最大值，其中x為[0，31]間的整數(shù)。解：這個問題本身比較簡單，其最大值很顯然是在x=31處。但作為一個例子，它有著較好的示范性和可理解性。按照遺傳算法，其求解過程如下：(1)編碼

由于x的定義域是區(qū)間[0，31]上的整數(shù)，由5位二進制數(shù)即可全部表示。因此，可采用二進制編碼方法，其編碼串的長度為5。例如，用二進制串00000來表示x=0,11111來表示x=31等。其中的0和1為基因值。

(2)生成初始種群

若假設給定的種群規(guī)模N=4，則可用4個隨機生成的長度為5的二進制串作為初始種群。再假設隨機生成的初始種群（即第0代種群）為：

s01=01101s02=11001s03=01000s04=100105.3.2遺傳算法6.遺傳算法應用簡例(1/10)66例5.15用遺傳算法求函數(shù)5.3.2遺傳算法66

(3)計算適應度

要計算個體的適應度，首先應該定義適應度函數(shù)。由于本例是求f(x)的最大值，因此可直接用f(x)來作為適應度函數(shù)。即：

f(s)=f(x)其中的二進制串s對應著變量x的值。根據此函數(shù)，初始種群中各個個體的適應值及其所占比例如表5-5所示。表5-5初始種群情況表可以看出，在4個個體中S03的適應值最大，是當前最佳個體。編號個體串（染色體）x適應值百分比%累計百分比%選中次數(shù)S01011011316914.4414.441S02110012562552.8867.182S03010008645.4172.590S04100101832427.4110015.3.2遺傳算法6.遺傳算法應用簡例(2/10)67(3)計算適應度編號個體串（染色體）x適應值百分(4)選擇操作

假設采用輪盤賭方式選擇個體，且依次生成的4個隨機數(shù)（相當于輪盤上指針所指的數(shù)）為0.85、0.32、0.12和0.46，經選擇后得到的新的種群為：

S01=10010S02=11001S03=01101S04=11001其中，染色體11001在種群中出現(xiàn)了2次，而原染色體01000則因適應值太小而被淘汰5.3.2遺傳算法6.遺傳算法應用簡例(3/10)68(4)選擇操作5.3.2遺傳算法68(5)交叉

假設交叉概率Pi為50%，則種群中只有1/2的染色體參與交叉。若規(guī)定種群中的染色體按順序兩兩配對交叉，且有S01與S02交叉，S03與S04不交叉，則交叉情況如表5-6所示。表5-6初始種群的交叉情況表可見，經交叉后得到的新的種群為：S01=10001S02=11010S03=01101S04=11001編號個體串（染色體）交叉對象交叉位子代適應值S0110010S02310001289S0211001S01311010676S0301101S04N01101169S0411001S03N110016255.3.2遺傳算法6.遺傳算法應用簡例(4/10)69(5)交叉編號個體串（染色體）交叉對象交叉位子(6)變異

變異概率Pm一般都很小，假設本次循環(huán)中沒有發(fā)生變異，則變異前的種群即為進化后所得到的第1代種群。即：

S11=10001S12=11010S13=01101S14=11001然后，對第1代種群重復上述(4)-(6)的操作

5.3.2遺傳算法6.遺傳算法應用簡例(5/10)70(6)變異5.3.2遺傳算法70對第1代種群，同樣重復上述(4)-(6)的操作。其選擇情況如表5-7所示。表5-7第1代種群的選擇情況表

其中若假設按輪盤賭選擇時依次生成的4個隨機數(shù)為0.14、0.51、0.24和0.82，經選擇后得到的新的種群為：S11=10001S12=11010S13=11010S14=11001可以看出，染色體11010被選擇了2次，而原染色體01101則因適應值太小而被淘汰。

編號個體串（染色體）x適應值百分比%累計百分比%選中次數(shù)S11100012728916.4316.4371S12110102667638.4354.862S1301101131699.6164.470S14110012562535.5310015.3.2遺傳算法6.遺傳算法應用簡例(6/10)71對第1代種群，同樣重復上述(4)-(6)的操作。其選擇情況如對第1代種群，其交叉情況如表5-8所示。表5-8第1代種群的交叉情況表可見，經雜交后得到的新的種群為：S11=10010S12=11001S13=11001S14=11010可以看出，第3位基因均為0，已經不可能通過交配達到最優(yōu)解。這種過早陷入局部最優(yōu)解的現(xiàn)象稱為早熟。為解決這一問題，需要采用變異操作。編號個體串（染色體）交叉對象交叉位子代適應值S1110001S12310010324S1211010S11311001625S13110101411001S132110106755.3.2遺傳算法6.遺傳算法應用簡例(7/10)72對第1代種群，其交叉情況如表5-8所示。編號個體串（對第1代種群，其變異情況如表5-9所示。表5-9第1代種群的變異情況表它是通過對S14的第3位的變異來實現(xiàn)的。變異后所得到的第2代種群為：S21=10010S22=11001S23=11001S24=11110接著，再對第2代種群同樣重復上述(4)-(6)的操作：

編號個體串（染色體）是否變異變異位子代適應值S1110010N10010324S1211001N11001625S1311001N11001625S1411010Y3111109005.3.2遺傳算法6.遺傳算法應用簡例(8/10)73對第1代種群，其變異情況如表5-9所示。編號個體串（對第2代種群，同樣重復上述(4)-(6)的操作。其選擇情況如表5-10所示。表5-10第2代種群的選擇情況表

其中若假設按輪盤賭選擇時依次生成的4個隨機數(shù)為0.42、0.15、0.59和0.91，經選擇后得到的新的種群為：S21=11001S22=10010S23=11001S24=11110編號個體串（染色體）x適應值百分比%累計百分比%選中次數(shù)S211001018324