基于遺傳算法的堆場自動化設備調(diào)度策略

孫 斐，沈安江

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

0 簡介

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

1 調(diào)度策略各模塊構成

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

系統(tǒng)各模塊及其功能如下：

1.1 初始化

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

1.2 個體評價

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

1.3 選擇運算

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

1.4 交叉運算

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

1.5 變異運算

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

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

1.6 終止條件判斷

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

1.7 計算過程

計算過程如圖1所示。

圖1 遺傳算法計算流程圖

2 算法的實現(xiàn)

2.1 概述

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

2.2 ASC-MS的編碼規(guī)則

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

將海側(cè)ASC作業(yè)一條任務定義為數(shù)值0。將陸側(cè)ASC作業(yè)一條任務定義為數(shù)值1。

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

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

2.3 ASC-MS的適應度函數(shù)

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

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

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

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

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

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

2.4 ASC-MS的選擇運算

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

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

優(yōu)秀的個體只在遺傳時進行使用，用更大幾率去產(chǎn)生更優(yōu)秀的個體。

2.5 ASC-MS的交叉運算

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

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

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

經(jīng)過交叉運算后得到新的兩個解：0000011111和1111100000。

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

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

2.6 ASC-MS的變異運算

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

還是以10條任務為例。

0000000000代表10條任務全部由海側(cè)ASC完成。經(jīng)過變異后得到新的解0000000001。

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

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

流程圖如圖2所示。

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

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

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

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

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

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

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

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

未到達迭代次數(shù)上限則繼續(xù)迭代。

遺傳算法模塊繼續(xù)迭代，根據(jù)選擇、交叉、變異規(guī)則產(chǎn)生下一代新的解。

遺傳算法模塊查看這些新的解之前是否已經(jīng)出現(xiàn)過。

剔除已經(jīng)出現(xiàn)過的解，把沒有出現(xiàn)過的解交給適應度函數(shù)進行計算。

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

遺傳算法提供ASC-MS框架一個最優(yōu)化的解。

3 不足和改進

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

當前算法尚無調(diào)整任務執(zhí)行的先后順序的能力。

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

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

4 結(jié)束語

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

參考文獻：

[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]陳國良,王熙法,莊鎮(zhèn)泉,王東生.遺傳算法及其應用[M].人民郵電出版社,1999,11(7):59-62.

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