【正文】 度函數(shù) 在遺傳算法中，有許多計(jì)算適應(yīng)度的方法，其中最常用的適應(yīng)度函數(shù)有以下兩種： ① 原始適應(yīng)度函數(shù) 它是直接將待求解問題的目標(biāo)函數(shù) f(x)定義為遺傳算法的適應(yīng)度函數(shù)。 遺傳算法 3. 遺傳編碼 (3/3) 50 適應(yīng)度函數(shù)是一個(gè)用于對(duì)個(gè)體的適應(yīng)性進(jìn)行度量的函數(shù)。由于實(shí)數(shù)編碼使用的是變量的真實(shí)值，因此這種編碼方法也叫做真值編碼方法。 ???????? 111 ibbibaiiii ???ijii ab1)2(mod49 (3) 實(shí)數(shù)編碼（ Real encoding） 實(shí)數(shù)編碼是將每個(gè)個(gè)體的染色體都用某一范圍的一個(gè)實(shí)數(shù)（浮點(diǎn)數(shù)）來表示，其編碼長(zhǎng)度等于該問題變量的個(gè)數(shù)。它有效地解決了漢明懸崖問題，其基本原理如下： 設(shè)有二進(jìn)制串 b1,b2,…,b n，對(duì)應(yīng)的格雷串為 a1,a2,…,a n，則從二進(jìn)制編碼到格雷編碼的變換為： () 其中， ⊕ 表示模 2加法。 遺傳算法 3. 遺傳編碼 (1/3) 48 遺傳算法 3. 遺傳編碼 (2/3) (2) 格雷編碼（ Gray encoding） 格雷編碼是對(duì)二進(jìn)制編碼進(jìn)行變換后所得到的一種編碼方法。 二進(jìn)制編碼存在的主要缺點(diǎn) 是漢明（ Hamming）懸崖。 例 假設(shè)變量 x的定義域?yàn)?[5， 10]，要求的計(jì)算精度為 105，則需要將 [5，10]至少分為 600000個(gè)等長(zhǎng)小區(qū)間，每個(gè)小區(qū)間用一個(gè)二進(jìn)制串表示。 (1)二進(jìn)制編碼（ Binary encoding） 二進(jìn)制編碼是將原問題的結(jié)構(gòu)變換為染色體的位串結(jié)構(gòu)。 遺傳算法 2. 遺傳算法的基本過程 (1/2) 46 計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度 ， 并進(jìn)行評(píng)價(jià) 滿足終止條件嗎 ？ 終止 選擇 交叉 變異 Y 圖 418 基本遺傳算法的算法流程圖 編碼和生成初始種群 N 選擇 其算法流程如圖 418所示。其函數(shù)值是遺傳算法實(shí)現(xiàn)優(yōu)勝劣汰的主要依據(jù) 遺傳操作 （ Geic Operator）：遺傳操作是指作用于種群而產(chǎn)生新的種群的操作。染色體中的每 1位稱為基因，染色體上由若干個(gè)基因構(gòu)成的一個(gè)有效信息段稱為基因組。例如，可以用 0、 1組成的長(zhǎng)度為 l的串來表示個(gè)體。遺傳算法的求解過程是從這個(gè)子集開始的。 進(jìn)化計(jì)算概述 3. 進(jìn)化計(jì)算的基本結(jié)構(gòu) 44 遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個(gè)體，并通過雜交、變異來產(chǎn)生新一代種群，如此逐代進(jìn)化，直到滿足目標(biāo)為止。 對(duì)初始種群進(jìn)行評(píng)價(jià)（即適應(yīng)度計(jì)算）； while（不滿足終止條件） do { t=t+1。 進(jìn)化計(jì)算概述 2. 進(jìn)化計(jì)算的產(chǎn)生與發(fā)展 (2/2) 43 進(jìn)化計(jì)算盡管有多個(gè)重要分支，并且不同分支的編碼方案、選擇策略和進(jìn)化操作也有可能不同，但它們卻有著共同的進(jìn)化框架。 進(jìn)入 20世紀(jì) 90年代以來，進(jìn)化計(jì)算得到了眾多研究機(jī)構(gòu)和學(xué)者的高度重視，新的研究成果不斷出現(xiàn)、應(yīng)用領(lǐng)域不斷擴(kuò)大。 進(jìn)化計(jì)算概述 2. 進(jìn)化計(jì)算的產(chǎn)生與發(fā)展 (1/2) 42 (3) 發(fā)展階段 這一階段是從 20世紀(jì) 90年代至今。同年，德國學(xué)者施韋費(fèi)爾（ Schwefel）在其博士論文中提出了一種由多個(gè)個(gè)體組成的群體參與進(jìn)化的，并且包括了變異和重組這兩種進(jìn)化操作的進(jìn)化策略。 (2) 成長(zhǎng)階段 這一階段是從 20世紀(jì) 70年代中期到 80年代后期。 1969年美國密執(zhí)安（ Michigan）大學(xué)的霍蘭德（ Holland）提出了系統(tǒng)本身和外部環(huán)境相互協(xié)調(diào)的遺傳算法。 1965年德國數(shù)學(xué)家雷切伯格（ Rechenberg）等人提出了一種只有單個(gè)個(gè)體參與進(jìn)化，并且僅有變異這一種進(jìn)化操作的 進(jìn)化策略 。 (1) 萌芽階段 這一階段是從 20世紀(jì) 50年代后期到 70年代中期。通過這種自然選擇，物種將逐漸向適應(yīng)于生存環(huán)境的方向進(jìn)化，甚至?xí)葑兂蔀榱硪粋€(gè)新的物種，而那些不適應(yīng)于環(huán)境的物種將會(huì)逐漸被淘汰。這種新基因?qū)⒁罁?jù)其與生存環(huán)境的適應(yīng)性而決定其增殖能力。遺傳和變異是生物進(jìn)化的兩種基本現(xiàn)象，優(yōu)勝劣汰、適者生存是生物進(jìn)化的基本規(guī)律。 復(fù)制差錯(cuò)， 是指在細(xì)胞復(fù)制過程中因 DNA上某些基因結(jié)構(gòu)的隨機(jī)改變而產(chǎn)生出新的染色體。變異是一種隨機(jī)、不可逆現(xiàn)象，是生物多樣性的基礎(chǔ)。 細(xì)胞在分裂過程中，其遺傳物質(zhì) DNA通過復(fù)制轉(zhuǎn)移到新生細(xì)胞中，從而實(shí)現(xiàn)了生物的遺傳功能。 染色體的形狀是一種雙螺旋結(jié)構(gòu)，構(gòu)成染色體的主要物質(zhì)叫做 脫氧核糖核酸 (DNA)，每個(gè)基因都在 DNA長(zhǎng)鏈中占有一定的位置。 細(xì)胞中含有一種包含著所有遺傳信息的復(fù)雜而又微小的絲狀化合物，人們稱其為 染色體 （ Chromosome）。正是由于遺傳的作用，自然界才能有穩(wěn)定的物種。 進(jìn)化計(jì)算概述 1. 進(jìn)化計(jì)算及其生物學(xué)基礎(chǔ) (1/3) (1) 什么是進(jìn)化計(jì)算 39 (2) 進(jìn)化計(jì)算的生物學(xué)基礎(chǔ) 自然界生物進(jìn)化過程是進(jìn)化計(jì)算的生物學(xué)基礎(chǔ)，它主要包括遺傳(Heredity)、變異 (Mutation)和進(jìn)化 (Evolution)理論。 進(jìn)化計(jì)算 38 進(jìn)化計(jì)算是一種模擬自然界生物進(jìn)化過程與機(jī)制進(jìn)行問題求解的自組織、自適應(yīng)的隨機(jī)搜索技術(shù)。 其中，第一個(gè)分支是進(jìn)化計(jì)算中最初形成的一種具有普遍影響的模擬進(jìn)化優(yōu)化算法。 35 圖 417 離散 Hopfield網(wǎng)絡(luò)的結(jié)構(gòu) ym Y2 Y1 x1 … … x2 xn 輸入層 輸出層 在 Hopfidld網(wǎng)絡(luò)中，雖然神經(jīng)元自身無連接，但由于每個(gè)神經(jīng)元都與其他神經(jīng)元相連，即每個(gè)神經(jīng)元的輸出都將通過突觸連接權(quán)值傳遞給別的神經(jīng)元，同時(shí)每個(gè)神經(jīng)元又都接受其他神經(jīng)元傳來的信息，這樣對(duì)每個(gè)神經(jīng)元來說，其輸出經(jīng)過其他神經(jīng)元后又有可能反饋給自己，因此 Hopfidld網(wǎng)絡(luò)是一種反饋神經(jīng)網(wǎng)絡(luò) 3. Hopfield網(wǎng)絡(luò)模型 離散 Hopfield網(wǎng)絡(luò)模型 (2/2) 36 概述 神經(jīng)計(jì)算 進(jìn)化計(jì)算 進(jìn)化計(jì)算概述 遺傳算法 模糊計(jì)算 粗糙集 第 4章 計(jì)算智能 37 進(jìn)化計(jì)算（ Evolutionary Computation,EC）是在達(dá)爾文（ Darwin）的進(jìn)化論和孟德爾（ Mendel）的遺傳變異理論的基礎(chǔ)上產(chǎn)生的一種在基因和種群層次上模擬自然界生物進(jìn)化過程與機(jī)制的問題求解技術(shù)。離散 Hopfield網(wǎng)絡(luò)模型是一個(gè)離散時(shí)間系統(tǒng)，每個(gè)神經(jīng)元只有 0和 1（或 1和 1）兩種狀態(tài)，任意神經(jīng)元i和 j之間的連接權(quán)值為 wij。 離散 Hopfield網(wǎng)絡(luò)的結(jié)構(gòu) 離散 Hopfield網(wǎng)絡(luò)是在非線性動(dòng)力學(xué)的基礎(chǔ)上由若干基本神經(jīng)元構(gòu)成的一種單層全互連網(wǎng)絡(luò)，其任意神經(jīng)元之間均有連接，并且是一種對(duì)稱連接結(jié)構(gòu)。 34 Hopfield網(wǎng)絡(luò)是由美國加州工學(xué)院物理學(xué)家霍普菲爾特 1982年提出來的一種單層全互連的對(duì)稱反饋網(wǎng)絡(luò)模型。 y1 y2 ym x1 x2 xn 輸出層 隱含層 輸入層 權(quán)可調(diào) 權(quán)可調(diào) … … … 圖 一個(gè)多層 BP網(wǎng)絡(luò)的結(jié)構(gòu) 2. BP網(wǎng)絡(luò)模型 模型結(jié)構(gòu) 33 對(duì) BP網(wǎng)絡(luò)需說明以下兩點(diǎn)： 第一， BP網(wǎng)絡(luò)的每個(gè)處理單元均為非線性輸入 /輸出關(guān)系，其作用函數(shù)通常采用的是可微的 Sigmoid函數(shù)，如： xexf ??? 11)(2. BP網(wǎng)絡(luò)模型 模型說明 第二， BP網(wǎng)絡(luò)的學(xué)習(xí)過程是由工作信號(hào)的正向傳播和誤差信號(hào)的反向傳播組成的。在 BP網(wǎng)絡(luò)中，同層節(jié)點(diǎn)之間不存在相互連接，層與層之間多采用全互連方式，且各層的連接權(quán)值可調(diào)。 1. 感知器模型 多層 感知器 (2/2) 32 誤差反向傳播 (Error Back Propagation)網(wǎng)絡(luò)通常簡(jiǎn)稱為 BP(Back Propagation)網(wǎng)絡(luò)，是由美國加州大學(xué)的魯梅爾哈特和麥克萊蘭在研究并行分布式信息處理方法，探索人類認(rèn)知微結(jié)構(gòu)的過程中，于 1985年提出的一種網(wǎng)絡(luò)模型。隱層神經(jīng)元 x12所確定的直線方程為 它也可以識(shí)別一個(gè)半平面。例如，對(duì)“異或”運(yùn)算，用圖 所示的多層感知器即可解決。 多層感知器的輸入與輸出之間是一種高度非線性的映射關(guān)系，如圖，若采用多層感知器模型，則該網(wǎng)絡(luò)就是一個(gè)從 n維歐氏空間到 m維歐氏空間的非線性映射。 (0,1) (0,0) (1,0) 圖 異或運(yùn)算問題圖示 (1,1) 1. 感知器模型 單層感知器 (77) 30 (2) 多層感知器 多層感知器是通過在單層感知器的輸入、輸出層之間加入一層或多層處理單元所構(gòu)成的。 圖 非運(yùn)算問題圖示 0 1 1. 感知器模型 單層感知器 (6/7) 29 例 “異或”運(yùn)算（ x1 XOR x2） 輸入 輸出 超平面 閾值條件 x1 x2 x1 XOR x2 w1*x1+ w2* x2θ=0 0 0 0 w1*0+ w2*0 θ＜ 0 θ＞ 0 0 1 1 w1*0+ w2*1 θ≥0 θ≤w2 1 0 1 w1*1+ w2*0 θ≥0 θ≤w1 1 1 0 w1*1+ w2*1θ0 θw1+ w2 此表無解，即無法找到滿足條件的 w w2和 θ，如右圖所示。x 1） 輸入 輸出 超平面 閾值條件 x1 172。 1. 感知器模型 單層感知器 (4/7) 27 例 “或”運(yùn)算（ x1∨ x2） 輸入 輸出 超平面 閾值條件 x1 x2 x1∨ x2 w1*x1+ w2* x2θ=0 0 0 0 w1*0+ w2*0 θ＜ 0 θ＞ 0 0 1 1 w1*0+ w2*1 θ≥0 θ≤w2 1 0 1 w1*1+ w2*0 θ≥0 θ≤w1 1 1 1 w1*1+ w2*1θ≥0 θ≤w1+ w2 此表也有解，例如取 w1=1， w2=1，θ=，其分類結(jié)果如右圖所示。 其中，輸出為 1的用實(shí)心圓，輸出為 0的用空心圓。事實(shí)上，單層感知器可以很好地實(shí)現(xiàn)“與”、“或”、“非”運(yùn)算，但卻不能解決“異或”問題。 羅森勃拉特已經(jīng)證明，如果外部輸入是線性可分的（指存在一個(gè)超平面可以將它們分開），則單層感知器一定能夠把它劃分為兩類。 1. 感知器模型 單層 感知器 (1/7) 24 單層感知器的結(jié)構(gòu)如下圖 … x1 x2 xn … y1 ym 輸入層 輸出層 權(quán)值 wij 輸入向量為 X=(x1,x2,…,x n)； 輸出向量為 Y=(y1,y2,…,y m)； 輸入層各個(gè)輸入到相應(yīng)神經(jīng)元的連接權(quán)值分別是 wij， i=1,2,..,n， j=1,2,.., m。當(dāng)輸入信息的加權(quán)和大于或等于閾值時(shí)，輸出為 1，否則輸出為 0或 1。 單層感知器 是一種只具有單層可調(diào)節(jié)連接權(quán)值神經(jīng)元的前向網(wǎng)絡(luò)，這些神經(jīng)元構(gòu)成了單層感知器的輸出層，是感知器的可計(jì)算節(jié)點(diǎn)。 重點(diǎn)討論 1. 感知器（ Perceptron）模型 2. 反向傳播（ BP）模型 3. 反饋網(wǎng)絡(luò)（ Hopfield）模型 人工神經(jīng)網(wǎng)絡(luò)的典型模型 23 感知器 是美國學(xué)者羅森勃拉特（ Rosenblatt）于 1957年為研究大腦的存儲(chǔ)、學(xué)習(xí)和認(rèn)知過程而提出的一類具有自學(xué)習(xí)能力的神經(jīng)網(wǎng)絡(luò)模型，其拓?fù)浣Y(jié)構(gòu)是一種分層前向網(wǎng)絡(luò)。常用的網(wǎng)絡(luò)模型已有數(shù)十種。 反饋網(wǎng)絡(luò) 則不同，它的每個(gè)神經(jīng)元的輸入都有可能包含有該神經(jīng)元先前輸出的反饋信息，即一個(gè)神經(jīng)元的輸出是由該神經(jīng)元當(dāng)前的輸入和先前的輸出這兩者來決定的，這就有點(diǎn)類似于人類的短期記憶的性質(zhì)。所謂反饋聯(lián)結(jié)方式是指一個(gè)神經(jīng)元的輸出可以被反饋至同層或前層的神經(jīng)元。 多層前饋網(wǎng)絡(luò)的典型代表是 BP網(wǎng)絡(luò)。隱含層的作用是通過對(duì)輸入層信號(hào)的加權(quán)處理，將其轉(zhuǎn)移成更能被輸出層接受的形式。 20 多層前饋網(wǎng)絡(luò) 是指那種除擁有輸入、輸出層外，還至少含有一個(gè)、或更多個(gè)隱含層的