改進遺傳算法在ETV 調度優化中的應用研究

郭春暉 （蘭州交通大學 機電技術研究所，甘肅 蘭州730070）

GUO Chun-hui (Institute of Electrical and Mechanical Technology, Lanzhou Jiaotong University, Lanzhou 730070, China)

0 引 言

圖1 為大型貨運站集裝貨物立體庫的平面布置示意圖，它由以下四大部分組成：（1） ULD 輥道式立體貨架，是ULD 貨物的存放單元。 （2） 升降式轉運車（ETV），在貨位之間的地面軌道上行走，實現貨架上貨物的存入或取出。（3） 集裝貨物分解組合系統與直通轉運系統設備，用于集裝貨物的分解、組合等任務。（4） 管理控制中心，負責整個貨運站的信息數據處理、監控終端、相關電氣控制設備的運行[1]。

ETV 在地面軌道上穿梭，完成集裝貨物的出、入庫任務。操作員或管理中心將取、送貨的信息發送給ETV 的控制計算機，由計算機控制ETV 的運動。在任務量高峰時，如果ETV 執行存、取貨任務過程中接收到新的任務指令，控制計算機會把新的命令加入到任務隊列等待執行。但在實際的貨運站內，尤其在任務密集的時間段，ETV 調度算法的優劣往往成為物流系統中的制約環節，所以針對ETV 的調度進行優化顯得尤為關鍵。

1 ETV 運行的數學模型建立

選擇ETV 的運動模型時，本文使用柔性S 型加減速度算法[2]。提出一種七段S 型加減速度算法，但該算法缺點是計算量大。五段S 型加減速算法與七段相比，省略勻加速和勻減速階段，在保持速度平滑性的同時，大大降低了計算復雜度[3]。圖2為五段S 型算法中速度V，加速度a，加速圓角參數j隨時間的變化規律。T1為加加速和減加速時間；T2為勻速時間；T3為加減速和減減速時間。

根據加加速度、加速度、速度及位移間的動力學規律有:

進而可以得到：

每個貨位長度為X，高度為Y。ETV 每完成一次調度操作要運行M列N層，則水平方向運行距離Sx=X*M，垂向運動距離為Sy=Y*N。

ETV 理參數如表1 所列：

表1 ETV 運行參數

集裝立體貨架采用縱向存儲式，單個貨位長為3.75m，共45 列；層高為3.75m，共5 層，貨位數45*5*2=450。ETV 在水平運行時間和垂向運行時間分別為Tx,Ty：

那么ETV 在兩個貨位點之間運行的時間開銷為：

通常，貨運站貨物處理區的任一批次的出入庫都包含n個集裝貨物任務的操作，每個任務花費的時間主要由3 部分組成：（1） 兩個貨位點間負重行走時間Tτa；（2） 兩個貨位點間空載行走時間Tτb；（3） 每完成一次取/放貨時間Tc，這部分的時間恒定。

由以上分析可知，完成1 個集裝貨物任務的操作的時間為：

2 遺傳算法計算與求解

遺傳算法以自然選擇和遺傳理論為基礎，通過對生物在遺傳和進化過程中選擇、交叉、變異機理的模仿，來完成對問題最優解的自適應搜索的一種算法[4]。選擇、交叉、變異運算是遺傳算法的主要步驟，改進的遺傳算法將針對這三個算子實現算法性能的提升。

2.1 選擇編碼策略

在研究調度優化問題時通常采用實數編碼。因此在用改進的遺傳算法對貨運站調度進行優化時，首先要建立貨位號和貨位編碼的對照表。

本文中的集裝貨物存儲區有2 行、5 層、45 列。假設貨位處于第2 行、第3 層、第3 列，則貨位號用（2-3-3） 表示，對應編碼號為28。具體編碼方式參照表2。

2.2 定義適應度函數

將目標函數進行變換可得到適應度函數，依據目標函數要遍歷所有等待任務的貨位點而費時最短原則，目標函數可定義為：

由于在貨運站內，等待任務列隊是即時變化的，故每加入一個新的調度任務后需執行一次新的優化，會使個別任務等待時間太長。因此，考慮任務等待時間的因素，目標函數變為：

表2 編碼號與貨位號對照表

式中：ti表示任務等待的時間；β 表示根據工作模式使用的參數。

2.3 遺傳算法的三個算子的改進

2.3.1 基于序的選擇算子設計

適應度值是進行選擇過程的依據。為了加快算法的收斂速度，本文采取的方法是快速選中種群中的優秀個體，并使優秀個體馬上參與到下一代交叉運算。通過增大優劣個體間的適應度值，可將優秀個體快速選出。為了增大個體之間適應度值的區分度，通過基于序的評價函數來實現。首先對種群中的個體按花費總時間的長短排序，并據此確定個體在隊列中的序號，對總時間越少的個體賦予小的序號數。如耗費最少時間的個體被賦予序號數1，則耗費最長時間的個體序號數為n，然后用下面的基于序的指數評價函數計算適應度：

式中，base為取值范圍在0 到1 間的基數，μ 是個體通過排序后得到的序號數，由于評價函數經指數計算后得到數據值較小，乘以10 000 的目的是放大數據從而使其不會在計算中被舍去。例如，個體A序號數是5，個體B序號數是7，個體C序號數是2，選擇基數為0.5，個體A、B、C的適應度分別為：

顯然，通過該評價函數計算后C的適應度是A的8 倍，是B的32 倍，個體C的優越性變得更加突出，它被選作父代的可能性就大為提升。確保適應度最高的基因快速傳到下代，加速算法收斂速度。

2.3.2 基于普萊姆算法的交叉算子設計

在用遺傳算法求解貨運站的調度優化問題時，貨運站內每個貨位點的位置編碼采用實數編碼，經常用到的交叉算子有：部分匹配交叉算子，順序交叉算子，循環交叉算子等，上述交叉算子只是單純產生新個體，在設計時沒有充分結合問題本身的特性進行考慮，最終算法尋優效果在整體性能方面不理想。在貨運站內，規定ETV 的起始點貨位為1，最后執行完任務后要回到起始貨位點，則把每個出入庫任務貨位點連起來是完全圖。把ETV 從上一貨位點到下一貨位點運行所需的時間稱為權，則要使ETV 依次抵達n個貨位點，至少需要n-1 條邊來表示，n個貨位點和n-1 條邊可生成一棵樹，把n-1 條邊的權值求和后存在一顆和最小的樹，稱這樣的樹為最小代價樹。設U表示n個貨位點的集合，E表示n-1 條邊的集合，那么普萊姆算法就是一種求最小代價樹的算法。

用普萊姆算法生成最小代價樹的例子如圖3 所示。

最小代價樹生成方法如下：

（1） 任意選一頂點A，令U=｛A｝，尋找A的相鄰邊使其權值最小，產生一條邊（A,B），則將B添入U內，（A,B）添入E內，得到U=｛A,B｝,E=｛（A,B）｝；

（2） 在E外再尋找A、B的鄰邊使權值最小，得到邊（A,C），再將C添入U內，并把（A,C）添入E內，此時U=｛A,B,C｝，E=｛（A,B）,（A,C）｝；

（3） 在E外搜索A、B、C的鄰邊使其權值最小，得到邊（B,D），將D添入U內，同時（B,D）加到E中，此時U=｛A,B,C,D｝，E=｛（A,B）,（A,C）,（B,D）｝，到此U中包括了所有的頂點。求得E的最小權值和為6。

根據普萊姆算法生成最小代價樹的思想，設計一種基于普萊姆算法的交叉算子步驟如下：

（1） 在種群中選取兩個個體Pa、Pb 作為父代，隨機產生一個貨位點，并把這個貨位點作為子代個體Ca首先到達的貨位點；

（2） 搜索ri在Pa、Pb 優化順序中右邊的貨位點rj1、rj2，比較con（ri,rj1）和con（ri,rj2）耗時的大小，如果con（ri,rj1）＞con（ri,rj2），則按照ri到rj2的順序更快，進入（4）；

（3） 若con（ri,rj1）＜con（ri,rj2），則按照ri到rj1的順序更快，就把rj1加入到ETV 下一訪問順序的貨位點，同時刪去Pa、Pb中ri的值，重新將ri賦值rj1，再進入（2） 開始下一步搜索，直到Pa、Pb 中剩下唯一的貨位點；

（4） 將rj2看成ETV 下一訪問的貨位點，同時刪去Pa、Pb 中ri的值，重新將ri賦值rj2，繼續轉入（2） 開始搜索，直到Pa、Pb 中只剩下最后一個貨位點；

（5） 通過Pa、Pb 向右尋優搜索雜交產生子代個體Ca。同樣對Pa、Pb 向左尋優搜索雜交產生子代個體Cb。

2.3.3 基于隨機時間長度的變異算子設計

設計一種基于隨機時間長度的變異算子，可增大種群多樣性，同時減小破壞優良個體基因概率，方法如下：

（1） 任意產生貨位點r1和r2，初始循環次數p=1；

（2） 計算調度隊列中上述兩個貨位點間的貨位點數q；

（4） 在r1和r2之間選取兩個貨位點ri、rj，替換ri、rj的次序，p=p+1；

（5） 若k＜m，則返回（4），否則跳出。

該交叉方法由初始的貨物點r1,r2之間的貨物點數量q確定需要隨機交換的次數s。若q越大，進行的替換次數就越多，否則就越少。根據時間耗費長短控制變異的次數，可以在保存了優良個體的同時增加了種群多樣性。長短控制變異的次數，可以在保存了優良個體的同時增加了種群多樣性。數量q確定需要隨機交換的次數s。若q越大，進行的替換次數就越多，否則就越少。根據時間耗費長短控制變異的次數，可以在保存了優良個體的同時增加了種群多樣性。

3 仿真驗證

為了測試改進的遺傳算法的性能，對圖1 所示的集裝貨物存儲區進行仿真試驗。實際中出入庫作業主要集中于空側區域，因此只討論空側區域的I/O 口。空側區域入口總共7 個，位置編號為41，101，181，201，311，341，441；出口共計6 個，編號為71，151，261，291，391，421。

有30 個入庫任務R1～R30，貨位編碼為：53、79、235、154、337、335、435、287、399、69、88、6、197、133、142、77、330、379、434、400、277、199、84、9、108、321、342、222、263、21。

30 個出庫任務C1～C30，貨位編號為：8、55、183、79、83、160、255、365、302、421、5、17、13、72、11、121、180、200、340、263、38、175、438、411、393、10、45、383、415、400。

將標準遺傳算法和改進遺傳算法分別應用于機場貨運站的ETV 調度優化中，用MATLAB7.11 進行仿真實驗。初始種群個體為30 個，代溝為0.9，雜交率為0.7，變異率為0.02，使用標準遺傳算法和改進遺傳算法分別進行500 次迭代。

為了更好地顯示改進遺傳算法的優越性，分別比較其與標準遺傳算法的單次優化效果和進行多次優化后性能的提升，對比結果如圖4 和圖5 所示。

對試驗數據對比分析得出：用標準的遺傳算法進行優化在迭代400 代左右后可得到最優解5 600s，而改進的遺傳算法在迭代300 次后就得到最優解5 200s，優化提升7.14%，計算時間大約縮短20%。在前100 次的迭代中，改進遺傳算法的收斂速度明顯快于標準遺傳算法。同時，由圖5 可看出，將改進的遺傳算法與標準的遺傳算法選用相同參數分別優化20 次，改進遺傳算法每次優化的結果都維持在5 200 秒左右，變化很平穩，而用標準遺傳算優化會出現較突出的波動，最嚴重時可達到2%。

4 結 論

本文使用柔性S 型運動曲線模型，保證了ETV 運動的平穩性，大大減少了運動過程中貨物的沖擊；運用組合優化的思想對標準遺傳算法選擇、交叉、變異三個算子進行改進并應用于ETV 的調度作業，相比標準的遺傳算法具有更好的可收斂性，避免了標準遺傳算法陷入局部最優解的缺陷，同時提高了優化效率，節約了計算時間。仿真結果證明，該算法對于提高ETV 的調度效率是有效的，提高貨運站的服務質量，降低運行成本都有積極意義。在今后的研究中，可考慮當多臺ETV 同時運行于一條軌道上的情況，從而使貨運站的吞吐量效率更高。

[1] 邱建東. 大型機場貨運站核心物流裝備調度優化問題研究[D]. 蘭州：蘭州交通大學，2014.

[2] 張汝成，王廣生，聶玉同. 電梯系統的高精度S 型速度曲線的生成和實現[J]. 起重運輸機械，2009(4):6-10.

[3] 劉筱，吳文江，鄭飂默. 柔性S 型加減速控制算法研究[J]. 組合機床與自動化加工技術，2013(3):66-69.

[4] 陳建安，郭大偉，徐乃平,等. 遺傳算法理論研究綜述[J]. 西安電子科技大學學報，1998(6):363-367.

[5] 李曉輝，鄔義杰，冷洪濱. S 曲線加減速控制新方法的研究[J]. 組合機床與自動化加工技術，2007(10):50-53.

[6] 張超勇，饒運清，李培根,等. 求解作業車間調度問題的一種改進遺傳算法[J]. 計算機集成制造系統，2004(8):966-971.

[7] 羅勇，陳治亞. 基于改進遺傳算法的物流配送路徑優化[J]. 系統工程，2012(8):118-123.

[8] 劉巍巍，趙紅，王迎春. 遺傳算法在自動化倉庫路徑調度問題中的應用[J]. 沈陽工業大學學報，2008(6):338-341.

[9] 王廳長，邱建東，商慶健,等. 病毒協同進化遺傳算法在自動化立體倉庫貨位優化中應用的研究[J]. 計算機科學，2014(11):35-38.

[10] 李建鋒，彭艦. 云計算環境下基于改進遺傳算法的任務調度算法[J]. 計算機應用，2013(11):184-187.

[11] 趙亮，宋宇博，蔣兆遠. BP 神經網絡在機場貨運站生產調度中的應用[J]. 起重運輸機械，2009(11):39-42.