清華大學(xué)人工智能導(dǎo)論課程電子教案公開課一等獎(jiǎng)?wù)n件省課獲獎(jiǎng)?wù)n件

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

輸入量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億次/秒）第6頁某些難組合優(yōu)化問題旅行商問題背包問題裝箱問題...謀求在能夠接收時(shí)間內(nèi)得到滿意解辦法第7頁鄰域概念鄰域，簡單說就是一種點(diǎn)附近其他點(diǎn)集合。在距離空間，鄰域就是以某一點(diǎn)為中心圓。組合優(yōu)化問題定義：設(shè)D是問題定義域，若存在一種映射N，使得：則稱N(S)為S鄰域。第8頁例：皇后問題S={Si}表達(dá)一種也許解，其中Si表達(dá)在第i行，第Si列有一種皇后。如四皇后問題一種解：S=(2,4,1,3)

Q

QQ

Q

第9頁定義映射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頁例：旅行商問題用一種都市序列表達(dá)一種也許解。通過交換兩個(gè)都市位置獲取S鄰居例：簡單交換辦法設(shè)S=(x1,x2,…xi-1,xi,xi+1,…,xj-1,xj,xj+1,…,xn)則通過交換xi和xj兩個(gè)都市位置能夠得到S一種鄰居：S'=(x1,x2,…xi-1,xj,xi+1,…,xj-1,xi,xj+1,…,xn)第11頁x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1第12頁例：逆序交換辦法設(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)第13頁x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1第14頁局部搜索算法基本思想：在搜索過程中，始終向著離目標(biāo)最接近方向搜索。目標(biāo)能夠是最大值，也能夠是最小值。在背面介紹中，假如沒有特殊說明，均假定是最小值。第15頁局部搜索算法（LocalSearch）1，隨機(jī)選擇一種初始也許解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)為指標(biāo)函數(shù)。6， 不然P=P–P'，轉(zhuǎn)2。7，End8，輸出計(jì)算成果9，結(jié)束第16頁例：5都市旅行商問題●●●●●ABCDE71361071010965第17頁設(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中選擇一種鄰居。第18頁第一次循環(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)}第19頁第二次循環(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)}第20頁第三次循環(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)}第21頁第四次循環(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)}第22頁第五次循環(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)}第23頁第六次循環(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)}第24頁第七次循環(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)}第25頁第八次循環(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)}第26頁第九次循環(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)}第27頁第十次循環(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)}第28頁第十一次循環(huán)從P中選擇一種元素，假設(shè)xn=(a,b,e,c,d),f(xn)=41,f(xn)>f(xb),P=P–{xn}={}P等于空，算法結(jié)束，得到成果為xb=(a,b,e,d,c),f(xb)=34。第29頁存在問題局部最優(yōu)問題

第30頁處理辦法每次并不一定選擇鄰域內(nèi)最優(yōu)點(diǎn)，而是根據(jù)一定概率，從鄰域內(nèi)選擇一種點(diǎn)，指標(biāo)函數(shù)優(yōu)點(diǎn)，被選中概率比較大，而指標(biāo)函數(shù)差點(diǎn)，被選中概率比較小。第31頁選擇概率計(jì)算設(shè)求最大值：第32頁選擇概率計(jì)算當(dāng)求最小值時(shí)：第33頁局部搜索算法1（LocalSearch1）1，隨機(jī)選擇一種初始也許解x0∈D，xb=x0，P=N(xb)2，假如不滿足結(jié)束條件，則3，Begin4， 對于所有x∈P計(jì)算指標(biāo)函數(shù)f(x)，并按照式（3）或者式（4）計(jì)算每一種點(diǎn)x概率5， 依計(jì)算概率值，從P中隨機(jī)選擇一種點(diǎn)xn，xb＝xn，P=N(xb)，轉(zhuǎn)26，End7，輸出計(jì)算成果8，結(jié)束第34頁存在問題步長問題初始值搜索到最優(yōu)解第35頁處理辦法變步長初始值搜索到最優(yōu)解第36頁局部搜索算法2（LocalSearch2）1，隨機(jī)選擇一種初始也許解x0∈D，xb=x0，確定一種初始步長計(jì)算P=N(xb)2，假如不滿足結(jié)束條件，則3，Begin4， 選擇P一種子集P'，xn為P'中最優(yōu)解5， 假如f(xn)<f(xb)，則xb＝xn6， 按照某種策略變化步長，計(jì)算P=N(xb)，轉(zhuǎn)27， 不然P=P–P'，轉(zhuǎn)2。8，End9，輸出計(jì)算成果10，結(jié)束第37頁存在問題起始點(diǎn)問題AB全局最大值局部最大值第38頁處理辦法隨機(jī)生成某些初始點(diǎn)，從每個(gè)初始點(diǎn)出發(fā)進(jìn)行搜索，找到各自最優(yōu)解。再從這些最優(yōu)解中選擇一種最佳成果作為最后成果。第39頁局部搜索算法3（LocalSearch3）1，k=02，隨機(jī)選擇一種初始也許解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達(dá)成了指定次數(shù)，則從k個(gè)成果中選擇一種最佳成果輸出，不然轉(zhuǎn)（2）11，輸出成果12，結(jié)束第40頁多種辦法集成以上幾個(gè)處理辦法能夠結(jié)合在一起使用，例如第一、第二種辦法結(jié)合，就產(chǎn)生了我們將在背面介紹模擬退火辦法。第41頁皇后搜索算法（QueenSearch）1，隨機(jī)地將n個(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，輸出成果7，結(jié)束。第42頁不一樣規(guī)模下皇后問題

平均求解時(shí)間

皇后數(shù)1005001000202350001000030000平均時(shí)間（秒）55122817090010000第43頁模擬退火算法是局部搜索算法一種擴(kuò)展最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地將模擬退火算法用于求解組合優(yōu)化問題?；舅枷胧墙栌媒饘偻嘶^程改善局部搜索算法第44頁固體退火過程溶解過程：伴隨溫度不停上升，粒子逐漸脫離開其平衡位置，變得越來越自由，直達(dá)到成固體溶解溫度，粒子排列從本來有序狀態(tài)變?yōu)橥耆珶o序狀態(tài)。退火過程：伴隨溫度下降，粒子熱運(yùn)動逐漸削弱，粒子逐漸停留在不一樣狀態(tài)，其排列也從無序向有序方向發(fā)展，直至到溫度很低時(shí)，粒子重新以一定構(gòu)造排列。

第45頁粒子不一樣排列構(gòu)造，對應(yīng)著不一樣能量水平。假如退火過程是遲緩進(jìn)行，也就是說，溫度下降假如非常遲緩話，使得在每個(gè)溫度下，粒子排列都達(dá)成一種平衡態(tài)，則當(dāng)溫度趨于0（絕對溫度）時(shí)，系統(tǒng)能量將趨于最小值。第46頁假如以粒子排列或者對應(yīng)能量來體現(xiàn)固體所處狀態(tài)，在溫度T下，固體所處狀態(tài)具有一定隨機(jī)性。一方面，物理系統(tǒng)傾向于能量較低狀態(tài)，另一方面，熱運(yùn)動又妨礙了系統(tǒng)精確落入低能狀態(tài)。第47頁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)分別表達(dá)在狀態(tài)i、j下能量，T是溫度，K＞0是波爾茲曼常數(shù)。第48頁在給定溫度T下，當(dāng)進(jìn)行足夠數(shù)次狀態(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)溫度趨于無窮時(shí)：其中|S|表達(dá)系統(tǒng)所有也許狀態(tài)數(shù)。

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

第52頁當(dāng)溫度趨于0時(shí)：設(shè)Sm表達(dá)系統(tǒng)最小能量狀態(tài)集合，Em是系統(tǒng)最小能量。上式分子、分母同乘以第53頁第54頁當(dāng)溫度趨近于0時(shí)，系統(tǒng)以等概率趨近于幾個(gè)能量最小狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)概率為0。以概率1達(dá)成能量最小狀態(tài)。第55頁當(dāng)溫度上升或下降時(shí)：第56頁第57頁系統(tǒng)落入低能量狀態(tài)概率伴隨溫度下降單調(diào)上升，而系統(tǒng)落入高能量狀態(tài)概率伴隨溫度下降單調(diào)下降。第58頁在高溫下，系統(tǒng)基本處于無序狀態(tài)，基本以等概率落入各個(gè)狀態(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)逐漸減少，當(dāng)溫度趨于0時(shí)，只剩下那些具有最小能量狀態(tài)，系統(tǒng)處于其他狀態(tài)概率趨近于0。因此最后系統(tǒng)將以概率1處于具有最小能量一種狀態(tài)。第59頁達(dá)成最小能量狀態(tài)三個(gè)條件

（1）初始溫度必須足夠高；（2）在每個(gè)溫度下，狀態(tài)交換必須足夠充足；（3）溫度T下降必須足夠遲緩。第60頁組合優(yōu)化問題與退火過程類比固體退火過程組合優(yōu)化問題物理系統(tǒng)中一種狀態(tài)組合優(yōu)化問題解狀態(tài)能量解指標(biāo)函數(shù)能量最低狀態(tài)最優(yōu)解溫度控制參數(shù)第61頁1，隨機(jī)選擇一種解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ī)選擇一種解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，輸出成果。16，結(jié)束。第62頁算法中問題初始溫度選用內(nèi)循環(huán)結(jié)束條件，即每個(gè)溫度狀態(tài)交換何時(shí)結(jié)束外循環(huán)結(jié)束條件，即溫度下降到什么時(shí)候結(jié)束溫度下降辦法第63頁在模擬退火過程中，給定溫度下狀態(tài)（解）轉(zhuǎn)移能夠看作是一種馬爾可夫鏈。對于任意兩個(gè)狀態(tài)i和j，我們用Pt(i,j)表達(dá)溫度t下，從狀態(tài)i轉(zhuǎn)移到狀態(tài)j一步轉(zhuǎn)移概率，則有：其中：Gt(i,j)是產(chǎn)生概率，表達(dá)從狀態(tài)i產(chǎn)生狀態(tài)j概率。At(i,j)是接收概率，表達(dá)在狀態(tài)i產(chǎn)生狀態(tài)j后，接收狀態(tài)j概率。第64頁定理1第65頁滿足條件Gt(i,j)、At(i,j)舉例：

說明：條件2后半部分除外，該條件與詳細(xì)問題有關(guān)。第66頁定理2：在定理1條件下，假如對于任意兩個(gè)狀態(tài)

有：則有：第67頁定理3（放寬了定理1條件）

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

第68頁算法實(shí)現(xiàn)（1）初始溫度t0；（2）溫度t衰減函數(shù)，即溫度下降 辦法；（3）算法終止準(zhǔn)則，用終止溫度tf或 者終止條件給出；（4）每個(gè)溫度t下馬爾可夫鏈長度Lk。第69頁起始溫度選用（1）一種合適初始溫度，應(yīng)確保平穩(wěn)分布中每一種狀態(tài)概率基本相等，也就是接收概率P0近似等于1。在Metropolis準(zhǔn)則下，即要求：第70頁假如我們給定一種比較大接收概率P0，則：第71頁其中，能夠有下列估計(jì)方式：第72頁起始溫度選用（2）假設(shè)在t0下隨機(jī)生成一種狀態(tài)序列，分別用m1和m2表達(dá)指標(biāo)函數(shù)下降狀態(tài)數(shù)和指標(biāo)函數(shù)上升狀態(tài)數(shù)，表達(dá)狀態(tài)增加平均值。則m2個(gè)狀態(tài)中，被接收個(gè)數(shù)為：第73頁因此平均接收率為：求解有：第74頁起始溫度選用（3）模擬固體升溫過程：（1）給定一種希望初始接收概率P0，給定一種較低初始溫度t0，例如t0＝1；（2）隨機(jī)產(chǎn)生一種狀態(tài)序列，并計(jì)算該序列接收率：假如接收率大于給定初始接收概率P0，則轉(zhuǎn)（4）；（3）提升溫度，更新t0，轉(zhuǎn)（2）；（4）結(jié)束。第75頁溫度下降辦法（1）等百分比下降第76頁溫度下降辦法（2）等值下降第77頁溫度下降辦法（3）由定理1我們懂得，在一定條件下，與模擬退火算法相伴時(shí)齊馬爾可夫鏈存在平穩(wěn)分布。假如溫度每次下降幅度比較小話，則相鄰溫度下平穩(wěn)分布應(yīng)當(dāng)變化不大，也就是說，對于任意一種狀態(tài)i，相鄰溫度下平穩(wěn)分布應(yīng)滿足：第78頁一種充足條件是：第79頁兩邊取對數(shù)，并整頓得：用替代可得溫度衰減函數(shù)：第80頁每一溫度下停頓準(zhǔn)則（1）

固定長度辦法在每一種溫度下，都使用相同Lk。Lk選用與詳細(xì)問題有關(guān)，一般與鄰域大小直接關(guān)聯(lián)，一般選擇為問題規(guī)模n一種多項(xiàng)式函數(shù)。第81頁每一溫度下停頓準(zhǔn)則（2）基于接收率停頓準(zhǔn)則：要求一種接收次數(shù)R，在某一溫度下，只有被接收狀態(tài)數(shù)達(dá)成R時(shí)，在該溫度下迭代才停頓，轉(zhuǎn)入下一種溫度。要求一種狀態(tài)接收率R，R等于該溫度下接收狀態(tài)數(shù)除以總生成總狀態(tài)數(shù)。假如接收率達(dá)成了R，則停頓該溫度下迭代，轉(zhuǎn)入下一種溫度。在迭代過程中，若干相鄰狀態(tài)稱為“一代”，假如相鄰兩代解指標(biāo)函數(shù)差值不大于要求值話，則停頓該溫度下迭代。第82頁算法終止標(biāo)準(zhǔn)（1）零度法設(shè)定一種正常數(shù)e，當(dāng)初tk<e時(shí)，算法結(jié)束。第83頁算法終止標(biāo)準(zhǔn)（2）循環(huán)總控制法

給定一種指定溫度下降次數(shù)K，當(dāng)溫度迭代次數(shù)達(dá)成K次時(shí)，則算法停頓。第84頁算法終止標(biāo)準(zhǔn)（3）無變化控制法假如在相鄰n個(gè)溫度中，得到解指標(biāo)函數(shù)值無任何變化，則說明算法已經(jīng)收斂。第85頁算法終止標(biāo)準(zhǔn)（4）接收概率控制法給定一種小概率值p，假如在目前溫度下除了局部最優(yōu)狀態(tài)外，其他狀態(tài)接收概率不大于p值，則算法結(jié)束。第86頁算法終止標(biāo)準(zhǔn)（5）領(lǐng)域平均概率控制法設(shè)大小為N一種領(lǐng)域，在鄰域內(nèi)一種狀態(tài)被接收平均概率為1/N。設(shè)f0、f1為該領(lǐng)域中局部最優(yōu)值和局部次最優(yōu)值。則次最優(yōu)解是除了局部最優(yōu)解以外接收概率最大，其接收概率為：第87頁假如該概率值不大于平均值1/N時(shí)，即：