最優(yōu)化方法及應(yīng)用郭科現(xiàn)代優(yōu)化算法簡介

第九章現(xiàn)代優(yōu)化算法簡介遺傳算法、模擬退火算法、禁忌算法、人工神經(jīng)網(wǎng)絡(luò)統(tǒng)稱20世紀(jì)80年代初產(chǎn)生的現(xiàn)代優(yōu)化算法．它主要解決優(yōu)化問題中的難解的問題，下面分別介紹遺傳算法、模擬退火算法、禁忌算法、人工神經(jīng)網(wǎng)絡(luò)．§9.1模擬退火算法一、模擬退火算法基本原理

模擬退火算法（SimalatedAnnealing，簡稱SA）屬于一種通用的隨機探索算法，1953年N.Metropolis等人提出了模擬退火算法，其基本思想是把某類優(yōu)化問題的求解過程與統(tǒng)計熱力學(xué)中的熱平衡問題進行對比試圖通過模擬高溫物體退火過程，來找到優(yōu)化問題的全局最優(yōu)解或近似全局最優(yōu)解．

一個物體（如金屬）的退火過程大體如下：首先對該物體高溫加熱（熔化），顯然物體內(nèi)原子處于高速運行的高能狀態(tài)．然而作為一個實際的物理系統(tǒng)，原子的運動又總是趨于最低的能量狀態(tài)，在退火的初始狀態(tài)，由于溫度較高，物體處于高能狀態(tài)，隨著溫度的逐漸降低，物體內(nèi)部原子運動化學(xué)能趨于低能狀態(tài)，這種由高能向低能逐漸降溫的過程稱為退火．當(dāng)溫度降至結(jié)晶溫度后，物體由原子運動變?yōu)閲@晶體格點的微小振動，液體凝固成固體，退火過程結(jié)束．對于一個優(yōu)化問題當(dāng)我們把目標(biāo)函數(shù)看成定義在可行集（解空間）上的能量曲面，而整個曲面凹凸不平，如果讓一個光滑圓球在曲面上自由滾動，這個圓球十有八九會滾到最近的凹處停止運動，但該低谷并不一定是最深的一個凹谷，模擬退火方法就類似于沿水平方向給圓球一個水平方向作用力，若作用于小球的作用力足夠大且小球所處的低谷并不很深．小球受水平力作用會從該低谷流出，落入另一低谷，然后受水平力作用又滾出，如此不斷滾動，如果作用小球的水平力掌握得適當(dāng)，小球很有可能停留在最深的低谷之中，這個最深低谷就是優(yōu)化問題的全局最優(yōu)解或接近于全局最優(yōu)解．作用于小球上的水平力相應(yīng)于模擬退火中的溫度T，水平作用力減小相應(yīng)于溫度降低，如圖9.1所示．圖9.1二、模擬退火算法基本迭代步驟(1)給定初始溫度及初始點X，計算該點的函數(shù)值．(2)隨機產(chǎn)生擾動得新點計算新點函數(shù)值及函數(shù)值差(3)若，則接受新點，作為下一次模擬的初始點．(4)若則計算新點接受概率，在區(qū)間[0,1]上產(chǎn)生服從均勻分布的偽隨機數(shù)．如果有，則接受新點作為下一次模擬的初始點；否則放棄新點，仍取原來的點作為下一次模擬的初始點．以上步驟，稱為Metropolis過程．按照一定的退火方案逐漸降低溫度，重復(fù)Metropolis過程，就構(gòu)成模擬退火迭代法．當(dāng)系統(tǒng)的溫度足夠低時，就認(rèn)為達到了全局最優(yōu)解．在模擬退火算法中，降溫的方式對算法有很大的影響．如果溫度下降過快，可能會丟失極值點，如果溫度下降過慢，算法的收斂速度又大大降低，為了提高模擬退火算法的有效性，許多學(xué)者提出了多種退火方案，如

(1)經(jīng)典退火方案：降溫公式為，特點是溫度下降很緩慢，因此，算法收斂程度很慢．

(2)快速退火方式：降溫公式為，特點是在高溫區(qū)溫度下降比較快，而在低溫區(qū)降溫的速度較慢．這符合熱力學(xué)分子運動理論，即分子在高溫時，具有較低能量的概率要比在低溫時小得多，因此尋優(yōu)的重點應(yīng)在低溫區(qū)，其中參數(shù)可以改善退火曲線的形態(tài)．三、模擬退火馬氏鏈模型令為所有狀態(tài)構(gòu)成的解空間，又令由所可得隨機序列若隨機序列滿足下式

則模擬退火狀態(tài)序列為馬氏鏈．馬氏鏈?zhǔn)且粋€時間離散，狀態(tài)離散的時間序列，其特點是具有無后效應(yīng)．馬氏鏈從某一時刻的某一狀態(tài)變?yōu)榱硪粫r刻的另一狀態(tài)稱為狀態(tài)的轉(zhuǎn)移，而從當(dāng)前狀態(tài)經(jīng)一次轉(zhuǎn)移到下個狀態(tài)的可能性稱為一步轉(zhuǎn)移概率，可記為

.

從當(dāng)前轉(zhuǎn)態(tài)經(jīng)n步轉(zhuǎn)移到下一狀態(tài)的概率，可記為．若解空間有限，馬氏鏈稱為有限狀態(tài)馬氏鏈，若，馬氏鏈稱為時齊的．以下討論的模擬退火算法算法為有限狀態(tài)馬氏鏈．

由前述模擬退火算法的迭代過程可知，算法是從一個初始狀態(tài)開始后，前一步狀態(tài)轉(zhuǎn)移均是在當(dāng)前狀態(tài)i的鄰域中隨機產(chǎn)生新狀態(tài)j，然后以一定概率進行接受．可見接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制．因此模擬退火算法算法顯然對應(yīng)一個馬氏鏈．若固定每一溫度T，算法均計算馬氏鏈的變化直系平穩(wěn)分布，然后下降溫度，稱這種算法為時齊算法．若無需各溫度下算法均達到平穩(wěn)分布，但溫度需按一定的速度下降，稱這料算法為非時齊或非平穩(wěn)馬氏鏈算法．馬氏鏈可用一個有的圖表示，其中，V為所有狀態(tài)構(gòu)成的頂點集，為邊集，其中是以頂點i為起點的有向線段的終點集合．記為由狀態(tài)i產(chǎn)生j概率，則其中，．通常與溫度無關(guān)．若新狀態(tài)在當(dāng)前狀態(tài)的鄰域中以等同概率產(chǎn)生，則，

其中為狀態(tài)的i鄰域中狀態(tài)總數(shù)．記為由當(dāng)前狀態(tài)i接受狀態(tài)j的概率，接受概率通常定義為.

其中為目標(biāo)函數(shù)，T為溫度參數(shù)．記為由狀態(tài)i到狀態(tài)j的轉(zhuǎn)移概率，則模擬退火馬氏鏈模型為綜上所述，模擬退火算法要實現(xiàn)全局收斂必須滿足如下三個條件：（1）狀態(tài)可達性，即無論起點如何，任何一個狀態(tài)都可以到達，由此有求得最優(yōu)解可能．（2）初值魯棒性，即算法的最終結(jié)果不依賴初值．（3）極限分布的存在性，即包含兩個方面內(nèi)容：一是當(dāng)溫度不變時，其馬氏鏈的極限分布存在；二是當(dāng)溫度漸近0時，其馬氏鏈也有極限分布．四、模擬退火算法的有關(guān)說明（關(guān)鍵參數(shù)調(diào)控）在模擬退火算法執(zhí)行過程中，算法效果取決于一組控制參數(shù)的選擇，關(guān)鍵參數(shù)的控制對算法性能影響很大．模擬退火算法的關(guān)鍵參數(shù)，包括初始溫度，溫度下降方法，每一溫度迭氏長度，終止準(zhǔn)則．

(1)初始溫度的控制模擬退火算法初始溫度控制直接影響算法的全局收斂性．初始溫度高、算法易搜索到全局最優(yōu)解，但計算速度慢，時間長；反之，速度快，時間短，但易收斂于局部最優(yōu)解．在工程實踐中，初始溫度的選擇一般要根據(jù)大量實驗結(jié)果分析來確定．實用中，一般取初始溫度的一個估計值為，其中，為足夠大的正數(shù)，的取值可按簡單估計．

(2)溫度下降方法的控制溫度控制是模擬退火算法中很難處理的問題．在鄰域探索過程中，當(dāng)解的質(zhì)量變差概率呈Boltzmann分布時，理論證明溫度下降控制可用公式

(9.1)

來收斂于全局最優(yōu)解，其中，K為正的常數(shù)．為降溫次數(shù)．在鄰域探索過程中，當(dāng)解的質(zhì)量變差概率呈Cauchy分布時，理論證明，溫度下降控制可用公式來收斂于全局最優(yōu)解，其中，K及k含義同式(9.1)相同．實際應(yīng)用中，分二種方式控制溫度下降：①每一步溫度以相同比率下降，即,

其中,，，為降溫系數(shù)．②每一步溫度以相同長度下降，即，其中，為初始溫度，為溫度下降的總次數(shù)．(3)每一溫度迭代長度的控制模擬退火算法的全局搜索性與每一溫度的迭代長度密切相關(guān)．一般地，同一溫度下的充分搜索是必要的，但需以計算時間增加為代價．實際應(yīng)用中常根據(jù)問題的特點設(shè)置合理的迭代長度，常用二種方法：①固定的迭代步數(shù)，即在每一溫度都設(shè)置相同的迭代步數(shù)，步數(shù)的選取通常采用與鄰域大小直接相關(guān)的規(guī)則．②根據(jù)接近和拒絕概率控制迭代步數(shù)．高溫時，各狀態(tài)被接受的概率基本相同，且?guī)缀跛袪顟B(tài)都被接受，可使同一溫度的迭代步數(shù)盡量少些；溫度逐漸變低后，越來越多的狀態(tài)被拒絕，則可相應(yīng)增大迭代步數(shù)．因此，可以采用，給定一個迭代步數(shù)，實現(xiàn)S和一個接受次數(shù)上限R，當(dāng)某一溫度的實際接受次數(shù)等于R時，不再迭代使溫度下降，否則繼續(xù)迭代到上限步數(shù)S．(4)終止準(zhǔn)則模擬退火算法的終止準(zhǔn)則，實際應(yīng)用中主要采用如下3種準(zhǔn)則．①零度終止準(zhǔn)則，即給定一個比較小的正數(shù)，當(dāng)溫度時，算法終止，表示達到最低溫度．②循環(huán)總數(shù)終止準(zhǔn)則，即設(shè)定溫度下降的總次數(shù)為T，當(dāng)溫度迭代次數(shù)達到T時，算法終止，．③接受概率終止準(zhǔn)則，即模擬退火的基本思想是有效擺脫局部最優(yōu)解．如果在溫度較高時，未能擺脫局部最優(yōu)解，則在溫度較低時擺脫局部最優(yōu)解的可能性更低．

因此可給定一個比較小的概率P，在一個溫度和給定的迭代步數(shù)內(nèi)，除當(dāng)前局部最優(yōu)解外，如果其它狀態(tài)的接受概率都小于P時，算法終止．

(5)模擬退火算法存在的不足由模擬退火算法的形成思想知，模擬退火算法是在一系列遞減溫度下產(chǎn)生的序列，該序列可看作為馬氏鏈，若按照一定的條件產(chǎn)生無限長的馬氏鏈，模擬退火算法從理論上講可以保證以概率收斂于全局最優(yōu)解．這是因為，在某一溫度下，只要計算時間足夠長，也就是馬氏鏈足夠長，其初始點的函數(shù)值將以很高的概率低于終止點的函數(shù)值，由此求得全局最優(yōu)解．然而，模擬退火算法要求計算時間足夠長．馬氏鏈長度無限，又導(dǎo)致模擬退火算法很難保證收斂到全局最優(yōu)，其次在每一溫度下，很難判定是否達到了平衡態(tài)，即馬氏鏈長度不易控制，具體反映到算法上，就是Metropolis過程的次數(shù)不易控制．§9.2遺傳算法一、遺傳算法基本原理

遺傳算法（GeneticAlgorithm，簡稱GA）是由美國Michigan大學(xué)的Holland教授于1975年首次提出，它的基本思想是基于Darwin的進化論和Mendel的遺傳學(xué)．即生物的遺傳，變異、選擇在生物的進化過程起著重要作用，它使生物不僅能夠保持自身固有特性，同時還能夠不斷改變自身以適應(yīng)新的生存環(huán)境．遺傳算法是一種基于群體進化的計算模型，它通過群體的個體之間繁殖、變異、競爭等方法進行的信息交換優(yōu)勝劣汰，從而一步步地逼近問題最優(yōu)解．對個體的遺傳操作主要是通過選擇（繁殖）交叉和變異（突變）這三個基本的遺傳算子來實現(xiàn)．生物的進貨是以群體的形式進行的，而群體的進化是通過個體的信息遺傳與交叉來完成的．與之對應(yīng)，遺傳算法的運算對象也是群體，它由N個個體組成一個集合，通過對該集合進行遺傳操作來模擬生物的進化過程，遺傳算法中的個體就是模擬生物的染色體，稱為人工染色體．為了完成對個體的遺傳操作，需要將個體的表現(xiàn)型轉(zhuǎn)換為基因型，這一個過程稱為編碼，反之，將基因型轉(zhuǎn)換為表現(xiàn)型的過程稱為解碼．二、遺傳算法的基本迭代步驟基本遺傳算法可用于解決求一般參數(shù)優(yōu)化問題的全局最優(yōu)解，即求

其尋優(yōu)過程如下：

(1)編碼對優(yōu)化問題解空間可行解（個體）進行編碼，也就是要將解空間的設(shè)計變量轉(zhuǎn)換為遺傳算法中的基因型數(shù)據(jù)結(jié)構(gòu)，通常用一個固定長度的二進制位串來進行編碼，形成遺傳算法中的染色體，這種編碼方式簡單，易于計算機上編程實現(xiàn)．在進行二進制編碼時，首先要確定二進制編碼串的長度l，串長l的長度依賴于變量的定義域以及問題所要求的精度，例如，若變量的定義域為[0，10]，而問題的精度要求為10-6，則要求確定編碼串l的長度為，首先要把[0，10]分割成10,000000個等長區(qū)間，而在每個區(qū)間范圍內(nèi)采用一個二進制編碼表示，這樣要能夠完全表示10,000000個區(qū)間范圍內(nèi)的所有個體，則是至少需要編碼串長度l為24．這樣對應(yīng)于[0，10]區(qū)域精度范圍內(nèi)的每個值都可用一個24位編碼串個體來表示，其轉(zhuǎn)換過程如下

當(dāng)優(yōu)化問題屬于多維優(yōu)化問題時，可先對各個變量分別進行編碼，然后將它們合并成一個長串．在解碼時，再對各個變量分別進行解碼即可．例9.1用一個5位的二進制串表示染色體．解一般對于一個n位二進制數(shù)，可以表示的狀態(tài)有個，5位的二進制串，則可以表示的染色體數(shù)為，下面是32個染色體及其編碼表示：

染色體1 11111

染色體2 11110┇

染色體31 00001

染色體32 00000遺傳算法中的染色體與優(yōu)化問題的解對應(yīng)，一個染色體對應(yīng)優(yōu)化問題的一個解，對染色體的遺傳操作就是對優(yōu)化問題解空間解的搜索．

(2)產(chǎn)生初始群體由于遺傳算法是對群體的反復(fù)操作，因此需要建立一個初始迭代的群體．群體的大小視具體問題而定，較小的優(yōu)化問題個體可以選擇10~20個，復(fù)雜一些的問題則需要50~100個．初始群體的每個個體都是通過隨機方法產(chǎn)生的，初始群體稱為進化第一代．

(3)構(gòu)造評價函數(shù)（適應(yīng)度）在遺傳算法中，通常將優(yōu)化問題的目標(biāo)函數(shù)進行適當(dāng)?shù)淖兓?，作為遺傳算法的評價函數(shù)，或稱為適應(yīng)度．群體在進化過程中，通過適應(yīng)度來評價個體的優(yōu)劣，作為遺傳操作的依據(jù)，并由此一步步地達到問題的最優(yōu)逼近值．

(4)遺傳操作在初始群體的基礎(chǔ)上，通過遺傳操作產(chǎn)生后代群體，遺傳操作也稱遺傳算子，它影響著群體的進化過程和效率．選擇（繁殖），交叉和變異（突變）是遺傳算法的三個主要操作算子，它們構(gòu)成了遺傳算法的主體，下面分別介紹，選擇（繁殖）、交叉和變異（突變）．①選擇（繁殖）選擇是遺傳算法的基本算子，它從當(dāng)前群體中選擇出一定數(shù)量的優(yōu)良個體，作為參與下一代群體繁殖的父代個體，使它們有機會繁殖后代，體現(xiàn)了“適者生存”的自然選擇原則．個體的選擇是依據(jù)適應(yīng)度大小進行的，適應(yīng)度大的個體被復(fù)制，適應(yīng)度小的被淘汰，而新群體個體的總數(shù)保持不變．假定一個群體有6個符號串，而且它們的適應(yīng)度值如表9.1所示．注意，一個群體中的每個符號串不必是唯一的，且一個群體的符號串?dāng)?shù)目是一個常數(shù)，而繁殖操作生成的是一個同樣大小的群體，這意味著適應(yīng)度較大的符號串最終會在群體中成為多數(shù)．實現(xiàn)上述選擇的一種方法是輪盤選擇．每個符號串在輪盤上占有一格，而格的大小則與符號串的適應(yīng)度值成正比．在選擇一個新的符號串時，只轉(zhuǎn)動輪盤，待輪盤停下，落在標(biāo)記處的格所對應(yīng)的符號串被選中．圖9.2描述了輪盤轉(zhuǎn)動6次生成一代新的群體，且符號串的期望組合為基于期望次數(shù)，見表9.2．新的群體可能是（A，A，A，B，C，C）．很明顯，如果繁殖操作被重復(fù)運用，適應(yīng)度較高符號串在整個群體中將占據(jù)主導(dǎo)地位．由于繁殖操作只能使新群體性能得到改善，但是不能生成新的符號串（個體）．②交叉交叉運算是使群體產(chǎn)生新個體的操作過程，簡單的交叉操作是首先對新群體中的個體（優(yōu)勝者）進行隨機配對，然后在配對個體中隨機選擇交叉點位置，然后將兩個個體的部分結(jié)構(gòu)加以替換，重組而生成新個體．一般交叉操作要求不要太多地破壞優(yōu)良個體的優(yōu)良特性，同時又能夠產(chǎn)生一些較好的新個體模式．交叉操作的主要內(nèi)容包括：

A在形成的配對庫中隨機產(chǎn)生配對個體組，并依概率決定是否進行交叉操作．

B設(shè)定配對交叉點并完成交叉操作．例如，有二個個體A和B，分別用6位二進制字符串編碼 交叉前 交叉后A個體11010111 11010110 A個體B個體01001010 01001011B個體 交叉位置則兩個個體字符串可按如下步驟進行：a

在個體字符串長度范圍內(nèi)，隨機選擇一個交叉點位置，將個體字符串?dāng)嚅_．b

交換個體字符串?dāng)嚅_后一部分信息．由此一來，兩個具有其父母雙方基因成分的符號串由此產(chǎn)生，這一交叉操作所產(chǎn)生的新個體有時和父代個體具有明顯的差別。

有時又會產(chǎn)生一定的相似性，正是有了交叉操作群體才保持著多樣性，從而擴大了遺傳算法的探索范圍，加快了優(yōu)化的收斂速度，需要注意的是，如果整個群體中只有一種符號串，交叉操作不會產(chǎn)生任何新的符號串，如何處理這種情況呢？我們可采用下面要介紹的突變操作來解決這個問題．③變異（突變）在生物的遺傳和自然進化過程中，其細(xì)胞分裂復(fù)制環(huán)節(jié)可能因為某些偶然因素的影響而產(chǎn)生一些復(fù)制差錯，這樣就會導(dǎo)致生物內(nèi)的某些范圍發(fā)生變異，從而產(chǎn)生出新的染色體，表現(xiàn)出新的生物性狀．雖然發(fā)生這種變異的可能性較小，但也是產(chǎn)生新物種的一個不可忽視的原因．

在遺傳算法中則利用變異來模擬生物遺傳和進貨過程中的由變異而產(chǎn)生的新個體．它是對群體中個體的某些基因坐上的基因值作變動．對于二進制編碼的個體，其編碼字符集為（0，1），變異操作就是將個體在變異點上的基因值按照變異概率取反，即1變0，0變1．如個體A依概率產(chǎn)生變異點，分別在第3位和第8位，變異后產(chǎn)生新個體，A個體11010111—→11110110個體．對于實數(shù)編碼（浮點數(shù)編碼）個體，若在某些變異點處的基因值的取值范圍為，變異操作就是用該范圍內(nèi)的一個隨機數(shù)替換原變異位置上的基因值．對于符號編碼個體，若其編碼字符集為，變異操作就是用這個字符集中的一個隨機指定的且與原基因值不相同的符號去替換變異點上的原有符號．

變異的個體以及變異的位置是依據(jù)概率來選擇，個體變異的概率很小，一般為0.001~0.1，也就是說，對于1000個字符中有1~10個發(fā)生變異，個體變異主要起二個作用，一個是繼續(xù)維持群體的多樣性，防止出現(xiàn)未成熟收斂現(xiàn)象，保證算法過程不會產(chǎn)生無法進行的單一群體；另一個是使遺傳算法具有局部的隨機搜索能力，當(dāng)接近最優(yōu)解鄰域時，通過變異可以加速最優(yōu)解收斂速度．

(5)判定遺傳算法的收斂性遺傳算法是一種基于群體進化的計算模型，它通過對群體中的個體進行遺傳操作（選擇、交叉和變異）使群體向著最優(yōu)方向移動并最后逼近問題最優(yōu)解，這樣的進化過程包含了大量的隨機性操作，顯然該進化過程為一隨機過程，從而可用隨機過程理論來研究進化過程.

由遺傳算法的進化過程可知，每一子代群體只和它的父代群體相關(guān)，而與其他代種群無關(guān)，因此進化過程具有天后效應(yīng)，同時，各代種群之間的轉(zhuǎn)換概率與時間的起點無關(guān)，因此可用Markov鏈分析遺傳算法收斂性．遺傳算法收斂定理：基本遺傳算法收斂于最優(yōu)解的概率小于1．由該定理可知，基本遺傳算法不能保證一定能夠收斂到全局最優(yōu)解。一般的，在實際應(yīng)用中，判斷群體的收斂性可以通過各種能夠反映群體進化動態(tài)過程的指標(biāo)加以判斷，如群體的平均適應(yīng)度變化率、最優(yōu)個體適應(yīng)度變化率等．每一子代群體只和它的父代群體相關(guān)，而與其他代種群無關(guān)，因此進化過程具有天后效應(yīng)，同時，各代種群之間的轉(zhuǎn)換概率與時間的起點無關(guān)，因此可用Markov鏈分析遺傳算法收斂性．

(6)最優(yōu)個體解碼（最優(yōu)解）當(dāng)群體進化結(jié)束時，如適應(yīng)度最大的個體，即最優(yōu)個體，進行解碼，從而可以得到應(yīng)相變量的值，這就是優(yōu)化問題的最優(yōu)解．綜上所述，遺傳算法的基本流程如圖9.3所示．例9.2

求二次函數(shù)的最大值，自變量x∈[0，3l]T．解利用遺傳算法來求解該優(yōu)化問題時，其主要步驟如下．（1）個體編碼．遺傳算法的運算對象是表示個體的字符串，為了實現(xiàn)方便，通常采用固定長度的字符串來表示，字符選用0或1．本例中，自變量x的取值范圍為0～31，可以用5位二進制數(shù)來表示x的取值，即0，1，…，31共32個整數(shù)值．（2）群體初始化．采用隨機產(chǎn)生的方法產(chǎn)生初始群體，這里選取群體規(guī)模數(shù)為4，得出由4個個體組成的初始群體，即

個體l01101

個體211000

個體301000

個體410011它們對應(yīng)的x值分別為13、24、8、19，如表9.3中第②欄所示．（3）構(gòu)造適應(yīng)度函數(shù)．本問題的目標(biāo)是使二次函數(shù)最大，而群體進化過程中適應(yīng)度最大的個體即是最優(yōu)個體，于是可以將該二次目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，這樣在進化結(jié)束時，最大適應(yīng)度值的個體所對應(yīng)變量x的值，將使目標(biāo)函數(shù)達到最大．本例中的目標(biāo)函數(shù)可以直接作為適應(yīng)度函數(shù)，在計算適應(yīng)度函數(shù)時需要對個體進行解碼．比如，個體1~個體4解碼后對應(yīng)的x值分別為13、24、8、19，相應(yīng)的適應(yīng)度則分別為169、576、64、361，如表9.3中第③和④欄所示．（4）選擇運算．選擇運算就是從當(dāng)前群體中選出優(yōu)良個體作為父代個體，使它們有機會繁殖后代，一般選擇那些適應(yīng)度較高的個體，個體適應(yīng)度越高．

被選擇的機會就越多，而適應(yīng)度小的個體則被刪除．選擇操作的實現(xiàn)方法很多．這里采用和適應(yīng)度值成正比的概率方法進行選擇．首先，計算出群體中所有個體的適應(yīng)度總和，然后計算每個個體的相對適應(yīng)度大小，并以此作為相應(yīng)的選擇概率，如表9.3中第⑤欄所示．也可以采用輪盤選種法進行篩選，將個體適應(yīng)度的值累加得到總適應(yīng)度的和，每個個體按照適應(yīng)度對應(yīng)著相應(yīng)區(qū)間，，，。

若在區(qū)間上隨機產(chǎn)生一個數(shù)，則該數(shù)值所在區(qū)間對應(yīng)的個體即被選為父代個體．顯然，適應(yīng)度大的個體在適應(yīng)度累計值中占有較大的比例，從而被選中的可能性也就大些．本例中，隨機選擇4個個體，其結(jié)果為：個體1被選擇1次，個體2被選擇2次，個體4被選擇1次．如表9.3中第⑦欄所示，表示傳遞給下一代的個體數(shù)目，其中2號個體占2個，第l、4號個體保持為1個，而3號個體為0，不會進行繁殖．群體中個體在理論上被選擇的概率分別為：0.58、1.97、0.22和1.23，如表9.3中第⑥欄所示．2號個體（11000）性能最優(yōu)（1.97），予以復(fù)制繁殖．3號個體（01000）性能最差（0.22），將它刪除，使之死亡，選擇的結(jié)果基本上反映了生物進化的內(nèi)部機制．新群體的4個個體分別是01101、11000、11000、10011，相應(yīng)的解碼變量值為13、24、24、19，如表9.4中第②和⑦欄所示．經(jīng)過選擇運算后，新一代群體的進化性能有明顯改善，如表9.4中第④欄所示．新群體的最小適應(yīng)度由原來的64提高到361，平均適應(yīng)度也由原來的增293增至421．這是因為在本次群體的進化過程中，淘汰了最差個體（3號）、增加了優(yōu)良個體（2號）的個數(shù)，從而使新群體的總適應(yīng)度累計都得了相應(yīng)的增加．（5）交叉運算（Crossover）選擇運算使新群體的性能得到改善，但是不能使群體產(chǎn)生新個體．交叉運算是使群體產(chǎn)生新個體的操作過程，它通過仿照生物學(xué)中雜交的辦法對染色體（符號串）的某些部分進行交叉換位．簡單的交叉（即一點交叉）操作過程是首先對新群體中的個體（優(yōu)勝者）進行隨機配對，然后在配對個體中隨機選擇交叉點位置．本例中，利用隨機配對的方法選擇1號和2號個體、3號和4號個體作為配對交換對象，如表9.4中第⑤列所示．再利用隨機定位的方法，確定這兩對配對個體的交叉換位的位置，交叉位分別為4和2．表9.4第⑥列中數(shù)字表明交叉點位于該基因座之后，從符號串的左數(shù)第4位及第2位開始進行部分基因的交換，表9.4中第⑦列為交叉操作之后的結(jié)果．例如，在配對庫中選擇第l號個體和第2號個體作為配對對象、交叉點為4，如下式左側(cè)所示．從配對個體字符串左數(shù)第4位個基因座之后進行交叉運算，用下橫線標(biāo)記，所得的新個體如下式的右側(cè)所示：

→．

同樣，配對庫中3號和4號個體進行配對交叉得到另外兩個新個體11011、10000．這4個新個體形成了新的群體，即新一代．表9.4中第⑦列中數(shù)字表明，經(jīng)過交叉操作之后，在群體中出現(xiàn)了更優(yōu)的個體（3號），其適應(yīng)度達到729，遠高于交換前的最大適應(yīng)度576，新群體的平均適應(yīng)度也由原來的421提高到439．由于本例中的適應(yīng)度函數(shù)也就是目標(biāo)函數(shù)本身，所以函數(shù)值也增大了，這說明交換后的新群體正朝著我們所期望的方向發(fā)展．（6）變異（Mutation）．變異運算是模仿生物學(xué)中基因變異的方法，對個體基因座上的基因值依概率進行改變，它將個體字符串某位符號進行逆變，即由1變?yōu)?或由0變?yōu)?．例如，3號個體的第3位發(fā)生變異，如下式左側(cè)，變異之后得到新的個體如下：3號個體{10000}——→{11000}．變異運算也是產(chǎn)生新個體的一種遺傳操作，個體是否進行變異以及在哪個部位變異都由事先給定的概率來決定，一般變異發(fā)生的概率是很小的．本例中取變異概率為0.001，由于群體中總共有20位，于是發(fā)生變異的位數(shù)為20×0.001=0.02位，這表明群體中沒有一位可以變異．反復(fù)執(zhí)行上述的步驟(1)～(5)，直到得出滿意的最優(yōu)解．以上的例子反映了遺傳算法的一些基本運算過程，它利用選擇、交換、突變等操作來模仿生物中的有關(guān)進化過程，不斷循環(huán)迭代計算直到逐漸逼近全局的最優(yōu)解．這一過程構(gòu)成了標(biāo)準(zhǔn)的遺傳算法，也稱為簡單遺傳算法SGA（simpleGA）．三、遺傳算法的有關(guān)說明從理論上講，遺傳算法能夠解決任意維函數(shù)的組合優(yōu)化問題，但實際應(yīng)用中又受超大規(guī)模優(yōu)化問題的限制，其原因，主要是遺傳算法在進化搜索的過程中，每代總要維持一定規(guī)模的群體，若群體規(guī)模太小，所包含信息量也少，不能使算法得到充分發(fā)揮，若群體規(guī)模太大，所包含的信息量也大，但計算次數(shù)會急劇增加，因而限制了算法的使用．遺傳算法的另一個不足之處是易“早熟”．導(dǎo)致算法“早熟”的原因，一方面是遺傳算法中最重要的交叉算子使群體中的染色體具有局部相似性，父代染色體的信息交換量小，從而使搜索停滯不前，另一方面，是變異概率又太小，導(dǎo)致不能使探索轉(zhuǎn)向其他的解空間進行搜索，此外遺傳算法還有“爬山”能力差的弱點，這也是由于變異概率低造成的．

§9.3禁忌搜索算法禁忌搜索（tahusearch或taboosearch，簡稱TS）算法是一種全局性領(lǐng)域搜索算法，它模擬人類具有記憶功能的最優(yōu)特征．1986年Glover最先提出禁忌搜索思想，它屬于確定性的迭代優(yōu)化算法．主要針對一般的下降算法的缺點而提出來的，一般的下降算法在搜索到個局部最優(yōu)解時，算法就容易自動停止，而禁忌搜索采用禁忌等略（或稱禁忌準(zhǔn)則）盡量避免已搜索過的對象，從而保證了對不同的搜索路徑的探索，禁忌搜索算法，不是搜索到局部最優(yōu)解就停止搜索，而是引導(dǎo)算法跳出局部最優(yōu)解，進而轉(zhuǎn)向全局最優(yōu)解．一、禁忌搜索算法的基本原理禁忌搜索算法是人工智能的一種體現(xiàn)，該算法最重要的思想是記住以往已搜索過的局部最優(yōu)解，并在進一步迭代搜索中盡量避開這些局部最優(yōu)解（而不是絕對禁止循環(huán)），進而使得搜索途徑多樣化，以此跳出局部最優(yōu)解．在禁忌搜索算法中涉及到鄰域，侯選解禁忌表，禁忌表規(guī)模，以及破禁水平等內(nèi)容．設(shè)有最優(yōu)化問題

，其中D為離散解集．禁忌搜索算法首先確定一個初始可行解X，初始可行解X可以從可行解集合中隨機選擇．然后選擇一系列的特定搜索方向（移動）作為試探，選擇實現(xiàn)讓特定的目標(biāo)函數(shù)值減少最多的移動．為了避免陷入局部最優(yōu)解，禁忌搜索中采用了一種靈活的“記憶”技術(shù)，對已經(jīng)進行的優(yōu)化過程進行記錄和選擇，已此指導(dǎo)下一步的搜索方面選擇，這就是Tabu表的建立Tabu表中保存了最近若干次迭代過程中所實現(xiàn)的移動的反方移動，凡是處于Tabu表中的移動在當(dāng)前迭代過程中是不允許實現(xiàn)的．這樣可以避免算法重新訪問最近若干次迭代過程中已經(jīng)訪問過的新解，從而防止重復(fù)搜索，幫助算法擺脫局部最優(yōu)解．二、禁忌搜索算法的基本迭代步驟禁忌搜索算法是一種由多種策略組成的混合啟發(fā)式算法．每種策略均是一個啟發(fā)式過程，它們對整個禁忌搜索起著關(guān)鍵的作用．禁忌搜索算法一般由下述若干要素和準(zhǔn)則（策略）構(gòu)成：

(1)鄰域移動鄰域移動是指從一個解（當(dāng)前解）產(chǎn)生另一個解（新解）的途徑，它是保證產(chǎn)生好的解和算法搜索速度的最重要因素之一．鄰域移動定義的方法很多，對于不同的問題應(yīng)采用不同的定義方法．通過移動，目標(biāo)函數(shù)值將產(chǎn)生變化，通過選擇策略產(chǎn)生最好移動．

(2)禁忌表不允許恢復(fù)即被禁止的性質(zhì)稱作禁忌（tabu）．禁忌對象通?？蛇x取解本身或狀態(tài)分量或適值的變化等．禁忌表主要目的是阻止搜索過程中出現(xiàn)循環(huán)和避免陷入局部最優(yōu)，它通常記錄前若干次的移動，禁止這些移動在近期內(nèi)返回．在迭代固定次數(shù)后，禁忌表釋放這些移動，重新參加運算，因此它是一個循環(huán)表．每迭代一次，它的禁忌對象被記錄在禁忌表的末端，而它的最早的一個移動就從禁忌表中釋放出來．有時，為了節(jié)省記憶和時間，禁忌表并不記錄所有的移動，只記錄那些有特殊性質(zhì)的移動，如記載能引起目標(biāo)函數(shù)發(fā)生變化的移動．

禁忌表是禁忌搜索算法的核心，禁忌表的大小在很大程度上影響著搜索速度和解的質(zhì)量．如果選擇得好，可有助于識別出曾搜索過的區(qū)域．實驗表明，如果禁忌表規(guī)模過小，那么搜索過程就可能進人死循環(huán)，整個搜索將圍繞著相同的幾個解徘徊．相反，如果禁忌表規(guī)模過大，那它將在相當(dāng)大的程度上限制了搜索區(qū)域，好的解就有可能被跳過，而且，不會改進解的效果反而增加算法運算時間．因此一個好的禁忌表規(guī)模應(yīng)該是盡可能小卻又能避免算法進入循環(huán)．禁忌表的這種特性非常類似于“短期記憶”，因而人們把禁忌表稱作短期記憶函數(shù)．禁忌表規(guī)?？梢允枪潭ǔ?shù)，也可以按某種準(zhǔn)則或公式在定義區(qū)間內(nèi)動態(tài)變化．禁忌表的另一作用是通過調(diào)整其大小使搜索發(fā)散或收斂．初始搜索時，為提高解的分散性，擴大搜索區(qū)域，使搜索路徑多樣化，經(jīng)常希望禁忌表規(guī)模?。幌喾?，當(dāng)搜索過程接近最優(yōu)解時，為提高解的集中性，減少分散，縮小搜索區(qū)域，這時通常希望禁忌表規(guī)模大．為達到這樣的目的，最近越來越多的人們允許禁忌表的大小和結(jié)構(gòu)隨搜索過程發(fā)生改變，即使用動態(tài)禁忌表，實驗結(jié)果表明了動態(tài)禁忌表往往會比固定禁忌表獲得更好的解．

(3)選擇策略選擇策略即擇優(yōu)規(guī)則，是對當(dāng)前的鄰域移動選擇一個移動而采用的準(zhǔn)則．在選擇策略中，問題解的適值是關(guān)鍵要素．與遺傳算法類似，目標(biāo)函數(shù)可以作為適值函數(shù)．當(dāng)然，目標(biāo)函數(shù)的任何變形都可作為適值函數(shù)，只要選取的適值增加與目標(biāo)函數(shù)的最優(yōu)性一致即可．擇優(yōu)規(guī)則可以采用多種策略，不同的策略影響算法的性能，一個好的選擇策略應(yīng)該是既保證解的質(zhì)量又保證計算速度．當(dāng)前采用最廣泛的兩類策略是最好解優(yōu)先策略（bestimprovedstrategy）和第一個改進解優(yōu)先策略（firstimprovedstrategy）．最好解優(yōu)先策略就是對當(dāng)前鄰域移動中選擇移動值最好的移動產(chǎn)生的解，作為下一次迭代的開始．而第一個改進解優(yōu)先策略是搜索鄰域移動時選擇第一個改進當(dāng)前解的鄰域移動產(chǎn)生的解作為下一次迭代的開始．最好改進解優(yōu)先策略相當(dāng)于尋找最陡的下降，這種擇優(yōu)規(guī)則效果比較好，但是它需要更多的計算時間；而最快的下降對應(yīng)尋找第一個改進解的移動，由于它無需搜索整個一次鄰域移動，所以它所花計算時間較少，對于比較大的鄰域，往往比較適合．

(4)破禁策略破禁策略通常指破禁水平（aspiration）函數(shù)選擇．當(dāng)一個禁忌移動在隨后|T|次的迭代內(nèi)再度出現(xiàn)時，如果它能把搜索帶到一個從未搜索過的區(qū)域，則應(yīng)該接受該移動即破禁，不受禁忌表的限制．衡量標(biāo)準(zhǔn)就是定義一個破禁水平函數(shù)．破禁水平函數(shù)選取通?；谝韵聝蓚€準(zhǔn)則：基于適值的準(zhǔn)則（若某個禁忌候選解的適值優(yōu)于以往搜索最優(yōu)解，則解禁此候選解為當(dāng)前解），基于搜索方向的準(zhǔn)則（正按有效的搜索途徑進行）．

(5)禁忌頻數(shù)禁忌頻數(shù)是對禁忌表的另一種補充，可改變選擇決策對象的范圍．例如，在實際求解時，可以根據(jù)問題和算法的需要，記憶某個狀態(tài)出現(xiàn)的頻率（該狀態(tài)出現(xiàn)次數(shù)與總迭代步數(shù)的比）或各種信息，可以增加禁忌表規(guī)模來避免循環(huán)；反之則縮小禁忌表規(guī)模來維持移動．目前有很多文獻在探討實施方法．禁忌長期表的使用就是其中一例，短期記憶用來避免最近所作的一些移動被修改，但是在很多情況下短期記憶并不足以把算法搜索帶到能夠改進解的區(qū)域．因此在實際應(yīng)用中常常把短期記憶與長期記憶結(jié)合使用，以保持局部的強化和全局的多樣化之間的平衡，即在加強與較優(yōu)解有關(guān)性質(zhì)的同時還能把搜索帶到未搜索過的區(qū)域．在長期記憶中，頻率起著非常重要的作用．使用頻率的目的就是通過了解同樣的選擇在過去做了多少次來重新指導(dǎo)局部選擇，當(dāng)在非禁忌移動中找不到可以改進的解時用長期記憶更有效．長期記憶函數(shù)主要有兩種形式，一種通過懲罰的形式，即用一些評價函數(shù)來懲罰在過去的搜索中用的最多或最少的那些選擇，并用一些啟發(fā)方式來產(chǎn)生新的初始點．用這種方式獲得的多樣性可以通過保持一段懲罰時間來得到加強，然后取消懲罰。禁忌搜索繼續(xù)按照正常的評價規(guī)則進行，另一種形式采用頻率矩陣，使用兩種長期記憶，一種是基于最小頻率的長期記憶，另一種是基于最大頻率的長期記憶．通過使用基于最小頻率的長期記憶，可以在未搜索的區(qū)域產(chǎn)生新的序列；而使用基于最大頻率的長期記憶，可以在過去的搜索中認(rèn)為是好的可行區(qū)域內(nèi)產(chǎn)生不同的序列，在整個搜索過程中頻率矩陣被不斷的修改．

(6)終止規(guī)則實際設(shè)計算法時通常采用如下終止準(zhǔn)則：①給定最大迭代步數(shù)；②設(shè)定某個對象的最大禁忌頻率；③設(shè)定適值的偏離幅度．禁忌搜索算法的流程如圖9.4所示．三、禁忌搜索算法的有關(guān)說明（關(guān)鍵參數(shù)確定及算法缺陷）

(1)禁忌對象確定禁忌對象是指禁忌表中被禁的變化元素．由于解狀態(tài)的變化分為解的簡單變化、解向量的分量變化和目標(biāo)值變化三種情況，因此禁忌對象的選取也有對解的簡單變化進行禁忌、對解向量的分量變化進行禁忌和對解的目標(biāo)值變化進行禁忌三種情況：①解的簡單變化禁忌當(dāng)解從X0到X1時，X1可能是局部最優(yōu)解，為了避開局部最優(yōu)解，應(yīng)禁忌X1這個解再度出現(xiàn)．禁忌的規(guī)則是：當(dāng)X1的鄰域N（X1）中有比它更優(yōu)的解時，則選擇更優(yōu)的解；當(dāng)X1為其鄰域N（X1）的局部最優(yōu)時，不再選X1，而選擇比X1較差的解．②解的分量的變化禁忌當(dāng)一個解X由多個分量構(gòu)成時，可通過構(gòu)造解X的鄰域N（X）各個分量在X的鄰域內(nèi)變化，其禁忌規(guī)則同情況（1）．③目標(biāo)值的變化禁忌在單目標(biāo)值情況下，目標(biāo)值變化禁忌類似于解的簡單變化禁忌；在多目標(biāo)情況下，可以通過綜合評價轉(zhuǎn)化為單目標(biāo)，按類似于解的簡單變化禁忌處理，也可以采用類似于解的分量的變化禁忌處理方法．

(2)禁忌長度確定禁忌長度是指被禁忌對象不允許被選取的迭代步數(shù)，一般是給被禁忌對象X一個數(shù)L，稱為禁忌長度，要求X在L步迭代內(nèi)被禁，在禁忌表中采用Tabu（X）=L記憶，每迭代一步，作運算Tabu（X）=L－1，直至Tabu（X）=0時解禁．在算法構(gòu)造和計算的過程中，要求盡量少地占用內(nèi)存，使禁忌長度、候選集合盡量?。?，禁忌長度過短造成搜索的循環(huán)，候選集合過小造成過早地陷入局部最優(yōu)．有關(guān)禁忌長度L的選取，可以歸納為以下幾種情況：①L為常數(shù)．如L=10，，（為鄰域中鄰居的個數(shù)），這種規(guī)則容易在算法中實現(xiàn)．②L∈[]．此時L是可以變化的數(shù)，其變化依據(jù)是被禁對象的目標(biāo)值和鄰域的結(jié)構(gòu)，此時和是確定的．確定和通常根據(jù)問題的規(guī)模N，限定變化區(qū)間，；也可以用鄰域中鄰居的個數(shù)確定變化區(qū)間，．③和的動態(tài)選?。械那闆r下，用和的變化能達到更好的解．禁忌長度的選取同實際問題、試驗和設(shè)計者的經(jīng)驗有緊密的聯(lián)系，同時它決定了計算的復(fù)雜性．過短會出現(xiàn)循環(huán)，過長又使計算時間增加．

(3)候選集合的確定候選集合由鄰域中的鄰居組成，常規(guī)的方法是從鄰域中選擇若干個目標(biāo)值或評價值最佳的鄰居入選．有時認(rèn)為上述方法的計算量還是太大，則不在鄰域的所有鄰居中選擇，而是在鄰域中的一部分鄰居中選擇若干個目標(biāo)值或評價值最佳的解狀態(tài)入選，也可以用隨機選取的方法實現(xiàn)部分鄰居的選?。?/p>

(4)釋放準(zhǔn)則在禁忌搜索算法的迭代過程中，候選集中的全部對象或某一對象會被禁忌，但若解禁則其目標(biāo)值將有非常大的下降情況．在這種情況下，為了達到全局的最優(yōu)，我們會讓一些禁忌對象重新可選，這種方法稱為釋放，相應(yīng)的準(zhǔn)則稱為釋放準(zhǔn)則．

(5)記憶頻率信思在計算的過程中，記憶一些信息對解決問題是有利的．如一個最好的目標(biāo)值出現(xiàn)的頻率很高，則可推測現(xiàn)有參數(shù)的算法可能無法再得到更好的解，因為重復(fù)的次數(shù)過高，有可能出現(xiàn)多次循環(huán)．此時，可以記憶解集合、有序被禁對象組、目標(biāo)值集合等的出現(xiàn)頻率．

(6)終止規(guī)則大體上有四種終止規(guī)則：①步數(shù)終止準(zhǔn)則；②頻率控制準(zhǔn)則；③目標(biāo)值變化控制準(zhǔn)則；④目標(biāo)值偏離程度準(zhǔn)則．

(7)禁忌算法的缺陷禁忌搜索對于初始解具有較強的依賴性．一個較好的初始解可使禁忌搜索在解空間中搜索到更好的解，而一個較差的初始解則會降低禁忌搜索的收斂速度．為此人們往往使用啟發(fā)式算法來獲得一個較好的初始解，以提高禁忌搜索的性能．禁忌搜索的另一缺陷是在搜索過程中初始解只能有一個，迭代一次，也只能是把一個解移動到另一個解．§9.4人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetworks，簡稱ANN）是基于生物學(xué)的神經(jīng)元網(wǎng)絡(luò)的基本原理而建立的，實質(zhì)上是模仿大腦的結(jié)構(gòu)和功能，借助計算機處理大規(guī)模信息的一種信息處理系統(tǒng)．如今人們對人工神經(jīng)網(wǎng)絡(luò)的研究正日趨成熟，人工神經(jīng)網(wǎng)絡(luò)已被廣泛應(yīng)用到函數(shù)逼近、模式識別、圖像處理與計算機視覺，信號處理、時間序列，專家系統(tǒng)、動力系統(tǒng)、人工智能以及最優(yōu)化等方面．由Minsley和Papert提出的多層前向神經(jīng)元網(wǎng)絡(luò)（也稱多層感和器）是目前最為常用的網(wǎng)絡(luò)結(jié)構(gòu)，它被廣泛地應(yīng)用到模式分類和函數(shù)逼近當(dāng)中，已經(jīng)證明含有任意多個隱層神經(jīng)元的多層前向神經(jīng)網(wǎng)絡(luò)可以逼近任意的連續(xù)函數(shù)．人工神經(jīng)網(wǎng)絡(luò)有單層和多層之分，每一層包含若干神經(jīng)元，即信息處理元，各神經(jīng)元之間用帶可變權(quán)重的有向弧連接，網(wǎng)絡(luò)通過對已知信息的反復(fù)學(xué)習(xí)訓(xùn)練，通過逐步調(diào)整改變神經(jīng)元連接權(quán)重的方法，達到處理信息、模擬輸入輸出之間關(guān)系的目的．它不需要知道輸入輸出之間的確切關(guān)系，不需大量參數(shù)，只需知道能引起輸出變化的非恒定因素，即非常量性參數(shù)．因此與傳統(tǒng)的數(shù)據(jù)處理方法相比，神經(jīng)網(wǎng)絡(luò)技術(shù)在處理模糊數(shù)據(jù)、隨機性數(shù)據(jù)、非線性數(shù)據(jù)方面具有明顯優(yōu)勢，對規(guī)模大、結(jié)構(gòu)復(fù)雜、信息不明確的系統(tǒng)尤為適用．一、人工神經(jīng)網(wǎng)絡(luò)的基本概念（一）人工神經(jīng)元神經(jīng)元是神經(jīng)網(wǎng)絡(luò)的基本單元，它是一個多輸人單輸出的非線性信息處理單元；根據(jù)神經(jīng)元的特性和功能，可以把神經(jīng)元抽象為一個簡單的數(shù)學(xué)模型，如圖9.5所示．它主要包括如下基本要素：

（1）一組權(quán)系數(shù)表示神經(jīng)元之間的連接強度，權(quán)系數(shù)值為正表示激活，為負(fù)表示抑制．（2）求和單元用于求取輸人信息的加權(quán)和．（3）非線性激勵函數(shù)f（·）起非線性映射作用，并將神經(jīng)元的輸出幅度限制在一定的范圍之內(nèi)．圖9.5中，是神經(jīng)元的輸人，代表前級n個神經(jīng)元的軸突的輸出信息，是神經(jīng)元k的閾值，分別是神經(jīng)元k對的權(quán)系數(shù)，亦即突觸信號的傳遞強度，是神經(jīng)元k的輸出，f（·）是激勵函數(shù)或傳遞函數(shù)，它反映了神經(jīng)元的非線性信息處理的特性．

由神經(jīng)元模型，可以得到神經(jīng)元的數(shù)學(xué)模型表達式其中，激發(fā)函數(shù)f（·）有多種形式，常用的有如下三種類型:

(1)閾值型激勵函數(shù)如圖9.6（a）所示，這是一種最簡單的激勵函數(shù)型，它只具有兩種輸出：0和1，分別表示神經(jīng)元的激活與抑制狀態(tài)，這種激勵函數(shù)的神經(jīng)元為離散輸出模型，其數(shù)學(xué)表達式為

(2)分段線性型激勵函數(shù)如圖9.6（b）所示，它表示在一定的范圍內(nèi)，輸入／輸出一線性變化關(guān)系．當(dāng)輸入達到某一量值時，神經(jīng)元則進入飽和限幅狀態(tài)，限制輸出的幅度．其數(shù)學(xué)表達式為

(3)Sigmoid型激勵函數(shù)如圖9.6（c）所示，這種函數(shù)具有連續(xù)、平滑及飽和的非線性特性，一般采用指數(shù)或雙曲正切等S狀的曲線來表示，如或（二）人工神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)雖然單個處理單元可以執(zhí)行簡單的圖型檢測功能，但更強的識別處理能力卻來自多個結(jié)點“連成”的網(wǎng)絡(luò)，也就是人工神經(jīng)網(wǎng)絡(luò)．這里所說的“連成”，是靠輸入至結(jié)點或結(jié)點至結(jié)點間的信號傳輸通路實現(xiàn)的．下面我們將把這種信號傳輸通路簡稱為“連接”．每一連接都具有一加權(quán)，也稱為連接權(quán)，反映連接的強度．

(1)單層網(wǎng)絡(luò)最簡單的網(wǎng)絡(luò)是把一組幾個結(jié)點形成一層，如圖9.7所示．圖9.7中，左邊的黑色圓點只起著分配輸入信號的作用，沒有計算作用，所以不看作網(wǎng)絡(luò)的一層，右邊用圓圈表示的一組結(jié)點則被看作一層．輸入信號可表示為行向量，其中每一分量通過加權(quán)連接到各結(jié)點．每一結(jié)點均可產(chǎn)生一個輸入的加權(quán)和．為了更一般化，這里仍然采用了全連接，并且都是前饋連接．在這種單層網(wǎng)絡(luò)中，可把各加權(quán)表示為加權(quán)矩陣W矩陣的維數(shù)是，n是輸入信號向量的分量數(shù)．我們稱輸入信號向量為輸入圖形．n是該層內(nèi)的結(jié)點數(shù)．W的分量這樣表示，例如由第三個輸入連到第二個結(jié)點的連接權(quán)表示為w32．輸入信號的加權(quán)和可表示為，

其中S是各結(jié)點加權(quán)和的行向量，S=[s1，s2，···，sn]．輸出向量，Y=[y1，y2，···，yn]，其中．

(2)多層網(wǎng)絡(luò)一般，大而復(fù)雜的網(wǎng)絡(luò)能提供更強的計算能力．雖然目前已構(gòu)成了很多網(wǎng)絡(luò)模型，但它們的結(jié)點都是按層排列的，這一點正是模仿了大腦皮層中的網(wǎng)絡(luò)模塊．構(gòu)成多層網(wǎng)絡(luò)，只要將單層網(wǎng)絡(luò)進行級聯(lián)就可以了，即一層的輸出作為下一層的輸入．圖9.8表示了兩層和三層網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)．但是應(yīng)該注意，在構(gòu)成多層網(wǎng)絡(luò)時，層間的轉(zhuǎn)移函數(shù)應(yīng)是非線性的，否則多層網(wǎng)絡(luò)的計算能力并不比單層網(wǎng)絡(luò)的強．因為在線性轉(zhuǎn)移函數(shù)的情況下，兩層網(wǎng)絡(luò)的輸出的計算是第一層的輸出為，作為第二層的輸入，通過第二個加權(quán)矩陣得到網(wǎng)絡(luò)輸出為或 ．這表明兩層線性網(wǎng)絡(luò)等效于單層網(wǎng)絡(luò)，只是后者的加權(quán)矩陣為兩個加權(quán)矩陣的乘積．所以，在多層網(wǎng)絡(luò)中，層間的轉(zhuǎn)移函數(shù)為非線性的．多層網(wǎng)絡(luò)中，接收輸人信號的輸入層不計入網(wǎng)絡(luò)的層數(shù)，因為它只起著輸入信號緩沖器的作用，沒有處理功能．產(chǎn)生輸出信號的層為輸出層．除此之外的中間層稱為隱層，因為它們不直接與外部環(huán)境打交道．一般，隱層數(shù)為零到幾層．注意圖9.8中所示多層網(wǎng)絡(luò)均為前饋全連接多層網(wǎng)絡(luò)，實際中可能有部分連接的情況。二、BP神經(jīng)網(wǎng)絡(luò)的基本原理目前人工神經(jīng)網(wǎng)絡(luò)應(yīng)用較多的是BP網(wǎng)絡(luò)，BP神經(jīng)網(wǎng)絡(luò)是一種單向傳播的多層前饋網(wǎng)絡(luò)．圖9.9是一個三層BP網(wǎng)絡(luò)示意圖．它由輸入層、隱層和輸出層構(gòu)成，相鄰層各個神經(jīng)元之間形成完全連接關(guān)系，而同一層內(nèi)各個神經(jīng)元之間沒有任何連接關(guān)系．n個輸入信號從輸入層進入網(wǎng)絡(luò)，經(jīng)傳遞函數(shù)（一般為Sigmoid函數(shù)）變換后到達隱層，然后再經(jīng)傳遞函數(shù)（有時是線性函數(shù)）變換到輸出層構(gòu)成m個輸出信號．由于同層內(nèi)各個神經(jīng)元之間無耦合關(guān)系，每一層神經(jīng)元的輸出信號只影響下一層神經(jīng)元的輸入和輸出．不難看出，BP神經(jīng)網(wǎng)絡(luò)是一個從n維空間Rn的輸入到m維空間Rm的輸出的高度非線性映射，網(wǎng)絡(luò)通過對簡單的非線性函數(shù)（傳遞函數(shù)或稱之為單元特性函數(shù)）進行數(shù)次復(fù)合，可以逼近一個非常復(fù)雜的非線性函數(shù)．當(dāng)然，這樣的三層BP神經(jīng)網(wǎng)絡(luò)可以逼近任意閉區(qū)間內(nèi)的任意連續(xù)函數(shù)．設(shè)BP神經(jīng)網(wǎng)絡(luò)的輸入為n維向量X∈Rn，，輸出為m維向量，隱層共有l(wèi)個神經(jīng)元，隱層輸出為l維向量，．網(wǎng)絡(luò)的輸出可表示為

其中，和分別為由輸入層到隱層和隱層到輸出層的連接權(quán)值，和分別為隱層和輸出層的閾值．傳遞函數(shù)一般為對數(shù)Sigmoid函數(shù)，即．對數(shù)Sigmoid函數(shù)的值域是（0，1）．根據(jù)使用場合不同，傳遞函數(shù)可以用雙曲正切Sigmoid函數(shù)，,x或線性函數(shù)．連接權(quán)值和以及閾值和是網(wǎng)絡(luò)的運行參數(shù)，其值可由網(wǎng)絡(luò)通過學(xué)習(xí)已知的樣本知識獲得．人工神經(jīng)網(wǎng)絡(luò)計算流程如圖9.10所示．如何確定最佳的網(wǎng)絡(luò)結(jié)構(gòu)是目前神經(jīng)元網(wǎng)絡(luò)研究中的一個重要課題，它依賴于隱層和隱層神經(jīng)元個數(shù)多少的選取．我們知道，如果具有無限個隱層神經(jīng)元，只有一個隱含層的前向神經(jīng)元網(wǎng)絡(luò)就可對連續(xù)函數(shù)進行任意精度的逼近．另外，雖然在一般情況下，兩個隱含層的神經(jīng)元網(wǎng)絡(luò)比單隱含層的神經(jīng)元網(wǎng)絡(luò)具有更好的逼近能力，但在大多數(shù)應(yīng)用問題中，只有一個隱含層的神經(jīng)元網(wǎng)絡(luò)就已經(jīng)足夠了．當(dāng)隱層個數(shù)確定以后，我們還需要決定使用多少個隱層神經(jīng)元．一方面，太少的隱層神經(jīng)元會使網(wǎng)絡(luò)缺乏逼近能力．另一方面，太多的隱層神經(jīng)元又會增加訓(xùn)練時間且降低神經(jīng)元網(wǎng)絡(luò)的反應(yīng)速度．研究人員提出了許多種確定隱層神經(jīng)元個數(shù)的方法，它們的主要思想是在訓(xùn)練的過程中逐漸增加或減少隱層神經(jīng)元的數(shù)目．三、BP神經(jīng)網(wǎng)絡(luò)算法基本迭代步驟

BP算法是一種有指導(dǎo)的梯度下降算法，其實現(xiàn)步驟為：

(1)將各初始權(quán)值和閾值賦予(－1，1)間的隨機數(shù)，可用均勻分布等隨機數(shù)，保證網(wǎng)絡(luò)不被大的加權(quán)所飽和．

(2)從訓(xùn)練樣本數(shù)據(jù)中選一對數(shù)據(jù)()，將輸入向量加到輸入層()，使得對所有輸入節(jié)點i有

，式中，上標(biāo)k指樣本標(biāo)號．

(3)信號通過網(wǎng)絡(luò)前向傳播，利用關(guān)系式計算從第一層開始的各層內(nèi)每個節(jié)點的輸出，直到輸出層的每個節(jié)點的輸出計算完為止．

(4)計算輸出層每個節(jié)點誤差值(對sigmoid函數(shù))

這個誤差由實際輸出與要求的目標(biāo)值之差獲得．

(5)計算前面各層每個節(jié)點誤差值．

這靠逐層反傳誤差獲得，其中直到將每層內(nèi)每個節(jié)點的誤差算完為止．(6)利用加權(quán)修正公式修正所有連接權(quán)值．一般，稱為訓(xùn)練速率系數(shù)．(7)返回步驟(2)，對下一輸入樣本重復(fù)步驟(2)～(7)，直至收斂到一定的精度范圍之內(nèi)．四、人工神經(jīng)網(wǎng)絡(luò)有關(guān)說明人工神經(jīng)網(wǎng)絡(luò)是基于人類大腦的結(jié)構(gòu)和功能而建立起來的新學(xué)科．盡管目前它只是大腦的低級近似，但它的很多特點和人類的智能特點類似．正是由于這些特點，使得神經(jīng)網(wǎng)絡(luò)不同于一般計算機和人工智能．（一）固有的并行結(jié)構(gòu)和并行處理人工神經(jīng)網(wǎng)絡(luò)與人類的大腦類似，不但結(jié)構(gòu)上是并行的，它的處理順序也是并行的和同時的．在同一層內(nèi)的處理單元都是同時操作的，即神經(jīng)網(wǎng)絡(luò)的計算功能分布在多個處理單元上．而一般計算機通常有一個處理單元，其處理順序是串行的．目前的神經(jīng)網(wǎng)絡(luò)功能常常用一般計算機的串行工作方式來模擬它的并行處理方式，所以顯得很慢，而真正的神經(jīng)網(wǎng)絡(luò)將會大大提高處理速度，并能實現(xiàn)實時處理．（二）知識的分布存儲

在神經(jīng)網(wǎng)絡(luò)中，知