面向生產(chǎn)車間的單車路徑優(yōu)化算法研究

陳澤宇，馮子驍，宋佳員

（1.河海大學(xué)機(jī)電學(xué)院，江蘇 常州213022；2.河海大學(xué)物聯(lián)網(wǎng)學(xué)院，江蘇 常州213022）

1 引言

自動(dòng)引導(dǎo)小車（Automated Guided Vehicle，AGV）在20 世紀(jì)50 年代被首次提出。作為一種智能搬運(yùn)設(shè)備，由于其自動(dòng)化程度高、易于控制等優(yōu)點(diǎn)，廣泛應(yīng)用于倉(cāng)儲(chǔ)、物流行業(yè)。在一些加工車間內(nèi)，使用AGV 來(lái)搬運(yùn)物料，能有效節(jié)約勞動(dòng)成本和提高工作效率，因此對(duì)AGV 應(yīng)用的研究極為重要，其中如何設(shè)置AGV 的路徑直接影響企業(yè)生產(chǎn)效率和成本，需要對(duì)其進(jìn)行深刻研究。

目前求解AGV 最優(yōu)路徑主要采用的是人工智能的算法，比如蟻群算法[1-2]、粒子群算法[3]、神經(jīng)網(wǎng)絡(luò)算法[4]、快速擴(kuò)展隨機(jī)樹(shù)尋路算法[5]以及遺傳算法[6-7]。這些有群體智能的算法都有正反饋機(jī)制和較優(yōu)的擴(kuò)展性，在路徑規(guī)劃和旅行商問(wèn)題（TSP）[8-10]中被成功應(yīng)用。文獻(xiàn)[1]中使用了優(yōu)化后的蟻群算法，相較于傳統(tǒng)算法避免了尋優(yōu)的盲目性，從而提高了算法效率。文獻(xiàn)[3]中使用三角函數(shù)變化方式對(duì)其參數(shù)進(jìn)行自適應(yīng)調(diào)整，并加入雞群算法去除擾動(dòng)，有效避免了算法停滯。文獻(xiàn)[4]采用的是基于神經(jīng)網(wǎng)絡(luò)算法來(lái)規(guī)劃?rùn)C(jī)器人移動(dòng)路徑，縮短了搜尋時(shí)間。而其中遺傳算法雖然提出時(shí)間較早，但是由于其是多點(diǎn)式搜索，更有可能搜索到全局的最優(yōu)解，所以如今多數(shù)路徑規(guī)劃問(wèn)題仍可以用遺傳算法去求解。但是傳統(tǒng)的遺傳算法有自身固有缺點(diǎn)，比如容易早熟、收斂效果差的缺點(diǎn)，因此，在使用時(shí)必須對(duì)其進(jìn)行改進(jìn)。本文提出的改進(jìn)型遺傳算法，是在傳統(tǒng)遺傳算法基礎(chǔ)上，對(duì)其中交叉和變異過(guò)程進(jìn)行優(yōu)化，提高算法計(jì)算效率，縮短計(jì)算時(shí)間，獲得更好的搜索結(jié)果。

2 模型建立

對(duì)于研究AGV 的路徑規(guī)劃問(wèn)題，首先要建立合適的地圖模型，常用的方法有可視圖法[11-12]、傳統(tǒng)柵格法[13]和人工勢(shì)場(chǎng)法[14-15]。其中柵格法（grid method）具有簡(jiǎn)單、易于表達(dá)和靈活等優(yōu)點(diǎn)，所以本文采用柵格法建立AGV 地圖模型。如圖1 所示，黑色區(qū)域表示障礙或者機(jī)器，白色區(qū)域AGV可以行駛，行駛方向?yàn)锳GV 所在格的周圍八個(gè)柵格。此外，此柵格可以坐標(biāo)化便于之后遺傳信息的編寫和路徑長(zhǎng)度計(jì)算。本文之后的算法都在此柵格地圖的基礎(chǔ)上進(jìn)行求解。

圖1 地圖柵格模型

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

3.1 改進(jìn)型遺傳算法模型

遺傳算法是模擬達(dá)爾文進(jìn)化論所創(chuàng)建的，根據(jù)生物遺傳和進(jìn)化的特點(diǎn)和步驟，引入了基因復(fù)制、交叉突變等遺傳信息的處理方式，并且采用了進(jìn)化論中適者生存的法則，對(duì)基因信息進(jìn)行篩選。

本文提出的改進(jìn)型遺傳算法來(lái)求解最優(yōu)路徑，首先會(huì)產(chǎn)生第一代中會(huì)產(chǎn)生多條路徑，記為1iL。其中，下標(biāo)i表示第一代的第i條路徑，上標(biāo)為代數(shù)，路徑由構(gòu)成路徑的坐標(biāo)點(diǎn)構(gòu)成，從點(diǎn)按順序排布，每一條路徑都能代表一個(gè)遺傳信息，如式（1）所示。

對(duì)于第一代所有路徑的集合記為C1，其中C1表示為：

之后計(jì)算C1中的長(zhǎng)度，記為，表示為：

比較之后選出這一代中路徑長(zhǎng)度最短的一組遺傳信息，將其路徑長(zhǎng)度作為之后評(píng)估的標(biāo)準(zhǔn)。

在獲取第一代信息后，對(duì)遺傳信息進(jìn)行復(fù)制，準(zhǔn)備下一步基因交叉和突變。復(fù)制時(shí)，根據(jù)每一條路徑的長(zhǎng)度和最短路徑的比值確定對(duì)應(yīng)遺傳信息的比值后設(shè)置一個(gè)復(fù)制閾值P0，如果比值低于這個(gè)閾值，則該遺傳信息不進(jìn)行復(fù)制，但這個(gè)值不能取太大，太大容易快速進(jìn)入局部最優(yōu)，損失部分可交換的遺傳信息，所以選擇合適的閾值有利于提高算法求解速度，且能提高算法的收斂性。

遺傳信息復(fù)制結(jié)束后需要對(duì)信息進(jìn)行重新結(jié)合，也就是“交叉重組”。交叉重組旨在擴(kuò)大搜索范圍，產(chǎn)生新品種的后代，為之后迭代復(fù)制提供資源，隨著復(fù)制過(guò)程中的篩選體現(xiàn)出優(yōu)勝劣汰的特點(diǎn)。該操作的過(guò)程是將已經(jīng)復(fù)制的遺傳信息進(jìn)行部分互換，找到兩組遺傳信息中共用的坐標(biāo)點(diǎn)，對(duì)其進(jìn)行前后段互換，即可得到一個(gè)新的遺傳信息，擴(kuò)大遺傳算法的搜索。具體先任選一個(gè)信息設(shè)為，然后算出該信息與其他信息之間的路徑的距離如式（4）所示。

i

0

i

按照此概率選擇方式完成一對(duì)信息配對(duì)后，將所有信息都進(jìn)行同樣的操作，之后對(duì)每一對(duì)信息組中的公共點(diǎn)隨機(jī)選擇作為交叉節(jié)點(diǎn)，互換遺傳信息，完成一次“交叉重組“操作，得到第二代遺傳信息

3.2 改進(jìn)型遺傳算法流程

基于以上算法描述，得到改進(jìn)型遺傳算法的基本流程如下：①獲取第一代所有的遺傳信息，即初始信息集合；②對(duì)信息集合中每一條遺傳信息進(jìn)行計(jì)算評(píng)估，根據(jù)其評(píng)估值和閾值的對(duì)比，判斷信息是否有繼續(xù)遺傳下去的必要，如果沒(méi)有則去除此信息，如果有則進(jìn)行下一步；③復(fù)制選擇后的遺傳信息，作為交叉重組的基礎(chǔ)；④使每一條遺傳信息根據(jù)概率公式配對(duì)、重組，得到新一代信息集合；⑤判斷是否到達(dá)最大迭代數(shù)，若是則輸出最優(yōu)路徑，算法結(jié)束，若不是則重復(fù)步驟②～④，直到算法結(jié)束。

4 仿真分析

在MATLAB 軟件中對(duì)改進(jìn)型遺傳算法進(jìn)行了仿真實(shí)驗(yàn)，在25×25 的柵格地圖的背景下進(jìn)行計(jì)算，總共設(shè)置100次迭代，每一代中有50 條遺傳信息，計(jì)算結(jié)果顯示改進(jìn)型遺傳算法在算法求解時(shí)間和收斂效果上均與傳統(tǒng)算法相比有提升。

圖2 為通過(guò)改進(jìn)型遺傳算法求解出的AGV 最短運(yùn)動(dòng)軌跡圖。表1 為改進(jìn)型遺傳算法和傳統(tǒng)的遺傳算法的對(duì)比數(shù)據(jù)，每種算法各在相同情況下運(yùn)行10 次后求平均值。

圖2 AGV 最短路徑軌跡

在兩種算法所需計(jì)算時(shí)間方面，由表1 數(shù)據(jù)可知，改進(jìn)型遺傳算法由于在復(fù)制時(shí)提前進(jìn)行篩查排除一些極差遺傳信息，減去了大量后期交叉重組所需要的時(shí)間，減少了一定的計(jì)算量，使得計(jì)算時(shí)間由平均13.862 9 s 縮短至12.684 7 s，減少了8.49%。

在兩種算法所解最短路徑長(zhǎng)度方面，由于改進(jìn)型算法在引入了概率計(jì)算和去除極端信息時(shí)，有助于算法收斂，所以改進(jìn)型遺傳算法的最短路徑為38.627 4，而傳統(tǒng)遺傳的最短路徑為39.974 1，且10 次平均下來(lái)改進(jìn)型遺傳算法也要優(yōu)于傳統(tǒng)算法，體現(xiàn)出改進(jìn)后算法的優(yōu)良性質(zhì)。

表1 算法性能對(duì)比

5 總結(jié)

對(duì)于傳統(tǒng)遺傳算法在求解AGV 最短路徑規(guī)劃問(wèn)題時(shí)的一些不足，在傳統(tǒng)算法的基礎(chǔ)上，我們?cè)黾恿诉z傳信息復(fù)制階段的評(píng)估篩選和交叉重組階段的概率配對(duì)，以此來(lái)縮短算法計(jì)算時(shí)間和提高算法的收斂性。最后的仿真結(jié)果也證明了改進(jìn)型遺傳算法有優(yōu)于傳統(tǒng)遺傳算法之處。