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

宋賀騰，鄒 方

（1.北京航空航天大學(xué) 機(jī)械工程及自動(dòng)化學(xué)院，北京 100191；2.北京航空制造工程研究所，北京 100024）

0 引言

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

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

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

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

1.1 基本假設(shè)

本實(shí)驗(yàn)基于以下情景設(shè)定進(jìn)行：

1）該立體庫(kù)有一個(gè)通道，一臺(tái)堆垛機(jī)，一排貨架，堆垛機(jī)在一側(cè)開始對(duì)貨架進(jìn)行操作出入庫(kù)操作，且初始位置為0000。

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

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

圖1 貨位號(hào)排列簡(jiǎn)圖

4）視堆垛機(jī)水平和垂直方向?yàn)閯蛩龠\(yùn)動(dòng)。

1.2 模型描述

下面定義相關(guān)符號(hào)，用于描述本實(shí)驗(yàn)。

立體庫(kù)有n列m行；Vx和Vy代表堆垛機(jī)水平和垂直方向速度；Lx和Ly代表貨位長(zhǎng)和高。

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

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

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

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

式中：Fit2代表物資距離加工的時(shí)間和揀選此物資堆垛機(jī)的運(yùn)行時(shí)間之和；Lx表示貨位長(zhǎng)度；Ly表示貨位寬度；tij代表將本物資搬運(yùn)到庫(kù)臺(tái)所需要時(shí)間；Tij代表本物資距離開始加工時(shí)間。

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

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

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

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

式中：T00表示堆垛機(jī)從原點(diǎn)到第一個(gè)庫(kù)位經(jīng)歷的時(shí)間；Ti0表示堆垛機(jī)從當(dāng)前貨位到庫(kù)臺(tái)所需時(shí)間；Ti（i+1）表示堆垛機(jī)從當(dāng)前貨位到下一貨位所經(jīng)歷時(shí)間；Tn0表示堆垛機(jī)送回最后一個(gè)貨位托盤后回到庫(kù)臺(tái)所需時(shí)間。

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

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

兩目的地間從至?xí)r間T計(jì)算方法如下：

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

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

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

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

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

2.1 染色體編碼

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

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

2.2 種群初始化

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

圖3 約束條件

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

圖4 約束轉(zhuǎn)換

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

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

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

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

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

2.4 遺傳算子設(shè)計(jì)

2.4.1 選擇

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

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

2.4.2 交叉和變異

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

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

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

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

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

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

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

3 實(shí)驗(yàn)仿真與評(píng)價(jià)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

兩種算法都使立體庫(kù)整體重心下移，穩(wěn)定性增強(qiáng)。以列數(shù)為橫坐標(biāo)，層數(shù)為縱坐標(biāo)，表1為優(yōu)化前后情況對(duì)比。描述了優(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%，堆垛機(jī)總運(yùn)行時(shí)間由原195.6秒縮短為150.1秒和140.2秒（本文僅考慮堆垛機(jī)往返行程時(shí)間），縮短23.3%和28.3%。對(duì)分析可以看出，自適應(yīng)遺傳算法相比普通遺傳算法優(yōu)化效果較好。

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

4 結(jié)論

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

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

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

[2]陳元文,吳曉波,孫耀磊,等.基于遺傳算法的軍隊(duì)立體倉(cāng)庫(kù)貨位再分配研究[J].計(jì)算機(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]劉金平,周炳海,奚立峰,等.在線自動(dòng)化立體倉(cāng)庫(kù)的庫(kù)位分配方法及其實(shí)證研究[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]陳月婷,何芳.基于改進(jìn)粒子群算法的立體倉(cāng)庫(kù)貨位分配優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用,2008,(11):229-236.

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

[8]沙麗娜.自動(dòng)化立體倉(cāng)庫(kù)貨位優(yōu)化管理方法[D].沈陽(yáng):東北大學(xué),2005:64-65.

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

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

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

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

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

[14]金晶,蘇勇.一種改進(jìn)的自適應(yīng)遺傳算法[J].計(jì)算機(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.