基于改進(jìn)遺傳算法的自動(dòng)導(dǎo)航小車路徑規(guī)劃調(diào)度

于佳喬，李巖

(長(zhǎng)春工業(yè)大學(xué)電氣與電子工程學(xué)院，吉林長(zhǎng)春 130012)

0 前言

隨著“中國(guó)制造2025”計(jì)劃的實(shí)施，制造業(yè)的生產(chǎn)模式發(fā)生了巨大變化，智能制造為傳統(tǒng)制造業(yè)開辟了一條新的道路。在新型智慧工廠中，柔性制造系統(tǒng)已應(yīng)用于大多數(shù)企業(yè)。柔性制造系統(tǒng)(Flexible Manufacturing System，F(xiàn)MS)是由統(tǒng)一的信息控制系統(tǒng)、物料儲(chǔ)運(yùn)系統(tǒng)和數(shù)字控制加工設(shè)備組成，能適應(yīng)加工對(duì)象變換的自動(dòng)化機(jī)械制造系統(tǒng)。其中自動(dòng)導(dǎo)航小車(Automated Guided Vehicle，AGV)在柔性生產(chǎn)系統(tǒng)的物料搬運(yùn)中發(fā)揮著越來越重要的作用。隨著AGV的廣泛應(yīng)用，隨之帶來的問題也不斷增加，其中路徑規(guī)劃是這一領(lǐng)域的重點(diǎn)問題。如何對(duì)AGV進(jìn)行合理的規(guī)劃，以提高物料搬運(yùn)效率和降低生產(chǎn)成本一直是企業(yè)關(guān)注的焦點(diǎn)。目前，國(guó)內(nèi)外已有許多學(xué)者對(duì)AGV路徑規(guī)劃問題進(jìn)行研究：文獻(xiàn)[5]中采用改進(jìn)的A*算法對(duì)智能車路徑進(jìn)行優(yōu)化；文獻(xiàn)[6]中應(yīng)用多種群遺傳算法對(duì)路徑規(guī)劃進(jìn)行研究;文獻(xiàn)[7]中提出了一種自適應(yīng)遺傳算法的路徑規(guī)劃方法,采用了人工勢(shì)場(chǎng)對(duì)種群初始化,提高了算法收斂速度；文獻(xiàn)[8]中應(yīng)用Voronoi圖法對(duì)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃；文獻(xiàn)[9]中提出了一種混合算法解決移動(dòng)機(jī)器人全局路徑規(guī)劃問題,提高AGV路徑的質(zhì)量；文獻(xiàn)[10]中將一種新的變異方法應(yīng)用到機(jī)器人動(dòng)態(tài)路徑規(guī)劃中；文獻(xiàn)[11]中在遺傳算法中加入轉(zhuǎn)彎角度因素對(duì)移動(dòng)機(jī)器人路徑規(guī)劃進(jìn)行分析；文獻(xiàn)[12]中提出一種新的基于排序遺傳算法的多目標(biāo)最優(yōu)路徑規(guī)劃；文獻(xiàn)[13]中提出了縱橫協(xié)同的多種群遺傳算法解決AGV調(diào)度問題；文獻(xiàn)[14]中采用了整數(shù)編碼和多參數(shù)編碼相結(jié)合的方式對(duì)遺傳算法進(jìn)行改進(jìn)，優(yōu)化AGV的任務(wù)排序列表以及行走路徑。

本文作者在傳統(tǒng)遺傳算法基礎(chǔ)上對(duì)編碼規(guī)則、變異算子以及交叉算子進(jìn)行改進(jìn)，在AGV數(shù)量及補(bǔ)料工位數(shù)量不同的情況下，擬優(yōu)化出任務(wù)最短路徑及排序，期望得到最優(yōu)方案。

1 問題描述

在柔性生產(chǎn)系統(tǒng)中，通常存在一個(gè)集中配料區(qū)，有序存放車間生產(chǎn)所需所有物料資源，當(dāng)有工位加工物料低于存儲(chǔ)安全值時(shí)，就需要AGV及時(shí)為其補(bǔ)充物料。在生產(chǎn)過程中，可能出現(xiàn)多個(gè)工位同時(shí)需要AGV為其補(bǔ)充物料的情況，這時(shí)候就需要對(duì)AGV補(bǔ)料的順序及路徑進(jìn)行優(yōu)化，使AGV在最短的時(shí)間內(nèi)為所有工位完成補(bǔ)料任務(wù)。本文作者在此基礎(chǔ)上以多個(gè)AGV 同時(shí)服務(wù)于多個(gè)工位為背景，對(duì)AGV路徑規(guī)劃進(jìn)行研究，擬達(dá)到降低AGV運(yùn)行成本及車間生產(chǎn)成本的目的。

對(duì)于AGV路徑規(guī)劃問題現(xiàn)做出如下假設(shè)：

(1)AGV出發(fā)點(diǎn)(物料存儲(chǔ)地)固定;

(2)上下料時(shí)間恒定且固定，故忽略不計(jì);

(3)任何任務(wù)都可以分配給任何一臺(tái)AGV;

(4)AGV容量足夠大，且無差別;

(5)同一任務(wù)只能被一臺(tái)AGV所執(zhí)行。

2 數(shù)學(xué)模型

柔性生產(chǎn)車間AGV調(diào)度問題可描述為輛AGV服務(wù)個(gè)工位，AGV編號(hào)為:∈{1,2,3，…，}，工位編號(hào)為:∈{1,2,3,…,}，AGV任務(wù)編號(hào)為:∈{1,2,3,…,}。染色體用表示,現(xiàn)根據(jù)以上約束條件及假設(shè)，建立如下數(shù)學(xué)模型：

(1)

(2)

0=0 ?,

(3)

=1 ?

(4)

其中：式(1)表示總路徑長(zhǎng)度為各AGV路徑長(zhǎng)度總和；式(2)表示每輛AGV的每個(gè)任務(wù)只為一個(gè)工位進(jìn)行補(bǔ)料；式(3)表示每輛AGV執(zhí)行任務(wù)前統(tǒng)一在初始位置集合；式(4)表示每輛AGV可裝載量足夠且固定。

3 改進(jìn)的遺傳算法

遺傳算法(Genetic Algorithm)是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)制的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。傳統(tǒng)的遺傳算法雖能尋找到最優(yōu)解，但是在求解速度以及局部最優(yōu)解問題的處理上并不理想。本文作者在傳統(tǒng)的遺傳算法基礎(chǔ)上對(duì)編碼、解碼、變異算子及交叉算子進(jìn)行改進(jìn)，應(yīng)用改進(jìn)的遺傳算法求解問題，以達(dá)到準(zhǔn)確、快速、高效解決問題的目的。

3.1 編碼設(shè)計(jì)

傳統(tǒng)的遺傳算法中編碼方法有二進(jìn)制編碼、浮點(diǎn)數(shù)編碼、實(shí)數(shù)編碼。針對(duì)文中所研究的內(nèi)容，提出一種雙層實(shí)數(shù)編碼方式：將染色體分為前后兩部分：前一部分代表工位編號(hào)(工位編號(hào)先后即AGV補(bǔ)料順序先后)；后一部分為AGV編號(hào)。例如：一條染色體為“2354113213”，其含義如圖1所示。

圖1 染色體編碼

基于以上染色體編碼方式其讀取方式為：第一輛AGV補(bǔ)料任務(wù)地點(diǎn)為工位1、工位4；第二輛AGV補(bǔ)料任務(wù)地點(diǎn)為工位3；第三輛AGV補(bǔ)料地點(diǎn)為工位2、工位5。

染色體編碼后按上述讀取規(guī)則對(duì)AGV行走路徑進(jìn)行解碼，通過讀取AGV行走路徑及搬運(yùn)順序記錄染色體目標(biāo)值。個(gè)體的適應(yīng)度函數(shù)()定義如下：

式中：()為第輛AGV行走總路徑之和。將所有AGV行走路徑之和加在一起組成個(gè)體的適應(yīng)度函數(shù)。根據(jù)上述定義可知，個(gè)體適應(yīng)度值越大，目標(biāo)值越小。當(dāng)目標(biāo)值最小時(shí)，得出最優(yōu)解。

3.2 初始種群的生成

由于文中在染色體生成時(shí)使用雙層編碼方式，同時(shí)滿足兩個(gè)變量要求：工位數(shù)和AGV數(shù)，所以傳統(tǒng)的種群生成方式不適用。文中初始種群的生成具體步驟如下：

(1)根據(jù)工位的數(shù)量確定第一層工位編碼范圍[1,…,]；

(2)根據(jù)可調(diào)用AGV數(shù)量確定第二層AGV編碼范圍[1,…,]；

(3)將第一層與第二層組成一條完整的染色體序列；

(4)重復(fù)步驟3、4，生成一組含有多個(gè)染色體的初始種群。

3.3 變異算子

變異操作是遺傳算法中一個(gè)重要的過程，變異算子的主要作用是改善系統(tǒng)的全局搜索能力，維持種群的多樣性。過小的變異率會(huì)導(dǎo)致新生成的種群產(chǎn)生新個(gè)體的能力較弱，抑制早熟現(xiàn)象的能力變差；過大的變異率會(huì)使系統(tǒng)隨機(jī)性更大，增加不必要的計(jì)算。本文作者在綜合考慮其影響因素后，提出一種變異方法：雙層編碼多次變異。多次的變異過程不僅增大了解的空間，而且維持了種群的多樣性，降低了算法陷入局部最優(yōu)解的概率。具體步驟如圖2所示。

圖2 變異過程

改進(jìn)的變異操作在第一層編碼的兩點(diǎn)變異后加入了逆轉(zhuǎn)變異以及滑動(dòng)變異來增大解的空間，增強(qiáng)算法的搜索能力，可以更好地找到最優(yōu)解。逆轉(zhuǎn)變異及滑動(dòng)變異具體原理如圖3—圖4所示(由于只對(duì)第一層編碼有效，示例僅編寫第一層編碼)：

(1)逆轉(zhuǎn)變異。在變異前產(chǎn)生隨機(jī)數(shù)<，例如=4，即染色體前4位進(jìn)行逆轉(zhuǎn)變異，由原始“53214”變?yōu)椤?2354”，如圖3所示。

圖3 逆轉(zhuǎn)變異

(2)滑動(dòng)變異。首先將原始染色體復(fù)制，組成一條新的染色體=[,]，長(zhǎng)度為二倍；其次生成隨機(jī)數(shù)<，取的第位到第+-1位為新染色體,如圖4所示。

圖4 滑動(dòng)變異

3.4 交叉操作

交叉算子是遺傳算法中控制全局搜索的一種算子，算子大小的調(diào)試對(duì)整個(gè)算法有重要影響：較大的交叉算子會(huì)增強(qiáng)算法開辟新的搜索區(qū)域的能力，但是過大的算子會(huì)增加不必要的計(jì)算成本；當(dāng)交叉算子過小時(shí)，系統(tǒng)會(huì)陷入遲鈍狀態(tài)，在搜索新個(gè)體時(shí)速度變慢，導(dǎo)致運(yùn)行停滯，增大運(yùn)行時(shí)間。基于雙層編碼方式對(duì)染色體進(jìn)行雙層兩點(diǎn)交叉，即對(duì)染色體第一、二層同時(shí)進(jìn)行兩點(diǎn)交叉。首先將所有染色體分為兩兩一組，組成若干個(gè)染色體對(duì)，為每個(gè)染色體對(duì)分配隨機(jī)數(shù)，當(dāng)0.5時(shí)，對(duì)染色體第二層進(jìn)行交叉，交換兩染色體AGV編號(hào)，產(chǎn)生新的染色體。相較于原染色體，新染色體為相同補(bǔ)料工位使用不同的AGV來完成任務(wù)，增加了補(bǔ)料工位分配任務(wù)的解空間。交叉完成后對(duì)于第一層染色體片段工位編碼部分，可能會(huì)出現(xiàn)重復(fù)工位的可能，因此在交叉后會(huì)對(duì)交叉后的染色體進(jìn)行修補(bǔ)：取交叉片段補(bǔ)集隨機(jī)排列到非交叉片段。具體過程如圖5—圖6所示。

圖5 染色體修補(bǔ)過程

圖6 交叉過程

3.5 迭代終止條件

迭代終止條件在遺傳算法中控制著算法運(yùn)行時(shí)間長(zhǎng)短：過小的終止條件會(huì)讓算法在未尋找到最優(yōu)值時(shí)停止，而沒有完成任務(wù)；過大則會(huì)增加算法不必要的過程，增加程序運(yùn)行成本。在遺傳算法中終止迭代有多種方法：(1)人為設(shè)置種群在迭代多次后強(qiáng)行終止，這種情況一般設(shè)置迭代次數(shù)為20～500之間；(2)當(dāng)種群在多次迭代后目標(biāo)值沒有發(fā)生變化時(shí)停止迭代；(3)當(dāng)?shù)蟮慕Y(jié)果小于人為設(shè)定的值時(shí)，程序停止運(yùn)行。文中選用第一種：當(dāng)?shù)螖?shù)為20～500代時(shí)，終止程序。這種方法會(huì)讓程序變得更加可控，在不斷觀察運(yùn)行結(jié)果時(shí)調(diào)整參數(shù)，以達(dá)到最優(yōu)的效果。

4 仿真實(shí)驗(yàn)與分析

環(huán)境地圖中最多有20個(gè)工位，將各工位置于-坐標(biāo)系中并計(jì)算其坐標(biāo)，結(jié)果如圖7所示。

圖7 工位點(diǎn)坐標(biāo)

以此坐標(biāo)作為地圖，應(yīng)用改進(jìn)的遺傳算法分別對(duì)相同工位數(shù)量、不同AGV數(shù)量以及相同AGV數(shù)量、不同工位數(shù)量在不同節(jié)拍要求下進(jìn)行仿真實(shí)驗(yàn)，通過對(duì)比計(jì)算出約束下的最優(yōu)方案。此算法中基本參數(shù)設(shè)置如下：種群數(shù)量=100；選擇方式：輪盤賭選擇；變異率：PM=0.1；交叉率：PC=0.7。迭代次數(shù)：當(dāng)工位數(shù)量較多時(shí)=500，工位數(shù)低于10時(shí)=300。部分仿真結(jié)果如圖8所示。

圖8 20工位4車優(yōu)化結(jié)果

以20個(gè)工位為例：當(dāng)車間共有20個(gè)工位需要補(bǔ)料時(shí)，應(yīng)用改進(jìn)的遺傳算法即可優(yōu)化出在固定節(jié)拍要求下的最優(yōu)路徑及最優(yōu)AGV數(shù)量，當(dāng)節(jié)拍允許范圍為100 s以下時(shí)，評(píng)估車輛成本及時(shí)間差成本選擇最優(yōu)車輛為4輛，由圖8可知AGV1運(yùn)輸路徑為：16→18→1→2；AGV2運(yùn)輸路徑為：12→5；AGV3運(yùn)輸路徑為：17→11→9→20→15→6→14→19；AGV4運(yùn)輸路徑為：8→10→7→4→13→3。圖9只是其中一種結(jié)果。如表1所示：完成任務(wù)時(shí)總運(yùn)行距離為399.6 m；平均節(jié)拍為99.9 s。相對(duì)于傳統(tǒng)算法AGV行走路徑長(zhǎng)度縮短了74.8 m，平均節(jié)拍減少了18.7 s，在節(jié)約成本的同時(shí)縮短了完成任務(wù)的工期，證明了文中算法的實(shí)用性。

圖9 20工位4車仿真結(jié)果

表1 不同工位-AGV組合比較

5 結(jié)束語

本文作者在不同條件背景下對(duì)多AGV多任務(wù)模式調(diào)度問題進(jìn)行研究，應(yīng)用改進(jìn)的遺傳算法對(duì)模型進(jìn)行優(yōu)化，當(dāng)任務(wù)較多時(shí)，改進(jìn)的遺傳算法無論從AGV行走距離、任務(wù)完成時(shí)間、迭代次數(shù)等方面都優(yōu)于傳統(tǒng)遺傳算法，從而證明了算法的有效性；隨后應(yīng)用于模型中并達(dá)到了預(yù)期效果，也證明改進(jìn)算法的實(shí)用性。通過算法對(duì)AGV進(jìn)行調(diào)度，使工廠變得更加數(shù)字化、智能化、科學(xué)化，同時(shí)響應(yīng)智慧工廠發(fā)展趨勢(shì)。