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

蔣柳鵬，戴南亭

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

0 引言

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

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

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

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

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

1 AGV 路徑規(guī)劃問題

1.1 AGV 路徑規(guī)劃環(huán)境建模

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

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

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

1.2 AGV 路徑規(guī)劃適應度函數(shù)設計

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

1） 路徑長度

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

總的路徑長度公式如下：

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

2） 路徑平滑度

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

3） AGV 與障礙物碰撞風險

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

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

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

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

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

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

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

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

該算法過程如下：

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

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

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

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

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

3 仿真實驗

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

3.1 AGV 靜態(tài)路徑規(guī)劃仿真實驗

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

表1 參數(shù)設置信息Table 1 Parameter setting information

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

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

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

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

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

3.2 AGV 動態(tài)路徑規(guī)劃仿真實驗

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

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

圖4 3 種不同算法的AGV 動態(tài)路徑規(guī)劃圖Fig. 4 AGV dynamic path diagram with three different algorithms

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

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

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

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

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

4 結語

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

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

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