局部搜索和模擬退火

1、高級(jí)搜索1主要內(nèi)容局部搜索方法模擬退火算法遺傳算法2優(yōu)化與組合優(yōu)化問(wèn)題很多問(wèn)題屬于優(yōu)化問(wèn)題，或者可以轉(zhuǎn)化為優(yōu)化問(wèn)題如TSP問(wèn)題，皇后問(wèn)題3優(yōu)化問(wèn)題的描述設(shè)x是決策變量，D是x的定義域，f(x)是指標(biāo)函數(shù)，g(x)是約束條件集合。則優(yōu)化問(wèn)題可以表示為，求解滿足g(x)的f(x)最小值問(wèn)題。 如果在定義域D上，滿足條件g(x)的解是有限的，則優(yōu)化問(wèn)題稱為組合優(yōu)化問(wèn)題。 4算法的時(shí)間復(fù)雜度對(duì)于組合優(yōu)化問(wèn)題，由于其可能的解是有限的，當(dāng)問(wèn)題的規(guī)模比較小時(shí)，總可以通過(guò)枚舉的方法獲得問(wèn)題的最優(yōu)解，但當(dāng)問(wèn)題的規(guī)模比較大時(shí)，就難于求解了。 常用的算法復(fù)雜度函數(shù)5 輸入量n復(fù)雜性函數(shù)10203040100n10n

2、s20ns30ns40ns100nsnlogn10ns26.0ns44.3ns64.1ns200nsn2100ns400ns900ns1.6us10us2n1.0us1.0ms1.1s18.3min4.0世紀(jì)n!3.6ms77.1年8.41013世紀(jì)2.61029世紀(jì)3.010139世紀(jì)時(shí)間復(fù)雜性函數(shù)比較（10億次/秒）6一些難的組合優(yōu)化問(wèn)題旅行商問(wèn)題背包問(wèn)題裝箱問(wèn)題.尋求在可以接受的時(shí)間內(nèi)得到滿意解的方法7鄰域的概念鄰域，簡(jiǎn)單的說(shuō)就是一個(gè)點(diǎn)附近的其他點(diǎn)的集合。 在距離空間，鄰域就是以某一點(diǎn)為中心的圓。 組合優(yōu)化問(wèn)題的定義：設(shè)D是問(wèn)題的定義域，若存在一個(gè)映射N，使得： 則稱N(S)為S的鄰域。

3、 8例：皇后問(wèn)題S=Si表示一個(gè)可能解，其中Si表示在第i行，第Si列有一個(gè)皇后。如四皇后問(wèn)題的一個(gè)解：S=(2, 4, 1, 3)QQQQ9定義映射N為棋盤上任意兩個(gè)皇后的所在行或列進(jìn)行交換，即S中任意兩個(gè)元素交換位置。例：當(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) 10例：旅行商問(wèn)題用一個(gè)城市的序列表示一個(gè)可能的解。通過(guò)交換兩個(gè)城市的位置獲取S的鄰居 例：簡(jiǎn)單交換方法 設(shè)S = (x1, x2, xi-1,

4、xi, xi+1, , xj-1, xj, xj+1, , xn)則通過(guò)交換xi和xj兩個(gè)城市的位置可以得到S的一個(gè)鄰居： S = (x1, x2, xi-1, xj, xi+1, , xj-1, xi, xj+1, , xn) 11x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+112例：逆序交換方法 設(shè)xi、xj是選取的兩個(gè)城市，所謂的逆序交換方式是指，通過(guò)逆轉(zhuǎn)xi、xj兩個(gè)城市之間的城市次序來(lái)得到S的鄰居。設(shè)：S = (x1, x2, xi-1, xi, xi+1, , xj-1, xj, xj+1, , xn)則：S = (x1,

5、x2, xi-1, xi, xj-1, x j-2, xi+1, xj, xj+1, , xn)13x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+114局部搜索算法基本思想：在搜索過(guò)程中，始終向著離目標(biāo)最接近的方向搜索。目標(biāo)可以是最大值，也可以是最小值。在后面的介紹中，如果沒(méi)有特殊說(shuō)明，均假定是最小值。 15局部搜索算法（Local Search）1，隨機(jī)的選擇一個(gè)初始的可能解x0D，xb=x0，P=N(xb)；2，如果不滿足結(jié)束條件，則3，Begin4， 選擇P的一個(gè)子集P，xn為P中的最優(yōu)解5， 如果f(xn) f(xb), P =

6、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) 19第二次循環(huán)從P中選擇一個(gè)元素，假設(shè)xn = (a, d, c, b, e), f(xn) = 45, f(xn) f(xb), P = P xn = (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d) 20第三次循環(huán)從P中選擇一個(gè)元素，假設(shè)xn = (a, e, c, d, b), f(xn) = 44, f(xn) f(xb),

7、 P = P xn = (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d) 21第四次循環(huán)從P中選擇一個(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) 22第五次循環(huán)從P中選擇一個(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),

8、(a, b, c, d, e), (a, b, e, c, d) 24第七次循環(huán)從P中選擇一個(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, d) 25第八次循環(huán)從P中選擇一個(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,

9、 d) 26第九次循環(huán)從P中選擇一個(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) 27第十次循環(huán)從P中選擇一個(gè)元素，假設(shè)xn = (a, b, c, d, e), f(xn) = 38, f(xn) f(xb), P = P xn = (a, b, e, c, d) 28第十一次循環(huán)從P中選擇一個(gè)元素，假設(shè)xn = (a, b, e, c, d), f(xn) = 41, f(xn) f(xb), P = P xn = P等于空，算法結(jié)束，得到結(jié)果為

10、xb = (a, b, e, d, c), f(xb) = 34。29存在的問(wèn)題局部最優(yōu)問(wèn)題 30解決方法每次并不一定選擇鄰域內(nèi)最優(yōu)的點(diǎn)，而是依據(jù)一定的概率，從鄰域內(nèi)選擇一個(gè)點(diǎn)，指標(biāo)函數(shù)優(yōu)的點(diǎn)，被選中的概率比較大，而指標(biāo)函數(shù)差的點(diǎn)，被選中的概率比較小。31選擇概率的計(jì)算設(shè)求最大值：32選擇概率的計(jì)算當(dāng)求最小值時(shí)：33局部搜索算法1（Local Search 1）1，隨機(jī)的選擇一個(gè)初始的可能解x0D，xb=x0，P=N(xb)2，如果不滿足結(jié)束條件，則3，Begin4， 對(duì)于所有的xP計(jì)算指標(biāo)函數(shù)f(x)， 并按照式（3）或者式（4）計(jì)算每一個(gè)點(diǎn) x的概率5， 依計(jì)算的概率值，從P中隨機(jī)選擇一個(gè)

11、點(diǎn) xn，xb xn，P = N(xb)，轉(zhuǎn)26，End7，輸出計(jì)算結(jié)果8，結(jié)束34存在的問(wèn)題步長(zhǎng)問(wèn)題 初始值搜索到的最優(yōu)解35解決方法變步長(zhǎng)初始值搜索到的最優(yōu)解36局部搜索算法2（Local Search 2）1，隨機(jī)的選擇一個(gè)初始的可能解x0D，xb=x0， 確定一個(gè)初始步長(zhǎng)計(jì)算P=N(xb)2，如果不滿足結(jié)束條件，則3，Begin4， 選擇P的一個(gè)子集P，xn為P中的最優(yōu)解5， 如果f(xn) f(xb)，則xb xn6， 按照某種策略改變步長(zhǎng)，計(jì)算P = N(xb)， 轉(zhuǎn)27， 否則P = P P，轉(zhuǎn)2。8，End9，輸出計(jì)算結(jié)果10，結(jié)束37存在問(wèn)題起始點(diǎn)問(wèn)題AB全局最大值局部最大值

12、38解決方法隨機(jī)的生成一些初始點(diǎn)，從每個(gè)初始點(diǎn)出發(fā)進(jìn)行搜索，找到各自的最優(yōu)解。再?gòu)倪@些最優(yōu)解中選擇一個(gè)最好的結(jié)果作為最終的結(jié)果。 39局部搜索算法3（Local Search 3）1，k = 02，隨機(jī)的選擇一個(gè)初始的可能解x0D，xb=x0， P=N(xb)3，如果不滿足結(jié)束條件，則4，Begin5， 選擇P的一個(gè)子集P，xn為P中的最優(yōu)解6， 如果f(xn) f(xb)，則xb xn，P = N(xb)，轉(zhuǎn)37， 否則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é)束 40多種方法的集

13、成以上幾種解決方法可以結(jié)合在一起使用，比如第一、第二種方法的結(jié)合，就產(chǎn)生了我們將在后面介紹的模擬退火方法。41皇后搜索算法（Queen Search）1，隨機(jī)地將n個(gè)皇后分布在棋盤上，使得棋盤 的每行、每列只有一個(gè)皇后。2，計(jì)算皇后間的沖突數(shù)conflicts。3，如果沖突數(shù)conflicts等于0，則轉(zhuǎn)（6）4，對(duì)于棋盤上的任意兩個(gè)皇后，交換他們的行 或者列，如果交換后的沖突數(shù)conflicts減少， 則接受這種交換，更新沖突數(shù)conflicts，轉(zhuǎn)3。5，如果陷入了局部極小，既交換了所有的皇后 后，沖突數(shù)仍然不能下降，則轉(zhuǎn)1。6，輸出結(jié)果7，結(jié)束。 42不同規(guī)模下皇后問(wèn)題的平均求解時(shí)間 皇

14、 后 數(shù)1005001000200050001000030000平均時(shí)間（秒）5512281709001000043模擬退火算法是局部搜索算法的一種擴(kuò)展最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地將模擬退火算法用于求解組合優(yōu)化問(wèn)題。 基本思想是借用金屬的退化過(guò)程改進(jìn)局部搜索算法44固體退火過(guò)程溶解過(guò)程：隨著溫度的不斷上升，粒子逐漸脫離開其平衡位置，變得越來(lái)越自由，直到達(dá)到固體的溶解溫度，粒子排列從原來(lái)的有序狀態(tài)變?yōu)橥耆臒o(wú)序狀態(tài)。 退火過(guò)程：隨著溫度的下降，粒子的熱運(yùn)動(dòng)逐漸減弱，粒子逐漸停留在不同的狀態(tài)，其排列也從無(wú)序向有序方向發(fā)展，直至到溫度很低時(shí)

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

16、別表示在狀態(tài)i、j下的能量，T是溫度，K0是波爾茲曼常數(shù)。 48在給定的溫度T下，當(dāng)進(jìn)行足夠多次的狀態(tài)轉(zhuǎn)換后，系統(tǒng)將達(dá)到熱平衡。此時(shí)系統(tǒng)處于某個(gè)狀態(tài)i的概率由波爾茲曼（Boltzmann）分布給出： （6）其中 為歸一化因子，S是所有可能狀態(tài)的集合。 49考察一下式（6）隨溫度T的變化情況：同一溫度下，兩個(gè)能量不同的狀態(tài)高溫下的情況低溫下的情況 當(dāng)溫度下降時(shí)的情況50在給定的溫度T下，設(shè)有i、j兩個(gè)狀態(tài)，E(i)E(j) ：即在任何溫度T下，系統(tǒng)處于能量低的狀態(tài)的概率大于處于能量高的狀態(tài)的概率。 由于E(i)E(j)，所以該項(xiàng)小于1 51當(dāng)溫度趨于無(wú)窮時(shí)： 其中|S|表示系統(tǒng)所有可能的狀態(tài)數(shù)。

17、 當(dāng)溫度很高時(shí)，系統(tǒng)處于各個(gè)狀態(tài)的概率基本相等，接近于平均值，與所處狀態(tài)的能量幾乎無(wú)關(guān)。 52當(dāng)溫度趨于0時(shí) ：設(shè)Sm表示系統(tǒng)最小能量狀態(tài)的集合，Em是系統(tǒng)的最小能量。上式分子、分母同乘以 53當(dāng)溫度趨近于0時(shí)，系統(tǒng)以等概率趨近于幾個(gè)能量最小的狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)的概率為0。以概率1達(dá)到能量最小的狀態(tài)。54當(dāng)溫度上升或下降時(shí)：55系統(tǒng)落入低能量狀態(tài)的概率隨著溫度的下降單調(diào)上升，而系統(tǒng)落入高能量狀態(tài)的概率隨著溫度的下降單調(diào)下降。 56在高溫下，系統(tǒng)基本處于無(wú)序的狀態(tài)，基本以等概率落入各個(gè)狀態(tài)。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于系統(tǒng)落入高能量狀態(tài)的概率，這樣在同一溫度下，如果系統(tǒng)

18、交換的足夠充分，則系統(tǒng)會(huì)趨向于落入較低能量的狀態(tài)。隨著溫度的緩慢下降，系統(tǒng)落入低能量狀態(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)。 57達(dá)到最小能量狀態(tài)的三個(gè)條件 （1）初始溫度必須足夠高；（2）在每個(gè)溫度下，狀態(tài)的交換必須足夠充分；（3）溫度T的下降必須足夠緩慢。58組

19、合優(yōu)化問(wèn)題與退火過(guò)程的類比固體退火過(guò)程組合優(yōu)化問(wèn)題物理系統(tǒng)中的一個(gè)狀態(tài)組合優(yōu)化問(wèn)題的解狀態(tài)的能量解的指標(biāo)函數(shù)能量最低狀態(tài)最優(yōu)解溫度控制參數(shù)591，隨機(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é)果。16，結(jié)束。6

20、0算法中的問(wèn)題初始溫度的選取內(nèi)循環(huán)的結(jié)束條件，即每個(gè)溫度狀態(tài)交換何時(shí)結(jié)束外循環(huán)的結(jié)束條件，即溫度下降到什么時(shí)候結(jié)束溫度的下降方法61在模擬退火過(guò)程中，給定溫度下?tīng)顟B(tài)（解）的轉(zhuǎn)移可以看作是一個(gè)馬爾可夫鏈。對(duì)于任意兩個(gè)狀態(tài)i和j，我們用Pt(i, j)表示溫度t下，從狀態(tài)i轉(zhuǎn)移到狀態(tài)j的一步轉(zhuǎn)移概率，則有：其中：Gt(i,j) 是產(chǎn)生概率，表示從狀態(tài)i產(chǎn)生狀態(tài)j的概率。At(i,j) 是接受概率，表示在狀態(tài)i產(chǎn)生狀態(tài)j后，接受狀態(tài)j的概率。 62定理163滿足條件的Gt(i,j)、At(i,j) 舉例： 說(shuō)明：條件2的后半部分除外，該條件與具體的問(wèn)題有關(guān)。64定理2：在定理1的條件下，如果對(duì)于任意

21、兩個(gè)狀態(tài) 有：則有： 65定理3（放寬了定理1的條件） Gt(i,j)、At(i,j)滿足定理1中除條件（2）以外的所有其他條件，并且： 1，對(duì)于任意兩個(gè)狀態(tài)i、j，它們相互為鄰居或者相互都不為鄰居；2，對(duì)于任意i，Gt(i,j)滿足：3，狀態(tài)空間S對(duì)于鄰域是連通的； 則與模擬退火算法相伴的時(shí)齊馬爾可夫鏈存在平穩(wěn)分布，其分布概率為： 66算法的實(shí)現(xiàn)（1）初始溫度t0；（2）溫度t的衰減函數(shù)，即溫度的下降 方法；（3）算法的終止準(zhǔn)則，用終止溫度tf或 者終止條件給出；（4）每個(gè)溫度t下的馬爾可夫鏈長(zhǎng)度Lk。 67起始溫度的選?。?）一個(gè)合適的初始溫度，應(yīng)保證平穩(wěn)分布中每一個(gè)狀態(tài)的概率基本相等，也

22、就是接受概率P0近似等于1。在Metropolis準(zhǔn)則下，即要求： 68如果我們給定一個(gè)比較大的接受概率P0，則： 69其中， 可以有以下估計(jì)方式：70起始溫度的選取（2）假設(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ù)為：71所以平均接受率為： 求解有：72起始溫度的選?。?）模擬固體的升溫過(guò)程：（1）給定一個(gè)希望的初始接受概率P0，給定一個(gè)較低的初始溫度t0，比如t01；（2）隨機(jī)的產(chǎn)生一個(gè)狀態(tài)序列，并計(jì)算該序列的接收率： 如果接收率大于給定的初始接受概率P0，則轉(zhuǎn)（4）；（3）提高溫度

23、，更新t0，轉(zhuǎn)（2）；（4）結(jié)束。73溫度的下降方法（1） 等比例下降 74溫度的下降方法（2）等值下降 75溫度的下降方法（3）由定理1我們知道，在一定的條件下，與模擬退火算法相伴的時(shí)齊馬爾可夫鏈存在平穩(wěn)分布。如果溫度每次下降的幅度比較小的話，則相鄰溫度下的平穩(wěn)分布應(yīng)該變化不大，也就是說(shuō)，對(duì)于任意一個(gè)狀態(tài)i，相鄰溫度下的平穩(wěn)分布應(yīng)滿足： 76一個(gè)充分條件是：77兩邊取對(duì)數(shù)，并整理得：用 代替 可得溫度的衰減函數(shù)： 78每一溫度下的停止準(zhǔn)則（1） 固定長(zhǎng)度方法 在每一個(gè)溫度下，都使用相同的Lk。Lk的選取與具體的問(wèn)題相關(guān)，一般與鄰域的大小直接關(guān)聯(lián)，通常選擇為問(wèn)題規(guī)模n的一個(gè)多項(xiàng)式函數(shù)。 79每

24、一溫度下的停止準(zhǔn)則（2）基于接受率的停止準(zhǔn)則 ：規(guī)定一個(gè)接受次數(shù)R，在某一溫度下，只有被接受的狀態(tài)數(shù)達(dá)到R時(shí)，在該溫度下的迭代才停止，轉(zhuǎn)入下一個(gè)溫度。 規(guī)定一個(gè)狀態(tài)接受率R，R等于該溫度下接受的狀態(tài)數(shù)除以總生成的總狀態(tài)數(shù)。如果接受率達(dá)到了R，則停止該溫度下的迭代，轉(zhuǎn)入下一個(gè)溫度。在迭代的過(guò)程中，若干相鄰的狀態(tài)稱為“一代”，如果相鄰兩代的解的指標(biāo)函數(shù)差值小于規(guī)定的值的話，則停止該溫度下的迭代。 80算法的終止原則 （1）零度法 設(shè)定一個(gè)正常數(shù)e，當(dāng)時(shí)tke時(shí)，算法結(jié)束。 81算法的終止原則 （2）循環(huán)總控制法 給定一個(gè)指定的溫度下降次數(shù)K，當(dāng)溫度的迭代次數(shù)達(dá)到K次時(shí)，則算法停止。 82算法的終止

25、原則 （3）無(wú)變化控制法 如果在相鄰的n個(gè)溫度中，得到的解的指標(biāo)函數(shù)值無(wú)任何變化，則說(shuō)明算法已經(jīng)收斂。 83算法的終止原則 （4）接受概率控制法 給定一個(gè)小的概率值p，如果在當(dāng)前溫度下除了局部最優(yōu)狀態(tài)外，其他狀態(tài)的接受概率小于p值，則算法結(jié)束。 84算法的終止原則 （5）領(lǐng)域平均概率控制法 設(shè)大小為N的一個(gè)領(lǐng)域，在鄰域內(nèi)一個(gè)狀態(tài)被接受的平均概率為1/N。設(shè)f0、f1為該領(lǐng)域中的局部最優(yōu)值和局部次最優(yōu)值。則次最優(yōu)解是除了局部最優(yōu)解以外接受概率最大的，其接受概率為： 85如果該概率值小于平均值1/N時(shí)，即： 可以認(rèn)為從局部最優(yōu)解跳出的可能性已經(jīng)很小了，因此可以終止算法。此時(shí)的終止溫度tf為： 86算法的終止原則 （6