清華大學(xué)人工智能導(dǎo)論課件_第七章

1、精選文檔第7章 高級搜索在第一章、第二章，我們分別介紹了深度優(yōu)先、寬度優(yōu)先、A*算法和AO*算法等常規(guī)的搜索算法。深度優(yōu)先、寬度優(yōu)先等盲目搜索算法就不用說了，即便是A*算法，一般情況下，其算法復(fù)雜性仍然是指數(shù)時(shí)間級的。因此，當(dāng)問題的規(guī)模大到一定程度之后，這些常規(guī)的搜索算法就顯得無能為力了。本章將介紹一些相對比較新的搜索方法，如局部搜索、模擬退火和遺傳算法等。這些算法的一個(gè)共同特點(diǎn)是引入了隨機(jī)因素，每次運(yùn)行并不能保證求得問題的最優(yōu)解，但經(jīng)過多次運(yùn)行之后，一般總能得到一個(gè)與最優(yōu)解相差不太大的滿意解。以放棄每次必然找到最佳解，換取了算法時(shí)間復(fù)雜度的降低，以適合于求解大規(guī)模的優(yōu)化問題。7.1 基本概念

2、7.1.1 組合優(yōu)化問題在現(xiàn)實(shí)世界中，很多問題屬于優(yōu)化問題，或者可以轉(zhuǎn)化為優(yōu)化問題求解。比如我們前面介紹過的旅行商問題（TSP），就是求解旅行商在滿足給定的約束條件下的最短路徑問題。這里的約束條件是“從某個(gè)城市出發(fā)，經(jīng)過n個(gè)指定的城市，每個(gè)城市只能且必須經(jīng)過一次，最后再回到出發(fā)城市”。還有皇后問題，它要求在一個(gè)nn的國際象棋棋盤上，擺放n個(gè)皇后，使得n個(gè)皇后之間不能相互“捕捉”，即在任何一行、一列和任何一個(gè)斜線上，只能有一個(gè)皇后?；屎髥栴}本身并不是一個(gè)優(yōu)化問題，但可以轉(zhuǎn)化為優(yōu)化問題來求解。比如我們可以定義指標(biāo)函數(shù)為棋盤上能夠相互“捕捉”的皇后數(shù)，顯然該指標(biāo)函數(shù)的取值范圍是一個(gè)大于等于0的整數(shù)，

3、當(dāng)棋盤上擺放了n個(gè)皇后，且其指標(biāo)函數(shù)取值為最小值0時(shí)，剛好是問題的解。因此皇后問題轉(zhuǎn)變成了求解該指標(biāo)函數(shù)最小的優(yōu)化問題。設(shè)x是決策變量，D是x的定義域，f(x)是指標(biāo)函數(shù)，g(x)是約束條件集合。則優(yōu)化問題可以表示為，求解滿足g(x)的f(x)最小值問題。即（7.1）如果在定義域D上，滿足條件g(x)的解是有限的，則優(yōu)化問題稱為組合優(yōu)化問題?，F(xiàn)實(shí)世界中的大量優(yōu)化問題，屬于組合優(yōu)化問題。像旅行商問題、皇后問題等是組合優(yōu)化問題的典型代表。對于組合優(yōu)化問題，由于其可能的解是有限的，當(dāng)問題的規(guī)模比較小時(shí)，總可以通過枚舉的方法獲得問題的最優(yōu)解，但當(dāng)問題的規(guī)模比較大時(shí)，其狀態(tài)數(shù)往往呈指數(shù)級增長，這樣就很難

4、通過枚舉的方式來獲得問題的最優(yōu)解了。一個(gè)問題的大小通常用輸入數(shù)據(jù)量n來衡量，如旅行商問題中的城市數(shù)目，皇后問題中的皇后數(shù)目等。對于同一個(gè)問題，不同的求解方法的效率是不同的，差別可能會(huì)非常大。通常用算法的時(shí)間復(fù)雜性來評價(jià)一個(gè)求解方法的好壞。常用的算法復(fù)雜性函數(shù)按復(fù)雜性從小到大排列有如下幾種：其中O(h(n)表示該算法的復(fù)雜性為h(n)量級。如n皇后問題，由問題的約束條件，我們知道每一行、每一列只能并且必須放一個(gè)皇后。如果我們先不考慮對角線的情況，先用枚舉法生成出n個(gè)皇后不在同一行、同一列的所有狀態(tài)，再從中找出滿足約束條件的解。從第一行開始放起，則第一行每個(gè)位置都可以放皇后，因此共有n種方法；第二

5、行除了第一行皇后的所在列以外，其他位置都可以放皇后，因此共有n-1種方法；依此類推，第i行共有n-i種擺放方法。所以所有可能的狀態(tài)數(shù)共n!個(gè)。這樣我們可以大概估算出，用這樣一種枚舉法求解n皇后問題，所花費(fèi)的時(shí)間與n!成正比關(guān)系，其時(shí)間復(fù)雜性用算法復(fù)雜性函數(shù)表示就是O(n!)。Nirwan Ansari和Edwin Hou在他們的書中，給出了假定計(jì)算機(jī)的處理速度為每秒鐘執(zhí)行10億次運(yùn)算的條件下，不同輸入數(shù)據(jù)量下各種復(fù)雜性函數(shù)所需要的計(jì)算時(shí)間。如表7.1所示。表7.1 時(shí)間復(fù)雜性函數(shù)比較 輸入量n復(fù)雜性函數(shù)10203040100n10ns20ns30ns40ns100nsnlogn10ns26.0

6、ns44.3ns64.1ns200nsn2100ns400ns900ns1.6s10s2n1.0s1.0ms1.1s18.3min4.0世紀(jì)n!3.6ms77.1年8.41013世紀(jì)2.61029世紀(jì)3.010139世紀(jì)當(dāng)一個(gè)算法的時(shí)間復(fù)雜性可以表示為多項(xiàng)式形式時(shí)，則稱之為多項(xiàng)式時(shí)間算法，否則就是一個(gè)指數(shù)時(shí)間算法。從表7.1中可以看出，如果一個(gè)算法是指數(shù)時(shí)間算法（2n或者n!），那么當(dāng)n大到一定程度時(shí)，因?yàn)樗ㄙM(fèi)的時(shí)間太長了，以至于不可能求解。一些組合優(yōu)化問題已經(jīng)找到了多項(xiàng)式時(shí)間算法，如線性規(guī)劃問題。還有一些被稱為難于求解的組合優(yōu)化問題，至今還沒有找到求解這些問題的最優(yōu)解的多項(xiàng)式時(shí)間算法。像旅

7、行商問題、背包問題、裝箱問題等，都屬于這類難于求解的組合優(yōu)化問題。由于這些問題都有很強(qiáng)的實(shí)際背景，為此人們研究一些不一定能求得最優(yōu)解，但往往能得到一個(gè)滿意解的算法，以此來降低算法的復(fù)雜性。而實(shí)際上很多情況下追求最優(yōu)解并不一定有意義，一個(gè)滿意解就已經(jīng)足夠了。這就如同夏天去買西瓜。你沒有必要非要買一個(gè)北京市最甜的西瓜，甚至于也沒有必要買一個(gè)西瓜攤中最甜的西瓜，因?yàn)檫@樣選擇的工作量太大了。你只需從面前的35個(gè)西瓜中選擇一個(gè)最好的就可以。當(dāng)面前的這幾個(gè)西瓜都感覺不合適時(shí)，你可以換一個(gè)位置，或者換另一個(gè)西瓜攤重新選擇。如果你對西瓜的評價(jià)是正確的話，那么這樣選擇出來的西瓜應(yīng)該是一個(gè)令你滿意的西瓜，與“最甜

8、的西瓜”差別也不會(huì)太多。7.1.2 鄰域在后面的介紹中經(jīng)常會(huì)用到鄰域的概念。我們先給出鄰域的定義。鄰域，簡單的說就是一個(gè)點(diǎn)附近的其他點(diǎn)的集合。在距離空間中，鄰域一般定義為以該點(diǎn)為中心的一個(gè)圓。在組合優(yōu)化問題中，距離的概念不一定適用，為此提出其他的鄰域定義。設(shè)D是問題的定義域，若存在一個(gè)映射N，使得：（7.2）則稱N(S)為S的鄰域，稱為S的鄰居。下面舉幾個(gè)例子。例1：皇后問題為了簡單起見，我們以4皇后問題為例說明。設(shè)棋盤從左到右依次為第一列、第二列、第四列，從上到下依次為第一行、第二行、第四行。我們用14的一個(gè)序列S=(si)(i = 1, 2, 3, 4; si=1, 2, 3, 4)表示4

9、皇后問題的一個(gè)可能的解。其中si表示在第i行、第si列有一個(gè)皇后。如：S = (2, 4, 1, 3)表示的是如圖7.1所示的棋盤格局。定義映射N為棋盤上任意兩個(gè)皇后的所在行或列進(jìn)行交換，即S中任意兩個(gè)元素交換位置，這樣可以得到S的所有鄰居共個(gè)，所有鄰居的集合就是S的鄰域。當(dāng)S = (2, 4, 1, 3)時(shí)，其鄰域?yàn)椋篘(S) = (4, 2, 1, 3), (1, 4, 2, 3), (3, 4, 1, 2), (2, 1, 4, 3), (2, 3, 1, 4), (2, 4, 3, 1)交換不一定限制在兩個(gè)皇后之間進(jìn)行，也可以選擇三個(gè)皇后進(jìn)行交換。不同的交換方式，得到的鄰域可能是不同的

10、。QQQQ圖7.1，4皇后問題的一個(gè)格局例2，旅行商問題旅行商問題可以用一個(gè)城市的序列表示一個(gè)可能的解。可以采用與皇后問題類似的方法，通過交換兩個(gè)城市的位置獲取S的鄰居。設(shè)S = (x1, x2, xi-1, xi, xi+1, , xj-1, xj, xj+1, , xn)則通過交換xi和xj兩個(gè)城市的位置可以得到S的一個(gè)鄰居：S = (x1, x2, xi-1, xj, xi+1, , xj-1, xi, xj+1, , xn)圖7.2給出了這種位置交換方式的示意圖。x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1 圖7.2. 位置交

11、換方式示意圖也可以采取逆序交換的方式獲取S的鄰居。設(shè)i、j是選取的兩個(gè)整數(shù)，ij，0i,jn+1。所謂的逆序交換方式是指，通過逆轉(zhuǎn)xi、xj兩個(gè)城市之間的城市次序來得到S的鄰居。即：S = (x1, x2, xi-1, xi, xj-1, x j-2, xi+1, xj, xj+1, , xn)圖7.3給出了逆序交換方式的示意圖。x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1 圖7.3. 逆序交換方式示意圖在一個(gè)鄰域內(nèi)的最優(yōu)解，我們稱為局部最優(yōu)解。相應(yīng)地，在整個(gè)定義域上的最優(yōu)解稱為全局最優(yōu)解。7.2 局部搜索算法局部搜索算法是從爬山法改

12、進(jìn)而來的。設(shè)想我們要爬一座自己從未爬過的高山，目標(biāo)是爬到山頂，那么如何設(shè)計(jì)一種策略使得我們可以最快的達(dá)到山頂呢？在一般的情況下，如果我們沒有任何有關(guān)山頂?shù)钠渌畔?，沿著最陡的山坡向上爬，?yīng)該是一種不錯(cuò)的選擇。這就是局部搜索算法中最基本的思想，即在搜索過程中，始終向著離目標(biāo)最接近的方向搜索。當(dāng)然最優(yōu)解可以是求解最大值，也可以是求解最小值，二者的思想是一樣的。在下面的討論中，如果沒有特殊說明，均假定最優(yōu)解求解的是最小值。下面我們首先給出局部搜索的最一般算法，在下面算法的描述中，“；”號后面的內(nèi)容為算法的注釋。局部搜索算法（Local Search）1，隨機(jī)的選擇一個(gè)初始的可能解x0D，xb=x0，

13、P=N(xb)；D是問題的定義域，xb用于記錄到目標(biāo)位置得到的最優(yōu)解，P為xb的鄰域。2，如果不滿足結(jié)束條件，則；結(jié)束條件包括達(dá)到了規(guī)定的循環(huán)次數(shù)、P為空等3，Begin4，選擇P的一個(gè)子集P，xn為P中的最優(yōu)解5，如果f(xn) f(xb), P = P xn = (a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)第2次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn = (a, d, c, b, e), f(xn) = 45, f(xn) f(xb), P = P xn = (a, e

14、, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)第3次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn = (a, e, c, d, b), f(xn) = 44, f(xn) f(xb), P = P xn = (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)第4次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn = (a, b, d, c, e), f(xn) = 44, f(xn) f(xb), P = P xn = (a, b, e, d, c), (a, b, c, e, d)第5

15、次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn = (a, b, e, d, c), f(xn) = 34, f(xn) f(xb), P = P xn = (a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)第7次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn = (a, d, e, b, c), f(xn) = 39, f(xn) f(xb), P = P xn = (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c,

16、 d)第8次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn = (a, c, e, d, b), f(xn) = 38, f(xn) f(xb), P = P xn = (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)第9次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn = (a, b, d, e, c), f(xn) = 38, f(xn) f(xb), P = P xn = (a, b, c, d, e), (a, b, e, c, d)第10次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn = (a, b, c, d, e), f(xn) = 38, f(xn)

17、 f(xb), P = P xn = (a, b, e, c, d)第11次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn = (a, b, e, c, d), f(xn) = 41, f(xn) f(xb), P = P xn = P等于空，算法結(jié)束，得到結(jié)果為xb = (a, b, e, d, c), f(xb) = 34。在該問題中，由于初始值(a, b, c, d, e)的指標(biāo)函數(shù)為38，已經(jīng)是一個(gè)比較不錯(cuò)的結(jié)果了，在11次循環(huán)的搜索過程中，指標(biāo)函數(shù)只下降了一次，最終的結(jié)果指標(biāo)函數(shù)為34，這剛好是該問題的最優(yōu)解。從局部搜索的一般算法可以看出，該方法非常簡單，但也存在著一些問題。一般情況下，并不

18、能像上例那樣幸運(yùn)，得到問題的最優(yōu)解。一般的局部搜索算法主要有以下幾個(gè)問題：（1）局部最優(yōu)問題如果指標(biāo)函數(shù)f在定義域D上只有一個(gè)極值點(diǎn)時(shí)，一般的局部搜索算法可以找到該極值點(diǎn)。但現(xiàn)實(shí)中的問題，其指標(biāo)函數(shù)f在定義域D上往往有多個(gè)局部的極值點(diǎn)，就如同一座群山中，往往有多個(gè)小山峰一樣。按照局部搜索的一般方法，一旦陷入了局部極值點(diǎn)，算法就將在該點(diǎn)處結(jié)束，這時(shí)得到的可能是一個(gè)非常糟糕的結(jié)果。解決的辦法是在算法的第四步，每次并不一定選擇鄰域內(nèi)最優(yōu)的點(diǎn)，而是依據(jù)一定的概率，從鄰域內(nèi)選擇一個(gè)點(diǎn)，指標(biāo)函數(shù)優(yōu)的點(diǎn)，被選中的概率比較大，而指標(biāo)函數(shù)差的點(diǎn)，被選中的概率比較小。并考慮歸一化的問題，使得鄰域內(nèi)所有點(diǎn)被選中的概

19、率之和為1。當(dāng)前點(diǎn)的一個(gè)鄰居被選中的概率可以由鄰域中所有鄰居的指標(biāo)函數(shù)值計(jì)算得到。設(shè)x為當(dāng)前點(diǎn)，其鄰域?yàn)镹(x)，當(dāng)求解的最優(yōu)解為極大值時(shí)，xiN(xi)被選中的概率Pmax(xi)可以定義為：（7.3）其中f(xi)是xi的指標(biāo)函數(shù)值。這樣的概率定義既符合概率和為1的歸一化條件，又與“指標(biāo)函數(shù)優(yōu)的點(diǎn)，被選中的概率大，而指標(biāo)函數(shù)差的點(diǎn)，被選中的概率小”的思想相一致。當(dāng)求解的最優(yōu)解為最小值時(shí)，也可以使用類似的思想定義概率值。比如用1Pmax(xi)作為xi被選中的概率，進(jìn)行歸一化處理后表示為Pmin(xi)，有： （7.4）根據(jù)這樣的思想，可以得到改進(jìn)的局部搜索算法如下：局部搜索算法1（Loca

20、l Search 1）1，隨機(jī)的選擇一個(gè)初始的可能解x0D，xb=x0，P=N(xb)；D是問題的定義域，xb用于記錄到目標(biāo)位置得到的最優(yōu)解，P為xb的鄰域。2，如果不滿足結(jié)束條件，則；結(jié)束條件包括達(dá)到了規(guī)定的循環(huán)次數(shù)、P為空等3，Begin4，對于所有的xP計(jì)算指標(biāo)函數(shù)f(x)，并按照式（3）或者式（4）計(jì)算每一個(gè)點(diǎn)x的概率5，依計(jì)算的概率值，從P中隨機(jī)選擇一個(gè)點(diǎn)xn，xb xn，P = N(xb)，轉(zhuǎn)26，End7，輸出計(jì)算結(jié)果8，結(jié)束局部搜索算法1通過引入隨機(jī)的機(jī)制，有可能從局部最優(yōu)解處跳出，但由于該算法會(huì)隨機(jī)的選擇一些不太好的點(diǎn)，因此有些情況下得到的結(jié)果可能會(huì)不太好，但總體上來說，效果

21、會(huì)比一般的局部搜索算法好。（2）步長問題在距離空間中，鄰域可以簡單的定義為距離當(dāng)前點(diǎn)固定距離的點(diǎn)。這里的固定距離稱之為步長。如果步長選擇的不合適，即便是單極值的指標(biāo)函數(shù)，一般的局部搜索算法也可能找不到一個(gè)可以接受的解。圖7.5（a）給出了這樣的一個(gè)例子。當(dāng)我們想求解該函數(shù)的最大值時(shí)，由于起始點(diǎn)和步長選擇的不合適，找到的是一個(gè)非常糟糕的解。那么是否可以通過選擇更小的步長來改進(jìn)搜索呢？一方面步長太小會(huì)使得搜索耗費(fèi)太多的時(shí)間，另一方面，由于我們事先對函數(shù)的形狀和分布并不了解，不知道步長到底小到什么程度才合適。初始值搜索到的最優(yōu)解初始值搜索到的最優(yōu)解 (a) (b)圖7.5 局部搜索中步長問題示意圖一

22、種可行的方法是將固定步長的搜索方法變?yōu)閯?dòng)態(tài)步長，開始時(shí)選擇比較大的步長，隨著搜索的進(jìn)行，逐步減小步長。這樣既解決了固定步長所帶來的問題，又在一定程度上解決了小步長搜索耗時(shí)的問題。圖7.5（b）給出的是這種搜索方法的示例。對于組合優(yōu)化問題，雖然有時(shí)距離的概念并不適用，但仍存在“步長”問題。這里的“步長”不是一般意義下的步長的概念，而是指一個(gè)點(diǎn)到它的鄰居的變化程度。以旅行商問題為例，鄰居可以通過交換兩個(gè)城市獲得，也可以通過交換三個(gè)、或者更多的城市獲得。顯然，交換三個(gè)城市比交換兩個(gè)城市變化大，可以認(rèn)為交換三個(gè)城市比交換兩個(gè)城市的“步長”長。從變步長的角度，可以得到如下的局部搜索算法：局部搜索算法2（

23、Local Search 2）1，隨機(jī)的選擇一個(gè)初始的可能解x0D，xb=x0，確定一個(gè)初始步長計(jì)算P=N(xb)；D是問題的定義域，xb用于記錄到目標(biāo)位置得到的最優(yōu)解，P為xb的鄰域。2，如果不滿足結(jié)束條件，則；結(jié)束條件包括達(dá)到了規(guī)定的循環(huán)次數(shù)、P為空等3，Begin4，選擇P的一個(gè)子集P，xn為P中的最優(yōu)解5，如果f(xn) f(xb)，則xb xn6，按照某種策略改變步長，計(jì)算P = N(xb)，轉(zhuǎn)2；f(x)為指標(biāo)函數(shù)。7，否則P = P P，轉(zhuǎn)2。8，End9，輸出計(jì)算結(jié)果10，結(jié)束（3）起始點(diǎn)問題一般的局部搜索算法是否能找到全局最優(yōu)解，與初始點(diǎn)的位置有很大的依賴關(guān)系。在圖7.6所示

24、的例子中，從初始點(diǎn)A開始搜索，可以找到函數(shù)的全局最大值，而如果從B點(diǎn)開始搜索，則只能找到函數(shù)的局部最大值。AB全局最大值局部最大值圖7.6. 初始點(diǎn)位置影響搜索結(jié)果一種改進(jìn)的方法就是隨機(jī)的生成一些初始點(diǎn)，從每個(gè)初始點(diǎn)出發(fā)進(jìn)行搜索，找到各自的最優(yōu)解。再從這些最優(yōu)解中選擇一個(gè)最好的結(jié)果作為最終的結(jié)果。改進(jìn)后的算法如下：局部搜索算法3（Local Search 3）1，k = 02，隨機(jī)的選擇一個(gè)初始的可能解x0D，xb=x0，P=N(xb)；D是問題的定義域，xb用于記錄到目標(biāo)位置得到的最優(yōu)解，P為xb的鄰域。3，如果不滿足結(jié)束條件，則；結(jié)束條件包括達(dá)到了規(guī)定的循環(huán)次數(shù)、P為空等4，Begin5，

25、選擇P的一個(gè)子集P，xn為P中的最優(yōu)解6，如果f(xn) f(xb)，則xb xn，P = N(xb)，轉(zhuǎn)3；f(x)為指標(biāo)函數(shù)。7，否則P = P P，轉(zhuǎn)3。8，End9，k = k+110，如果k達(dá)到了指定的次數(shù)，則從k個(gè)結(jié)果中選擇一個(gè)最好的結(jié)果輸出，否則轉(zhuǎn)（2）11，輸出結(jié)果12，結(jié)束以上根據(jù)一般的局部搜索算法存在的問題，給出了三個(gè)改進(jìn)的局部搜索算法，這三種改進(jìn)方法往往并不是孤立使用的，而是互相結(jié)合在一起使用。如把局部搜索算法1和局部搜索算法2結(jié)合在一起，就是我們將在后面介紹的模擬退火算法。J. Gu在其論文中探討了用局部搜索算法求解大數(shù)目的皇后問題。采用回溯算法難于求解大數(shù)目的皇后問題

26、，一般認(rèn)為當(dāng)皇后數(shù)目達(dá)到100左右時(shí)，回溯方法就已經(jīng)難于求解了。而J. Gu用局部搜索算法成功的求解了多達(dá)百萬量級的皇后問題。J. Gu的皇后搜索算法如下：皇后搜索算法（Queen Search）1，隨機(jī)地將n個(gè)皇后分布在棋盤上，使得棋盤的每行、每列只有一個(gè)皇后。2，計(jì)算皇后間的沖突數(shù)conflicts。3，如果沖突數(shù)conflicts等于0，則轉(zhuǎn)（6）4，對于棋盤上的任意兩個(gè)皇后，交換他們的行或者列，如果交換后的沖突數(shù)conflicts減少，則接受這種交換，更新沖突數(shù)conflicts，轉(zhuǎn)3。5，如果陷入了局部極小，既交換了所有的皇后后，沖突數(shù)仍然不能下降，則轉(zhuǎn)1。6，輸出結(jié)果7，結(jié)束。筆者

27、利用以上算法，在奔騰III微機(jī)上做了一些測試，在不同的規(guī)模下，求解皇后問題所需的平均時(shí)間如下表所示。需要說明的是，由于局部搜索算法是一種隨機(jī)算法，對于同樣規(guī)模的問題，每次求解所需的時(shí)間是不同的，這里給出的是幾次運(yùn)行的平均時(shí)間。表2：不同規(guī)模下皇后問題的平均求解時(shí)間皇 后 數(shù)1005001000200050001000030000平均時(shí)間（秒）551228170900100007.3 模擬退火算法模擬退火算法是局部搜索算法的一種擴(kuò)展，該算法的思想最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地將模擬退火算法用于求解組合優(yōu)化問題。作為求解復(fù)雜組合優(yōu)化問題的一

28、種有效的方法，模擬退化算法已經(jīng)在許多工程和科學(xué)領(lǐng)域得到廣泛的應(yīng)用。7.3.1 固體退火過程模擬退火算法是根據(jù)復(fù)雜組合優(yōu)化問題與固體的退火過程間的相似之處，在它們之間建立聯(lián)系而提出來的。固體的退火過程是一種物理現(xiàn)象，屬于熱力學(xué)和統(tǒng)計(jì)物理學(xué)的研究范疇。當(dāng)對一個(gè)固體進(jìn)行加熱時(shí)，粒子的熱運(yùn)動(dòng)不斷增加，隨著溫度的不斷上升，粒子逐漸脫離開其平衡位置，變得越來越自由，直到達(dá)到固體的溶解溫度，粒子排列從原來的有序狀態(tài)變?yōu)橥耆臒o序狀態(tài)。這就是固體的溶解過程。退火過程與溶解過程剛好相反。隨著溫度的下降，粒子的熱運(yùn)動(dòng)逐漸減弱，粒子逐漸停留在不同的狀態(tài)，其排列也從無序向有序方向發(fā)展，直至到溫度很低時(shí)，粒子重新以一定

29、的結(jié)構(gòu)排列。粒子不同的排列結(jié)構(gòu)，對應(yīng)著不同的能量水平。如果退火過程是緩慢進(jìn)行的，也就是說，溫度的下降如果非常緩慢的話，使得在每個(gè)溫度下，粒子的排列都達(dá)到一種平衡態(tài)，則當(dāng)溫度趨于0（絕對溫度）時(shí)，系統(tǒng)的能量將趨于最小值。如果以粒子的排列或者相應(yīng)的能量來表達(dá)固體所處的狀態(tài)，在溫度T下，固體所處的狀態(tài)具有一定的隨機(jī)性。一方面，物理系統(tǒng)傾向于能量較低的狀態(tài)，另一方面，熱運(yùn)動(dòng)又妨礙了系統(tǒng)準(zhǔn)確落入低能狀態(tài)。根據(jù)這一物理現(xiàn)象，Metropolis給出了從狀態(tài)i轉(zhuǎn)換為狀態(tài)j的準(zhǔn)則：如果E(j)E(i)，則狀態(tài)轉(zhuǎn)換被接受；如果E(j)E(i)，則狀態(tài)轉(zhuǎn)移被接受的概率為： （7.5）其中E(i)、E(j)分別表示

30、在狀態(tài)i、j下的能量，T是溫度，K0是波爾茲曼常數(shù)。Metropolis準(zhǔn)則表達(dá)了這樣一種現(xiàn)象：在溫度T下，系統(tǒng)處于某種狀態(tài)，由于粒子的移動(dòng)，系統(tǒng)的狀態(tài)發(fā)生微小的變化，并導(dǎo)致了系統(tǒng)能量的變化。如果這種變化使得系統(tǒng)的能量減少，則接受這種轉(zhuǎn)換；如果變換使得系統(tǒng)的能量增加，則以一定的概率接受這種轉(zhuǎn)換。在給定的溫度T下，當(dāng)進(jìn)行足夠多次的狀態(tài)轉(zhuǎn)換后，系統(tǒng)將達(dá)到熱平衡。此時(shí)系統(tǒng)處于某個(gè)狀態(tài)i的概率由Boltzmann分布給出： （7.6）其中為歸一化因子，S是所有可能狀態(tài)的集合。我們考察一下式（7.6）隨溫度T的變化情況。在給定的溫度T下，設(shè)有i、j兩個(gè)狀態(tài)，E(i)E(j)。由式（7.6）有： (7.7

31、)由于E(i)E(j)，所以：所以有： （7.8）即在任何溫度T下，系統(tǒng)處于能量低的狀態(tài)的概率大于處于能量高的狀態(tài)的概率。當(dāng)溫度很高時(shí)，由式（7.6）有： （7.9）其中|S|表示系統(tǒng)所有可能的狀態(tài)數(shù)。由式（7.9）可以看出，當(dāng)溫度很高時(shí)，系統(tǒng)處于各個(gè)狀態(tài)的概率基本相等，接近于平均值，與所處狀態(tài)的能量幾乎無關(guān)。當(dāng)溫度很低時(shí)，由式（7.6）有： （7.10）設(shè)Sm表示系統(tǒng)最小能量狀態(tài)的集合，Em是系統(tǒng)的最小能量。上式分子、分母同乘以有： （7.11）由式（7.11）可以看出，當(dāng)溫度趨近于0時(shí)，系統(tǒng)以等概率趨近于幾個(gè)能量最小的狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)的概率為0。由于： （7.12）其中： （7

32、.13）是溫度T下，各狀態(tài)能量的期望值。由于、K、T均大于0，因此由式（7.12），我們有： （7.14）由此我們可以看出，系統(tǒng)落入能量較低的狀態(tài)的概率是隨溫度T單調(diào)下降的，而系統(tǒng)落入高能量狀態(tài)的概率是隨溫度T單調(diào)上升的。也就是說，系統(tǒng)落入低能量狀態(tài)的概率隨著溫度的下降單調(diào)上升，而系統(tǒng)落入高能量狀態(tài)的概率隨著溫度的下降單調(diào)下降?？偨Y(jié)以上內(nèi)容，我們可以得出如下結(jié)論：在高溫下，系統(tǒng)基本處于無序的狀態(tài)，基本以等概率落入各個(gè)狀態(tài)。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于系統(tǒng)落入高能量狀態(tài)的概率，這樣在同一溫度下，如果系統(tǒng)交換的足夠充分，則系統(tǒng)會(huì)趨向于落入較低能量的狀態(tài)。隨著溫度的緩慢下降，系統(tǒng)落入

33、低能量狀態(tài)的概率逐步增加，而落入高能量狀態(tài)的概率逐步減少，使得系統(tǒng)各狀態(tài)能量的期望值隨溫度的下降單調(diào)下降，而只有那些能量小于期望值的狀態(tài)，其概率才隨溫度下降增加，其他狀態(tài)均隨溫度下降而下降。因此，隨著能量期望值的逐步下降，能量低于期望值的狀態(tài)逐步減少，當(dāng)溫度趨于0時(shí)，只剩下那些具有最小能量的狀態(tài)，系統(tǒng)處于其他狀態(tài)的概率趨近于0。因此最終系統(tǒng)將以概率1處于具有最小能量的一個(gè)狀態(tài)。固體退火過程，最終達(dá)到最小能量的一個(gè)狀態(tài)，從理論上來說，必須滿足以下三個(gè)條件：（1）初始溫度必須足夠高；（2）在每個(gè)溫度下，狀態(tài)的交換必須足夠充分；（3）溫度T的下降必須足夠緩慢。7.3.2 模擬退火算法受固體退火過程的

34、啟發(fā)，Kirkpatrick等人意識(shí)到組合優(yōu)化問題與固體退火過程的類似性，將組合優(yōu)化問題類比為固體的退火過程，提出了求解組合優(yōu)化問題的模擬退火算法。表7.3給出了組合優(yōu)化問題與固體退火過程的類比關(guān)系。表7.3：組合優(yōu)化問題與退火過程的類比固體退火過程組合優(yōu)化問題物理系統(tǒng)中的一個(gè)狀態(tài)組合優(yōu)化問題的解狀態(tài)的能量解的指標(biāo)函數(shù)能量最低狀態(tài)最優(yōu)解溫度控制參數(shù)設(shè)一個(gè)定義在有限集S上的組合優(yōu)化問題，iS是該問題的一個(gè)解，f(i)是解i的指標(biāo)函數(shù)。由表7.3給出的類比關(guān)系，i對應(yīng)物理系統(tǒng)的一個(gè)狀態(tài)，f(i)對應(yīng)該狀態(tài)的能量E(i)，一個(gè)用于控制算法的進(jìn)程、其值隨算法進(jìn)程遞減的控制參數(shù)t對應(yīng)固體退火中的溫度T，

35、粒子的熱運(yùn)動(dòng)則用解在鄰域中的交換來代替。這樣就將一個(gè)組合優(yōu)化問題與固體的退火過程建立了聯(lián)系。在求解組合優(yōu)化問題時(shí)，首先給定一個(gè)比較大的t值，這相當(dāng)于給定一個(gè)比較高的溫度T。隨機(jī)給定一個(gè)問題的解i，作為問題的初始解。在給定的t下，隨機(jī)產(chǎn)生一個(gè)問題的解j，jN(i)，其中N(i)是i的鄰域。從解i到新解j的轉(zhuǎn)移概率，按照Metropolis準(zhǔn)則確定，即： （7.15）如果新解j被接受，則以解j代替解i，否則繼續(xù)保持解i。重復(fù)該過程，直到在該控制參數(shù)t下達(dá)到平衡。與退火過程中的溫度T緩慢下降相對應(yīng)，在進(jìn)行足夠多的狀態(tài)轉(zhuǎn)移之后，控制參數(shù)t要緩慢下降，并在每個(gè)參數(shù)t下，重復(fù)以上過程，直到控制參數(shù)t降低到

36、足夠小為止。最終我們得到的是該組合優(yōu)化問題的一個(gè)最優(yōu)解。由于這樣一個(gè)過程模擬的是退火過程，所以被稱為模擬退火算法。下面，我們給出模擬退火算法的描述。模擬退火算法：1，隨機(jī)選擇一個(gè)解i，k=0，t0=Tmax（初始溫度），計(jì)算指標(biāo)函數(shù)f(i)。2，如果滿足結(jié)束條件，則轉(zhuǎn)（15）。3，Begin4，如果在該溫度內(nèi)達(dá)到了平衡條件，則轉(zhuǎn)（13）。5，Begin6，從i的鄰域N(i)中隨機(jī)選擇一個(gè)解j。7，計(jì)算指標(biāo)函數(shù)f(j)。8，如果f(j)j)Random(0, 1)，則i=j，f(i)=f(j)。11，轉(zhuǎn)（4）12，End13，tk+1=Drop(tk)，k=k+1。14，End15，輸出結(jié)果。1

37、6，結(jié)束。該算法有內(nèi)外兩層循環(huán)。內(nèi)循環(huán)模擬的是在給定溫度下系統(tǒng)達(dá)到熱平衡的過程。每次循環(huán)隨機(jī)的產(chǎn)生一個(gè)新解，然后按照Metropolis準(zhǔn)則，隨機(jī)的接受該解。算法中的Random(0, 1)，是一個(gè)在0, 1間均勻分布的隨機(jī)數(shù)發(fā)生器，與從解i到劣解j的轉(zhuǎn)移概率相結(jié)合，模擬系統(tǒng)是否接受了劣解j。外循環(huán)模擬的是溫度的下降過程，控制參數(shù)tk起到與溫度T相類似的作用，表示的是第k次循環(huán)時(shí)系統(tǒng)所處的溫度。算法中的Drop(tk)是一個(gè)溫度下降函數(shù)，它按照一定的原則實(shí)施溫度的緩慢下降。模擬退火算法與局部搜索算法很相似，二者最大的不同是模擬退火算法按照Metropolis準(zhǔn)則隨機(jī)的接受一些劣解，即指標(biāo)函數(shù)值

38、大的解。當(dāng)溫度比較高時(shí)，接受劣解的概率比較大，在初始高溫下，幾乎以接近100的概率接受劣解。隨著溫度的下降，接受劣解的概率逐漸減少，直到當(dāng)溫度趨于0時(shí)，接受劣解的概率也同時(shí)趨于0。這樣，將有利于算法從局部最優(yōu)解中跳出，求得問題的全局最優(yōu)解。上述模擬退火算法只是給出了一個(gè)算法的框架，其中重要的三個(gè)條件：初始溫度的選取，內(nèi)循環(huán)的結(jié)束條件和外循環(huán)的結(jié)束條件，算法中都沒有提及，而這正是模擬退火算法的關(guān)鍵所在。因?yàn)檎袂懊鏀⑹鲞^的那樣，對于固體退火過程來說，要最終使得物理系統(tǒng)以概率1處于能量最小的一個(gè)狀態(tài)，在退火過程中必須滿足以下三個(gè)條件：（1）初始溫度必須足夠高；（2）在每個(gè)溫度下，狀態(tài)的交換必須足夠

39、充分；（3）溫度T的下降必須足夠緩慢。這三個(gè)條件剛好是與算法中未提及的三個(gè)重要條件相對應(yīng)的。與固體退火過程一樣，為了使得模擬退火算法以概率1求解到問題的最優(yōu)解，則至少也要滿足這三個(gè)條件。然而“初始溫度必須足夠高，狀態(tài)交換必須足夠充分，溫度的下降必須足夠緩慢”這樣的條件是與我們試圖給出求解組合優(yōu)化問題的低復(fù)雜度算法的初衷相違背的。如果模擬退火算法仍然是一個(gè)指數(shù)復(fù)雜度的算法，則對于求解復(fù)雜組合優(yōu)化問題不會(huì)帶來任何意義下的幫助?，F(xiàn)在的問題是，如何弱化一些條件，使得我們能夠在一個(gè)多項(xiàng)式時(shí)間復(fù)雜度內(nèi)，求得一個(gè)組合優(yōu)化問題的滿意解。在下一節(jié)我們將討論這些問題，給出一些如何確定初始溫度以及內(nèi)、外循環(huán)結(jié)束條件

40、的基本方法。在模擬退火過程中，給定溫度下狀態(tài)（解）的轉(zhuǎn)移可以看作是一個(gè)馬爾可夫鏈。對于任意兩個(gè)狀態(tài)i和j，我們用Pt(i, j)表示溫度t下，從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的一步轉(zhuǎn)移概率，則有： （7.16）其中Gt(i,j)是產(chǎn)生概率，表示從狀態(tài)i產(chǎn)生狀態(tài)j的概率。如果在鄰域內(nèi)等概率選取的話，則： （7.17）At(i,j)是接受概率，表示在狀態(tài)i產(chǎn)生狀態(tài)j后，接受狀態(tài)j的概率。如按照Metropolis準(zhǔn)則的接受概率為： （7.18）在定義的鄰域滿足一定的條件情況下，可以證明，這樣得到的馬爾可夫鏈滿足不可約和非周期性條件，其平穩(wěn)分布唯一存在。在給定的t下，經(jīng)過足夠多次的轉(zhuǎn)移之后，得到解i的概率為：

41、（7.19）該式與式（7.6）基本一致，仿照類似的分析，有： （7.20）所以： （7.21）該式說明，只要在每個(gè)t下進(jìn)行足夠多次的狀態(tài)轉(zhuǎn)移，使得達(dá)到式（7.19）所示的平衡分布，則模擬退火算法將以概率1得到問題的全局最優(yōu)解。一般的，關(guān)于平穩(wěn)分布和全局最優(yōu)問題，有下面的定理。定理1：如果和滿足以下條件：（1）與t無關(guān)；（2），均有，并且存在，使得：；（3）均有；（4），均有；（5），均有；則與模擬退火算法相伴的時(shí)齊馬爾可夫鏈存在平穩(wěn)分布，其分布概率為：， （7.22）其中。當(dāng)由式（7.18）給出時(shí)，很容易從式（7.22）推出式（7.19）。定理1給出了與模擬退火算法相伴的時(shí)齊馬爾可夫鏈存在平穩(wěn)

42、分布的充分條件，這些條件中，有些條件還是比較強(qiáng)的。如條件（2）。該條件包含了兩部分內(nèi)容：第一要求產(chǎn)生概率是對稱的，即從狀態(tài)i產(chǎn)生狀態(tài)j的概率與從狀態(tài)j產(chǎn)生狀態(tài)i的概率相等；第二要求鄰域是連通的，即從任意一個(gè)狀態(tài)都可能經(jīng)過有限次的狀態(tài)轉(zhuǎn)移之后，到達(dá)任意一個(gè)狀態(tài)。容易驗(yàn)證由式（7.18）定義的滿足定理1的（3）、（4）和（5）三個(gè)條件。如果定義為： （7.23）其中N是一個(gè)正常數(shù)。則滿足定理1條件（2）的前半部分，后半部分由于要求鄰域是連通的，與具體的鄰域生成算法有關(guān)。式（7.23）是式（7.17）在任意一個(gè)狀態(tài)的鄰域其長度都相等條件下的一個(gè)特例。定理2：在定理1的條件下，如果對于任意兩個(gè)狀態(tài)，有

43、： （7.24）則有： （7.25）定理1和定理2給出了與模擬退火算法相伴的時(shí)齊馬爾可夫鏈全局收斂的充分條件。這些條件要求還是比較苛刻的。比如當(dāng)不同狀態(tài)的鄰域不是等長時(shí)，式（7.17）就不滿足定理1的條件（2）。定理3給出了稍微放寬了一些的充分條件。定理3：和滿足定理1中除條件（2）以外的所有其他條件，并且：（1）對于任意兩個(gè)狀態(tài)，它們相互為鄰居或者相互都不為鄰居；（2）對于任意，滿足： （7.26）（3）狀態(tài)空間S對于鄰域是連通的；則與模擬退火算法相伴的時(shí)齊馬爾可夫鏈存在平穩(wěn)分布，其分布概率為： (7.27)有些學(xué)者還給出了一些其他的時(shí)齊馬爾可夫鏈存在平穩(wěn)分布的充分條件，這里就不一一列舉了。

44、定理1、定理2和定理3的證明，需要用到一些馬爾可夫鏈的有關(guān)知識(shí)，我們在這里就不給出其證明了，有興趣的讀者可以參見有關(guān)的參考文獻(xiàn)。這三個(gè)定理，保證了只要我們合適的構(gòu)造、和鄰域，就可以保證模擬退火算法以概率1找到全局最優(yōu)解。7.3.3 參數(shù)的確定從以上的分析我們知道，模擬退火算法以概率1找到全局最優(yōu)解的基本條件，是初始溫度必須足夠高，在每個(gè)溫度下狀態(tài)的交換必須足夠充分，溫度t的下降必須足夠緩慢。因此初始的溫度t0，在每個(gè)溫度下狀態(tài)的交換次數(shù)、溫度t的下降方法，以及溫度下降到什么程度算法結(jié)束等參數(shù)確定，成為模擬退火算法求解問題時(shí)必須要考慮的問題。因?yàn)閺睦碚撋蟻碚f，模擬退火算法逐漸達(dá)到最優(yōu)解的能力是以

45、搜索過程的無限次狀態(tài)轉(zhuǎn)移為前提的，作為一種最優(yōu)化的求解算法，其算法的時(shí)間復(fù)雜性仍然是指數(shù)時(shí)間的，無法用于大規(guī)模的組合優(yōu)化問題求解。但是對于很多實(shí)際問題，正如我們在第一節(jié)已經(jīng)討論的那樣，求解問題最優(yōu)解的意義并不大，一個(gè)滿意解就足夠了。而是否能在一個(gè)多項(xiàng)式的時(shí)間內(nèi)得到問題的滿意解，則是我們關(guān)心的主要問題。并不是任何一組參數(shù)，都能夠保證模擬退火算法收斂于某個(gè)近似解，大量的實(shí)驗(yàn)表明，解的質(zhì)量與算法的運(yùn)行時(shí)間是成正比關(guān)系的，很難做到兩全其美。下面我們給出模擬退火算法中一些參數(shù)或者準(zhǔn)則的確定方法，試圖在求解時(shí)間與解的質(zhì)量之間作一個(gè)折中的選擇。這些參數(shù)或者準(zhǔn)則包括：（1）初始溫度t0；（2）溫度t的衰減函數(shù)

46、，即溫度的下降方法；（3）算法的終止準(zhǔn)則，用終止溫度tf或者終止條件給出；（4）每個(gè)溫度t下的馬爾可夫鏈長度Lk。1，起始溫度t0的選取模擬退火算法要求初始溫度足夠高，這樣才能夠使得在初始溫度下，以等概率處于任何一個(gè)狀態(tài)。多高的溫度才算“足夠高”呢？這顯然與具體的問題有關(guān)，就像金屬材料中，不同的材料具有不同的溶解溫度一樣。因此，初始溫度應(yīng)根據(jù)具體的問題而定。一個(gè)合適的初始溫度，應(yīng)保證平穩(wěn)分布中每一個(gè)狀態(tài)的概率基本相等，也就是接受概率P0近似等于1。在Metropolis準(zhǔn)則下，即要求： （7.28）如果我們給定一個(gè)比較大的接受概率P0，比如P0=0.9或者0.8，就可以從式（7.28）計(jì)算出t

47、0值： （7.29）其中可以取最大值： （7.30）或者是平均值： （7.31）式（7.31）計(jì)算起來復(fù)雜性太高，可以用下式代替： （7.32）其中S是由S隨機(jī)產(chǎn)生的一個(gè)有序集，S(i)表示S的第i個(gè)元素。對于比較復(fù)雜的問題，產(chǎn)生出所有的狀態(tài)具有一定的難度，也沒有必要，一般可以隨機(jī)的產(chǎn)生一些狀態(tài)，代替集合S進(jìn)行上述計(jì)算。例4：當(dāng)P0=0.9，100時(shí)，通過式（7.29）我們可以得到：與式（7.29）的得出過程相類似，也可以通過下述方法得到t0值。假設(shè)在t0下隨機(jī)的生成一個(gè)狀態(tài)序列，分別用m1和m2表示指標(biāo)函數(shù)下降的狀態(tài)數(shù)和指標(biāo)函數(shù)上升的狀態(tài)數(shù)，表示狀態(tài)增加的平均值。則m2個(gè)狀態(tài)中，被接受的個(gè)數(shù)

48、為：所以平均接受率為： （7.33）求解有： （7.34）對比式（7.29）和式（7.34），可以發(fā)現(xiàn)，在不考慮m1的情況下，這兩個(gè)計(jì)算公式是一樣的。也就是說，用式（7.29）計(jì)算得到的t0比較保守。因?yàn)橛墒剑?.34）有： （7.35）所以由式（7.34）計(jì)算得到的t0要小于由式（7.29）計(jì)算得到的t0。表4給出了在m1=m2的情況下，由式（7.29）得到的t0與由式（7.34）得到的t0之比值（表中用t0(29)/t0(34)表示），由表中可以看出，式（7.29）得到的t0大約是式（7.34）得到的t0的2倍。表4：分別由式（7.29）和式（7.34）得到的t0之比P00.80.850.

49、90.95t0(29)/t0(34)2.292.202.122.05仿照固體的升溫過程，也可以通過逐步升溫的方法，得到一個(gè)合適的初始溫度。方法如下：（1）給定一個(gè)希望的初始接受概率P0，給定一個(gè)較低的初始溫度t0，比如t01；（2）隨機(jī)的產(chǎn)生一個(gè)狀態(tài)序列，并計(jì)算該序列的接收率：如果接收率大于給定的初始接受概率P0，則轉(zhuǎn)（4）；（3）提高溫度，更新t0，轉(zhuǎn)（2）；（4）結(jié)束。其中更新t0可以采用每次加倍的方法：t0=2t0也可以采用每次加固定值的方法：t0=t0T這里的T為一個(gè)事先給定的常量。2溫度的下降方法退火過程要求溫度下降足夠緩慢，常用的溫度下降方法有以下三種：（1）等比例下降。該方法通過設(shè)置一個(gè)衰減系數(shù)，使得溫度每次以相同的比率下降：，k=0,1,.。 （7.36）其中tk是當(dāng)前溫度，tk+1是下一個(gè)時(shí)刻的溫度，是一個(gè)常數(shù)。越接近于1，溫度下降的越慢，一般可以選取0.80.95左右的一個(gè)值。該方法簡單實(shí)用，是一種常用的溫度下降方法。（2）等值下降該方法每次溫度的下降幅度是一個(gè)固定值： （7.37）設(shè)K是希望的溫度下降總次數(shù)，則： （7.38）其中t0是初始溫度。該方法的好處是可以控制總的溫度下降次數(shù)，但由于每次溫度下降的是一個(gè)固定值，如果設(shè)置過小，在高溫時(shí)溫度下降太慢，如果設(shè)置的大，在低溫下溫度下降的又過快。（3）基