【正文】 搜索方法叫做有序搜索 或 最佳優(yōu)先搜索 (bestfirst search)，而其算法就叫做有序搜索算法 或 最佳優(yōu)先算法 。對(duì)于 i的每一個(gè)后繼節(jié)點(diǎn) j： (a) 計(jì)算 f(j)。 啟發(fā)式搜索 有序搜索 開(kāi)始 把 S放入 OPEN表 OPEN為空表？ 失敗 選取 OPEN表中 f值最小 的節(jié)點(diǎn) i，放入 CLOSED表 i=Sg？ 成功 是 是 擴(kuò)展 i得后繼節(jié)點(diǎn) j，計(jì)算 f(j)，提 供返回 i的指針，利用 f(j)對(duì) OPEN 表重新排序調(diào)整父子關(guān)系及指針 啟發(fā)式搜索 有序搜索 寬度優(yōu)先搜索、等代價(jià)搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。 1. A*算法的估價(jià)函數(shù) k(ni， nj)：表示任意兩個(gè)節(jié)點(diǎn) ni和 nj之間最小代價(jià)路徑的實(shí)際代價(jià) (對(duì)于兩節(jié)點(diǎn)間沒(méi)有通路的節(jié)點(diǎn)，函數(shù) k沒(méi)有定義 )。 h(n)：對(duì) h*(n)的估計(jì)，依賴于有關(guān)問(wèn)題的領(lǐng)域的啟發(fā)信息。 A*算法 開(kāi)始 把 S放入 OPEN表 ,記 f=h OPEN為空表？ 失敗 選取 OPEN表中未設(shè)置過(guò)的具有最小 f值 的節(jié)點(diǎn) BESTNODE，放入 CLOSED表 BESTNODE=Sg？ 成功 是 是 擴(kuò)展 BESTNODE，產(chǎn)生后繼節(jié)點(diǎn) SUVVESSOR 建立從 SUCCESSOR返回 BESTNODE的指針 計(jì)算 g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR) SUCCESSOR∈ OPEN？ 否 是 A*算法 把 SECCESSOR放入 OPEN表， 加入 BESTNODE的后裔表 g(SUCCESSOR)g(OLD)？ 否 重新確定 OLD的父輩節(jié)點(diǎn)為 BESTNODE， 并修正父輩節(jié)點(diǎn)的 g值和 f值，記下 g(OLD) SUCCESSOR∈ CLOSED？ 否 是 SECCESSOR=OLD，把它添到 BESTNODE的后繼節(jié)點(diǎn)表中 是 否 計(jì)算 f值 博弈樹(shù)搜索 博弈概述 何謂博弈？ 博弈就是下棋、打牌、競(jìng)技、戰(zhàn)爭(zhēng)等一類競(jìng)爭(zhēng)性智能活動(dòng)。 博弈樹(shù)有如下特點(diǎn)： （ 1）博弈的初始格局是初始節(jié)點(diǎn)。在圖中，方框形狀“□”表示是 MAX方控制的或節(jié)點(diǎn)；圓形框形狀“○”表示 MIN方控制與節(jié)點(diǎn)。 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博弈樹(shù)的倒推值計(jì)算 h(S0)=？ 4 8 2 0 1 4 1 博弈樹(shù)搜索 博弈樹(shù)搜索 αβ剪枝技術(shù) 基本思想：邊生成博弈樹(shù)邊估算各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無(wú)必要再擴(kuò)展的子節(jié)點(diǎn)。 （ 2）一個(gè) MIN節(jié)點(diǎn)的 β 值等于其后繼節(jié)點(diǎn)當(dāng)前最小的最終倒推值。從 1985年起，國(guó)際上開(kāi)始陸續(xù)舉行遺傳算法的國(guó)際會(huì)議，后來(lái)又更名為進(jìn)化計(jì)算。從此，遺傳算法始才得到學(xué)術(shù)界普遍關(guān)注與認(rèn)可。按一條回路中城市的次序進(jìn)行編碼。改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作，以達(dá)到更高的效率。 交叉：按概率 Pc進(jìn)行 變異：按概率 Pm進(jìn)行 終止條件： ① 完成了預(yù)先給定的進(jìn)化代數(shù) ② 種群中的最優(yōu)個(gè)體在連續(xù)若干代 沒(méi)有改進(jìn)或平均適應(yīng)度在連續(xù)若 干代基本沒(méi)有改進(jìn) 開(kāi)始 初始化種群 選擇操作 終止條件 否 適應(yīng)度最有優(yōu)個(gè)體 計(jì)算適應(yīng)度值 交叉操作 變異操作 結(jié)束 遺傳算法 遺傳算法的性能 遺傳算法求得的解是一滿意解。 要在四個(gè)種子個(gè)體中做選擇，要求仍然得到四個(gè)染色體，可依據(jù)適應(yīng)度概率比例制定如下規(guī)則： 低于 ； 在 ～ ； 在 ～ ； 在 ～ ； 在 。 特點(diǎn)：每經(jīng)一次進(jìn)化計(jì)算步驟 ,問(wèn)題解答便向著最優(yōu)方向前進(jìn)了一步 。 自然免疫系統(tǒng)：一個(gè)復(fù)雜的自適應(yīng)系統(tǒng)，通過(guò)一套復(fù)雜的機(jī)制來(lái)重組基因，以產(chǎn)生相應(yīng)入侵抗原的抗體；同時(shí)還具有學(xué)習(xí)和記憶功能，可以區(qū)分自身細(xì)胞和抗原細(xì)胞，并最終消滅抗原細(xì)胞。 識(shí)別的有限性：一個(gè)免疫細(xì)胞（抗體）不一定能夠與所有的抗原匹配。 排斥力：描述兩個(gè)抗體之間的相異程度。通過(guò)免疫算子產(chǎn)生新的抗體，并計(jì)算新抗體的親和力及其之間的排斥力。在選擇時(shí)，給那些親和力大的抗體賦予較大的選擇概率。將與抗原親和力高的抗體加入到記憶單元中，并淘汰與其排斥力最高的原有抗體。輸入問(wèn)題的目標(biāo)函數(shù)和各種約束條件，作為免疫算法的抗原。 免疫算法 免疫算法（ immunealgorithm）：在模仿生物免疫機(jī)制的基礎(chǔ)上，綜合基因進(jìn)化機(jī)理，人工地構(gòu)造的一類優(yōu)化算法，它實(shí)現(xiàn)了類似于免疫系統(tǒng)自我調(diào)節(jié)功能和生成不同抗體的功能。 遺傳算法 固體退火原理：固體內(nèi)部粒子隨著溫度升高而變?yōu)闊o(wú)序，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。對(duì)應(yīng)輪盤賭轉(zhuǎn)盤的隨機(jī)方法 ,根據(jù)表 ，繪制出的輪盤賭轉(zhuǎn)盤 ,如圖所示 : 進(jìn)化計(jì)算 ——基本 遺傳算法原理 ﹪ % % % ? 01101 ? 11000 ? 11000 ? 10011 遺傳算法 初始種群 x 值 適應(yīng)度 選擇概率 期望值 實(shí)際復(fù)制數(shù) 編號(hào) （ 隨機(jī)產(chǎn)生 ） （ 無(wú)符號(hào)整數(shù) ） f (x) = x2 Pc f(xi)/fA （ 或轉(zhuǎn)輪法 ） 1 01101 13 169 1 2 11000 24 576 2 3 01000 8 64 0 4 10011 19 361 1 ∑ 1170 平均 (A) 293 MAX 576 初始種群染色體準(zhǔn)備復(fù)制操作的各項(xiàng)計(jì)算數(shù)據(jù) （ 4） 交叉 : 交叉具體分兩步：①將新復(fù)制產(chǎn)生的 染色體 隨機(jī)兩兩匹配 ,稱其為雙親染色體 ；②再把 雙親染色體 進(jìn)行交叉繁殖。 （ 1） 確定適當(dāng)?shù)木幋a方案：將 x編碼表示為染色體的數(shù)字符號(hào)串。 簡(jiǎn)單遺傳算法采用賭輪選擇機(jī)制，令 ∑fi表示群體的適應(yīng)度值之總和， fi表示種群中第 i個(gè)染色體的適應(yīng)度值，它產(chǎn)生后代的能力正好為其適應(yīng)度值所占份額 fi /∑fi。它其實(shí)是 1， …… ， n的一個(gè)循環(huán)排列?，F(xiàn)以此作為討論主要對(duì)象，加上適應(yīng)的改進(jìn)，來(lái)分析遺傳算法的結(jié)構(gòu)和機(jī)理。從此，進(jìn)化計(jì)算逐漸成為人們用來(lái)解決高度復(fù)雜問(wèn)題的新思路和新方法。因此采用αβ剪枝技術(shù)通常都要使用某種深度優(yōu)先的搜索方法。這一過(guò)程稱為 α剪枝。此時(shí)估算出來(lái)的得分稱為的靜態(tài)估值。 如果自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，則對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。 （ 2）全信息： 在對(duì)壘過(guò)程中，任何一方都了解當(dāng)前格局及過(guò)去的歷史。把 h叫做啟發(fā)函數(shù)。 h*(n)：表示整個(gè)目標(biāo)節(jié)點(diǎn)集合｛ ti｝上所有 k(n,ti)中最小的一個(gè)，因此， h*(n)就是從 n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的代價(jià)，而且從 n到目標(biāo)節(jié)點(diǎn)能夠獲得 h*(n)的任一路徑就是一條從 n到某個(gè)目標(biāo)節(jié)點(diǎn)的最佳路徑 (對(duì)于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn) n，函數(shù) h*沒(méi)有定義 )。對(duì)于等代價(jià)搜索， f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn) i這段路徑的代價(jià)。從 j加一指向其父輩節(jié)點(diǎn) i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。 (2) 如果 OPEN是個(gè)空表，則失敗退出，無(wú)解。 啟發(fā)式搜索 有序搜索（ ordered search）：利用第一種啟發(fā)信息，總是選擇“最有希望”的節(jié)點(diǎn)作為下一個(gè)被擴(kuò)展的節(jié)點(diǎn)。