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