基于（1+1）進化策略的港口AGV 路徑規劃改進進化算法

蔣柳鵬，戴南亭

（河海大學港口海岸與近海工程學院，江蘇 南京 210098）

0 引言

AGV（Automated Guided Vehicle），即自動導引車，憑借其智能高效的優勢，被廣泛應用于港口物流、城市交通和智能倉儲系統等領域。港口AGV 路徑規劃通常指為裝運集裝箱的AGV 尋找從接貨點到卸貨點的最優路徑。根據AGV 搬運特點，該路徑需要綜合考慮搬運距離短、避免碰撞、安全轉向等問題，以有序完成搬運任務。港口AGV 路徑規劃是AGV 高效完成貨物搬運的核心問題，需要高效的優化算法求解其路徑規劃模型。

優化算法可分為兩大類：一是以數學為基礎的經典優化算法，如單純形法、最速下降法[1]等；二是啟發式智能優化算法，如遺傳算法、模擬退火算法、差分進化算法等。經典優化算法計算復雜，無法求解高維度、復雜目標函數的問題，因此AGV 路徑規劃中更多采用智能優化算法。其中進化算法（evolutionary algorithms，EA）是智能算法中的一個重要的“算法簇”，其產生的靈感源于大自然中生物的進化[2]。與基于微積分的傳統方法和窮舉法等優化算法相比，進化算法更加成熟，且作為全局優化方法具有魯棒性高、適用性廣及自組織、自適應和自學習的特性，能夠有效處理傳統優化算法難以求解的復雜問題，所以AGV 路徑規劃問題可以用EA 算法求解。

進化算法主要有3 種類型：遺傳算法（genetic algorithm，GA），進化規劃（evolutionaryprogramming，EP）和進化策略（evolutionary strategies，ES）等[3]。其中ES 摒棄了梯度計算，強調個體級的行為變化，使用交叉算子，采用實數值作為基因，并且遵循零均值、某一方差高斯分布的變化產生新個體，在選擇和變異的操作上更為靈活，整體計算更加高效，適用于AGV 路徑規劃問題。

根據選擇方法的不同，進化策略可以分為（1+1）進化策略（（1+1）-ES）和（μ，λ）進化策略（（μ，λ）-ES）兩種，其中（1+1）-ES 較為方便有效，被廣泛應用。近年國內外學者針對（1+1）-ES 算法的改進做了大量研究，KAYHANI A 等[4-5]引入步長自適應機制，并應用于基準函數和工程實例，結果表明，與其他算法相比，該算法具有高效性、魯棒性和全局尋優能力；KRAMER O 等[6-7]提出一種可以自適應改變算法中學習參數的方法，實驗結果表明該算法的總體性能有了顯著提高；JEBALIA M 等[8-9]基于（1+1）-ES 對球函數上的收斂性進行了數學分析，并顯著提高其邊界下限，實現了對均勻突變算子的連續優化。

在AGV 路徑優化問題上，目前使用較多的有強化學習、A*算法、Dijkstra 算法、蟻群算法和遺傳算法等[10-14]，（1+1）-ES 算法在AGV 路徑規劃中的研究成果較少。因此，本文嘗試提出一種改進的（1+1）進化策略及相應算法，應用于AGV 路徑規劃問題，同時優化該問題的適應度函數，以提升AGV 路徑規劃的效果。

1 AGV 路徑規劃問題

1.1 AGV 路徑規劃環境建模

AGV 在港口碼頭進行搬運工作的實際環境如圖1 所示，集裝箱被AGV 從堆場運至岸橋進行裝卸，實際環境由AGV、障礙物和支路組成。為方便研究，將AGV 假設成一個質點，將作業區的障礙物假設為同一尺寸，不考慮其實際尺寸?；跂鸥竦貓D法操作較為簡單、易于理解和實現的優點，本文采用柵格地圖法進行環境建模，長為3個單位柵格長度、寬為1 個單位柵格長度的黑色柵格表示障礙物，空白柵格表示可自由移動的空間，地圖左下角的黑色柵格表示AGV 運動的起點，地圖右上角的黑色柵格表示AGV 運動的終點[15]，AGV 環境建模如圖1 所示。

圖1 AGV 工作環境實際地圖和建模地圖Fig.1 Actual map and modeling map of AGV working environment

將AGV 工作環境等分為20 行20 列的柵格地圖，單位柵格可完全容納AGV，地圖上的所有點都可用坐標表示?？刂葡到y通過后臺控制向AGV發送搬運任務，AGV 會沿著計算得出的路徑進行運動，將該路徑上的點用柵格中的坐標表示，這些坐標通過遺傳算法的編碼后變成一條路徑染色體，每一條染色體便代表了一個解即一條路徑。

1.2 AGV 路徑規劃適應度函數設計

適應度函數是篩選路徑的標準，用來評價路徑的優劣，適應度越高說明該路徑越符合設定的約束條件[16]。傳統路徑規劃的適應度函數大多采用路徑長度最小為目標函數，本文結合港口碼頭AGV 實際的工作情況，例如AGV 運行過程中可能存在轉彎和與障礙物碰撞的情況，若轉彎角度過大或與障礙物碰撞將降低搬運的工作效率，并造成AGV 的損壞，所以本文對目標函數進行了改進，在路徑長度的基礎上增加了路徑平滑度和碰撞風險函數，從路徑長度、路徑平滑度、碰撞風險這3 個方面設計港口碼頭AGV 路徑規劃的適應度函數。

1） 路徑長度

（xi，yi）表示地圖上第i個點的坐標，Li表示（xi，yi）和（xi-1，yi-1）兩點之間的距離，相鄰兩點間的距離公式如下：

總的路徑長度公式如下：

將L無量綱化，并設置目標函數為：

2） 路徑平滑度

在AGV 運行過程中需要轉彎時，若轉彎角度過大將增加AGV 通過的時間，降低工作效率，并對AGV 本身造成一定的損耗，所以本文對路徑平滑度函數設置懲罰系數ω。當轉彎角度θ<45°時，ω 設置為1；當轉彎角度45°≤θ≤90°時，ω 設置為10；當轉彎角度θ>90°時，ω 設置為1 000。將ωθ 無量綱化，并設置路徑平滑度函數如下：

3） AGV 與障礙物碰撞風險

當障礙物的位置與AGV 的位置越近時，AGV與障礙物的碰撞風險越高，為防止AGV 與障礙物發生碰撞，本文設置位置風險系數λ。本文選擇將距離AGV 最近的障礙物的中心點坐標（xj，yj）與AGV 的位置坐標（xi，yi）間的距離作為判斷標準，若距離小于1.5 個單位柵格長度則判斷為有較大的碰撞風險，λ 設置為100，反之則λ=0。將λLij無量綱化，并設置障礙物與AGV 間的距離和碰撞風險函數如下：

綜合上述因素，設計路徑評價函數為：

式中：a、b、c為權重系數，且三者和為1。

當路徑評價函數數值越大時，說明該個體適應度越高，被保留到下一代的概率越大；當路徑評價函數數值越小時，說明該個體適應度越低，被保留到下一代的概率越小，該染色體被淘汰的概率越大。

2 （1+1）-ES 的AGV 路徑規劃求解算法設計

（1+1）-ES 是進化策略中較為簡單有效的一種[17]，是1 個父代通過高斯變異產生1 個子代尋優的算法，即只有1 個父親且每次只產生1 個新的個體，然后從這2 個個體中保留較好的進入后續的進化[18]。為了能夠在AGV 路徑規劃巨大的解空間中探索更好的解，避免陷入局部最優的情況，需要對變異過程進行改進，（1+1）-ES 是較好的方法。

（1+1）-ES 的變異強度由正態分布N（0，δ）決定，δ 為變異強度，通過控制分布，選取擾動，用擾動影響進化強度；通過對比擾動帶來的反饋，選擇成功變異的擾動，控制進化方向，能否找到最優解很大程度上取決于δ[19]。（1+1）-ES 的收斂過程遵循1/5 成功原則，當個體中有1/5 的變異個體比原始個體優秀時即判斷為即將收斂。收斂過程中如若未達到收斂條件，則增大變異強度，如若即將達到收斂條件，則減小變異強度。該策略根據歷史成功變異能力不斷調控δ，在很大程度上解決了使用其他優化算法會出現的陷入局部最優的問題。本文提出的（1+1）-ES 算法流程圖見圖2。

圖2 （1+1）-ES 算法流程圖Fig.2 (1+1)-ES algorithm flowchart

該算法過程如下：

1） 通過樣本產生初始個體x；

2） 通過初始個體x和變異強度δ 產生新的解，公式如下：

3） 計算個體的適應度函數值f（x）和f（y），如果f（y）>f（x），則用y替換x；

4） 調控變異強度大小，重復操作2） 和3）直到滿足輸出條件后輸出結果，變異強度的公式如下（δɡ表示第ɡ 代個體的變異強度，ps表示變異成功率，Cd為固定參數）[20]：

本文提出的（1+1）-ES 算法在原（1+1）-ES 算法基礎上改進了其適應度函數，提高了適應度函數的綜合程度，使其更適用于本文要解決的AGV路徑規劃問題。

3 仿真實驗

本文使用的路徑規劃算法在Python 語言和spyder 平臺進行開發，相關軟件及第三方庫的版本如下：Python 3.8.5，geatpy2.6.0。程序調試和算例求解均在1 臺CPU 主頻為1.80 GHz，GPU 為NVIDIA GeForce MX150，內存為8.00 GB 的個人計算機上完成。

3.1 AGV 靜態路徑規劃仿真實驗

在AGV 靜態路徑規劃中只考慮所有障礙物都是靜止狀態的情況，即地圖中不存在動態障礙。地圖中靜態障礙物的尺寸皆設置為長3 個單位柵格長度、寬1 個單位柵格長度，AGV 由1 個單位柵格表示，AGV 的仿真任務為從起點運行到終點。起點和終點也由1 個單位柵格表示，起點的坐標為（0，0），終點的坐標為（20，20）。其他各參數設置見表1。

表1 參數設置信息Table 1 Parameter setting information

使用本文設計的（1+1）-ES 算法得到的部分最優路徑見圖3，路徑具體信息見表2。

表2 基于（1+1）-ES 的部分路徑具體信息表Table Partial path specific information based on(1+1)-ES

圖3 基于（1+1）-ES 的AGV 靜態路徑規劃圖Fig.3 Static path diagram of AGV based on(1+1)-ES

由圖3 和表2 可以看出，使用本文提出的基于（1+1）-ES 的AGV 靜態路徑規劃得到的路徑在地圖中分布較廣，沒有出現大部分路徑高度重合的情況，即算法在整個過程中沒有出現陷入局部最優的情況，搜索范圍較為廣泛。這4 條路徑雖然都被算法的適應度評價指標評價為最優路徑，具體路線不同，但這些路徑的優勢各不相同。路徑1 開始所行方向與終點相差較遠，所以路徑長度是4 條路徑里最長的，轉彎次數較少且角度較小所以路徑平滑度較為優秀；路徑2 的路徑長度最小，但由于AGV 三次轉彎的角度都偏大，所以路徑平滑度相對較差；路徑3 由于轉彎次數較多且轉彎角度較大，所以路徑平滑度是4 條路徑里最大的，但總體運行方向相比于其他3 條路徑最為接近起點與終點的直線，所以路徑長度較短；路徑4 的轉彎角度較小，所以路徑4 的路徑平滑度最小即轉彎角度總和最小，轉彎次數較少，所以路徑長度也較小。總體來說這4 條路徑的2 種指標都較為優秀，且所有路徑的碰撞風險皆為0。

由上述仿真實驗結果可以看出：在靜態的環境下，使用本文設計的基于（1+1）-ES 的方法可以實現較為優秀的路徑規劃，該算法對各項指標都能夠有一定程度上的優化，很大程度上避免了其他算法可能出現的陷入局部最優的問題。

3.2 AGV 動態路徑規劃仿真實驗

考慮到AGV 的實際工作場地除了靜態障礙物外，會有工作人員隨機出現的情況，在原始的地圖上增加5 個隨機生成的柵格來代表可能會出現的工作人員。靜態障礙物的尺寸設置和向AGV 發布的模擬任務同靜態路徑規劃相同，算法的各參數設置也相同，具體參數設置見表2。為更加直觀地看出本文設計的基于（1+1）-ES 的優勢所在，本文選擇將其結果與差分進化算法和遺傳算法所得結果進行對比分析。3 種算法皆使用同樣的參數和柵格地圖，其中遺傳算法的變異概率設置為0.8，交叉概率設置為0.6，得到的某一條最優路徑如圖4 所示，路徑信息如表3 所示，算法收斂如圖5 所示。路徑平滑度較大，路徑長度也較長，這會降低AGV 的工作效率和增加對AGV 的損耗，另外未考慮碰撞的風險；由差分進化算法得到的最優DE 算法路徑在運行過程中同樣出現多次轉彎角度過大的情況導致該條路徑的路徑平滑度較大，路徑長度較長，并且在運行過程中有一處與障礙物相距過近，增加了AGV 與障礙物碰撞的風險；由（1+1）-ES 得到的最優（1+1）-ES 算法路徑運行方向總體與起點和終點間的連線最為接近，所以路徑長度相較于其他2 條路徑最短，并且轉彎次數較少，所有轉彎角度皆小于45°，所以路徑平滑度最小，無碰撞風險。

表3 基于不同算法的部分路徑的具體信息表Table 3 Partial path specific information based on different algorithms

圖4 3 種不同算法的AGV 動態路徑規劃圖Fig. 4 AGV dynamic path diagram with three different algorithms

圖5 算法收斂曲線Fig.5 Algorithmic convergence curve

由圖5 可以看出，遺傳算法的算法收斂曲線在迭代次數為0~38 次之間波動較大，運行不穩定，在迭代38 次時達到收斂狀態；差分進化算法的收斂曲線在迭代次數為0~36 次之間波動較大，運行同樣不夠穩定，在迭代36 次時達到收斂狀態；（1+1）-ES 前期有一處波動，總體運行較為穩定，且收斂速度相比于其他2 種算法更快，在迭代20 次時達到收斂狀態。

綜合分析，可以看出本文設計的（1+1）-ES 在適應度指標、運行穩定和收斂速度這3 個方面都明顯優于遺傳算法和差分進化算法，優勢總結具體見表4。

表4 不同算法結果的對比Table 4 Comparison results of different algorithm results

由圖4 和表3 可以明顯看出，在設置同樣的參數和地圖條件下，本文設計的（1+1）-ES 算法在路徑長度和路徑平滑度上明顯優于遺傳算法和差分進化算法。由遺傳算法得到的最優GA 算法路徑在運行過程中多次出現轉彎角度過大的情況，其中1 個轉彎的角度超過了90°，導致該條路徑的

4 結語

本文提出了一種基于（1+1）-ES 的AGV 路徑規劃改進算法，從路徑長度、路徑平滑度和碰撞風險3 個方面改進了算法的適應度函數，使其更加適用于AGV 的路徑規劃問題。

在仿真實驗中設計柵格地圖來模擬實際港口AGV 的工作環境，通過仿真實驗可以看出，在靜態路徑規劃和動態路徑規劃中，本文提出的改進后的（1+1）-ES 算法均提高了搜索效率，并有效解決了算法求解易陷入局部最優的問題，驗證了本文提出的基于（1+1）-ES 在解決AGV 路徑規劃中的高效性和可靠性。

本文在有限障礙物和單個AGV 的前提下進行了路徑規劃研究，在后續的研究中，本文將對障礙物的隨機性和不確定性進行進一步的復雜假設，并且加入其它的AGV 進行多AGV 的路徑規劃問題研究。