路徑規(guī)劃的主要算法與展望

1、路徑規(guī)劃的主要算法與展望摘要：路徑規(guī)劃算法是智能領(lǐng)域中一項(xiàng)新興的關(guān)鍵支撐技術(shù)；依據(jù)路徑規(guī)劃算法的實(shí)現(xiàn)原理，將其分為進(jìn)化型算法與非進(jìn)化型算法；再依據(jù)數(shù)學(xué)特征將非進(jìn)化型算法細(xì)分為經(jīng)典數(shù)學(xué)與幾何圖論兩類；針對(duì)每類算法，分別從發(fā)展背景、設(shè)計(jì)思想、優(yōu)缺點(diǎn)、改進(jìn)與發(fā)展等方面簡要?dú)w納分析；最后對(duì)路徑規(guī)劃算法的未來發(fā)展趨勢進(jìn)行展望。關(guān)鍵詞：路徑規(guī)劃; 進(jìn)化型算法; 非進(jìn)化型算法; 未來展望;Summary of Path Planning AlgorithmsLIANG Xiao-hui MU Yong-hui WU Bei-hua JIANG YuShijiazhuang Campus of Army En

2、gineering UniversityAbstract：Path planning algorithm is an emerging key supporting technology in the field of intelligence; According to the implementation principle of path planning algorithm, it is divided into evolutionary algorithm and non-evolutionary algorithm; Then based on the mathematical c

3、haracteristics, the non-evolutionary algorithm can be divided into two types: classical mathematics and geometric graph theory; For each type of algorithm, the paper will give a brief summary and analysis from some aspects: the background of development,design ideas, advantages and disadvantages, im

4、provement. Finally the future development trend of the path planning algorithm is forecasted.0 引言路徑規(guī)劃（Path Planning)1是智能技術(shù)中的熱點(diǎn)研究問題，已在多領(lǐng)域有所突破并成功得以應(yīng)用。在軍事領(lǐng)域涉及到的有無人機(jī)飛行路徑自動(dòng)規(guī)劃2，導(dǎo)彈回避威脅3，智能機(jī)器人控制4，水下無人航行器（Unmanned underwater vehicle UUV）的自主航行5以及美國國防高級(jí)研究計(jì)劃局小精靈;項(xiàng)目6等；在日常方面涉及的有基于地理信息系統(tǒng)（Geographic Information Sys

5、tem,GIS）的路徑規(guī)劃7，城市智能交通動(dòng)態(tài)路徑規(guī)劃8，物流或外賣配送9以及自動(dòng)導(dǎo)引裝置（Automated Guided Vehicle,AGV）的路徑規(guī)劃與調(diào)度10等。11路徑規(guī)劃的實(shí)現(xiàn)主要依靠高級(jí)語言編制出的算法，其主要包含：模擬退火法，A*算法，Dijkstra算法，遺傳算法，粒子束算法，人工勢場法，Voronoi法等。少部分路徑規(guī)劃也可通過硬件加以改善，例如可以使用微電子器件或光學(xué)器件解決路徑規(guī)劃在實(shí)時(shí)系統(tǒng)中速度慢的缺陷12。1 路徑規(guī)劃算法依據(jù)算法實(shí)現(xiàn)原理，可將路徑規(guī)劃算法歸類為非進(jìn)化型與進(jìn)化型兩種。1.1 非進(jìn)化型算法非進(jìn)化型算法具有簡潔的設(shè)計(jì)思想流程和較高效率的處理能力。但在

6、機(jī)械式;解決路徑規(guī)劃問題時(shí)，不易產(chǎn)生最優(yōu)路徑，且無法在過程中實(shí)現(xiàn)自我學(xué)習(xí)和自我完善，不具備記憶能力。在處理高維空間形式下的路徑規(guī)劃問題時(shí)，結(jié)果與期望有較大偏差。依據(jù)算法數(shù)學(xué)特征，可將非進(jìn)化型算法分成經(jīng)典數(shù)學(xué)與幾何圖論兩類型。1.1.1 經(jīng)典數(shù)學(xué)(1)圖搜索概率法。20世紀(jì)90年代初期，M.H.Overmars提出PRM(Probabilistic Roadmaps Method）圖搜索概率法13,14。PRM主要包含離線學(xué)習(xí)階段和在線學(xué)習(xí)階段，依據(jù)搜索算法在終始點(diǎn)之間的優(yōu)化規(guī)則形成路標(biāo)圖，并在一定條件的約束下有效的解決在多維空間和復(fù)雜環(huán)境中的路徑規(guī)劃問題。PRM圖搜索概率法的尋徑方式簡便，整個(gè)

7、規(guī)劃場景的大小與構(gòu)形空間的多維性沒有特別強(qiáng)烈的關(guān)系，因此復(fù)雜度較低，不需要精確建模。但由于所采集樣點(diǎn)隨機(jī)分布，無法覆蓋自由空間中的全部路徑，易出現(xiàn)搜索路徑不是所需的最優(yōu)路徑，同時(shí)在規(guī)劃路徑時(shí)遇到狹窄通路或是復(fù)雜度較高的障礙集合時(shí)，算法效率就會(huì)顯得十分低下。在對(duì)PRM的改進(jìn)中，夏炎等人通過節(jié)點(diǎn)增強(qiáng)法將原路徑上的節(jié)點(diǎn)代替，利用圓弧替代路徑上的折線，達(dá)到減小節(jié)點(diǎn)拐點(diǎn)個(gè)數(shù)，縮短規(guī)劃路徑長度，并實(shí)現(xiàn)搜索路徑有較高的平滑度15。G.Sanchez等人在PRM的基礎(chǔ)上提出了SBL-PRM算法，即通過從兩個(gè)基本位姿點(diǎn)出發(fā)，找到路徑后再經(jīng)過碰撞檢測等手段使得計(jì)算更加實(shí)時(shí)高效16,17。(2)模擬退火算法。195

8、3年，N.Metropolis等人將模擬退火算法SA的思想提出。它通過模擬熱力學(xué)中固體物質(zhì)的退火過程與一般組合優(yōu)化問題之間的相似性并結(jié)合概率突跳特性，使得局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)的模式。模擬退火法在算法實(shí)行中需要一個(gè)輸入作為初始解，在求解的過程中對(duì)于壞解具有包容性，不會(huì)局限于初始解所在的收斂域內(nèi)。模擬退火在計(jì)算中可跳出局部極小值點(diǎn)，造成了所獲得的解不一定是最優(yōu)解，卻一定是全局的次優(yōu)解，不可避免地使算法整體受參數(shù)影響，導(dǎo)致全局搜索能力變差18。1985年，多目標(biāo)模擬退火算法MOSA被Ulungu提出，解決傳統(tǒng)的SA算法只針對(duì)單個(gè)目標(biāo)求解并表現(xiàn)出了良好的性能19。2011年，Sa

9、nkaraoB等人提出了一種具有魯棒性的多目標(biāo)退火算法r MOSA，能夠在較少的模擬次數(shù)下熟練到Pareto解集，使得在MOSA算法的基礎(chǔ)上實(shí)施擾動(dòng)選擇新解，從而具有魯棒性20。2005年，田東平等人將適合全局搜索的遺傳算法（GA）和適合局部搜索的模擬退火算法（SA）相結(jié)合，提出了混合GA-SA計(jì)算方法，有效提高了收斂速度，并有效防止種群早熟現(xiàn)象，且驗(yàn)證了該算法的可行性和有效性21。(3)人工勢場法。1986年，人工勢場法由Khatib博士22提出。它是一種虛擬力法，通過在目標(biāo)位置與障礙物周圍構(gòu)造出起共同作用的引力場與斥力場，再通過搜索勢函數(shù)的下降方向來規(guī)劃出無碰的最優(yōu)路徑，整個(gè)勢場力正是由引

10、力部分和斥力部分組成23。由于人工勢場法高效的實(shí)時(shí)控制性，可以實(shí)現(xiàn)實(shí)時(shí)路徑規(guī)劃和平滑軌跡處理，因而也得到了廣泛應(yīng)用。但是當(dāng)在勢場空間中同時(shí)出現(xiàn)多個(gè)障礙物時(shí)，易出現(xiàn)零勢能點(diǎn)，使勢能法陷入局部最小點(diǎn)，造成混亂，無法完成勢場空間中的路徑規(guī)劃任務(wù)24。很多學(xué)者針對(duì)勢場原理的幾個(gè)缺點(diǎn)進(jìn)行了改進(jìn)，使其具備學(xué)習(xí)能力，從而可以適應(yīng)未知復(fù)雜環(huán)境或者能在多障礙物情況下消除零勢能25。日本的Ya-Chun chang等人結(jié)合人工勢場法和Voronoi圖表法提出了一種混合的路徑規(guī)劃算法，在此計(jì)算中分別利用了兩種方法的優(yōu)點(diǎn)同時(shí)解決勢場信息構(gòu)造最優(yōu)路徑的選擇26。喬莎莎等人對(duì)于遺傳算法與人工勢場法進(jìn)行結(jié)合仿真，有效避免基

11、于行為的盲目性，增加了路徑節(jié)點(diǎn)和平滑度，但對(duì)于全局規(guī)劃帶來的問題把握不夠27。(4)A*算法。1968年，A*算法由Stanford研究院的Peter Hart等人共同發(fā)表，是一種常用的路徑查找和圖形遍歷算法。它通過尋找最小路徑來估算節(jié)點(diǎn)的代價(jià)評(píng)估函數(shù)并作為節(jié)點(diǎn)的綜合優(yōu)先級(jí)，當(dāng)選擇下一個(gè)需要遍歷的節(jié)點(diǎn)時(shí)，再選取綜合優(yōu)先級(jí)最高的節(jié)點(diǎn)一步步地找到最優(yōu)路徑。A*算法的一般過程可在文獻(xiàn)中查到28。A*算法可以方便的找到開銷最小，路程最短的路徑，但是隨著數(shù)據(jù)量的增大，無用節(jié)點(diǎn)會(huì)導(dǎo)致A*算法搜索時(shí)間增長，同時(shí)也可以通過調(diào)節(jié)啟發(fā)函數(shù)來控制算法的速度和精確度。Szczerba等人提出了稀疏A*搜索算法（SAS

12、），通過將約束條件與搜索算法結(jié)合起來，可有效剪裁搜索空間29。高蝦蝦等人通過搜索節(jié)點(diǎn)進(jìn)行優(yōu)化，解決了二維航線中存在的局限性問題，減少運(yùn)行時(shí)間和消耗內(nèi)存30。占偉偉等人也提出一種改進(jìn)的A*算法解決大范圍三維戰(zhàn)場環(huán)境的無人機(jī)航跡規(guī)劃問題，但是由于戰(zhàn)場環(huán)境動(dòng)態(tài)變化，無法達(dá)到實(shí)時(shí)航跡規(guī)劃。(5)Dijkstra算法。1959年，Dijkstra算法由荷蘭科學(xué)家Edsger W.Dijkstra提出31。該算法是單源路徑算法，用來求解一個(gè)頂點(diǎn)到其余各項(xiàng)頂點(diǎn)的最短路徑問題，它通過起始點(diǎn)為中心向外層層擴(kuò)展，直至擴(kuò)展到終點(diǎn)為止得到最短路徑。Dijkstra算法十分簡潔，能夠有效的找到最優(yōu)解，不足之處在數(shù)據(jù)節(jié)點(diǎn)

13、龐大時(shí)所需的節(jié)點(diǎn)繁多，效率隨著數(shù)據(jù)節(jié)點(diǎn)的增加而下降，耗費(fèi)大量內(nèi)存空間與計(jì)算時(shí)間。侯莉莉等人以鄰接鏈表和最小二叉堆的數(shù)據(jù)結(jié)構(gòu)優(yōu)化了Dijkstra算法，改進(jìn)后的算法運(yùn)行時(shí)間有所減少，效率有所提高32；何少佳等利用Dijkstra算法的優(yōu)點(diǎn)與蟻群算法進(jìn)行改進(jìn)，有效提高了搜索效率，縮短路徑長度，改善搜索路徑質(zhì)量33,34。(6)Floyd算法。1978年，F(xiàn)loyd算法由圖靈獎(jiǎng)獲得者教授Robert W.Floyd命名，通過分析有權(quán)圖的帶權(quán)鄰接矩陣，而后在矩陣中求任意兩點(diǎn)的最短路徑11。Floyd算法適用于任意兩點(diǎn)間的最短路徑，同時(shí)也被經(jīng)常用于計(jì)算有向圖的傳遞閉包，規(guī)劃效率要高于Dijkstra算法

14、，但其復(fù)雜度達(dá)到了三次方的級(jí)別，不能直觀反映出各個(gè)頂點(diǎn)之間最短路徑序列的先后關(guān)系。為了提高查找效率，減少頂點(diǎn)之間長度比較，代修宇等人對(duì)傳統(tǒng)的Floyd算法進(jìn)行了優(yōu)化改進(jìn)35；王靖東通過對(duì)頂點(diǎn)過濾，頂點(diǎn)計(jì)算優(yōu)化和反比例優(yōu)化來提高路徑規(guī)劃成功率和效率36。程曉蓉等結(jié)合Dijkstra算法和Floyd算法的優(yōu)點(diǎn)，提出了一種新的求最短路徑的優(yōu)化算法F.D算法，并將這種更高效、快捷的方法應(yīng)用于求解基于GIS的電力通信路線最短路徑問題上。1.1.2 幾何圖論(1)Voronoi圖算法。1908年，俄國數(shù)學(xué)家Georgy Fedoseevich提出Voronoi圖算法。這種空間分割算法的靈感來源于笛卡爾的凸

15、域分割空間的思想，是計(jì)算幾何中的一個(gè)重要分支，對(duì)于路徑規(guī)劃的輔助性意義很大。Voronoi圖目前的生成算法主要有兩大類：矢量法和柵格法37。2007年，Bhattacharya P等人提出了一種基于Voronoi圖解障礙是簡單多邊形的最短路徑問題提供了詳細(xì)算法的描述，及Voronoi圖算法的維護(hù)和動(dòng)態(tài)的更新，該方法性能優(yōu)于其他有關(guān)路徑規(guī)劃算法38;2010年，徐鵬飛等人利用半平面與Voronoi頂點(diǎn)的位置關(guān)系，提出了簡單增量構(gòu)造Voronoi圖的算法，此算法在處理Voronoi邊與節(jié)點(diǎn)的特殊情況，并且該算法的平均時(shí)間復(fù)雜度接近線性39。(2)矢量法。矢量法包括以下幾種經(jīng)典型算法：分治法、增量法

16、、和間接法-Delaunay三角網(wǎng)法。矢量法提高了運(yùn)算的復(fù)雜程度，縮短了運(yùn)算時(shí)間，不影響全局空間的分割，具有精度高，效率高的特性，但是也造成生成圖像的精準(zhǔn)度不夠，儲(chǔ)存結(jié)構(gòu)也相對(duì)復(fù)雜37。在Voronoi圖的發(fā)展歷程中，矢量法的出現(xiàn)要早于柵格法。1975年，謝姆斯等人提出的采用分治法構(gòu)造平面點(diǎn)集Voronoi圖算法40;1993年，Barry J等人把線狀障礙物的VSP-VD和Delaunay三角網(wǎng)分別定義為有限制的Voronoi圖和有限制的Delaunay三角網(wǎng)41。(3)柵格法。1968年，柵格法由W.E.Howden提出，它將路徑規(guī)劃所占用的環(huán)境分解成具有二值信息的網(wǎng)絡(luò)單元42。這種方法的

17、特點(diǎn)是簡單、易于實(shí)現(xiàn)，它同時(shí)具有表達(dá)不規(guī)則障礙物的能力。其缺點(diǎn)是表示效率不高，存在著時(shí)空開銷與求解精度之間的矛盾。路徑規(guī)劃時(shí)柵格法多以環(huán)境建模形式存在，采以柵格（grid）來表示環(huán)境信息，以此避免復(fù)雜的計(jì)算。單位柵格越小，障礙物的表示越精確，但也會(huì)浪費(fèi)大量的存儲(chǔ)空間，搜索的范圍會(huì)以指數(shù)的形式激增。單位柵格過大，由算法規(guī)劃的路徑會(huì)變得很不精確。43目前基于對(duì)柵格法改進(jìn)方案多是通過與其它算法的復(fù)合。2009年，雷艷敏等提出通過對(duì)柵格屬性的設(shè)置來彌補(bǔ)勢場法和柵格法的缺點(diǎn)，仿真結(jié)果表明該方法是可行有效的44;2007年，鄭秀敏等提出將柵格法與模擬退火法進(jìn)行結(jié)合，采用柵格法表示環(huán)境信息，模擬退火法來進(jìn)行

18、局部的路徑規(guī)劃成功提高了路徑規(guī)劃的效率，增強(qiáng)了可靠性45。1.2 進(jìn)化型算法進(jìn)化型算法可以理解成智能算法，是人們受自然（生物界）規(guī)律得到的啟迪而模仿出的算法，具有一定的自我學(xué)習(xí)，自我更新和記憶能力。對(duì)問題的解決方式較為復(fù)雜，能夠處理復(fù)雜的路徑規(guī)劃問題，但是在龐大的計(jì)算量下易造成效率低下，無法高效的完成實(shí)時(shí)控制。1.2.1 禁忌搜索法1986年，禁忌搜索算法（Tabu Search,TS）由Glover教授正式提出，是一種亞啟發(fā)式（meta-henristic）的搜索算法46,47,48。TS通過引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和與之對(duì)應(yīng)的禁忌準(zhǔn)則，并通過藐視準(zhǔn)則赦免一些被禁忌的優(yōu)良狀態(tài)，借此保證多樣化的

19、有效搜索來實(shí)現(xiàn)最終的全局優(yōu)化。其最主要的特點(diǎn)就是采用了禁忌技術(shù)和特赦規(guī)則，使得算法可以跳出局部最優(yōu)解，進(jìn)行有效的計(jì)算，最終實(shí)現(xiàn)全局的優(yōu)化49。禁忌搜索算法易于實(shí)現(xiàn)，通用性及局部開發(fā)能力較強(qiáng)，收斂速度快，但全局開發(fā)能力相對(duì)較弱，搜索結(jié)果完全依賴于初始解和領(lǐng)域的映射關(guān)系?；旌纤惴ǖ某霈F(xiàn)，尤其是遺傳算法和模擬退火算法的有效結(jié)合對(duì)于算法性能和效率有較大幅度的改善50,51,52,53。2012年，王超利用禁忌搜索算法和遺傳算法的特點(diǎn)將二者結(jié)合，得到較強(qiáng)的全局搜索能力和局部搜索能力的混合算法54;2010年，蘭任55在其論文中利用粒子群PSO算法前期收斂速度快和TS的優(yōu)點(diǎn)對(duì)蛋白質(zhì)結(jié)構(gòu)進(jìn)行預(yù)測，通過對(duì)結(jié)果

20、的分析驗(yàn)證了混合型算法的優(yōu)越性。1.2.2 神經(jīng)網(wǎng)絡(luò)算法神經(jīng)網(wǎng)絡(luò)算法（Neural Network）是一種以人腦的神經(jīng)網(wǎng)絡(luò)作為啟發(fā)，通過簡化，抽象與模擬人腦存儲(chǔ)和處理信息的過程并用數(shù)學(xué)語言加以描述而衍生出來的智能化信息處理技術(shù)56。根據(jù)學(xué)習(xí)算法與網(wǎng)絡(luò)結(jié)構(gòu)兩個(gè)方面相結(jié)合的角度來對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行分類57，有以下幾個(gè)類別，單層前向網(wǎng)絡(luò)，多層前向網(wǎng)絡(luò)，反饋神經(jīng)網(wǎng)絡(luò)，隨機(jī)神經(jīng)網(wǎng)絡(luò)和競爭神經(jīng)網(wǎng)絡(luò)等。神經(jīng)網(wǎng)絡(luò)算法具有自學(xué)習(xí)，聯(lián)想存儲(chǔ)，具備高速尋找最優(yōu)解的能力，但是算法的網(wǎng)絡(luò)參數(shù)較多，屬于黑盒狀態(tài)，不可觀察結(jié)果，學(xué)習(xí)時(shí)間較長，容易陷入局部最小值。BP(Back Propagation）算法是人工神經(jīng)網(wǎng)絡(luò)中研究最

21、為成熟，應(yīng)用也是最為廣泛的人工神經(jīng)網(wǎng)絡(luò)模型之一58，它由Rumelhart等人在1986年提出，按照誤差逆向傳播算法訓(xùn)練的多層前饋神經(jīng)網(wǎng)絡(luò)，其結(jié)構(gòu)簡單，可塑性強(qiáng)，具有自我學(xué)習(xí)的特性，但是學(xué)習(xí)速率固定，不儲(chǔ)存學(xué)習(xí)過程中的參數(shù)，因此無記憶能力59。神經(jīng)網(wǎng)絡(luò)算法與其它算法的有機(jī)結(jié)合是目前改進(jìn)劣勢的重要方式。2016年，王和杰提出用遺傳算法來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)，改善初始值和閾值，可充分發(fā)揮BP神經(jīng)網(wǎng)絡(luò)的局部搜索能力，提高算法穩(wěn)定性，避免陷入局部最優(yōu)值60。2017年，劉品提出采用高階神經(jīng)網(wǎng)絡(luò)對(duì)BP網(wǎng)絡(luò)模型結(jié)構(gòu)進(jìn)行優(yōu)化，能夠產(chǎn)生更好的擬合，可以解決高度復(fù)雜問題61。1.2.3 蟻群算法二十世紀(jì)九十年代，意

22、大利學(xué)者Dorigo Mden通過模擬螞蟻的行為規(guī)律，以螞蟻在自然界中協(xié)同工作尋找食物為數(shù)學(xué)模型提出了蟻群算法（Ant Colony Optimization），這是一種貪婪啟發(fā)式的搜索算法。傳統(tǒng)蟻群算法具有正反饋機(jī)制，加強(qiáng)了算法的尋優(yōu)能力，個(gè)體與個(gè)體建立的信息共享，互相合作，促進(jìn)該算法能夠搜索到最優(yōu)解。蟻群算法易于與其他算法結(jié)合使用，擁有更強(qiáng)大的搜索能力。但是無法實(shí)現(xiàn)實(shí)時(shí)在線搜索，尤其是面對(duì)空間較大，不易在有限時(shí)間內(nèi)找到最優(yōu)解，且其易陷入局部最優(yōu)的局面。Gambardella等人在1995年提出Ant-Q蟻群算法，此算法通過最優(yōu)信息的反饋，以較大的概率選擇信息素強(qiáng)度最大的路徑62;Stutz

23、le and Hoos在1997年改進(jìn)擴(kuò)展了蟻群算法的全局搜索范圍，減小了算法陷入局部最優(yōu)導(dǎo)致早熟現(xiàn)象發(fā)生的幾率63；徐精明等人首次提出了多態(tài)蟻群算法，對(duì)人工蟻進(jìn)行合理分工，結(jié)合局部與全局搜索，加快了算法收斂速度64;2013年，李擎等人提出了粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法，通過全局異步和精英策略成功減少粒子群算法調(diào)用蟻群算法的迭代次數(shù)65。1.2.4 遺傳算法1962年，遺傳算法被John Holland66提出。它是模擬生物進(jìn)化論中的自然選擇和遺傳變異為基礎(chǔ)理論而形成的一種搜索算法。遺傳算法具有自組織，自適應(yīng)和自學(xué)習(xí)性，能夠同時(shí)處理多個(gè)群體中的多個(gè)個(gè)體，從串集進(jìn)行搜索，覆蓋面大，有利于全局搜

24、索。但是其屬于隨機(jī)類算法，結(jié)果的可靠性較差，不能穩(wěn)定的得到最優(yōu)解。王璇通過將遺傳算法與粒子群算法和人工免疫算法相結(jié)合形成混合遺傳算法，有效提高收斂速度，且使算法不易陷入局部最優(yōu)值，并使用測試函數(shù)驗(yàn)證了算法收斂的有效性67。在文獻(xiàn)68中提出了量子遺傳算法，它是對(duì)量子計(jì)算和遺傳算法相結(jié)合的產(chǎn)物，使得算法的適應(yīng)性更強(qiáng)，效率更高；2016年，田欣提出新的自適應(yīng)調(diào)整方式，提高了遺傳算法的尋優(yōu)效率，并通過引入模擬退火算法克服遺傳算法有容易陷入局部最優(yōu)的缺點(diǎn)69。1.2.5 粒子群算法1995年，Eberhart等人提出PSO算法70。它是通過模擬鳥群的生存行為提出的一種新型群智能優(yōu)化算法，兼有進(jìn)化計(jì)算和群

25、智能的特點(diǎn)來實(shí)現(xiàn)復(fù)雜空間中最優(yōu)解的搜索。PSO算法在初始時(shí)并非十分完善，在實(shí)際的應(yīng)用時(shí)往往出現(xiàn)早熟收斂和全局收斂性能差等缺點(diǎn)。PSO在離散域問題特別是組合優(yōu)化問題的求解研究還比較少，這方面領(lǐng)域的研究被稱為離散PSO。1997年，J.Kennedy等人71提出了粒子群算法的離散二進(jìn)制版本，將經(jīng)過簡單的修改，使其應(yīng)用于搜索二進(jìn)制的空間。XiaoFeng Xie等人提出的自組織耗散PSO算法，從熱力學(xué)的角度指出PSO的社會(huì)模型具有自組織耗散結(jié)構(gòu)的特點(diǎn)，進(jìn)而引入了混亂算子，避免了群體過早的進(jìn)入穩(wěn)定狀態(tài)72。2 未來展望路徑規(guī)劃算法目前多處于理論研究，試驗(yàn)或試運(yùn)行階段，應(yīng)用到實(shí)際層面仍需要一段時(shí)間。同其

26、它技術(shù)理論一樣，路徑規(guī)劃算法的產(chǎn)生與發(fā)展主要來自社會(huì)進(jìn)步和軍事需求，同時(shí)也受已有技術(shù)的限制。針對(duì)軍事領(lǐng)域或智能控制領(lǐng)域出現(xiàn)的復(fù)雜問題，單一算法顯然無法高效解決。這就需要多學(xué)科知識(shí)的交叉融合，將具有不同優(yōu)勢的算法有效結(jié)合成更加高效的復(fù)合型路徑規(guī)劃算法，這也是目前主流的研究方向。由于非進(jìn)化類算法具有運(yùn)算量小、可實(shí)現(xiàn)性較強(qiáng)的優(yōu)勢，依舊占據(jù)著一定的生存空間。但隨硬件成本的降低，運(yùn)算能力水平不斷提升，具備人工智能的進(jìn)化類算法必將成為該領(lǐng)域的核心。未來很大概率會(huì)有更高效、實(shí)時(shí)、精確處理路徑規(guī)劃問題的新算法誕生，使得軍事武器和生產(chǎn)生活智能化的前景更加廣闊。參考文獻(xiàn)1謝娟.路徑規(guī)劃算法的研究及應(yīng)用D.電子科技

27、大學(xué)，2015,03.2馬傳焱多無人機(jī)飛行路徑自動(dòng)規(guī)劃算法研究J無線電工程，2015,45(2):5-7,33.3馬云紅，周德云一種簡單快速的導(dǎo)彈路徑規(guī)劃方法J導(dǎo)彈與制導(dǎo)學(xué)報(bào)，2005,25(3):23-26.4張佳，陳杰，竇麗華基于路徑規(guī)劃的智能機(jī)器人控制實(shí)驗(yàn)J實(shí)驗(yàn)技術(shù)與管理，2010,27(12):44-47.5溫志文，蔡衛(wèi)軍，楊春武UUV自主航行路徑規(guī)劃方法J制造業(yè)自動(dòng)化，2016,38(11):1-5.6袁成美國國防高級(jí)研究計(jì)劃局小精靈;項(xiàng)目J兵器知識(shí)，2016,9:37-39.7孫蘭會(huì)，成鋒，陸愈實(shí)基于GIS的路徑規(guī)劃算法研究與實(shí)現(xiàn)J現(xiàn)代電子技術(shù)，2016,39(5):101-109

28、.8 李軍.城市智能交通中的動(dòng)態(tài)路徑規(guī)劃研究D.杭州電子科技大學(xué)，2017,04.9 高小芳.物流配送最優(yōu)路徑規(guī)劃D.華僑大學(xué)，2017,02.10 劉維民AGV路徑規(guī)劃與調(diào)度系統(tǒng)研究D.華南理工大學(xué)，2017,02.11張廣林，胡小梅，柴劍飛，趙磊，俞濤路徑規(guī)劃算法及其應(yīng)用綜述J現(xiàn)代機(jī)械，2011,5:85-90.12曾慶立，李麗華，唐圣學(xué)基于神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃的硬件設(shè)計(jì)J吉首大學(xué)學(xué)報(bào)（自然科學(xué)版），2007,28(6):74-76.13 L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H.Overmars. Probabilistic roa

29、dmaps for path planning in highdimensional configuration spacesJ. IEEE Transactions on Robotics and Automation, 1996,12(4):566-580.14 Kavrak i L, Svestka P, Latombe J C, et al. Probabilistic Road Maps for Path Planning in High-dimensional ConfigurationSpacesJ. IEEE Transactions on Robotics and Autom

30、ation,1996,12(4):566-580.15夏炎，隋巖.PRM路徑規(guī)劃算法優(yōu)化研究J.應(yīng)用科技，2010,37(10):1-5.16 Sanchez G.,Latombe J. C. Single-Query Bi-Directional Motion Planning with lazy Collision CheckingC. International Symposium on Robotics Research, Lorne, Australia, 2001.17 Sanchez G., Latombe J. C. On Delaying Collision Checking

31、 in PRM Planning Application to Multi-Robot CoordinationC.International Journal of Robotics Research, 2002, 21(1):5-26.18 鄭秀敏，顧大鵬，劉相術(shù).基于柵格法-模擬退火算法的機(jī)器人路徑規(guī)劃J.機(jī)器人技術(shù)，1008-0570(2007)02-2-0247-02.19楊理云.用模擬退火算法求解旅行商問題J.微電子學(xué)與計(jì)算機(jī)，2007(05):193-196.20 卜文浩.模擬退火算法綜述D.西安理工大學(xué)，2007,08.21田東平，遲洪欽.混合遺傳算法和模擬退火法J.計(jì)算機(jī)工程與

32、應(yīng)用，2006(22):63-65.22 Khatib O.Realtime Abstract Avoidance for Manipulators,and Mobile Robots in ProeJ.IEEE Int Conf.On.Robotics and Automation March 25-381985.500-505,also in Int JRobot Res,1986,5(1):90-98.23王肖青，王奇志.傳統(tǒng)人工勢場的改進(jìn)J.計(jì)算機(jī)技術(shù)與發(fā)展，1005-3751(2006)04-0096-03.24王奇志.基于改進(jìn)人工勢場法的多障礙機(jī)器人運(yùn)動(dòng)控制C.北京：2003年中國

33、智能自動(dòng)化會(huì)議論文論文集（上冊(cè)）.25許亞.基于改進(jìn)的人工勢能場的移動(dòng)機(jī)器人的路徑規(guī)劃研究J.科技展望，2016(33).26Chang Y-C,Yamamoto Y.Pathplanning of whelled mobile robot with simultaneous free space locating capability,Intelligent Service Robotics,2009,2(1):19-22.27喬莎莎，吳勇，張建東，史國慶.基于遺傳算法和人工勢場法的路徑規(guī)劃J.現(xiàn)代電子技術(shù)，2012,35:75-78.28熊壬浩，劉羽.A*算法的改進(jìn)及并行化J.計(jì)算機(jī)應(yīng)用，

34、2015,35(7):1843-1848.29 NILSSON N.Problem-solving methods in artificial intelligenceM.IEEE Transactions on Aerospace and Electronic System,2000,36(3):869-878.30高蝦蝦，郭國龍，徐成華，馮蓉.基于改進(jìn)A*算法的三維飛行航線規(guī)劃.第三屆高分辨率對(duì)地觀測學(xué)術(shù)年會(huì)論文集C.2014,12.31Dijkstra E. A note on two problems in connexi on with graphsJ.Numerische Math

35、ematik,1951,1(1):269-271.32趙磊，侯莉莉.一種Dijkstra算法的優(yōu)化實(shí)現(xiàn)算法-學(xué)術(shù)研究，2014.33何少佳，史劍清，王海坤.基于改進(jìn)蟻群粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃J.桂林理工大學(xué)學(xué)報(bào)，2014,34(4):765-770.34王輝，朱龍彪，王景良，陳紅艷，邵小江，朱志慧.基于Dijkstra-蟻群算法的泊車系統(tǒng)路徑規(guī)劃研究J.工程設(shè)計(jì)學(xué)報(bào)，2016,05.35代修宇，程國忠.Floyd算法的改進(jìn)與優(yōu)化J.西昌學(xué)院學(xué)報(bào)·自然科學(xué)版，2012,03:63-65.36王靖東，楊凌.基于優(yōu)化Floyd算法的室內(nèi)機(jī)器人路徑規(guī)劃研究D.西北農(nóng)林科技大學(xué)，2

36、015.37 徐政超.基于voronoi圖算法的航路規(guī)劃方法研究D.長安大學(xué)，2015.38 BHATTACHARYA, GAVRILOVA M L. Voronoi Diagrami n Optimal Path PlanningC. The 4th Int-ernational Symposium on Voronoi Diagrams in Science and Engineering, 2007:38-47.39徐鵬飛，陳志剛.增量構(gòu)造Voronoi區(qū)域的改進(jìn)算法J.計(jì)算機(jī)工程與應(yīng)用，2010,46(8):8-10.40 SHAMOS M I, HOEY D. Closest Poi

37、nt ProblemsC. In Proceedings of 16th IEEE Symposium on Foundations of Computer Science, 1975:151-162.41BARRY J, WANG C A. Duality of Constrained Voronoi Diagrams and Delaunay TriangulationsJ. Algorithmica, 1999, 9(2):142-155.42 徐鵬.基于模擬退火算法的機(jī)器人路徑規(guī)劃與研究J.信息與通信，1671-4792-(2011)1-0042-03.43 鄭秀敏，顧大鵬，劉相術(shù).基

38、于柵格法-模擬退火算法的機(jī)器人路徑規(guī)劃J.機(jī)器人技術(shù)，1008-0570(2007)02-2-0247-02.44雷艷敏，馮志彬.改進(jìn)的勢場柵格法在機(jī)器人路徑規(guī)劃中的應(yīng)用J.長春大學(xué)學(xué)報(bào)，2009,19(1):38-42.45 鄭秀敏，顧大鵬，劉相術(shù).基于柵格法-模擬退火法的機(jī)器人路徑規(guī)劃J.機(jī)器人技術(shù)，1008-0570(2007)02-2-0247-02.46 Glover F.and M. Tabu Search. Boston, Kluwer Academic Publishers,1997.47邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法M.清華大學(xué)出版社，2005:51-68.48王凌.智能優(yōu)

39、化算法及其應(yīng)用M.清華大學(xué)出版社，2001.49王玉晶.基于禁忌搜索算法的生理信號(hào)情感識(shí)別研究D.西南大學(xué)，2008,05.50J.A. Hageman et. al.,Hybrid genetic algorithm-tabu search approach for optimising multilayer optical coatings,Analytica Chimica Acta, 490, 2003,211-222.51柯坷，張世英.禁忌一遞階遺傳算法研究J.控制與決策，2001,16(4):480-483.52孫艷豐，鄭加齊.GATS混合算法及其收斂性研究J.鐵道學(xué)報(bào)，22(2)

40、:94-98.53李大衛(wèi)，王莉，王夢(mèng)光.遺傳算法與禁忌搜索算法的混合策略J.系統(tǒng)工程學(xué)報(bào)，1998,13(3):28-34.54王超.基于混合遺傳禁忌搜索算法的多目標(biāo)柔性作業(yè)車間調(diào)度問題研究D.重慶大學(xué)，2012.55 蘭任.基于并行混合粒子群算法的蛋白質(zhì)結(jié)構(gòu)預(yù)測D.大連理工大學(xué)，2011.56 袁曾人工神經(jīng)元網(wǎng)絡(luò)及其應(yīng)用M北京：清華大學(xué)出版社，1999,10.57曾顯峰基于人工神經(jīng)網(wǎng)絡(luò)的入侵檢測技術(shù)研究D.廣州市：華南理工大學(xué)，2010.58 張雨濃.人工神經(jīng)網(wǎng)絡(luò)的面向?qū)ο筌浖?shí)現(xiàn)D.廣州：華南理工大學(xué)，1999.59 劉品.BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化研究及應(yīng)用D.中國地質(zhì)大學(xué)，2017,02.60 王和杰.基于遺傳算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)的汽車油耗計(jì)算模