塑料機械網
技術文章
準確 藍芯科技給您推薦路徑搜索
閱讀：921 發布時間：2019-11-19 引言
正所謂在家靠父母，出門靠高德。在那錯綜復雜的工廠里，我們的機器人哪怕視力驚人，也沒辦法一眼看到目的地。為了準確又的把貨物送到目的地，小藍(杭州藍芯科技有限公司簡稱)只能祭出殺招了，那就是----搜索算法。在路徑搜索問題中，搜索算法可以生成一個的解，按照搜索邏輯不同，可以分為深度優先法和廣度優先法。但是，在實際工程上會使用一些近似算法去解決路徑搜索問題，主要分為啟發式搜索的A*、D*、Focused D*算法和準啟發式搜索的退火、進化、蟻群優化算法。本文通過介紹啟發式搜索的A*算法和準啟發式搜索的遺傳進化算法，讓大家感受這兩類算法的特色與魅力。
A*算法
A*算法作為經典啟發式搜索算法，正廣泛運用于智能機器人、無人駕駛等領域。詳細來說，A*算法是一種靜態路網中求解短路徑有效的直接搜索方法，也是許多其他問題的常用啟發式算法。從公式上的描述是：
f(n)=g(n)+h(n),
f(n) 是從初始狀態經由狀態n到目標狀態的代價估計，
g(n) 是在狀態空間中從初始狀態到狀態n的實際代價，
h(n) 是從狀態n到目標狀態的低的估計代價。
那么什么是代價呢，為了便于理解，你可以直接認為這里的代價就是距離。假設如圖1中場景，小藍要從出發點begin到目標點end，該如何選擇路線呢？首先從出發點開始，可以選擇去a點，也可以選擇去d點。那么究竟去哪個點更合適呢？d點說了，我到目標點的直線距離是4.5，出發點到我距離是2，近預估總距離只要6.5，選我選我~。a點輕蔑的一笑道：我到目標點的直線距離是4，出發點到我的距離只要1.5，近的預估總距離只要5.5。于是小藍立馬投向了a點的懷抱。
那么機智的小藍下一步該怎么走呢，小藍只能從a點出發，去往的目的地b點，掐指一算，已經走過的距離是3.5，到目標點的直線距離是2，總距離還是5.5。小藍輕輕瞟了一眼躲在角落懷揣6.5的d點，二話不說向b點奔去。
到了b點以后，抬頭一看，下面只有c點。到了c點以后，已經走過的距離變成了6.5，到目標點的直線距離是4，總距離一下子變成了10.5。于是小藍深情的看著d點已經它手中的6.5的牌牌，留下了悔恨的淚水。俗話說，浪子回頭金不換，d點也接受了小藍，讓他可以重新開始。
重新選擇了從d點出發的小藍，抬頭望向了e點。嗯很好，到e點實際距離也只有5，到目標點的直線距離是2，總距離也只有7。又回憶起c點的10.5的預估距離，小藍不禁一陣后怕。
到達e點，小藍便見到了金光閃閃的終點二字。這便結束了么？不，如今的小藍已經可以稱得上是一個江湖了，萬一后是一段望山跑死馬的遠路，豈不是得虧虧虧死…于是再次打起了自己的小算盤，e點到終點的距離是2，那么走過的總距離是7，掰掰手指頭就知道比途徑c點更近。于是小藍便方向大膽的邁向了終點，獲取了一條低代價的路徑。
這就是一次A*搜索的全部過程啦。為了加深大家的記憶，小藍決定再次祭出學習A*算法之*組圖，看看在棋盤格地圖中，小藍是如何進行A*路徑搜索滴。
進化算法
進化算法也是在人工智能領域中用于解決優化問題的一種準啟發式搜索算法。進化算法的思想參考了生物界的遺傳進化理論，讓達爾文爺爺的思想從豌豆領域出發，進軍計算機領域。簡單來說，進化算法將優化問題的解(特征值集合)表示為一個編碼串，稱為個體或者染色體，個體中的每一位，就叫做基因。那么很多個體就可以組成一個種群。為了避免局部，進化算法同樣借鑒了生物學中的遺傳/突變/自然選擇以及雜交等。
那么進化算法是如何為后路徑搜索服務的呢，小藍通過遺傳算法進行舉例說明，假設下圖中，小藍要從0點出發到15點。
那么首先要對該圖進行整理，也就是編碼過程，編碼表格如下所示：
然后檢查兩點之間是否可達，形成路徑連接表，如下表所示：
這樣就可以通過適應度函數進行路徑評估了，不可達的路徑的適應度為0。適應度函數表達如下所示：
這樣，通過添加隨機數，并加入首尾后，就能生成一群初始化群體了。生成初始化群體以后，小藍就萬事俱備，開始遺傳啦。遺傳過程如下圖所示，通過選擇，交叉和變異產生新的群體，然后按照適應度進行篩選，通過重采樣的方式留下適應度高的個體，進行下一輪的計算。
看到想加幾個就加幾個的基因，故而遺傳算法是可以同時對多個可行解進行搜索，且不容易陷入局部。同時還允許使用非常復雜的適應度函數，還能對變量的變化范圍加以限制。但是很遺憾的是，遺傳算法目前都還沒有一個很的數學解釋，所以遺傳算法還是非常考驗我們碼農的技術滴。
總結
到這里又要和大家說拜拜啦，通過介紹啟發式搜索中的A*算法和準啟發式搜索的遺傳進化算法后，想必大家對路徑搜索方法已經有所了解了。其實類似的方法很多，同樣方法的下變化也很多，在實際工程應用中要結合實際情況，進行靈活選擇和調整。這才是我們工程師存在的意義啊~