基于自適應(yīng)遺傳算法立體庫貨位優(yōu)化調(diào)整

宋賀騰，鄒 方

（1.北京航空航天大學 機械工程及自動化學院，北京 100191；2.北京航空制造工程研究所，北京 100024）

0 引言

隨時間推移、物料的運入運出，使得一些物料距離加工時間越來越近，同時立體庫的中心不斷發(fā)生變化，這導(dǎo)致立體倉庫運行穩(wěn)定性下降，物料之前的存放位置已不是最優(yōu)的選擇。如何從新獲得最優(yōu)的存放位置并進行較快的調(diào)整一直以一個熱點問題。

隨機存儲和分類存儲以及定位存儲等是當前自動化立體倉庫經(jīng)常使用的存儲方案[1]。當物料分類明顯時，會采用分類存儲策略方案指導(dǎo)貨位的優(yōu)化再分配。如文獻[2]，研究了特定環(huán)境下基于遺傳算法按類分配貨位的方法，文獻[3]提出將周轉(zhuǎn)率以及分類用于不確定環(huán)境中庫位的分配和利用。當物料工藝BOM比較完備時，可以建立物料的特征碼同庫位進行匹配，以提高將來出入庫任務(wù)執(zhí)行的效率。如文獻[4]提出了將特征碼應(yīng)用于庫位的利用和分配，文獻[5]提出通過BOM進行分類以對庫位采用合理分配的方案。對于物料需求頻率等比較明了詳細的情況，可將立體庫貨位進合理的分區(qū)，同物資出入庫頻率進行匹配，達到合理分配貨位的目的。如文獻[6]研究了立體庫貨位的分配優(yōu)化方案，介紹了立體庫貨位優(yōu)化的數(shù)學模型。

分析上述文獻，均針對既定情況存放新物資，對貨位優(yōu)化再分配的數(shù)學模型及其優(yōu)化調(diào)度順序的研究較少。本文研究原型為某工廠單元貨格式立體倉庫（以下簡稱立體庫），對其內(nèi)存放物資進行貨位優(yōu)化調(diào)整。采用自適應(yīng)遺傳算子，對一般自適應(yīng)算法交叉概率和變異概率進行改進，根據(jù)變適應(yīng)度的尺度變換（fitness scaling）—變適應(yīng)度指數(shù)變換，結(jié)合種群信息自適應(yīng)調(diào)節(jié)目標函數(shù)權(quán)值大小進行問題優(yōu)化，提高計算效率，避免早熟和局部收斂，得到較優(yōu)解。以期縮短自動化立體倉庫物料出庫時間并降低貨架重心提高穩(wěn)定性。

1 貨位調(diào)整優(yōu)化問題描述

1.1 基本假設(shè)

本實驗基于以下情景設(shè)定進行：

1）該立體庫有一個通道，一臺堆垛機，一排貨架，堆垛機在一側(cè)開始對貨架進行操作出入庫操作，且初始位置為0000。

2）在立體庫中有多種貨物，均以箱為單位存放，且每個托盤只能存取一箱貨物，貨物之間沒有相關(guān)性，所有托盤規(guī)格相同且與貨位一一對應(yīng)。

3）貨位越靠近立體庫出入庫工作臺（以下簡稱庫臺）編號越小，依次順序遞增，且編號可以較直觀反映出貨位位置，如0608，表示6列8層，出入庫工作臺設(shè)為0000，如圖1所示。

圖1 貨位號排列簡圖

4）視堆垛機水平和垂直方向為勻速運動。

1.2 模型描述

下面定義相關(guān)符號，用于描述本實驗。

立體庫有n列m行；Vx和Vy代表堆垛機水平和垂直方向速度；Lx和Ly代表貨位長和高。

根據(jù)立體庫現(xiàn)有物料狀況，重新分配貨位，以保證縮短即將進行的立體倉庫物料出庫時間并降低貨架重心提高穩(wěn)定性。

保證立體庫承力均勻，遵循上輕下重的原則，可使所有貨物的重量與所在托盤層數(shù)的乘積之和最小，建立數(shù)學模型如下：

式中：Fit1是每個貨物的重量與其所在托盤層數(shù)的乘積和；Wij代表貨架上第i行j列的物料重量；P在放有物料時為1，否則為0。

保證整體出庫效率較高，可使所有貨物距離加工的時間和堆垛機揀選貨物時運行的時間之和最小，建立數(shù)學模型如下：

式中：Fit2代表物資距離加工的時間和揀選此物資堆垛機的運行時間之和；Lx表示貨位長度；Ly表示貨位寬度；tij代表將本物資搬運到庫臺所需要時間；Tij代表本物資距離開始加工時間。

綜上，可以得到立體庫貨位優(yōu)化調(diào)整再分配模型如下[7]：顯然，這是多目標優(yōu)化問題，求解復(fù)雜，在本文，通過將權(quán)重賦予兩目標函數(shù)，將其變成單目標問題，這里賦給權(quán)重相等，又因為距離加工時間T沒有變量系數(shù)，故也可以省去，可得最終的作業(yè)優(yōu)化函數(shù)如下：

此實驗中，堆垛機和貨位間有如下運作關(guān)系：堆垛機接收運輸指令，從最初的庫臺（0000）出發(fā)，運行至第一個任務(wù)目的地，將此貨位托盤取出運至庫臺，由工作人員（或機器人）按需求取出（或放入）物資，堆垛機將托盤運回原貨位，至此完成本條任務(wù)。之后，若有下條任務(wù)，堆垛機并不會回庫臺，而是直接運行至下一任務(wù)目的地，開始執(zhí)行下一條出/入庫任務(wù)，如此直至完成最后一個任務(wù)，堆垛機返回庫臺。示例如圖2所示。

圖2 任務(wù)執(zhí)行簡圖

假定有n條運輸任務(wù)，那運行總時間為[8]：

式中：T00表示堆垛機從原點到第一個庫位經(jīng)歷的時間；Ti0表示堆垛機從當前貨位到庫臺所需時間；Ti（i+1）表示堆垛機從當前貨位到下一貨位所經(jīng)歷時間；Tn0表示堆垛機送回最后一個貨位托盤后回到庫臺所需時間。

對式(8)進行分析，在運輸任務(wù)確定后，每個目的地都會經(jīng)歷一次同庫臺之間的往返運作，即相對本次運輸任務(wù)為確定值，那將式(8)分為兩部分：

將T2作為某一常數(shù)，調(diào)整順序優(yōu)化模型轉(zhuǎn)為式(10)。

兩目的地間從至時間T計算方法如下：

此時問題轉(zhuǎn)為有約束條件的旅行商問題（Traveling Salesman Problem with Precedence Constraint , TSPPC）。

相比啟發(fā)式搜索技術(shù)、隨機搜索技術(shù)、枚舉技術(shù)等方法，遺傳算法具有較強魯棒性，其從群體開始搜索，初始解具有多樣性，覆蓋面廣，利于全局擇優(yōu)，其最大優(yōu)點是通過群體之間的相互作用，保有已獲得的信息，這是基于單次搜索過程的優(yōu)化方法無法達到的[10]。經(jīng)過不斷發(fā)展，GA許多領(lǐng)域都得到成功的應(yīng)用，如工智能領(lǐng)域[15]等。本文將遺傳算法作為優(yōu)化調(diào)整的算法。

2 遺傳算法實現(xiàn)

遺傳算法是模擬生物在自然界遺傳和進化過程的隨機搜索算法，由美國Michigan大學的J.H.Holland教授于二十世紀末提出[11]。遺傳算法涉及的控制參數(shù)有：種群大小、交叉概率、變異概率等。控制參數(shù)設(shè)定的合理與否會對算法的性能有特別大影響。

下面對本文采用遺傳算法要素介紹。

2.1 染色體編碼

（0103-0301,0203-0302,0102-0301,0201-0102,0304-0201,0302-0203）

表示堆垛機作業(yè)依次揀選，將0103貨位物料運至0301，將0203貨位物料運至0302貨位，以此類推。

2.2 種群初始化

在最初的優(yōu)化調(diào)整中，初始種群較多采用隨機產(chǎn)生的方法。而在之后的調(diào)整順序優(yōu)化中，個體要滿足一定的約束條件，以（0103-0301,0203-0302,0102-0301,0201-0102,0304-0201,0302-0203）為例，運用有向圖進行介紹，如圖3所示。

圖3 約束條件

圖3顯示了會出現(xiàn)的所有3種典型約束情況，其中箭頭表示約束，可以看出，情況1沒有任何限制，情況2為兩貨位物料互換，這就需引入第三方貨位進行周轉(zhuǎn)，如圖4示例，引入空閑貨位0101。情況3則嚴格按照先后順序進行，即在0102貨位物料運出至0301貨位后才能將0201貨位物料運至0102貨位。

圖4 約束轉(zhuǎn)換

具體初始化步驟為：1）隨機選取各約束情況中沒被指向箭頭的結(jié)點作為個體一個基因；2）刪除此結(jié)點及其指出的箭頭；3）重復(fù)步驟1）、2），直到各約束情況中不存在結(jié)點。由圖5可得某個體：

2.3 適應(yīng)度函數(shù)設(shè)計

在最初的優(yōu)化調(diào)整中，兩個階段染色體適應(yīng)值分別通過式(5)和式(10)確定，求問題的最小值。此處采用指數(shù)變換法，將目標函數(shù)進行線性變換，轉(zhuǎn)換為求最大值問題。

系數(shù)a的變化可以控制新適應(yīng)度函數(shù)值得變化，這決定了選擇的概率大小。若不是將a作為恒定值，而是較好的控制其變化，將會取得很好地實驗結(jié)果。在遺傳算法運行過程中，種群在不同階段的狀況不盡相同，特別在前后期之間差別巨大[9]，故本文采用基于指數(shù)變換的變適應(yīng)度策略，根據(jù)當前種群情況調(diào)節(jié)參數(shù)a的大小，使其隨進化代數(shù)增加進行動態(tài)變化。對a取值式(15)[12]。

式中：t表示當前進化代數(shù)；T表示最大遺傳代數(shù)；Favg為平均適應(yīng)度；是防止平均適應(yīng)度為0的足夠小正數(shù)。

2.4 遺傳算子設(shè)計

2.4.1 選擇

本文采用基于輪盤賭的比例選擇法。

可看出，適應(yīng)度較高的個體以比較大的概率被選擇到下一代，反之以較小的概率被選擇。

2.4.2 交叉和變異

普通遺傳算法在初始會設(shè)定固定的交叉率Pc和變異率Pm，但種群在不同階段的狀況不盡相同，一成不變的交叉率和變異率會導(dǎo)致抑制出現(xiàn)早熟和局部收斂現(xiàn)象的作用降低。

目前，動態(tài)自適應(yīng)技術(shù)已成為算法控制參數(shù)比較好的方法，Pc、Pm會在進化過程中以種群各個階段的情況為依據(jù)，隨機調(diào)整其大小[13]。以達到對適應(yīng)度較高個體降低Pc、Pm，保證其進入下一代，對適應(yīng)度較低個體增大Pc、Pm，使其被淘汰的目的。

sigmoid函數(shù)在線性和非線性行為之間有較好的平衡，其有平滑的頂部和底部[14]。本文采用此函數(shù)用于Pc、Pm的自適應(yīng)調(diào)整。

為了以較好比例顯示圖形，選a=9.903438[15]，當ax＞9.903438的時候，f(x)=1；當ax＜-9.903438的時候，f(x)=0。

根據(jù)sigmoid函數(shù)設(shè)計貨位優(yōu)化調(diào)整問題交叉率和變異率自適應(yīng)調(diào)整公式如式(18)和式(19)。

式中，Pc是個體交叉率，Pm是個體變異率，Pcmax是定義的最大交叉率，Pcmin是定義的最小交叉率，c是定義的最大變異率，Pmmin是定義的最小變異率，F(xiàn)it*是當前種群新適應(yīng)度，F(xiàn)it*avg是當前種群新平均適應(yīng)度，F(xiàn)it*max是當前種群最大新適應(yīng)度，F(xiàn)it*min是當前種群最小新適應(yīng)度，ε是一足夠小正數(shù)；α=-9.903438。

取Pc∈[0.60～1.00]，Pm∈[0.005～0.01]。

3 實驗仿真與評價

本文考慮一單排10列10層100個貨位的單元貨格式自動化立體倉庫為實驗對象進行驗證，每個貨位長1.2 m，高0.8m，堆垛機水平向最大速度為2m/s，垂直方向為1m/s。在立體庫中放有40箱物資，堆垛機每次只能運輸一個托盤，其空閑時，停留位置為庫臺處。遺傳算法中的種群規(guī)模P=200，交叉率取Pc=0.6～1.0，變異率取Pm=0.005～0.01，最大遺傳代數(shù)設(shè)為2000。

本文根據(jù)海明距離刻畫種群的多樣性程度進行分析[9]。

設(shè)個體編碼長度為L，種群規(guī)模為N，在第m代中，Xi(m)代表第個體i（i=1,2,3,…,N），記Xik(m)是Xi(m)的第k位（k=1,2,3,…,N），兩個體Xi(m)和Xj(m)間的海明距離如式(20)。

若Xik(m)和Xjk(m)相同，P取0，否則，P取值1。

第m代種群平均海明距離如式(21)所示。

根據(jù)海明距離，利用式(22)刻畫第m代種群多樣性程度，F(xiàn)(m)會隨著個體間的差異改變。

根據(jù)種群多樣性，可得對比結(jié)果如圖5和圖6所示（取前150代進行對比）。

圖5 新貨位分配多樣性函數(shù)F(m)

圖6 優(yōu)化調(diào)整順序多樣性函數(shù)F(m)

由圖6和圖7可看出，采用自適應(yīng)遺傳算法的多樣性函數(shù)相比普通遺傳算法多樣性函數(shù)，上升速度較慢，無論是前期的新貨位分配還是后期調(diào)整順序優(yōu)化，都能保證進化過程中種群的多樣性。

圖7和圖8描述了每一代種群最大適應(yīng)度的變化過程。相比普通遺傳算法，自適應(yīng)遺傳算法達到局部最優(yōu)解的有效進化過程比普通遺傳算法長，可有效地解決進化過程中早熟收斂的問題。

圖7 新貨位分配最大適應(yīng)度函數(shù)值

圖8 優(yōu)化調(diào)整順序最大適應(yīng)度函數(shù)值

圖9示意立體庫存儲物資調(diào)整前后結(jié)果。

圖9 貨位調(diào)整前后對比

兩種算法都使立體庫整體重心下移，穩(wěn)定性增強。以列數(shù)為橫坐標，層數(shù)為縱坐標，表1為優(yōu)化前后情況對比。描述了優(yōu)化后結(jié)果，普通遺傳算法將重心由原始（6.70,4.96）優(yōu)化為（5.18,2.19），自適應(yīng)遺傳算法將重心由原始的（6.70,4.96）優(yōu)化為（5.59,2.09），重心分別下移55.8%和57.9%，堆垛機總運行時間由原195.6秒縮短為150.1秒和140.2秒（本文僅考慮堆垛機往返行程時間），縮短23.3%和28.3%。對分析可以看出，自適應(yīng)遺傳算法相比普通遺傳算法優(yōu)化效果較好。

表1 優(yōu)化前后情況對比

4 結(jié)論

在遺傳算法中，交叉率和變異率的取值會很大程度的影響遺傳算法性能，將會直接影響算法的效果，有效解決結(jié)果的早熟收斂問題。

本文闡述了基于自適應(yīng)遺傳算法的單元貨格式自動化立體倉庫貨位優(yōu)化調(diào)整方法：1）根據(jù)物料加工時間、取送時間、物料重量等，減少了堆垛機針對加工任務(wù)取物資總運行時間，降低立體庫重心，增強了穩(wěn)定性。2）變適應(yīng)遺傳算法可很好地解決進化過程中早熟收斂的問題，較容易達到全局最優(yōu)解。

[1]李詩珍,陳漁,帥玉妹,等.立體倉庫自動存取系統(tǒng)的作業(yè)周期與貨位分區(qū)管理[J].起重運輸機械,2002,(10):8-11.

[2]陳元文,吳曉波,孫耀磊,等.基于遺傳算法的軍隊立體倉庫貨位再分配研究[J].計算機工程與應(yīng)用,2013,(24):233-237.

[3]Hsieh S,Tsai K C.A ROM Oriented Class2Based Storage Assignment in an Automated StorageP Retrieval System[J].International Journal of Advanced Manufacturing Technology.2001,48(7):683-691.

[4]劉金平,周炳海,奚立峰,等.在線自動化立體倉庫的庫位分配方法及其實證研究[J].工業(yè)工程與管理,2005,10(1):11-16.

[5]Thonemann U W,Brandeau ML.Optimal storage assignment policies for automated storage and retrieval systems with stochastic demands[J].Management Science.1998,44(1):142-148.

[6]陳月婷,何芳.基于改進粒子群算法的立體倉庫貨位分配優(yōu)化[J].計算機工程與應(yīng)用,2008,(11):229-236.

[7]陳厚松.自動化立體倉庫出入庫貨位分配優(yōu)化研究[D].武漢:武漢理工大學,2011:24-26.

[8]沙麗娜.自動化立體倉庫貨位優(yōu)化管理方法[D].沈陽:東北大學,2005:64-65.

[9]韓瑞鋒.遺傳算法原理與應(yīng)用實例[M].北京:兵器工業(yè)出版社,2010:89-90.

[10]吳志遠,邵惠鶴,吳新余,等.一種新的自適應(yīng)遺傳算法及其在多峰值函數(shù)優(yōu)化中的應(yīng)用[J].控制理論與應(yīng)用,1999,16(1):127-129.

[11]劉民,吳澄.制造過程智能優(yōu)化調(diào)度算法及其應(yīng)用[M].北京:國防工業(yè)出版社,2008:39.

[12]金芬.遺傳算法在函數(shù)優(yōu)化中的應(yīng)用研究[D].蘇州:蘇州大學,2008:32.

[13]張玉萍.自適應(yīng)遺傳算法的研究及應(yīng)用[D].哈爾濱:哈爾濱工業(yè)大學,2009.

[14]金晶,蘇勇.一種改進的自適應(yīng)遺傳算法[J].計算機工程與應(yīng)用,2005,41(18):64-69.

[15]Renata FurtunaSilvia Curteanu ,Florin Leon.An elitist nondominated sorting genetic algorithm enhanced with a neural network applied to the multi-objective optimization of a polysiloxane synthesis process[J].Engineering Applications of Artificial Intelligence,2011,24(5):772-785.