劉婷婷 高 尚

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212003）

1 引言

無(wú)人駕駛汽車在某種性能參數(shù)的作用下，索引一條自起點(diǎn)至目標(biāo)終點(diǎn)的最優(yōu)級(jí)、次優(yōu)級(jí)無(wú)碰路徑，這種技術(shù)被人們稱作路徑規(guī)劃［1］。工作實(shí)踐中，單點(diǎn)搜索算法極易陷身局部最優(yōu)的狀況，禁忌搜索算法的出現(xiàn)，為求解車輛路徑問題提供了新的工具［1］。禁忌搜索算法簡(jiǎn)單易于理解，程序容易實(shí)現(xiàn)，運(yùn)行所需時(shí)間較短，禁忌表的約束使算法不易陷入局部極小，在無(wú)人駕駛汽車的路徑規(guī)劃技術(shù)中，這種算法已然引發(fā)了相關(guān)科研工作者地高度關(guān)注。本文針對(duì)現(xiàn)有研究中原禁忌搜索算法大多采用有向邊排列的解作為表示方法來(lái)構(gòu)造算法，這樣的解的表示不夠直觀，算法策略表現(xiàn)復(fù)雜使人難以理解，搜索效率低和收斂速度慢等缺點(diǎn)。提出了引入A*算法確定初始解的改進(jìn)措施，通過簡(jiǎn)化解的表示方法來(lái)提高其求解路徑規(guī)劃問題的全局尋優(yōu)能力。在柵格地圖法中，通過對(duì)其他智能算法的仿真實(shí)驗(yàn)表明，改進(jìn)的禁忌搜索算法全局尋優(yōu)能力提高，且具有更快的收斂速度和更高的尋優(yōu)精度。

2 禁忌搜索算法

2.1 禁忌搜索算法基本原理

禁忌搜索算法（Tabu Search，TS）技術(shù)是一種在局部鄰域搜索的基礎(chǔ)上進(jìn)行擴(kuò)展的亞啟發(fā)式搜索技術(shù)，是一種逐步尋優(yōu)算法［2］。局部鄰域搜索是在貪婪思想的基礎(chǔ)上，對(duì)當(dāng)前解的鄰域進(jìn)行搜索，這樣的搜索方式使得鄰域的結(jié)構(gòu)和初始解的選取決定了其性能的優(yōu)劣［3］，這樣的搜索結(jié)果容易陷入局部極小而無(wú)法保證全局最優(yōu)。而禁忌搜索算法李用一個(gè)禁忌表將已經(jīng)到達(dá)過的局部最優(yōu)點(diǎn)記錄下來(lái)，并在下一次搜索過程中有選擇的避免重復(fù)搜索這些點(diǎn)［4］，以此跳出局部最優(yōu)點(diǎn)［5］。這好比人類的短期記憶，人們不會(huì)重復(fù)或者有選擇的重復(fù)剛剛走過的路；同時(shí)“遺忘”又使這些禁止在一段時(shí)間后失效，最終達(dá)到全局優(yōu)化的目的［3］。

該算法可以簡(jiǎn)單地表示為

STEP1 選定一個(gè)初始解Xnow；令禁忌表H=ф；

STEP2 若滿足終止準(zhǔn)則，則中止計(jì)算；否則在Xnow的鄰域N（Xnow）中選出滿足禁忌要求的候選集Can-N（Xnow）；

STEP3 在Can-N（Xnow）中選定一個(gè)評(píng)價(jià)值最好的解Xbest，令Xnow=Xbest，更新禁忌表H，重復(fù)STEP2；

STEP4 輸出計(jì)算結(jié)果，停止。

2.2 禁忌搜索算法的改進(jìn)

禁忌搜索算法作為一種啟發(fā)式隨機(jī)搜索算法，確定初始解對(duì)算法的優(yōu)化至關(guān)重要。1968 年發(fā)明的A*算法就是把啟發(fā)式方法如BFS，和常規(guī)方法如Dijsktra 算法結(jié)合在一起的算法。A*算法計(jì)算敏捷，雖然無(wú)法保證尋求最佳路徑，A*卻一定能夠找到一條最短路徑［6］。以這樣的解作為初始解可以保證優(yōu)化算法的高效運(yùn)行。

假設(shè)：將局部范圍內(nèi)路面視為一個(gè)第一象限坐標(biāo)圖，已知單位長(zhǎng)度為1，以任意點(diǎn)為原點(diǎn)，車輛可向任意方向移動(dòng)，求網(wǎng)格中任意兩個(gè)給定坐標(biāo)之間的最短路徑。若將已知的坐標(biāo)距離改為路徑上的障礙物或其他代價(jià)參數(shù)，例如，路段擁擠、路面限行或者交通事故等因素及其組合，就相當(dāng)于求任意兩點(diǎn)之間繞過障礙物且有最短路程或最少等待的通路。

輸入：圖G=｛（x，y）|x＞0，y＞0｝有一個(gè)元定點(diǎn)s和會(huì)定點(diǎn)t，障礙物點(diǎn)B，以及每個(gè)相鄰單位之間路徑代價(jià)C。

輸出：G中從S到T的最短路徑的長(zhǎng)度。

初始化階段：

STEP 0：運(yùn)行A*算法得到一條最短路徑，設(shè)為初始解。元定點(diǎn)s標(biāo)記為永久標(biāo)記Y，對(duì)初始解路徑上點(diǎn)做臨時(shí)標(biāo)記L，令禁忌表為空。

搜索階段：

STEP 1：將與永久標(biāo)記Y 相鄰的5 個(gè)帶有臨時(shí)標(biāo)記L 的坐標(biāo)n，按f（n）=g（n）+h（n）做新的臨時(shí)標(biāo)記L。g（n）表示從帶有標(biāo)記Y 的點(diǎn)到任意點(diǎn)n 的代價(jià)，h（n）表示從點(diǎn)n 到路徑上與標(biāo)記Y間隔為5的會(huì)定點(diǎn)t的評(píng)估代價(jià)。

在柵格地圖中：

計(jì)算其最短距離，并將最小點(diǎn)標(biāo)記為永久坐標(biāo)Y。

STEP 2：更新禁忌表及當(dāng)前最優(yōu)解的記錄。

STEP 3：判斷f值是否為最小，且路徑不經(jīng)過障礙物，如果是，則f 值在沿著該路徑進(jìn)行時(shí)數(shù)值恒定。如果否，則將要進(jìn)行的路徑上的f 值均大于恒定f 值。若已經(jīng)具備最佳f值的結(jié)點(diǎn)，算法忽略f 值較高的節(jié)點(diǎn)的路徑，則刪除。重讀第2步和第3步，直到取得最優(yōu)解。

3 數(shù)值仿真與分析

3.1 環(huán)境建模

為了驗(yàn)證改進(jìn)后的算法是否在路徑規(guī)劃問題中得到有效應(yīng)用，本文采用對(duì)環(huán)境描述較為直接，且容易表示與修改的柵格地圖法。設(shè)計(jì)一個(gè)25×25 規(guī)模的二維柵格環(huán)境模型，每個(gè)柵格單元的大小為4m×4m，如圖1 所示，黑色區(qū)域代表的是未經(jīng)膨脹處理的障礙物，其余灰色區(qū)域表示沒有障礙。并將質(zhì)點(diǎn)以圈狀表示汽車的一定體積，保障規(guī)劃路徑與障礙物之間的安全距離。應(yīng)用改進(jìn)后的禁忌搜索算法完成從a 點(diǎn)到b 點(diǎn)的安全路徑規(guī)劃，同時(shí)還與初始解A*算法（如圖1）、人工魚群算法、蟻群算法以及粒子群算法的仿真結(jié)果進(jìn)行對(duì)比分析。

圖1 TS-P算法與初始解A*算法對(duì)比圖

3.2 初始參數(shù)設(shè)置

應(yīng)用經(jīng)驗(yàn)試錯(cuò)法，設(shè)置改進(jìn)禁忌搜索算法（TS-P）；蟻群優(yōu)化算法（ACO）的功能則是參考文獻(xiàn)編程實(shí)現(xiàn)［7］；粒子群優(yōu)化算法（PSO）的功能參考文獻(xiàn)實(shí)現(xiàn)［8］；魚群尋優(yōu)算法（AFSA）的功能則是參考文獻(xiàn)的內(nèi)容編程實(shí)現(xiàn)［9］。

3.3 有效性分析

仿真實(shí)驗(yàn)的軟件平臺(tái)是Matlab 2017，硬件平臺(tái)是Windows10的64位操作系統(tǒng)，2.53GHz的主頻，4G 的運(yùn)行內(nèi)存與Core i5 的處理芯片。各算法所規(guī)劃的路徑效果如圖2 中各曲線所示，并將各算法分別運(yùn)行32 次，統(tǒng)計(jì)各算法的平均路徑長(zhǎng)度（去掉最長(zhǎng)路徑與最短路徑）和平均耗時(shí)，結(jié)果如表1所示。

圖2 TS-P算法與其它算法對(duì)比圖

仿真結(jié)果顯示：A*算法運(yùn)算時(shí)間為0.076，求的距離為164m，采用優(yōu)化后的禁忌搜索算法，將A*得到的結(jié)果作為禁忌搜索的初始值，經(jīng)過10 次迭代，路徑距離為138.49m。其迭代過程如圖3 所示，改進(jìn)后的ST-P 算法經(jīng)過6 次迭代即可找到最短路徑，收斂速度非常快，尋優(yōu)性能極高。

圖3 TS-P算法迭代過程圖

由圖1、圖2以及表1可知，初始解A*算法和粒子群算法及魚群算法雖然較高的時(shí)效性，但其規(guī)劃出的路徑過于曲折并且路程較長(zhǎng)；而改進(jìn)后的禁忌搜索算法（TS-P）和魚群算法（AFSA）的路徑比較光滑且長(zhǎng)度短，兩種算法在時(shí)效性方面相差不大，但優(yōu)化后的TS 算法的路徑長(zhǎng)度方差明顯小于AFSA算法，說明優(yōu)化后的算法穩(wěn)定性好。

表1 各個(gè)算法計(jì)算結(jié)果統(tǒng)計(jì)表

4 結(jié)語(yǔ)

禁忌搜索算法是局部搜索算法的擴(kuò)展，其特點(diǎn)是采用了禁忌表來(lái)避免重復(fù)前面的工作。相較于其他群智能算法，禁忌搜索算法用一個(gè)禁忌表記錄下已經(jīng)到取得的最優(yōu)解，并且利用禁忌表中的信息必變重復(fù)搜索之前的點(diǎn)，簡(jiǎn)化計(jì)算。TS 算法原理簡(jiǎn)單，計(jì)算速度快，易于實(shí)現(xiàn)。本文針對(duì)原有算法在解決路徑規(guī)劃問題時(shí)采用的解的表示方法不夠直觀，算法策略表現(xiàn)復(fù)雜使人難以理解、計(jì)算難度大、收斂速度較慢等缺點(diǎn)，提出引入A*算法確定初始解的改進(jìn)措施，通過簡(jiǎn)化解的表示方法來(lái)提高其求解路徑規(guī)劃問題的全局尋優(yōu)能力。仿真實(shí)驗(yàn)表明，與參考文獻(xiàn)中其他智能算法相比，改進(jìn)后的TS算法在路徑規(guī)劃實(shí)例中計(jì)算速度和精度都有很大的提高，可用于解決汽車局部路徑規(guī)劃問題的實(shí)用高效的智能方法，本文算法有效、可行。