基于AS-NSGA-Ⅱ算法的多旋轉(zhuǎn)貨架儲(chǔ)位優(yōu)化研究

段軍雨，芮萬智，賈正榮

(海軍工程大學(xué) 艦船綜合電力技術(shù)國(guó)防科技重點(diǎn)實(shí)驗(yàn)室，武漢 430033)

0 引言

多模塊旋轉(zhuǎn)貨架裝置以其周轉(zhuǎn)速度快、占地空間小、準(zhǔn)確率高等優(yōu)點(diǎn)常配置于現(xiàn)代物流倉(cāng)儲(chǔ)系統(tǒng)，廣泛用于種類、數(shù)量繁多貨品的控制和管理。儲(chǔ)位分配優(yōu)化針對(duì)貨品與貨架兩者的關(guān)系，使得貨品存儲(chǔ)順序、貨架倉(cāng)儲(chǔ)空間得到合理安排，實(shí)現(xiàn)高效入庫(kù)作業(yè)，以此達(dá)到提升貨架的協(xié)同作業(yè)效率、節(jié)省調(diào)度成本的目的。

儲(chǔ)位分配優(yōu)化的問題模型主要分為“網(wǎng)格填充式”自動(dòng)化立體倉(cāng)庫(kù)、“回轉(zhuǎn)排列式”旋轉(zhuǎn)貨架裝置。對(duì)于自動(dòng)化立體倉(cāng)庫(kù)的儲(chǔ)位優(yōu)化研究，分別以貨品的出入庫(kù)頻率[1]、貨架穩(wěn)定性[2]、貨品關(guān)聯(lián)性[3]、空間利用率[4]等為優(yōu)化目標(biāo)，或者結(jié)合多目標(biāo)[5-6]建立數(shù)學(xué)模型，取得了諸多有意義的研究成果；對(duì)于旋轉(zhuǎn)貨架模型采取的約束條件、優(yōu)化目標(biāo)較為單一，主要結(jié)合直觀的啟發(fā)式策略以縮短入庫(kù)時(shí)間[7]、保持貨架穩(wěn)定性[8]等為目標(biāo)，進(jìn)行旋轉(zhuǎn)貨架儲(chǔ)位分配模型的建立。

儲(chǔ)位分配優(yōu)化的求解算法主要是結(jié)合多目標(biāo)優(yōu)化模型進(jìn)行改進(jìn)，在不同程度上提高了原智能算法的求解效率。王賀[9]通過自適應(yīng)遺傳算法求解以貨品關(guān)聯(lián)規(guī)則、空間利用率為目標(biāo)的儲(chǔ)位分配問題；焦玉玲[10]設(shè)計(jì)了多種群遺傳算法，并采取加權(quán)方法將儲(chǔ)位優(yōu)化的多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)進(jìn)行求解；藺一帥[11]建立了以縮短作業(yè)時(shí)間、提升貨品相關(guān)度為目標(biāo)的儲(chǔ)位優(yōu)化模型，并結(jié)合改進(jìn)的協(xié)同優(yōu)化遺傳算法求解；印美[12]采取基于NSGA-Ⅱ和動(dòng)態(tài)倉(cāng)儲(chǔ)模式的優(yōu)化方法，求解能耗、貨架穩(wěn)定性、作業(yè)效率3個(gè)目標(biāo)的儲(chǔ)位優(yōu)化問題；朱杰[13]通過線性加權(quán)建立儲(chǔ)位優(yōu)化的多目標(biāo)模型，提出改進(jìn)的自適應(yīng)遺傳模擬退火算法求解；薛亞莉[14]提出一種基于遺傳模擬退火的Memetic算法求解貨位分配模型。

分析上述文獻(xiàn)可知，一方面，多目標(biāo)儲(chǔ)位優(yōu)化主要以立體倉(cāng)庫(kù)為問題模型，而對(duì)于旋轉(zhuǎn)貨架模型的存儲(chǔ)策略及優(yōu)化目標(biāo)單一，現(xiàn)有的多模塊、多目標(biāo)儲(chǔ)位優(yōu)化模型不能夠適用于旋轉(zhuǎn)貨架裝置的研究；另一方面，用于求解多目標(biāo)優(yōu)化問題的遺傳算法不斷深入推廣，改善了算法的求解性能，但以往僅基于遺傳算子或者進(jìn)化階段融入改進(jìn)策略，即單方面考慮進(jìn)化環(huán)境對(duì)個(gè)體或者種群的影響，仍存在一定的局限性。因此，本文建立包含作業(yè)能耗、裝置穩(wěn)定性以及存儲(chǔ)效率目標(biāo)的多旋轉(zhuǎn)貨架儲(chǔ)位優(yōu)化模型，提出一種基于自適應(yīng)策略的非支配排序遺傳算法(NSGA-ⅡBased on Adaptive Strategy, AS-NSGA-Ⅱ)用于求解多旋轉(zhuǎn)貨架裝置的最佳儲(chǔ)位分配方案，并通過仿真試驗(yàn)對(duì)比說明算法具備更優(yōu)的計(jì)算性能。

1 多旋轉(zhuǎn)貨架儲(chǔ)位優(yōu)化問題描述

多旋轉(zhuǎn)貨架裝置由N個(gè)旋轉(zhuǎn)貨架組合而成、并列擺放，允許混裝各類貨品，沿正、反方向任意轉(zhuǎn)動(dòng)。各個(gè)貨架包含的儲(chǔ)位大小相同、數(shù)量M不同(M={M1,…,My},y≤N)，貨品規(guī)格根據(jù)對(duì)應(yīng)的貨品種類確定，其中貨品規(guī)格是指存儲(chǔ)貨品占用的空間大小。多個(gè)出入庫(kù)堆垛機(jī)與各個(gè)貨架一一對(duì)應(yīng)，貨架勻速轉(zhuǎn)動(dòng)且按照貨品類別依次完成入庫(kù)，直至得到所有貨品的儲(chǔ)位分配結(jié)果?！盎剞D(zhuǎn)排列式”多旋轉(zhuǎn)貨架裝置如圖1所示。

圖1 多模塊旋轉(zhuǎn)貨架裝置示意圖

結(jié)合上述多旋轉(zhuǎn)貨架的存儲(chǔ)布局方式，將儲(chǔ)位優(yōu)化問題的調(diào)度原則總結(jié)為四項(xiàng)，具體內(nèi)容如下：

1)分散存儲(chǔ)原則：為避免某個(gè)貨架故障或阻塞，影響調(diào)度作業(yè)的進(jìn)行，使同一類型貨品分散存儲(chǔ)于各個(gè)貨架，即將各類貨品在多個(gè)旋轉(zhuǎn)貨架上“按比例分層”，以此為約束條件將問題轉(zhuǎn)化為單個(gè)旋轉(zhuǎn)貨架的儲(chǔ)位優(yōu)化。

2)貨架穩(wěn)定性原則：貨品分布需要保證裝置的受力均勻，避免因重量失衡而影響整個(gè)貨架的安全性。根據(jù)貨品的平面坐標(biāo)(x,y)(x表示旋轉(zhuǎn)貨架上的儲(chǔ)位坐標(biāo)，x≤M；y表示旋轉(zhuǎn)貨架編號(hào)，y≤N)以及對(duì)應(yīng)的貨品重量，計(jì)算貨架重心使其保持均衡。

3)存儲(chǔ)效率原則：堆垛機(jī)在順、逆時(shí)針方向均以速度v轉(zhuǎn)動(dòng)，不考慮堆垛機(jī)啟動(dòng)、操作等準(zhǔn)備時(shí)間，貨品的入庫(kù)效率能夠以過程中轉(zhuǎn)運(yùn)時(shí)間的數(shù)學(xué)期望來描述。

4)作業(yè)能耗原則：周轉(zhuǎn)率高、質(zhì)量大的貨品放置在離出貨口近的儲(chǔ)位上，能夠減少貨品出庫(kù)時(shí)的運(yùn)行成本，提升作業(yè)效率。考慮將儲(chǔ)位和貨品進(jìn)行編號(hào)，通過編號(hào)對(duì)應(yīng)得到儲(chǔ)位-貨品的耦合關(guān)系，表示儲(chǔ)位上貨品運(yùn)出時(shí)的能量消耗。方式如下：

①儲(chǔ)位編號(hào)：為產(chǎn)生儲(chǔ)位排序的優(yōu)先級(jí)，通過構(gòu)造儲(chǔ)位能耗算子[12]E排序各個(gè)儲(chǔ)位，表示為：

E=l×g×c

(1)

式中，g為重力加速度、c為摩擦系數(shù)、l為儲(chǔ)位到出入庫(kù)堆垛機(jī)的水平距離。將儲(chǔ)位能耗算子進(jìn)行排序得到儲(chǔ)位編號(hào)C，表示貨品轉(zhuǎn)運(yùn)消耗能量的高低。

②貨品編號(hào)：根據(jù)貨品立方體索引規(guī)則[15]，將貨品索引值(Cube-Per-Order，COI)進(jìn)行修改表示貨品編號(hào)：

(2)

式中，Ij為某類貨品j(j=1,…,K)的COI值，Sj為貨品j對(duì)應(yīng)的儲(chǔ)位空間(入庫(kù)數(shù)量×貨品規(guī)格)，fj為貨品j的周轉(zhuǎn)率，mj為貨品j的重量。依據(jù)COI值將貨品從小到大進(jìn)行排序，體現(xiàn)貨品的優(yōu)先調(diào)取順序。

2 多目標(biāo)儲(chǔ)位優(yōu)化數(shù)學(xué)模型

結(jié)合問題特點(diǎn)和調(diào)度原則，考慮以貨品分散存儲(chǔ)、貨架實(shí)際裝載情況為約束條件，將所有貨品進(jìn)行“分層”操作，使得原問題轉(zhuǎn)化為單個(gè)旋轉(zhuǎn)貨架的儲(chǔ)位優(yōu)化問題，以降低轉(zhuǎn)運(yùn)能耗、穩(wěn)定儲(chǔ)存重心、縮短入庫(kù)時(shí)間進(jìn)行多目標(biāo)優(yōu)化，從而構(gòu)建多旋轉(zhuǎn)貨架儲(chǔ)位優(yōu)化的數(shù)學(xué)模型：

1)貨品分散存儲(chǔ)。

依據(jù)旋轉(zhuǎn)貨架數(shù)量N、儲(chǔ)位數(shù)量M，將K類貨品進(jìn)行“按比例分層”，確定各個(gè)貨架上分配的貨品種類和數(shù)量，即得到每類貨品在各個(gè)貨架上分配的數(shù)量集合，數(shù)學(xué)描述為：

le(j)={|u1|,|u2|,…,|uy|}

(3)

(4)

式中，單個(gè)旋轉(zhuǎn)貨架上的儲(chǔ)位總數(shù)My；貨品j的庫(kù)存總數(shù)Uj；uy表示貨品的分層數(shù)量，|a|表示對(duì)a向上取整。

2)減少貨架轉(zhuǎn)運(yùn)能耗。

依據(jù)根據(jù)公式(1)、(2)得到的儲(chǔ)位編號(hào)C和貨品編號(hào)Ixy，完成各類貨品與儲(chǔ)位的合理對(duì)應(yīng)，即將COI值偏小的貨品與能耗算子低的儲(chǔ)位對(duì)應(yīng)，達(dá)到降低轉(zhuǎn)運(yùn)能耗的目的，即Ixy與C的乘積最小，數(shù)學(xué)描述為：

(5)

3)提高儲(chǔ)存重心穩(wěn)定性。

考慮到旋轉(zhuǎn)貨架水平放置，合理分配兩側(cè)貨品的重量來實(shí)現(xiàn)旋轉(zhuǎn)貨架穩(wěn)定，使得旋轉(zhuǎn)貨架的等效重心接近水平方向的中心軸線，即旋轉(zhuǎn)貨架的幾何重心與中心軸線的距離最短，數(shù)學(xué)描述為：

minFG(x,y)=

(6)

(7)

(8)

式中，w為單個(gè)儲(chǔ)位寬度；XG1、XG2表示旋轉(zhuǎn)貨架等效的幾何重心位置；X1、X2表示中心軸線位置；mxy表示貨品重量。

4)減少貨品入庫(kù)時(shí)間。

為提高作業(yè)效率，旋轉(zhuǎn)貨架按照類別依次裝載貨品、規(guī)劃轉(zhuǎn)運(yùn)路徑，能夠有效縮短貨架轉(zhuǎn)運(yùn)時(shí)間，即使得周轉(zhuǎn)率越高的貨品入庫(kù)時(shí)間越短，以貨品入庫(kù)時(shí)轉(zhuǎn)運(yùn)時(shí)間的期望值最小為目標(biāo)，數(shù)學(xué)描述為

(9)

式中，fxy為旋轉(zhuǎn)貨架y、儲(chǔ)位坐標(biāo)x上貨品的周轉(zhuǎn)率；txy表示該儲(chǔ)位貨品完成入庫(kù)的轉(zhuǎn)運(yùn)時(shí)間；

因此，多目標(biāo)儲(chǔ)位優(yōu)化模型描述為：

(10)

(11)

3 AS-NSGA-Ⅱ的算法實(shí)現(xiàn)

NSGA-Ⅱ是用結(jié)合遺傳算法解決多目標(biāo)優(yōu)化問題的常用算法，為協(xié)調(diào)各個(gè)目標(biāo)函數(shù)間的沖突關(guān)系，主要通過3種方式：精英策略選擇、快速非支配排序、擁擠距離計(jì)算[16]。多旋轉(zhuǎn)貨架的儲(chǔ)位優(yōu)化問題屬于多變量多約束問題，采取NSGA-Ⅱ求解存在后期收斂速度慢、解集多樣性不理想的現(xiàn)象，適應(yīng)性策略能夠抑制該現(xiàn)象的發(fā)生。然而原始適應(yīng)策略通常以進(jìn)化環(huán)境和種群進(jìn)行分類[17]，未結(jié)合兩者考慮使其存在局限性，自適應(yīng)策略在此基礎(chǔ)上進(jìn)行改進(jìn)，實(shí)現(xiàn)進(jìn)化環(huán)境、種群以及非支配分層等級(jí)對(duì)遺傳算子的改善。

AS-NSGA-Ⅱ的設(shè)計(jì)及流程：

針對(duì)原始適應(yīng)策略與NSGA-Ⅱ的缺陷，AS-NSGA-Ⅱ通過引入自適應(yīng)策略，即設(shè)計(jì)選擇操作方式，交叉算子、變異算子的動(dòng)態(tài)調(diào)整模型，提升原算法的全局尋優(yōu)性能。為便于闡述算法步驟，對(duì)涉及的參數(shù)進(jìn)行定義如表1所示。

表1 算法參數(shù)定義

1)編碼、解碼方式。

初始種群的染色體編碼采用實(shí)數(shù)編碼方式，為便于計(jì)算將環(huán)形貨架進(jìn)行線性展開，依據(jù)儲(chǔ)位排列方式得到編碼X。取m個(gè)互不重復(fù)的隨機(jī)整數(shù)組成一個(gè)染色體(取值范圍[1,M])，即表示進(jìn)化過程中的一種儲(chǔ)位分配方式，染色體中的每個(gè)基因元素表示相應(yīng)的儲(chǔ)位位置，形如：

解碼時(shí)根據(jù)貨品類別以及入庫(kù)數(shù)量，將染色體編碼進(jìn)行分區(qū)，每個(gè)元素值在劃分后得到對(duì)應(yīng)的分區(qū)類別則作為解碼值Y，當(dāng)類別k∈[1,3]時(shí)，染色體的編碼、解碼表示為：

Y:1,1,1,1,2,2,2,2,2,3,…,3

由解碼值組成的整數(shù)序列對(duì)應(yīng)染色體編碼中的基因元素，即為各類別貨品分配的儲(chǔ)位位置，所有染色體的編碼、解碼值組成規(guī)模為N×m的數(shù)組表示貨品的儲(chǔ)位分配方案。

2)選擇操作設(shè)計(jì)。

NSGA-Ⅱ算法常使用二元制錦標(biāo)賽進(jìn)行選擇和精英保留，該方式在進(jìn)化前期選擇父代個(gè)體通常發(fā)生局部收斂現(xiàn)象，不能保證解集的多樣性。為此，本文結(jié)合自適應(yīng)策略能夠動(dòng)態(tài)調(diào)整目標(biāo)函數(shù)值，采用輪盤賭法進(jìn)行并列選擇父代個(gè)體，提升算法收斂速度并保證解集空間分布均勻。

其中，并列選擇是在執(zhí)行選擇操作之前，將染色體種群劃分成多個(gè)子種群，種群數(shù)量同目標(biāo)函數(shù)數(shù)量，使得子種群與目標(biāo)函數(shù)一一對(duì)應(yīng)。根據(jù)目標(biāo)函數(shù)適應(yīng)度計(jì)算概率，通過輪盤賭法在各個(gè)子種群中并列進(jìn)行、按概率選擇，最后合并成新的染色體選擇種群。

sigmoid曲線函數(shù)[14]能夠平衡線性和非線性之間的取值，自適應(yīng)選擇方式基于sigmoid函數(shù)進(jìn)行改進(jìn)，根據(jù)迭代次數(shù)、非支配分層等級(jí)調(diào)整個(gè)體的目標(biāo)函數(shù)適應(yīng)度，表示為：

(12)

因此，在每代進(jìn)行輪盤賭選擇時(shí)，依據(jù)自適應(yīng)策略得到個(gè)體的選擇概率為:

3)交叉操作設(shè)計(jì)。

排列優(yōu)化問題中的染色體基因元素通常只出現(xiàn)一次，若保持NSGA-Ⅱ常用的模擬二進(jìn)制交叉，會(huì)使得染色體中的基因元素排列紊亂。針對(duì)研究的儲(chǔ)位優(yōu)化實(shí)數(shù)編碼方式，本文采用部分映射交叉算子(PMX)進(jìn)行交叉，即個(gè)體間部分基因元素進(jìn)行互換，通過映射操作保證染色體無重復(fù)、排列合理，如圖2所示。

圖2 交叉操作

為提升算法整體的搜索速度，抑制種群陷入局部最優(yōu)解，一方面交叉操作基于進(jìn)化環(huán)境(進(jìn)化階段、非支配分層等級(jí))交叉率實(shí)現(xiàn)自適應(yīng)調(diào)整，并且為保留每代種群中的較優(yōu)個(gè)體，將交叉算子調(diào)整模型分為兩種，表示如下：支配個(gè)體交叉率：

(13)

非支配個(gè)體交叉率：

(14)

另一方面，為提高種群的環(huán)境適應(yīng)性，動(dòng)態(tài)調(diào)整隨機(jī)選擇的交叉映射區(qū)域，并且合理設(shè)置α(α∈(0,2])保證操作的基因個(gè)數(shù)為非零漸近值，本文設(shè)置為1.5，表示為:

(15)

4)變異操作設(shè)計(jì)。

針對(duì)旋轉(zhuǎn)貨架的儲(chǔ)位分配特點(diǎn)，變異操作采用基因位對(duì)調(diào)方式，并設(shè)定個(gè)體變異時(shí)選擇解碼值不同的基因位對(duì)調(diào)，避免同類貨品儲(chǔ)位間的循環(huán)變異。為提升精英個(gè)體(適應(yīng)度高的個(gè)體)的選中概率，結(jié)合自適應(yīng)策略調(diào)整變異率、區(qū)域。變異算子的調(diào)整模型表示如下：

支配個(gè)體變異率：

(16)

非支配個(gè)體變異率：

(17)

基因位對(duì)調(diào)區(qū)域：

Lm=ceil(rank(i)/eα)

(18)

5)最優(yōu)個(gè)體選擇。

在求解j個(gè)目標(biāo)的問題優(yōu)化時(shí)，由于解集中目標(biāo)函數(shù)的單位、量級(jí)不同，因此要通過歸整處理對(duì)其進(jìn)行調(diào)整，并得到個(gè)體的目標(biāo)函數(shù)值適應(yīng)度，表示為：

(19)

(20)

式中，β參數(shù)的取值為0.005，其設(shè)定是為了避免目標(biāo)函數(shù)值出現(xiàn)超出閾值的計(jì)算結(jié)果。

設(shè)定適應(yīng)度參考指標(biāo)為(1,1,1,…,1)K，尋找近似參考指標(biāo)最大的個(gè)體，確定其為Pareto最優(yōu)解集中的最優(yōu)個(gè)體，即H(max)=H(i)，則Pbest=P(i)。

6)算法實(shí)現(xiàn)。

基于AS- NSGA-Ⅱ求解多旋轉(zhuǎn)貨架儲(chǔ)位優(yōu)化模型的步驟如下。

輸入：訂單任務(wù)信息(入庫(kù)任務(wù)類型、貨品種類及數(shù)量)，貨架編號(hào)；

輸出：各個(gè)貨架的貨品種類、數(shù)量，儲(chǔ)位分配結(jié)果；

Step1：初始化算法參數(shù)(pop、D、Pc、Pm)，采取實(shí)數(shù)編碼、解碼生成初始種群，；

Step2：對(duì)種群個(gè)體進(jìn)行非支配等級(jí)劃分， 計(jì)算個(gè)體的適應(yīng)度值、擁擠度距離，并進(jìn)行賦值更新；

Step3：根據(jù)自適應(yīng)策略調(diào)整目標(biāo)函數(shù)值，通過輪盤賭方式并列選擇多個(gè)子種群，合并成新種群；

Step4：通過設(shè)計(jì)的交叉、變異操作得到與父代種群Pk相同規(guī)模的子代種群Ok；

Step5：父代種群Pk、子代種群Ok組成中間子群，依據(jù)其非支配排序分層等級(jí)、擁擠度距離進(jìn)行排序，通過二元制錦標(biāo)賽方式保留固定數(shù)量的精英個(gè)體，得到進(jìn)入下一代的新種群；

Step6：判斷算法是否滿足最大進(jìn)化次數(shù)，若滿足，輸出pareto最優(yōu)解集、前沿，否則返回Step2；

Step7：通過目標(biāo)函數(shù)歸一化，從pareto最優(yōu)解集中選取最優(yōu)個(gè)體，得到最佳儲(chǔ)位分配方案。

AS- NSGA-Ⅱ算法流程圖如圖3所示。

圖3 儲(chǔ)位優(yōu)化求解的算法流程圖

4 實(shí)驗(yàn)分析

4.1 算例分析

4.1.1 測(cè)試參數(shù)設(shè)置

本文以某軍械倉(cāng)庫(kù)的一條自動(dòng)化生產(chǎn)線為例，配置的多旋轉(zhuǎn)貨架裝置數(shù)量為10，每個(gè)貨架的儲(chǔ)位數(shù)量在80～100之間隨機(jī)選取，儲(chǔ)位大小為1×1m2，水平轉(zhuǎn)動(dòng)速度為0.12 m/s。根據(jù)某次執(zhí)行的入庫(kù)訂單任務(wù)，貨品參數(shù)如表2所示，周轉(zhuǎn)率表示貨品入庫(kù)次數(shù)占總次數(shù)的百分比，編號(hào)根據(jù)貨品COI值而定。

表2 入庫(kù)任務(wù)貨品參數(shù)

為驗(yàn)證本文算法的求解效果和性能優(yōu)勢(shì)，根據(jù)貨品參數(shù)得到的“分層”結(jié)果，采用NSGA-Ⅱ、多種群遺傳算法[10](MPGA)以及本文的AS-NSGA-Ⅱ?qū)Χ嗄繕?biāo)儲(chǔ)位優(yōu)化進(jìn)行測(cè)試。通過Matlab實(shí)現(xiàn)算法編程、模擬數(shù)值計(jì)算，設(shè)置種群規(guī)模p=300，最大進(jìn)化次數(shù)D=500，初始交叉概率Pc0=0.5，變異概率Pm0=0.05。

4.1.2 模型驗(yàn)證

為驗(yàn)證多目標(biāo)優(yōu)化模型的正確性，分別以(能耗)FE、(重心差值)FG/m、(轉(zhuǎn)運(yùn)時(shí)間)FT/s進(jìn)行優(yōu)化，將求解結(jié)果與基于多目標(biāo)優(yōu)化的最優(yōu)解進(jìn)行對(duì)照分析，對(duì)比結(jié)果如表3所示。

表3 單目標(biāo)、多目標(biāo)優(yōu)化結(jié)果對(duì)比

由表3可以看出，相比以FE最小進(jìn)行的單目標(biāo)優(yōu)化，多目標(biāo)優(yōu)化結(jié)果以增加能耗指標(biāo)為代價(jià)，不僅減小了重心差值，而且縮減了轉(zhuǎn)運(yùn)時(shí)間。同樣，分別對(duì)比以FG最小、FT最小的單目標(biāo)優(yōu)化，多目標(biāo)優(yōu)化都能夠降低另外兩個(gè)目標(biāo)函數(shù)值，由此，可得多目標(biāo)優(yōu)化符合Pareto最優(yōu)解集思想，驗(yàn)證了多旋轉(zhuǎn)貨架儲(chǔ)位優(yōu)化模型的正確性。

4.1.3 目標(biāo)函數(shù)值對(duì)比分析

根據(jù)選取的最優(yōu)個(gè)體確定最佳儲(chǔ)位分配方案，對(duì)比傳統(tǒng)方法(順序存儲(chǔ))與各算法優(yōu)化后的3個(gè)目標(biāo)函數(shù)值。由表4可知，較傳統(tǒng)方法求解，NSGA-Ⅱ、MPGA、AS- NSGA-Ⅱ?qū)τ贔E目標(biāo)值分別降低了47.0%、46.4%、40.7%；對(duì)于FG目標(biāo)值分別降低了93.53%、95.02%、94.03%；對(duì)于FT目標(biāo)值分別降低了37.4%、35.8%、44.6%；在Pareto前沿中各目標(biāo)函數(shù)值存在競(jìng)爭(zhēng)，其中一個(gè)減小會(huì)引起其他兩個(gè)目標(biāo)函數(shù)值變化，因此，各算法對(duì)于能耗FE、轉(zhuǎn)運(yùn)時(shí)間FT的優(yōu)化率在合理范圍內(nèi)，能夠保證Pareto前沿質(zhì)量。然而在實(shí)際倉(cāng)儲(chǔ)應(yīng)用中，衡量調(diào)度作業(yè)效率的轉(zhuǎn)運(yùn)時(shí)間FT作為首要目標(biāo)，AS- NSGA-Ⅱ的儲(chǔ)位優(yōu)化結(jié)果更符合預(yù)期。

表4 各算法優(yōu)化結(jié)果

4.2 算法性能分析

4.2.1 性能分析指標(biāo)

用于分析多目標(biāo)優(yōu)化算法的性能指標(biāo)主要涵蓋兩部分[18]：

1)算法的時(shí)間復(fù)雜度。AS- NSGA-Ⅱ算法是對(duì)NSGA-Ⅱ算法加入自適應(yīng)策略的改進(jìn)，一方面通過輪盤賭方式對(duì)種群進(jìn)行并行分類選擇，另一方面對(duì)交叉算子、變異算子增加動(dòng)態(tài)調(diào)整操作，兩方面在操作步驟中并行調(diào)整且均為線性，因此兩者的時(shí)間復(fù)雜度一致均為O(mn2)，其中其中m為優(yōu)化目標(biāo)數(shù)量、n為進(jìn)化個(gè)體數(shù)量；AS- NSGA-Ⅱ算法與MPGA算法對(duì)比，MPGA算法在構(gòu)建初始種群時(shí)生成多個(gè)子種群，解集在子種群間協(xié)同進(jìn)化、串聯(lián)進(jìn)行，時(shí)間復(fù)雜度為O(lmn2)高于AS- NSGA-Ⅱ算法，其中l(wèi)為種群數(shù)量。

2)評(píng)價(jià)解集的收斂性和多樣性。算法在保證Pareto前沿質(zhì)量，使求得Pareto最優(yōu)解集盡可能接近理想最優(yōu)解的同時(shí)，提升解集的收斂性和多樣性。分別采取收斂性準(zhǔn)則[19](GD,generational distance)、分布多樣性準(zhǔn)則[20](Diversity MetricΔ)評(píng)價(jià)算法的收斂性、多樣性，定義如下：

(21)

(22)

其中:GD值越小，表示Pareto前沿與最優(yōu)目標(biāo)函數(shù)值的差距越小，代表收斂性更好；Δ值越小，Pareto前沿邊界值與極端值的距離越小，連續(xù)解向量之間的距離與均值越相近，代表多樣性更好。

4.2.2 結(jié)果和分析

1)算法收斂性分析。

通過圖4可知，AS- NSGA-Ⅱ在進(jìn)化前期不易陷入“早熟”，收斂速度比NSGA-Ⅱ、MPGA更快，并且在進(jìn)化后期個(gè)體與Pareto前沿的距離更近。這是由于引入自適應(yīng)的并列選擇方式，提升了個(gè)體對(duì)于目標(biāo)函數(shù)值的選擇靈敏度。

圖4 收斂性測(cè)試結(jié)果

為驗(yàn)證各個(gè)算法的求解結(jié)果是否存在顯著差異，采取3種算例輸入，對(duì)每個(gè)算法進(jìn)行100次重復(fù)試驗(yàn)，計(jì)算GD指標(biāo)的均值、方差如表5所示。

表5 收斂性評(píng)價(jià)指標(biāo)分析

由表5分析可知，3種算例情況下，AS- NSGA-Ⅱ求得Pareto最優(yōu)解集的收斂性能指標(biāo)值更小，表現(xiàn)的全局收斂性更優(yōu)。

2)算法多樣性分析。

由圖5可以看出，NSGA-Ⅱ、MPGA 求得的Pareto最優(yōu)解集空間分布不均勻，而AS- NSGA-Ⅱ?qū)?yīng)解集的空間分布性更好、更加均勻，這是由于根據(jù)進(jìn)化階段和非支配分層等級(jí)，自適應(yīng)調(diào)整交叉、變異率以及交叉、變異區(qū)域，提升了種群和個(gè)體對(duì)環(huán)境的適應(yīng)能力。

圖5 算法多樣性測(cè)試結(jié)果

為具體比較算法的多樣性指標(biāo)Δ，采取3種算例輸入，同樣對(duì)每個(gè)算法進(jìn)行100次重復(fù)試驗(yàn)并計(jì)算Δ的均值和方差，如表6所示。

表6 多樣性評(píng)價(jià)指標(biāo)分析

由表6可知，算例3 中AS- NSGA-Ⅱ的Δ均值和方差均為最小，表現(xiàn)多樣性更好，雖然算例1、2中AS- NSGA-Ⅱ多樣性指標(biāo)方差略高于其他兩個(gè)算法，但其多樣性指標(biāo)均值為最優(yōu)，提升了原算法Pareto最優(yōu)解集的多樣性。

5 結(jié)束語

本文結(jié)合多旋轉(zhuǎn)貨架的儲(chǔ)位分配原則，以轉(zhuǎn)運(yùn)能耗最低、儲(chǔ)存重心最穩(wěn)、入庫(kù)時(shí)間最短作為優(yōu)化目標(biāo)，建立旋轉(zhuǎn)貨架儲(chǔ)位分配的多目標(biāo)優(yōu)化數(shù)學(xué)模型，并改進(jìn)、設(shè)計(jì)非支配排序遺傳算法，提出了一種AS- NSGA-Ⅱ算法求解儲(chǔ)位分配模型。該算法考慮進(jìn)化環(huán)境對(duì)個(gè)體或者種群的影響，結(jié)合輪盤賭法進(jìn)行并列選擇進(jìn)化個(gè)體，通過進(jìn)化環(huán)境動(dòng)態(tài)調(diào)整交叉、變異率和交叉、變異范圍，對(duì)Pareto前沿進(jìn)行加權(quán)歸一化處理得到儲(chǔ)位分配最優(yōu)方案，同時(shí)給出了自適應(yīng)模型實(shí)現(xiàn)運(yùn)行參數(shù)的調(diào)整，達(dá)到自適應(yīng)進(jìn)化的效果。仿真實(shí)驗(yàn)分析表明，AS- NSGA-Ⅱ算法具有更好的收斂性、多樣性以及執(zhí)行效率，對(duì)于求解多旋轉(zhuǎn)貨架儲(chǔ)位優(yōu)化問題具有良好的計(jì)算性能。