計(jì)算智能概述

第5章計(jì)算智能計(jì)算智能是信息科學(xué)、生命科學(xué)、認(rèn)知科學(xué)等不一樣學(xué)科相互交叉產(chǎn)物。它主要借鑒仿生學(xué)思想，基于人們對(duì)生物體智能機(jī)理認(rèn)識(shí)，采取數(shù)值計(jì)算方法去模擬和實(shí)現(xiàn)人類智能。計(jì)算智能主要研究領(lǐng)域包含：神經(jīng)計(jì)算、進(jìn)化計(jì)算、含糊計(jì)算、免疫計(jì)算、DNA計(jì)算和人工生命等。本章主要討論神經(jīng)計(jì)算、進(jìn)化計(jì)算和含糊計(jì)算問(wèn)題。

5.1概述5.2神經(jīng)計(jì)算5.3進(jìn)化計(jì)算5.4含糊計(jì)算1計(jì)算智能概述第1頁(yè)5.1概述

5.1.1什么是計(jì)算智能5.1.2計(jì)算智能產(chǎn)生與發(fā)展5.1.3計(jì)算智能與人工智能關(guān)系2計(jì)算智能概述第2頁(yè)5.1.1什么是計(jì)算智能計(jì)算智能（ComputationalIntelligence，CI）當(dāng)前還沒(méi)有一個(gè)統(tǒng)一定義，使用較多是美國(guó)科學(xué)家貝慈德克（J.C.Bezdek）從計(jì)算智能系統(tǒng)角度所給出定義:假如一個(gè)系統(tǒng)僅處理低層數(shù)值數(shù)據(jù)，含有模式識(shí)別部件，沒(méi)有使用人工智能意義上知識(shí)，且含有計(jì)算適應(yīng)性、計(jì)算容錯(cuò)力、靠近人計(jì)算速度和近似于人誤差率這4個(gè)特征，則它是計(jì)算智能。從學(xué)科范圍看，計(jì)算智能是在神經(jīng)網(wǎng)絡(luò)（NeuralNetworks,NN）、進(jìn)化計(jì)算（EvolutionaryComputation,EC）及含糊系統(tǒng)（FuzzySystem,FS）這3個(gè)領(lǐng)域發(fā)展相對(duì)成熟基礎(chǔ)上形成一個(gè)統(tǒng)一學(xué)科概念。

3計(jì)算智能概述第3頁(yè)

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

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

細(xì)胞體由細(xì)胞核、細(xì)胞質(zhì)和細(xì)胞膜等組成，其直徑大約為0.5-100μm大小不等。細(xì)胞體是神經(jīng)元主體，用于處理由樹(shù)突接收其它神經(jīng)元傳來(lái)信號(hào),其內(nèi)部是細(xì)胞核，外部是細(xì)胞膜，細(xì)胞膜外面是許多向外延伸出纖維。

11計(jì)算智能概述第11頁(yè)軸突是由細(xì)胞體向外延伸出全部纖維中最長(zhǎng)一條分枝，用來(lái)向外傳遞神經(jīng)元產(chǎn)生輸出電信號(hào)。每個(gè)神經(jīng)元都有一條軸突，其最大長(zhǎng)度可達(dá)1m以上。在軸突末端形成了許多很細(xì)分枝，這些分支叫神經(jīng)末梢。每一條神經(jīng)末梢能夠與其它神經(jīng)元形成功效性接觸，該接觸部位稱為突觸。所謂功效性接觸，是指非永久性接觸，這正是神經(jīng)元之間傳遞信息奧秘之處樹(shù)突是指由細(xì)胞體向外延伸除軸突以外其它全部分支。樹(shù)突長(zhǎng)度普通較短，但數(shù)量很多，它是神經(jīng)元輸入端，用于接收從其它神經(jīng)元突觸傳來(lái)信號(hào)。12計(jì)算智能概述第12頁(yè)(2)生物神經(jīng)元功效

依據(jù)神經(jīng)生理學(xué)研究，生物神經(jīng)元2個(gè)主要功效是:神經(jīng)元興奮與抑制，神經(jīng)元內(nèi)神經(jīng)沖動(dòng)傳導(dǎo)。①神經(jīng)元抑制與興奮抑制狀態(tài)是指神經(jīng)元在沒(méi)有產(chǎn)生沖動(dòng)時(shí)工作狀態(tài)。興奮狀態(tài)是指神經(jīng)元產(chǎn)生沖動(dòng)時(shí)工作狀態(tài)。通常情況下，神經(jīng)元膜電位約為-70毫伏，膜內(nèi)為負(fù)，膜外為正，處于抑制狀態(tài)。當(dāng)神經(jīng)元受到外部刺激時(shí)，其膜電位隨之發(fā)生改變，即膜內(nèi)電位上升、膜外電位下降，當(dāng)膜內(nèi)外電位差大于閾值電位（約+40毫伏）時(shí)，神經(jīng)元產(chǎn)生沖動(dòng)而進(jìn)入興奮狀態(tài)。說(shuō)明:神經(jīng)元每次沖動(dòng)連續(xù)時(shí)間大約1毫秒左右，在此期間即使刺激強(qiáng)度再增加也不會(huì)引發(fā)沖動(dòng)強(qiáng)度增加。神經(jīng)元每次沖動(dòng)結(jié)束后，都會(huì)重新回到抑制狀態(tài)。假如神經(jīng)元受到刺激作用不能使細(xì)胞膜內(nèi)外電位差大于閾值電位，則神經(jīng)元不會(huì)產(chǎn)生沖動(dòng)，將仍處于抑制狀態(tài)。②神經(jīng)元內(nèi)神經(jīng)沖動(dòng)傳導(dǎo)神經(jīng)沖動(dòng)在神經(jīng)元內(nèi)傳導(dǎo)是一個(gè)電傳導(dǎo)過(guò)程，神經(jīng)沖動(dòng)沿神經(jīng)纖維傳導(dǎo)速度卻在3.2---320km/s之間，且其傳導(dǎo)速度與纖維粗細(xì)、髓鞘有沒(méi)有有一定關(guān)系。普通來(lái)說(shuō)，有髓鞘纖維傳導(dǎo)速度較快，而無(wú)髓鞘纖維傳導(dǎo)速度較慢。13計(jì)算智能概述第13頁(yè)(3)人腦神經(jīng)系統(tǒng)聯(lián)結(jié)機(jī)制

①人腦神經(jīng)系統(tǒng)聯(lián)結(jié)規(guī)模人腦大約由1011--1012個(gè)神經(jīng)元所組成，其中每個(gè)神經(jīng)元大約有3＊104個(gè)突觸。小腦中每個(gè)神經(jīng)元大約有105個(gè)突觸，而且每個(gè)突觸都能夠與別神經(jīng)元一個(gè)樹(shù)突相連。人腦神經(jīng)系統(tǒng)就是由這些巨量生物神經(jīng)元經(jīng)廣泛并行互連所形成一個(gè)高度并行性、非常復(fù)雜神經(jīng)網(wǎng)絡(luò)系統(tǒng)。②人腦神經(jīng)系統(tǒng)分布功效人腦神經(jīng)系記憶和處理功效是有機(jī)結(jié)合在一起，每個(gè)神經(jīng)元既含有存放功效，同時(shí)又含有處理能力。從結(jié)構(gòu)上看，人腦神經(jīng)系統(tǒng)又是一個(gè)分布式系統(tǒng)統(tǒng)。人們經(jīng)過(guò)對(duì)腦損壞病人所做神經(jīng)生理學(xué)研究，沒(méi)有發(fā)覺(jué)大腦中哪一部分能夠決定其余全部各部分活動(dòng)，也沒(méi)有發(fā)覺(jué)在大腦中存在有用于驅(qū)動(dòng)和管理整個(gè)智能處理過(guò)程任何中央控制部分。即，人類大腦各個(gè)部分是協(xié)同工作、相互影響。在大腦中，不但知識(shí)存放是分散，而且其控制和決議也是分散。

14計(jì)算智能概述第14頁(yè)人工神經(jīng)網(wǎng)絡(luò)是由大量人工神經(jīng)元經(jīng)廣泛互聯(lián)所形成一個(gè)人工網(wǎng)絡(luò)系統(tǒng)，用以模擬人類神經(jīng)系統(tǒng)結(jié)構(gòu)和功效。(1)人工神經(jīng)元結(jié)構(gòu)(2)慣用人工神經(jīng)元模型

5.2.1神經(jīng)計(jì)算基礎(chǔ)2.人工神經(jīng)網(wǎng)絡(luò)介紹15計(jì)算智能概述第15頁(yè)人工神經(jīng)元結(jié)構(gòu)θ…x1x2xnw1w2wny人工神經(jīng)元是對(duì)生物神經(jīng)元抽象與模擬下列圖是一個(gè)MP神經(jīng)元模型

1943年，心理學(xué)家麥克洛奇(W.McMulloch)和數(shù)理邏輯學(xué)家皮茨(W.Pitts)依據(jù)生物神經(jīng)元功效和結(jié)構(gòu)，提出了一個(gè)將神經(jīng)元看作二進(jìn)制閾值元件簡(jiǎn)單模型，即MP模型。圖中x1,x2,…,xn表示某一神經(jīng)元n個(gè)輸入；wi表示第i個(gè)輸入連接強(qiáng)度，稱為連接權(quán)值；θ為神經(jīng)元閾值；y為神經(jīng)元輸出?？梢?jiàn)，人工神經(jīng)元是一個(gè)含有多輸入，單輸出非線性器件。其輸入為,輸出為其中，f稱為神經(jīng)元功效函數(shù)（或作用函數(shù)，激活函數(shù)）。16計(jì)算智能概述第16頁(yè)慣用人工神經(jīng)元模型依據(jù)功效函數(shù)不一樣，可得到不一樣神經(jīng)元模型。慣用模型包含：閾值型(Threshold)θf(wàn)(θ)1這種模型神經(jīng)元沒(méi)有內(nèi)部狀態(tài)，作用函數(shù)f是一個(gè)階躍函數(shù)，他表示激活值σ和輸出之間關(guān)系。這是一個(gè)連續(xù)神經(jīng)元模型，其輸入輸出特征慣用指數(shù)、對(duì)數(shù)或雙曲正切等S型函數(shù)表示。它反應(yīng)是神經(jīng)元飽和特征.分段線性強(qiáng)飽和型(LinearSaturation)S型(Sibmoid)子閾累積型(SubthresholdSummation)也是一個(gè)非線性函數(shù)，當(dāng)產(chǎn)生激活值超出T值時(shí)，該神經(jīng)元被激活產(chǎn)生個(gè)反響。在線性范圍內(nèi)，系統(tǒng)反響是線性。T1這種模型又稱為偽線性，其輸入/輸出之間在一定范圍內(nèi)滿足線性關(guān)系，一直延續(xù)到輸出為最大值1為止。但當(dāng)?shù)竭_(dá)最大值后，輸出就不再增。17計(jì)算智能概述第17頁(yè)5.2.2人工神經(jīng)網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)人工神經(jīng)網(wǎng)絡(luò)互連結(jié)構(gòu)（或稱拓?fù)浣Y(jié)構(gòu)）是指單個(gè)神經(jīng)元之間連接模式，它是結(jié)構(gòu)神經(jīng)網(wǎng)絡(luò)基礎(chǔ)，也是神經(jīng)網(wǎng)絡(luò)誘發(fā)偏差主要起源。從互連結(jié)構(gòu)角度：前饋網(wǎng)絡(luò)反饋網(wǎng)絡(luò)單層前饋網(wǎng)絡(luò)

多層前饋網(wǎng)絡(luò)

單層反饋網(wǎng)絡(luò)多層反饋網(wǎng)絡(luò)僅含輸入層和輸出層，且只有輸出層神經(jīng)元是可計(jì)算節(jié)點(diǎn)

除擁有輸入、輸出層外，還最少含有一個(gè)、或更多個(gè)隱含層前向網(wǎng)絡(luò)

指不擁有隱含層反饋網(wǎng)絡(luò)

指擁有隱含層反饋網(wǎng)絡(luò)

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

18計(jì)算智能概述第18頁(yè)包含單層前饋網(wǎng)絡(luò)和多層前饋網(wǎng)絡(luò)。單層前饋網(wǎng)絡(luò)是指那種只擁有單層計(jì)算節(jié)點(diǎn)前向網(wǎng)絡(luò)。它僅含有輸入層和輸出層，且只有輸出層神經(jīng)元是可計(jì)算節(jié)點(diǎn)，以下列圖所表示其中，輸入向量為X=(x1,x2,…,xn)；輸出向量為Y=(y1,y2,…,ym)；輸入層各個(gè)輸入到對(duì)應(yīng)神經(jīng)元連接權(quán)值分別是wij，i=1,2,..,n，j=1,2,..,m?！瓁1X2X3xny1Y2ym權(quán)值wij輸出層輸入層圖5.8單層前饋網(wǎng)絡(luò)結(jié)構(gòu)5.2.2人工神經(jīng)網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)1.前饋網(wǎng)絡(luò)(1/3)19計(jì)算智能概述第19頁(yè)若假設(shè)各神經(jīng)元閾值分別是θj，j=1,2,…,m，則各神經(jīng)元輸出yj,j=1,2,..,m分別為：其中，由全部連接權(quán)值wij組成連接權(quán)值矩陣W為：

在實(shí)際應(yīng)用中，該矩陣是經(jīng)過(guò)大量訓(xùn)練示例學(xué)習(xí)而形成。5.2.2人工神經(jīng)網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)1.前饋網(wǎng)絡(luò)(2/3)20計(jì)算智能概述第20頁(yè)多層前饋網(wǎng)絡(luò)是指那種除擁有輸入、輸出層外，還最少含有一個(gè)、或更多個(gè)隱含層前饋網(wǎng)絡(luò)。隱含層是指由那些既不屬于輸入層又不屬于輸出層神經(jīng)元所組成處理層,也被稱為中間層。隱含層作用是經(jīng)過(guò)對(duì)輸入層信號(hào)加權(quán)處理，將其轉(zhuǎn)移成更能被輸出層接收形式。

多層前饋網(wǎng)絡(luò)輸入層輸出向量是第一隱含層輸入信號(hào)，而第一隱含層輸出則是第二隱含層輸入信號(hào)，以這類推，直到輸出層。多層前饋網(wǎng)絡(luò)經(jīng)典代表是BP網(wǎng)絡(luò)。x1X2Xny1Ym隱含層輸出層輸入層圖5.9多層前饋網(wǎng)絡(luò)結(jié)構(gòu)………權(quán)值權(quán)值5.2.2人工神經(jīng)網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)1.前饋網(wǎng)絡(luò)(3/3)21計(jì)算智能概述第21頁(yè)5.2.2人工神經(jīng)網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu)2.反饋網(wǎng)絡(luò)

反饋網(wǎng)絡(luò)是指允許采取反饋聯(lián)結(jié)方式所形成神經(jīng)網(wǎng)絡(luò)。所謂反饋聯(lián)結(jié)方式是指一個(gè)神經(jīng)元輸出能夠被反饋至同層或前層神經(jīng)元。

反饋網(wǎng)絡(luò)和前向網(wǎng)絡(luò)不一樣：

前向網(wǎng)絡(luò)屬于非循環(huán)連接模式，它每個(gè)神經(jīng)元輸入都沒(méi)有包含該神經(jīng)元先前輸出，所以不含有“短期記憶”性質(zhì)。

反饋網(wǎng)絡(luò)則不一樣，它每個(gè)神經(jīng)元輸入都有可能包含有該神經(jīng)元先前輸出反饋信息，即一個(gè)神經(jīng)元輸出是由該神經(jīng)元當(dāng)前輸入和先前輸出這二者來(lái)決定，這就有點(diǎn)類似于人類短期記憶性質(zhì)。反饋網(wǎng)絡(luò)經(jīng)典例子是后面將要介紹Hopfield網(wǎng)絡(luò)22計(jì)算智能概述第22頁(yè)人工神經(jīng)網(wǎng)絡(luò)模型是指對(duì)網(wǎng)絡(luò)結(jié)構(gòu)、聯(lián)結(jié)權(quán)值和學(xué)習(xí)能力總括。慣用網(wǎng)絡(luò)模型已經(jīng)有數(shù)十種。比如：傳統(tǒng)感知機(jī)模型，含有誤差反向傳輸功效反向傳輸網(wǎng)絡(luò)模型，采取多變量插值徑向基函數(shù)網(wǎng)絡(luò)模型，建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上支撐向量機(jī)網(wǎng)絡(luò)模型，采取反饋聯(lián)接方式反饋網(wǎng)絡(luò)模型，基于模擬退火算法隨機(jī)網(wǎng)絡(luò)模型。本小節(jié)主要討論感知機(jī)（Perceptron）模型反向傳輸（BP）模型反饋網(wǎng)絡(luò)（Hopfield）模型

3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型

23計(jì)算智能概述第23頁(yè)感知器是美國(guó)學(xué)者羅森勃拉特（Rosenblatt）于1957年為研究大腦存放、學(xué)習(xí)和認(rèn)知過(guò)程而提出一類含有自學(xué)習(xí)能力神經(jīng)網(wǎng)絡(luò)模型，其拓?fù)浣Y(jié)構(gòu)是一個(gè)分層前向網(wǎng)絡(luò)。它包含：?jiǎn)螌痈兄鞫鄬痈兄?.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型1.感知器模型(1/10)24計(jì)算智能概述第24頁(yè)(1)單層感知器單層感知器是一個(gè)只含有單層可調(diào)整連接權(quán)值神經(jīng)元前向網(wǎng)絡(luò)，這些神經(jīng)元組成了單層感知器輸出層，是感知器可計(jì)算節(jié)點(diǎn)。在單層感知器中，每個(gè)可計(jì)算節(jié)點(diǎn)都是一個(gè)線性閾值神經(jīng)元。當(dāng)輸入信息加權(quán)和大于或等于閾值時(shí)，輸出為1，不然輸出為0或-1。單層感知器輸出層每個(gè)神經(jīng)元都只有一個(gè)輸出，且該輸出僅與本神經(jīng)元輸入及聯(lián)接權(quán)值相關(guān)，而與其它神經(jīng)元無(wú)關(guān)。3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型1.感知器模型(2/10)25計(jì)算智能概述第25頁(yè)單層感知器結(jié)構(gòu)以下列圖…x1x2xn…y1ym輸入層輸出層權(quán)值wij輸入向量為X=(x1,x2,…,xn)；輸出向量為Y=(y1,y2,…,ym)；輸入層各個(gè)輸入到對(duì)應(yīng)神經(jīng)元連接權(quán)值分別是wij，i=1,2,..,n，j=1,2,..,m。

若假設(shè)各神經(jīng)元閾值分別是θj，j=1,2,…,m，則各神經(jīng)元輸出yj,j=1,2,..,m分別為其中，由全部連接權(quán)值wji組成連接權(quán)值矩陣W為：在實(shí)際應(yīng)用中，該矩陣是經(jīng)過(guò)大量訓(xùn)練示例學(xué)習(xí)而形成26計(jì)算智能概述第26頁(yè)使用感知器主要目標(biāo)是為了對(duì)外部輸入進(jìn)行分類。羅森勃拉特已經(jīng)證實(shí)，假如外部輸入是線性可分（指存在一個(gè)超平面能夠?qū)⑺鼈兎珠_(kāi)），則單層感知器一定能夠把它劃分為兩類。其判別超平面由以下判別式確定：

作為例子，下面討論用單個(gè)感知器實(shí)現(xiàn)邏輯運(yùn)算問(wèn)題。實(shí)際上，單層感知器能夠很好地實(shí)現(xiàn)“與”、“或”、“非”運(yùn)算，但卻不能處理“異或”問(wèn)題。

3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型1.感知器模型(4/10)27計(jì)算智能概述第27頁(yè)例5.1“與”運(yùn)算（x1∧x2）(0,0)(1,1)(0,1)(1,0)圖5.10與運(yùn)算問(wèn)題圖示輸入輸出超平面閾值條件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

能夠證實(shí)此表有解，比如取w1=1，w2=1，θ=1.5，其分類結(jié)果如右圖所表示。其中，輸出為1用實(shí)心圓，輸出為0用空心圓。后面約定相同。3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型1.感知器模型(5/10)28計(jì)算智能概述第28頁(yè)例5.2“或”運(yùn)算（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，其分類結(jié)果如右圖所表示。(0,1)(0,0)(1,0)圖5.11與運(yùn)算問(wèn)題圖示(1,1)3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型1.感知器模型(6/10)29計(jì)算智能概述第29頁(yè)例5.3“非”運(yùn)算（?x1）輸入輸出超平面閾值條件x1?x1w1*x1-θ=001w1*0-θ≥0θ≤010w1*1

–θ<0θ>w1此表也有解，比如取w1=-1，θ=-0.5，其分類結(jié)果如右圖所表示。圖5.12非運(yùn)算問(wèn)題圖示013.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型1.感知器模型(7/10)30計(jì)算智能概述第30頁(yè)例5.4“異或”運(yùn)算（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

此表無(wú)解，即無(wú)法找到滿足條件w1、w2和θ，如右圖所表示。因?yàn)楫惢騿?wèn)題是一個(gè)非線性可分問(wèn)題，需要用多層感知器來(lái)處理。(0,1)(0,0)(1,0)圖5.13異或運(yùn)算問(wèn)題圖示(1,1)3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型1.感知器模型(8/10)31計(jì)算智能概述第31頁(yè)(2)多層感知器多層感知器是經(jīng)過(guò)在單層感知器輸入、輸出層之間加入一層或多層處理單元所組成。其拓?fù)浣Y(jié)構(gòu)與圖5.9所表示多層前向網(wǎng)絡(luò)相同，差異也在于其計(jì)算節(jié)點(diǎn)連接權(quán)值是可變。多層感知器輸入與輸出之間是一個(gè)高度非線性映射關(guān)系，如圖5.9所表示多層前向網(wǎng)絡(luò)，若采取多層感知器模型，則該網(wǎng)絡(luò)就是一個(gè)從n維歐氏空間到m維歐氏空間非線性映射。所以，多層感知器能夠?qū)崿F(xiàn)非線性可分問(wèn)題分類。比如，對(duì)“異或”運(yùn)算，用圖5.14所表示多層感知器即可處理。3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型1.感知器模型(9/10)32計(jì)算智能概述第32頁(yè)x11y=x1

XORx2x1X2x121-1111-1輸入層隱層輸出層權(quán)值權(quán)值圖5.14“異或”問(wèn)題多層感知器閾值0.5閾值-1.5閾值1.5(0,1)(0,0)(1,0)圖5.15異或問(wèn)題處理(1,1)在圖5.14中，隱層神經(jīng)元x11所確定直線方程為它能夠識(shí)別一個(gè)半平面。隱層神經(jīng)元x12所確定直線方程為它也能夠識(shí)別一個(gè)半平面。輸出層神經(jīng)元所確定直線方程為它相當(dāng)于對(duì)隱層神經(jīng)元x11和x12輸出作“邏輯與”運(yùn)算，所以可識(shí)別由隱層已識(shí)別兩個(gè)半平面交集所組成一個(gè)凸多邊形，如圖5.15所表示。

33計(jì)算智能概述第33頁(yè)

誤差反向傳輸(ErrorBackPropagation)網(wǎng)絡(luò)通常簡(jiǎn)稱為BP(BackPropagation)網(wǎng)絡(luò)，是由美國(guó)加州大學(xué)魯梅爾哈特和麥克萊蘭在研究并行分布式信息處理方法，探索人類認(rèn)知微結(jié)構(gòu)過(guò)程中，于1985年提出一個(gè)網(wǎng)絡(luò)模型。BP網(wǎng)絡(luò)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是多層前向網(wǎng)絡(luò)，如圖5.16所表示。在BP網(wǎng)絡(luò)中，同層節(jié)點(diǎn)之間不存在相互連接，層與層之間多采取全互連方式，且各層連接權(quán)值可調(diào)。BP網(wǎng)絡(luò)實(shí)現(xiàn)了明斯基多層網(wǎng)絡(luò)構(gòu)想，是當(dāng)今神經(jīng)網(wǎng)絡(luò)模型中使用最廣泛一個(gè)。y1y2ymx1x2xn輸出層隱含層輸入層權(quán)可調(diào)權(quán)可調(diào)………圖5.16一個(gè)多層BP網(wǎng)絡(luò)結(jié)構(gòu)3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型2.BP網(wǎng)絡(luò)模型(1/2)34計(jì)算智能概述第34頁(yè)

對(duì)BP網(wǎng)絡(luò)需說(shuō)明以下兩點(diǎn)：第一，BP網(wǎng)絡(luò)每個(gè)處理單元均為非線性輸入/輸出關(guān)系，其作用函數(shù)通常采取是可微Sigmoid函數(shù)，如：第二，BP網(wǎng)絡(luò)學(xué)習(xí)過(guò)程是由工作信號(hào)正向傳輸和誤差信號(hào)反向傳輸組成。所謂正向傳輸，是指輸入模式經(jīng)隱層到輸出層，最終形成輸出模式；所謂誤差反向傳輸，是指從輸出層開(kāi)始逐層將誤差傳到輸入層，并修改各層聯(lián)接權(quán)值，使誤差信號(hào)為最小過(guò)程。3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型2.BP網(wǎng)絡(luò)模型(2/2)35計(jì)算智能概述第35頁(yè)

Hopfield網(wǎng)絡(luò)是由美國(guó)加州工學(xué)院物理學(xué)家霍普菲爾特1982年提出來(lái)一個(gè)單層全互連對(duì)稱反饋網(wǎng)絡(luò)模型。它可分為離散Hopfield網(wǎng)絡(luò)和連續(xù)Hopfield網(wǎng)絡(luò)，限于篇幅，本書(shū)重點(diǎn)討論離散Hopfield網(wǎng)絡(luò)。離散Hopfield網(wǎng)絡(luò)結(jié)構(gòu)離散Hopfield網(wǎng)絡(luò)是在非線性動(dòng)力學(xué)基礎(chǔ)上由若干基本神經(jīng)元組成一個(gè)單層全互連網(wǎng)絡(luò)，其任意神經(jīng)元之間都有連接，而且是一個(gè)對(duì)稱連接結(jié)構(gòu)。一個(gè)經(jīng)典離散Hopfidld網(wǎng)絡(luò)結(jié)構(gòu)如圖5-17所表示。離散Hopfield網(wǎng)絡(luò)模型是一個(gè)離散時(shí)間系統(tǒng)，每個(gè)神經(jīng)元只有0和1（或-1和1）兩種狀態(tài)，任意神經(jīng)元i和j之間連接權(quán)值為wij。因?yàn)樯窠?jīng)元之間為對(duì)稱連接，且神經(jīng)元本身無(wú)連接，所以有

由該連接權(quán)值所組成連接矩陣是一個(gè)零對(duì)角對(duì)稱矩陣。3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型2.Hopfield網(wǎng)絡(luò)模型(1/2)36計(jì)算智能概述第36頁(yè)圖5?17離散Hopfield網(wǎng)絡(luò)結(jié)構(gòu)ymY2Y1x1……x2xn輸入層輸出層在Hopfidld網(wǎng)絡(luò)中，即使神經(jīng)元本身無(wú)連接，但因?yàn)槊總€(gè)神經(jīng)元都與其它神經(jīng)元相連，即每個(gè)神經(jīng)元輸出都將經(jīng)過(guò)突觸連接權(quán)值傳遞給別神經(jīng)元，同時(shí)每個(gè)神經(jīng)元又都接收其它神經(jīng)元傳來(lái)信息，這么對(duì)每個(gè)神經(jīng)元來(lái)說(shuō)，其輸出經(jīng)過(guò)其它神經(jīng)元后又有可能反饋給自己，所以Hopfidld網(wǎng)絡(luò)是一個(gè)反饋神經(jīng)網(wǎng)絡(luò)

3.2.3人工神經(jīng)網(wǎng)絡(luò)經(jīng)典模型2.Hopfield網(wǎng)絡(luò)模型(2/2)37計(jì)算智能概述第37頁(yè)

進(jìn)化計(jì)算（EvolutionaryComputation,EC）是在達(dá)爾文（Darwin）進(jìn)化論和孟德?tīng)枺∕endel）遺傳變異理論基礎(chǔ)上產(chǎn)生一個(gè)在基因和種群層次上模擬自然界生物進(jìn)化過(guò)程與機(jī)制問(wèn)題求解技術(shù)。它主要包含遺傳算法（GeneticAlgorithm，GA）進(jìn)化策略（EvolutionaryStrategy,ES）進(jìn)化規(guī)劃（EvolutionaryProgramming,EP）遺傳規(guī)劃（GeneticProgramming,GP）四大分支。其中，第一個(gè)分支是進(jìn)化計(jì)算中最初形成一個(gè)含有普遍影響模擬進(jìn)化優(yōu)化算法。所以我們主要討論遺傳算法。5.3進(jìn)化計(jì)算38計(jì)算智能概述第38頁(yè)進(jìn)化計(jì)算是一個(gè)模擬自然界生物進(jìn)化過(guò)程與機(jī)制進(jìn)行問(wèn)題求解自組織、自適應(yīng)隨機(jī)搜索技術(shù)。它以達(dá)爾文進(jìn)化論“物竟天擇、適者生存”作為算法進(jìn)化規(guī)則，并結(jié)合孟德?tīng)栠z傳變異理論，將生物進(jìn)化過(guò)程中繁殖（Reproduction）變異（Mutation）競(jìng)爭(zhēng)（Competition）選擇（Selection）引入到了算法中。5.3.1進(jìn)化計(jì)算概述1.進(jìn)化計(jì)算及其生物學(xué)基礎(chǔ)(1/3)(1)什么是進(jìn)化計(jì)算39計(jì)算智能概述第39頁(yè)(2)進(jìn)化計(jì)算生物學(xué)基礎(chǔ)

自然界生物進(jìn)化過(guò)程是進(jìn)化計(jì)算生物學(xué)基礎(chǔ)，它主要包含遺傳(Heredity)、變異(Mutation)和進(jìn)化(Evolution)理論。①遺傳理論

遺傳是指父代（或親代）利用遺傳基因?qū)⒈旧砘蛐畔鬟f給下一代（或子代），使子代能夠繼承其父代特征或性狀這種生命現(xiàn)象。正是因?yàn)檫z傳作用，自然界才能有穩(wěn)定物種。在自然界，組成生物基本結(jié)構(gòu)與功效單位是細(xì)胞（Cell）。細(xì)胞中含有一個(gè)包含著全部遺傳信息復(fù)雜而又微小絲狀化合物，人們稱其為染色體（Chromosome）。在染色體中，遺傳信息由基因（Gene）所組成，基因決定著生物性狀，是遺傳基本單位。染色體形狀是一個(gè)雙螺旋結(jié)構(gòu)，組成染色體主要物質(zhì)叫做脫氧核糖核酸(DNA)，每個(gè)基因都在DNA長(zhǎng)鏈中占有一定位置。一個(gè)細(xì)胞中全部染色體所攜帶遺傳信息全體稱為一個(gè)基因組(Genome)。細(xì)胞在分裂過(guò)程中，其遺傳物質(zhì)DNA經(jīng)過(guò)復(fù)制轉(zhuǎn)移到新生細(xì)胞中，從而實(shí)現(xiàn)了生物遺傳功效。5.3.1進(jìn)化計(jì)算概述1.進(jìn)化計(jì)算及其生物學(xué)基礎(chǔ)(2/3)40計(jì)算智能概述第40頁(yè)②變異理論

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

進(jìn)化是指在生物延續(xù)生存過(guò)程中，逐步適應(yīng)其生存環(huán)境，使得其品質(zhì)不停得到改良這種生命現(xiàn)象。遺傳和變異是生物進(jìn)化兩種基本現(xiàn)象，優(yōu)勝劣汰、適者生存是生物進(jìn)化基本規(guī)律。達(dá)爾文自然選擇學(xué)說(shuō)認(rèn)為：在生物進(jìn)化中，一個(gè)基因有可能發(fā)生變異而產(chǎn)生出另一個(gè)新生物基因。這種新基因?qū)⒁罁?jù)其與生存環(huán)境適應(yīng)性而決定其增殖能力。普通情況下，適應(yīng)性強(qiáng)基因會(huì)不停增多，而適應(yīng)性差基因則會(huì)逐步降低。經(jīng)過(guò)這種自然選擇，物種將逐步向適應(yīng)于生存環(huán)境方向進(jìn)化，甚至?xí)葑兂蔀榱硪粋€(gè)新物種，而那些不適應(yīng)于環(huán)境物種將會(huì)逐步被淘汰。5.3.1進(jìn)化計(jì)算概述1.進(jìn)化計(jì)算及其生物學(xué)基礎(chǔ)(3/3)41計(jì)算智能概述第41頁(yè)

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

這一階段是從20世紀(jì)90年代至今。1989年，美國(guó)斯坦福（Stanford）大學(xué)科扎（Koza）提出了遺傳規(guī)劃新概念，并于1992年出版了專著《遺傳規(guī)劃----應(yīng)用自然選擇法則計(jì)算機(jī)程序設(shè)計(jì)（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection）》該書(shū)全方面介紹了遺傳規(guī)劃基本原理及應(yīng)用實(shí)例，標(biāo)志著遺傳規(guī)劃作為計(jì)算智能一個(gè)分支已基本形成。進(jìn)入20世紀(jì)90年代以來(lái)，進(jìn)化計(jì)算得到了眾多研究機(jī)構(gòu)和學(xué)者高度重視，新研究結(jié)果不停出現(xiàn)、應(yīng)用領(lǐng)域不停擴(kuò)大。當(dāng)前，進(jìn)化計(jì)算已成為人工智能領(lǐng)域又一個(gè)新研究熱點(diǎn)。

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

種群（Population）：種群是指用遺傳算法求解問(wèn)題時(shí)，初始給定多個(gè)解集合。遺傳算法求解過(guò)程是從這個(gè)子集開(kāi)始。

個(gè)體（Individual）：個(gè)體是指種群中單個(gè)元素，它通常由一個(gè)用于描述其基本遺傳結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)來(lái)表示。比如，能夠用0、1組成長(zhǎng)度為l串來(lái)表示個(gè)體。

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

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

遺傳操作（GeneticOperator）：遺傳操作是指作用于種群而產(chǎn)生新種群操作。標(biāo)準(zhǔn)遺傳操作包含以下3種基本形式：

選擇（Selection）

交叉（Crosssover）

變異（Mutation）5.3.2遺傳算法1.遺傳算法基本概念45計(jì)算智能概述第45頁(yè)

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

(1)選擇編碼策略，將問(wèn)題搜索空間中每個(gè)可能點(diǎn)用對(duì)應(yīng)編碼策略表示出來(lái)，即形成染色體；(2)定義遺傳策略，包含種群規(guī)模N，交叉、變異方法，以及選擇概率Pr、交叉概率Pc、變異概率Pm等遺傳參數(shù)；(3)令t=0，隨機(jī)選擇N個(gè)染色體初始化種群P(0)；(4)定義適應(yīng)度函數(shù)f（f>0）；(5)計(jì)算P(t)中每個(gè)染色體適應(yīng)值；(6)t=t+1；(7)利用選擇算子，從P(t-1)中得到P(t)；(8)對(duì)P(t)中每個(gè)染色體，按概率Pc參加交叉；(9)對(duì)染色體中基因，以概率Pm參加變異運(yùn)算；(10)判斷群體性能是否滿足預(yù)先設(shè)定終止標(biāo)準(zhǔn)，若不滿足則返回(5)。5.3.2遺傳算法2.遺傳算法基本結(jié)構(gòu)(1/2)46計(jì)算智能概述第46頁(yè)計(jì)算種群中各個(gè)個(gè)體適應(yīng)度，并進(jìn)行評(píng)價(jià)滿足終止條件嗎？終止選擇交叉變異Y圖5-18基本遺傳算法算法流程圖編碼和生成初始種群N選擇其算法流程如圖5-18所表示。5.3.2遺傳算法2.遺傳算法基本結(jié)構(gòu)(2/2)47計(jì)算智能概述第47頁(yè)慣用遺傳編碼算法有霍蘭德二進(jìn)制碼、格雷碼（GrayCode）、實(shí)數(shù)編碼和字符編碼等。

(1)二進(jìn)制編碼（Binaryencoding）

二進(jìn)制編碼是將原問(wèn)題結(jié)構(gòu)變換為染色體位串結(jié)構(gòu)。在二進(jìn)制編碼中，首先要確定二進(jìn)制字符串長(zhǎng)度l，該長(zhǎng)度與變量定義域和所求問(wèn)題計(jì)算精度相關(guān)。例5.5

假設(shè)變量x定義域?yàn)閇5，10]，要求計(jì)算精度為10-5，則需要將[5，10]最少分為600000個(gè)等長(zhǎng)小區(qū)間，每個(gè)小區(qū)間用一個(gè)二進(jìn)制串表示。于是，串長(zhǎng)最少等于20，原因是：524288=219<600000<220=1048576這么，對(duì)應(yīng)于區(qū)間[5，10]內(nèi)滿足精度要求每個(gè)值x，都可用一個(gè)20位編碼二進(jìn)制串<b19,b18,…,b0>來(lái)表示。

二進(jìn)制編碼存在主要缺點(diǎn)是漢明（Hamming）懸崖。比如，7和8二進(jìn)制數(shù)分別為0111和1000，當(dāng)算法從7改進(jìn)到8時(shí)，就必須改變?nèi)课弧?/p>

5.3.2遺傳算法3.遺傳編碼(1/3)48計(jì)算智能概述第48頁(yè)5.3.2遺傳算法3.遺傳編碼(2/3)(2)格雷編碼（Grayencoding）

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

十進(jìn)制數(shù)7和8二進(jìn)制編碼分別為0111和1000，而其格雷編碼分別為0100和1100。49計(jì)算智能概述第49頁(yè)

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

實(shí)數(shù)編碼是將每個(gè)個(gè)體染色體都用某一范圍一個(gè)實(shí)數(shù)（浮點(diǎn)數(shù)）來(lái)表示，其編碼長(zhǎng)度等于該問(wèn)題變量個(gè)數(shù)。這種編碼方法是將問(wèn)題解空間映射到實(shí)數(shù)空間上，然后在實(shí)數(shù)空間上進(jìn)行遺傳操作。因?yàn)閷?shí)數(shù)編碼使用是變量真實(shí)值，所以這種編碼方法也叫做真值編碼方法。實(shí)數(shù)編碼適應(yīng)于那種多維、高精度要求連續(xù)函數(shù)優(yōu)化問(wèn)題。

5.3.2遺傳算法3.遺傳編碼(3/3)50計(jì)算智能概述第50頁(yè)

適應(yīng)度函數(shù)是一個(gè)用于對(duì)個(gè)體適應(yīng)性進(jìn)行度量函數(shù)。通常，一個(gè)個(gè)體適應(yīng)度值越大，它被遺傳到下一代種群中概率也就越大。(1)慣用適應(yīng)度函數(shù)

在遺傳算法中，有許多計(jì)算適應(yīng)度方法，其中最慣用適應(yīng)度函數(shù)有以下兩種：①原始適應(yīng)度函數(shù)它是直接將待求解問(wèn)題目標(biāo)函數(shù)f(x)定義為遺傳算法適應(yīng)度函數(shù)。比如，在求解極值問(wèn)題時(shí)，f(x)即為x原始適應(yīng)度函數(shù)。采取原始適應(yīng)度函數(shù)優(yōu)點(diǎn)是能夠直接反應(yīng)出待求解問(wèn)題最初求解目標(biāo)，其缺點(diǎn)是有可能出現(xiàn)適應(yīng)度值為負(fù)情況。

5.3.2遺傳算法4.適應(yīng)度函數(shù)(1/4)51計(jì)算智能概述第51頁(yè)②標(biāo)準(zhǔn)適應(yīng)度函數(shù)在遺傳算法中，普通要求適應(yīng)度函數(shù)非負(fù)，并其適應(yīng)度值越大越好。這就往往需要對(duì)原始適應(yīng)函數(shù)進(jìn)行某種變換，將其轉(zhuǎn)換為標(biāo)準(zhǔn)度量方式，以滿足進(jìn)化操作要求，這么所得到適應(yīng)度函數(shù)被稱為標(biāo)準(zhǔn)適應(yīng)度函數(shù)fNormal(x)。極小化問(wèn)題對(duì)極小化問(wèn)題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為其中，fmax(x)是原始適應(yīng)函數(shù)f(x)一個(gè)上界。假如fmax(x)未知，則可用當(dāng)前代或到當(dāng)前為止各演化代中f(x)最大值來(lái)代替?？梢?jiàn)，fmax(x)是會(huì)伴隨進(jìn)化代數(shù)增加而不停改變。

5.3.2遺傳算法4.適應(yīng)度函數(shù)(2/4)52計(jì)算智能概述第52頁(yè)極大化問(wèn)題對(duì)極大化問(wèn)題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為其中，fmin(x)是原始適應(yīng)函數(shù)f(x)一個(gè)下界。假如fmin(x)未知，則可用當(dāng)前代或到當(dāng)前為止各演化代中f(x)最小值來(lái)代替。

5.3.2遺傳算法4.適應(yīng)度函數(shù)(3/4)53計(jì)算智能概述第53頁(yè)(2)適應(yīng)度函數(shù)加速變換在一些情況下，適應(yīng)度函數(shù)在極值附近改變可能會(huì)非常小，以至于不一樣個(gè)體適應(yīng)值非常靠近，使得難以區(qū)分出哪個(gè)染色體更占優(yōu)勢(shì)。對(duì)此，最好能定義新適應(yīng)度函數(shù)，使該適應(yīng)度函數(shù)既與問(wèn)題目標(biāo)函數(shù)含有相同改變趨勢(shì)，又有更加快改變速度。適應(yīng)度函數(shù)加速變換有兩種基本方法①線性加速適應(yīng)度函數(shù)定義以下：

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

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

f’(x)=exp(-βf(x))5.3.2遺傳算法4.適應(yīng)度函數(shù)(4/4)54計(jì)算智能概述第54頁(yè)

遺傳算法中基本遺傳操作包含選擇、交叉和變異3種，而每種操作又包含各種不一樣方法，下面分別對(duì)它們進(jìn)行介紹。(1).選擇操作

選擇（Selection）操作是指依據(jù)選擇概率按某種策略從當(dāng)前種群中挑選出一定數(shù)目標(biāo)個(gè)體，使它們能夠有更多機(jī)會(huì)被遺傳到下一代中。慣用選擇策略可分為百分比選擇、排序選擇和競(jìng)技選擇三種類型。①百分比選擇

百分比選擇方法（ProportionalModel）基本思想是：各個(gè)個(gè)體被選中概率與其適應(yīng)度大小成正比。慣用百分比選擇策略包含輪盤賭選擇繁殖池選擇5.3.2遺傳算法5.基本遺傳操作(1/11)55計(jì)算智能概述第55頁(yè)②輪盤賭選擇

輪盤賭選擇法又被稱為轉(zhuǎn)盤賭選擇法或輪盤選擇法。在這種方法中，個(gè)體被選中概率取決于該個(gè)體相對(duì)適應(yīng)度。而相對(duì)適應(yīng)度定義為：其中，P(xi)是個(gè)體xi相對(duì)適應(yīng)度，即個(gè)體xi被選中概率；f(xi)是個(gè)體xi原始適應(yīng)度；是種群累加適應(yīng)度。輪盤賭選擇算法基本思想是：依據(jù)每個(gè)個(gè)體選擇概率P(xi)將一個(gè)圓盤分成N個(gè)扇區(qū)，其中第i個(gè)扇區(qū)中心角為：并再設(shè)置一個(gè)固定指針。當(dāng)進(jìn)行選擇時(shí)，能夠假想轉(zhuǎn)動(dòng)圓盤，若圓盤靜止時(shí)指針指向第i個(gè)扇區(qū)，則選擇個(gè)體i。其物理意義如圖5-19所表示。

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

(2)交叉操作

交叉（Crossover）操作是指按照某種方式對(duì)選擇父代個(gè)體染色體部分基因進(jìn)行交配重組，從而形成新個(gè)體。交配重組是自然界中生物遺傳進(jìn)化一個(gè)主要步驟，也是遺傳算法中產(chǎn)生新個(gè)體最主要方法。依據(jù)個(gè)體編碼方法不一樣，遺傳算法中交叉操作可分為二進(jìn)制交叉和實(shí)值交叉兩種類型。①二進(jìn)制交叉

二進(jìn)制交叉（BinaryValuedCrossover）是指二進(jìn)制編碼情況下所采取交叉操作，它主要包含單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉和均勻交叉等方法。5.3.2遺傳算法5.基本遺傳操作(4/11)58計(jì)算智能概述第58頁(yè)單點(diǎn)交叉

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

yk+1…yn

Y’=y1y2…yk

xk+1…xn

例5.7

設(shè)有兩個(gè)父代個(gè)體串A=001101

和B=110010

，若隨機(jī)交叉點(diǎn)為4，則交叉后生成兩個(gè)新個(gè)體是：A’=001110

B’=110001

5.3.2遺傳算法5.基本遺傳操作(5/11)59計(jì)算智能概述第59頁(yè)兩點(diǎn)交叉

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

yi+1…yjxj+1…xn

Y’=y1y2…yi

xi+1…xjyj+1…yn

例5.8

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

xj+1…xk

yk+1

…yn

Y’=y1y2…yi

xi+1…xjyj+1…yk

xk+1…xn

例5.9

設(shè)有兩個(gè)父代個(gè)體串A=001101和B=110010，若隨機(jī)交叉點(diǎn)為1、3和5，則交叉后兩個(gè)新個(gè)體是：A’=010100

B’=101011

5.3.2遺傳算法5.基本遺傳操作(7/11)61計(jì)算智能概述第61頁(yè)均勻交叉均勻交叉（UniformCrossover）是先隨機(jī)生成一個(gè)與父串含有相同長(zhǎng)度，并被稱為交叉模版（或交叉掩碼）二進(jìn)制串，然后再利用該模版對(duì)兩個(gè)父串進(jìn)行交叉，即將模版中1對(duì)應(yīng)位進(jìn)行交換，而0對(duì)應(yīng)位不交換，依此生成子代中兩個(gè)新個(gè)體。實(shí)際上，這種方法對(duì)父串中每一位都是以相同概率隨機(jī)進(jìn)行交叉。例5.10

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

0

B’：10000

15.3.2遺傳算法5.基本遺傳操作(8/11)62計(jì)算智能概述第62頁(yè)

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

yk+1…ynY’=y1y2…yk

xk+1…xn例5.11

設(shè)有兩個(gè)父代個(gè)體向量A=201619321826和B=362538122130，若隨機(jī)選擇對(duì)第3個(gè)分量以后全部分量進(jìn)行交叉，則交叉后兩個(gè)新個(gè)體向量是：A’=20161912

21

30B’=36253832

18

26

5.3.2遺傳算法5.基本遺傳操作(9/11)63計(jì)算智能概述第63頁(yè)

(3)變異操作

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

②實(shí)值變異當(dāng)個(gè)體染色體采取實(shí)數(shù)編碼表示時(shí)，其變異操作應(yīng)采取實(shí)值變異方法。該方法是用另外一個(gè)在要求范圍內(nèi)隨機(jī)實(shí)數(shù)去替換原變異位置上基因值，產(chǎn)生一個(gè)新個(gè)體。最慣用實(shí)值變異操作有:基于位置變異方法該方法是先隨機(jī)地產(chǎn)生兩個(gè)變異位置，然后將第二個(gè)變異位置上基因移動(dòng)到第一個(gè)變異位置前面。例5.13

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

設(shè)選中個(gè)體向量D=201216192130，若隨機(jī)產(chǎn)生兩個(gè)變異位置分別時(shí)2和4，則變異后新個(gè)體向量是：D’=2019161221305.3.2遺傳算法5.基本遺傳操作(11/11)65計(jì)算智能概述第65頁(yè)例5.15

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

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

因?yàn)閤定義域是區(qū)間[0，31]上整數(shù)，由5位二進(jìn)制數(shù)即可全部表示。所以，可采取二進(jìn)制編碼方法，其編碼串長(zhǎng)度為5。比如，用二進(jìn)制串00000來(lái)表示x=0,11111來(lái)表示x=31等。其中0和1為基因值。

(2)生成初始種群

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

s01=01101s02=11001s03=01000s04=100105.3.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(1/10)66計(jì)算智能概述第66頁(yè)(3)計(jì)算適應(yīng)度要計(jì)算個(gè)體適應(yīng)度，首先應(yīng)該定義適應(yīng)度函數(shù)。因?yàn)楸纠乔骹(x)最大值，所以可直接用f(x)來(lái)作為適應(yīng)度函數(shù)。即：f(s)=f(x)其中二進(jìn)制串s對(duì)應(yīng)著變量x值。根據(jù)此函數(shù)，初始種群中各個(gè)個(gè)體適應(yīng)值及其所占百分比如表5-5所示。表5-5初始種群情況表能夠看出，在4個(gè)個(gè)體中S03適應(yīng)值最大，是當(dāng)前最佳個(gè)體。編號(hào)個(gè)體串（染色體）x適應(yīng)值百分比%累計(jì)百分比%選中次數(shù)S01011011316914.4414.441S02110012562552.8867.182S03010008645.4172.590S04100101832427.4110015.3.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(2/10)67計(jì)算智能概述第67頁(yè)(4)選擇操作

假設(shè)采取輪盤賭方式選擇個(gè)體，且依次生成4個(gè)隨機(jī)數(shù)（相當(dāng)于輪盤上指針?biāo)笖?shù)）為0.85、0.32、0.12和0.46，經(jīng)選擇后得到新種群為：

S01=10010S02=11001S03=01101S04=11001其中，染色體11001在種群中出現(xiàn)了2次，而原染色體01000則因適應(yīng)值太小而被淘汰5.3.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(3/10)68計(jì)算智能概述第68頁(yè)(5)交叉

假設(shè)交叉概率Pi為50%，則種群中只有1/2染色體參加交叉。若要求種群中染色體按次序兩兩配對(duì)交叉，且有S01與S02交叉，S03與S04不交叉，則交叉情況如表5-6所表示。表5-6初始種群交叉情況表可見(jiàn)，經(jīng)交叉后得到新種群為：S01=10001S02=11010S03=01101S04=11001編號(hào)個(gè)體串（染色體）交叉對(duì)象交叉位子代適應(yīng)值S0110010S02310001289S0211001S01311010676S0301101S04N01101169S0411001S03N110016255.3.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(4/10)69計(jì)算智能概述第69頁(yè)(6)變異

變異概率Pm普通都很小，假設(shè)此次循環(huán)中沒(méi)有發(fā)生變異，則變異前種群即為進(jìn)化后所得到第1代種群。即：

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

5.3.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(5/10)70計(jì)算智能概述第70頁(yè)對(duì)第1代種群，一樣重復(fù)上述(4)-(6)操作。其選擇情況如表5-7所表示。表5-7第1代種群選擇情況表

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

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

編號(hào)個(gè)體串（染色體）是否變異變異位子代適應(yīng)值S1110010N10010324S1211001N11001625S1311001N11001625S1411010Y3111109005.3.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(8/10)73計(jì)算智能概述第73頁(yè)對(duì)第2代種群，一樣重復(fù)上述(4)-(6)操作。其選擇情況如表5-10所表示。表5-10第2代種群選擇情況表

其中若假設(shè)按輪盤賭選擇時(shí)依次生成4個(gè)隨機(jī)數(shù)為0.42、0.15、0.59和0.91，經(jīng)選擇后得到新種群為：S21=11001S22=10010S23=11001S24=11110編號(hào)個(gè)體串（染色體）x適應(yīng)值百分比%累計(jì)百分比%選中次數(shù)S21100101832423.9223.921S22110012562522.1246.041S23110012562522.1268.161S24111103090031.8410015.3.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(9/10)74計(jì)算智能概述第74頁(yè)

對(duì)第2代種群，其交叉情況如表5-11所表示。

這時(shí)，函數(shù)最大值已經(jīng)出現(xiàn)，其對(duì)應(yīng)染色體為11111，經(jīng)解碼后可知問(wèn)題最優(yōu)解是在點(diǎn)x=31處。

求解過(guò)程結(jié)束。編號(hào)個(gè)體串（染色體）交叉對(duì)象交叉位子代適應(yīng)值S2111001S22311010676S2210010S21310001289S2311001S24411000576S2411110S234111119615.3.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(10/10)75計(jì)算智能概述第75頁(yè)5.4含糊計(jì)算美國(guó)加州大學(xué)扎德(Zadeh)教授于1965年提出含糊集合與含糊邏輯理論是含糊計(jì)算數(shù)學(xué)基礎(chǔ)。它主要用來(lái)處理現(xiàn)實(shí)世界中因含糊而引發(fā)不確定性。當(dāng)前，含糊理論已經(jīng)在推理、控制、決議等方面得到了非常廣泛應(yīng)用。本節(jié)主要討論含糊理論基礎(chǔ)，對(duì)于含糊推理將放到下一章討論。76計(jì)算智能概述第76頁(yè)

定義5.1設(shè)U是給定論域，是把任意u∈U映射為[0,1]上某個(gè)實(shí)值函數(shù)，即：U→[0,1]u→則稱為定義在U上一個(gè)隸屬函數(shù)，由（對(duì)全部）所組成集合F稱為U上一個(gè)含糊集，稱為u對(duì)F隸屬度。說(shuō)明：

①含糊集F完全是由隸屬函數(shù)來(lái)刻畫(huà)，把U中每一個(gè)元素u都映射為[0,1]上一個(gè)值。②值表示u隸屬于F程度，其值越大，表示u隸屬于F程度越高。當(dāng)僅取0和1時(shí)，含糊集F便退化為一個(gè)普通集合。5.4.1含糊集及其運(yùn)算1.含糊集定義(1/2)77計(jì)算智能概述第77頁(yè)例5.15

設(shè)論域U={20,30,40,50,60}給出是年紀(jì)，請(qǐng)確定一個(gè)刻畫(huà)含糊概念“年輕”含糊集F。解：因?yàn)楹怯闷潆`屬函數(shù)來(lái)刻畫(huà)，所以需要先求出描述含糊概念“青年”隸屬函數(shù)。假設(shè)對(duì)論域U中元素，其隸屬函數(shù)值分別為：

則可得到刻畫(huà)含糊概念“年輕”含糊集F={1,0.8,0.4,0.1,0}說(shuō)明其含義。5.4.1含糊集及其運(yùn)算1.含糊集定義(2/2)78計(jì)算智能概述第78頁(yè)(1)離散且為有限論域表示方法

設(shè)論域U={u1,u2,…,un}為離散論域，則其含糊集可表示為：F={,,…,}為了能夠表示出論域中元素與其隸屬度之間對(duì)應(yīng)關(guān)系，扎德引入了一個(gè)含糊集表示方式：先為論域中每個(gè)元素都標(biāo)上其隸屬度，然后再用“+”號(hào)把它們連接起來(lái)，即也可寫(xiě)成其中，為ui對(duì)F隸屬度；“/ui”不是相除關(guān)系，只是一個(gè)記號(hào)；“+”也不是算術(shù)意義上加，只是一個(gè)連接符號(hào)。

5.4.1含糊集及其運(yùn)算2.含糊集表示(1/3)79計(jì)算智能概述第79頁(yè)在這種表示方法中，當(dāng)某個(gè)ui對(duì)F隸屬度=0時(shí)，可省略不寫(xiě)。比如，前面例5.15含糊集F可表示為：F=1/20+0.8/30+0.6/40+0.2/50有時(shí)，含糊集也可寫(xiě)成以下兩種形式：其中，前一個(gè)稱為單點(diǎn)形式，后一個(gè)稱為序偶形式。5.4.1含糊集及其運(yùn)算2.含糊集表示(2/3)80計(jì)算智能概述第80頁(yè)

(2)