人工智能導(dǎo)論-第三章高級(jí)搜索1課件

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

輸入量n復(fù)雜性函數(shù)10203040100n10ns20ns30ns40ns100nsnlogn10ns26.0ns44.3ns64.1ns200nsn2100ns400ns900ns1.6us10us2n1.0us1.0ms1.1s18.3min4.0世紀(jì)n!3.6ms77.1年8.4×1013世紀(jì)2.6×1029世紀(jì)3.0×10139世紀(jì)時(shí)間復(fù)雜性函數(shù)比較（10億次/秒）一些難的組合優(yōu)化問題旅行商問題背包問題裝箱問題...尋求在可以接受的時(shí)間內(nèi)得到滿意解的方法鄰域的概念鄰域，簡(jiǎn)單的說就是一個(gè)點(diǎn)附近的其他點(diǎn)的集合。在距離空間，鄰域就是以某一點(diǎn)為中心的圓。在組合優(yōu)化問題中的定義：設(shè)D是問題的定義域，若存在一個(gè)映射N，使得：則稱N(S)為S的鄰域。領(lǐng)域中的元素稱為鄰居。例：皇后問題S={Si}表示一個(gè)可能解，其中Si表示在第i行，第Si列有一個(gè)皇后。如四皇后問題的一個(gè)解：S=(2,4,1,3)

Q

QQ

Q

定義映射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)}例：旅行商問題用一個(gè)城市的序列表示一個(gè)可能的解。通過交換兩個(gè)城市的位置獲取S的鄰居例：簡(jiǎn)單交換方法設(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)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1例：逆序交換方法設(shè)xi、xj是選取的兩個(gè)城市，所謂的逆序交換方式是指，通過逆轉(zhuǎn)xi、xj兩個(gè)城市之間的城市次序來得到S的鄰居。設(shè)：S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)則：S'=(x1,x2,…xi-1,xi,xj-1,xj-2…,xi+1,xj,xj+1,…,xn)x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1局部搜索算法基本思想：在搜索過程中，始終向著離目標(biāo)最接近的方向搜索。目標(biāo)可以是最大值，也可以是最小值。在后面的介紹中，如果沒有特殊說明，均假定是最小值。局部搜索算法（LocalSearch）1，隨機(jī)的選擇一個(gè)初始的可能解x0∈D，xb=x0，P=N(xb)；2，如果不滿足結(jié)束條件，則3，Begin4， 選擇P的一個(gè)子集P'，xn為P'中的最優(yōu)解5， 如果f(xn)<f(xb)，則xb＝xn，P=N(xb)，轉(zhuǎn)2；f(x)為指標(biāo)函數(shù)。6， 否則P=P–P'，轉(zhuǎn)2。7，End8，輸出計(jì)算結(jié)果9，結(jié)束例：5城市旅行商問題●●●●●ABCDE71361071010965設(shè)初始的可能解：x0=(a,b,c,d,e)f(xb)=f(x0)=38通過交換兩個(gè)城市獲得領(lǐng)域P={(a,c,b,d,e),(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)}設(shè)每次隨機(jī)從P中選擇一個(gè)鄰居。第一次循環(huán)從P中選擇一個(gè)元素，假設(shè)xn=(a,c,b,d,e),f(xn)=42,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)}第二次循環(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)}第三次循環(huán)從P中選擇一個(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)}第四次循環(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)}第五次循環(huán)從P中選擇一個(gè)元素，假設(shè)xn=(a,b,e,d,c),f(xn)=34,f(xn)<f(xb),xb=(a,b,e,d,c),P={(a,e,b,d,c),(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)}第六次循環(huán)從P中選擇一個(gè)元素，假設(shè)xn=(a,e,b,d,c),f(xn)=44,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)}第七次循環(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)}第八次循環(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,d)}第九次循環(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)}第十次循環(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)}第十一次循環(huán)從P中選擇一個(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。存在的問題局部最優(yōu)問題

解決方法每次并不一定選擇鄰域內(nèi)最優(yōu)的點(diǎn)，而是依據(jù)一定的概率，從鄰域內(nèi)選擇一個(gè)點(diǎn)，指標(biāo)函數(shù)優(yōu)的點(diǎn)，被選中的概率比較大，而指標(biāo)函數(shù)差的點(diǎn)，被選中的概率比較小。選擇概率的計(jì)算設(shè)求最大值時(shí)：選擇概率的計(jì)算當(dāng)求最小值時(shí)：局部搜索算法1（LocalSearch1）1，隨機(jī)的選擇一個(gè)初始的可能解x0∈D，xb=x0，P=N(xb)2，如果不滿足結(jié)束條件，則3，Begin4，對(duì)于所有的x∈P計(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é)束存在的問題步長(zhǎng)問題初始值搜索到的最優(yōu)解解決方法變步長(zhǎng)初始值搜索到的最優(yōu)解局部搜索算法2（LocalSearch2）1，隨機(jī)的選擇一個(gè)初始的可能解x0∈D，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é)束存在問題起始點(diǎn)問題AB全局最大值局部最大值解決方法隨機(jī)的生成一些初始點(diǎn)，從每個(gè)初始點(diǎn)出發(fā)進(jìn)行搜索，找到各自的最優(yōu)解。再從這些最優(yōu)解中選擇一個(gè)最好的結(jié)果作為最終的結(jié)果。局部搜索算法3（LocalSearch3）1，k=02，隨機(jī)的選擇一個(gè)初始的可能解x0∈D，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é)束多種方法的集成以上幾種解決方法可以結(jié)合在一起使用，比如第一、第二種方法的結(jié)合，就產(chǎn)生了我們將在后面介紹的模擬退火方法。皇后搜索算法（QueenSearch）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é)束。不同規(guī)模下皇后問題的

平均求解時(shí)間

皇后數(shù)1005001000200050001000030000平均時(shí)間（秒）55122817090010000說明：早期比較慢的機(jī)器的結(jié)果(PIII)模擬退火算法是局部搜索算法的一種擴(kuò)展最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地將模擬退火算法用于求解組合優(yōu)化問題?；舅枷胧墙栌媒饘俚耐嘶疬^程改進(jìn)局部搜索算法固體退火過程溶解過程：隨著溫度的不斷上升，粒子逐漸脫離開其平衡位置，變得越來越自由，直到達(dá)到固體的溶解溫度，粒子排列從原來的有序狀態(tài)變?yōu)橥耆臒o序狀態(tài)。退火過程：隨著溫度的下降，粒子的熱運(yùn)動(dòng)逐漸減弱，粒子逐漸停留在不同的狀態(tài)，其排列也從無序向有序方向發(fā)展，直至到溫度很低時(shí)，粒子重新以一定的結(jié)構(gòu)排列。

粒子不同的排列結(jié)構(gòu)，對(duì)應(yīng)著不同的能量水平。如果退火過程是緩慢進(jìn)行的，也就是說，溫度的下降如果非常緩慢的話，使得在每個(gè)溫度下，粒子的排列都達(dá)到一種平衡態(tài)，則當(dāng)溫度趨于0（絕對(duì)溫度）時(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)。Metropolis準(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)分別表示在狀態(tài)i、j下的能量，T是溫度，K＞0是波爾茲曼常數(shù)。在給定的溫度T下，當(dāng)進(jìn)行足夠多次的狀態(tài)轉(zhuǎn)換后，系統(tǒng)將達(dá)到熱平衡。此時(shí)系統(tǒng)處于某個(gè)狀態(tài)i的概率由波爾茲曼（Boltzmann）分布給出：（6）其中為歸一化因子，S是所有可能狀態(tài)的集合?？疾煲幌率剑?）隨溫度T的變化情況：同一溫度下，兩個(gè)能量不同的狀態(tài)高溫下的情況低溫下的情況當(dāng)溫度下降時(shí)的情況在給定的溫度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

當(dāng)溫度趨于無窮時(shí)：其中|S|表示系統(tǒng)所有可能的狀態(tài)數(shù)。

當(dāng)溫度很高時(shí)，系統(tǒng)處于各個(gè)狀態(tài)的概率基本相等，接近于平均值，與所處狀態(tài)的能量幾乎無關(guān)。

當(dāng)溫度趨于0時(shí)：設(shè)Sm表示系統(tǒng)最小能量狀態(tài)的集合，Em是系統(tǒng)的最小能量。上式分子、分母同乘以當(dāng)溫度趨近于0時(shí)，系統(tǒng)以等概率趨近于幾個(gè)能量最小的狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)的概率為0。以概率1達(dá)到能量最小的狀態(tài)。當(dāng)溫度上升或下降時(shí)：系統(tǒng)落入低能量狀態(tài)的概率隨著溫度的下降單調(diào)上升，而系統(tǒng)落入高能量狀態(tài)的概率隨著溫度的下降單調(diào)下降。在高溫下，系統(tǒng)基本處于無序的狀態(tài)，基本以等概率落入各個(gè)狀態(tài)。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于系統(tǒng)落入高能量狀態(tài)的概率，這樣在同一溫度下，如果系統(tǒng)交換的足夠充分，則系統(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)。達(dá)到最小能量狀態(tài)的三個(gè)條件

（1）初始溫度必須足夠高；（2）在每個(gè)溫度下，狀態(tài)的交換必須足夠充分；（3）溫度T的下降必須足夠緩慢。組合優(yōu)化問題與退火過程的類比固體退火過程組合優(yōu)化問題物理系統(tǒng)中的一個(gè)狀態(tài)組合優(yōu)化問題的解狀態(tài)的能量解的指標(biāo)函數(shù)能量最低狀態(tài)最優(yōu)解溫度控制參數(shù)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)<f(i)，則i=j，f(i)=f(j)，轉(zhuǎn)（4）。9， 計(jì)算10， 如果Pt(i=>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é)束。算法中的問題初始溫度的選取內(nèi)循環(huán)的結(jié)束條件，即每個(gè)溫度狀態(tài)交換何時(shí)結(jié)束外循環(huán)的結(jié)束條件，即溫度下降到什么時(shí)候結(jié)束溫度的下降方法在模擬退火過程中，給定溫度下狀態(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的概率。定理1滿足條件的Gt(i,j)、At(i,j)舉例：

說明：條件2的后半部分除外，該條件與具體的問題有關(guān)。定理2：在定理1的條件下，如果對(duì)于任意兩個(gè)狀態(tài)

有：則有：定理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)分布，其分布概率為：

算法的實(shí)現(xiàn)（1）初始溫度t0；（2）溫度t的衰減函數(shù)，即溫度的下降 方法；（3）算法的終止準(zhǔn)則，用終止溫度tf或 者終止條件給出；（4）每個(gè)溫度t下的馬爾可夫鏈長(zhǎng)度Lk。起始溫度的選?。?）一個(gè)合適的初始溫度，應(yīng)保證平穩(wěn)分布中每一個(gè)狀態(tài)的概率基本相等，也就是接受概率P0近似等于1。在Metropolis準(zhǔn)則下，即要求：如果我們給定一個(gè)比較大的接受概率P0，則：其中，可以有以下估計(jì)方式：起始溫度的選?。?）假設(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ù)為：所以平均接受率為：求解有：起始溫度的選?。?）模擬固體的升溫過程：（1）給定一個(gè)希望的初始接受概率P0，給定一個(gè)較低的初始溫度t0，比如t0＝1；（2）隨機(jī)的產(chǎn)生一個(gè)狀態(tài)序列，并計(jì)算該序列的接收率：如果接收率大于給定的初始接受概率P0，則轉(zhuǎn)（4）；（3）提高溫度，更新t0，轉(zhuǎn)（2）；（4）結(jié)束。溫度的下降方法（1）等比例下降溫度的下降方法（2）等值下降溫度的下降方法（3）由定理1我們知道，在一定的條件下，與模擬退火算法相伴的時(shí)齊馬爾可夫鏈存在平穩(wěn)分布。如果溫度每次下降的幅度比較小的話，則相鄰溫度下的平穩(wěn)分布應(yīng)該變化不大，也就是說，對(duì)于任意一個(gè)狀態(tài)i，相鄰溫度下的平穩(wěn)分布應(yīng)滿足：一個(gè)充分條件是：兩邊取對(duì)數(shù)，并整理得：用代替可得溫度的衰減函數(shù)：每一溫度下的停止準(zhǔn)則（1）

固定長(zhǎng)度方法在每一個(gè)溫度下，都使用相同的Lk。Lk的選取與具體的問題相關(guān)，一般與鄰域的大小直接關(guān)聯(lián)，通常選擇為問題規(guī)模n的一個(gè)多項(xiàng)式函數(shù)。每一溫度下的停止準(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è)溫度。在迭代的過程中，若干相鄰的狀態(tài)稱為“一代”，如果相鄰兩代的解的指標(biāo)函數(shù)差值小于規(guī)定的值的話，則停止該溫度下的迭代。算法的終止原則（1）零度法設(shè)定一個(gè)正常數(shù)e，當(dāng)時(shí)tk<e時(shí)，算法結(jié)束。算法的終止原則（2）循環(huán)總控制法

給定一個(gè)指定的溫度下降次數(shù)K，當(dāng)溫度的迭代次數(shù)達(dá)到K次時(shí)，則算法停止。算法的終止原則（3）無變化控制法如果在相鄰的n個(gè)溫度中，得到的解的指標(biāo)函數(shù)值無任何變化，則說明算法已經(jīng)收斂。算法的終止原則（4）接受概率控制法給定一個(gè)小的概率值p，如果在當(dāng)前溫度下除了局部最優(yōu)狀態(tài)外，其他狀態(tài)的接受概率小于p值，則算法結(jié)束。算法的終止原則（5）領(lǐng)域平均概率控制法設(shè)大小為N的一個(gè)鄰域，在鄰域內(nèi)一個(gè)狀態(tài)被接受的平均概率為1/N。設(shè)f0、f1為該領(lǐng)域中的局部最優(yōu)值和局部次最優(yōu)值。則次最優(yōu)解是除了局部最優(yōu)解以外接受概率最大的，其接受概率為：如果該概率值小于平均值1/N時(shí)，即：可以認(rèn)為從局部最優(yōu)解跳出的可能性已經(jīng)很小了，因此可以終止算法。此時(shí)的終止溫度tf為：算法的終止原則（6）相對(duì)誤差估計(jì)法設(shè)溫度t時(shí)指標(biāo)函數(shù)的期望值為：則當(dāng)終止溫度<<1時(shí)，由泰勒展開近似有：由于：所以可用下式估計(jì)當(dāng)前解與最優(yōu)解之間的誤差：或者使用相對(duì)于的相對(duì)誤差：說明：推導(dǎo)請(qǐng)見補(bǔ)充教材實(shí)際計(jì)算時(shí)：其中：應(yīng)用舉例——旅行商問題

解的表示：n個(gè)城市的任何一種排列均是問題的一個(gè)可能解，表示為:指標(biāo)函數(shù)(能量函數(shù))其中新解的產(chǎn)生采用第一節(jié)介紹的兩個(gè)城市間的逆序交換方式得到問題的一個(gè)新解。設(shè)當(dāng)前解是，被選中要逆序交換的城市是第u和第v個(gè)到訪的城市，u<v。則逆序排列u和v之間的城市，得到問題的新解為：則兩個(gè)路徑的距離差為：新解的接受準(zhǔn)則初始參數(shù)的確定康立山等人的方法：初始溫度t0=280；在每個(gè)溫度下采用固定的迭代次數(shù)，Lk=100n，n為城市數(shù)；溫度的衰減系數(shù)＝0.92，即tk+1=0.92×tk；算法的停止準(zhǔn)則為：當(dāng)相鄰兩個(gè)溫度得到的解無任何變化時(shí)算法停止。NirwanAnsari和EdwinHou的方法：初始溫度t0是這樣確定的：從t0=1出發(fā)，并以t0=1.05×t0對(duì)t0進(jìn)行更新，直到接受概率大于等于0.9時(shí)為止，此時(shí)得到的溫度為初始溫度；在每個(gè)溫度下采用固定的迭代次數(shù)，Lk=10n，n為城市數(shù)；溫度的衰減系數(shù)＝0.95，即tk+1=0.95×tk；10城市旅行商問題求解結(jié)果

路徑長(zhǎng)度出現(xiàn)次數(shù)平均轉(zhuǎn)移次數(shù)路徑最優(yōu)2.6919063952BCADEFGHIJ次優(yōu)2.752464056BCADEGFHIJ第三2.769104053DEFGHIJCBA最差2.89854497ABCDEFHIJG20城市旅行商問題求解結(jié)果

路徑長(zhǎng)度出現(xiàn)次數(shù)平均轉(zhuǎn)移次數(shù)路徑最優(yōu)24.527928740ACLBIQFTMEPRGSOJHDKN次優(yōu)24.621678638ADCLBIQFTMEPRGSOJHKN第三25.17399902ANKDHIOJSGRPEMTFQBLC最差25.5015794AQFTMEPRGSJOIBLCDHKN人工智能

是一門交叉學(xué)科

腦科學(xué)認(rèn)知科學(xué)心理學(xué)語言學(xué)邏輯學(xué)哲學(xué)計(jì)算機(jī)科學(xué)人工智能什么是人工智能人工智能的定義可以分為兩部分，即“人工”和“智能”。關(guān)于什么是“智能”？智能需要具備的特征？具有感知能力（系統(tǒng)輸入）:

機(jī)器視覺，機(jī)器聽覺，圖像語音識(shí)別……具有記憶與思維能力：思維是智能的根本原因，思維是一個(gè)動(dòng)態(tài)的過程。思維分為：邏輯思維，形象思維和頓悟思維。具有學(xué)習(xí)能力及自適應(yīng)能力：適應(yīng)環(huán)境的變換、積累經(jīng)驗(yàn)的能力

具有行為能力（系統(tǒng)輸出）：對(duì)外界的智能化反應(yīng)早期判斷是否有智能的方法———圖靈測(cè)試英國(guó)數(shù)學(xué)家阿蘭·圖靈(AlanTuring)提出了現(xiàn)稱為“圖靈測(cè)試”(TuringTest)的方法。簡(jiǎn)單來講,圖靈測(cè)試的做法是:讓一位測(cè)試者分別與一臺(tái)計(jì)算機(jī)和一個(gè)人進(jìn)行交談(當(dāng)時(shí)是用電傳打字機(jī)),而測(cè)試者事先并不知道哪一個(gè)是人,哪一個(gè)是計(jì)算機(jī)。如果交談后測(cè)試者分不出哪一個(gè)被測(cè)者是人,

哪一個(gè)是計(jì)算機(jī),則可以認(rèn)為這臺(tái)被測(cè)的計(jì)算機(jī)具有智能。

Turing測(cè)試存在的問題“圖靈測(cè)試”沒有規(guī)定問題的范圍和提問的標(biāo)準(zhǔn)僅反映了結(jié)果的比較，無涉及思維過程沒指出是什么人爭(zhēng)論：通過了圖靈檢驗(yàn)的電腦就具備思維能力了么？測(cè)試主持人被測(cè)機(jī)器被測(cè)人中文屋子約翰·西爾勒的中文屋子假設(shè)是說:有一臺(tái)計(jì)算機(jī)閱讀了一段故事并且能正確回答相關(guān)問題,這樣這臺(tái)計(jì)算就通過了圖靈測(cè)試。而西爾勒設(shè)想將這段故事和問題改用中文描述(因?yàn)樗救瞬欢形?,然后將自己封閉在一個(gè)屋子里,代替計(jì)算機(jī)閱讀這段故事并且回答相關(guān)問題。描述這段故事和問題的一連串中文符號(hào)只能通過一個(gè)很小的縫隙被送到屋子里。西爾勒則完全按照原先計(jì)算機(jī)程序的處理方式和過程(如符號(hào)匹配、查找、照抄等)對(duì)這些符號(hào)串進(jìn)行操作,然后把得到的結(jié)果即問題答案通過小縫隙送出去。西爾勒也得到了問題的正確答案。西爾勒認(rèn)為盡管計(jì)算機(jī)用這種符號(hào)處理方式也能正確回答問題,并且也可通過圖靈測(cè)試,但仍然不能說計(jì)算機(jī)就有了智能。

人工智能的發(fā)展概況

1.形成期（1956--1970年）AI誕生于一次歷史性的聚會(huì)(Dartmouth人工智能夏季研討會(huì))時(shí)間：1956年夏季地點(diǎn)：美國(guó)達(dá)特茅斯(Dartmouth)大學(xué)目的：為使計(jì)算機(jī)變得更“聰明”，或者說使計(jì)算機(jī)具有智能發(fā)起人：麥卡錫(J.McCarthy），Dartmouth的年輕數(shù)學(xué)家、計(jì)算機(jī)專家，后為MIT教授明斯基(M.L.Minsky），哈佛大學(xué)數(shù)學(xué)家、神經(jīng)學(xué)家，后為MIT教授洛切斯特(N.Lochester)，IBM公司信息中心負(fù)責(zé)人香農(nóng)(C.E.Shannon)，貝爾實(shí)驗(yàn)室信息部數(shù)學(xué)研究員會(huì)議結(jié)果：由麥卡錫提議正式采用了“ArtificialIntelligence”這一術(shù)語人工智能的發(fā)展概況2.形成期（1956----1970年）其他開創(chuàng)性貢獻(xiàn)1958年，美籍華人數(shù)理邏輯學(xué)家王浩在IBM-740計(jì)算機(jī)上僅用了3-5分鐘就證明了《數(shù)學(xué)原理》命題演算全部220條定理。1965年，費(fèi)根鮑姆(E.A.Feigenbaum)開始研究化學(xué)專家系統(tǒng)DENDRAL，用于質(zhì)譜儀分析有機(jī)化合物的分子結(jié)構(gòu)。1969年召開了第一屆國(guó)際人工智能聯(lián)合會(huì)議（InternationalJointConferenceonAI，IJCAI），標(biāo)志著人工智能作為一門獨(dú)立學(xué)科登上了國(guó)際學(xué)術(shù)舞臺(tái)。此后IJCAI每?jī)赡暾匍_一次。1970年《InternationalJournalofAI》創(chuàng)刊。人工智能的發(fā)展概況3.暗淡期（1966----1974年）失敗的預(yù)言給人工智能的聲譽(yù)造成重大傷害“20年內(nèi)，機(jī)器將能做人所能做的一切”---------1965在博弈方面：塞繆爾的下棋程序在與世界冠軍對(duì)弈時(shí)，5局?jǐn)×?局。在定理證明方面：發(fā)現(xiàn)魯賓遜歸結(jié)法的能力有限。當(dāng)用歸結(jié)原理證明兩個(gè)連續(xù)函數(shù)之和還是連續(xù)函數(shù)時(shí)，推了10萬步也沒證出結(jié)果。在機(jī)器翻譯方面：發(fā)現(xiàn)并不那么簡(jiǎn)單，甚至?xí)[出笑話。例如，把“心有余而力不足”的英語句子翻譯成俄語，再翻譯回來時(shí)竟變成了“酒是好的，肉變質(zhì)了”在問題求解方面：對(duì)于不良結(jié)構(gòu)，會(huì)產(chǎn)生組合爆炸問題。在神經(jīng)生理學(xué)方面：研究發(fā)現(xiàn)人腦有1011-12以上的神經(jīng)元，在現(xiàn)有技術(shù)條件下用機(jī)器從結(jié)構(gòu)上模擬人腦是根本不可能的。在英國(guó)，劍橋大學(xué)的詹姆教授指責(zé)“人工智能研究不是騙局，也是庸人自擾”。從此，形勢(shì)急轉(zhuǎn)直下，在全世界范圍內(nèi)人工智能研究陷入困境、落入低谷。

人工智能的發(fā)展概況

4.知識(shí)應(yīng)用期（1970----1988年）整個(gè)20世紀(jì)80年代，專家系統(tǒng)和知識(shí)工程在全世界得到了迅速發(fā)展。專家系統(tǒng)為企業(yè)等用戶贏得了巨大的經(jīng)濟(jì)效益。在開發(fā)專家系統(tǒng)過程中，許多研究者獲得共識(shí)，即人工智能系統(tǒng)是一個(gè)知識(shí)處理系統(tǒng)，而知識(shí)獲取、知識(shí)表示和知識(shí)利用則成為人工智能系統(tǒng)的三大基本問題。同時(shí)出現(xiàn)新的問題：專家系統(tǒng)本身所存在的應(yīng)用領(lǐng)域狹窄、缺乏常識(shí)性知識(shí)、知識(shí)獲取困難、推理方法單一、沒有分布式功能、不能訪問現(xiàn)存數(shù)據(jù)庫等問題被逐漸暴露出來。人工智能的發(fā)展概況

5.集成發(fā)展期（1986年以來）1997年5月11日，由IBM研制的超級(jí)計(jì)算機(jī)“深藍(lán)”首次擊敗了國(guó)際象棋特級(jí)大師卡斯帕洛夫。2000年，中國(guó)科學(xué)院計(jì)算所開發(fā)出知識(shí)發(fā)現(xiàn)系統(tǒng)MSMiner。該系統(tǒng)是一種多策略知識(shí)發(fā)現(xiàn)平臺(tái)，能夠提供快捷有效的數(shù)據(jù)挖掘解決方案，提供多種知識(shí)發(fā)現(xiàn)方法。2011年，IBM超級(jí)電腦“沃森”亮相美國(guó)最受歡迎的智力競(jìng)賽節(jié)目《危險(xiǎn)邊緣》戰(zhàn)勝該節(jié)目?jī)晌蛔畛晒Φ倪x手。人工智能研究形成了三大學(xué)派符號(hào)主義連接主義行為主義符號(hào)主義又稱：邏輯主義、心理學(xué)派或計(jì)算機(jī)學(xué)派符號(hào)主義的實(shí)現(xiàn)基礎(chǔ)是紐威爾和西蒙提出的物理符號(hào)系統(tǒng)假設(shè)。該學(xué)派認(rèn)為：人類認(rèn)知和思維的基本單元是符號(hào)，而認(rèn)知過程就是在符號(hào)表示上的一種運(yùn)算。它認(rèn)為人是一個(gè)物理符號(hào)系統(tǒng),計(jì)算機(jī)也是一個(gè)物理符號(hào)系