一種改進的粒子群算法的路徑規劃研究

王文豐,宋 勇,韓龍哲,包學才,劉天元,徐 燈

1(南昌工程學院 江西省水信息協同感知與智能處理重點實驗室,南昌 330099)2(南昌工程學院 信息工程學院,南昌 330099)3(武漢理工大學 自動化學院,武漢 430000)

1 引 言

隨著經濟全球化,各國之間的貿易往來越來越密切.在進行貿易過程中,交通運輸是個重要問題.海洋運輸以其成本低等特點在跨國貿易中扮演重要角色,而其發展主要受限于船舶航行路徑規劃的科學性,因此實現船舶航行路徑規劃的智能化具有重要的現實意義[1].

目前,國內外眾多專家學者對船舶路徑規劃問題進行了深入的研究.船舶航行路徑規劃問題主要包括海洋環境建模和路徑優化.其中,海洋環境建模主要有可視圖法、柵格法、拓撲法、鏈接圖法等.可視圖法算法靈活、實現簡單,但不能對圓形障礙物進行有效處理,每次搜索都要重新構建可視圖,比較耗費時間;柵格法對于柵格大小的選取要求較高;拓撲圖法具有建模速度快、存儲空間少等優點,但不能解決障礙物特征不明顯、分布稀疏的環境下路徑規劃問題;鏈接圖法具有運用靈活的優點,當路徑的起點和終點發生改變時,整個連通圖不會發生變化,其缺點在于:當環境中的障礙物較多時,所構造的連通圖會較復雜,加大了路徑規劃的難度.路徑優化的典型方法有神經網絡、蟻群算法和遺傳算法等[2-4].神經網絡具有規劃速度快、魯棒性強等優點,但泛化能力差,通常將其和其它算法結合運用進行路徑規劃;蟻群算法能夠完成分布式計算,但算法計算量大、收斂速度慢,而且容易陷入局部最優;遺傳算法具有實時性好的優點,但運算速度慢、進化規則多等缺點限制了其應用.

近年來,由于粒子群算法具有參數簡單、搜索速度快等優點,因此在船舶路徑規劃的研究中得到了廣泛的應用.文獻[5]提出將粒子群算法和滾動優化策略進行結合,利用粒子群算法求解每一個移動窗口內的最優路徑,從而獲取全局最優路徑.粒子群算法為解決船舶路徑規劃問題提供了有效方法,但依然存在路徑規劃速度慢、規劃路徑較長甚至失敗等缺點.文獻[6]針對傳統的粒子群算法存在的問題,提出了一種非線性的動態調整慣性權重的方法,同時在適應度函數中引入平滑度和安全度概念.該方法能夠明顯降低算法陷入局部最優的概率.也有部分學者從改進算法本身的角度出發,和其它算法相結合以避免陷入局部最優并提高全局求解精度,如文獻[7]通過將遺傳算法和粒子群算法結合以充分利用兩者的優點,大大提高了局部尋優能力.

本文在傳統的船舶路徑規劃研究的基礎上,針對粒子群算法存在的容易陷入局部最優、尋優精度低等問題,提出了一種基于混沌理論并引入多種群的粒子群優化算法(Chaos Multi-population Particle Swarm Optimization,CMPSO).在提高算法的解的精度同時,將速度自適應調整策略引入到種群更新中來,加快算法的收斂速度.

2 海洋環境的建模

解決船舶路徑規劃問題,首先需要對相應的海洋環境進行建模,將非狀態空間轉換為狀態空間.海洋環境的建模在實際的處理過程中主要考慮航線的表達、航線的安全和信息的處理等問題.由于本文所研究的海洋環境相對陸地以及其它環境的障礙物較少,能充分發揮鏈接圖法的優點、避免了其不足之處,因此本文選用鏈接圖法作為環境建模方法.

鏈接圖法是自由空間建模的一種方法,它先把空間內的障礙物抽象成各種平面凸邊形,再利用圖論知識在該空間中建立一個全局連通圖,最后在這個連通圖上實現路徑規劃.在進行環境建模之前,考慮到船舶本身的特性以及海洋環境的復雜性需要進行相應的簡化處理,作出以下幾點假設:

1)只考慮必要的環境信息,忽略氣流等信息;

2)只考慮船舶在二維平面上的運動,不考慮高度信息;

3)用凸多邊形描述環境中的邊界以及各種障礙物;

4)適當擴大障礙物的邊界范圍,以保證當船舶在航行過程中沿著障礙物邊緣行進時,不會與障礙物發生碰撞;

5)將船舶看作一個質點,忽略其尺寸大小;

6)根據需要適當縮小環境的邊界范圍以減少一些不必要的工作量;

3 路徑規劃算法設計

3.1 初始路徑規劃

1959年,E.W.Dijkstra基于貪心算法研究單源最短路徑問題,提出了Dijkstra算法,該算法是目前公認的最好的求解最短路徑的方法[8].算法解決的是有向圖中單個源點到其它頂點的最短路徑問題,其基本思路是每次迭代時始終選擇除標記點之外其它頂點中距離源點最近的點作為下一個頂點,從而保證所得路徑最短[9].

圖1 Dijkstra算法獲取船舶初始路徑流程圖Fig.1 Flowchart of acquiring initial path by Dijkstra

通過Dijkstra計算圖G中的最短路徑時,需要指定起點s.此外,引進兩個集合S和U.集合S用于記錄已求出最短路徑的頂點以及相應的最短路徑長度,而集合U則記錄還未求出最短路徑的頂點以及該頂點到起點s的距離[10].Dijkstra算法流程圖如圖1所示.

3.2 路徑優化

通過Dijkstra算法規劃出的路徑是基于鏈接圖法所建立的模型所得,并非全局最優路徑.因此,在該初始路徑的基礎上,采用粒子群算法進行路徑優化.在利用PSO算法進行路徑規劃時,通常將一條條路徑對應于種群中的粒子,每一條可行路徑包括一系列路徑點,粒子各個維度的分量表示路徑點在該鏈接線上的位置,再利用算法的全局尋優能力對路徑點的位置進行調整,最終獲得全局最優路徑.

(1)

其中,hi為比例系數,d為路徑劃分的節點數.

由式(1)可知,通過Dijkstra算法得到的路徑經過自由鏈接線時,任意一組參數(h1,h2,…,hd)即對應一條從起點到終點的新路徑.因此,(h1,h2,…,hd)可表示相應的路徑信息,也即粒子群優化算法解的形式.

通過仿真實驗發現,粒子群優化算法雖然能獲取全局最優路徑,但算法本身存在的容易陷入局部最優、尋優精度不高等問題依然突出[11,12].為解決上述問題,本文對粒子群優化算法進行改進,提出了一種基于混沌理論并引入多種群的粒子群優化算法(Chaos Multi-population Particle Swarm Optimization,CMPSO).

1)基于混沌理論的粒子群優化算法改進

一般粒子群優化算法的種群初始化是隨機進行的.這種處理方法雖然簡單,但可能造成初始粒子分布不夠均勻,而且遠離最優解,這會造成大量不必要的搜索操作,嚴重影響了算法的執行效率.因此,本文利用混沌理論產生初始種群以使初始粒子分布均勻,提高算法執行效率.基于混沌理論的模型有很多種,本文采用較常見的Logistic映射模型.Logistic模型是一種最簡單的回歸方程,而且遍歷性較好,可使粒子均勻分布,其回歸方程如下:

xi+1=4xi(1-xi),xi∈(0,1)

(2)

根據上述分析,充分利用混沌理論的隨機性和遍歷性,在種群初始化時,利用混沌序列產生初始化種群以保證粒子的均勻分布.同時,為了提高初始粒子的質量,在利用混沌序列進行種群初始化時產生過量粒子,并從中選出適應度值高的部分粒子作為初始種群.這樣既保證了初始粒子在解空間中的均勻分布,也使初始種群中粒子更接近最優解,加快算法收斂速度[13].

2)引入多種群的粒子群優化算法改進

通過前文對粒子群算法原理和數學模型的分析可知,粒子具有全局搜索能力和局部搜索能力,而且這兩種能力相互影響.當前學者通過引入慣性權重來平衡粒子的全局搜索能力和局部搜索能力[14].這雖然取得了一定效果,但在處理復雜問題時效果欠佳.

本文通過建立多種群機制以對粒子群算法進行改進.在改進的粒子群優化算法中,將整個種群分成三個子種群.第一個種群粒子的慣性權重較大.根據對粒子群優化算法數學模型的分析可知,該種群具有較強的全局搜索能力,能夠完成在解空間內的大范圍搜索,提高算法收斂速度.第二個種群的慣性權重較小,該種群具有較強的局部搜索能力,能夠對局部范圍進行精細搜索,提高算法解的精度.第三個種群粒子的全局搜索能力和局部搜索能力相當.為了提高第三個種群算法的收斂速度,在該種群中引入自適應速度調整的策略.根據實際情況的分析可知,當粒子朝全局最優粒子方向運動且粒子不斷找到更優的點時,此時若不改其飛行方向可使粒子更快地飛向最優粒子,從而加快算法收斂速度.因此,第三個種群的速度更新公式改為如下:

(3)

根據上式可知,若當前粒子本次迭代的適應度值比上次高,則說明該粒子沿著當前方向運動有利于找到全局最優粒子;若當前粒子本次迭代的適應度值比上次低,則說明粒子當前并非向全局最優粒子方向運動,下次粒子的速度按標準粒子群優化算法粒子速度更新方式進行更新.

通過上述改進方法可保證粒子種群的多樣性,各個子群分工明確、相互協作,使算法將解空間中的極值點一一找出,避免算法陷入局部最優,而且加快了算法的收斂速度,提高了解的精度.

3.3 路徑平滑優化

通過上述算法規劃所得的最優路徑是由一系列路徑點組成的折線.若船舶按該路徑航行,船舶的轉彎次數較多,且某些航段航行距離較短,某些轉向點處轉彎角度過大,這不利于船舶的安全航行,增加了經濟成本,這并非一個理想的效果.

本文在基本粒子群優化算法的基礎上引入路徑平滑處理,從而提高算法執行效率,減少船舶轉彎次數,增強所得路徑的實用性.本文所采取的平滑處理思路是,對于優化后的每個航段進行處理,盡可能地截彎取直,用直線將各個路徑點相連,從而減小了船舶的轉彎角度,并且使船舶在每個航段的航行距離較長.假設粒子群優化算法所得路徑序列為(P1,P2,…,Pi,…,Pn),路徑平滑處理流程圖如圖2所示.按照初始所得路徑序列順序,從第一個路徑點開始與最后一個路徑點相連,若所連線段沒有穿越障礙物,則將該段路徑存入路徑序列作為全局路徑的一個子路徑段,否則與其前一個路徑點相連.如此循環,直至求解到倒數第二個路徑點為止.通過將每個路徑點進行平滑處理即可得到更理想的全局最優路徑.

圖2 路徑平滑處理流程圖Fig.2 Flowchart of smoothing path

4 實驗結果分析

本文以某海島區域為背景,利用Matlab軟件對相關算法進行仿真實驗.

首先,在進行必要的假設后,利用鏈接圖法對海洋環境建模.設置起點坐標為P(148.56,37.42),終點坐標為Q(198.84,145.68),利用Dijkstra算法獲取一條從起點到終點的初始路徑,如圖3所示.

圖3 Dijkstra算法獲取初始路徑示意圖Fig.3 Obtain the initial path by Dijkstra algorithm

接著,在初始路徑的基礎上利用線性遞減慣性權重粒子群算法(LDW-PSO)搜索出全局最優路徑.從圖3中可看出,Dijkstra算法規劃出的初始路徑共有8個路徑點.因此,LDW-PSO的每個粒子包括8個維度.設置算法的粒子數為100,迭代次數為300,max=0.95,min=0.2,c1=c2=2.采用線性遞減慣性權重粒子群算法(LDW-PSO)進行全局路徑規劃所得路徑如圖4所示,圖5為路徑長度隨迭代次數變化情況.從圖3可看出,船舶在航行過程中8次改變航向,且部分轉向角度過大,這不利于船舶的安全高速航行.從圖5可看出,當算法迭代到了第27代時即出現了并非最優的收斂,并陷入局部最優狀態,直至到第261代才出現了相對可行的路徑,所得最優路徑長度為171.114km,總共耗時6.87s.

圖4 LDW-PSO進行全局路徑規劃示意圖Fig.4 Global path planning by LDW-PSO

圖5 路徑總長度隨迭代次數變化曲線Fig.5 Changes for total length of the path with the number of iterations

圖6 采用加入路徑平滑優化處理的路徑規劃示意圖Fig.6 Schematic diagram of path planning with path smoothing optimization

在上述基礎上加入路徑平滑處理,所規劃出的路徑如圖6所示.本次規劃所得路徑長度為148.372km,總共耗時1.65s, 路徑全長總共有2次改變航向, 且每次所需轉向角度都不大.進行路徑優化處理前后相關數據如表1所示.通過兩者對比可看出,加入路徑平滑處理方法可極大地提高算法的執行效率,且所規劃出的路徑轉向點數更少,對于船舶的安全高速航行具有重要意義.

表1 路徑平滑優化處理前后對比
Table 1 Comparison before and after smoothing path

方法規劃路徑長度(km)最小航段長度(km)轉彎點數量(個)最大轉彎角度(度)平均計算時間(s)改前171.11424.42864.86.87改后148.37247.81242.71.65

接著,分別利用線性遞減慣性權重粒子群算法(LDW-PSO)和改進的粒子群優化算法(CMPSO)進行船舶路徑規劃以比較兩者實際效果.改進的粒子群優化算法的第一個子群的慣性權重ω=0.9,第二個子群的慣性權重ω=0.4,第三個子群的慣性權重ω=0.75,而且這三個子群占整個種群的比例分別為2∶1∶2,三個子群中c1=c2=2.采用線性遞減的粒子群優化算法的ωmax=0.9,ωmin=0.4,c1=c2=2.兩種算法的種群粒子數均為100,最大迭代次數為300.設置起點坐標為P(68.25,72.36),終點坐標為Q(131.72,23.64),分別利用兩種算法進行路徑規劃30次,且均不加入路徑平滑優化處理,記錄所獲取的全局最優路徑長度,其最優個體適應度值的平均值隨迭代次數的變化如圖7所示.計算全局最優路徑的均值以及方差,結果如表2所示.

圖7 路徑規劃適應度值隨迭代次數變化曲線1Fig.7 Fitness of path planning varies with the number of iterations firstly

從圖7、表2可看出LDW-PSO和CMPSO均能實現全局路徑規劃,兩者所規劃出的全局最優路徑長度相差不大,但本文提出的改進算法計算時間更短、效率更高,方差也稍小于前者.結合本次路徑規劃所定的起點和終點,發現算法的搜索環境較好,沒有很多復雜障礙物.因此可得出,在相對簡單的環境下進行路徑規劃,線性遞減慣性權重粒子群算法和本文提出的改進算法均能實現全局路徑規劃,但改進后的算法收斂速度更快,算法的穩定性更高.

表2 利用粒子群優化算法和改進后的算法效果對比1
Table 2 Particle swarm optimization algorithm and the improved algorithm are compared firstly

方法平均規劃路徑長度(km)方差平均計算時間(s)LDW-PSO118.480.0272.47CMPSO117.2501.28

為檢驗兩種算法在復雜環境下進行路徑規劃的表現,設置起點坐標為P(47.24,233.75),終點坐標為Q(163.48,32.63),其它參數均與上述實驗相同.分別利用兩種算法進行路徑規劃30次,記錄所獲取的全局最優路徑長度, 其最優個體適應度值的平均值隨迭代次數的變化如圖8所示.計算全局最優路徑的均值以及方差,結果如表3所示.

圖8 路徑規劃適應度值隨迭代次數變化曲線2Fig.8 Fitness of path planning varies with the number of iterations secondly

結合圖8、表3分析可看出,在對復雜環境進行路徑規劃時,線性遞減慣性權重粒子群算法較容易陷入局部最優,偏差較大,不能有效規劃出全局最優路徑.相對而言,本文提出的改進算法不僅能取得更好的最優值,規劃出更優的全局路徑,而且算法平均計算時間短,方差較小.這些說明改進的算法不僅能解決復雜環境下的全局最優解的搜索,而且算法收斂速度更快,搜索精度更高,穩定性更強.

表3 利用粒子群優化算法和改進后的算法效果對比2
Table 3 Particle swarm optimization algorithm and the improved algorithm are compared secondly

方法平均規劃路徑長度(km)方差平均計算時間(s)LDW-PSO277.844.76212.74CMPSO246.470.0672.54

5 結 語

本文利用粒子群優化算法規劃出全局最優路徑,并加入平滑優化處理,將優化后的路徑與前者進行對比可發現刪除冗余點的平滑優化處理方法可極大地提高算法運行效率,保證船舶安全高速航行.針對線性遞減慣性權重粒子群算法存在的問題,本文提出了改進算法.通過混沌序列對初始種群進行初始化,并進行一定的篩選,保證了初始粒子的質量和分布的均勻性.并且建立多種群機制,平衡種群的全局搜索能力和局部搜索能力,最后通過仿真實驗驗證了該算法的有效性.