【正文】 ?把所有城市都游過后，返回， 并留下外激素，其量與路程長度成反比 ?所有螞蟻都返回后，圖上留下外激素的標志 進行第二輪的漫游（傾向選激素多的路徑） … 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十六、螞蟻算法 算法應(yīng)用 (3)螞蟻清除垃圾 螞蟻能將巢里的垃圾或死螞蟻 ,打掃成幾大堆給以清除 ?一群螞蟻隨機出發(fā) ,遇到垃圾 ,就將其拉走（方向也是隨機的） ?拉垃圾時 ,若碰到某一堆垃圾時 ,就放下 ?放下垃圾后 , 再隨時機進行打掃工作 …… 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十七、粒子群算法 基本原理 模擬鳥集群飛行覓食的行為，鳥之間通過集體的協(xié)作使群體達到最優(yōu)目的。另外 ,也可以不用整個種群而只是用其中一部分的鄰居。 對無后代的節(jié)點和搜索層次達到極限的節(jié)點，仍用靜態(tài)估計函數(shù)來計算它們的估計值，對于其它節(jié)點，均令父結(jié)點的估計值為各子節(jié)點的估計值的負數(shù)的極大值，即 PS[i,4]=max(PS[i+1,4]) (i+1遍及 i的所有子節(jié)點） 第三章 搜索技術(shù) 第三節(jié) 博弈樹搜索 五、帶剪枝的博弈樹搜索算法的改進 B*算法 (1)盡早查出不合用的壞分枝，并把它剪掉 (改進 ??剪枝 ) (2)合理地確定搜索的深度限制 (3)每個節(jié)點設(shè)立兩個估計值：樂觀估計和悲觀估計，且兩個估計值可動態(tài)可變。這個解叫做個體極值 pBest. 另一個極值是整個種群目前找到的最優(yōu)解。 (2)后面的螞蟻，就會沿著有外激素的路徑行走（外激素越多引誘螞蟻的能力就越強）。 ? 對已經(jīng)搜索過的局部最優(yōu)解進行標記（禁忌） ? 在迭代搜索中盡量避免重復(fù)相同的搜索（但不是完全隔絕） 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十五、禁忌搜索算法 (Tabu Search) 算法步驟 (1)給定算法參數(shù)，隨機產(chǎn)生初始解 x，置禁忌表為空。初溫的確定應(yīng)折衷考慮優(yōu)化質(zhì)量和優(yōu)化效率。 (4)首先生成一個隨機解 ,然后對其進行擾動 (在同一溫度下進行多次擾動 ),對擾動后得到的解進行評估與替換 ,溫度逐漸下將形成多代。 cp第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑵ 基本遺傳算法的實現(xiàn) ④ 基本位變異算子 ? 基本位變異算子的具體執(zhí)行過程為：對個體的每一個基因座，依變異概率 指定其為變異點；對每一個指定的變異點，對其基因值做取反運算或用其他等位基因值來代替，從而產(chǎn)生出一個新的個體。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本遺傳算法 ⑵ 基本遺傳算法的實現(xiàn) ① 個體適應(yīng)度評價 ? 在遺傳算法中，以個體適應(yīng)度的大小來確定該個體被遺傳到下一代群體中的概率。初始群體中各個個體的基因值可用均勻分布的隨機數(shù)來生成。 *X第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 十二、遺傳算法 基本思想 生物的進化過程主要是通過染色體之間的交叉和染色體的變異來完成的。染色體 X也稱為個體 X，對于每一個個體 X，要按照一定的規(guī)則確定出其適應(yīng)度。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 八、 A*算法 注： 7)在 f(x)=g(x)+h(x)中， g(x)是“經(jīng)驗”項，起著穩(wěn)定形勢的作用，而 h(x)是“冒險”項。 注： 1)可以證明：只要目標狀態(tài)存在，并且從初始狀態(tài)到目標狀態(tài)有一條通路，則 H*算法一定在有限步內(nèi)終止，并找到一個最優(yōu)解 (即代價為最低的解）。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 二、有序搜索算法 算法 1)建立一個空的 狀態(tài) 序列 SS 2)建立一個空的 狀態(tài) 庫 SB 3)定義一個估值函數(shù) f 4)若初始狀態(tài)為 S0,則定義初始 狀態(tài) S0(0,f(0))為當前新 狀態(tài) 5)將當前新 狀態(tài) 按估計值從小到大的順序插入到 SS中，若新狀態(tài)為目標狀態(tài)，則將相應(yīng) 狀態(tài) 插入到具有相同估計值的 狀態(tài) 的最前面；否則將相應(yīng) 狀態(tài) 插入到具有相同估計值的 狀態(tài) 的最后面 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 二、有序搜索算法 算法 6)若在 SS或 SB中原有一個 狀態(tài) 與當前新 狀態(tài) 共一個狀態(tài)，則刪去原有 狀態(tài) 7)若新 狀態(tài) 在 SS的最前面，則轉(zhuǎn) 11) 8)若某種狀態(tài)極限已達到，則搜索失敗，算法運行結(jié)束，無解 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 二、有序搜索算法 算法 9)若任何規(guī)則均不能應(yīng)用于 狀態(tài) 序列 SS中的第一個狀態(tài)，或者雖能應(yīng)用，但不能產(chǎn)生合適的新狀態(tài) (在 SS或 SB中均沒有者，稱為新 )，或雖能產(chǎn)生合適的新 狀態(tài) S(path2,f(path2)),但不是改進型的(若 SS和 SB中已有 狀態(tài) S(path1,f(path1)),它與新 狀態(tài) 共一個狀態(tài) S，且 f(path2)?f(path1),則稱新狀態(tài)不是改進型的 )，則將此第一個狀態(tài)從 SS中除去，送入 SB中，否則轉(zhuǎn) 12) 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 二、有序搜索算法 算法 10)若 SS成為空序列，則搜索失敗，算法運行結(jié)束，無解 11)若 SS中第一個狀態(tài)已是目標狀態(tài)，則搜索成功，算法運行結(jié)束 (若該 狀態(tài) 形如 S(path,f(path))，則解就是 (path))；否則轉(zhuǎn) 9) 12)取一個可應(yīng)用于 SS的第一個 狀態(tài)S(path,f(path))，并產(chǎn)生改進型的合適新 狀態(tài) 的規(guī)則 Rn，產(chǎn)生新 狀態(tài) T(path,n,f(path))，定義它為當前新 狀態(tài) ，轉(zhuǎn) 5) 算法完 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 二、有序搜索算法 算法 注： 1)狀態(tài) 是帶路徑和估計值的狀態(tài)，而狀態(tài)只是一個狀態(tài) 2)對當前生成的新狀態(tài)是否是目標狀態(tài)的判斷需要兩次 3)這里每次只生成一個后代 4)給定估計值函數(shù) f的意義，則有序搜索就可歸結(jié)為已知的搜索，如令 f為狀態(tài)節(jié)點的深度，則有序搜索就成為廣度優(yōu)先搜索 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 二、有序搜索算法 算法 注： 5)有序搜索算法不一定找到解，即使有解 6)有序搜索算法的特點是使用啟發(fā)式信息(表現(xiàn)在估計值函數(shù) f上 )，可是啟發(fā)式信息也會騙人，會引人誤入歧途 7)有序搜索即使能找到解，也未必一定是最優(yōu)的 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 二、有序搜索算法 算法改進 1)用多個估計值函數(shù)來“層層設(shè)卡” 2)對估計值函數(shù)的形式加以限制，以保證它一定能找到解，甚至一定能找到最優(yōu)解。 注：關(guān)于“啟發(fā)式”，可有兩種看法： 1)任何有助于找到問題的解，但不能保證找到解的方法均是啟發(fā)式方法； 2)有助于加速求解過程和找到較優(yōu)解的方法是啟發(fā)式方法。 對于一般搜索，搜索空間基本是靜態(tài)的，或表或數(shù)組或數(shù)據(jù)庫。 第三章 搜索技術(shù) 第一節(jié) 引言 二、研究和選用搜索算法的原則 搜索空間是靜態(tài)的還是動態(tài)生成的？ 在人工智能中，搜索的對象 (常稱狀態(tài) )是在搜索過程中逐步生成的，需將搜索對象的生成和評估的代價計算在內(nèi)。 單向搜索還是雙向搜索？ 第三章 搜索技術(shù) 第一節(jié) 引言 二、研究和選用搜索算法的原則 盲目搜索還是啟發(fā)式搜索？ 按照預(yù)定的控制策略實行搜索，在搜索過程中獲取的中間信息不用來改進控制策略，稱為盲目搜索，反之，稱為啟發(fā)式搜索。 c)計算狀態(tài)估計值的函數(shù)是確定的，但每個狀態(tài)的估計值的大小與初始狀態(tài)到該路徑有關(guān)。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 五、 H*算法 1. 在 H算法中規(guī)定 h(n)?h*(n) 2. 推廣 k*(ni,nj)的定義：令 k*(n1,n2,…,n m)為從 n1出發(fā)，經(jīng)過 n2,…, 到達 nm的最小代價，規(guī)定存在一個正整數(shù) e0，使得對任意的 ni,nj,nm(nj?nm)均有 k*(ni,nj,nm)k*(ni,nj)e H算法就是 H*算法。 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 八、 A*算法 在 A算法規(guī)定： h(n)?h*(n), k*(ni,nj,nm)k*(ni,nj)e,則 A算法成為 A*算法 注： 1)A*算法與 H*算法的主要區(qū)別有 a)在 H*算法中每次只生成一個后繼節(jié)點，而在A*算法中每次生成一個節(jié)點的所有節(jié)點 b)在 H*算法中，每生成一個新節(jié)點，就詢問它是否是目標節(jié)點，而在 A*算法中，只詢問棧頂節(jié)點是否是目標節(jié)點 2)在 A*算法中，估計值函數(shù) f(n)=g(n)+h(n)的選擇是一個關(guān)鍵 第三章 搜索技術(shù) 第二節(jié) 啟發(fā)式搜索 八、 A*算法 注： 3)A*算法一定能保證找到最優(yōu)解 4)若按展開的節(jié)點個數(shù)來估計它的效率，則當啟發(fā)式函數(shù) h的值單調(diào)上升時，它的效率只會