準(zhǔn)確高效 藍(lán)芯科技給您推薦路徑搜索

引言

正所謂在家靠父母，出門靠高德。在那錯(cuò)綜復(fù)雜的工廠里，我們的機(jī)器人哪怕視力驚人，也沒辦法一眼看到目的地。為了準(zhǔn)確又高效的把貨物送到目的地，小藍(lán)（杭州藍(lán)芯科技有限公司簡(jiǎn)稱）只能祭出殺招了，那就是----搜索算法。在路徑搜索問題中，搜索算法可以生成一個(gè)精確的優(yōu)解，按照搜索邏輯不同，可以分為深度優(yōu)先法和廣度優(yōu)先法。但是，在實(shí)際工程上會(huì)使用一些近似算法去解決路徑搜索問題，主要分為啟發(fā)式搜索的A*、D*、Focused D*算法和準(zhǔn)啟發(fā)式搜索的退火、進(jìn)化、蟻群優(yōu)化算法。本文通過介紹啟發(fā)式搜索的A*算法和準(zhǔn)啟發(fā)式搜索的遺傳進(jìn)化算法，讓大家感受這兩類算法的特色與魅力。

A*算法

A*算法作為經(jīng)典啟發(fā)式搜索算法，正廣泛運(yùn)用于智能機(jī)器人、無人駕駛等領(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)的代價(jià)估計(jì)，
g(n) 是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實(shí)際代價(jià)，
h(n) 是從狀態(tài)n到目標(biāo)狀態(tài)的低的估計(jì)代價(jià)。

那么什么是代價(jià)呢，為了便于理解，你可以直接認(rèn)為這里的代價(jià)就是距離。假設(shè)如圖1中場(chǎng)景，小藍(lán)要從出發(fā)點(diǎn)begin到目標(biāo)點(diǎn)end，該如何選擇路線呢？首先從出發(fā)點(diǎn)開始，可以選擇去a點(diǎn)，也可以選擇去d點(diǎn)。那么究竟去哪個(gè)點(diǎn)更合適呢？d點(diǎn)說了，我到目標(biāo)點(diǎn)的直線距離是4.5，出發(fā)點(diǎn)到我距離是2，近預(yù)估總距離只要6.5，選我選我~。a點(diǎn)輕蔑的一笑道：我到目標(biāo)點(diǎn)的直線距離是4，出發(fā)點(diǎn)到我的距離只要1.5，近的預(yù)估總距離只要5.5。于是小藍(lán)立馬投向了a點(diǎn)的懷抱。

那么機(jī)智的小藍(lán)下一步該怎么走呢，小藍(lán)只能從a點(diǎn)出發(fā)，去往*的目的地b點(diǎn)，掐指一算，已經(jīng)走過的距離是3.5，到目標(biāo)點(diǎn)的直線距離是2，總距離還是5.5。小藍(lán)輕輕瞟了一眼躲在角落懷揣6.5的d點(diǎn)，二話不說向b點(diǎn)奔去。

到了b點(diǎn)以后，抬頭一看，下面只有c點(diǎn)。到了c點(diǎn)以后，已經(jīng)走過的距離變成了6.5，到目標(biāo)點(diǎn)的直線距離是4，總距離一下子變成了10.5。于是小藍(lán)深情的看著d點(diǎn)已經(jīng)它手中的6.5的牌牌，留下了悔恨的淚水。俗話說，浪子回頭金不換，d點(diǎn)也接受了小藍(lán)，讓他可以重新開始。

重新選擇了從d點(diǎn)出發(fā)的小藍(lán)，抬頭望向了e點(diǎn)。嗯很好，到e點(diǎn)實(shí)際距離也只有5，到目標(biāo)點(diǎn)的直線距離是2，總距離也只有7。又回憶起c點(diǎn)的10.5的預(yù)估距離，小藍(lán)不禁一陣后怕。

到達(dá)e點(diǎn)，小藍(lán)便見到了金光閃閃的終點(diǎn)二字。這便結(jié)束了么？不，如今的小藍(lán)已經(jīng)可以稱得上是一個(gè)lao江湖了，萬一后是一段望山跑死馬的遠(yuǎn)路，豈不是得虧虧虧死…于是再次打起了自己的小算盤，e點(diǎn)到終點(diǎn)的距離是2，那么走過的總距離是7，掰掰手指頭就知道比途徑c點(diǎn)更近。于是小藍(lán)便方向大膽的邁向了終點(diǎn)，獲取了一條低代價(jià)的路徑。

這就是一次A*搜索的全部過程啦。為了加深大家的記憶，小藍(lán)決定再次祭出學(xué)習(xí)A*算法之*組圖，看看在棋盤格地圖中，小藍(lán)是如何進(jìn)行A*路徑搜索滴。

進(jìn)化算法

進(jìn)化算法也是在人工智能領(lǐng)域中用于解決優(yōu)化問題的一種準(zhǔn)啟發(fā)式搜索算法。進(jìn)化算法的思想?yún)⒖剂松锝绲倪z傳進(jìn)化理論，讓達(dá)爾文爺爺?shù)乃枷霃耐愣诡I(lǐng)域出發(fā)，進(jìn)軍計(jì)算機(jī)領(lǐng)域。簡(jiǎn)單來說，進(jìn)化算法將優(yōu)化問題的解（特征值集合）表示為一個(gè)編碼串，稱為個(gè)體或者染色體，個(gè)體中的每一位，就叫做基因。那么很多個(gè)體就可以組成一個(gè)種群。進(jìn)化算法同樣借鑒了生物學(xué)中的遺傳/突變/自然選擇以及雜交等。

那么進(jìn)化算法是如何為后路徑搜索服務(wù)的呢，小藍(lán)通過遺傳算法進(jìn)行舉例說明，假設(shè)下圖中，小藍(lán)要從0點(diǎn)出發(fā)到15點(diǎn)。
 

那么首先要對(duì)該圖進(jìn)行整理，也就是編碼過程，編碼表格如下所示：

然后檢查兩點(diǎn)之間是否可達(dá)，形成路徑連接表，如下表所示：

這樣就可以通過適應(yīng)度函數(shù)進(jìn)行路徑評(píng)估了，不可達(dá)的路徑的適應(yīng)度為0。適應(yīng)度函數(shù)表達(dá)如下所示：

這樣，通過添加隨機(jī)數(shù)，并加入首尾后，就能生成一群初始化群體了。生成初始化群體以后，小藍(lán)就萬事俱備，開始遺傳啦。遺傳過程如下圖所示，通過選擇，交叉和變異產(chǎn)生新的群體，然后按照適應(yīng)度進(jìn)行篩選，通過重采樣的方式留下適應(yīng)度高的個(gè)體，進(jìn)行下一輪的計(jì)算。

看到想加幾個(gè)就加幾個(gè)的基因，故而遺傳算法是可以同時(shí)對(duì)多個(gè)可行解進(jìn)行搜索。同時(shí)還允許使用非常復(fù)雜的適應(yīng)度函數(shù)，還能對(duì)變量的變化范圍加以限制。但是很遺憾的是，遺傳算法目前都還沒有一個(gè)很完美的數(shù)學(xué)解釋，所以遺傳算法還是非常考驗(yàn)我們碼農(nóng)的技術(shù)滴。

總結(jié)

到這里又要和大家說拜拜啦，通過介紹啟發(fā)式搜索中的A*算法和準(zhǔn)啟發(fā)式搜索的遺傳進(jìn)化算法后，想必大家對(duì)路徑搜索方法已經(jīng)有所了解了。其實(shí)類似的方法很多，同樣方法的下變化也很多，在實(shí)際工程應(yīng)用中要結(jié)合實(shí)際情況，進(jìn)行靈活選擇和調(diào)整。這才是我們工程師存在的意義啊~

本文屬于純?cè)瓌?chuàng)文章，轉(zhuǎn)載請(qǐng)注明杭州藍(lán)芯科技有限公司