基于改進(jìn)遺傳算法的預(yù)混料生產(chǎn)線(xiàn)配料車(chē)路徑優(yōu)化

付澤鵬， 張幗英

（1.沈陽(yáng)建筑大學(xué)， 遼寧沈陽(yáng) 110170； 2.內(nèi)蒙古北方重工集團(tuán)， 內(nèi)蒙古包頭 014033）

0 引言

隨著預(yù)混料工業(yè)的發(fā)展，企業(yè)對(duì)預(yù)混料生產(chǎn)效率的要求也越來(lái)越高。為了提高預(yù)混料生產(chǎn)線(xiàn)的生產(chǎn)效率，以配料車(chē)日生產(chǎn)量為基本目標(biāo)，建立了配料系統(tǒng)的數(shù)學(xué)模型，提出了配料車(chē)路徑優(yōu)化的具體方案， 通過(guò)改進(jìn)遺傳算法尋優(yōu)計(jì)算[1]，得到了配料車(chē)最佳路徑并確定了配料系統(tǒng)的優(yōu)化方案。在預(yù)混料的配料控制系統(tǒng)[2]中，配料車(chē)是有承上啟下作用的系統(tǒng)核心，它工作效率的高低直接影響整個(gè)配料系統(tǒng)的生產(chǎn)效率乃至整個(gè)預(yù)混料生產(chǎn)線(xiàn)的性能[3]。本文通過(guò)改進(jìn)遺傳算法對(duì)配料車(chē)的路徑進(jìn)行優(yōu)化，以保證最大工作效率。

1 問(wèn)題描述與建模

1.1 問(wèn)題描述

國(guó)內(nèi)的預(yù)混料生產(chǎn)企業(yè)，大多是雙配料車(chē)配料系統(tǒng)，但均未對(duì)配料車(chē)路徑進(jìn)行規(guī)劃， 采用按料倉(cāng)順序依次接料，配料車(chē)相遇時(shí)，停止等待，或采用兩車(chē)輪流作業(yè)等方式，使得一個(gè)配料周期達(dá)到10min 以上，生產(chǎn)效率低。 在這種情況下，通過(guò)算法優(yōu)化配料車(chē)的配料路徑，在避免兩車(chē)發(fā)生碰撞的同時(shí)，縮短配料周期，具有重要的意義。

本文根據(jù)實(shí)際配料系統(tǒng)的情況歸納了兩種優(yōu)化方案，在此基礎(chǔ)上進(jìn)行建模、仿真、比較，最終得出最優(yōu)的優(yōu)化方案。 兩種方案如下：

方案一：同步啟動(dòng)。兩輛配料車(chē)每次配料時(shí)同步啟動(dòng)，相遇時(shí)，兩車(chē)均可進(jìn)行避讓等待，先完成配料的配料車(chē)，等待另一輛完成配料后，再同時(shí)出發(fā)，進(jìn)行下一次配料。

方案二：異步啟動(dòng)。 兩輛配料車(chē)在任意時(shí)刻啟動(dòng)，后開(kāi)始的配料車(chē)對(duì)正在工作的配料車(chē)進(jìn)行避讓等待， 每次都是后啟動(dòng)的配料車(chē)對(duì)正在工作的配料車(chē)避讓等待，兩車(chē)按此規(guī)則配料。

1.2 建模

配料車(chē)根據(jù)配方完成接料，卸料過(guò)程的時(shí)間，是一個(gè)配料周期，本文把每日完成的周期數(shù)作為日生產(chǎn)量。 為了避免不相關(guān)因素干擾，本文將一些條件做如下假設(shè)：

配方是配料車(chē)要到達(dá)的工位（接料點(diǎn)、卸料點(diǎn)），位置已知；硩車(chē)和工位看作一個(gè)點(diǎn)，1、2 號(hào)配料車(chē)間距小于2個(gè)工位時(shí)視為碰撞；

在工位的停留時(shí)間即接料、卸料時(shí)間，與物料重量、成分相關(guān)；

配料車(chē)速度分三個(gè)檔，即快速、勻速和慢速。 距離目標(biāo)工位超過(guò)10m，采用快速檔行駛，距離小于1m 時(shí)，采用慢速檔，其他采用勻速檔。

1.2.1 方案一

兩輛配料車(chē)最大周期的最小值是最小配料周期Tm，生產(chǎn)量Ck最大，所以目標(biāo)函數(shù)為：

其中，T1和T2是1、2 號(hào)車(chē)的配料周期；Td—工作時(shí)間。

對(duì)于路徑優(yōu)化的配料周期可以描述為， 配料車(chē)按配方走完所有工位的行走時(shí)間及工位的停留時(shí)間， 加上避讓和等待時(shí)間。 若k 值代表1、2 號(hào)配料車(chē)，有n 個(gè)接料工位和始末兩個(gè)卸料工位的配方路徑集合記為：

1.2.2 方案二

兩輛配料車(chē)的配料周期Tk都最小，得到總生產(chǎn)量Ck最大，故目標(biāo)函數(shù)為：

配料車(chē)行走時(shí)間tij，約束條件同公式（5）、式（7）。

由于2 號(hào)車(chē)的配料路徑已確定，1 號(hào)車(chē)每次向下一個(gè)工位行走時(shí)都進(jìn)行判斷。 根據(jù)產(chǎn)生等待避讓時(shí)間的情況得到1 號(hào)配料車(chē)在i 工位的等待和避讓時(shí)間為

2 改進(jìn)遺傳算法

配料車(chē)路徑優(yōu)化問(wèn)題屬于復(fù)雜路徑優(yōu)化問(wèn)題， 遺傳算法具有獨(dú)特的算法形式和運(yùn)行機(jī)理[4]，在復(fù)雜路徑優(yōu)化問(wèn)題的求解中有著明顯的優(yōu)勢(shì)[5]，有效解決了其解空間不連續(xù)、解領(lǐng)域表達(dá)困難等問(wèn)題，故在本文中用遺傳算法來(lái)求解路徑優(yōu)化的模型。

傳統(tǒng)遺傳算法執(zhí)行效率通常不高，且容易出現(xiàn)過(guò)早收斂的問(wèn)題。 提高配料系統(tǒng)效率必須提高執(zhí)行效率和計(jì)算結(jié)果的準(zhǔn)確性，盡量避免過(guò)早收斂的問(wèn)題。傳統(tǒng)遺傳算法的結(jié)構(gòu)是以交叉操作為基礎(chǔ)進(jìn)行的變異操作， 認(rèn)為交叉作用更大，而變異只是一個(gè)生物學(xué)背景機(jī)制。對(duì)于交叉變異的具體操作，交叉采用均勻交叉、單點(diǎn)交叉、多點(diǎn)交叉等，變異采用Guassian 分布[6-7]或Cauchy 分布[8]的隨機(jī)變異。 后經(jīng)Rudolph 的理論分析[9]，Chellailla 進(jìn)一步把二者結(jié)合起來(lái)[10]，但改進(jìn)效果并不明顯。 根據(jù)《混沌學(xué)導(dǎo)論》[11]將生物進(jìn)化看成是系統(tǒng)內(nèi)部隨機(jī)性加上反饋的特點(diǎn)，根據(jù)以上特點(diǎn)本文對(duì)基于求解路徑規(guī)劃的遺傳算法進(jìn)行改進(jìn)[12]，既確保算法收斂精度，又避免算法早熟。

本文從算法結(jié)構(gòu)到具體的遺傳操作都進(jìn)行了改進(jìn)，具體改進(jìn)方式如下：

（1）算法結(jié)構(gòu)。本文將遺傳算法中的變異、交叉分開(kāi)操作，使得遺傳算法可以通過(guò)并行計(jì)算來(lái)提高實(shí)現(xiàn)的效率。

（2）交叉操作。交叉操作按父代個(gè)體的適應(yīng)度函數(shù)值或者目標(biāo)函數(shù)值大小，進(jìn)行“大對(duì)大、小對(duì)小”原則配對(duì)。然后由混沌序列確定交叉點(diǎn)的位置，進(jìn)行交叉操作。這種單點(diǎn)交叉對(duì)原解改動(dòng)很小， 可以減少遺傳算法在組合優(yōu)化應(yīng)用中產(chǎn)生的尋優(yōu)抖振問(wèn)題，提高算法收斂精度。

（3）變異操作。 變異操作由幾個(gè)隨機(jī)整數(shù)確定變異的基因位置，利用混沌序列得到數(shù)值作為新的基因值，進(jìn)而得到變異后的染色體。這樣采用較大強(qiáng)度的多個(gè)基因變異正好解決了單一的單點(diǎn)交叉很容易使算法早熟的問(wèn)題。

算法的流程如圖1 所示。

圖1 遺傳算法流程圖

3 案例分析

以某企業(yè)預(yù)混料生產(chǎn)線(xiàn)為例，該生產(chǎn)線(xiàn)的兩個(gè)配料車(chē)根據(jù)配方按料倉(cāng)從左到右依次接料，兩車(chē)等待避讓時(shí)間很長(zhǎng)，生產(chǎn)效率低下。

該配料系統(tǒng)有46 個(gè)雙列結(jié)構(gòu)的料倉(cāng)，6 個(gè)卸料口。料倉(cāng)兩兩并排共用一個(gè)下料口，占用一個(gè)工位，料倉(cāng)編號(hào)1～23，卸料口編號(hào)為24～29。 其中9～15 號(hào)料倉(cāng)和26、27 號(hào)卸料口屬于公共配料區(qū)。兩輛配料車(chē)分別生產(chǎn)兩種不同物料，且均不超過(guò)公共配區(qū)去接料，不在公共區(qū)卸料，在各自區(qū)域的卸料口輪流下料。 其結(jié)構(gòu)見(jiàn)圖2。

圖2 預(yù)混料生產(chǎn)線(xiàn)簡(jiǎn)圖

已知如下條件：

（1）工位位置：由現(xiàn)場(chǎng)傳感器測(cè)得；

（2）配方：以企業(yè)最常用的兩種配方為例，1、2 號(hào)車(chē)配方集合分別為[25，1，4，6，8，9，11，12，13，15，24]，[28，9，10，11，12，13，15，17，18，20，29]；

（3）停留時(shí)間：1、2 號(hào)車(chē)對(duì)應(yīng)配方工位的停留時(shí)間集合分別為[0，26，28，20，35，23，36，25，15，21，45]，[0，9，20，11，15，20，15，29，16，25，30，30]；

（4）行駛速度：配料車(chē)三個(gè)速度檔為60m/min、40m/min、10m/min；

（5）仿真參數(shù)：種群大小初值20，迭代次數(shù)200。

運(yùn)用Matlab 編程進(jìn)行如下仿真實(shí)驗(yàn)。

方案一： 通過(guò)仿真計(jì)算得到的兩車(chē)配料車(chē)路徑和最優(yōu)解周期與進(jìn)化代數(shù)見(jiàn)圖3，圖4。

圖3 配料車(chē)路徑圖

圖4 每代最優(yōu)解與進(jìn)化代數(shù)

由仿真結(jié)果得到的兩車(chē)最優(yōu)路徑分別為：[25，7，5，4，8，11，12，13，15，1，24]和[28，9，10，11，15，12，13，20，17，18，29]。配料周期為397.1s。計(jì)算周期取20 次的平均值用于本文的方案對(duì)比，平均值為396.6s。

方案二： 假設(shè)某次配料中，2 號(hào)配料車(chē)未完成的路徑集合為[12，9，15，11，17，18，28]時(shí)，1 號(hào)車(chē)開(kāi)始配料。 通過(guò)仿真得到如圖5，圖6 所示。

圖5 配料車(chē)路徑圖

圖6 每代最優(yōu)解與進(jìn)化代數(shù)

由仿真結(jié)果得到的1 號(hào)車(chē)最優(yōu)路徑為：[25，5，7，8，15，13，12，11，4，1，24]。 配料周期387.0s。

在下次2 號(hào)配料車(chē)配料中，1 號(hào)車(chē)未完成的路徑集合為[13，12，11，4，1，24]。 仿真得到如圖7，圖8 所示。

圖7 配料車(chē)路徑圖

圖8 每代最優(yōu)解與進(jìn)化代數(shù)

圖8 Ⅰ型和Ⅱ型控制器誤差Fig.8 Error ofⅠandⅡcontroller

由仿真結(jié)果得到的2 號(hào)車(chē)最優(yōu)路徑為：[28，20，15，13，12，11，10，9，17，18，29]，周期時(shí)間317.8s。

由于方案二每次配料都需要重新規(guī)劃路徑，計(jì)算周期取10 次的平均值用于本文的方案對(duì)比， 仿真得到的兩輛配料車(chē)10 次配料周期取平均值分別為389.7s 和318.6s。

算法仿真得到的最優(yōu)解，與原方案相比配料周期縮短了30%左右， 同步方案兩種物料生產(chǎn)量均約為73 批/天，異步方案兩種物料生產(chǎn)量分別約為74 批/天和90 批/天。

從配料車(chē)路徑圖可以看出， 通過(guò)算法優(yōu)化避免了相遇問(wèn)題，使同步方案避讓靈活的優(yōu)勢(shì)并沒(méi)有作用，反而在等待同步啟動(dòng)的過(guò)程中花費(fèi)更多的時(shí)間。相比之下，異步方案時(shí)間利用充分，啟停靈活，更適合應(yīng)用在規(guī)劃路徑方案中。

4 結(jié)論

基于改進(jìn)遺傳設(shè)計(jì)的方案均能減小配料周期， 提高配料系統(tǒng)生產(chǎn)效率。 異步方案比同步方案在效率和便捷性方面都更佳。 本文設(shè)計(jì)的配料車(chē)路徑優(yōu)化方案對(duì)企業(yè)提高生產(chǎn)率有一定參考價(jià)值。