人工智能導論-第三章高級搜索1課件

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

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

Q

QQ

Q

定義映射N為棋盤上任意兩個皇后的所在行或列進行交換，即S中任意兩個元素交換位置。例：當S=(2,4,1,3)時，其鄰域為：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)}例：旅行商問題用一個城市的序列表示一個可能的解。通過交換兩個城市的位置獲取S的鄰居例：簡單交換方法設(shè)S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)則通過交換xi和xj兩個城市的位置可以得到S的一個鄰居：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是選取的兩個城市，所謂的逆序交換方式是指，通過逆轉(zhuǎn)xi、xj兩個城市之間的城市次序來得到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局部搜索算法基本思想：在搜索過程中，始終向著離目標最接近的方向搜索。目標可以是最大值，也可以是最小值。在后面的介紹中，如果沒有特殊說明，均假定是最小值。局部搜索算法（LocalSearch）1，隨機的選擇一個初始的可能解x0∈D，xb=x0，P=N(xb)；2，如果不滿足結(jié)束條件，則3，Begin4， 選擇P的一個子集P'，xn為P'中的最優(yōu)解5， 如果f(xn)<f(xb)，則xb＝xn，P=N(xb)，轉(zhuǎn)2；f(x)為指標函數(shù)。6， 否則P=P–P'，轉(zhuǎn)2。7，End8，輸出計算結(jié)果9，結(jié)束例：5城市旅行商問題●●●●●ABCDE71361071010965設(shè)初始的可能解：x0=(a,b,c,d,e)f(xb)=f(x0)=38通過交換兩個城市獲得領(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è)每次隨機從P中選擇一個鄰居。第一次循環(huán)從P中選擇一個元素，假設(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中選擇一個元素，假設(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中選擇一個元素，假設(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中選擇一個元素，假設(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中選擇一個元素，假設(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中選擇一個元素，假設(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中選擇一個元素，假設(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中選擇一個元素，假設(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中選擇一個元素，假設(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中選擇一個元素，假設(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中選擇一個元素，假設(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)的點，而是依據(jù)一定的概率，從鄰域內(nèi)選擇一個點，指標函數(shù)優(yōu)的點，被選中的概率比較大，而指標函數(shù)差的點，被選中的概率比較小。選擇概率的計算設(shè)求最大值時：選擇概率的計算當求最小值時：局部搜索算法1（LocalSearch1）1，隨機的選擇一個初始的可能解x0∈D，xb=x0，P=N(xb)2，如果不滿足結(jié)束條件，則3，Begin4，對于所有的x∈P計算指標函數(shù)f(x)，并按照式（3）或者式（4）計算每一個點x的概率5，依計算的概率值，從P中隨機選擇一個點xn，xb＝xn，P=N(xb)，轉(zhuǎn)26，End7，輸出計算結(jié)果8，結(jié)束存在的問題步長問題初始值搜索到的最優(yōu)解解決方法變步長初始值搜索到的最優(yōu)解局部搜索算法2（LocalSearch2）1，隨機的選擇一個初始的可能解x0∈D，xb=x0，確定一個初始步長計算P=N(xb)2，如果不滿足結(jié)束條件，則3，Begin4， 選擇P的一個子集P'，xn為P'中的最優(yōu)解5， 如果f(xn)<f(xb)，則xb＝xn6， 按照某種策略改變步長，計算P=N(xb)，轉(zhuǎn)27， 否則P=P–P'，轉(zhuǎn)2。8，End9，輸出計算結(jié)果10，結(jié)束存在問題起始點問題AB全局最大值局部最大值解決方法隨機的生成一些初始點，從每個初始點出發(fā)進行搜索，找到各自的最優(yōu)解。再從這些最優(yōu)解中選擇一個最好的結(jié)果作為最終的結(jié)果。局部搜索算法3（LocalSearch3）1，k=02，隨機的選擇一個初始的可能解x0∈D，xb=x0，P=N(xb)3，如果不滿足結(jié)束條件，則4，Begin5， 選擇P的一個子集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達到了指定的次數(shù)，則從k個結(jié)果中選擇一個最好的結(jié)果輸出，否則轉(zhuǎn)（2）11，輸出結(jié)果12，結(jié)束多種方法的集成以上幾種解決方法可以結(jié)合在一起使用，比如第一、第二種方法的結(jié)合，就產(chǎn)生了我們將在后面介紹的模擬退火方法?；屎笏阉魉惴ǎ≦ueenSearch）1，隨機地將n個皇后分布在棋盤上，使得棋盤的每行、每列只有一個皇后。2，計算皇后間的沖突數(shù)conflicts。3，如果沖突數(shù)conflicts等于0，則轉(zhuǎn)（6）4，對于棋盤上的任意兩個皇后，交換他們的行或者列，如果交換后的沖突數(shù)conflicts減少，則接受這種交換，更新沖突數(shù)conflicts，轉(zhuǎn)3。5，如果陷入了局部極小，既交換了所有的皇后后，沖突數(shù)仍然不能下降，則轉(zhuǎn)1。6，輸出結(jié)果7，結(jié)束。不同規(guī)模下皇后問題的

平均求解時間

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

粒子不同的排列結(jié)構(gòu)，對應著不同的能量水平。如果退火過程是緩慢進行的，也就是說，溫度的下降如果非常緩慢的話，使得在每個溫度下，粒子的排列都達到一種平衡態(tài)，則當溫度趨于0（絕對溫度）時，系統(tǒng)的能量將趨于最小值。如果以粒子的排列或者相應的能量來表達固體所處的狀態(tài)，在溫度T下，固體所處的狀態(tài)具有一定的隨機性。一方面，物理系統(tǒng)傾向于能量較低的狀態(tài)，另一方面，熱運動又妨礙了系統(tǒng)準確落入低能狀態(tài)。Metropolis準則

從狀態(tài)i轉(zhuǎn)換為狀態(tài)j的準則：如果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下，當進行足夠多次的狀態(tài)轉(zhuǎn)換后，系統(tǒng)將達到熱平衡。此時系統(tǒng)處于某個狀態(tài)i的概率由波爾茲曼（Boltzmann）分布給出：（6）其中為歸一化因子，S是所有可能狀態(tài)的集合?？疾煲幌率剑?）隨溫度T的變化情況：同一溫度下，兩個能量不同的狀態(tài)高溫下的情況低溫下的情況當溫度下降時的情況在給定的溫度T下，設(shè)有i、j兩個狀態(tài)，E(i)＜E(j)：即在任何溫度T下，系統(tǒng)處于能量低的狀態(tài)的概率大于處于能量高的狀態(tài)的概率。

由于E(i)＜E(j)，所以該項小于1

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

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

當溫度趨于0時：設(shè)Sm表示系統(tǒng)最小能量狀態(tài)的集合，Em是系統(tǒng)的最小能量。上式分子、分母同乘以當溫度趨近于0時，系統(tǒng)以等概率趨近于幾個能量最小的狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)的概率為0。以概率1達到能量最小的狀態(tài)。當溫度上升或下降時：系統(tǒng)落入低能量狀態(tài)的概率隨著溫度的下降單調(diào)上升，而系統(tǒng)落入高能量狀態(tài)的概率隨著溫度的下降單調(diào)下降。在高溫下，系統(tǒng)基本處于無序的狀態(tài)，基本以等概率落入各個狀態(tài)。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于系統(tǒng)落入高能量狀態(tài)的概率，這樣在同一溫度下，如果系統(tǒng)交換的足夠充分，則系統(tǒng)會趨向于落入較低能量的狀態(tài)。隨著溫度的緩慢下降，系統(tǒng)落入低能量狀態(tài)的概率逐步增加，而落入高能量狀態(tài)的概率逐步減少，使得系統(tǒng)各狀態(tài)能量的期望值隨溫度的下降單調(diào)下降，而只有那些能量小于期望值的狀態(tài)，其概率才隨溫度下降增加，其他狀態(tài)均隨溫度下降而下降。因此，隨著能量期望值的逐步下降，能量低于期望值的狀態(tài)逐步減少，當溫度趨于0時，只剩下那些具有最小能量的狀態(tài)，系統(tǒng)處于其他狀態(tài)的概率趨近于0。因此最終系統(tǒng)將以概率1處于具有最小能量的一個狀態(tài)。達到最小能量狀態(tài)的三個條件

（1）初始溫度必須足夠高；（2）在每個溫度下，狀態(tài)的交換必須足夠充分；（3）溫度T的下降必須足夠緩慢。組合優(yōu)化問題與退火過程的類比固體退火過程組合優(yōu)化問題物理系統(tǒng)中的一個狀態(tài)組合優(yōu)化問題的解狀態(tài)的能量解的指標函數(shù)能量最低狀態(tài)最優(yōu)解溫度控制參數(shù)1，隨機選擇一個解i，k=0，t0=Tmax（初始溫度），計算指標函數(shù)f(i)。2，如果滿足結(jié)束條件，則轉(zhuǎn)（15）。3，Begin4， 如果在該溫度內(nèi)達到了平衡條件，則轉(zhuǎn)（13）。5， Begin6， 從i的鄰域N(i)中隨機選擇一個解j。7， 計算指標函數(shù)f(j)。8， 如果f(j)<f(i)，則i=j，f(i)=f(j)，轉(zhuǎn)（4）。9， 計算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é)束條件，即每個溫度狀態(tài)交換何時結(jié)束外循環(huán)的結(jié)束條件，即溫度下降到什么時候結(jié)束溫度的下降方法在模擬退火過程中，給定溫度下狀態(tài)（解）的轉(zhuǎn)移可以看作是一個馬爾可夫鏈。對于任意兩個狀態(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的條件下，如果對于任意兩個狀態(tài)

有：則有：定理3（放寬了定理1的條件）

Gt(i,j)、At(i,j)滿足定理1中除條件（2）以外的所有其他條件，并且：1，對于任意兩個狀態(tài)i、j，它們相互為鄰居或者相互都不為鄰居；2，對于任意i，Gt(i,j)滿足：3，狀態(tài)空間S對于鄰域是連通的；則與模擬退火算法相伴的時齊馬爾可夫鏈存在平穩(wěn)分布，其分布概率為：

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

固定長度方法在每一個溫度下，都使用相同的Lk。Lk的選取與具體的問題相關(guān)，一般與鄰域的大小直接關(guān)聯(lián)，通常選擇為問題規(guī)模n的一個多項式函數(shù)。每一溫度下的停止準則（2）基于接受率的停止準則：規(guī)定一個接受次數(shù)R，在某一溫度下，只有被接受的狀態(tài)數(shù)達到R時，在該溫度下的迭代才停止，轉(zhuǎn)入下一個溫度。規(guī)定一個狀態(tài)接受率R，R等于該溫度下接受的狀態(tài)數(shù)除以總生成的總狀態(tài)數(shù)。如果接受率達到了R，則停止該溫度下的迭代，轉(zhuǎn)入下一個溫度。在迭代的過程中，若干相鄰的狀態(tài)稱為“一代”，如果相鄰兩代的解的指標函數(shù)差值小于規(guī)定的值的話，則停止該溫度下的迭代。算法的終止原則（1）零度法設(shè)定一個正常數(shù)e，當時tk<e時，算法結(jié)束。算法的終止原則（2）循環(huán)總控制法

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

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

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

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

是一門交叉學科

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

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

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

哪一個是計算機,則可以認為這臺被測的計算機具有智能。

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

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

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

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

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

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