第九章現代優化算法簡介遺傳算法、模擬退火算法、禁忌算法、人工神經網絡統稱20世紀80年代初產生的現代優化算法．它主要解決優化問題中的難解的問題，下面分別介紹遺傳算法、模擬退火算法、禁忌算法、人工神經網絡．§9.1模擬退火算法一、模擬退火算法基本原理

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

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

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

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

則模擬退火狀態序列為馬氏鏈．馬氏鏈是一個時間離散，狀態離散的時間序列，其特點是具有無后效應．馬氏鏈從某一時刻的某一狀態變為另一時刻的另一狀態稱為狀態的轉移，而從當前狀態經一次轉移到下個狀態的可能性稱為一步轉移概率，可記為

.

從當前轉態經n步轉移到下一狀態的概率，可記為．若解空間有限，馬氏鏈稱為有限狀態馬氏鏈，若，馬氏鏈稱為時齊的．以下討論的模擬退火算法算法為有限狀態馬氏鏈．

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

其中為狀態的i鄰域中狀態總數．記為由當前狀態i接受狀態j的概率，接受概率通常定義為.

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

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

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

(9.1)

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

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

因此可給定一個比較小的概率P，在一個溫度和給定的迭代步數內，除當前局部最優解外，如果其它狀態的接受概率都小于P時，算法終止．

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

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

其尋優過程如下：

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

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

染色體1 11111

染色體2 11110┇

染色體31 00001

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

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

(3)構造評價函數（適應度）在遺傳算法中，通常將優化問題的目標函數進行適當的變化后，作為遺傳算法的評價函數，或稱為適應度．群體在進化過程中，通過適應度來評價個體的優劣，作為遺傳操作的依據，并由此一步步地達到問題的最優逼近值．

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

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

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

在個體字符串長度范圍內，隨機選擇一個交叉點位置，將個體字符串斷開．b

交換個體字符串斷開后一部分信息．由此一來，兩個具有其父母雙方基因成分的符號串由此產生，這一交叉操作所產生的新個體有時和父代個體具有明顯的差別。

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

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

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

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

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

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

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

個體l01101

個體211000

個體301000

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

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

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

→．

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

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

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

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

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

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

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

(4)破禁策略破禁策略通常指破禁水平（aspiration）函數選擇．當一個禁忌移動在隨后|T|次的迭代內再度出現時，如果它能把搜索帶到一個從未搜索過的區域，則應該接受該移動即破禁，不受禁忌表的限制．衡量標準就是定義一個破禁水平函數．破禁水平函數選取通常基于以下兩個準則：基于適值的準則（若某個禁忌候選解的適值優于以往搜索最優解，則解禁此候選解為當前解），基于搜索方向的準則（正按有效的搜索途徑進行）．

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

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

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

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

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

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

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

(6)終止規則大體上有四種終止規則：①步數終止準則；②頻率控制準則；③目標值變化控制準則；④目標值偏離程度準則．

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

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

由神經元模型，可以得到神經元的數學模型表達式其中，激發函數f（·）有多種形式，常用的有如下三種類型:

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

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

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

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

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

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

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

BP算法是一種有指導的梯度下降算法，其實現步驟為：

(1)將各初始權值和閾值賦予(－1，1)間的隨機數，可用均勻分布等隨機數，保證網絡不被大的加權所飽和．

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

，式中，上標k指樣本標號．

(3)信號通過網絡前向傳播，利用關系式計算從第一層開始的各層內每個節點的輸出，直到輸出層的每個節點的輸出計算完為止．

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

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

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

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

在神經網絡中，知