3搜索問題-啟發(fā)式搜索

搜索問題1啟發(fā)式搜索啟發(fā)式搜索，也稱為有信息搜索，借助問題的特定知識(shí)來幫助選擇搜索方向在搜索過程中對(duì)待擴(kuò)展的每一個(gè)節(jié)點(diǎn)進(jìn)行評(píng)估，得到最好的位置，再從這個(gè)位置進(jìn)行搜索直到目標(biāo)。啟發(fā)式搜索的目的是省略大量無謂的搜索路徑，提到效率。在啟發(fā)式搜索中，對(duì)節(jié)點(diǎn)的評(píng)價(jià)是十分重要的，評(píng)價(jià)函數(shù)是搜索成敗的關(guān)鍵。啟發(fā)式搜索評(píng)價(jià)函數(shù)，也稱為啟發(fā)函數(shù)提供問題的啟發(fā)性信息，按其用途劃分，可分為以下三類：用于擴(kuò)展節(jié)點(diǎn)的選擇，即用于決定應(yīng)先擴(kuò)展哪一個(gè)節(jié)點(diǎn)，以免盲目擴(kuò)展用于生成節(jié)點(diǎn)的選擇，即用于決定應(yīng)生成哪些后續(xù)節(jié)點(diǎn)，以免盲目地生成過多無用節(jié)點(diǎn)用于刪除節(jié)點(diǎn)的選擇，即用于決定應(yīng)刪除哪些無用節(jié)點(diǎn)，以免造成進(jìn)一步的時(shí)空浪費(fèi)啟發(fā)式搜索一個(gè)節(jié)點(diǎn)n的評(píng)價(jià)函數(shù)的構(gòu)造通常由兩部分構(gòu)成從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的路徑耗散從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的期望耗散即：評(píng)價(jià)函數(shù)可表示為：這兩部分里，通常是比較明確的，容易得到而難以構(gòu)造，也沒有固定的模式，需要根據(jù)具體問題分析利用知識(shí)來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉鳎赡芸梢哉业阶顑?yōu)解啟發(fā)式圖搜索引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。希望：定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來擴(kuò)展?；舅枷朐u(píng)價(jià)函數(shù)的格式：

f(n)=g(n)+h(n) f(n)：評(píng)價(jià)函數(shù)

h(n)：啟發(fā)函數(shù)g(x)——從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的實(shí)際代價(jià)；h(x)——從x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的評(píng)估代價(jià)，它體現(xiàn)了問題的啟發(fā)式信息，其形式要根據(jù)問題的特性確定，h(x)稱為啟發(fā)式函數(shù)。1、啟發(fā)式搜索算法A（A算法）g*(n)：從s到n的最短路徑的耗散值h*(n)：從n到g的最短路徑的耗散值f*(n)=g*(n)+h*(n)：從s經(jīng)過n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值定義開始把S放入OPEN表，計(jì)算估價(jià)函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點(diǎn)i放入CLOSED表i為目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展i，得后繼節(jié)點(diǎn)j，計(jì)算f(j)，提供返回節(jié)點(diǎn)i的指針，利用f(j)對(duì)OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功有序搜索算法框圖是否是否算法A算法1.Open:=(s)，f(s):=g(s)+h(s);2.LOOP:IFOpen=()THENEXIT(FAIL);3.n:=FIRST(OPEN);4.IFGOAL(n)THENEXIT(SUCCESS);5.

REMOVE(n,Open),ADD(n,Closed);

6.EXPAND(n)→(mi)，把mi作為n的后繼節(jié)點(diǎn)添入G，計(jì)算

f(n→mi)=g(n→mi)+h(mi)；6-1)ADD(mj,Open);6-2)IFf(n→mk)<f(mk)THENf(mk):=f(n→mk);6-3)IFf(n→ml)<f(ml)THENf(ml):=f(n→ml);ADD(ml,Open);7.Open中的節(jié)點(diǎn)按f

值從小到大排序;

8.

GOLOOP;算法的說明：A算法由一般的圖搜索算法改變而成。算法第7步每次按照f(n)值的大小對(duì)Open表中的元素進(jìn)行排序，f(n)值小的節(jié)點(diǎn)排在前面，而f(n)值大的節(jié)點(diǎn)則放在Open表的后面，這樣每次擴(kuò)展節(jié)點(diǎn)時(shí)，都選擇當(dāng)前f(n)值最小的節(jié)點(diǎn)來優(yōu)先擴(kuò)展。A算法是按f(n)遞增的順序來排列Open表中節(jié)點(diǎn)的，因而優(yōu)先擴(kuò)展f(n)值小的節(jié)點(diǎn)，體現(xiàn)了好的優(yōu)先搜索的思想，所以算法A是一個(gè)好的優(yōu)先搜索策略。擴(kuò)展n后新生成的子節(jié)點(diǎn)m1({mj})、m2({mk})、m3({ml})分別計(jì)算評(píng)價(jià)函數(shù)值：f(m1)=g(m1)+h(m1)f(n,m2)=g(n,m2)+h(m2)f(n,m3)=g(n,m3)+h(m3)按第6步比較不同路徑的耗散值并進(jìn)行相應(yīng)的指針修正.snf(n)m2m1m3m31m32f(m3)f(m1)f(m2)f(m31)f(m32)圖2-12搜索示意圖定義評(píng)價(jià)函數(shù)：

f(x)=d(x)+w(x)

d(x)表示節(jié)點(diǎn)在x搜索樹中的深度，w(x)表示節(jié)點(diǎn)x中不在目標(biāo)狀態(tài)中相應(yīng)位置的數(shù)碼個(gè)數(shù)，w(x)就包含了問題的啟發(fā)式信息。一般來說某節(jié)點(diǎn)的w(x)越大，即“不在目標(biāo)位”的數(shù)碼個(gè)數(shù)越多，說明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)。

一個(gè)A算法的例子2831647512384765對(duì)初始節(jié)點(diǎn)S0，由于d(S0)=0，w(S0)=5，因此f(S0)=5。在搜索過程中除了需要計(jì)算初始節(jié)點(diǎn)的評(píng)估函數(shù)外，更多的是需要計(jì)算新生節(jié)點(diǎn)的評(píng)估函數(shù)。

w(n)=4h計(jì)算舉例2

831

64751234576

8由CLOSED表可知，解路徑為S0-S2-S5-S9-S11-S122831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)123456OPEN和CLOSED表的元素排列如下：

OPEN表：1）初始化（s（4））2）第一循環(huán)結(jié)束（B（4）A（6）C（6））3)第二循環(huán)結(jié)束（D（5）E（5）A（6）C（6）F（6））4)第三循環(huán)結(jié)束（E（5）A（6）C（6）F（6）G（6）H（7））5)第四循環(huán)結(jié)束（I（5）A（6）C（6）F（6）G（6）H（7）J（7））6)第五循環(huán)結(jié)束（K（5）A（6）C（6）F（6）G（6）H（7）J（7））7)第六循環(huán)結(jié)束（L（5）A（6）C（6）F（6）G（6）H（7）J（7）M（7））第七循環(huán)結(jié)束在算法第4步成功退出CLOSED表：1)（）2)（s（4））3)（s（4）B（4））4)（s（4）B（4）D（5））5)（s（4）B（4）D（5）E（5））6)（s（4）B（4）D（5）E（5）I（5））7)（s（4）B（4）D（5）E（5）I（5）K（5））啟發(fā)式搜索A算法的表現(xiàn)極大地依賴于評(píng)價(jià)函數(shù)，特別是h(n),即：從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最佳路徑的估計(jì)耗散假定h*(n)表示節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最佳路徑的實(shí)際耗散如果h(n)>

h*(n),搜索的節(jié)點(diǎn)數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。如果h(n)<=h*(n)

，這種情況下，搜索的節(jié)點(diǎn)數(shù)多，搜索范圍大，效率低，但能得到最優(yōu)解啟發(fā)式搜索滿足h(n)<=h*(n)

條件的A搜索，稱為A*(A-star)搜索A*搜索中，h(n)越接近h*(n)

，搜索效率越高寬度優(yōu)先算法可以看作A*算法的特例，即：g(n)是節(jié)點(diǎn)所在的層數(shù)，h(n)=0

代價(jià)樹寬度搜索也可以看作A*算法的特例，即：g(n)是節(jié)點(diǎn)n的實(shí)際路徑耗散，h(n)=0跟前兩個(gè)算法一樣，A*算法也具有完備性和最優(yōu)性啟發(fā)式搜索例：八數(shù)碼問題啟發(fā)函數(shù)1：h1(n)=不在位的數(shù)碼的總數(shù)問題1：圖中S0狀態(tài)h(S0)是什么，h*(S0)

又是什么問題2：這個(gè)啟發(fā)函數(shù)是否一定滿足h(n)<=h*(n)

問題3：對(duì)于八數(shù)碼問題，還能提出其他的啟發(fā)函數(shù)嗎？h(S0)=4啟發(fā)式搜索例：八數(shù)碼問題啟發(fā)函數(shù)2：h2(n)=所有數(shù)碼到目標(biāo)位置的距離和（曼哈頓距離）問題1：圖中S0狀態(tài)h(S0)是什么，h*(S0)

又是什么問題2：這個(gè)啟發(fā)函數(shù)是否一定滿足h(n)<=h*(n)

數(shù)碼1：1數(shù)碼2：1數(shù)碼3：0數(shù)碼4：0數(shù)碼5：0數(shù)碼6：1數(shù)碼7：0數(shù)碼8：2h2(S0)=5啟發(fā)式搜索A*算法當(dāng)h(n)<=h*(n)

時(shí)，同時(shí)滿足完備性和最優(yōu)性要求h(n)越接近于真實(shí)耗散h*(n)，算法的搜索效率越高，對(duì)內(nèi)存和時(shí)間的需求越小如果滿足h(n)=h*(n)，是最完美的A*算法h(n)的設(shè)計(jì)是A*算法的核心，也是最困難的地方完備的：如果存在解，則一定能找到該解最優(yōu)的可納的：如果存在解，則一定能找到最優(yōu)解搜索目標(biāo)時(shí)的搜索空間的節(jié)點(diǎn)數(shù)是目標(biāo)深度的指數(shù)，搜索過程中的復(fù)雜性呈指數(shù)級(jí)增長。并且，它在內(nèi)存空間中保存了所有的節(jié)點(diǎn)。A*算法分析2.5.3 分支限界法

分支限界法是優(yōu)先擴(kuò)展當(dāng)前具有最小耗散值分支路徑的葉節(jié)點(diǎn)n，其評(píng)價(jià)函數(shù)為f(n)=g(n)。其思想是：建立一個(gè)局部路徑（或分支）的隊(duì)列表，每次都選耗散值最小的那個(gè)分支上的葉節(jié)點(diǎn)來擴(kuò)展，直到生成含有目標(biāo)節(jié)點(diǎn)的路徑為止。分支界限法(最小代價(jià)優(yōu)先法)

●基本思想是：每次從OPEN表中選出g(x)值最小的節(jié)點(diǎn)進(jìn)行考察,而不管這個(gè)節(jié)點(diǎn)在搜索樹的什么位置上。

●算法與前面的“全局擇優(yōu)法”

僅有引導(dǎo)搜索的函數(shù)不同，前者為啟發(fā)函數(shù)h(x)，后者為代價(jià)g(x)。

●注意：代價(jià)值g(x)是從初始節(jié)點(diǎn)So方向計(jì)算而來的,而啟發(fā)函數(shù)值h(x)則是朝目標(biāo)節(jié)點(diǎn)方向計(jì)算的。

分支限界法

過程Branch-Bound1）QUEUE：=（s-s），g（s）=0；2）LOOP：IFQUEUE=（）THENEXIT（FAIL）；3）PATH：=FIRST（QUEUE），n：=LAST（PATH）；4）IFGOAL（n）THENEXIT（SUCCESS）；5）EXPAND（n）→{mi}，計(jì)算g（mi）=g（n，mi），REMOVE（s-n，QUEUE），ADD（s-n-mi，QUEUE）；6）QUEUE中局部路徑g值最小者排在前面；7）GOLOOP；例：八城市地圖網(wǎng)問題應(yīng)用分支限界法求解圖2-14的最短路徑問題，其搜索圖如圖2-15所示。

圖2-14 八城市地圖網(wǎng)示意圖SDBDCEDFEBFABEBFACtg=01g=3A2g=4g=7g=83g=9g=64g=11g=105g=11g=126g=107g=139g=15g=148g=1310g=15g=151112g=14g=1613圖2-15 分支限界搜索圖求解過程中QUEUE的結(jié)果：

初始（s（0））1）（A（3）D（4））2）（D（4）B（7）D（8））3）（E（6）B（7）D（8）A（9））4）（B（7）D（8）A（9）F（10）B（11））5）（D（8）A（9）F（10）B（11）C（11）E（12））6）（A（9）F（10）E（10）B（11）C（11）E（12））7）（F（10）E（10）B（11）C（11）E（12）B（13））8）（E（10）B（11）C（11）E（12）t（13)B（13）)9）（B（11）C（11）E（12）t（13）B（13）F（14）B（15））10）（C（11）E（12）t（13）B（13）F（14）B（15）A（15)C（15））11）（E（12）t（13）B（13）F（14）B（15）A（15）C（15））12）（t（13）B（13）F（14）D（14）B（15）A（15）C（15）F（16））13）結(jié)束。2.5.4 動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃法實(shí)際上是對(duì)分支限界法的改進(jìn)。動(dòng)態(tài)規(guī)劃原理指出，求s→t的最佳路徑時(shí)，對(duì)某個(gè)中間節(jié)點(diǎn)I，只考慮s到I中具有最小耗散值這一條局部路徑就可以，其余s到I的路徑是多余的。如果對(duì)于任何n，當(dāng)h(n)=0時(shí)，A*算法就成為了動(dòng)態(tài)規(guī)劃算法。具有動(dòng)態(tài)規(guī)劃原理的分支限界算法過程Dynamic-Programming1）QUEUE：=（s-s），g（s）=0；2）LOOP：IFQUEUE：=（）THENEXIT（FAIL）；3）PATH：=FIRST（QUEUE），n：=LAST（PATH）；4）IFGOAL（n）THENEXIT（SUCCESS）；5）EXPAND（n）→{mi}，計(jì)算g（mi）=g（n，mi），REMOVE（s-n，QUEUE），ADD（s-mi，QUEUE）；6）QUEUE中有多條到達(dá)某一公共節(jié)點(diǎn)的路徑時(shí)，只保留耗散值最小的那條路徑，其余刪去，并重新排序，g值最小者排在前面；7）GOLOOP；SAD1g=0g=3g=42BDg=7g=8×3AEg=9g=6×4BFg=11g=10×5ECg=11g=12×6tg=13圖2-16 動(dòng)態(tài)規(guī)劃原理的搜索樹動(dòng)態(tài)規(guī)劃st第一階段第二階段第三階段第四階段第五階段加權(quán)狀態(tài)圖搜索加權(quán)狀態(tài)圖與代價(jià)樹設(shè)A城是出發(fā)地,E城是目的地,邊上的數(shù)字代表兩城之間的交通費(fèi)。試求從A到E最小費(fèi)用的旅行路線。

代價(jià)樹的搜索。所謂代價(jià)，可以是兩點(diǎn)之間的距離、交通費(fèi)用或所需時(shí)間等等。通常用g(x)表示從初始節(jié)點(diǎn)So到節(jié)點(diǎn)x的代價(jià),用c(xi,xj)表示父節(jié)點(diǎn)xi到子節(jié)點(diǎn)xj的代價(jià),即邊(xi,xj)的代價(jià)。從而有

g(xj)＝g(xi)＋c(xi,xj)而

g(So)＝0旅行商問題（Traveling-SalesmanProblem，TSP）設(shè)有n個(gè)互相可直達(dá)的城市,某推銷商準(zhǔn)備從其中的A城出發(fā),周游各城市一遍,最后又回到A城。要求為該推銷商規(guī)劃一條最短的旅行路線。

該問題的狀態(tài)為以A打頭的已訪問過的城市序列:A…

So:A。

Sg:A,…,A。其中“…”為其余n-1個(gè)城市的一個(gè)序列。

狀態(tài)轉(zhuǎn)換規(guī)則：

規(guī)則1

如果當(dāng)前城市的下一個(gè)城市還未去過,則去該城市,并把該城市名排在已去過的城市名序列后端。

規(guī)則2

如果所有城市都去過一次,則從當(dāng)前城市返回A城,把A也添在去過的城市名序列后端。

狀態(tài)圖表示（簡化）一個(gè)問題的狀態(tài)圖是一個(gè)三元組

(S,F,G)

其中S是問題的初始狀態(tài)集合,F是問題的狀態(tài)轉(zhuǎn)換規(guī)則集合,G是問題的目標(biāo)狀態(tài)集合。一個(gè)問題的全體狀態(tài)及其關(guān)系就構(gòu)成一個(gè)空間,稱為狀態(tài)空間。所以,狀態(tài)圖也稱為狀態(tài)空間圖。

例迷宮問題的狀態(tài)圖表示。

S：SoF：｛(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)｝G：SgX1X2X3X８X0X4X7X6X5八數(shù)碼難題的狀態(tài)圖表示。

用向量

A＝(X0,X1,X2,X3,X4,X5,X6,X7,X8)表示,Xi為變量,Xi的值就是所在方格內(nèi)的數(shù)字。于是,向量A就是該問題的狀態(tài)表達(dá)式。我們將棋局

設(shè)初始狀態(tài)和目標(biāo)狀態(tài)分別為

So＝(0,2,8,3,4,5,6,7,1)

Sg＝(0,1,2,3,4,5,6,7,8)

例：在下圖所示的由17根火柴組成的圖案中，去掉5根火柴，使圖案形成三個(gè)小正方形。解：（1）以火柴棍為單位進(jìn)行去除操作，需要實(shí)驗(yàn)的總次數(shù)是 次。（2）以小方塊為單位進(jìn)行去除操作，需要實(shí)驗(yàn)的總次數(shù)是 次。（3）考慮到火柴去掉5根后還有12根，要形成三個(gè)小方塊，那么這三個(gè)小方塊不能有公共邊，在此圖案中僅有兩種可能。狀態(tài)圖搜索策略小結(jié)爬山法搜索模擬退火搜索局部剪枝搜索局部搜索算法啟發(fā)式搜索-爬山法爬山法模擬人們出游爬山的決策過程以目標(biāo)值增加的方向?yàn)樗阉鞣较蛉绻卸鄠€(gè)增加的方向，選使目標(biāo)值增加速度最快的方向爬山法會(huì)在某個(gè)峰頂終止，其相鄰狀態(tài)中沒有更高的目標(biāo)值了，稱為局部極大值啟發(fā)式搜索-爬山法爬山法的基本步驟1、初始化，確定初始節(jié)點(diǎn)等參數(shù)2、檢查當(dāng)前節(jié)點(diǎn)是否滿足目標(biāo)條件，如果滿足，則搜索成功，結(jié)束3、取鄰域中每一個(gè)相鄰節(jié)點(diǎn)，計(jì)算其目標(biāo)函數(shù)的改進(jìn)值4、取改進(jìn)值最大的相鄰節(jié)點(diǎn)作為搜索目標(biāo)，替換當(dāng)前節(jié)點(diǎn)5、檢查是否滿足循環(huán)終止條件。如果滿足，則中止循環(huán)，否則轉(zhuǎn)步2啟發(fā)式搜索-爬山法爬山法的缺陷難以處理山肩的情況貪婪搜索方向不一定是正確的搜索方向啟發(fā)式搜索-爬山法爬山法的改進(jìn)隨機(jī)爬山法：在上山移動(dòng)中隨機(jī)的選擇下一步可回溯爬山法：給定啟發(fā)式的回溯策略，允許回頭搜索其他節(jié)點(diǎn)洪水爬山法：不斷尋找改進(jìn)方向允許水平移動(dòng)可回溯啟發(fā)式搜索-模擬退火算法（simulatedannealing）

爬山法是完完全全的貪心法，每次都選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火其實(shí)也是一種貪心算法，但是它的搜索過程引入了隨機(jī)因素。模擬退火算法以一定的概率來接受一個(gè)比當(dāng)前解要差的解，因此有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。移動(dòng)后得到更優(yōu)解，則總是接受該移動(dòng)移動(dòng)后的解比當(dāng)前解要差，則以一定的概率接受移動(dòng)，而且這個(gè)概率隨著時(shí)間推移逐漸降低（逐漸降低才能趨向穩(wěn)定）這里的“一定的概率”的計(jì)算參考了金屬冶煉的退火過程，這也是模擬退火算法名稱的由來模擬退火算法模擬退火搜索：結(jié)合爬山法和隨機(jī)行走比喻：在冶金中退火是為了增強(qiáng)金屬和玻璃的韌性和硬度而先把它們加熱到高溫然后逐漸冷卻的過程啟發(fā)式搜索-模擬退火算法模擬退火過程思想來源于固體退火原理，屬于熱力學(xué)范疇將固體加溫至充分高，再讓其緩慢冷卻加溫時(shí)，固體內(nèi)部的粒子隨溫升脫離原先的平衡態(tài)，變?yōu)闊o序狀緩慢冷卻時(shí)，粒子活性逐漸下降，逐漸停留在不同狀態(tài)，重新形成粒子的排列結(jié)構(gòu)如果降溫過程足夠緩慢，粒子的排列就會(huì)達(dá)到一種平衡態(tài)，使系統(tǒng)能量最小啟發(fā)式搜索-模擬退火算法初始狀態(tài)加溫冷卻啟發(fā)式搜索-模擬退火算法模擬退火的基本步驟:

(1)初始化：初始溫度T(充分大)，初始狀態(tài)S，迭代次數(shù)L

(2)對(duì)k=1，……，L重復(fù)第(3)至第6步：

(3)產(chǎn)生新解S’

(4)計(jì)算增量Δt’=C(S’)-C(S)，其中C(S)為評(píng)價(jià)函數(shù)

(5)若Δt’<0則接受S’作為新的當(dāng)前解，否則以概率exp(-Δt’/T)接受S’作為新的當(dāng)前解

(6)如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。

(7)T逐漸減少，且T>0，然后轉(zhuǎn)第2步。啟發(fā)式搜索-模擬退火算法冷卻進(jìn)度表：是指調(diào)整模擬退火法的一系列重要參數(shù)，它控制溫度參數(shù)T的初值及其衰減函數(shù)。冷卻進(jìn)度表的內(nèi)容：控制參數(shù)T的初值;控制參數(shù)T的衰減函數(shù)；每一個(gè)溫度下的迭代次數(shù)L，即每一次隨機(jī)游走過程，要迭代多少次，才能趨于一個(gè)準(zhǔn)平衡分布結(jié)束條件啟發(fā)式搜索-模擬退火算法模擬退火算法的關(guān)鍵點(diǎn)初始溫度必須足夠高在每一個(gè)溫度下，狀態(tài)的轉(zhuǎn)換必須足夠充分溫度T的下降必須足夠緩慢啟發(fā)式搜索-模擬退火算法模擬退火算法的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：計(jì)算過程簡單，通用，魯棒性強(qiáng)適用于并行處理，可用于求解復(fù)雜的非線性優(yōu)化問題缺點(diǎn)：如果降溫過程足夠緩慢，多得到的解的性能會(huì)比較好，但與此相對(duì)的是收斂速度太慢;如果降溫過程過快，很可能得不到全局最優(yōu)解爬山算法：兔子朝著比現(xiàn)在高的地方跳去。它找到了不遠(yuǎn)處的最高山峰。可能這只兔子“登泰山而小天下”，但是卻沒有找到珠穆朗瑪峰。這就是爬山算法，它不能保證局部最優(yōu)值就是全局最優(yōu)值。模擬退火：對(duì)兔子來說，兔子喝醉了。他迷迷糊糊地跳了很長時(shí)間。這期間，它可能走向高處，也可能踏入平地。但是，他漸漸清醒了并朝最高方向跳去。為了保證有比較優(yōu)的解，算法運(yùn)行時(shí)間比較長，這也是模擬退火的最大缺點(diǎn)。人喝醉了酒辦起事來都不利索，何況兔子？例如有這樣一個(gè)問題：為了找出地球上最高的山珠穆朗瑪峰，一群有志氣的兔子們開始想辦法。

遺傳算法：兔子們吃了失憶藥片，并被發(fā)射到太空，然后隨機(jī)落到了地球上的某些地方。他們不知道自己的使命是什么