本文由 伯樂在線 - 土豆粉ss 翻譯括细，黃利民 校稿伪很。未經(jīng)許可，禁止轉(zhuǎn)載奋单！
英文出處：theory.stanford.edu锉试。歡迎加入翻譯組。
本系列：
- 關(guān)于尋路算法的一些思考（1）：A* 算法介紹
- 關(guān)于尋路算法的一些思考（2）：Heuristics 函數(shù)
- 關(guān)于尋路算法的一些思考（3）：A* 算法的實現(xiàn)
- 關(guān)于尋路算法的一些思考（4）：A* 算法的變體
- 關(guān)于尋路算法的一些思考（5）：處理移動中的障礙物
- 關(guān)于尋路算法的一些思考（6）：預(yù)先計算好的路徑的所用空間
- 關(guān)于尋路算法的一些思考（7）：地圖表示
- 關(guān)于尋路算法的一些思考（8）：長期和短期目標(biāo)
- 關(guān)于尋路算法的一些思考（9）：尋路者的移動成本
- 關(guān)于尋路算法的一些思考（10）：最短路徑的用戶體驗
- 關(guān)于尋路算法的一些思考（11）：尋路算法的其他應(yīng)用
- 關(guān)于尋路算法的一些思考（12）：AI 技術(shù)
AI技術(shù)
尋路問題常常會和人工智能（AI） 聯(lián)系在一起应又，原因是 A算法和許多其他尋路算法是由 AI 研究者開發(fā)出來的。一些生物啟發(fā)式的 AI 技術(shù)目前十分流行，我也收到一些為何不使用這類技術(shù)的咨詢奖磁。神經(jīng)網(wǎng)絡(luò)是依據(jù)實例的大腦學(xué)習(xí)建模——給定一個正解的集合鸣哀，它會學(xué)習(xí)出一個一般的解決問題模式。強(qiáng)化學(xué)習(xí)是依據(jù)經(jīng)驗的大腦學(xué)習(xí)建模——給定一些行為的集合和最終獎懲結(jié)果破加，它會學(xué)習(xí)出哪種行為是正確或錯誤的了罪。遺傳算法根據(jù)自然選擇的進(jìn)化規(guī)律建母ū纾——給定一些agent 集合踊餐，優(yōu)勝劣汰。通常情況下，遺傳算法不允許 agent 在他們的生存時間內(nèi)進(jìn)行學(xué)習(xí)获搏。強(qiáng)化學(xué)習(xí)則不但允許 agent 在生存時間內(nèi)學(xué)習(xí)纬乍，還可以和其他 agent 分享知識墓贿。（譯注：agent：智能體队伟，正文保留未翻）*
神經(jīng)網(wǎng)絡(luò)
神經(jīng)網(wǎng)絡(luò)是這樣構(gòu)建的：它受到訓(xùn)練代嗤，來對輸入進(jì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ù)的表達(dá)可以明顯小于真實的函數(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ù)表達(dá)。
在尋路問題中类垦，函數(shù) f(start,goal)=path砰琢。我們并不知道輸出路徑是什么况增。我們可以使用一些方法为肮，可能是 A*算法，來計算它們。但是如果我們能根據(jù)(start, goal)計算路徑累盗，那么我們就已經(jīng)知道了函數(shù) f蠢琳，那么為什么還要自找麻煩的找它的近似函數(shù)呢？因為我們已經(jīng)完全知道了函數(shù) f，再歸納 f 就沒有用了。用函數(shù)近似的唯一潛在的好處可能會降低 f 的表達(dá)規(guī)模翅雏。但f 表達(dá)的是個相當(dāng)簡潔幾乎不占用空間的算法靴迫，所以我認(rèn)為神經(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ù)可以計算到達(dá)目的地的最小成本，如果一個單元沿著路徑 P=p1,p2,…,pn移動屹培，當(dāng)每穿過一段路徑的時候，我們可以更新 n到近似函數(shù) h 中甫何，其中g(shù)(pi,pn)=（從i到 n 的實際移動成本）。當(dāng)啟發(fā)函數(shù)優(yōu)化了娄琉，A算法也會運(yùn)行的更快杏慰。
神經(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 值比較遠(yuǎn)的點表現(xiàn)更好鸥滨。遺傳算法改善了爬山算法嗦哆，它保留了 x 的多樣性，使用比如變異和交換的進(jìn)化-啟發(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ìn)化出一個新的算法衍腥。
也許在和神經(jīng)網(wǎng)絡(luò)結(jié)合的情況下绽快，遺傳算法可以應(yīng)用于尋路問題的某個部分。但是紧阔，在這篇文章中我還不知道有何用處坊罢。相反，如果問題解是已知的擅耽，估計會有一個更有前途的方法作為許多可行工具之一活孩，在尋路問題中優(yōu)化 agent。
強(qiáng)化學(xué)習(xí)
和遺傳算法一樣乖仇，強(qiáng)化學(xué)習(xí)是一種非監(jiān)督學(xué)習(xí)憾儒。然而询兴，和遺傳算法不同的是，agent 可以在他們的生存時間內(nèi)學(xué)習(xí)起趾；沒必要等著觀察他們的存活情況诗舰。并且，多 agents 同時參與到不同部分中分享各自學(xué)習(xí)成果是可能的训裆。強(qiáng)化學(xué)習(xí)和 A*的核心部分有著一些相似的地方眶根。
在 A中，到達(dá)結(jié)束目標(biāo)后會沿著經(jīng)過的路徑追溯回去边琉，標(biāo)記到目前為止所有路徑的選擇属百；其他選擇就被去掉了。在強(qiáng)化學(xué)習(xí)中变姨，可以測算每個狀態(tài)時的情況族扰，并且當(dāng)前的獎（懲）都可以追溯回導(dǎo)致這個狀態(tài)之前的所有選擇。使用一個值函數(shù)表達(dá)這個追溯的過程定欧，這有點像 A中的啟發(fā)式函數(shù)渔呵，但隨著 agent 嘗試新路徑并對這過程進(jìn)行學(xué)習(xí)的更新，這一方面兩者是不同的砍鸠。
相比于更簡單的算法來說厘肮，強(qiáng)化學(xué)習(xí)和遺傳算法的一個關(guān)鍵的優(yōu)勢是：在探求新解和利用目前學(xué)到的信息兩者間是可以做出選擇的。遺傳算法睦番，通過變異尋找（新解）类茂；強(qiáng)化學(xué)習(xí)，通過明確給出選擇新行為的概率尋找（新解）托嚣。
即使和遺傳算法結(jié)合巩检，我認(rèn)為強(qiáng)化學(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)注伯樂在線的其他文章 :)
