001 ~ 4章 用搜尋法對問題求解 & 進階搜尋

Post date: 2012/8/2 上午 08:24:27

http://www.youtube.com/watch?v=BnIJ7Ba5Sr4&feature=autoshare

人工智慧現代方法 第一章節 主要講授的是人工智慧歷史還有應用以及近代各個比賽與組織

我認為當心靈趨近於成熟,身體也發展健全之後,學會基礎工具的應用,再來就是需要各種理論的支持,才能有更進階的發展。

人工智慧現代方法 第二章節

章節內容主要在介紹以各種目的產生的代理人程式

智慧型代理人

環境的多樣性

非全知且理性

學習和自主性

靜態、動態、離散、連續

基於模型、反射、學習

以及學習方法、獎勵、預期效用

執行汽、感測器、問題產生器

● 代理人是可以感知環境並在環境中行動。代理人函數指定代理人回應任何知覺序列時所採取的行動。

● 效能指標評價代理人在環境中的行為表現。對於目前為止她能看到的知覺序列,理性代理人的行動是為了使他的效能指標的期望值最大化

● 任務環境的規格包括效能指標、外部環境、執行器、感測器。設計代理人時,第一步一定是訂定任務環境的規格,而且要盡可能的全面。

● 任務環境沿著幾個顯著的維度做變化。他們可能是完全或部分可觀察的,確定性的或隨機的,片段式的或延續式的,靜態的或動態的,離散的或連續的,單代理人或多代理人的。

● 代理人程式時做了代理人函數。有各種基本的代理人程式設計,反映出明確表示並用於決策過程的資訊種類。這些設計在效率、簡潔性和彈性等方面各有不同。適當的代理人程式設計取決於環境的本質。

● 簡單反射型代理人直接對知覺做出反應,而基於模型的反射型代理人保有內部狀態,追蹤紀錄世界中不能從當前的知覺得知的各個層面。基於目標的代理人行動是為了達到目標,而基於效用的代理人試圖最大化她們自己期望的「快樂」。

● 所有代理人都可以透過學習來改進他們的效能。

人工智慧現代方法第三章

用搜尋法對問題求解

本章中,我們來看看當代理人沒有單獨的行動可以解決問題的時候,她如何找到一個行動序列以完成它的目標。

本章介紹了在確定性的、可觀察的、靜態的和完全已知的環境下,代理人可以用來選擇行動的方法。在這種情況下,代理人可以建構達到目標的行動序列;這個過程稱為搜尋。

人工智慧-現代方法

第三章

在瑪奇上的應用

1.計算路徑成本

2.計算商品成本

3.分析商品更新的價格

4.獎勵 最小時間 + 1分

5.獎勵 最小成本 + 1分

6.獎勵 最大金幣 + 1分

7.分析商品更新前後的價格,判斷獎勵最高的路線及產品

8.決策在幾分鐘內在你所在的位置,行動到貿易開始最佳路線及產品

上面我們用初始狀態、後繼函數、目標測試和路徑成本來對貿易最佳路線及產品這個問題做正規化。但其仍為一個模型--一個抽象的數學描述而不是實體物。把我們選擇的簡單狀態敘述和第一次實際的貿易行動比較一下,實際的世界狀態包括許多事情:旅行同伴、撥放的音樂、途中的野外生物、可愛的腳色。所有這些需要考慮的事項都被拋在我們的狀態敘述之外,因為他們與找到貿易最佳路線及產品成本最小化這個問題無關。將這些細節從表示法去除的過程稱為抽象化

除了抽象化狀態敘述之外,我們還需要抽象化行動本身。一個貿易行動會有很多後果。除了路上遇敵、上廁所、滑鼠點累了、點自動巡路。我們的正規化只考慮位置的變化,透過網路搜尋到商品的資訊,商品的價值。同時,我們也一併忽略了許多其他行動:朋友的招呼,看到漂亮的場景,電腦爆炸等等。當然,我們更不會將行動詳細指定到「按下滑鼠左鍵移動到某座標點」這種層次上。

這裡的抽象化包括了什麼?行動都被抽象化為他們的開始和結束狀態,忽略了當貿易時所處的中間位置。我們同時也去除掉一些行動,諸如使用朋友膠囊瞬間移動到貿易地點,或者把電腦砸了永遠不開瑪奇。我們只保留和遊戲規則相關的敘述,而避開所有實際操作的細節。

無資訊搜尋策略

{

廣度優先搜尋 使用FIFO佇列

先展開根結點,接著展開跟節點的所有後繼,然後再展開他們的後繼,依此類推。

簡單二元樹上的廣度優先搜尋。在每個階段,箭頭會指出下一個要展開的節點

搜尋的節點指的是搜尋關鍵字或符合搜尋條件的數值

廣度優先搜尋的時間和記憶體需求。搜尋樹的分支因數為

b+b^2+b^3+...b^d = O(b^d)

b = 10;

1個節點/秒;

1000位元組/節點

由上述公式可學習到兩件事。

第一是,在廣度優先搜尋演算法中記憶體的需求是比執行時間更大的問題。有人可能會等待13天,等一個搜尋深度12的重要問題的解答出來,但沒有個人電腦擁有所需的P位元組級的記憶體。幸運的是,其他策略需要較少的記憶體。

第二個是,時間仍然是個主要因素。如果你的問題在第 16 層有一個解,那麼(按照我們所給的假設)廣度優先搜尋(或者甚至任何一種無接收資訊搜尋)需要花費 350 年的時間才能找到他。

一般而言,除了極小型的實例以外,指數級複雜度的搜尋問題不能用無資訊的方法解決。

當所有步成本相等時,廣度優先搜尋是最佳的,因為她總是先展開深度最淺的未展開節點。

成本一致搜尋

展開的是路徑成本g(n)最低的節點n,而非深度最淺的節點。

作法是將邊緣儲存為一個由g排序的優先佇列。

結合一個優先佇列和一個雜湊表

部分的瑪奇狀態空間,選擇用以說明成本一致搜尋

深度優先搜尋 使用LIFO佇列

總是展開搜尋樹目前的邊緣中最深的節點。

在無窮狀態空間中,若碰到一個無窮的非目標路徑時,兩個版本都會失敗。

深度優先搜尋數僅需儲存一個從根到葉節點的路徑,連同該路徑上各節點的其餘未展開的兄弟節點。

一旦展開一個節點,當他的所有後代都被完全探索過後,這個節點就可以從記憶體中刪除,

我們發現對深度 d = 16 的深度優先搜尋只需要156KB,而不是10EB,前者只需後者約百億分之一的空間。

回朔搜尋

深度優先搜尋的另外一種變形,所用的記憶體空間更少。

再回朔搜尋中,每次只產生一個後繼節點,而非所有的後繼節點;每個被部分展開的節點要記住下一個要產生的節點是哪個。

有限深度搜尋

深度優先搜尋在無窮狀態空間令人尷尬的失敗,可以用具有先覺深度限制L的深度優先搜尋來改善。

就是說,把深度為L的節點當作沒有後季節點來看待。

缺點 如果我們選擇的L<d,即最淺的深度目標節點的深度超過了深度限制,那麼他又引入了不完備性(這在d未知的情況下不是不可能發生的)。

如果選擇的L>d的話,有限深度搜尋也不會是最佳的。

有時候,深度限制可建立在對問題的認識上。例如,在瑪奇的地圖上有8個城市。因此,我們知道如果有解的話,其路徑長度最多為7,所以L = 7 是一個可能的選擇。

疊代深入的深度優先搜尋

是一個用來搜尋最佳深度限制的一般策略,他經常和深度優先搜尋結合使用。

他的做法是,逐步增加限制先是0,然後1,然後2,依此類推直到找到一個目標。

當深度限制達到d(最淺目標節點的深度)時,就能找到目標節點。

他反覆用逐漸增加的深度限制來進行有限深度搜尋。

他在兩種情況下會中止:找到解,或是有限深度搜尋傳回failure,即無解

疊代延長搜尋

與成本一致搜尋相比,壘代延長搜尋反而帶來大量負擔

雙向搜尋

雙向搜尋的概念是同時執行兩個搜尋 其中一個從初始狀態前向搜尋,而另一個從目標狀態後向搜尋,當他們在中間相遇時搜尋中止。

成功條件為:出自起始節點的一個分支與自目標節點的另一個分支相遇

如果有幾個明確列出的目標狀態例如,吸塵器問題 圖3.3中的兩個乾淨的目標狀態 那麼我們可以建構出一個虛擬的目標狀態,他的直接祖先節點是所有實際目標狀態。

但如果目標是一個抽象描述,如「沒有女王攻擊另一個女王」這個在n皇后問題中的目標,雙向搜尋將很難使用。

}

無資訊搜尋策略的比較

廣度優先 成本一致 深度優先 有限深度 壘代深入 雙向搜尋(如果可用)

是否完整? 是a 是a,b 否 否 是a 是a,d

時間 O(b^d) O(b^1+[C*/e]) O(b^m) O(b^l) O(b^d) O(b^d/2)

空間 O(b^d) O(b^1+[C*/e]) O(b^m) O(b^l) O(b^d) O(b^d/2)

是否最佳? 是c 是 否 否 是c 是c,d

b是分支因數;d是最淺的解的深度;m是搜尋樹的最大深度;l是深度限制。

上標的涵義如下:a如果b是有限的,則是完備的;b如果對於正值常數e,所有單步成本>=e,

則是完備的;c如果單步成本都是相同的,則是最佳的;d如果兩個方向的搜尋都使用廣度優先搜尋

有資訊(啟發式)搜尋策略

{

貪婪最佳-優先搜尋

試圖擴展離目標節點最近的節點,建立在這樣可能很快找到解的基礎上。f(n) = h(n)

在每一步他都試圖找到離目標盡可能最近的節點。

使用直線距離啟發式hSLD的貪婪最佳優先搜尋,尋找前往班克爾的最短路徑的幾個階段。節點都標明了該節點的h值

A*搜尋 : 最小化總的估計解成本

最佳優先搜尋的最廣為人知的形式稱為A*搜尋(發音為「A-Star 搜尋」。

他把到達節點的成本g(n)和從該節點到目標節點的成本h(n)結合起來對節點進行評價:

f(n) = g(n) + h(n)

因為g(n)給出了從起始節點到節點n的路徑成本,而h(n)是從節點n到目標節點的最便宜成本的估計成本,因此

f(n) = 經過節點n的最便宜解的估計成本

倘若啟發函數 h(n)滿足一定的條件,A*搜尋既是完備的也是最佳的。

該演算法等同於 Uniform-cost Search(UCS 統一成本搜尋),除了A*用 g + h 取代 g。

最佳化的條件:可採納性和一致性 h(n)為可採納啟發式。

可採納啟發是永遠不會超估到達目標的成本。因為g(n)危言當前路徑到達n的實際成本,且f(n) = g(n) + h(n),

所以我們有個直接結果就是,f(n)部會超估沿當前路徑經過n的解答其實際成本。

第二個稍強的條件稱作一致性(有時稱單調性),只有在應用 A*至圖形搜尋時才需要。

我們稱啟發式h(n)式一致的,如果對於每個節點n和透過任何行動a產生的n的每個後繼者節點n',

從節點n到達目標的估計成本不大於從n到n'的單部成本與從n'到達目標的估計成本之和:

h(n) <= c(n,a,n') + h(n')

本彰中我們討論的可採納啟發式都是一致的。例如,考慮hSLD。我們知道當每邊都用直線距離來度量時是滿足一般的三角形不等式的,

而且n和n'之間的直線距離不超過c(n,a,n')。因此,hSLD是一個一致的啟發式。

A*的最佳化

A*具有以下性質:若h(n)為可採納,A*的樹-搜尋版本為最佳,而當h(n)為一致時,圖形搜尋版本為最佳。

如果C*是最佳解路徑成本那麼我們可以得到:

● A*演算法擴展所有 f(n) < C* 的節點。

● A*演算法在擴展目標節點前可能會擴展一些正好處於「目標等高線」【f(n) = C*】上的節點。

完備性要求只存在有限個成本小於等於C*的節點,如果所有的單步成本都大於一個有限的數E並且b是有限的,那麼這個條件是成立的。

注意A*演算法步擴展f(n) > C*的節點

在上圖中度巴頓往班克爾會經歷一個地圖,儘管是根節點的子節點,也沒有被擴展。我們說在此圖下的子樹被剪枝了;因為hSLD是可採納的,搜尋演算法可以安全地忽略這顆子樹,仍然能保證最佳性。

剪枝這個概念───不需要檢驗就直接把他們的可能性從考慮中排除───這在AI的很多領域中都是很重要的。

記憶體受限制的啟發函數搜尋

A*演算法記憶體需求的最簡單辦法就是將疊代深入的想法用在啟發函數搜尋內容上,形成疊代深入 A*(IDA*)演算法。

遞迴最佳優先搜尋(RBFS) 是一個模仿標準的最佳優先搜尋的遞迴演算法,但是她只使用線性的儲存空間。

當遞迴回溯時,對回溯前的當前路徑上的每個節點,RBFS用其子節點的最佳 f 值,───備份值(backed-up value)───替換其f值。

這樣,RBFS能記住被他遺忘的子樹中的最佳業節點的f值,並因此能夠在以後某個時刻決定是否值得重新擴展該子樹。

RBFS比IDA*演算法效率更高,但是他還是需要重複產生大量節點。

像A*演算法一樣,如果啟發函數 h(n)是可採納的,那麼RBFS演算法是最佳的。

IDA* 和 RBFS的問題在於利用的記憶體過於小了。在兩次疊代之間,IDA*只保留一個數字:當前的f-成本值限制。

RBFS在記憶體中保留的資訊多一些,但他只使用線性空間:即便有更多可用的記憶體,RBFS 也沒辦法利用。

因此,充分利用可用記憶體的看來是更明智的。

有兩個這樣做的演算法,MA*演算法(記憶體受限制 A*演算法) 和 SMA*演算法(簡化MA*演算法)。

SMA*演算法像 A* 演算法一樣,擴展最佳業節點直到記憶體內存放滿為止。SAM總是丟棄最差的一個葉節點───即 f 值最高的一個。

如果節點n的所有子孫節點都被遺忘了,我們將不知道從n該走哪條路,但是我們將仍知道從n去別處是否值得。

如果有可達到的解───也就是說,如果最淺的目標節點的深度d小於記憶體大小(由節點數來表示),那麼SMA*演算法是完備的。

如果任何最佳解釋可達到的,那麼這個演算法也是最佳的;

SMA*是尋找最佳解答的一個相當強力的選擇,特別是在狀態空間為一圖形,步成本不一致,且節點生成相較於維護邊緣和探索集的經常費用是較貴時。

然而在一些非常困難的問題中,SMA*演算法將會在候選解路徑集裡的路徑之間換來換去只有一個很小的子集可以放到記憶體中(這很像硬碟分業排程系統遇到的記憶體反覆調入條出問題)。

那麼重複產生相同節點需要的額外時間意味著一個具備無限的記憶體的條件下能被A*演算法實際解決的問題,對於SMA*演算法會成為不可操作的。

為了更好的搜尋而學習(終於到了我最感興趣的章節了,可惜只是簡單介紹要到21章才是更進階的)

前面提出了幾個固定的搜尋策略───廣度優先,貪婪最佳優先,等等───

為了讓代理人能夠學習如何更好的搜尋,其方法依賴於一個稱為後設狀態層狀態空間的重要概念。

後設狀態層狀態空間(metalevel state space)

每個狀態都要捕捉一個程式的內部(可計算的)狀態,程式搜尋的範圍則是諸如羅馬尼亞問題中的目標層狀態空間(object-level state space)。

例如,A*演算法的內部狀態由當前的搜尋樹組成。

後設狀態層狀態空間中的每個行動是一個改變內部狀態的計算步驟;

例如,A*演算法中每個可計算的步驟都擴展一個葉節點並把他的後繼者節點加入搜樹。

後設狀態層學習(metalevel learning)演算法可以從這些經驗中學到怎樣避免探索沒有希望的子樹。

學習的目標是使問題求解的總成本(total cost)最小化,在計算開銷和路徑成本之間取得折衷。

啟發函數

在本節中,將看看八方塊(魔術方塊)遊戲的啟發函數,以使啟發函數的一般化性質清楚明白地顯現出來。

(用講解的很難說明啟發函數是什麼東西,這裡舉個例子)

八方塊遊戲是最早的啟發函數搜尋問題之一。

這個遊戲的目標是把棋子水平或垂直的滑動到空格中,直到棋盤組態和目標組態一致

程式方面我們可以用陣列來表示 初始陣列A[9] 目標陣列B[9]

A[0] = 7 A[1] = 2 A[2] = 4

A[3] = 5 A[4] = 0 A[5] = 6

A[6] = 8 A[7] = 3 A[8] = 1

B[0] = 0 B[1] = 1 B[2] = 2

B[3] = 3 B[4] = 4 B[5] = 5

B[6] = 6 B[7] = 7 B[8] = 8

我們要讓 A 陣列跟 B 陣列的數字相等

此時我們可以透過演算法來計算各種結果,目的是讓A跟B陣列相等,並且希望滑動的步驟最小化

因此挑選一個適合此問題的演算法

那個演算法就是所謂的啟發函數

我們需要一個絕不會高估到達目標步數的啟發函數

以書中的啟發函示來做比較

h1 = 不在位的棋子數,所有的八個棋子都不在正確的位置,因此起始狀態的h1 = 8

h1 是一個可採納的啟發函數,因為要把不在位子的棋子都移動到正確的位置上,每個錯位的棋子至少要移動一次。

h2 = 所有棋子到其目標位置的距離和,因為棋子不能斜著移動,我們計算的距離是水平和垂直的距離和。

這個說法有時被稱為城市距離或曼哈頓距離(數學說法)。h2也是可採納的,因為任何移動能做的最多是把棋子項目標移進一步。在開始狀態的棋子 1 到 8 給出曼哈頓距離為

h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18

如我們所預期,這兩個啟發函數都不會超過實際的解成本 26 。

啟發函數的精確度對性能的影響

有效分支因數(effective branching factor)b* 是一個描述啟發函數的質量的途徑。

如果對於一個特殊問題,A*演算法產生的總結點數為N,解的深度為d,那麼b*就是深度為d的一致搜尋樹,為了能夠包括 N + 1 個節點所必需的分支因數。因此,

N + 1 = 1 + b* + (b*)^2 + ... + (b*)^d

例如,如果A*演算法使用 52 個節點在第 5 層找到一個解, 那麼有效分支因數是1.92。有效分支因數可能根據問題實力發生變化,

但是通常在足夠難的問題中他是相當穩定的。因此(IDS比較適合在更難的問題上求解)

搜尋成本 有效分支因數

d IDS A*(h1) A*(h2) | IDS A*(h1) A*(h2)

2 10 6 6 2.45 1.79 1.79

4 112 13 12 2.87 1.48 1.45

6 680 20 18 2.73 1.34 1.30

8 6384 39 25 2.80 1.33 1.24

10 47127 93 39 2.79 1.42 1.22

12 3644035 227 73 2.78 1.44 1.24

一個良好設計的啟發函數會使b*的直接近於1

從鬆弛的問題產生可採納啟發式

h1 和 h2 評估的是八方塊遊戲中剩餘路徑的長度,但是對於遊戲的一個簡化版本他們也是非常精確的路徑長度。

如果遊戲的規則改變為每個方塊可以隨便移動,降低了行動限制的問題稱為鬆弛問題(relaxed problem)。

鬆弛問題的狀態-空間圖形為原始狀態空間的超圖形,因為移除限制時會在圖形增加邊緣。

一個鬆弛問題的最佳解的成本是原問題的一個可採納的啟發函數。由於得到的啟發函數是鬆弛問題的確切成本,他一定遵守三角不等式,因而是一致的。

問題的定義透過形式化語言描述,那麼自動的構造他的鬆弛問題是可能的,如果八方快遊戲的行動描述如下:

若 A 為水平或是垂直的鄰接 B 且 B為空格,則棋子可以從 A 移動到 B。

我們藉由移除一個或兩個情況來產生三個鬆弛問題:

(a) 一個棋子可以從方格 A 移動到方格 B,如果 A 和 B 相鄰。

(b) 一個棋子可以從方格 A 移動到方格 B,如果 B 是空的。

(c) 一個棋子可以從方格 A 移動到方格 B。

由(a),我們可以得到 h2(曼哈頓距離)。

原因是如果我們依次將每個棋子移入其目的地,那麼 h2 就是相對應的步數。

由(b)得到的啟發函數在習題3.34討論...

由(c)我們可以得到 h1(不在位的棋子數),因為如果把不在位的棋子一步移動到其目的地, h1 就是相對應的步數。

一個稱為 ABSOLVER 的城市可以從原始問題的定義出發,使用「鬆弛問題」方法和各種其他技術自動的產生啟發函數

h(n) = max{h1(n),...,hm(n)}

從子問題產生可採納啟發式 :模式資料庫

可採納的啟發函數也可以得至問題的子問題的解成本。

八方快的一個子問題。他的目標是將棋子1、2、3 和 4 移到正確的位置上,而不考慮其他棋子的情況

模式資料庫的想法就是儲存每個可能的子問題實例───在我們的例子中,就是四個棋子和一個空洞組成的每個可能局面───的精確解成本。(注意其他四個棋子的位置與解決這個子問題是無關的,但是移動那四個棋子的成本也要算在成本裡)。然後,我們對搜尋中遇到的每個完全狀態,在資料庫裡尋找相對應的子問題布局,都能計算出一個可採納的啟發函數hDB。

該資料庫本身的構造是透過從目標狀態,向後搜尋並記錄下每個新遇到模式的成本完成的;這個搜尋的開銷分攤到許多子問題實例上。

這種組合的啟發函數比曼哈頓菊犁要精確地多;求解隨機的 15 方塊遊戲時所產生的結點數要比曼哈頓距離作為啟發函數擴展的節點數少 1000 倍。

無交集的模式資料庫

我們紀錄的不是求解那麼很容易看出來兩個子問題的成本之和仍然是求解整個問題的成本地下界

從經驗裡學習啟發函數

啟發函數 h(n) 是用來估計從節點 n 出發的解成本的。

設計一個很容易找到最佳解的鬆弛問題。

「經驗」在這裡意味著求解大量的八方快遊戲。每個八方快遊戲的最優姊都提供了可學習 h(n) 的實例。

每個實例都包括解路徑上的一個狀態和從這個狀態到達解的成本。

一個歸納學習演算法可以用於構造能夠預測搜尋過程中所出現的其他狀態的解成本的函數 h(n) 。

用神經元網路、決策樹還有其他一些方法完成這項工作的技術 將在第十八張中介紹。(第二十一章中描述的強化學習方法也是可行的)。

歸納學習方法在提供了與其評價相關的狀態特徵的情況下是最可行的,比使用未加工的狀態描述好。例如,特徵「不在位的棋子數」對於預測從一個狀態到目標狀態的真實距離是有用的。

特徵 x1(n)

我們選取100個隨機產生的八方快遊戲布局,收集他們實際的解成本的統計資料。我們會發現當 x1(n) 是 5 的時候,平均解成本約為14

我們可以使用多個特徵。

第二特徵 x2(m) 可以是「現在相鄰並且在目標狀態中也相鄰的棋子對數」 如何將 x1 和 x2 結合起來預測 h(n) ? 通常的方法是使用線性組合:

h(n) = c1x1(n) + c2x2(n)

常數 c1 和 c2 用來調整結果,以最符合解成本的實際資料。 我們預期 c1 和 c2 為正,因為錯位的棋子和不正確相鄰對會使問題難以解決。

注意到,這個啟發是滿足條件:目標狀態的 h(n) = 0 ,但不必然為可採納或一致的。

}

人工智慧現代方法 第四章 進階搜尋

局部搜尋演算法和最佳化問題

如果目標存在,那麼完備的局部搜尋演算法總能找到目標;一個最佳的搜尋演算法總能找到全局最

小值/最大值。

爬山法搜尋

隨機重新開始爬山法採納了一條著名的諺語:「如果一開始沒有

成功,那麼嘗試,繼續嘗試。它透過隨機產生的初始狀態[1]來進行一系列的爬山法搜尋,直到找到

目標時停止搜尋。

爬山法搜尋演算法從來不「下山」,即不會向值比當前節點低的(或成本高的)方向搜尋,它肯定

是不完備的,因為它可能停留在局部極大值上。

相反地,純粹的隨機行走——就是從後繼者集合中

均勻的隨機選取一個後繼者,然後移動到這個選出來的後繼者——是完備的,但是毫無效率可言。

模擬退火

試圖把爬山法和隨機行走以某種方式結合起來,同時得到效率和完備性的想法是合理的。

在冶金中,退火是為了增強金屬和玻璃的韌性

或硬度而先把它們加熱到高溫再讓它們逐漸冷卻的過程,能使材料結合成一個低能量的結晶態。

模擬退火演算法,一個允許下山的隨機爬山法演算法。在退火初期下山移動容易被接受,而隨時

間推移下山的次數越來越少。輸入的schedule 決定了為時間函數的溫度T 的值

局部剪枝搜尋

記錄k 個狀態而不是一個。它由k 個隨機產生的狀態開始。每一步都產生全部

k 個狀態的所有後繼者狀態。如果其中有一個是目標狀態,演算法就停止。否則,它從整個後繼者列

表中選擇k 個最佳的後繼者,然後重複這個過程。

隨機剪枝搜尋

隨機剪枝搜尋不是從候選後繼

者集合中選擇最好的k 個後繼者狀態,而是按一定概率隨機地選擇k 個後繼者狀態,其中選擇給定

後繼者狀態的概率是狀態值的遞增函數。隨機剪枝選擇和自然選擇的過程有些相似性,「狀態」(生

物體)根據它的「值」(適應性)產生它的「後繼者」(後代)作為下一代。

基因遺傳演算法

是隨機剪枝搜尋的一個變化形式,它不是透過

修改單一狀態而是透過把兩個父代結合來產生後繼者的。它與自然選擇類似,這點和隨機剪枝搜尋

是一樣的,除了我們現在處理的是有性繁殖而不是無性繁殖。

像剪枝搜尋一樣,基因遺傳演算法也是從k 個隨機產生的狀態開始,我們稱作種群。每個狀態,

或稱個體,用一個有限長度的字串表示——通常是0、1 字串。例如,八皇后問題的狀態必須指定

八個皇后的位置,每列有八個位置,那麼一個狀態則需要8 × log28 = 24 位元來表示。或者每個

狀態可以由八個數字表示,每個數字的範圍都是從1 到8。(我們將在後面看到這兩種不同的編碼形

式其表現差異很大。圖4.6(a)顯示了一個由4 個表示八皇后狀態的8 數字字串組成的種群。

基因遺傳演算法,圖解說明以數字字串表示八皇后的狀態。(a)是初始種群,(b)是適應度函數,(c)

是配對結果。(d)是它們雜交產生的後代,(e)是突變的結果

(b)-(e)顯示了產生下一代狀態的過程。在(b)中,每個狀態都由它的目標函數或適應度函數

(在基因遺傳演算法的術語裡)給出評價值(適應值)。對於好的狀態,適應度函數將返回較高的值,因

此,對於八皇后問題,我們用不相互攻擊的皇后對的數目來表示,最佳解的適應值是28。這四個狀

態的適應值分別是24,23,20 和11。在這個特定的基因遺傳演算法形式中,被選擇進行繁殖的概

率直接與個體的適應值成正比,其百分比在原始得分旁邊標出。

在(c)中,按照(b)中的機率隨機地選擇兩對進行繁殖。注意其中的一個個體被選擇了兩次而另一

個一次也沒選中。對於要配對的每一對個體,雜交點是在字串中隨機選擇的一個位置。在圖中,

雜交點在第一對的第三數字之後和在第二對的第五數字之後。

在(d)中,後代本身是透過父代字串在雜交點上進行雜交而創造出來的。例如,第一對的第一個

後代從第一個父代得到了前三數字、從第二個父代那裡得到剩下的數字,而第二個後代從第二個父

代得到了前三數字、從第一個父代得到剩下數字。下圖顯示了這次繁殖過程中涉及的八皇后狀態。

這個例子顯示一個事實,如果兩個父代字串差異很大,那麼雜交產生的狀態和每個父代狀態都相差

很遠。通常的情況是過程中早期的群體是多樣化的,因此雜交(類似於模擬退火)在搜尋過程的早期階

段在狀態空間中常採用較大的步調,而在後來當大多數個體都很相似的時候採用較小的步調。

與圖(c)中的前兩個父代還有圖(d)中的第一個後代相對應的八皇后問題的狀態。陰影部分的

列在雜交過程中丟失了,非陰影部分的列保留了下來

最後,在(e)中每個位置都會按照一個獨立的小概率隨機地變異。在第一、第三和第四個後代中

都有一個數字發生了突變。在八皇后問題中,這相當於隨機地選取一個皇后把它隨機地放到該列的

某一個方格裡。

像隨機剪枝搜尋一樣,基因遺傳演算法結合了上山的趨勢和隨機的探索,並在並列搜尋引線之

間交換資訊。基因遺傳演算法最主要的優點,如果有的話,還是來自於雜交的操作。不過可以在數

學上證明,如果基因編碼的位置在初始的時候就隨機地轉換的話,雜交就沒有優勢了。直觀地講,

雜交的優勢在於它能夠將獨立發展出來而能執行有用功能的「磚塊」(多個相對固定的字元構成)結合

起來,因此提高了搜尋操作的解析度水準。例如,將前三個皇后分別放在位置2、4 和6(互相不攻擊)

就組成了一個有用的磚塊,它可以和其他有用的磚塊結合起來構造問題的解。

基因遺傳演算法的理論用模式(schema)的想法解譯了這是怎樣運轉的,模式就是其中某些數字未

確定的一個子字串。例如,模式246*****描述了所有前三個皇后的位置分別是2、4、6 的狀態。能

匹配這個模式的字串(例如24613578)被稱作該模式的實例。可以顯示,如果一個模式的實例的平均

適應值是超過均值的,那麼種群內這個模式的實例數量就會隨時間增加。顯然,如果鄰近位元相互

之間是無關的,那麼這個效果就沒有那麼顯著了,因為只有很少的鄰接磚塊能提供一致的好處。基

因遺傳演算法在模式與解的有意義的成份相對應時才工作得最好。例如,如果字串表示的是一個天

線,那麼這些模式就表示天線的組成部分,諸如反射器和偏轉儀。一個好的組成部分在各種不同設

計下很可能都是好的。這說明基因遺傳演算法的成功運用需要仔細的知識表示工程。

實際上,基因遺傳演算法在最佳化問題上有很廣泛的影響,諸如電路佈局和零工型工廠間排程

問題。現在,還不清楚基因遺傳演算法的吸引力是源自其性能,還是源自其美學角度滿足了進化論

的形式。為了確認在什麼情況下使用基因遺傳演算法能夠達到好的效果,還有很多研究工作要做。

進化與搜尋

進化論是查理斯‧達爾文(Charles Darwin)在《物種起源》(On the Origin of Species by Means of

Natural Selection,1859)(編註:直譯為《透過自然選擇方式的物種起源》)一書中提出的。它的核心

想法很簡單:變化出現在繁殖過程中,並且將在後代中保存下來,與它們對繁殖適應度的影響呈近

似比例。

達爾文的理論並沒有揭示出生物體的特性是怎樣遺傳下來或改變的。控制這個過程的機率規律

首先是由一個叫葛列格‧孟德爾(Gregor Mendel,1866)的修道士發現的,他在甜豌豆上進行了實驗。

很久以後,Watson 和Crick(1953)確定了DNA 分子的結構及其序列,AGTC(腺嘌呤,鳥嘌呤,胸腺

嘧啶,胞嘧啶)。在標準的模型中,基因序列上的某點的突變或者「雜交」(後代的DNA 序列是透過

雙親DNA 序列長片段的合成產生的)都會導致發生變異。

與局部搜尋演算法的相似性我們已經介紹過了;隨機剪枝搜尋演算法與進化演算法之間最主要

的區別就是對有性繁殖的利用,在有性繁殖中後代是由多個而不是一個生物體產生的。然而,實際

的進化機制比多數基因遺傳演算法要豐富得多。例如,變異就包括DNA 的反轉、複製和大段的移動;

一些病毒借用一個生物體的DNA,再插入到其他生物體的DNA 裡;在基因組裡還有可換位基因,

它除了把自己複製成千上萬遍以外不做其他事情。甚至還有些基因破壞不攜帶該基因的細胞以避免

可能的配對,從而提高它們本身的複製機率。最重要的是基因本身對基因控制進行編碼,這些編碼

決定了基因組是如何繁殖和轉變成為生物體的。在基因遺傳演算法中,這些機制是單獨的程式,而

不是表現在被處理的字串中。

達爾文的進化論,可能會出現效率低下,一點兒都沒有改進它的搜尋啟發函數而盲目地產生了

大約1045 種生物。然而,比達爾文早50 年,另一位偉大的法國自然科學家讓‧拉馬克(Jean Lamarck,

1809)提出了一種進化理論,在生物的一生中透過適應獲得的特性將會傳給它的後代。這個過程是很

有效率的,但是在自然界裡似乎不太可能發生。很多年之後,詹姆斯‧鮑德溫(James Baldwin,1896)

提出了一個更淺顯的類似理論:在生物體存活的時間裡學習到的行為能夠加快進化速度。鮑德溫的

理論與拉馬克的不同,而與達爾文的進化論卻是完全一致的,因為它依賴於作用在個體上的選擇壓

力,這些個體會在遺傳天性允許的可能行為集合上找到局部最佳。電腦模擬確認「鮑德溫效應」是

真實的,「普通的」進化曾經創造出內在性能度量和實際適應性相關的生物體。

連續空間的局部搜尋

我們描述過的(除了首選爬山法及模擬退火)演算法沒有一個能夠處理連續狀態及行動空間,因其有無

限多個分支因數。

局部搜尋演算法在連續狀態空間和離散狀態空間都一樣受到局部極大值、山脊、高原的影響。

隨機重新開始和模擬退火都可以使用,並且經常都很有用。然而高維的連續空間,在這種大的地方很

容易使這種演算法迷失。

限制最佳化

若問題的解須滿足對於每個變數值的某些嚴格限制,

則這個最佳化問題是受限制的。例如,在我們的機場選址問題中,我們可以限制機場的位置是在羅

馬尼亞境內,並且是在旱地上(而不是在湖中央)。限制最佳化問題的難點取決於限制和目標函數的性

質。最著名的一種限制最佳化問題是線性規劃問題,其限制必須是線性不等式並且能夠組成一個凸

多邊形集[8],同時目標函數也是線性的。線性規劃中的時間複雜度,顯現於其多項式中的變數數。

不確定性行動的搜尋

在部分可觀察的環境中,每個知覺有助於縮小代理人可能存在的狀態組,從而使得代理人更容易完成其目標。當環境為

不確定性時,知覺告訴代理人,已實際發生行動的可能結果。在這兩種情況下,未來的知覺不能事

先確定,代理人的未來行動將取決於這些未來的知覺。因此,問題的解並不是一個序列,而是一個

偶發/應變規劃(也稱為策略),它指定該怎麼做則取決於收到什麼知覺。

我們還需要將問題的解轉成一般化的概念。例如,如果我們在狀態1 開始,沒有單一行動序列

可解決此問題。相反地,我們需要一項如以下的偶發規劃:

[Suck, if State =5 then [Right, Suck] else [ ] ] (4.3)

因此,不確定性問題的解可以包含巢狀if-then-else 語句,這意味著它們是樹(tree),而不是序列。這

使得選擇行動可基於執行過程中產生的偶發事件。許多在真實、實體世界的問題都是偶發性問題,

因為確切的預測是不可能的。由於這個原因,很多人在走路或者開車時都會睜開眼睛。

AND-OR 搜尋樹

在確定性環境中,唯一的分支,是在每個狀態中由代理人自己所選擇引入。我們稱這些節點為OR(或)節點。

在不確定性的環境中,分支也是在每個行動的結果由環境的選擇引入。我們稱這些節點為AND(及)節點。

用於不確定性環境產生的AND-OR 圖的一個搜尋演算法。它回傳一個有條件的規劃,其在所有

的環境下到達目標狀態(符號[ x | l ]列表,是在 l 列表的前面加入目標x 而得)

嘗試,繼續嘗試

一般來說一個循環規劃可被視為一種解,它提供每個葉子都是一個目標狀態,且從規劃中的每一個點都可以到達葉子。

給循環解下個定義,代理人執行這樣的解,最終會到達目標,每一個不確定性行動的結果,終

究會發生。這種情況合理嗎?這取決於不確定性的原因。如果行動為擲骰子,那麼它的合理假設,

最終將擲出六。如果行動是插入卡片鑰匙到酒店的門鎖,但它第一次並沒有效,然後也許最終會有

效,或者鑰匙是錯誤的(或房間是錯誤的!)。經過七、八次嘗試後,多數人會認為問題是鑰匙,並回

到櫃台換一個新的。一種理解這個決定的方法是說,最初丟棄問題的形式化(可觀察的,不確定性的),

是為支持不同的形式化(部分可觀察的,確定性的),其失敗是因為鑰匙不可觀察的性質。在第13 章

我們有更詳細的說明這個課題。

使用部分觀察的搜尋

即使是在確定性的環境,則一個行動可能會導致幾個可能的結果之一。解決部分可觀察的問題,需要的關鍵概念是信度狀態,

代表代理人對其可能存在的實體狀態的當前信念,給予行動序列和到該點的知覺。我們首先從最簡單的情況下研究信度狀態,

這是當代理人完全沒有感測器,然後我們加入部分感測以及不確定性的行動。

使用沒有觀察的搜尋

當代理人的知覺沒有提供任何資訊時,即我們所謂的無感測器問題,或者有時稱為一致性問題。

感測的高成本是另一個避免它的原因:例如,醫生經常開廣譜抗生素,而不是使用應變規劃:

先進行昂貴的血液測試,然後等著結果出來,再開更特效的抗生素,或是因為已感染太廣而住院。

即使是最有效的解的演算法,在沒有解存在時也是沒有多大用處。沒有感測時,很多事是無法

做到的。例如,無感測器八方塊遊戲是不可能的。另一方面,一點點的感測即可走一段很長的路。

例如,如果只有一個方格是看得見的,則每個八方塊遊戲的實例是可解的——這解包括了按順序移

動每個方塊到看得見的方格,然後跟踪它的位置。

使用觀察的搜尋

部分可觀察問題的不確定性,來自於無法準確預測哪些知覺會在行動之後被接收到;在

實體環境中的基本不確定性,經由擴大在預測階段的信度狀態可能會貢獻到此,使在觀察階段導致

更多的知覺。

求解部分可觀察的問題

部分可觀察的環境代理人

有時知覺對於局部化並沒有太大的幫助:如果有一個或更多個長的

東西向走廊,那麼機器人可以收到長序列的NS 知覺,但永遠不知道它是在走廊的哪裡。

可能的機器人位置,☉,(a) 在一個觀察E1 =NSW 之後;(b) 在第二個觀察E2 = NS 之後。當感

測器是無雜訊且轉換模式是準確的,則機器人沒有其他可能的位置,與這兩個觀察序列一致

線上搜尋代理人和未知環境

至今為止我們一直把目光集中在代理人的離線搜尋演算法。他們在踏上現實世界之前先計算出一

個完整的解,然後再執行該解。與之相反,線上搜尋代理人是透過計算和行動的交叉完成的:首

先它先採取一個行動,然後觀察問題的環境並且計算出下一個行動。線上搜尋在動態或半動態的問

題領域——對於停留不動或者計算時間太長都會有懲罰的領域——是一個好的想法。線上搜尋也有

助於在不確定性的領域,因為它允許代理人集中努力其運算在實際發生的偶發情況,而不是那些可

能但也許不會發生的情況。當然,有一個權衡:代理人事先規劃的越多,那麼它自己會發現沒有槳

的小溪越少。

線上搜尋對未知環境是一個必要的想法,在那裡的代理人並不知道存在什麼狀態,或做什麼行

動。在這種無知的狀態下,代理人面臨了探索問題,必須使用自己的行動作為實驗,學習足以讓其

想法是值得的。

線上搜尋的一個範例是放在新建大樓裡的機器人,要求它探索大樓,繪製出一張從A 到B 的地

圖。逃離迷宮的方法——胸懷抱負的古代英雄所需的知識——也是線上搜尋演算法的一個例子。不

過,空間探索不是探索的唯一形式。考慮新生嬰兒:它有許多可能的行動,但是不知道這些行動的

後果,而且它只經歷過少數幾個它能到達的可能狀態。嬰兒對世界運轉情況的逐步發現,部分地,

也是一個線上搜尋過程。

線上搜尋問題

線上搜尋問題必須透過代理人執行行動解決,而不是純粹的計算過程。我們假設一個確定性的,

且完全可觀察的環境(第17 章放鬆這些假設),但我們規定,代理人只知道以下幾點:

● ACTIONS(s),傳回狀態s 下的可能行動的列表;

● 單步成本函數c(s, a, s')——注意直到代理人知道行動的結果為狀態s' 時才能用;

● GOAL-TEST(s)。

死路是機器人探索中的實際困難——樓梯、斜坡、懸崖、單行道和各式各樣自然的地形都提供

了不可逆行為的機會。為了取得進展,我們可以簡單地假設狀態空間是可安全探索的——也就是說,

從每個可到達的狀態出發都有某些目標狀態是可到達的。具有可逆行動的狀態空間,例如迷宮問題

和八方塊遊戲,可以視為無向圖,並且顯然是可安全探索的。

即使在可安全探索的環境裡,如果有無限大成本的路徑,就一定會有無上限的競爭率。這在行

動不可逆的環境中很容易顯示出來,不過事實上它在行動可逆的情況下也是成立的,如圖4.20(b)所

示。由於這個原因,通常根據整個狀態空間的大小,而不是僅根據最淺的目標的深度,來描述線上

搜尋演算法的性能。

線上搜尋代理人

在每個行動之後,線上代理人都能接收到知覺資訊,告訴它到達了哪個狀態;根據這個資訊,

它可以擴展自己的環境地圖。當前的地圖用來決定下一步往哪裡走。這種規劃和行動的交叉意味著

線上搜尋演算法,和我們看到的離線搜尋演算法是相當不同的。

使用深度優先探索的一個線上搜尋代理人。該代理人只適用於,其中每個行動都可以由其他一

些行動使其「未完成」這樣的狀態空間

線上局部搜尋

如同深度優先搜尋,爬山法搜尋在節點擴展的時候也有局部性。實際上,因為它在記憶體中只

存放一個當前狀態,爬山法搜尋其實就是一個線上搜尋演算法了!不幸的是,它最簡單的形式並沒

什麼用,因為它使代理人呆在局部極大值上而無處可去。此外,隨機重新開始演算法是不能用的,

因為代理人不能把自己傳送到一個新的狀態。

取代隨機重新開始,可以考慮使用隨機行走來探索環境。隨機行走簡單地從當前狀態隨機選擇

可能的行動之一;選擇的時候可以偏向尚未嘗試過的行動。很容易證明倘若狀態空間為有限,隨機

行走最終會找到目標或完成探索。然而,這個過程會很慢。圖顯示了一個環境,在其中隨機

行走演算法將耗費指數級的步數來找到目標,因為每一步往回走的進展都是向前走的兩倍。當然這

個例子是設計出來的,但是許多現實世界的狀態空間的拓撲結構都能造成此類對隨機行走而言的「陷

阱」。

在一個一維狀態空間上LRTA*的五次疊代。每個狀態都標出到達目標的當前成本估計H(s),每條連線則標出其單步成本。

陰影狀態表示代理人所在的位置,並將每次疊代的更新成本估計,畫上圓圈標記出來。

提高爬山法演算法的記憶體利用率而不是隨機性是個更有效的方法。

LRTA*-AGENT 根據相鄰狀態的值選擇一個行動,代理人在狀態之間移動時更新狀態值

線上搜尋的學習

線上搜尋代理人初始對環境的無知提供了一些學習的機會。首先,代理人僅僅根據它的經歷學

習到環境的「地圖」——更精確地說,是每個狀態經過每個行動的結果。(注意確定性環境的假設意

味著每個行動經歷一次就足夠了)。其次,局部搜尋代理人利用局部更新規則(和LRTA*中的情況一

樣)可以得到每個狀態更精確的估計值。

一個簡單的迷宮問題。代理人從狀態S 出發要到達狀態G,但是代理人對環境一無所知

追蹤ONLINE-DFS-AGENT 在上圖環境中的行為表現,你將

會注意到代理人並不十分聰明。例如,當它已經看到行動Up 能從狀態(1, 1)到狀態(1, 2)時,它仍然

不知道行動Down 能回到狀態(1, 1),或者行動Up 還能從狀態(2, 1)到狀態(2, 2),從狀態(2, 2)到狀態

(2, 3),等等。通常,我們希望代理人學習到Up 能使y 座標值增加,除非遇到牆;Down 能使y 座標

值減少,等等。要達到這些必須滿足兩件事情。首先,需要一個對這種一般規則,具形式化和明確

的可操作描述,到目前為止,我們把這些資訊隱藏在稱為RESULT 函數的黑盒子裡。

總結

本章研究了在「傳統」可觀察的、確定性的、離散的環境中,尋找到達目標的最短路徑問題案

例之外的一些搜尋演算法。

● 局部搜尋方法諸如爬山法用於完全狀態形式化,它只在記憶體中保留很少數目的節點。已經發

展了幾種隨機演算法,包括模擬退火,當給定一個合適的冷卻排程安排時,它能夠返回最佳解。

● 許多局部搜尋方法也適用於在連續空間的問題。線性規劃和凸多邊形最佳化問題,遵守狀態空

間的一定形狀的限制和目標函數的性質,並認同在實務中往往是非常有效的多項式時間演算法。

● 基因遺傳演算法是一個保留大量狀態種群的隨機爬山法搜尋。新的狀態透過突變和雜交產生,

雜交把來自種群的狀態對結合在一起。

● 在不確定性的環境中,代理人可以應用AND-OR 搜尋產生偶發規劃,無論在執行過程中發生任

何結果,它都會到達目標。

● 當環境是部分可觀察的,信度狀態表示出該代理人可能存在的狀態集

● 標準的搜尋演算法可以直接應用於信度狀態空間來解決無感測器問題,信度狀態 AND-OR 搜尋

可以解決部分可觀察的問題。在漸增演算法,信度狀態中透過狀態到狀態的構建解,往往更有

效率。

● 探索問題出現在代理人對環境的狀態和行動一無所知時。對於可安全探索的環境,線上搜尋代

理人能夠建造一個地圖並且找到可能存在的目標。根據經驗更新啟發函數估計,提供了一種避

免局部極小值的有效方法。