基于改進自適應(yīng)遺傳粒子群混合算法的多AGV路徑規(guī)劃研究

錢 成 董春芳

（東北林業(yè)大學，黑龍江 哈爾濱 150036）

0 引言

隨著物流倉儲領(lǐng)域?qū)ψ詣踊揭蟮牟粩嗵岣撸珹GV已經(jīng)成為影響物流運輸效率的關(guān)鍵工具。AGV 路徑規(guī)劃是規(guī)劃1 條從起點到目標點的無障礙路徑，路徑規(guī)劃能力將直接影響整個物流系統(tǒng)的工作效率[1]。

遺傳算法憑借尋優(yōu)能力強的優(yōu)勢，被廣泛應(yīng)用于路徑規(guī)劃領(lǐng)域。苑光明等[2]在傳統(tǒng)遺傳算法的基礎(chǔ)上改進了精英選擇策略，動態(tài)調(diào)整交叉、變異概率，提高了AGV 搜索路徑的質(zhì)量。粒子群算法具有原理簡單、收斂速度快以及尋優(yōu)穩(wěn)定性高的特點，同樣具有廣泛的應(yīng)用范圍。丁承君等[3]提出一種具有遺傳因子的改進粒子群算法，引入自適應(yīng)慣性權(quán)重并對粒子進行交叉、變異操作，以降低算法迭代次數(shù)。

上述學者采用的方法在一定程度上提高了AGV 的路徑質(zhì)量，但是針對處理多AGV 路徑規(guī)劃還是存在尋優(yōu)能力較差、運行時間長等問題，該文提出了一種改進自適應(yīng)遺傳粒子群混合算法（HpsoGA），根據(jù)迭代次數(shù)動態(tài)修改權(quán)重、學習因子，同時對遺傳算法中的交叉、變異概率進行動態(tài)非線性調(diào)整，在適應(yīng)度函數(shù)中引入擁堵系數(shù)來懲罰可能擁堵的路徑，從而規(guī)劃更優(yōu)路徑。

1 模型創(chuàng)建

1.1 問題描述

在物流倉庫中，需要AGV 從起點出發(fā)，根據(jù)相應(yīng)的路徑到達目標任務(wù)點完成取貨作業(yè)，同時需要避免與其他工作中的AGV 發(fā)生沖突。多AGV 路徑規(guī)劃的目標是在不產(chǎn)生沖突的前提下找到最優(yōu)路徑，從而提高整個系統(tǒng)的運行效率。需要考慮以下6 個約束條件：1） 已知每臺AGV 以及目標點的位置。2） 環(huán)境地圖已知且只存在動態(tài)障礙物，即移動中的AGV。3）每臺AGV 采用四向移動策略，即能完成4 個方向（前、后、左和右）的移動。4） 每臺AGV 對應(yīng)1 個目標任務(wù)，將貨物運輸?shù)綄?yīng)目標位置即完成任務(wù)。5） 地圖中的道路為單通道雙向行駛，每個位置節(jié)點僅能容納1 臺AGV。6） AGV 保持勻速行駛，不考慮加減速以及能耗。

1.2 建立模型

系統(tǒng)中有多臺AGV 以及目標位置點，將整個環(huán)境看作二維平面，建立平面直角坐標系。以O(shè)點為坐標原點，定義原點坐標為（0，0）。

在多AGV 系統(tǒng)R=（R1，R2，...，RM）中，系統(tǒng)為各AGV規(guī)劃的全局路徑是一組自由節(jié)點。記第i個AGV 的路徑為Pi={（xi1，yi1），（xi2，yi2）}，...，（xiNsi，yiNsi），其中（xi1，yi1）為第i個AGV 路徑中的第一個節(jié)點；Nsi為第i個AGV 的路徑節(jié)點個數(shù)。多AGV 路徑規(guī)劃的目標是規(guī)劃最優(yōu)路徑，各臺AGV 到達任務(wù)點經(jīng)過的路徑總和最優(yōu)，同時需要考慮AGV 之間的路徑?jīng)_突。多AGV 路徑規(guī)劃的目標函數(shù)如公式（1）所示，總目標函數(shù)使多AGV 系統(tǒng)整體總運輸路徑最短，保證多AGV 系統(tǒng)中路徑整體最優(yōu)。

式中：k為第i個AGV 路徑中的節(jié)點序號。

AGV 需要滿足的連續(xù)約束條件如公式（2）所示。各AGV在移動過程中不能跨點移動，每次移動的步長不能超過節(jié)點之間的最大間距，即組成P的節(jié)點必須是一組連續(xù)的節(jié)點集合。

式中：αx、αy為橫向、縱向的最大移動距離。安全約束條件如公式（3）所示。

式中：lα為安全距離，在移動的過程中，AGV 在任一路徑節(jié)點（xik，yik）與障礙物的中心坐標（xh，yh）之間的距離不能小于安全距離；M為AGV 的總數(shù)目。

時間窗約束條件如公式（4）所示。

式中：TRim為第i臺AGV 經(jīng)過m個節(jié)點的時間；TRjm為第j臺AGV 經(jīng)過n個節(jié)點的時間；Tc為沖突限制時間；Ri為第i臺AGV 的編號；Rj為第j臺AGV 的編號；Nsm為第i個AGV 經(jīng)過的路徑節(jié)點個數(shù)；Nsn為第j個AGV 的路徑節(jié)點個數(shù)。

公式（4）表示任意2 個AGV 到達任意路徑節(jié)點的時間必須大于沖突限制時間Tc。

2 多AGV 路徑規(guī)劃的自適應(yīng)遺傳粒子群混合算法

2.1 基本粒子群算法

粒子群算法（PSO）又稱鳥群算法。假設(shè)在D維空間中粒子的個數(shù)為M，其位置和速度按照公式（5）和公式（6）進行更新。

式中：v（k）為k時刻的速度；presenf（k）是k時刻的位置；pbest（k）為k時刻的個體已知最優(yōu)解；gbest（k）為k時刻的群體已知最優(yōu)解；r1和r2為2 個服從伯努利分布的0 或1 隨機數(shù)；ω是慣性權(quán)重因子；c1為全局學習因子；c2為局部學習因子。

2.2 非線性遞減慣性權(quán)重與學習因子優(yōu)化

在基本粒子群算法中，較大的ω可以提高全局搜索能力，跳出局部極值，而較小的ω可以提高粒子群算法的局部搜索能力。文獻[4]引入了一種非線性遞減的慣性權(quán)重系數(shù)對粒子群算法進行改進，使粒子能更細致地對優(yōu)化目標進行搜索，如公式（7）所示。

式中：ωk為當前迭代的權(quán)重值；ωmin為最小慣性權(quán)重；Nmax為迭代次數(shù)最大值；NT為當前迭代次數(shù)；ω為慣性權(quán)重系數(shù)。

該文提出了一種新的非線性遞減慣性權(quán)重，如公式（8）所示。

式中：ωmax為最大慣性權(quán)重，ω的取值范圍為0.4~0.9；m為隨機權(quán)重調(diào)整因子，m=2.1；σ為慣性調(diào)整因子；NT為當前迭代次數(shù)；Brand為MATLAB 中的隨機數(shù)生成器，能生成符合貝塔分布的隨機數(shù)[5]。

為了更合理地對ω進行調(diào)整，使用貝塔分布并加入慣性調(diào)整因子來調(diào)整慣性權(quán)重，其中σ=0.1。

為了有效改善粒子群算法的搜索效果，在整個算法中c1逐漸變小，c2應(yīng)逐漸增大。該文采用動態(tài)學習因子來改善粒子群算法的搜索效果，如公式（9）、公式（10）所示。

式中：c1為全局學習因子；c2為局部學習因子。

當?shù)螖?shù)為1 時，c1≈c1max，c2≈c2min；當NT=Nmax時，c1≈c1min，c2≈c2min。隨著算法迭代，學習因子也會隨著迭代次數(shù)進行調(diào)整，從而避免陷入局部最優(yōu)。

2.3 選擇、交叉與變異

為了提高算法的收斂速度，根據(jù)算法進化過程中適應(yīng)度值的變化，動態(tài)調(diào)整Pc和Pm。該文采用文獻[2]中的交叉、變異概率調(diào)整公式，如公式（11）、公式（12）所示。

式中：Pc、Pm分別為交叉概率參數(shù)、變異概率參數(shù)；Pcmax、Pcmin分別為交叉概率的上、下限；Pmmax、Pmmin分別為變異概率的上、下限；Fmax、Fmin分別為群體適應(yīng)度的最大值、最小值；Fc為交叉的2 個個體中較大的適應(yīng)度值；Fm為要變異個體的適應(yīng)度值。

2.4 適應(yīng)度函數(shù)

AGV 路徑規(guī)劃常以路徑總長度的倒數(shù)為適應(yīng)度函數(shù)評價標準。考慮多AGV 的影響，以路徑總長度以及轉(zhuǎn)彎次數(shù)為評價指標，同時引入擁堵系數(shù)建立適應(yīng)度函數(shù)fit，如公式（13）所示。

式中：lp為路徑總長度；pn為轉(zhuǎn)彎路徑節(jié)點數(shù)；pk為擁堵系數(shù)；a、b為2 個權(quán)重因子，a+b=1。

由于運行過程中可能發(fā)生多AGV 之間的路徑?jīng)_突，因此需要通過擁堵系數(shù)對擁堵程度高的路徑進行懲罰，從而避免擁堵[6]。擁堵系數(shù)是表示一定時間內(nèi)某一節(jié)點遍歷的次數(shù)對總節(jié)點數(shù)的比率，如公式（14）、公式（15）所示。

式中：Pk為在節(jié)點k的擁堵系數(shù)；n為節(jié)點號；k為經(jīng)過的節(jié)點號；H為時間段內(nèi)節(jié)點的使用頻率；M為節(jié)點出現(xiàn)的次數(shù)集合；A為AGV 在當前節(jié)點的出現(xiàn)次數(shù)集合；NAGV為小車數(shù)量。

Pk越大，適應(yīng)度函數(shù)fit就越大。

2.5 改進自適應(yīng)遺傳粒子群混合算法多AGV 路徑規(guī)劃步驟

改進自適應(yīng)遺傳粒子群混合算法多AGV 路徑規(guī)劃步驟如下：1） 確定AGV 路徑上各個節(jié)點的坐標位置。2） 初始化參數(shù)，對粒子個體進行編碼，生成初始種群，設(shè)定粒子的初始位置和初始速度。3） 計算各粒子的適應(yīng)度值，根據(jù)適應(yīng)度值的優(yōu)劣來更新粒子最優(yōu)解pbest以及全局最優(yōu)解gbest。4） 根據(jù)公式（7）~公式（10）分別對慣性權(quán)重系數(shù)ω、全局學習因子c1以及局部學習因子c2進行更新。5） 根據(jù)公式（5）、公式（6）更新粒子的位置和速度。6） 保留適應(yīng)度好的前三層，最后一層用適應(yīng)度值最好的個體代替。7） 根據(jù)公式（11）選擇需要交叉的粒子，完成交叉。8） 根據(jù)公式（12）進行粒子變異操作，產(chǎn)生新的子代。對粒子進行解碼，計算適應(yīng)度值并記錄。9） 判斷是否滿足終止條件。如果是，那么算法結(jié)束，輸出結(jié)果；否則回到第三步。

3 實例仿真分析

為了增加合理性對比驗證，對文獻[2]中的改進遺傳算法（HGA）、文獻[4]中的改進粒子群算法（HPSO）和該文的HpsoGA 進行對比。根據(jù)某物流倉庫中的實際環(huán)境以及AGV 運行情況建立具有20×20 節(jié)點位置的地圖模型，地圖中共有400個節(jié)點，設(shè)置M=9，目標任務(wù)數(shù)Nr=9，編號集合為TP=（TP1，TP2，...，TPNr）。采用HGA、HPSO 進行路徑規(guī)劃，其收斂時間-路徑長度折線如圖1 所示。

記錄HGA、HPSO 每次運行的最優(yōu)路徑以及收斂時的迭代次數(shù)，結(jié)果見表1、表2。

表1 相對最優(yōu)路徑的數(shù)據(jù)對比表

表2 收斂時迭代次數(shù)對比表

由表1、表2 可知，與HGA 相比，HPSO 算法的收斂時間會縮短22.41%，但是HGA 規(guī)劃的最短路徑長度能比HPSO縮短了13.85%。

針對HGA 和HPSO 的優(yōu)、缺點，該文采用HpsoGA 進行路徑規(guī)劃，在相同的參數(shù)下迭代100 次，其收斂時間-路徑長度折線如圖2 所示。

圖2 HPSO/HGA/HpsoGA 對比圖

記錄3 種算法在迭代100 次的前提下達到收斂時的最優(yōu)解以及相應(yīng)的迭代次數(shù)，其運行結(jié)果、對比結(jié)果見表3、表4。

表3 3 種算法的運行結(jié)果

表4 3 種算法的對比結(jié)果

由對比結(jié)果可以看出，HpsoGA 平均迭代8 次就可以搜索到全局最優(yōu)路徑，最優(yōu)路徑平均值為55.8，比HPSO 的收斂速度快，尋優(yōu)能力更強且算法穩(wěn)定性更高。

4 結(jié)語

在多AGV 路徑規(guī)劃問題中，已有的改進遺傳算法具有收斂速度慢的缺點，而改進粒子群算法容易陷入局部最優(yōu)，過早達到收斂。該文提出了一種改進自適應(yīng)遺傳粒子群混合算法，采用一種新的非線性遞減慣性權(quán)重優(yōu)化并采用動態(tài)學習因子進行改進，引入擁堵系數(shù)構(gòu)建適應(yīng)度函數(shù)。結(jié)果表明，該算法能以更短的時間規(guī)劃更優(yōu)的路徑，從而提高AGV 的運行效率。