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

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

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

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

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

.

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

由前述模擬退火算法的迭代過程可知，算法是從一個(gè)初始狀態(tài)開始后，前一步狀態(tài)轉(zhuǎn)移均是在當(dāng)前狀態(tài)i的鄰域中隨機(jī)產(chǎn)生新狀態(tài)j，然后以一定概率進(jìn)行接受．可見接受概率僅依賴于新狀態(tài)和當(dāng)前狀態(tài)，并由溫度加以控制．因此模擬退火算法算法顯然對應(yīng)一個(gè)馬氏鏈．若固定每一溫度T，算法均計(jì)算馬氏鏈的變化直系平穩(wěn)分布，然后下降溫度，稱這種算法為時(shí)齊算法．若無需各溫度下算法均達(dá)到平穩(wěn)分布，但溫度需按一定的速度下降，稱這料算法為非時(shí)齊或非平穩(wěn)馬氏鏈算法．馬氏鏈可用一個(gè)有的圖表示，其中，V為所有狀態(tài)構(gòu)成的頂點(diǎn)集，為邊集，其中是以頂點(diǎn)i為起點(diǎn)的有向線段的終點(diǎn)集合．記為由狀態(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)移概率，則模擬退火馬氏鏈模型為綜上所述，模擬退火算法要實(shí)現(xiàn)全局收斂必須滿足如下三個(gè)條件：（1）狀態(tài)可達(dá)性，即無論起點(diǎn)如何，任何一個(gè)狀態(tài)都可以到達(dá)，由此有求得最優(yōu)解可能．（2）初值魯棒性，即算法的最終結(jié)果不依賴初值．（3）極限分布的存在性，即包含兩個(gè)方面內(nèi)容：一是當(dāng)溫度不變時(shí)，其馬氏鏈的極限分布存在；二是當(dāng)溫度漸近0時(shí)，其馬氏鏈也有極限分布．四、模擬退火算法的有關(guān)說明（關(guān)鍵參數(shù)調(diào)控）在模擬退火算法執(zhí)行過程中，算法效果取決于一組控制參數(shù)的選擇，關(guān)鍵參數(shù)的控制對算法性能影響很大．模擬退火算法的關(guān)鍵參數(shù)，包括初始溫度，溫度下降方法，每一溫度迭氏長度，終止準(zhǔn)則．

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

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

(9.1)

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

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

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

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

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

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

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

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

染色體1 11111

染色體2 11110┇

染色體31 00001

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

個(gè)體l01101

個(gè)體211000

個(gè)體301000

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

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

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

→．

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(7)禁忌算法的缺陷禁忌搜索對于初始解具有較強(qiáng)的依賴性．一個(gè)較好的初始解可使禁忌搜索在解空間中搜索到更好的解，而一個(gè)較差的初始解則會降低禁忌搜索的收斂速度．為此人們往往使用啟發(fā)式算法來獲得一個(gè)較好的初始解，以提高禁忌搜索的性能．禁忌搜索的另一缺陷是在搜索過程中初始解只能有一個(gè)，迭代一次，也只能是把一個(gè)解移動(dòng)到另一個(gè)解．§9.4人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetworks，簡稱ANN）是基于生物學(xué)的神經(jīng)元網(wǎng)絡(luò)的基本原理而建立的，實(shí)質(zhì)上是模仿大腦的結(jié)構(gòu)和功能，借助計(jì)算機(jī)處理大規(guī)模信息的一種信息處理系統(tǒng)．如今人們對人工神經(jīng)網(wǎng)絡(luò)的研究正日趨成熟，人工神經(jīng)網(wǎng)絡(luò)已被廣泛應(yīng)用到函數(shù)逼近、模式識別、圖像處理與計(jì)算機(jī)視覺，信號處理、時(shí)間序列，專家系統(tǒng)、動(dò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)證明含有任意多個(gè)隱層神經(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)重的方法，達(dá)到處理信息、模擬輸入輸出之間關(guān)系的目的．它不需要知道輸入輸出之間的確切關(guān)系，不需大量參數(shù)，只需知道能引起輸出變化的非恒定因素，即非常量性參數(shù)．因此與傳統(tǒng)的數(shù)據(jù)處理方法相比，神經(jīng)網(wǎng)絡(luò)技術(shù)在處理模糊數(shù)據(jù)、隨機(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ò)的基本單元，它是一個(gè)多輸人單輸出的非線性信息處理單元；根據(jù)神經(jīng)元的特性和功能，可以把神經(jīng)元抽象為一個(gè)簡單的數(shù)學(xué)模型，如圖9.5所示．它主要包括如下基本要素：

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

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

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

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

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

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

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

(2)多層網(wǎng)絡(luò)一般，大而復(fù)雜的網(wǎng)絡(luò)能提供更強(qiáng)的計(jì)算能力．雖然目前已構(gòu)成了很多網(wǎng)絡(luò)模型，但它們的結(jié)點(diǎn)都是按層排列的，這一點(diǎn)正是模仿了大腦皮層中的網(wǎng)絡(luò)模塊．構(gòu)成多層網(wǎng)絡(luò)，只要將單層網(wǎng)絡(luò)進(jìn)行級聯(lián)就可以了，即一層的輸出作為下一層的輸入．圖9.8表示了兩層和三層網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)．但是應(yīng)該注意，在構(gòu)成多層網(wǎng)絡(luò)時(shí)，層間的轉(zhuǎn)移函數(shù)應(yīng)是非線性的，否則多層網(wǎng)絡(luò)的計(jì)算能力并不比單層網(wǎng)絡(luò)的強(qiáng)．因?yàn)樵诰€性轉(zhuǎn)移函數(shù)的情況下，兩層網(wǎng)絡(luò)的輸出的計(jì)算是第一層的輸出為，作為第二層的輸入，通過第二個(gè)加權(quán)矩陣得到網(wǎng)絡(luò)輸出為或 ．這表明兩層線性網(wǎng)絡(luò)等效于單層網(wǎng)絡(luò)，只是后者的加權(quán)矩陣為兩個(gè)加權(quán)矩陣的乘積．所以，在多層網(wǎng)絡(luò)中，層間的轉(zhuǎn)移函數(shù)為非線性的．多層網(wǎng)絡(luò)中，接收輸人信號的輸入層不計(jì)入網(wǎng)絡(luò)的層數(shù)，因?yàn)樗黄鹬斎胄盘柧彌_器的作用，沒有處理功能．產(chǎn)生輸出信號的層為輸出層．除此之外的中間層稱為隱層，因?yàn)樗鼈儾恢苯优c外部環(huán)境打交道．一般，隱層數(shù)為零到幾層．注意圖9.8中所示多層網(wǎng)絡(luò)均為前饋全連接多層網(wǎng)絡(luò)，實(shí)際中可能有部分連接的情況。二、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是一個(gè)三層BP網(wǎng)絡(luò)示意圖．它由輸入層、隱層和輸出層構(gòu)成，相鄰層各個(gè)神經(jīng)元之間形成完全連接關(guān)系，而同一層內(nèi)各個(gè)神經(jīng)元之間沒有任何連接關(guān)系．n個(gè)輸入信號從輸入層進(jìn)入網(wǎng)絡(luò)，經(jīng)傳遞函數(shù)（一般為Sigmoid函數(shù)）變換后到達(dá)隱層，然后再經(jīng)傳遞函數(shù)（有時(shí)是線性函數(shù)）變換到輸出層構(gòu)成m個(gè)輸出信號．由于同層內(nèi)各個(gè)神經(jīng)元之間無耦合關(guān)系，每一層神經(jīng)元的輸出信號只影響下一層神經(jīng)元的輸入和輸出．不難看出，BP神經(jīng)網(wǎng)絡(luò)是一個(gè)從n維空間Rn的輸入到m維空間Rm的輸出的高度非線性映射，網(wǎng)絡(luò)通過對簡單的非線性函數(shù)（傳遞函數(shù)或稱之為單元特性函數(shù)）進(jìn)行數(shù)次復(fù)合，可以逼近一個(gè)非常復(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)個(gè)神經(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ò)的運(yùn)行參數(shù)，其值可由網(wǎng)絡(luò)通過學(xué)習(xí)已知的樣本知識獲得．人工神經(jīng)網(wǎng)絡(luò)計(jì)算流程如圖9.10所示．如何確定最佳的網(wǎng)絡(luò)結(jié)構(gòu)是目前神經(jīng)元網(wǎng)絡(luò)研究中的一個(gè)重要課題，它依賴于隱層和隱層神經(jīng)元個(gè)數(shù)多少的選?。覀冎?，如果具有無限個(gè)隱層神經(jīng)元，只有一個(gè)隱含層的前向神經(jīng)元網(wǎng)絡(luò)就可對連續(xù)函數(shù)進(jìn)行任意精度的逼近．另外，雖然在一般情況下，兩個(gè)隱含層的神經(jīng)元網(wǎng)絡(luò)比單隱含層的神經(jīng)元網(wǎng)絡(luò)具有更好的逼近能力，但在大多數(shù)應(yīng)用問題中，只有一個(gè)隱含層的神經(jīng)元網(wǎng)絡(luò)就已經(jīng)足夠了．當(dāng)隱層個(gè)數(shù)確定以后，我們還需要決定使用多少個(gè)隱層神經(jīng)元．一方面，太少的隱層神經(jīng)元會使網(wǎng)絡(luò)缺乏逼近能力．另一方面，太多的隱層神經(jīng)元又會增加訓(xùn)練時(shí)間且降低神經(jīng)元網(wǎng)絡(luò)的反應(yīng)速度．研究人員提出了許多種確定隱層神經(jīng)元個(gè)數(shù)的方法，它們的主要思想是在訓(xùn)練的過程中逐漸增加或減少隱層神經(jīng)元的數(shù)目．三、BP神經(jīng)網(wǎng)絡(luò)算法基本迭代步驟

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

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

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

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

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

(4)計(jì)算輸出層每個(gè)節(jié)點(diǎn)誤差值(對sigmoid函數(shù))

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

(5)計(jì)算前面各層每個(gè)節(jié)點(diǎn)誤差值．

這靠逐層反傳誤差獲得，其中直到將每層內(nèi)每個(gè)節(jié)點(diǎn)的誤差算完為止．(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é)科．盡管目前它只是大腦的低級近似，但它的很多特點(diǎn)和人類的智能特點(diǎn)類似．正是由于這些特點(diǎn)，使得神經(jīng)網(wǎng)絡(luò)不同于一般計(jì)算機(jī)和人工智能．（一）固有的并行結(jié)構(gòu)和并行處理人工神經(jīng)網(wǎng)絡(luò)與人類的大腦類似，不但結(jié)構(gòu)上是并行的，它的處理順序也是并行的和同時(shí)的．在同一層內(nèi)的處理單元都是同時(shí)操作的，即神經(jīng)網(wǎng)絡(luò)的計(jì)算功能分布在多個(gè)處理單元上．而一般計(jì)算機(jī)通常有一個(gè)處理單元，其處理順序是串行的．目前的神經(jīng)網(wǎng)絡(luò)功能常常用一般計(jì)算機(jī)的串行工作方式來模擬它的并行處理方式，所以顯得很慢，而真正的神經(jīng)網(wǎng)絡(luò)將會大大提高處理速度，并能實(shí)現(xiàn)實(shí)時(shí)處理．（二）知識的分布存儲

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