1第十一章

啟發(fā)式算法

2進入21世紀(jì)，盡管人們已經(jīng)可以讓計算機完成一些過去無法想象的任務(wù)，但仍有許多復(fù)雜的實際問題得不到很好的解決，如問題難度隨其規(guī)模呈指數(shù)增長的NP(非確定性多項式時間)難題。當(dāng)問題規(guī)模較大時，由于所謂的“組合爆炸”，導(dǎo)致計算機無法在現(xiàn)有的存儲空間和有效的時間內(nèi)求得問題的最佳答案，于是在實際應(yīng)用中，為得到一個現(xiàn)實的解決方案，人們往往放棄獲得問題最優(yōu)解的愿望，退而求其次，借助啟發(fā)式（Heuristic）方法來獲得問題的一個較好的滿意解決方案。3§11-1啟發(fā)式算法的基本概念§11-2經(jīng)典啟發(fā)式算法§11-3現(xiàn)代啟發(fā)式算法4§11-1啟發(fā)式算法的基本概念一、啟發(fā)式算法的定義與設(shè)計

啟發(fā)式算法是相對于最優(yōu)算法提出的。

☆

啟發(fā)式算法是一種基于直觀或經(jīng)驗構(gòu)造的算法。

☆

啟發(fā)式算法一種技術(shù)。

☆

不考慮算法所得解與最優(yōu)解的偏離程度。

啟發(fā)式算法的設(shè)計分為：

（1）數(shù)學(xué)途徑——用參數(shù)來體現(xiàn)最壞的情形，用于相當(dāng)簡單的標(biāo)準(zhǔn)問題。

（2）工程途徑——對實際問題的求解更為合適。

5§11-1啟發(fā)式算法的基本概念二、啟發(fā)式算法的策略

啟發(fā)式算法常用的策略：

（1）逐步構(gòu)解策略——根據(jù)一定的順序每次確定解的一個分量，直到產(chǎn)生解的所有分量為止。

（2）分解合成策略——將該問題分解為多個小規(guī)模的子問題，先求解子問題，再進行綜合。

（3）改進策略——從初始解出發(fā)，不斷對解改進。

（4）搜索學(xué)習(xí)策略——搜集信息，調(diào)整策略。

☆可以單獨使用一種策略，也可以幾種策略結(jié)合使用。

6§11-1啟發(fā)式算法的基本概念三、啟發(fā)式算法的分類

可以分為經(jīng)典啟發(fā)式算法和現(xiàn)代啟發(fā)式算法。

☆經(jīng)典啟發(fā)式方法，根據(jù)問題的部分已知信息來啟發(fā)式地探索該問題的解決方案。

☆

現(xiàn)代啟發(fā)式算法，又稱為元啟發(fā)式算法或者智能優(yōu)化算法，是近幾十年內(nèi)興起的一類新型算法，其思想吸收了許多其他學(xué)科中的思想、概念和方法。典型算法有：遺傳算法、模擬退火算法、禁忌搜索法、螞蟻算法、人工神經(jīng)網(wǎng)絡(luò)等。

7§11-1啟發(fā)式算法的基本概念三、啟發(fā)式算法的分類

可以分為經(jīng)典啟發(fā)式算法和現(xiàn)代啟發(fā)式算法?！罱?jīng)典啟發(fā)式方法，根據(jù)問題的部分已知信息來啟發(fā)式地探索該問題的解決方案?！?/p>

現(xiàn)代啟發(fā)式算法，又稱為元啟發(fā)式算法或者智能優(yōu)化算法，是近幾十年內(nèi)興起的一類新型算法，其思想吸收了許多其他學(xué)科中的思想、概念和方法。典型算法有：遺傳算法、模擬退火算法、禁忌搜索法、螞蟻算法、人工神經(jīng)網(wǎng)絡(luò)等。

8§11-2經(jīng)典啟發(fā)式算法一、貪婪經(jīng)典啟發(fā)式算法的基本思路

許多經(jīng)典啟發(fā)式算法都是基于貪婪搜索策略，要求每一次優(yōu)化搜索后的目標(biāo)函數(shù)值有所改進，重復(fù)上述過程直到目標(biāo)函數(shù)值無法改進為止，并以當(dāng)前解作為最終解。

貪婪啟發(fā)式算法的基本思路是：將問題的求解過程看作是一系列選擇，每次選擇都是當(dāng)前狀態(tài)下的最好選擇（局部最優(yōu)解）。每作一次選擇后，所求問題會簡化為一個規(guī)模更小的子問題，從而通過每一步的局部解逐步到達整體解。

貪婪啟發(fā)式算法不像單純形算法那樣有具體的計算步驟，而要對待求解問題進行具體分析，探討問題和算法間的聯(lián)系，并從中獲得啟發(fā)，設(shè)計求解問題的思路。9§11-2經(jīng)典啟發(fā)式算法一、經(jīng)典啟發(fā)式算法的求解步驟（一）背包問題

最常見的背包問題是0-1背包問題，可描述為：給定n個物品和一個背包，每個物品i的重量為wj、價值為pj（j=1,2,…,n），背包能容納的物品重量為c，現(xiàn)要從這n個物品中選出若干件放入背包，使得放入物品的總重量不超過c，且總價值達到最大。令變量則0-1背包問題模型可寫成如下的0-1整數(shù)線性規(guī)劃形式：10§11-2經(jīng)典啟發(fā)式算法一、經(jīng)典啟發(fā)式算法的求解步驟（一）背包問題在求解背包問題時，令ej=pj/wj表示物品j的價值密度，并規(guī)定的pj、wj和c都為正數(shù)，先作如下處理：

(1)移除wi>c的物品；

(2)若所有物品的wi之和≤c，則所有物品均可裝入，問題已不用求解；

(3)將物品按價值密度ej=pi/wi非增排序：11§11-2經(jīng)典啟發(fā)式算法一、經(jīng)典啟發(fā)式算法的求解步驟（一）背包問題綜上所述，貪婪啟發(fā)式算法求解0-1背包問題的步驟如下：Step1.將各物品按價值密度由高到低排序；Step2.選擇價值密度值最高者放入背包；Step3.計算背包剩余重量；Step4.在剩余物品中取價值密度最高者放入背包；Step5.放入物品的總重量達到最大重量限制，則算法終止。這里，以一個具體算例說明其求解過程。12§11-2經(jīng)典啟發(fā)式算法一、經(jīng)典啟發(fā)式算法的求解步驟（一）背包問題

例11-1在背包問題中，n=4，(wj)=(40,30,10,30)，(pj)=(200,180,30,120)，c=95。解按價值密度由高到低排序為第2、1、4、3個物品。第一步，將第2個物品裝入背包中，背包剩余重量為55；第二步，將第1個物品裝入背包中，背包剩余重量為25；第三步，將第4個物品裝入背包中，背包剩余重量為15，此時背包剩余重量小于第3個物品重量，算法停止。該背包問題的最優(yōu)解為x1*=x2*=x4*=1,x3*=0，最優(yōu)值z*=410。求解采用了逐步構(gòu)解策略，方法本身并不保證一定能獲得全局最優(yōu)解，但本例中得到的恰好是最優(yōu)解。13§11-2經(jīng)典啟發(fā)式算法一、經(jīng)典啟發(fā)式算法的求解步驟（二）旅行商問題有一個旅行商從城市1出發(fā)，需要到城市2、3、…、n去推銷貨物，最后返回城市1，若任意兩個城市間的距離已知，則該旅行商應(yīng)如何選擇其最佳行走路線？記為賦權(quán)圖，為頂點集，為邊集，各頂點間的距離已知。設(shè)14§11-2經(jīng)典啟發(fā)式算法一、經(jīng)典啟發(fā)式算法的求解步驟（二）旅行商問題則經(jīng)典的TSP可寫為如下的數(shù)學(xué)規(guī)劃模型：模型中，為集合中所含圖的頂點數(shù)。前兩個約束意味著對每個點而言，僅有一條邊進和一條邊出；第三個約束則保證了沒有任何子回路解的產(chǎn)生。于是，滿足所有約束的解構(gòu)成了一條Hamilton回路。15§11-2經(jīng)典啟發(fā)式算法一、經(jīng)典啟發(fā)式算法的求解步驟（二）旅行商問題這里以一個具體算例，采用改進策略設(shè)計貪婪啟發(fā)式算法。例11-2在有7個城市的旅行商問題中，分別用A、B、C、D、E、F和G表示，對應(yīng)位置坐標(biāo)分別為（10，23）、（0，13）、（1，0）、（21，2）、（14，3）、（11，6）和（10，10）。解首先構(gòu)造一個初始可行解，例如以A點為起點（也可以取其他點為起點）的一條Hamilton回路為AFCGDBEA，路徑總長度為114.50。16§11-2經(jīng)典啟發(fā)式算法一、經(jīng)典啟發(fā)式算法的求解步驟（二）旅行商問題

采用2-opt方法對初始解進行改進，算法產(chǎn)生的最好Hamilton回路為ABCDEFGA（見圖11-2），路徑總長度為75.48。這里，2-opt方法是一種局部搜索算法，對給定的初始回路解，每次交換兩條邊來進行改進。該啟發(fā)式算法并不保證一定得到最優(yōu)解，但本例中獲得的恰好是最優(yōu)解。17§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（一）基本思想

遺傳算法GA是一種來自生物進化理論中“自然選擇、適者生存”原則的搜索（尋優(yōu)）算法，其基本思想源于生物學(xué)的自然選擇原理和遺傳機制，用模擬生命進化的方式來尋找問題的最優(yōu)解。這種新發(fā)展起來的完全異于傳統(tǒng)思想的搜索和優(yōu)化方法自JohnHolland等人在1975年提出以來，獲得了廣泛的應(yīng)用。遺傳算法用于優(yōu)化問題時，其最主要特征就是：（1）它不在單點上尋優(yōu)，而是從整個種群中選擇生命力強的個體來產(chǎn)生新的種群；（2）它使用隨機轉(zhuǎn)換原理而不是確定性規(guī)則來工作。

18§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（二）基本算子

遺傳算法中常用的遺傳操作包括三個基本算子：選擇、交叉和變異。以下給出這三種操作的實現(xiàn)方式：

1、選擇。

從當(dāng)前群體中選擇適應(yīng)度函數(shù)值大的個體，使這些優(yōu)良個體有可能作為父代來繁殖下一代。選擇操作直接體現(xiàn)了“適者生存、優(yōu)勝劣汰”的原則。在該階段，個體的適應(yīng)度函數(shù)值越大，被選擇作為父代的概率也越大；個體的適應(yīng)度函數(shù)值越小，被淘汰的概率也越大。

19§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（二）基本算子2、交叉。

在生物進化中，兩個個體通過交叉互換染色體部分基因而重組產(chǎn)生新個體。在遺傳算法中，交叉是產(chǎn)生新解的重要操作。要進行交叉操作，首先需要解決配對問題，采用隨機配對是最基本的方法。一般情況下，對二進制編碼的個體采用點交叉方法。所謂點交叉，就是在兩個配對字符串隨機選擇一個或多個交叉點，互換部分子串從而產(chǎn)生新的字符串。如果只選擇一個交叉點，則稱為單點交叉。以此類推，還有兩點交叉以及多點交叉。20§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（二）基本算子

3、變異。

生物進化中，由于偶然因素，染色體某個（些）基因會發(fā)生突變，從而產(chǎn)生新的染色體。在遺傳算法中，變異是產(chǎn)生新解的另一種操作。交叉操作相當(dāng)于進行全局探索，變異操作則相當(dāng)于進行局部開發(fā)，而全局探索和局部開發(fā)是智能優(yōu)化算法必備的兩種搜索能力。對二進制編碼的染色體進行變異操作，相當(dāng)于進行補運算，即將字符0變?yōu)?，或?qū)⒆址?變?yōu)?。

21§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（三）主要步驟

Step1.產(chǎn)生初始群體。

Step2.計算每個個體適應(yīng)度函數(shù)值。

Step3.選擇進入到下一代群體中的個體。

Step4.兩兩配對的個體進行交叉操作以產(chǎn)生新個體。

Step5.新個體進行變異操作。

Step6.將群體中迄今出現(xiàn)的最好個體直接復(fù)制到下一代中(精英保留策略)

Step7.反復(fù)執(zhí)行Step2到Step6，直到滿足算法終止條件。

22§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例1.二進制編碼法

例11-3MaxZ=x2，x∈[0,31]，x為整數(shù)。

（1）采用5位二進制編碼表示[0,31]上的整數(shù)。

由于變量最大值是31，故可采用5位二進制編碼表示，如：10000→16，11111→31，01001→9，00010→2上述編碼稱為染色體，每個二進制位稱為基因。

23§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例1.二進制編碼法

例11-3MaxZ=x2，x∈[0,31]，x為整數(shù)。

（2）產(chǎn)生初始種群。

現(xiàn)隨機取4個染色體構(gòu)成一個群組：

x1=(00000)，x2=(11001)，x3=(01111)，x4=(01000)。適應(yīng)度函數(shù)可根據(jù)目標(biāo)函數(shù)而定，現(xiàn)采用fitness(x)=f(x)=x2。于是，fitness(x1)

=0，fitness(x2)

=252=625，fitness(x3)=152=225，fitness(x4)=82=64。

24§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例1.二進制編碼法

例11-3MaxZ=x2，x∈[0,31]，x為整數(shù)。

（2）產(chǎn)生初始種群。

定義第i個個體入選種群的概率

為

其中，n表示群體規(guī)模。

則各個體的選擇概率為：

=0，=625/914=0.68，

=225/914=0.25，

=64/914=0.07。

基于選擇概率定義累積概率，第i個個體的累積概率為25§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例1.二進制編碼法

例11-3MaxZ=x2，x∈[0,31]，x為整數(shù)。

（3）采用輪盤賭法，確定被選中的個體。

隨機產(chǎn)生在0到1之間服從均勻分布的隨機數(shù)

，當(dāng)時，則選擇個體i。重復(fù)上述步驟n次，就可以選擇n個個體。

經(jīng)過計算，x2被選中2次，x3和x4各被選中1次。

現(xiàn)對新群體進行如下交叉操作：

26§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例2.路徑表示法

例11-4考慮5個城市的對稱TSP問題：

（1）構(gòu)造初始群組：

p1={1,2,3,4,5}，p2={2,1,4,3,5}，

p3={1,3,4,2,5}，p4={3,4,5,1,2}

（2）計算評價函數(shù)值（計算每個個體的路長）：f(p1)=10+8+20+5+2=45f(p2)=10+6+20+15+9=60f(p3)=15+20+13+9+2=59f(p4)=20+5+2+10+8=4527§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例2.路徑表示法

（3）比較評價函數(shù)值并排序，進行選擇后得：

p1，p4，p3，p2

（4）復(fù)制與刪除：

刪除p3、p2，保留p1、p4并依次復(fù)制到p1、p2，得

p1={1,2,3,4,5}，p2={3,4,5,1,2}

f(p1)=10+8+20+5+2=45，

f(p2)=20+5+2+10+8=4528§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例2.路徑表示法

（5）交叉與變異

(a)交叉算子

對個體p1、p2，交叉點為2和4，交叉位置以“|”標(biāo)記，則有：p1={1,|2,3,4,|5}，p2={3,|4,5,1,|2}

按下述方式產(chǎn)生后代：

①首先，交叉點之間的片段被拷貝到后代里：

o1=（#,|2,3,4,|#），o2=（#,|4,5,1,|#）

其中“#”表示待定。29§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例2.路徑表示法

（5）交叉與變異

(a)交叉算子

②為得到后代o1，我們只需要移走p2中已在o1中的城市2、3和4后，得到5-1，并將該序列順次放在o1中，并令

p3=o1=（5,|2,3,4,|1），

f(p3)=f(o1)=9+8+20+6+2=45

類似地，為得到后代o2，令

p4=o2=（2,|4,5,1,|3），

f(p4)=f(o2)=13+5+2+15+8=4330§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例2.路徑表示法

（5）交叉與變異

(b)比較評價函數(shù)值并排序，得：

p4，p1，p2，p3。

刪除p2、p3，保留p4、p1，并依次復(fù)制到p1、p2，得

p1={2,4,5,1,3}，

p2={1,2,3,4,5}，

f(p1)=1+3+2+2+2=43，

f(p2)=1+2+2+2+4=4531§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例2.路徑表示法

（5）交叉與變異

(c)變異算子

采用倒置變異，即在染色體上隨機地選擇兩點，將兩點間的子串反轉(zhuǎn)。如，原個體：

p1={2,4,5,1,3}，p2={1,2,3,4,5}

隨機選擇兩點：p1={2,4,|5,1,|3},p2={1,|2,3,|4,5}

倒置后得個體：p3={2,4,|1,5,|3},p4={1,|3,2,|4,5}

f(p3)=13+6+2+15+8=44，

f(p4)=15+8+13+5+2=4332§11-3現(xiàn)代啟發(fā)式算法一、遺傳算法（四）范例2.路徑表示法

（5）交叉與變異

(d)比較評價函數(shù)值并排序，得：

p1，p4，p3，p2。刪除p3、p2，保留p1、p4，并依次復(fù)制到p1、p2，得p1={2,4,5,1,3}，p2=p4={1,3,2,4,5}，f(p1)=13+5+2+15+8=43，f(p2)=15+8+13+5+2=43

（6）可對得到的p1、p2繼續(xù)前述運算。若在此時結(jié)束計算，則得到的解為p1={2,4,5,1,3}，f(p1)=43。

即此時的TSP回路為{2,4,5,1,3}，回路總長為43。33§11-3現(xiàn)代啟發(fā)式算法二、模擬退火算法（一）基本思想

模擬退火法SA的思想最早由Metropolis于1953年提出，Kirkpatrick在1983年成功地將其應(yīng)用于組合最優(yōu)化問題中。

模擬退火算法源自物理學(xué)，其出發(fā)點是將組合優(yōu)化問題與統(tǒng)計力學(xué)的熱平衡作類比，把優(yōu)化的目標(biāo)函數(shù)視作能量函數(shù)，模擬物理學(xué)中固體物質(zhì)的退火處理，先加溫使之具有足夠高的能量，然后再逐漸降溫，其內(nèi)部能量也相應(yīng)下降，在熱平衡條件下，物體內(nèi)部處于不同狀態(tài)的概率服從Boltzman分布，若退火步驟恰當(dāng)，則最終會形成最低能量的基態(tài)。34§11-3現(xiàn)代啟發(fā)式算法二、模擬退火算法（一）基本思想

該算法思想在求解優(yōu)化問題時，不但接受對目標(biāo)函數(shù)(能量函數(shù))有改進的狀態(tài)，還以某種概率接受使目標(biāo)函數(shù)惡化的狀態(tài)，從而可使之避免過早收斂到某個局部極值點，也正是這種概率性的擾動，使之能夠跳出局部極值點，故而得到的解常常很好。35§11-3現(xiàn)代啟發(fā)式算法二、模擬退火算法（二）主要過程

可用如下的偽碼表示。其中，T(t)為降溫函數(shù)，N(t)為鄰域狀態(tài)生成函數(shù)，其作用是產(chǎn)生反復(fù)次數(shù)。36§11-3現(xiàn)代啟發(fā)式算法二、模擬退火算法（二）主要過程

常用的降溫函數(shù)和鄰域狀態(tài)生成函數(shù)形式有：

T(t)=C；T(t)=T(t-1)+C；

T(t)=α(t)T(t-1),α(t)<1；T(t)=C/ln(t+1)；

N(t)=C；N(t)=N(t-1)+C；等等，這里C為常數(shù)。

停機判別條件可選擇：⑴達到一定的降溫次數(shù)；(2)溫度低于給定的最低溫度；(3)目標(biāo)函數(shù)無改進；等等。

初始溫度可選取目標(biāo)函數(shù)在定義域上的上下限之差(或其大致估計值)。37§11-3現(xiàn)代啟發(fā)式算法二、模擬退火算法（三）范例

例11-5根據(jù)標(biāo)準(zhǔn)問題庫TSPLIB的算例ulysses

16,共有16個城市,城市序號分別用1~16表示，對應(yīng)位置的坐標(biāo)為：

(38.24,20.42),(39.57,26.15),(40.56,25.32),(36.26,23.12)(33.48,10.54),(37.56,12.19),(38.42,13.11),(37.52,20.44),

(41.23,9.10),(41.17,13.05),(36.08,5.21),(38.47,15.13),

(38.15,15.35),(37.51,15.17),(35.49,14.32),(39.36,19.56)

解采用運籌學(xué)—管理科學(xué)集成軟件包，迭代100次，可得問題的解為：

初始回路總長=107，改進回路總長=69，回路路徑={8,4,2,3,16,12,7,6,10,9,11,5,15,14,13,13}。38§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（一）基本思想

F.Glover在1986年首次提出禁忌搜索TS這一概念，進而形成一套完整的優(yōu)化算法。TS的基本思想相當(dāng)簡單，它采用了一種“記憶”裝置，驅(qū)使算法去探索解空間的新區(qū)域而達到禁止重復(fù)已做過的搜索工作，具體操作中采用一個禁忌表來記錄已經(jīng)到達過的局部最優(yōu)點，使得在以后一段時期的搜索中，不再重復(fù)搜索這些解，以此來跳出局部極值點。

禁忌搜索中被禁止的元素依靠不斷演變的存儲來接受其狀態(tài)，這種存儲允許元素的禁忌狀態(tài)根據(jù)時間和環(huán)境來變化。39§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（二）基本流程（以函數(shù)f(x)的極小化為例）

與遺傳算法、模擬退火法類似，禁忌搜索法的運行效果也在很大程度上受其有關(guān)參數(shù)的影響。40§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（三）相關(guān)參數(shù)

1.禁忌對象、長度和候選集

解狀態(tài)的變化分為：解的簡單變化、解向量分量的變化和目標(biāo)值變化，因此，禁忌對象的選取可以是其中任何一種。

在算法的構(gòu)造和計算過程中，一方面要求占用盡量少的內(nèi)存，即禁忌長度、侯選集合盡可能小。但另一方面，禁忌長度過短會造成搜索的循環(huán)，候選集合過小會造成過早陷入局部最優(yōu)。因此，它們的選取同實際問題、試驗和設(shè)計者的經(jīng)驗有緊密聯(lián)系。41§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（三）相關(guān)參數(shù)

2.破禁水平

由“AspirationLevel”一詞翻譯而來，亦稱為藐視準(zhǔn)則、破忌條件、特赦規(guī)則等。在TS的迭代過程中，候選集中的全部對象或某一對象會被禁忌，但如果解禁，則其目標(biāo)值會有較大改善，在這種情況下，為達到全局最優(yōu)，可讓一些禁忌對象重新可選，這種方法稱為破禁。

42§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（三）相關(guān)參數(shù)

3.記憶頻率

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

4.終止規(guī)則TS的停止規(guī)則通常有兩種，一種是將最大迭代次數(shù)作為停止算法的標(biāo)準(zhǔn)；另一種是在給定次數(shù)的迭代內(nèi)所發(fā)現(xiàn)的最好解無法改進或無法跳出時，停止計算。43§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（四）范例

例11-6求解例11-4中的TSP。解將5個頂點依次記為A、B、C、D、E。禁忌對象為簡單的解變化，禁忌表H只記憶三個被禁的解，即禁忌長度為3。解的鄰域采用2-交換法，即交換解序列中某2個點以構(gòu)成新的解序列。第0步：初始解x0=（ABCDE），f(x0)=45；xnow=x0；從當(dāng)前鄰域中選出最佳的五個解構(gòu)成侯選集Can_N(xnow)。

44§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（四）范例

第1步：

xnow=（ABCDE），f(xnow)=45，H=Φ={}，Can_N(xnow)={（ABCDE；45），（ACBDE；43），（ADCBE；45），（ABEDC；59），（ABCED；44）}；由于禁忌表H為空，因此，從候選集中選出最好的一個，并將之加入到禁忌表中，xnext=（ACBDE），H={(ACBDE；43)}。

45§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（四）范例

第2步：

xnow=（ACBDE），f(xnow)=43，H={(ACBDE；43)}，Can_N(xnow)={（ACBDE；43），（ACBED；43），（ADBCE；44），（ABCDE；45），（ACEDB；58）}；

由于（ACBDE；43）在禁忌表受禁，所以選xnext=（ACBED），并將之加入到禁忌表中，得H={（ACBDE；43）；（ACBED；43）}。

46§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（四）范例

第3步：

xnow=（ACBED），f(xnow)=43，H={(ACBDE；43)；(ACBED；43)}，Can_N(xnow)={（ACBED；43），（ACBDE；43），（ABCED；44），（AEBCD；45），（ADBEC；58）}；由于H={（ACBDE；43）；（ACBED；43）}受禁，所以選xnext=（ABCED），并將之加入到禁忌表中，得H={（ACBDE；43）；（ACBED；43）；（ABCED；44）}。

47§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（四）范例

第4步

xnow=（ABCED），f(xnow)=44，H={（ACBDE；43）；（ACBED；43）；（ABCED；44）}，Can_N(xnow)={（ACBED；43），（AECBD；44），（ABCDE；45），（ABCED；44），（ABDEC；58）}；由于H={（ACBDE；43）；（ACBED；43）；（ABCED；44）}受禁，所以選xnext=（AECBD），此時H中已達3個解，新加入到禁忌表中的解須替代最早被禁的解，得H={（ACBED；43）；（ABCED；44）；（AECBD；44）}。

48§11-3現(xiàn)代啟發(fā)式算法三、禁忌搜索算法（四）范例

第5步：

xnow=（AECBD），f(xnow)=44，H={（ACBED；43）；（ABCED；44）；（AECBD；44）}，Can_N(xnow)={（AEDBC；43），（ABCED；44），（AECBD；44），（AECDB；44），（AEBCD；45）}；由于H={（ACBED；43）；（ABCED；44）；（AECBD；44）}受禁，所以選xne