基于改進遺傳算法的預混料生產線配料車路徑優化

付澤鵬， 張幗英

（1.沈陽建筑大學， 遼寧沈陽 110170； 2.內蒙古北方重工集團， 內蒙古包頭 014033）

0 引言

隨著預混料工業的發展，企業對預混料生產效率的要求也越來越高。為了提高預混料生產線的生產效率，以配料車日生產量為基本目標，建立了配料系統的數學模型，提出了配料車路徑優化的具體方案， 通過改進遺傳算法尋優計算[1]，得到了配料車最佳路徑并確定了配料系統的優化方案。在預混料的配料控制系統[2]中，配料車是有承上啟下作用的系統核心，它工作效率的高低直接影響整個配料系統的生產效率乃至整個預混料生產線的性能[3]。本文通過改進遺傳算法對配料車的路徑進行優化，以保證最大工作效率。

1 問題描述與建模

1.1 問題描述

國內的預混料生產企業，大多是雙配料車配料系統，但均未對配料車路徑進行規劃， 采用按料倉順序依次接料，配料車相遇時，停止等待，或采用兩車輪流作業等方式，使得一個配料周期達到10min 以上，生產效率低。 在這種情況下，通過算法優化配料車的配料路徑，在避免兩車發生碰撞的同時，縮短配料周期，具有重要的意義。

本文根據實際配料系統的情況歸納了兩種優化方案，在此基礎上進行建模、仿真、比較，最終得出最優的優化方案。 兩種方案如下：

方案一：同步啟動。兩輛配料車每次配料時同步啟動，相遇時，兩車均可進行避讓等待，先完成配料的配料車，等待另一輛完成配料后，再同時出發，進行下一次配料。

方案二：異步啟動。 兩輛配料車在任意時刻啟動，后開始的配料車對正在工作的配料車進行避讓等待， 每次都是后啟動的配料車對正在工作的配料車避讓等待，兩車按此規則配料。

1.2 建模

配料車根據配方完成接料，卸料過程的時間，是一個配料周期，本文把每日完成的周期數作為日生產量。 為了避免不相關因素干擾，本文將一些條件做如下假設：

配方是配料車要到達的工位（接料點、卸料點），位置已知；硩車和工位看作一個點，1、2 號配料車間距小于2個工位時視為碰撞；

在工位的停留時間即接料、卸料時間，與物料重量、成分相關；

配料車速度分三個檔，即快速、勻速和慢速。 距離目標工位超過10m，采用快速檔行駛，距離小于1m 時，采用慢速檔，其他采用勻速檔。

1.2.1 方案一

兩輛配料車最大周期的最小值是最小配料周期Tm，生產量Ck最大，所以目標函數為：

其中，T1和T2是1、2 號車的配料周期；Td—工作時間。

對于路徑優化的配料周期可以描述為， 配料車按配方走完所有工位的行走時間及工位的停留時間， 加上避讓和等待時間。 若k 值代表1、2 號配料車，有n 個接料工位和始末兩個卸料工位的配方路徑集合記為：

1.2.2 方案二

兩輛配料車的配料周期Tk都最小，得到總生產量Ck最大，故目標函數為：

配料車行走時間tij，約束條件同公式（5）、式（7）。

由于2 號車的配料路徑已確定，1 號車每次向下一個工位行走時都進行判斷。 根據產生等待避讓時間的情況得到1 號配料車在i 工位的等待和避讓時間為

2 改進遺傳算法

配料車路徑優化問題屬于復雜路徑優化問題， 遺傳算法具有獨特的算法形式和運行機理[4]，在復雜路徑優化問題的求解中有著明顯的優勢[5]，有效解決了其解空間不連續、解領域表達困難等問題，故在本文中用遺傳算法來求解路徑優化的模型。

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

本文從算法結構到具體的遺傳操作都進行了改進，具體改進方式如下：

（1）算法結構。本文將遺傳算法中的變異、交叉分開操作，使得遺傳算法可以通過并行計算來提高實現的效率。

（2）交叉操作。交叉操作按父代個體的適應度函數值或者目標函數值大小，進行“大對大、小對小”原則配對。然后由混沌序列確定交叉點的位置，進行交叉操作。這種單點交叉對原解改動很小， 可以減少遺傳算法在組合優化應用中產生的尋優抖振問題，提高算法收斂精度。

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

算法的流程如圖1 所示。

圖1 遺傳算法流程圖

3 案例分析

以某企業預混料生產線為例，該生產線的兩個配料車根據配方按料倉從左到右依次接料，兩車等待避讓時間很長，生產效率低下。

該配料系統有46 個雙列結構的料倉，6 個卸料口。料倉兩兩并排共用一個下料口，占用一個工位，料倉編號1～23，卸料口編號為24～29。 其中9～15 號料倉和26、27 號卸料口屬于公共配料區。兩輛配料車分別生產兩種不同物料，且均不超過公共配區去接料，不在公共區卸料，在各自區域的卸料口輪流下料。 其結構見圖2。

圖2 預混料生產線簡圖

已知如下條件：

（1）工位位置：由現場傳感器測得；

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

（3）停留時間：1、2 號車對應配方工位的停留時間集合分別為[0，26，28，20，35，23，36，25，15，21，45]，[0，9，20，11，15，20，15，29，16，25，30，30]；

（4）行駛速度：配料車三個速度檔為60m/min、40m/min、10m/min；

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

運用Matlab 編程進行如下仿真實驗。

方案一： 通過仿真計算得到的兩車配料車路徑和最優解周期與進化代數見圖3，圖4。

圖3 配料車路徑圖

圖4 每代最優解與進化代數

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

方案二： 假設某次配料中，2 號配料車未完成的路徑集合為[12，9，15，11，17，18，28]時，1 號車開始配料。 通過仿真得到如圖5，圖6 所示。

圖5 配料車路徑圖

圖6 每代最優解與進化代數

由仿真結果得到的1 號車最優路徑為：[25，5，7，8，15，13，12，11，4，1，24]。 配料周期387.0s。

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

圖7 配料車路徑圖

圖8 每代最優解與進化代數

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

由仿真結果得到的2 號車最優路徑為：[28，20，15，13，12，11，10，9，17，18，29]，周期時間317.8s。

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

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

從配料車路徑圖可以看出， 通過算法優化避免了相遇問題，使同步方案避讓靈活的優勢并沒有作用，反而在等待同步啟動的過程中花費更多的時間。相比之下，異步方案時間利用充分，啟停靈活，更適合應用在規劃路徑方案中。

4 結論

基于改進遺傳設計的方案均能減小配料周期， 提高配料系統生產效率。 異步方案比同步方案在效率和便捷性方面都更佳。 本文設計的配料車路徑優化方案對企業提高生產率有一定參考價值。