第7章智能最優(yōu)化算法隨著仿生學(xué)、遺傳學(xué)和人工智能科學(xué)的發(fā)展，從20世紀70年代以來，科學(xué)家相繼將遺傳學(xué)、神經(jīng)網(wǎng)絡(luò)科學(xué)的原理和方法應(yīng)用到最優(yōu)化領(lǐng)域，形成了一系列新的最優(yōu)化方法，如遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、蟻群算法等。

這些算法不需要構(gòu)造精確的數(shù)學(xué)搜索方向，不需要進行繁雜的一維搜索，而是通過大量簡單的信息傳播和演變方法，得到問題的最優(yōu)解。遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應(yīng)全局最優(yōu)化概率搜索算法。7.1遺傳算法7.1.1生物的遺傳與進化生物從其親代繼承特性或形狀的現(xiàn)象稱為遺傳；生物在其延續(xù)生存的過程中,逐漸適應(yīng)生存環(huán)境，使其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱進化。構(gòu)成生物的基本結(jié)構(gòu)和功能單元是細胞細胞中含有一種微小的絲狀化合物稱染色體染色體主要由一種叫做核糖核酸(簡稱DNA)的物質(zhì)構(gòu)成

DNA按一定規(guī)則排列的長連稱基因基因是遺傳的基本單位另外，在進行細胞復(fù)制時，也可能產(chǎn)生某些差錯，從而使DNA發(fā)生某種變異，產(chǎn)生新的染色體?？梢?，同源染色體之間的復(fù)制、交叉或變異會使基因或染色體發(fā)生各種各樣的變化，從而，使生物呈現(xiàn)新的性狀，產(chǎn)生新的物種。細胞在分裂時，遺傳物質(zhì)DNA通過復(fù)制轉(zhuǎn)移到新的細胞中，新細胞就繼承了舊細胞的基因。有性生殖生物在繁殖下一代時，兩個同源染色體之間通過交叉而重組，即在兩個染色體的某一相同位置處DNA被切斷，然后分別交叉組合形成兩個新的染色體。7.1.2基本遺傳算法可以看作由n

個遺傳基因組成的染色體，也稱個體。最簡單的等位基因由0和1這兩個整數(shù)組成，相應(yīng)的染色體或個體就是一個二進制符號串。在遺傳算法中，將設(shè)計變量用符號串表示。由m

個個體組成一個群體，記作這種編碼所形成的符號串稱個體的基因型，與之對應(yīng)的值稱個體的表現(xiàn)型。把其中每一個看作一個遺傳基因，它的所有可能的取值稱等位基因。（1）遺傳編碼遺傳算法的運行不直接對設(shè)計變量本身進行操作，而是對表示可行解的個體編碼進行選擇、交叉和變異等遺傳運算。在遺傳算法中把原問題的可行解轉(zhuǎn)化為個體符號串的方法稱編碼?，F(xiàn)有的編碼方法可以分為三類，它們是二進制編碼、浮點數(shù)編碼和符號編碼。二進制編碼所用的符號集是由0和1組成的二值符號集，

它所構(gòu)成的個體基因型是一個二進制符號串。符號串的長度與所要求的求解精度有關(guān)。假設(shè)某一參數(shù)的取值范圍是，若用長度為的二進制符號串來表示，總共能夠產(chǎn)生個編碼。編碼精度為（7-1）這里介紹常用的二進制編碼方法。假設(shè)某一個體的編碼是：(7-2)則對應(yīng)的解碼公式為(7-3)

就表示一個個體，稱個體的基因型，對應(yīng)的十進制數(shù)175就是個體的表現(xiàn)型，編碼精度為例如，對于變量若采用10位二進制編碼時，可代表個不同的個體。如

在研究生物的遺傳和進化現(xiàn)象時，生物學(xué)家使用適應(yīng)度這個術(shù)語來度量物種對生存環(huán)境的適應(yīng)程度。，一般由目標函數(shù)或懲罰函數(shù)（2）個體適應(yīng)度

在遺傳算法中使用適應(yīng)度這個概念來度量群體中個體的優(yōu)劣程度。適應(yīng)度較高的個體遺傳到下一代的概率較大，反之則較小。

度量個體適應(yīng)度的函數(shù)稱適應(yīng)度函數(shù)，一般由目標函數(shù)或懲罰函數(shù)轉(zhuǎn)換而來。以目標函數(shù)為例，常用的轉(zhuǎn)換關(guān)系如下：對于極大化問題：(7-4)式中為一適當小的正數(shù)。

對于極小化問題：(7-5)為一較大的正數(shù)。式中，

生物的進化是以集團為主體進行的。與此對應(yīng)，遺傳算法的運算對象也是由M個個體所組成的集合，稱群體。第t代群體記作P（t），遺傳算法的運算就是群體的反復(fù)演變過程。（3）遺傳運算遺傳算法將染色體中基因的復(fù)制、交叉和變異歸結(jié)為各自的運算規(guī)則或遺傳算子，并反復(fù)將這些遺傳算子作用于群體P（t），對其進行選擇、交叉和變異運算，以求得到最優(yōu)的個體，即問題的最優(yōu)解。生物的進化過程主要是通過染色體之間的復(fù)制、交叉和變異來完成的。1）選擇運算遺傳算法使用選擇算子來對群體中的個體進行優(yōu)勝劣汰操作。適應(yīng)度較高的個體有較大的概率遺傳到下一代。

設(shè)群體的大小為M，個體i

的適應(yīng)度為fi，則個體i被選中的概率Pis為：目前常用比例選擇運算。其基本的操作是：個體被選中并遺傳到下一代的概率與它的適應(yīng)度的大小成正比。每個概率值組成一個區(qū)間，全部概率值之和為1。2）交叉運算

交配重組是生物遺傳進化過程中的一個重要環(huán)節(jié)。模仿這一過程，遺傳算法使用交叉運算，即在兩個相互配對的個體間按某種方式交換其部分基因，從而形成兩個新生的個體。

運算前需對群體中的個體進行隨機配對，然后以不同的方式確定配對個體交叉點的位置，并在這些位置上進行部分基因的交換，形成不同的交叉運算方法。目前最常用的是單點交叉運算。

產(chǎn)生一個0到1之間的隨機數(shù)，依據(jù)概率值所出現(xiàn)的區(qū)間來決定對應(yīng)的個體被選中的次數(shù)，此法亦稱輪盤法。11000000010001010011父個體1父個體211000100010001000011子個體1子個體2交叉運算交叉點交叉點

單點交叉又稱簡單交叉，它是在個體編碼串中隨機地設(shè)置一個交叉點，并在該交叉點上相互交換兩個配對個體的基因，如下所示：3）變異運算

生物的遺傳和進化過程中，在細胞的分裂和復(fù)制環(huán)節(jié)上可能產(chǎn)生一些差錯，從而導(dǎo)致生物的某些基因發(fā)生某種變異，產(chǎn)生出新的染色體，表現(xiàn)出新的生物性狀。

模仿這一過程，遺傳算法采用變異運算，將個體編碼串中的某些基因座上的基因值用它的不同等位基因來替換，從而產(chǎn)生新的個體。

有很多變異運算方法，最簡單的是基本位變異。基本位變異操作是在個體編碼串中依變異概率Ps隨機指定某一位或某幾位基因座上的基因值作變異運算，如下所示：11000100011100011001變異運算編碼，構(gòu)成初始群體P(t)計算P(t)中各個體的適應(yīng)度圖7-1遺傳算法的運算流程圖給定T、置t=0t=t+1得到新的群體p(t+1)變異運算交叉運算選擇運算

Y取最大適應(yīng)度的個體解碼輸出終止遺傳算法的運算流程圖如下：

N例用遺傳算法求如下函數(shù)的全局最大值s.t.xi∈{1,2,…,7}(i=1,2)由此開始的遺傳算法求解過程如表所示。

解，由于變量的取值上限為7下限為0，故對和均采用3位二進制編碼。0.230.210.420.14(16)53509834適應(yīng)度f(x1,x2)(15)7,27,17,73,5變量x1,x2(14)子代群體P（1）(13)111010111001111111011101變異結(jié)果(12)6254變異點(11)111011101001111101011001交叉結(jié)果(10)54交叉點(9)3-41-2配對情況(8)111001101011111001011101選擇結(jié)果(7)2011選擇次數(shù)(6)0.350.170.240.24(5)50253434適應(yīng)度f(x1,x2)(4)

7,13,45,33,5變量x1,x2(3)111001011100101011011101初始群體P(0)(2)4321個體編號i(1)

需要說明的是，表中第②、⑦、⑨、⑩、12欄的數(shù)據(jù)是應(yīng)該隨機產(chǎn)生的，這里特意選擇了一些較好的數(shù)據(jù)以便盡快得到較好的結(jié)果。實際運算中一般需求經(jīng)過多次進化才能得到這樣的最優(yōu)結(jié)果。

從表中可以看出，群體經(jīng)過一代進化后，其適應(yīng)度的最大值和平均值都得到了明顯的改進。實際上已經(jīng)找到了最佳的個體“111111”以及對應(yīng)的最優(yōu)解：

X＝[7,7]T,f(X)=987.2神經(jīng)網(wǎng)絡(luò)算法7.2.1人工神經(jīng)元與神經(jīng)網(wǎng)絡(luò)人的大腦中有100多億個神經(jīng)細胞。一個神經(jīng)細胞主要由細胞體、樹突、軸突和突觸組成。

樹突伸向四方，其作用是收集四周神經(jīng)細胞的信息。

突觸是兩個神經(jīng)細胞之間起連接作用的部分。樹突將收集到的信息經(jīng)過軸突輸出，傳給其他細胞。突觸有興奮性和抑止性兩種狀態(tài)。興奮性突觸在脈沖的刺激下能使下一個神經(jīng)細胞產(chǎn)生興奮性膜電位，很多細胞通過各自的突觸對某一個神經(jīng)細胞發(fā)生作用，使其膜電位發(fā)生變化，當膜電位的累加值超過某一閾值時，就會使該細胞產(chǎn)生一個新的脈沖。

一個神經(jīng)細胞周圍大約有100~1000個其他細胞，神經(jīng)細胞的信息就是這樣從一個細胞傳遞給另外一個細胞的，從一個神經(jīng)網(wǎng)絡(luò)傳到另一個神經(jīng)網(wǎng)絡(luò)。

1943年，美國心理學(xué)家W.McCllochhe和數(shù)學(xué)家W.pitts根據(jù)生物神經(jīng)元的基本特性，提出MP神經(jīng)元模型，開創(chuàng)了人工神經(jīng)元研究的新紀元。MP神經(jīng)元模型如圖所示

圖7-2MP神經(jīng)元模型wj1x2xnwj2wjnθjf()ujyjx1

圖7-3MP模型的激活函數(shù)ujff(uj)1其符號的正負表示產(chǎn)生的作用是興奮性的或抑止性的，其數(shù)值的大小表達作用的強弱；表示神經(jīng)元的閾值（觸發(fā)值）

代表神經(jīng)元的總輸入，表示神經(jīng)元的狀態(tài)或輸出。

圖7-2MP神經(jīng)元模型wj1x2xnwj2wjnθjf()ujyjx1其中個神經(jīng)元對第個表示第神經(jīng)元的作用權(quán)值，

于是一個神經(jīng)元在某時刻的狀態(tài)或輸出可用下面的數(shù)學(xué)表達式加以描述（7-7）其中稱激活函數(shù)。

(7-8)時，神經(jīng)元的狀態(tài)是總輸入的雙值函數(shù)。

當激活函數(shù)取如圖7-3所示的符號函數(shù)

當小于零時，表示神經(jīng)元未被觸發(fā)，保持原來的狀態(tài)不變。

這與生物神經(jīng)細胞對信息的反應(yīng)和傳遞是一致的，因此它也成為人工神經(jīng)元及其所構(gòu)成的神經(jīng)網(wǎng)絡(luò)最基本的數(shù)學(xué)描述。

除符號函數(shù)之外，常用的激活函數(shù)還有如圖7-4所示的線性函數(shù)和S型函數(shù)等。

當大于零時，表示神經(jīng)元被觸發(fā)產(chǎn)生一個新的脈沖。（a）線性函數(shù)0ua1-ua-1yjuj圖7-4激活函數(shù)(b)S型函數(shù)

01-1yjuj

目前提出的人工神經(jīng)網(wǎng)絡(luò)模型已有40多種按網(wǎng)絡(luò)結(jié)構(gòu)分為前饋型和反饋型；按網(wǎng)絡(luò)性能分為連續(xù)型、離散型、確定型和隨機型；按學(xué)習(xí)方式分為有導(dǎo)師型和無導(dǎo)師型；按突觸連接性質(zhì)分為一階線性型和高階非線性型等。

人工神經(jīng)網(wǎng)絡(luò)是將上述人工神經(jīng)元以某種方式組合起來的網(wǎng)絡(luò)結(jié)構(gòu)。

人工神經(jīng)網(wǎng)絡(luò)通過某種學(xué)習(xí)（訓(xùn)練）方法模擬生物體中神經(jīng)網(wǎng)絡(luò)的某些結(jié)構(gòu)與功能，從而用以解決不同的工程實際問題。

目前常用的BP網(wǎng)絡(luò)和RBF網(wǎng)絡(luò)屬前饋型神經(jīng)網(wǎng)絡(luò)，Hopfield網(wǎng)絡(luò)屬反饋型網(wǎng)絡(luò)。

BP網(wǎng)絡(luò)由多個輸入結(jié)點、多個隱含層和一個輸出層組成。每層包含多個神經(jīng)元（結(jié)點）。前后層之間實現(xiàn)全連接，層內(nèi)各結(jié)點之間無連接。

7.2.2BP網(wǎng)絡(luò)

BP網(wǎng)絡(luò)是一種輸入信號前向傳播、誤差信號反向傳播的多層前饋型網(wǎng)絡(luò)。（1）BP網(wǎng)絡(luò)結(jié)構(gòu)BP網(wǎng)絡(luò)中，隱含層神經(jīng)元的激活函數(shù)一般采用Sigmoid型的對數(shù)函數(shù)或正切函數(shù)，輸出層神經(jīng)元通常采用線性激活函數(shù)。圖7-5所示為單隱層BP網(wǎng)絡(luò)的結(jié)。(a)結(jié)構(gòu)圖隱層（n個神經(jīng)元）輸出層（m個神經(jīng)元）x1x2x3xn1w111w1n,n1w1n,3u1unu2v1v2vnh1h2hny1y2ynw112w2m,nw211圖7-5單隱層BP網(wǎng)絡(luò)輸入W1W2隱含層輸出層

線性激活函數(shù)S型激活函數(shù)

(b)結(jié)構(gòu)簡圖Xn1×1n×1n×1uyvhm×1m×nn×1n×n1m×1(c)網(wǎng)絡(luò)結(jié)構(gòu)示意圖

XW1JHLYW2網(wǎng)絡(luò)中隱含層和輸出層神經(jīng)元的輸出為

(7-9)若將神經(jīng)元的閾值也視為一個連接權(quán)值，即令

則上式可寫成如下形式

（7-10）（2