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

錢 成 董春芳

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

0 引言

隨著物流倉儲(chǔ)領(lǐng)域?qū)ψ詣?dòng)化水平要求的不斷提高，AGV已經(jīng)成為影響物流運(yùn)輸效率的關(guān)鍵工具。AGV 路徑規(guī)劃是規(guī)劃1 條從起點(diǎn)到目標(biāo)點(diǎn)的無障礙路徑，路徑規(guī)劃能力將直接影響整個(gè)物流系統(tǒng)的工作效率[1]。

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

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

1 模型創(chuàng)建

1.1 問題描述

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

1.2 建立模型

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

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

式中：k為第i個(gè)AGV 路徑中的節(jié)點(diǎn)序號(hào)。

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

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

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

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

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

公式（4）表示任意2 個(gè)AGV 到達(dá)任意路徑節(jié)點(diǎn)的時(shí)間必須大于沖突限制時(shí)間Tc。

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

2.1 基本粒子群算法

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

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

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

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

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

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

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

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

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

式中：c1為全局學(xué)習(xí)因子；c2為局部學(xué)習(xí)因子。

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

2.3 選擇、交叉與變異

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

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

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

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

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

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

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

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

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

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

3 實(shí)例仿真分析

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

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

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

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

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

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

圖2 HPSO/HGA/HpsoGA 對(duì)比圖

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

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

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

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

4 結(jié)語

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