關(guān)于尋路算法的一些思考（12）：AI 技術(shù)

本文由 伯樂在線 - 土豆粉ss 翻譯，黃利民 校稿。未經(jīng)許可，禁止轉(zhuǎn)載！
英文出處：theory.stanford.edu。歡迎加入翻譯組。

本系列：

AI技術(shù)

尋路問題常常會和人工智能（AI） 聯(lián)系在一起，原因是 A算法和許多其他尋路算法是由 AI 研究者開發(fā)出來的。一些生物啟發(fā)式的 AI 技術(shù)目前十分流行，我也收到一些為何不使用這類技術(shù)的咨詢。神經(jīng)網(wǎng)絡(luò)是依據(jù)實例的大腦學(xué)習(xí)建?！o定一個正解的集合，它會學(xué)習(xí)出一個一般的解決問題模式。強化學(xué)習(xí)是依據(jù)經(jīng)驗的大腦學(xué)習(xí)建?！o定一些行為的集合和最終獎懲結(jié)果，它會學(xué)習(xí)出哪種行為是正確或錯誤的。遺傳算法根據(jù)自然選擇的進化規(guī)律建?！o定一些agent 集合，優(yōu)勝劣汰。通常情況下，遺傳算法不允許 agent 在他們的生存時間內(nèi)進行學(xué)習(xí)。強化學(xué)習(xí)則不但允許 agent 在生存時間內(nèi)學(xué)習(xí)，還可以和其他 agent 分享知識。（譯注：agent：智能體，正文保留未翻）*

神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)是這樣構(gòu)建的：它受到訓(xùn)練，來對輸入進行模式識別。他們是一種用來處理函數(shù)近似的方法:給定 y1 = f(x1),y2 = f(x2), …, yn = f(xn)，構(gòu)建一個函數(shù) f’使得 f’逼近 f。近似函數(shù) f’一般都是光滑的：對于接近 x 點的 x’，我們希望 f’(x)也能接近f’(x’)。

函數(shù)近似方法可以滿足以下兩個目的：

  • 規(guī)模：近似函數(shù)的表達可以明顯小于真實的函數(shù)規(guī)模。
  • 泛化：未知函數(shù)值的輸入數(shù)據(jù)可以使用近似函數(shù)

神經(jīng)網(wǎng)絡(luò)典型做法是使用一組輸入值向量，產(chǎn)生一組輸出值向量。在算法內(nèi)部，訓(xùn)練“神經(jīng)元”(neurons)的權(quán)重。神經(jīng)網(wǎng)絡(luò)使用監(jiān)督學(xué)習(xí)，即輸入和輸出都是已知的，學(xué)習(xí)的目標(biāo)是建立一個可以近似輸入輸出映射的函數(shù)表達。

在尋路問題中，函數(shù) f(start,goal)=path。我們并不知道輸出路徑是什么。我們可以使用一些方法，可能是 A*算法，來計算它們。但是如果我們能根據(jù)(start, goal)計算路徑，那么我們就已經(jīng)知道了函數(shù) f，那么為什么還要自找麻煩的找它的近似函數(shù)呢？因為我們已經(jīng)完全知道了函數(shù) f，再歸納 f 就沒有用了。用函數(shù)近似的唯一潛在的好處可能會降低 f 的表達規(guī)模。但f 表達的是個相當(dāng)簡潔幾乎不占用空間的算法，所以我認為神經(jīng)網(wǎng)絡(luò)在這里也沒有什么用。另外，神經(jīng)網(wǎng)絡(luò)輸出規(guī)模是固定的，而尋路問題規(guī)模是可變的。

但另一方面，函數(shù)近似可能對構(gòu)建尋路的一些組成部分有用。比如移動的成本函數(shù)是未知的。例如，沒有實際移動操作和戰(zhàn)役的情況下，穿越怪獸聚集森林的成本，我們可能并不知道。使用函數(shù)近似的方法的話，每次穿越森林時，移動成本函數(shù)f(number of orcs, size of forest)可以測量出來并裝入神經(jīng)網(wǎng)絡(luò)模型中（注：這里移動成本f的自變量是怪獸數(shù)量和森林規(guī)模）。對于未來的尋路部分，根據(jù)算出的未知移動成本，我們可以找到更好的路線。

另一個可以從歸功于近似計算的函數(shù)是啟發(fā)式函數(shù)。A算法中的啟發(fā)式函數(shù)可以計算到達目的地的最小成本，如果一個單元沿著路徑 P=p1,p2,…,pn移動，當(dāng)每穿過一段路徑的時候，我們可以更新 n到近似函數(shù) h 中，其中g(shù)(pi,pn)=（從i到 n 的實際移動成本）。當(dāng)啟發(fā)函數(shù)優(yōu)化了，A算法也會運行的更快。

神經(jīng)網(wǎng)絡(luò)盡管對于尋路算法本體不太實用，但對 A*算法使用的函數(shù)可以起到作用。移動函數(shù)和啟發(fā)式函數(shù)都可以測算，因此能給函數(shù)近似反饋。

遺傳算法

根據(jù)適應(yīng)度函數(shù)（fitness function），遺傳算法允許開發(fā)參數(shù)空間來求得效果良好的解。他們是一種用來處理函數(shù)優(yōu)化的方法：給定一個函數(shù)g(x)（x 是一組典型的參數(shù)值向量），求得能最大化（或最小化）g(x)的 x 值。這是一種非監(jiān)督學(xué)習(xí)——問題的正確答案預(yù)先并不知道。

對于尋路問題，給定一個起始位置和一個目標(biāo)位置，x 是這兩點間的路徑，g(x)是穿越這路徑的成本。簡單的優(yōu)化方法，比如爬山算法會以增加g(x)為代價的方法改變 x。不幸的是，在一些問題中，會遇到“局部最大值”，x 值周圍沒有點 具有更大的對應(yīng)g值，但是某個離x 值比較遠的點表現(xiàn)更好。遺傳算法改善了爬山算法，它保留了 x 的多樣性，使用比如變異和交換的進化-啟發(fā)式方法更新 x。

爬山算法和遺傳算法可以用來學(xué)習(xí)出 x 的最優(yōu)值。然而對于尋路問題，我們已經(jīng)有了 A*算法找到最優(yōu)的 x ，因此函數(shù)優(yōu)化的方法就不需要了。

遺傳編程是遺傳算法的更深層次，它把程序當(dāng)做參數(shù)。例如，你可以輸入的是尋路算法而不是尋路路徑，你的適應(yīng)值函數(shù)會根據(jù)表現(xiàn)測算每個算法。對于尋路問題來說，我們已經(jīng)有個很好的算法，我們無需在進化出一個新的算法。

也許在和神經(jīng)網(wǎng)絡(luò)結(jié)合的情況下，遺傳算法可以應(yīng)用于尋路問題的某個部分。但是，在這篇文章中我還不知道有何用處。相反，如果問題解是已知的，估計會有一個更有前途的方法作為許多可行工具之一，在尋路問題中優(yōu)化 agent。

強化學(xué)習(xí)

和遺傳算法一樣，強化學(xué)習(xí)是一種非監(jiān)督學(xué)習(xí)。然而，和遺傳算法不同的是，agent 可以在他們的生存時間內(nèi)學(xué)習(xí)；沒必要等著觀察他們的存活情況。并且，多 agents 同時參與到不同部分中分享各自學(xué)習(xí)成果是可能的。強化學(xué)習(xí)和 A*的核心部分有著一些相似的地方。

在 A中，到達結(jié)束目標(biāo)后會沿著經(jīng)過的路徑追溯回去，標(biāo)記到目前為止所有路徑的選擇；其他選擇就被去掉了。在強化學(xué)習(xí)中，可以測算每個狀態(tài)時的情況，并且當(dāng)前的獎（懲）都可以追溯回導(dǎo)致這個狀態(tài)之前的所有選擇。使用一個值函數(shù)表達這個追溯的過程，這有點像 A中的啟發(fā)式函數(shù)，但隨著 agent 嘗試新路徑并對這過程進行學(xué)習(xí)的更新，這一方面兩者是不同的。

相比于更簡單的算法來說，強化學(xué)習(xí)和遺傳算法的一個關(guān)鍵的優(yōu)勢是：在探求新解和利用目前學(xué)到的信息兩者間是可以做出選擇的。遺傳算法，通過變異尋找（新解）；強化學(xué)習(xí)，通過明確給出選擇新行為的概率尋找（新解）。

即使和遺傳算法結(jié)合，我認為強化學(xué)習(xí)也不會在尋路問題本身上使用。但是相對來說，它卻可以作為一個向?qū)В笇?dǎo)agent 在游戲世界中如何表現(xiàn)。

注： 函數(shù)近似方法可以變形為函數(shù)優(yōu)化問題。為了找到最逼近 f(x)的f'(x),令 g(f’)=∑(f’(x)-f(x))^2（即在所有輸入 x 上(f’(x)-f(x))^2的和）。

參考

作者寫這個系列的參考文章在這里。我們翻譯組的工作，基本結(jié)束了此為止咯，歡迎大家保持關(guān)注伯樂在線的其他文章 :)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容