人工智能章計算智能

1、人工智能章計算智能第1頁，共111頁，2022年，5月20日，10點59分，星期日4.1.1 什么是計算智能概念解釋 計算智能（Computational Intelligence，CI）目前還沒有一個統(tǒng)一的的定義，使用較多的是美國科學家貝慈德克（J.C.Bezdek）從計算智能系統(tǒng)角度所給出的定義。 從計算智能系統(tǒng)角度 如果一個系統(tǒng)僅處理低層的數(shù)值數(shù)據(jù)，含有模式識別部件，沒有使用人工智能意義上的知識，且具有計算適應性、計算容錯力、接近人的計算速度和近似于人的誤差率這4個特性，則它是計算智能的。 從學科范疇看 計算智能是在神經(jīng)網(wǎng)絡（Neural Networks,NN）、進化計算（Evolut

2、ionary Computation, EC）及模糊系統(tǒng)（Fuzzy System,FS）這3個領(lǐng)域發(fā)展相對成熟的基礎上形成的一個統(tǒng)一的學科概念。2第2頁，共111頁，2022年，5月20日，10點59分，星期日4.1.1 什么是計算智能 研究領(lǐng)域神經(jīng)網(wǎng)絡 是一種對人類智能的結(jié)構(gòu)模擬方法，它是通過對大量人工神經(jīng)元的廣泛并行互聯(lián)，構(gòu)造人工神經(jīng)網(wǎng)絡系統(tǒng)去模擬生物神經(jīng)系統(tǒng)的智能機理的。進化計算 是一種對人類智能的演化模擬方法，它是通過對生物遺傳和演化過程的認識，用進化算法去模擬人類智能的進化規(guī)律的。模糊計算 是一種對人類智能的邏輯模擬方法，它是通過對人類處理模糊現(xiàn)象的認知能力的認識，用模糊邏輯去模擬

3、人類的智能行為的。 綜合解釋 從貝慈德克的定義和上述學科范疇可以看出以下兩點： 第一，計算智能是借鑒仿生學的思想，基于生物神經(jīng)系統(tǒng)的結(jié)構(gòu)、進化和認知對自然智能進行模擬的。 第二，計算智能是一種以模型（計算模型、數(shù)學模型）為基礎，以分布、并行計算為特征的自然智能模擬方法。 3第3頁，共111頁，2022年，5月20日，10點59分，星期日4.1.2 計算智能的產(chǎn)生與發(fā)展 1992年，貝慈德克在Approximate Reasoning學報上首次 提出了“計算智能”的概念。 1994年6月底到7月初，IEEE在美國佛羅里達州的奧蘭多市召開了首屆國際計算智能大會(簡稱WCCI94)。會議第一次將神經(jīng)

4、網(wǎng)絡、進化計算和模糊系統(tǒng)這三個領(lǐng)域合并在一起，形成了“計算智能”這個統(tǒng)一的學科范疇。 在此之后，WCCI大會就成了IEEE的一個系列性學術(shù)會議，每4年舉辦一次。1998年5月，在美國阿拉斯加州的安克雷奇市又召開了第2屆計算智能國際會議WCCI98。2002年5月，在美國州夏威夷州首府火奴魯魯市又召開了第3屆計算智能國際會議WCCI02。此外，IEEE還出版了一些與計算智能有關(guān)的刊物。 目前，計算智能的發(fā)展得到了國內(nèi)外眾多的學術(shù)組織和研究機構(gòu)的高度重視，并已成為智能科學技術(shù)一個重要的研究領(lǐng)域。4第4頁，共111頁，2022年，5月20日，10點59分，星期日4.1.3 計算智能與人工智能的關(guān)系

5、目前，對計算智能與人工智能的關(guān)系有2種觀點，一種認為計算智能是人工智能的一個子集，另一種認為計算智能和人工智能是不同的范疇。 第一種觀點的代表人物是貝慈德克。他把智能（Intelligence，I）和神經(jīng)網(wǎng)絡（Neural Network，NN）都分為計算的（Computational，C）、人工的（Artificial，A）和生物的（Biological,B）3個層次，并以模式識別（PR）為例，給出了下圖所示的智能的層次結(jié)構(gòu)。 在該圖中，底層是計算智能（CI），它通過數(shù)值計算來實現(xiàn)，其基礎是CNN；中間層是人工智能（AI），它通過人造的符號系統(tǒng)實現(xiàn)，其基礎是ANN；頂層是生物智能（BI），它

6、通過生物神經(jīng)系統(tǒng)來實現(xiàn)，其基礎是BNN。 按照貝慈德克的觀點，CNN是指按生物激勵模型構(gòu)造的NN，ANN是指CNN+知識，BNN是指人腦，即ANN包含了CNN，BNN又包含了ANN。對智能也一樣，貝慈德克認為AI包含了CI，BI又包含了AI，即計算智能是人工智能的一個子集。5第5頁，共111頁，2022年，5月20日，10點59分，星期日CNNCPRCIANNAPRAIBNNBPRBI人類知識(+)傳感輸入知識(+)傳感數(shù)據(jù)計算(+)傳感器B生物的A符號的C數(shù)值的復雜性復雜性輸入層次 貝慈德克的智能的3個層次4.1.3 計算智能與人工智能的關(guān)系6第6頁，共111頁，2022年，5月20日，10

7、點59分，星期日 第二種觀點是大多數(shù)學者所持有的觀點，其代表人物是艾伯哈特（R.C.Eberhart）。他們認為：雖然人工智能與計算智能之間有重合，但計算智能是一個全新的學科領(lǐng)域，無論是生物智能還是機器智能，計算智能都是其最核心的部分，而人工智能則是外層。 事實上，CI和傳統(tǒng)的AI只是智能的兩個不同層次，各自都有自身的優(yōu)勢和局限性，相互之間只應該互補，而不能取代。 大量實踐證明，只有把AI和CI很好地結(jié)合起來，才能更好地模擬人類智能，才是智能科學技術(shù)發(fā)展的正確方向。4.1.3 計算智能與人工智能的關(guān)系7第7頁，共111頁，2022年，5月20日，10點59分，星期日 4.1 概述 4.2 神經(jīng)

8、計算 4.2.1 神經(jīng)計算基礎 4.2.2 人工神經(jīng)網(wǎng)絡的互連結(jié)構(gòu) 4.2.3 人工神經(jīng)網(wǎng)絡的典型模型 4.3 進化計算 4.4 模糊計算 4.5 粗糙集第4章 計算智能 神經(jīng)計算或叫神經(jīng)網(wǎng)絡，是計算智能的重要基礎和核心。 基于神經(jīng)網(wǎng)絡的連接學習機制放到機器學習部分討論。 8第8頁，共111頁，2022年，5月20日，10點59分，星期日4.2.1 神經(jīng)計算基礎 生物神經(jīng)系統(tǒng)是人工神經(jīng)網(wǎng)絡的基礎。人工神經(jīng)網(wǎng)絡是對人腦神經(jīng)系統(tǒng)的簡化、抽象和模擬，具有人腦功能的許多基本特征。 1. 生物神經(jīng)系統(tǒng)簡介 (1) 生物神經(jīng)元的結(jié)構(gòu) (2) 生物神經(jīng)細胞及工作方式 (3) 突觸聯(lián)結(jié) (4) 突觸傳遞方式2

9、. 人工神經(jīng)網(wǎng)絡簡介9第9頁，共111頁，2022年，5月20日，10點59分，星期日結(jié)構(gòu)： 胞體 軸突 樹突 突觸長度： 最長1米狀態(tài)： 抑制 興奮細胞體軸突樹突突觸1. 生物神經(jīng)系統(tǒng)簡介生物神經(jīng)元的結(jié)構(gòu)10第10頁，共111頁，2022年，5月20日，10點59分，星期日細胞結(jié)構(gòu) 細胞膜，細胞質(zhì)，細胞核神經(jīng)遞質(zhì)傳遞 乙酰膽堿、兒茶酚胺類、氨基酸等信號跨膜轉(zhuǎn)導 離子通道基本狀態(tài)： 抑制：-70毫伏 興奮：+40 毫伏靜息膜電位： -70毫伏動作電位： +40 毫伏工作方式： 刺激疊加 瞬間沖動細胞膜細胞質(zhì)細胞核1. 生物神經(jīng)系統(tǒng)簡介神經(jīng)細胞及工作方式11第11頁，共111頁，2022年，5月

10、20日，10點59分，星期日1. 生物神經(jīng)系統(tǒng)簡介突觸聯(lián)結(jié)方式12第12頁，共111頁，2022年，5月20日，10點59分，星期日1. 生物神經(jīng)系統(tǒng)簡介突觸傳導突觸后膜突觸間隙突觸前膜神經(jīng)微管線粒體突觸小泡存儲顆粒 突觸傳導由電變化和化學變化兩個過程完成。 當一個神經(jīng)沖動傳到神經(jīng)末梢時，促使小泡前移與突觸前膜融合，并在融合處出現(xiàn)裂口，使其所含神經(jīng)遞質(zhì)釋放，釋放出來的神經(jīng)遞質(zhì)通過突觸前膜的張口進入突出間隙。 進入突觸間隙的神經(jīng)遞質(zhì)又迅速作用于突觸后膜，改變突觸后膜的通透性，引起突觸后成分中的電位變化，實現(xiàn)神經(jīng)沖動的傳遞。 由于神經(jīng)末梢所釋放的遞質(zhì)不同（興奮作用和抑制作用），因此突觸可分為興奮性

11、突觸和抑制性突觸。13第13頁，共111頁，2022年，5月20日，10點59分，星期日4.2.1 神經(jīng)計算基礎 生物神經(jīng)系統(tǒng)是人工神經(jīng)網(wǎng)絡的基礎。人工神經(jīng)網(wǎng)絡是對人腦神經(jīng)系統(tǒng)的簡化、抽象和模擬，具有人腦功能的許多基本特征。 1. 生物神經(jīng)系統(tǒng)簡介2. 人工神經(jīng)網(wǎng)絡簡介 (1) 人工神經(jīng)元的結(jié)構(gòu) (2) 常用的人工神經(jīng)元模型 (3) 人工神經(jīng)網(wǎng)絡及其分類 14第14頁，共111頁，2022年，5月20日，10點59分，星期日x1x2xnw1w2wny MP模型是美國心理學家麥克洛奇(W.McM ulloch)和數(shù)理邏輯學家皮茨(W.Pitts) 根據(jù)生物神經(jīng)元的功能和結(jié)構(gòu)，于1943年提出的一

12、種將神經(jīng)元看作二進制閾值元件的簡單模型。 圖中的x1, x2, ,xn表示某一神經(jīng)元的n個輸入；wi表示第i個輸入的連接強度，稱為連接權(quán)值；為神經(jīng)元的閾值；y為神經(jīng)元的輸出。2. 人工神經(jīng)網(wǎng)絡簡介人工神經(jīng)元的結(jié)構(gòu)圖4.3 MP神經(jīng)元模型 人工神經(jīng)元是一個具有多輸入，單輸出的非線性器件。其輸入為： 其輸出為：15第15頁，共111頁，2022年，5月20日，10點59分，星期日 根據(jù)功能函數(shù)的不同，可得不同的神經(jīng)元模型。閾值型(Threshold) 這種模型的神經(jīng)元沒有內(nèi)部狀態(tài)，作用函數(shù)f是一個階躍函數(shù)，他表示激活值和輸出之間的關(guān)系。分段線性強飽和型(Linear Saturation) 這種模

13、型又稱為偽線性，其輸入/輸出之間在一定范圍內(nèi)滿足線性關(guān)系，一直延續(xù)到輸出為最大值1為止。但當達到最大值后，輸出就不再增。S型(Sibmoid) 這是一種連續(xù)的神經(jīng)元模型，其輸入輸出特性常用指數(shù)、對數(shù)或雙曲正切等S型函數(shù)表示。它反映的是神經(jīng)元的飽和特性.子閾累積型(Subthreshold Summation) 也是一個非線性函數(shù)，當產(chǎn)生的激活值超過T值時，該神經(jīng)元被激活產(chǎn)生個反響。在線性范圍內(nèi)，系統(tǒng)的反響是線性的。f()1T12. 人工神經(jīng)網(wǎng)絡簡介常用的人工神經(jīng)元模型f()100f()10f()016第16頁，共111頁，2022年，5月20日，10點59分，星期日 人工神經(jīng)網(wǎng)絡是一種對人工神

14、經(jīng)元進行互聯(lián)所形成的網(wǎng)絡，它是對生物神經(jīng)網(wǎng)絡的模擬。反映的是神經(jīng)元的飽和特性.2. 人工神經(jīng)網(wǎng)絡簡介人工神經(jīng)網(wǎng)絡及其分類人工神經(jīng)網(wǎng)絡的概念人工神經(jīng)網(wǎng)絡的分類按學習方法前饋網(wǎng)絡反饋網(wǎng)絡按拓撲結(jié)構(gòu)有導師指導無導師指導按網(wǎng)絡性能連續(xù)型網(wǎng)絡離散型網(wǎng)絡17第17頁，共111頁，2022年，5月20日，10點59分，星期日4.2.2 人工神經(jīng)網(wǎng)絡的互聯(lián)結(jié)構(gòu) 人工神經(jīng)網(wǎng)絡的互連結(jié)構(gòu)（或稱拓撲結(jié)構(gòu)）是指單個神經(jīng)元之間的連接模式，它是構(gòu)造神經(jīng)網(wǎng)絡的基礎，也是神經(jīng)網(wǎng)絡誘發(fā)偏差的主要來源。從互連結(jié)構(gòu)的角度：1. 前饋網(wǎng)絡2. 反饋網(wǎng)絡單層前饋網(wǎng)絡 多層前饋網(wǎng)絡 單層反饋網(wǎng)絡多層反饋網(wǎng)絡僅含輸入層和輸出層，且只有輸出

15、層的神經(jīng)元是可計算節(jié)點 除擁有輸入、輸出層外，還至少含有一個、或更多個隱含層的前向網(wǎng)絡 指不擁有隱含層的反饋網(wǎng)絡 指擁有隱含層的反饋網(wǎng)絡 （可含有反饋聯(lián)結(jié)）（只包含前向聯(lián)結(jié)） 18第18頁，共111頁，2022年，5月20日，10點59分，星期日 單層前饋網(wǎng)絡是指那種只擁有單層計算節(jié)點的前向網(wǎng)絡。它僅含有輸入層和輸出層，且只有輸出層的神經(jīng)元是可計算節(jié)點，如下圖所示x1X2X3xny1Y2ym權(quán)值wij輸出層輸入層圖4.8 單層前饋網(wǎng)絡結(jié)構(gòu)1. 前饋網(wǎng)絡單層前饋網(wǎng)絡(1/3) 其中，輸入向量為X=(x1,x2,xn)；輸出向量為Y=(y1,y2,ym)；輸入層各個輸入到相應神經(jīng)元的連接權(quán)值分別是

16、wij，i=1,2,.,n，j=1,2,., m。19第19頁，共111頁，2022年，5月20日，10點59分，星期日 若假設各神經(jīng)元的閾值分別是j，j=1,2,m，則各神經(jīng)元的輸出yj, j=1,2,.,m分別為：1. 前饋網(wǎng)絡單層前饋網(wǎng)絡(2/3)其中，由所有連接權(quán)值wij構(gòu)成的連接權(quán)值矩陣W為： 在實際應用中，該矩陣是通過大量的訓練示例學習而形成的。20第20頁，共111頁，2022年，5月20日，10點59分，星期日 多層前饋網(wǎng)絡是指那種除擁有輸入、輸出層外，還至少含有一個、或更多個隱含層的前饋網(wǎng)絡。 隱含層是指由那些既不屬于輸入層又不屬于輸出層的神經(jīng)元所構(gòu)成的處理層,也被稱為中間層

17、。隱含層的作用是通過對輸入層信號的加權(quán)處理，將其轉(zhuǎn)移成更能被輸出層接受的形式。 x1X2Xny1Ym隱含層輸出層輸入層圖4.9 多層前饋網(wǎng)絡結(jié)構(gòu)權(quán)值權(quán)值1. 前饋網(wǎng)絡多層前饋網(wǎng)絡(3/3) 多層前饋網(wǎng)絡的輸入層的輸出向量是第一隱含層的輸入信號，而第一隱含層的輸出則是第二隱含層的輸入信號，以此類推，直到輸出層。 多層前饋網(wǎng)絡的典型代表是BP網(wǎng)絡。21第21頁，共111頁，2022年，5月20日，10點59分，星期日2. 反饋經(jīng)網(wǎng)絡 反饋網(wǎng)絡是指允許采用反饋聯(lián)結(jié)方式所形成的神經(jīng)網(wǎng)絡。所謂反饋聯(lián)結(jié)方式是指一個神經(jīng)元的輸出可以被反饋至同層或前層的神經(jīng)元。 反饋網(wǎng)絡和前向網(wǎng)絡不同： 前向網(wǎng)絡屬于非循環(huán)連

18、接模式，它的每個神經(jīng)元的輸入都沒有包含該神經(jīng)元先前的輸出，因此不具有“短期記憶”的性質(zhì)。 反饋網(wǎng)絡則不同，它的每個神經(jīng)元的輸入都有可能包含有該神經(jīng)元先前輸出的反饋信息，即一個神經(jīng)元的輸出是由該神經(jīng)元當前的輸入和先前的輸出這兩者來決定的，這就有點類似于人類的短期記憶的性質(zhì)。 反饋網(wǎng)絡的典型例子是后面將要介紹的Hopfield網(wǎng)絡 22第22頁，共111頁，2022年，5月20日，10點59分，星期日人工神經(jīng)網(wǎng)絡模型 人工神經(jīng)網(wǎng)絡模型是指對網(wǎng)絡結(jié)構(gòu)、聯(lián)結(jié)權(quán)值和學習能力的總括。常用的網(wǎng)絡模型已有數(shù)十種。例如： 傳統(tǒng)的感知機模型；具有誤差反向傳播功能的反向傳播網(wǎng)絡模型；采用多變量插值的徑向基函數(shù)網(wǎng)絡模

19、型；建立在統(tǒng)計學習理論基礎上的支撐向量機網(wǎng)絡模型；采用反饋聯(lián)接方式的反饋網(wǎng)絡模型；基于模擬退火算法的隨機網(wǎng)絡模型。重點討論 1. 感知器（Perceptron）模型 2. 反向傳播（BP）模型 3. 反饋網(wǎng)絡（Hopfield）模型4.2.3 人工神經(jīng)網(wǎng)絡的典型模型23第23頁，共111頁，2022年，5月20日，10點59分，星期日 感知器是美國學者羅森勃拉特（Rosenblatt）于1957年為研究大腦的存儲、學習和認知過程而提出的一類具有自學習能力的神經(jīng)網(wǎng)絡模型，其拓撲結(jié)構(gòu)是一種分層前向網(wǎng)絡。它包括：單層感知器和多層感知器。 單層感知器是一種只具有單層可調(diào)節(jié)連接權(quán)值神經(jīng)元的前向網(wǎng)絡，這些

20、神經(jīng)元構(gòu)成了單層感知器的輸出層，是感知器的可計算節(jié)點。 在單層感知器中，每個可計算節(jié)點都是一個線性閾值神經(jīng)元。當輸入信息的加權(quán)和大于或等于閾值時，輸出為1，否則輸出為0或-1。 單層感知器的輸出層的每個神經(jīng)元都只有一個輸出，且該輸出僅與本神經(jīng)元的輸入及聯(lián)接權(quán)值有關(guān)，而與其他神經(jīng)元無關(guān)。1. 感知器模型單層 感知器(1/7)24第24頁，共111頁，2022年，5月20日，10點59分，星期日單層感知器的結(jié)構(gòu)如下圖x1x2xny1ym輸入層輸出層權(quán)值 wij輸入向量為X=(x1,x2,xn)；輸出向量為Y=(y1,y2,ym)；輸入層各個輸入到相應神經(jīng)元的連接權(quán)值分別是wij，i=1,2,.,n

21、，j=1,2,., m。 若假設各神經(jīng)元的閾值分別是j，j=1,2,m，則各神經(jīng)元的輸出yj, j=1,2,.,m分別為 其中，由所有連接權(quán)值wji構(gòu)成的連接權(quán)值矩陣W為： 在實際應用中，該矩陣是通過大量的訓練示例學習而形成的1. 感知器模型單層感知器(2/7)25第25頁，共111頁，2022年，5月20日，10點59分，星期日 使用感知器的主要目的是為了對外部輸入進行分類。 羅森勃拉特已經(jīng)證明，如果外部輸入是線性可分的（指存在一個超平面可以將它們分開），則單層感知器一定能夠把它劃分為兩類。其判別超平面由如下判別式確定：1.感知器模型單層感知器(3/7) 作為例子，下面討論用單個感知器實現(xiàn)邏

22、輯運算的問題。事實上，單層感知器可以很好地實現(xiàn)“與”、“或”、“非”運算，但卻不能解決“異或”問題。26第26頁，共111頁，2022年，5月20日，10點59分，星期日例4.1 “與”運算（x1x2）(0,0)(1,1)(0,1)(1,0)圖4.10 與運算問題圖示輸入輸出超平面閾值條件x1x2x1x2w1*x1+ w2* x2-=0 000w1*0+ w2*0 -0 0 010w1*0+ w2*1 -0 w2 100w1*1+ w2*0 -0 w1 111w1*1+ w2*1-0 w1+ w2 可以證明此表有解，例如取w1=1，w2=1，=1.5，其分類結(jié)果如右圖所示。 其中，輸出為1的用

23、實心圓，輸出為0的用空心圓。后面約定相同。1. 感知器模型單層感知器(4/7)27第27頁，共111頁，2022年，5月20日，10點59分，星期日例4.2 “或”運算（x1x2）輸入輸出超平面閾值條件x1x2x1x2w1*x1+ w2* x2-=0 000w1*0+ w2*0 -0 0 011w1*0+ w2*1 -0 w2 101w1*1+ w2*0 -0 w1 111w1*1+ w2*1-0 w1+ w2 此表也有解，例如取w1=1，w2=1，=0.5，其分類結(jié)果如右圖所示。(0,1)(0,0)(1,0)圖4.11 或運算問題圖示(1,1)1. 感知器模型單層感知器(5/7)28第28頁

24、，共111頁，2022年，5月20日，10點59分，星期日例4.3 “非”運算（x1）輸入輸出超平面閾值條件x1x1w1*x1-=0 01w1*0 - 0 0 10w1*1 w1 此表也有解，例如取w1=-1，=-0.5，其分類結(jié)果如右圖所示。 圖4.12 非運算問題圖示011. 感知器模型單層感知器(6/7)29第29頁，共111頁，2022年，5月20日，10點59分，星期日例4.4 “異或”運算（x1 XOR x2）輸入輸出超平面閾值條件x1x2x1 XOR x2w1*x1+ w2* x2-=0 000w1*0+ w2*0 -0 0 011w1*0+ w2*1 -0 w2 101w1*1

25、+ w2*0 -0 w1 110w1*1+ w2*1-w1+ w2 此表無解，即無法找到滿足條件的w1、w2和，如右圖所示。因為異或問題是一個非線性可分問題，需要用多層感知器來解決。(0,1)(0,0)(1,0)圖4.13 異或運算問題圖示(1,1)1. 感知器模型單層感知器(77)30第30頁，共111頁，2022年，5月20日，10點59分，星期日 (2) 多層感知器 多層感知器是通過在單層感知器的輸入、輸出層之間加入一層或多層處理單元所構(gòu)成的。其拓撲結(jié)構(gòu)與圖5.9所示的多層前向網(wǎng)絡相似，差別也在于其計算節(jié)點的連接權(quán)值是可變的。 多層感知器的輸入與輸出之間是一種高度非線性的映射關(guān)系，如圖4

26、.9所示的多層前向網(wǎng)絡，若采用多層感知器模型，則該網(wǎng)絡就是一個從n維歐氏空間到m維歐氏空間的非線性映射。因此，多層感知器可以實現(xiàn)非線性可分問題的分類。例如，對“異或”運算，用圖4.14所示的多層感知器即可解決。 1. 感知器模型多層 感知器(1/2)31第31頁，共111頁，2022年，5月20日，10點59分，星期日x11y=x1 XOR x2x1X2x121-1111-1輸入層隱層輸出層權(quán)值權(quán)值圖4.14 “異或”問題的多層感知器閾值0.5閾值-1.5閾值1.5(0,1)(0,0)(1,0)圖4.15異或問題的解決(1,1) 在圖4.14中，隱層神經(jīng)元x11所確定的直線方程為 它可以識別一

27、個半平面。隱層神經(jīng)元x12所確定的直線方程為它也可以識別一個半平面。輸出層神經(jīng)元所確定的直線方程為 它相當于對隱層神經(jīng)元x11和x12的輸出作“邏輯與”運算，因此可識別由隱層已識別的兩個半平面的交集所構(gòu)成的一個凸多邊形，如圖4.15所示。1. 感知器模型多層 感知器(2/2)32第32頁，共111頁，2022年，5月20日，10點59分，星期日 誤差反向傳播(Error Back Propagation)網(wǎng)絡通常簡稱為BP(Back Propagation)網(wǎng)絡，是由美國加州大學的魯梅爾哈特和麥克萊蘭在研究并行分布式信息處理方法，探索人類認知微結(jié)構(gòu)的過程中，于1985年提出的一種網(wǎng)絡模型。 B

28、P網(wǎng)絡的網(wǎng)絡拓撲結(jié)構(gòu)是多層前向網(wǎng)絡，如圖4.16所示。在BP網(wǎng)絡中，同層節(jié)點之間不存在相互連接，層與層之間多采用全互連方式，且各層的連接權(quán)值可調(diào)。BP網(wǎng)絡實現(xiàn)了明斯基的多層網(wǎng)絡的設想，是當今神經(jīng)網(wǎng)絡模型中使用最廣泛的一種。 y1y2ymx1x2xn輸出層隱含層輸入層權(quán)可調(diào)權(quán)可調(diào)圖4.16 一個多層BP網(wǎng)絡的結(jié)構(gòu)2. BP網(wǎng)絡模型模型結(jié)構(gòu)33第33頁，共111頁，2022年，5月20日，10點59分，星期日對BP網(wǎng)絡需說明以下兩點： 第一，BP網(wǎng)絡的每個處理單元均為非線性輸入/輸出關(guān)系，其作用函數(shù)通常采用的是可微的Sigmoid函數(shù)，如：2. BP網(wǎng)絡模型模型說明 第二，BP網(wǎng)絡的學習過程是由工

29、作信號的正向傳播和誤差信號的反向傳播組成的。所謂正向傳播，是指輸入模式經(jīng)隱層到輸出層，最后形成輸出模式；所謂誤差反向傳播，是指從輸出層開始逐層將誤差傳到輸入層，并修改各層聯(lián)接權(quán)值，使誤差信號為最小的過程。34第34頁，共111頁，2022年，5月20日，10點59分，星期日 Hopfield網(wǎng)絡是由美國加州工學院物理學家霍普菲爾特1982年提出來的一種單層全互連的對稱反饋網(wǎng)絡模型。它可分為離散Hopfield網(wǎng)絡和連續(xù)Hopfield網(wǎng)絡，限于篇幅，本書重點討論離散Hopfield網(wǎng)絡。 離散Hopfield網(wǎng)絡的結(jié)構(gòu) 離散Hopfield網(wǎng)絡是在非線性動力學的基礎上由若干基本神經(jīng)元構(gòu)成的一種

30、單層全互連網(wǎng)絡，其任意神經(jīng)元之間均有連接，并且是一種對稱連接結(jié)構(gòu)。一個典型的離散 Hopfidld網(wǎng)絡結(jié)構(gòu)如圖4-17所示。離散Hopfield網(wǎng)絡模型是一個離散時間系統(tǒng)，每個神經(jīng)元只有0和1（或-1和1）兩種狀態(tài)，任意神經(jīng)元i和j之間的連接權(quán)值為wij。由于神經(jīng)元之間為對稱連接，且神經(jīng)元自身無連接，因此有3. Hopfield網(wǎng)絡模型離散Hopfield網(wǎng)絡模型(1/2)由該連接權(quán)值所構(gòu)成的連接矩陣是一個零對角的對稱矩陣。35第35頁，共111頁，2022年，5月20日，10點59分，星期日圖 417 離散Hopfield網(wǎng)絡的結(jié)構(gòu)ymY2Y1x1x2xn輸入層輸出層 在 Hopfidld網(wǎng)

31、絡中，雖然神經(jīng)元自身無連接，但由于每個神經(jīng)元都與其他神經(jīng)元相連，即每個神經(jīng)元的輸出都將通過突觸連接權(quán)值傳遞給別的神經(jīng)元，同時每個神經(jīng)元又都接受其他神經(jīng)元傳來的信息，這樣對每個神經(jīng)元來說，其輸出經(jīng)過其他神經(jīng)元后又有可能反饋給自己，因此Hopfidld網(wǎng)絡是一種反饋神經(jīng)網(wǎng)絡 3. Hopfield網(wǎng)絡模型離散Hopfield網(wǎng)絡模型(2/2)36第36頁，共111頁，2022年，5月20日，10點59分，星期日 4.1 概述 4.2 神經(jīng)計算 4.3 進化計算 4.3.1 進化計算概述 4.3.2 遺傳算法 4.4 模糊計算 4.5 粗糙集第4章 計算智能37第37頁，共111頁，2022年，5月

32、20日，10點59分，星期日 進化計算（Evolutionary Computation,EC）是在達爾文（Darwin）的進化論和孟德爾（Mendel）的遺傳變異理論的基礎上產(chǎn)生的一種在基因和種群層次上模擬自然界生物進化過程與機制的問題求解技術(shù)。它主要包括 遺傳算法（Genetic Algorithm，GA） 進化策略（Evolutionary Strategy,ES） 進化規(guī)劃（Evolutionary Programming,EP） 遺傳規(guī)劃（Genetic Programming,GP）四大分支。其中，第一個分支是進化計算中最初形成的一種具有普遍影響的模擬進化優(yōu)化算法。因此我們主要討論

33、遺傳算法。4.3 進化計算38第38頁，共111頁，2022年，5月20日，10點59分，星期日 進化計算是一種模擬自然界生物進化過程與機制進行問題求解的自組織、自適應的隨機搜索技術(shù)。它以達爾文進化論的“物竟天擇、適者生存”作為算法的進化規(guī)則，并結(jié)合孟德爾的遺傳變異理論，將生物進化過程中的 繁殖（Reproduction） 變異（Mutation） 競爭（Competition） 選擇（Selection）引入到了算法中。4.3.1 進化計算概述1. 進化計算及其生物學基礎(1/3) (1) 什么是進化計算39第39頁，共111頁，2022年，5月20日，10點59分，星期日(2) 進化計算的

34、生物學基礎 自然界生物進化過程是進化計算的生物學基礎，它主要包括遺傳(Heredity)、變異(Mutation)和進化(Evolution)理論。 遺傳理論 遺傳是指父代（或親代）利用遺傳基因?qū)⒆陨淼幕蛐畔鬟f給下一代（或子代），使子代能夠繼承其父代的特征或性狀的這種生命現(xiàn)象。正是由于遺傳的作用，自然界才能有穩(wěn)定的物種。 在自然界，構(gòu)成生物基本結(jié)構(gòu)與功能的單位是細胞（Cell）。 細胞中含有一種包含著所有遺傳信息的復雜而又微小的絲狀化合物，人們稱其為染色體（Chromosome）。 在染色體中，遺傳信息由基因（Gene）所組成，基因決定著生物的性狀，是遺傳的基本單位。 染色體的形狀是一種雙

35、螺旋結(jié)構(gòu)，構(gòu)成染色體的主要物質(zhì)叫做脫氧核糖核酸(DNA)，每個基因都在DNA長鏈中占有一定的位置。 一個細胞中的所有染色體所攜帶的遺傳信息的全體稱為一個基因組(Genome)。 細胞在分裂過程中，其遺傳物質(zhì)DNA通過復制轉(zhuǎn)移到新生細胞中，從而實現(xiàn)了生物的遺傳功能。4.3.1 進化計算概述1. 進化計算及其生物學基礎(2/3)40第40頁，共111頁，2022年，5月20日，10點59分，星期日 變異理論 變異是指子代和父代之間，以及子代的各個不同個體之間產(chǎn)生差異的現(xiàn)象。變異是一種隨機、不可逆現(xiàn)象，是生物多樣性的基礎。引起變異的主要原因： 雜交，是指有性生殖生物在繁殖下一代時兩個同源染色體之間的

36、交配重組，即兩個染色體在某一相同處的DNA被切斷后再進行交配重組，形成兩個新的染色體。 復制差錯，是指在細胞復制過程中因DNA上某些基因結(jié)構(gòu)的隨機改變而產(chǎn)生出新的染色體。 進化論 進化是指在生物延續(xù)生存過程中，逐漸適應其生存環(huán)境，使得其品質(zhì)不斷得到改良的這種生命現(xiàn)象。遺傳和變異是生物進化的兩種基本現(xiàn)象，優(yōu)勝劣汰、適者生存是生物進化的基本規(guī)律。 達爾文的自然選擇學說：在生物進化中，一種基因有可能發(fā)生變異而產(chǎn)生出另一種新的基因。這種新基因?qū)⒁罁?jù)其與生存環(huán)境的適應性而決定其增殖能力。通常，適應性強的基因會不斷增多，而適應性差的基因則會逐漸減少。通過這種自然選擇，物種將逐漸向適應于生存環(huán)境的方向進化，

37、甚至會演變成為另一個新的物種，而那些不適應于環(huán)境的物種將會逐漸被淘汰。4.3.1 進化計算概述1. 進化計算及其生物學基礎(3/3)41第41頁，共111頁，2022年，5月20日，10點59分，星期日 進化計算自20世紀50年代以來，其發(fā)展過程大致可分為三個階段。 (1) 萌芽階段 這一階段是從20世紀50年代后期到70年代中期。20世紀50年代后期，一些生物學家在研究如何用計算機模擬生物遺傳系統(tǒng)中，產(chǎn)生了遺傳算法的基本思想，并于1962年由美國密執(zhí)安（Michigan）大學霍蘭德（Holland）提出。1965年德國數(shù)學家雷切伯格（Rechenberg）等人提出了一種只有單個個體參與進化，

38、并且僅有變異這一種進化操作的進化策略。同年，美國學者弗格爾（Fogel）提出了一種具有多個個體和僅有變異一種進化操作的進化規(guī)劃。1969年美國密執(zhí)安（Michigan）大學的霍蘭德（Holland）提出了系統(tǒng)本身和外部環(huán)境相互協(xié)調(diào)的遺傳算法。至此，進化計算的三大分支基本形成。 (2) 成長階段 這一階段是從20世紀70年代中期到80年代后期。1975年，霍蘭德出版專著自然和人工系統(tǒng)的適應性（Adaptation in Natural and Artificial System），全面介紹了遺傳算法。同年，德國學者施韋費爾（Schwefel）在其博士論文中提出了一種由多個個體組成的群體參與進化的

39、，并且包括了變異和重組這兩種進化操作的進化策略。1989年，霍蘭德的學生戈爾德伯格（Goldberg）博士出版專著遺傳算法-搜索、優(yōu)化及機器學習（Genetic Algorithm-in Search Optimization and Machine Learning），使遺傳算法得到了普及與推廣。4.3.1 進化計算概述2. 進化計算的產(chǎn)生與發(fā)展(1/2)42第42頁，共111頁，2022年，5月20日，10點59分，星期日 (3) 發(fā)展階段 這一階段是從20世紀90年代至今。1989年，美國斯坦福（Stanford）大學的科扎（Koza）提出了遺傳規(guī)劃的新概念，并于1992年出版了專著遺傳

40、規(guī)劃-應用自然選擇法則的計算機程序設計（Genetic Programming :on the Programming of Computer by Means of Natural Selection）該書全面介紹了遺傳規(guī)劃的基本原理及應用實例，標志著遺傳規(guī)劃作為計算智能的一個分支已基本形成。 進入20世紀90年代以來，進化計算得到了眾多研究機構(gòu)和學者的高度重視，新的研究成果不斷出現(xiàn)、應用領(lǐng)域不斷擴大。目前，進化計算已成為人工智能領(lǐng)域的又一個新的研究熱點。 4.3.1 進化計算概述2. 進化計算的產(chǎn)生與發(fā)展(2/2)43第43頁，共111頁，2022年，5月20日，10點59分，星期日 進化

41、計算盡管有多個重要分支，并且不同分支的編碼方案、選擇策略和進化操作也有可能不同，但它們卻有著共同的進化框架。若假設P為種群(Population，或稱為群體)，t為進化代數(shù)， P(t)為第t代種群 , 則進化計算的基本結(jié)構(gòu)可粗略描述如下： 確定編碼形式并生成搜索空間； 初始化各個進化參數(shù)，并設置進化代數(shù)t=0； 初始化種群P(0); 對初始種群進行評價（即適應度計算）； while（不滿足終止條件）do t=t+1; 利用選擇操作從P(t-1)代中選出P(t)代群體； 對P(t)代種群執(zhí)行進化操作； 對執(zhí)行完進化操作后的種群進行評價（即適應度計算）； 可以看出，上述基本結(jié)構(gòu)包含了生物進化中所必

42、需的選擇操作、進化操作和適應度評價等過程。4.3.1 進化計算概述3. 進化計算的基本結(jié)構(gòu)44第44頁，共111頁，2022年，5月20日，10點59分，星期日 遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個體，并通過雜交、變異來產(chǎn)生新一代種群，如此逐代進化，直到滿足目標為止。遺傳算法所涉及到的基本概念主要有以下幾個： 種群（Population）：種群是指用遺傳算法求解問題時，初始給定的多個解的集合。遺傳算法的求解過程是從這個子集開始的。 個體（Individual）：個體是指種群中的單個元素，它通常由一個用于描述其基本遺傳結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)來表示。例如，可以用0、1

43、組成的長度為l的串來表示個體。 染色體（Chromos）：染色體是指對個體進行編碼后所得到的編碼串。染色體中的每1位稱為基因，染色體上由若干個基因構(gòu)成的一個有效信息段稱為基因組。 適應度（Fitness）函數(shù)：適應度函數(shù)是一種用來對種群中各個個體的環(huán)境適應性進行度量的函數(shù)。其函數(shù)值是遺傳算法實現(xiàn)優(yōu)勝劣汰的主要依據(jù) 遺傳操作（Genetic Operator）：遺傳操作是指作用于種群而產(chǎn)生新的種群的操作。標準的遺傳操作包括以下3種基本形式： 選擇（Selection） 交叉（Crosssover） 變異（Mutation） 4.3.2 遺傳算法1. 遺傳算法的基本概念45第45頁，共111頁，2

44、022年，5月20日，10點59分，星期日 遺傳算法主要由染色體編碼、初始種群設定、適應度函數(shù)設定、遺傳操作設計等幾大部分所組成，其算法主要內(nèi)容和基本步驟可描述如下： (1) 選擇編碼策略，將問題搜索空間中每個可能的點用相應的編碼策略表示出來，即形成染色體； (2) 定義遺傳策略，包括種群規(guī)模N，交叉、變異方法，以及選擇概率Pr、交叉概率Pc、變異概率Pm等遺傳參數(shù)； (3) 令t=0，隨機選擇N個染色體初始化種群P(0)； (4) 定義適應度函數(shù)f（f0）； (5) 計算P(t)中每個染色體的適應值； (6) t=t+1； (7) 運用選擇算子，從P(t-1)中得到P(t)； (8) 對P(

45、t)中的每個染色體，按概率Pc參與交叉； (9) 對染色體中的基因，以概率Pm參與變異運算； (10) 判斷群體性能是否滿足預先設定的終止標準，若不滿足則返回(5)。4.3.2 遺傳算法2. 遺傳算法的基本過程(1/2)46第46頁，共111頁，2022年，5月20日，10點59分，星期日計算種群中各個個體的適應度，并進行評價滿足終止條件嗎？終止選擇交叉變異Y圖4-18 基本遺傳算法的算法流程圖編碼和生成初始種群N選擇 其算法流程如圖4-18所示。45.3.2 遺傳算法2. 遺傳算法的基本結(jié)構(gòu)(2/2)47第47頁，共111頁，2022年，5月20日，10點59分，星期日 常用的遺傳編碼算法有

46、霍蘭德二進制碼、格雷碼（Gray Code）、實數(shù)編碼和字符編碼等。(1)二進制編碼（Binary encoding） 二進制編碼是將原問題的結(jié)構(gòu)變換為染色體的位串結(jié)構(gòu)。在二進制編碼中，首先要確定二進制字符串的長度l，該長度與變量的定義域和所求問題的計算精度有關(guān)。 例5.5 假設變量x的定義域為5，10，要求的計算精度為10-5，則需要將5，10至少分為600000個等長小區(qū)間，每個小區(qū)間用一個二進制串表示。于是，串長至少等于20，原因是： 524288=219600000220=1048576這樣，對應于區(qū)間5，10內(nèi)滿足精度要求的每個值x，都可用一個20位編碼的二進制串來表示。 二進制編碼

47、存在的主要缺點是漢明（Hamming）懸崖。 例如，7和8的二進制數(shù)分別為0111和1000，當算法從7改進到8時，就必須改變所有的位。 4.3.2 遺傳算法3. 遺傳編碼(1/3)48第48頁，共111頁，2022年，5月20日，10點59分，星期日4.3.2 遺傳算法3. 遺傳編碼(2/3)(2) 格雷編碼（Gray encoding） 格雷編碼是對二進制編碼進行變換后所得到的一種編碼方法。這種編碼方法要求兩個連續(xù)整數(shù)的編碼之間只能有一個碼位不同，其余碼位都是完全相同的。它有效地解決了漢明懸崖問題，其基本原理如下： 設有二進制串b1,b2,bn，對應的格雷串為a1,a2,an，則從二進制編

48、碼到格雷編碼的變換為： (4.9)其中，表示模2加法。而從一個格雷串到二進制串的變換為： (4.10) 例4.6 十進制數(shù)7和8的二進制編碼分別為0111和1000，而其格雷編碼分別為0100和1100。49第49頁，共111頁，2022年，5月20日，10點59分，星期日(3) 實數(shù)編碼（Real encoding） 實數(shù)編碼是將每個個體的染色體都用某一范圍的一個實數(shù)（浮點數(shù)）來表示，其編碼長度等于該問題變量的個數(shù)。 這種編碼方法是將問題的解空間映射到實數(shù)空間上，然后在實數(shù)空間上進行遺傳操作。由于實數(shù)編碼使用的是變量的真實值，因此這種編碼方法也叫做真值編碼方法。 實數(shù)編碼適應于那種多維、高精

49、度要求的連續(xù)函數(shù)優(yōu)化問題。 4.3.2 遺傳算法3. 遺傳編碼(3/3)50第50頁，共111頁，2022年，5月20日，10點59分，星期日 適應度函數(shù)是一個用于對個體的適應性進行度量的函數(shù)。通常，一個個體的適應度值越大，它被遺傳到下一代種群中的概率也就越大。(1) 常用的適應度函數(shù) 在遺傳算法中，有許多計算適應度的方法，其中最常用的適應度函數(shù)有以下兩種： 原始適應度函數(shù) 它是直接將待求解問題的目標函數(shù)f(x)定義為遺傳算法的適應度函數(shù)。例如，在求解極值問題時，f(x)即為x的原始適應度函數(shù)。 采用原始適應度函數(shù)的優(yōu)點是能夠直接反映出待求解問題的最初求解目標，其缺點是有可能出現(xiàn)適應度值為負的

50、情況。 4.3.2 遺傳算法4. 適應度函數(shù)(1/5)51第51頁，共111頁，2022年，5月20日，10點59分，星期日 標準適應度函數(shù) 在遺傳算法中，一般要求適應度函數(shù)非負，并其適應度值越大越好。這就往往需要對原始適應函數(shù)進行某種變換，將其轉(zhuǎn)換為標準的度量方式，以滿足進化操作的要求，這樣所得到的適應度函數(shù)被稱為標準適應度函數(shù)fNormal(x)。例如下面的極小化和極大化問題： 極小化問題 對極小化問題，其標準適應度函數(shù)可定義為 (4.11)其中，fmax (x)是原始適應函數(shù)f(x)的一個上界。如果fmax (x) 未知，則可用當前代或到目前為止各演化代中的f(x)的最大值來代替?？梢?，

51、 fmax (x) 是會隨著進化代數(shù)的增加而不斷變化的。 4.3.2 遺傳算法4. 適應度函數(shù)(2/5)52第52頁，共111頁，2022年，5月20日，10點59分，星期日 極大化問題 對極大化問題，其標準適應度函數(shù)可定義為 (4.12)其中，fmin(x)是原始適應函數(shù)f(x)的一個下界。如果fmin(x) 未知，則可用當前代或到目前為止各演化代中的f(x)的最小值來代替。 4.3.2 遺傳算法4. 適應度函數(shù)(3/5)53第53頁，共111頁，2022年，5月20日，10點59分，星期日(2) 適應度函數(shù)的加速變換 在某些情況下，適應度函數(shù)在極值附近的變化可能會非常小，以至于不同個體的適

52、應值非常接近，使得難以區(qū)分出哪個染色體更占優(yōu)勢。對此，最好能定義新的適應度函數(shù)，使該適應度函數(shù)既與問題的目標函數(shù)具有相同的變化趨勢，又有更快的變化速度。 適應度函數(shù)的加速變換有兩種基本方法 線性加速的適應度函數(shù)的定義如下： f(x)=f(x)+其中，f(x)是加速轉(zhuǎn)換前的適應度函數(shù)； f(x)是加速轉(zhuǎn)換后的適應度函數(shù)；和是轉(zhuǎn)換系數(shù),它們應滿足如下條件： 變化后得到的新的適應度函數(shù)平均值要等于原適應度函數(shù)的平均值。即 （4.13）其中，xi(i=1,n)為當前代中的染色體。4.3.2 遺傳算法4. 適應度函數(shù)(4/5)54第54頁，共111頁，2022年，5月20日，10點59分，星期日 變換后

53、所得到的新的種群個體所具有的最大適應度要等于其平均適應度的指數(shù)倍數(shù)。即有關(guān)系： （4.14） 式中，xi(i=1,n) 為當前代中的染色體，M是指將當前的最大適應度放大為平均值的M倍。目的是通過M拉開不同染色體適應度值的差距。 非線性加速 冪函數(shù)變換方法 f(x)=f(x)k (4.15) 指數(shù)變換方法 f(x)=exp(-f(x) (4.16) 4.3.2 遺傳算法4. 適應度函數(shù)(5/5)55第55頁，共111頁，2022年，5月20日，10點59分，星期日 遺傳算法中的基本遺傳操作包括選擇、交叉和變異3種，而每種操作又包括多種不同的方法，下面分別對它們進行介紹。(1). 選擇操作 選擇（

54、Selection）操作是指根據(jù)選擇概率按某種策略從當前種群中挑選出一定數(shù)目的個體，使它們能夠有更多的機會被遺傳到下一代中。 常用的選擇策略可分為比例選擇、排序選擇和競技選擇三種類型。 比例選擇 比例選擇方法（Proportional Model）的基本思想是：各個個體被選中的概率與其適應度大小成正比。 常用的比例選擇策略包括 輪盤賭選擇 繁殖池選擇4.3.2 遺傳算法5. 基本遺傳操作(1/11)56第56頁，共111頁，2022年，5月20日，10點59分，星期日 輪盤賭選擇 輪盤賭選擇法又被稱為轉(zhuǎn)盤賭選擇法或輪盤選擇法。在這種方法中，個體被選中的概率取決于該個體的相對適應度。而相對適應度

55、的定義為：其中，P(xi)是個體xi的相對適應度，即個體xi被選中的概率；f(xi)是個體xi的原始適應度；是種群的累加適應度。 輪盤賭選擇算法的基本思想是：根據(jù)每個個體的選擇概率P(xi)將一個圓盤分成N個扇區(qū)，其中第i個扇區(qū)的中心角為：再設立一個移動指針，將圓盤的轉(zhuǎn)動等價為指針的移動。選擇時，假想轉(zhuǎn)動圓盤，若靜止時指針指向第i個扇區(qū)，則選擇個體i。其物理意義如圖5-19所示。4.3.2 遺傳算法5. 基本遺傳操作(2/11)57第57頁，共111頁，2022年，5月20日，10點59分，星期日P(x1)P(x2)P(xN)P(xi)2p(xi)圖4-19 輪盤賭選擇 從統(tǒng)計角度看，個體的適

56、應度值越大，其對應的扇區(qū)的面積越大，被選中的可能性也越大。這種方法有點類似于發(fā)放獎品使用的輪盤，并帶有某種賭博的意思，因此亦被稱為輪盤賭選擇。4.3.2 遺傳算法5. 基本遺傳操作(3/11)58第58頁，共111頁，2022年，5月20日，10點59分，星期日(2)交叉操作 交叉（Crossover）操作是指按照某種方式對選擇的父代個體的染色體的部分基因進行交配重組，從而形成新的個體。交配重組是自然界中生物遺傳進化的一個主要環(huán)節(jié)，也是遺傳算法中產(chǎn)生新的個體的最主要方法。根據(jù)個體編碼方法的不同，遺傳算法中的交叉操作可分為二進制交叉和實值交叉兩種類型。 二進制交叉 二進制交叉（Binary Va

57、lued Crossover）是指二進制編碼情況下所采用的交叉操作，它主要包括單點交叉、兩點交叉、多點交叉和均勻交叉等方法。4.3.2 遺傳算法5. 基本遺傳操作(4/11)59第59頁，共111頁，2022年，5月20日，10點59分，星期日 單點交叉 單點交叉也稱簡單交叉，它是先在兩個父代個體的編碼串中隨機設定一個交叉點，然后對這兩個父代個體交叉點前面或后面部分的基因進行交換，并生成子代中的兩個新的個體。假設兩個父代的個體串分別是： X=x1 x2 xk xk+1 xn Y=y1 y2 yk yk+1 yn 隨機選擇第k位為交叉點，若采用對交叉點后面的基因進行交換的方法，但點交叉是將X中的

58、xk+1到xn部分與Y中的yk+1到y(tǒng)n部分進行交叉，交叉后生成的兩個新的個體是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk xk+1 xn 例4.7 設有兩個父代的個體串A=0 0 1 1 0 1 和B=1 1 0 0 1 0 ，若隨機交叉點為4，則交叉后生成的兩個新的個體是： A= 0 0 1 1 1 0 B= 1 1 0 0 0 1 4.3.2 遺傳算法5. 基本遺傳操作(5/11)60第60頁，共111頁，2022年，5月20日，10點59分，星期日 兩點交叉 兩點交叉是指先在兩個父代個體的編碼串中隨機設定兩個交叉點，然后再按這兩個交叉點進行部分基因交換，生成子代

59、中的兩個新的個體。 假設兩個父代的個體串分別是： X=x1 x2 xi xj xn Y=y1 y2 yi yj ,yn 隨機設定第i、j位為兩個交叉點（其中ijn），兩點交叉是將X中的xi+1到xj部分與Y中的yi+1到y(tǒng)j部分進行交換，交叉后生成的兩個新的個體是： X= x1 x2 xi yi+1 yj xj+1 xn Y= y1 y2 yi xi+1 xj yj+1 yn 例4.8 設有兩個父代的個體串A= 0 0 1 1 0 1 和B= 1 1 0 0 1 0 ，若隨機交叉點為3和5，則交叉后的兩個新的個體是： A= 0 0 1 0 1 1 B= 1 1 0 1 0 0 4.3.2 遺傳

60、算法5. 基本遺傳操作(6/11)61第61頁，共111頁，2022年，5月20日，10點59分，星期日 多點交叉 多點交是指先隨機生成多個交叉點，然后再按這些交叉點分段地進行部分基因交換，生成子代中的兩個新的個體。 假設交叉點個數(shù)為m，則可將個體串劃分為m+1個分段，其劃分方法是： 當m為偶數(shù)時，對全部交叉點依次進行兩兩配對，構(gòu)成m/2個交叉段。 當m為奇數(shù)時，對前(m-1)個交叉點依次進行兩兩配對，構(gòu)成(m-1)/2個交叉段，而第m個交叉點則按單點交叉方法構(gòu)成一個交叉段。 下面以m=3為例進行討論。假設兩個父代的個體串分別是X=x1 x2 xi xj xk xn和Y=y1 y2 yi yj