基于遺傳算法的堆場自動化設備調度策略

孫 斐，沈安江

（上海振華重工集團股份有限公司，上海 200125）

0 簡介

隨著人力成本的增加，全球物流需求的增長，國內外越來越多的港口開始啟用自動化設備進行堆場作業。由于堆場在碼頭運輸中的重要地位，堆場的作業效率很大程度上影響了裝卸船的整體速度，是決定碼頭服務能力的關鍵因素之一。在堆場建造設計和設備機械性能一定的前提下，優化作業任務的調度可以有效的提升堆場的作業效率。因此，本文提出一種利用遺傳算法為數學模型從而解決復雜的堆場任務調度問題的策略，適用于在TOS一次性發送多條同一個堆垛的任務給ASC-MS的情況下，ASC-MS如何使用遺傳算法解決同一個堆垛內2臺ASC的選車問題、調度問題、避讓問題等問題。本文提出的自動化堆場調度策略繼承了遺傳算法的優點與特性，不需要知道研究目標的內在性質也能進行求解。

1 調度策略各模塊構成

本策略采用遺傳算法（Genetic Algorithm）作為系統框架來進行問題求解。遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的策略。遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體（individual）組成。每個個體實際上是染色體（chromosome）帶有特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解。

系統各模塊及其功能如下：

1.1 初始化

設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。

1.2 個體評價

計算群體P(t)中各個個體的適應度。

1.3 選擇運算

將選擇算子作用于群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

1.4 交叉運算

將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。

1.5 變異運算

將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。

群體P(t)經過選擇、交叉、變異運算之后得到下一代群體P(t+1)。

1.6 終止條件判斷

若t=T，則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。

1.7 計算過程

計算過程如圖1所示。

圖1 遺傳算法計算流程圖

2 算法的實現

2.1 概述

本章節闡述如何將遺傳算法應用于堆場設備解決ASC-MS（智能堆場管理系統）的選車問題、調度問題、避讓問題等問題。

2.2 ASC-MS的編碼規則

本算法將TOS發送給自動化堆場的N條任務定義為長度為N位的二進制數值。

將海側ASC作業一條任務定義為數值0。將陸側ASC作業一條任務定義為數值1。

例：TOS發送10條任務給自動化堆場，經過遺傳算法計算后可能得到完成五條任務時間最快的排列為10101。

這代表第一條任務使用陸側ASC，第二條任務使用海側設備，第三條任務使用陸側設備，第四條任務使用海側ASC，第五條任務使用陸側ASC。

2.3 ASC-MS的適應度函數

ASC-MS的適應度函數的目的是將遺傳算法生成的二進制數值進行計算，適應度函數的輸入是代表設備選擇、運行方案的二進制數值，任務的具體信息以及設備的運行參數等數據，適應度函數的輸出是代表設備選擇、運行方案的完成總時間。經過計算獲得該數值代表的ASC運行的總體時間，時間越短，則適應度越高，解越優。

由于ASC大車運動是非勻速的甚至是非線性的，為了獲得更接近實際情況的任務完成時間，本算法快速模擬了設備的機構動作從而得到任務完成所需的時間值。

對于兩臺設備在作業過程中可能發生的避讓需求，具體方法如下：

根據兩車當前任務狀態得到目標位置（任務暫停狀態下設備的目標位置為任務目標位置加/減安全距離，左側設備為減，右側為加）。如果兩車目標位置（大車）沒有沖突，即左側設備的目標位置+安全距離<右側設備的目標位置，則按照目標位置移動或抓放箱。如果存在沖突，處于空閑狀態或任務暫停狀態下的設備要進行避讓，兩車都正常作業的情況下任務優先級低的要避讓優先級高的，如果優先級也相同，采用生成隨機數比較大小的方式來決定哪臺做要避讓。避讓位置為另一臺的目標位置加/減安全距離，左側設備為減，右側為加。最后得出兩車決策目標位置。如果一輛車已有指令，則另一輛沒有新指令的車若存在位置沖突需要 避讓。

兩臺ASC各自生成隨機數，初始范圍為0到3，比較兩個整數大小，若相等則再進行一次隨機，直到不等為止。隨機數大的那臺設備獲得“勝利”，另一臺需要進行避讓。“失敗”的設備將隨機數生成范圍翻倍，以提高下次避讓決策時的獲勝概率，減小連續失敗的可能性，獲勝后，生成范圍恢復為初始狀態。

通過對同一基因的多次計算，選取用時最短的結果作為適應度并記錄它所對應的避讓策略。

2.4 ASC-MS的選擇運算

選擇運算（或稱為復制運算）把當前群體中適應度較高的個體按某種規則或模型遺傳到下一代群體中。一般要求適應度較高的個體將有更多的機會遺傳到下一代群體中。

在本算法中，每一個得到的個體都會被保存，而遺傳到下一代的個體將不會重復計算其適應度，以避免時間的浪費。

優秀的個體只在遺傳時進行使用，用更大幾率去產生更優秀的個體。

2.5 ASC-MS的交叉運算

交叉運算是遺傳算法中產生新個體的主要操作過程，它以某一概率相互交換某兩個個體之間的部分染色體。

在本算法中，以10條任務為例。

0000000000代表10條任務全部由海側ASC完成，1111111111代表10條任務全部有陸側ASC完成。

經過交叉運算后得到新的兩個解：0000011111和1111100000。

0000011111代表前5條任務由海側ASC完成，后5條任務由陸側ASC完成。

1111100000代表前5條任務由陸側ASC完成，后5條任務由海側ASC完成。

2.6 ASC-MS的變異運算

變異運算是對個體的某一個或某一些基因座上的基因值按某一較小的概率進行改變，它也是產生新個體的一種操作方法。

還是以10條任務為例。

0000000000代表10條任務全部由海側ASC完成。經過變異后得到新的解0000000001。

0000000001代表前9條任務由海側ASC完成，最后1條任務由陸側ASC完成。

2.7 ASC-MS使用遺傳算法的流程圖

流程圖如圖2所示。

圖2 ASC-MS使用遺傳算法的流程圖

2.8 ASC-MS使用遺傳算法的流程說明

當ASC-MS獲取到TOS任務時，ASC-MS開始調用遺傳算法模塊。

ASC-MS將TOS任務傳給遺傳算法模塊。

遺傳算法模塊根據傳入的TOS信息進行二進制編碼，并產生第一組初始解。類似于1010111001（10條任務），有幾條任務，二進制數值就一共會有幾位。

遺傳算法模塊調用適應度函數，在本方案中，適應度函數通過任務信息，計算完成這些任務所需要花費的總時間，時間越短，代表解越好，適應度越高。

遺傳算法模塊獲得這些解及其適應度（時間），保存在內存中。

遺傳算法模塊查看是否有必要進行下一次迭代，本方案中，按照設定的迭代次數，到達迭代次數上限則停止迭代。

未到達迭代次數上限則繼續迭代。

遺傳算法模塊繼續迭代，根據選擇、交叉、變異規則產生下一代新的解。

遺傳算法模塊查看這些新的解之前是否已經出現過。

剔除已經出現過的解，把沒有出現過的解交給適應度函數進行計算。

遺傳算法模塊獲得這些解及其適應度（時間），保存在內存中，然后進行下次迭代，直到達到迭代次數上限。

遺傳算法提供ASC-MS框架一個最優化的解。

3 不足和改進

當前的遺傳算法編碼規則為二進制，0代表海側ASC，1代表陸側ASC，因此當一個堆垛的ASC數量大于2臺時，無法適用當前編碼規則和遺傳規則，因此需要改進。

當前算法尚無調整任務執行的先后順序的能力。

當前算法還沒有計算接力的情況。

當前算法尚未試驗得出一組交叉和變異的參數值使得迭代能更好地趨向于種群進化，即得到更優的解，并跳出局部最優解陷阱。

4 結束語

本文提出的策略通過使用遺傳算法模型建立堆場調度的解決方案并在計算適應度的同時得出了基于一定任務分配條件下兩車避讓的決策優化。相較于基于就近原則的任務調度策略及其它基于固定邏輯的調度算法，此策略對于各種復雜工況有著更好的自適應能力，能整體地提高堆場作業效率。實現了自動化堆場管理和執行批任務的工作模式。

參考文獻：

[1]Taejin Park · Ri Choe · Seung Min Ok ·Kwang Ryel Ryu.Realtime scheduling for twin RMGs in an automated container yard[J]. Springer-Verlag 2010,Published online:4 April 2010.

[2]陳國良,王熙法,莊鎮泉,王東生.遺傳算法及其應用[M].人民郵電出版社,1999,11(7):59-62.

[3]周明,孫樹棟.遺傳算法原理及應用[M].國防工業出版社,1999.