【正文】 盲目搜索 深度優(yōu)先搜索 有界深度優(yōu)先算法步驟： (1)初始結(jié)點 S放入堆棧 OPEN中； (2)若 OPEN為空，則搜索失敗，問題無解； (3)彈出 OPEN中棧頂結(jié)點 n，放入 CLOSE表中，并給出順序編號 n； (4)若 n為目標結(jié)點 D，則搜索成功，問題有解； (5)若 n的深度 d(n)=d，則轉(zhuǎn) (2) ； (6)若 n無子結(jié)點，即不可擴展，轉(zhuǎn) (2) ； (7)擴展結(jié)點 n，將其所有子結(jié)點配上返回 n的指針，并壓入 OPEN堆棧，轉(zhuǎn) (2) 。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 19/79 啟發(fā)式搜索 盲目搜索的不足：效率低，耗費空間與時間。 （ 3）用于確定某些應(yīng)該從搜索樹中拋棄或修剪得節(jié)點。這些特點被認為與向目標節(jié)點前進一步的希望程度有關(guān)。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 22/79 啟發(fā)式搜索 有序搜索 有序狀態(tài)空間搜索算法： (1) 把起始節(jié)點 S放到 OPEN表中，計算 f(S)并把其值與節(jié)點 S聯(lián)系起來。 (4) 把節(jié)點 i從 OPEN表中移出，并把它放入 CLOSED的擴展節(jié)點表中。 (b) 如果 j既不在 OPEN表中，又不在 CLOSED表中，則用估價函數(shù) f把它添入 OPEN表。 (ii) 從 j指向 i，而不是指向它的父輩節(jié)點。對于寬度優(yōu)先搜索，選擇 f(i)作為節(jié)點 i的深度。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 27/79 啟發(fā)式搜索 有序搜索 例 ：八數(shù)碼難題 , 采用了簡單的估價函數(shù) f(n)=d(n)+W(n) 其中： d(n)是搜索樹中節(jié)點 n的深度； W(n)用來計算對應(yīng)于節(jié)點 n的數(shù)據(jù)庫中錯放的棋子個數(shù)。 k(n,ti)：從節(jié)點 n到某個具體的目標節(jié)點 ti，某一條最小代價路徑的代價。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 31/79 啟發(fā)式搜索 A*算法 希望估價函數(shù) f是 f*的一個估計，此估計可由下式給出： f(n)=g(n)+h(n) 其中： g是 g*的估計； h是 h*的估計。這種信息可能與八數(shù)碼難題中的函數(shù) W(n)所用的那種信息相似。 定義 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的 A算法，稱為 A*算法。 “二人零和非偶然性全信息”博弈 （ 1）二人零和： 對壘的 MAX、 MIN雙方輪流采取行動，博弈的結(jié)果只有三種情況： MAX方勝， MIN方勝，和局。因此，當一方面臨多個行動方案選擇時， 博弈的各方總是要挑選對自己最為有利而對對方最不利的那個行動方案。 （ 2）在博弈樹中，由于 雙方輪流地擴展節(jié)點，“或”節(jié)點和“與”節(jié)點逐層交替出現(xiàn)。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 38/79 博弈樹搜索 極小極大分析法 在二人博弈過程中，最直觀而可靠的常用分析方法就是極小極大化搜索法。 （ 2）考慮每一方案實施后對方可能采取的所有行動，并為其計算可能的得分； （ 3）為計算得分，需要根據(jù)問題的特性信息定義一個估價函數(shù)，用來估算當前博弈樹所有端節(jié)點的得分。 （ 5）如果一個行動方案能獲得較大的倒推值，則它就是當前最好的行動方案。 具體剪枝方法： （ 1） 對于一個“與”節(jié)點 MIN，若能估計出其倒推值上界 β，并且這個 β值不大于 MIN的父輩節(jié)點（一定是“或”節(jié)點）的估計倒推值的下界 α，即 α≥ β，則就不必要再擴展該 MIN節(jié)點的其余子節(jié)點了。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 42/79 博弈樹搜索 αβ剪枝技術(shù) 從算法中看到： （ 1） MAX節(jié)點（包括起始節(jié)點）的 α值永不減少。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 43/79 博弈樹搜索 αβ剪枝技術(shù) 例 一字棋搜索樹 α和 β值計算 估價函數(shù) g(p)定義如下： （ 1）若當前棋局對任何一方都不是獲勝的，則 g(p)=(所有空格都放上 MAX的棋子之后 3個棋子所組成的行列及對角線的總數(shù)） — （所有空格都放上 MIN的棋子之后 3個棋子所組成的行列及對角線的總數(shù)） （ 2）若 p是 MAX獲勝，則 g(p)=+∞ （ 3）若 p是 MIN獲勝，則 g(p)=∞ 上圖中， g(p)=64=2，其中 表示 MAX方， ○表示 MIN方 ○ 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 44/79 αβ剪枝技術(shù) 博弈樹搜索 ○ ○ ○ ○ ○ ○ 初始節(jié)點 α=1 A B C 1 β=1 65=1 55=0 65=1 55=0 45=1 56=1 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 45/79 αβ剪枝技術(shù) 博弈樹搜索 4 1 1 8 1 2 5 0 4 9 1 5 11 4 3 1 –1 5 8 10 1 4 2 5 5 9 6 0 6 4 10 –9 1 12 5 MAXMIN博弈樹的倒推值計算 h(S0)=？ 4 8 2 0 1 4 1 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 46/79 αβ剪枝技術(shù) 博弈樹搜索 h(S0)=？ 4 4 11 3 3 –1 –1 8 8 10 8 2 2 5 5 2 2 4 4 x?5 5 4 α α β α α α α 博弈樹的 α β 剪枝實現(xiàn)過程 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 47/79 博弈樹搜索 αβ剪枝技術(shù) 要進行 αβ剪枝，必須至少使某一部分的搜索樹生長到最大深度，因為 α和 β值必須以端節(jié)點的靜態(tài)估值為依據(jù)。 遺傳算法是模仿生物遺傳學和自然選擇機理，通過人工方式構(gòu)造的一類優(yōu)化搜索算法，是對生物進化過程進行的一種數(shù)學仿真，是進化計算的一種最重要形式。參加進化計算國際會議的人數(shù)及收錄文章的數(shù)量、廣度和深度逐年擴大。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 51/79 遺傳算法 遺傳算法應(yīng)用： 1975年提出遺傳算法 ,當時并沒有引起學術(shù)界足夠的重視。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 52/79 遺傳算法 遺傳算法的基本原理 霍蘭德提出的遺傳算法通常稱為簡單遺傳算法（ SGA）。將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫解碼或譯碼。從城市w1開始，依次經(jīng)過城市 w2 ， …… ， wn，最后回到城市 w1，我們就有如下編碼表示： w1 w2 …… wn 由于是回路，記 wn+1=w1。TSP的目標是路徑總長度為最短，自然地，路徑總長度的倒數(shù)就可作為 TSP問題的適應(yīng)度函數(shù) : 其中 wn+1=w1 適應(yīng)度函數(shù)要有效反映每一個染色體與問題的最優(yōu)解染色體之間的差距。 選擇操作也叫復(fù)制（ reproduction）操作，根據(jù)個體的適應(yīng)度函數(shù)值所度量的優(yōu)劣程度決定它在下一代是被淘汰還是被遺傳。二進制編碼表示的簡單變異操作是將 0與 1互換： 0變異為 1， 1變異為 0。影響解質(zhì)量的因素： 種群的數(shù)量：太小缺少多樣性，太多影響效率 適應(yīng)度函數(shù)：提升優(yōu)良個體的適應(yīng)度 交叉和變異：不同的問題需構(gòu)造性能更優(yōu)的交叉和變異操作 交叉概率和變異概率： 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 62/79 分析：對該問題雖然也可以采用枚舉的方法來解決 ,但枚舉法卻是一種效率很低的方法 .可運用遺傳算法來求解該問題 . 解：首先對問題進行初始化，以獲得初始種群 。 遺傳算法 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 63/79 （ 2）選擇初始種群 :通過隨機的方法來產(chǎn)生染色體的數(shù)字串，并組成初始種群。 遺傳算法 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 67/79 對應(yīng)于上例，按照適應(yīng)度的計算，經(jīng)復(fù)制操作后，得到新的染色體種群為 01101 11000 11000 10011 遺傳算法 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 68/79 某個染色體是否被復(fù)制 ,可以通過概率決策法、適應(yīng)度比例法或“輪盤賭”的隨機方法來斷定。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 72/79 遺傳算法 編號 復(fù)制操作后的區(qū)配池 匹配號 (隨機選取 ) 交叉空隙位 ( 隨機選取 ) 交叉后新種群 新種群x值 適應(yīng)度 f(x) = x2 1 01101 2 2 01000 8 64 2 11000 1 2 11101 29 841 3 11000 4 4 11001 25 625 4 10011 3 4 10000 16 256 總計 （ ∑ ） 1786 平均 (A) 最大值 (MAX) 841 復(fù)制、交叉操作的各項數(shù)據(jù) 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 73/79 （ 5）變異 : 設(shè)變異概率取為 ,則對于種群總共有 20個基因位 . 期望的變異串位數(shù)計算 :20 =(位 ), 故一般來說 ,該例中無基因位數(shù)值的改變 .從表 112和 113可以看出 ,每經(jīng)過一次復(fù)制、交叉和變異操作后 ,目標函數(shù)的最優(yōu)值和平均值就會有所提高。若該過程一直進行下去 ,就將最終走向全局的最優(yōu)解 .可見進化計算的每一步操作簡單 ,并且系統(tǒng)的求解過程是依照計算方法與規(guī)律來決定 ,與本源問題自身的特性很少相關(guān)。退火過程由冷卻進度表控制，包括控制參數(shù)的初值 t及其衰減因子 △ t、每個 t值時的迭代次數(shù) L和停止條件 S。 人工免疫系統(tǒng)的研究： 20世紀 90年代，解決網(wǎng)絡(luò)適應(yīng)性問題、傳感器網(wǎng)絡(luò)故障診斷、病毒檢測、機器學習。 抗體（ antibody）：在免疫算法中抗體是指根據(jù)疫苗修正某個個體基因所得到的新個體（新基因）；在免疫學中，抗體是一種具有免疫功能的球蛋白，是人體抵抗力最重要的組成部分。 識別的多樣性：一個免疫細胞可以識別多種不同的抗原。 算法步驟： （ 1）識別抗原。 （ 3）計算親和力和排斥力。 （ 5）更新記憶能力。否則轉(zhuǎn)（ 7）。 （ 8）轉(zhuǎn)（ 3） 免疫算法 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 80/79 演講完畢，謝謝觀看！