基于NSGA-Ⅱ算法的備件存儲(chǔ)分配優(yōu)化研究?

柴志君 歐陽(yáng)中輝 劉文彪

（1.海軍航空大學(xué)岸防兵學(xué)院研究生大隊(duì) 煙臺(tái) 264001）（2.海軍航空大學(xué)岸防兵學(xué)院304教研室 煙臺(tái) 264001）

1 引言

隨著我國(guó)航母事業(yè)的發(fā)展，航母戰(zhàn)斗力的逐步形成，以及出海、訓(xùn)練等任務(wù)的不斷增多，所面臨的保障問(wèn)題也越來(lái)越多。航母上的備件艙空間十分有限，因此怎樣合理有效地利用有限的空間，使備件得到最優(yōu)化的存儲(chǔ)，是一個(gè)亟需解決的問(wèn)題。目前，艦上備件存儲(chǔ)分配以人工為主，所依賴的是艦員的知識(shí)和經(jīng)驗(yàn)，其效率會(huì)因人而異，雖然減少了計(jì)算機(jī)等設(shè)備投入費(fèi)用，但存在明顯缺點(diǎn):出錯(cuò)率高、分配效率低、需要大量人力。為解決這一問(wèn)題，可采用計(jì)算機(jī)輔助分配方式。這種分配方式是利用圖形監(jiān)控系統(tǒng)，收集備件存放位置信息并顯示其使用情況，供艦員實(shí)時(shí)查詢，為備件存儲(chǔ)分配提供參考，可以很好地解決人工分配存在的不足［1～3］。

2 備件存儲(chǔ)分配的優(yōu)化

2.1 基本原則

1）備件存放架的受力情況良好。較重的備件存放在較低的位置，較輕的備件存放在高處的位置，以保證存放架相對(duì)穩(wěn)定和牢固。備件應(yīng)分散在存放艙室的不同位置，以避免由于集中存放而引起存放架受力不均等問(wèn)題。

2）提高備件使用效率。使用頻率越高的備件所存放的位置應(yīng)更容易取存，并且離存放艙室的出入口更近，以縮短應(yīng)急情況下取用備件所需的時(shí)間。同種備件使用時(shí)，應(yīng)先取用先入艙室存放的備件，以避免因備件長(zhǎng)期積壓造成銹蝕、變形、變質(zhì)等損壞［4～6］。

2.2 建立數(shù)學(xué)模型

設(shè)備件的種類編號(hào)依次為｛1，2，…，p｝，其中i類備件的立方體索引號(hào)COI（cube per order index）值為Ih（0 ＜h ≤p）:

其中:Ch為h 類備件存儲(chǔ)所需的容量，fh為h 類備件的出庫(kù)頻率。

COI 值的大小描述了備件出入庫(kù)頻率的高低。給定一個(gè)m 層n 排的備件存放架，設(shè)每個(gè)備件存放位長(zhǎng)度為L(zhǎng)，高度為H，并把最低層記為第1層，距離巷道口最近的排記為第1 排，處于第i排第j 層的備件存放位置記為（i，j）（i=1，2，…，n；j=1，2，…，m）。

1）為保證備件存放架受力情況良好，應(yīng)使質(zhì)量（用mij表示）較小的備件盡量放在存放架的高處，即:

式中:f1為備件所在層編號(hào)與質(zhì)量mij之商。

2）為實(shí)現(xiàn)備件使用效率最大化，所有備件的COI 值就應(yīng)與其所分配的備件區(qū)編號(hào)的乘積之和盡可能?。?～10］，即:

2.3 約束條件

1）在文獻(xiàn)［7］中，POTRC 對(duì)貨架寬度與高度之比對(duì)立體倉(cāng)庫(kù)性能產(chǎn)生的影響進(jìn)行了討論，這里作為備件存放架性能的參考，根據(jù)文中的計(jì)算結(jié)果，設(shè)寬度為L(zhǎng)，高度為H，則理想比值為

2）備件在任意兩點(diǎn)（i1，j1）和（i2，j2）進(jìn)行存放作業(yè)時(shí)，存放次序應(yīng)該滿足由近及遠(yuǎn)的原則，即:i1≤i2，j1≤j2。 而備件在任意兩點(diǎn)（i3，j3）和（i4，j4）進(jìn)行取出操作時(shí)，則應(yīng)滿足由遠(yuǎn)及近的原則，即:

3）在存放備件時(shí)，要保證備件所存儲(chǔ)的位置為空，即:

對(duì)備件存儲(chǔ)分配的優(yōu)化，需要同時(shí)滿足式（2）～（3）的要求。這兩個(gè)公式一般情況下是相互矛盾的，所以優(yōu)化問(wèn)題的求解就是一個(gè)多目標(biāo)優(yōu)化問(wèn)題。加入約束條件（4）～（6）后，該問(wèn)題就成為一個(gè)約束多目標(biāo)優(yōu)化問(wèn)題。對(duì)于約束多目標(biāo)優(yōu)化問(wèn)題的求解，一般可以采用如下數(shù)學(xué)模型進(jìn)行描述［11］:

3 NSGA-II多目標(biāo)優(yōu)化算法介紹

多目標(biāo)優(yōu)化問(wèn)題（MPO）［12］在現(xiàn)實(shí)生活和工程應(yīng)用中都具有非常重要的地位，這些問(wèn)題通常具有復(fù)雜的約束條件，各約束條件和目標(biāo)函數(shù)之間又存在復(fù)雜多樣的聯(lián)系。NSGA-II 算法（第2 代非劣解排序遺傳算法）適應(yīng)于復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題，由K-Deb 教授于2002 在論文《A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II》中提出，是目前最優(yōu)秀的進(jìn)化多目標(biāo)算法之一［13］。

NSGA-Ⅱ算法的運(yùn)算步驟主要有種群初始化（initialize variables）、快速非支配排序和擁擠都計(jì)算（non dominate sort and crowding distance）、錦標(biāo)賽選擇（tournament selection）、遺傳操作（genetic operator 包括交叉和變異操作）、替代操作（replace chromosome）。

NSGA-II 是NSGA 算法的改進(jìn)版，其改進(jìn)主要是針對(duì)以下三個(gè)方面:

1）提出了快速非支配排序算法，一方面使計(jì)算復(fù)雜度降低，另一方面將父代和子代種群進(jìn)行合并，使得下一代的種群可以從雙倍的空間中進(jìn)行選取，進(jìn)而使保留的所有個(gè)體最優(yōu)化；

2）引進(jìn)精英策略，以確保在進(jìn)化過(guò)程中某些優(yōu)良的種群個(gè)體不會(huì)被丟棄，從而提高了優(yōu)化結(jié)果的準(zhǔn)確度；

3）采用擁擠度和擁擠度比較算子，不但克服了NSGA 中需要人為指定共享參數(shù)的缺陷，而且將其作為種群中個(gè)體間的比較標(biāo)準(zhǔn)，使得準(zhǔn)Pareto 域中的個(gè)體能均勻地?cái)U(kuò)展到整個(gè)Pareto 域，保證了種群的多樣性［14～16］。

4 備件存儲(chǔ)分配優(yōu)化模型計(jì)算及仿真

鑒于NSGA-II 的以上優(yōu)點(diǎn)和在處理多目標(biāo)約束優(yōu)化問(wèn)題上的成功應(yīng)用，本文基于NSGA-Ⅱ算法對(duì)模型進(jìn)行求解，并將結(jié)果與多目標(biāo)粒子群算法（MPSO）對(duì)比說(shuō)明?？疾炷硞浼揂 存放架為6排、10層，架寬為20cm，備件編號(hào)、數(shù)量、質(zhì)量、使用頻率等信息情況如表1所示。

表1 備件信息統(tǒng)計(jì)表

本文針對(duì)該備件艙存儲(chǔ)分配優(yōu)化模型應(yīng)用NSGA-Ⅱ算法求解的總流程圖如圖1所示。

該求解過(guò)程的主要步驟有以下幾點(diǎn)［17］:

1）隨機(jī)產(chǎn)生種群大小為200的初始種群P0；

2）計(jì)算種群Pt目標(biāo)函數(shù)值并進(jìn)行非劣排序；

3）對(duì)種群Pt執(zhí)行遺傳操作（模擬二進(jìn)制交叉和多項(xiàng)式變異）得到子代種群Qt；

4）種群合并Rt=Pt∪Ut對(duì)Rt中的個(gè)體進(jìn)行非劣排序、擁擠度距離計(jì)算；

5）運(yùn)用錦標(biāo)賽規(guī)則選擇并保留精英個(gè)體選取前N 個(gè)個(gè)體作為父代種群Pt+1；

6）循環(huán)執(zhí)行程序并進(jìn)行終止條件判斷，按照事先設(shè)置好最大遺傳代數(shù)判斷，若t＞400算法終止。

在試驗(yàn)中，取種群最大規(guī)模為200，交叉概率pc=0.7，變異概率pm=0.1，最大允許進(jìn)化代數(shù)Genmax=400，采用Matlab 平臺(tái)構(gòu)造備件存儲(chǔ)分配優(yōu)化模型并進(jìn)行仿真［18～21］，可得目標(biāo)函數(shù)f1和f2的迭代曲線如圖2和圖3所示。

圖1 模型求解總流程圖

圖2 目標(biāo)函數(shù)f1 的迭代曲線

圖3 目標(biāo)函數(shù)f2 的迭代曲線

5 結(jié)果分析

本文在對(duì)備件艙A 備件存儲(chǔ)分配優(yōu)化過(guò)程中，求解模型時(shí)采用了NSGA-Ⅱ算法和MPSO 算法來(lái)進(jìn)行效果比較，得到兩種算法的帕累托（Pareto）前沿如圖4所示。

圖4 帕累托前沿比較圖

從圖4 可以看出NSGA-Ⅱ算法的帕累托前沿點(diǎn)數(shù)多于MPSO 算法的點(diǎn)數(shù)，說(shuō)明NSGA-Ⅱ算法的求解效果要優(yōu)于MPSO 求解結(jié)果，證明該算法在求解備件存儲(chǔ)分配優(yōu)化問(wèn)題上具有優(yōu)越性。

通過(guò)NSGA-Ⅱ算法求解對(duì)表1 中備件原存儲(chǔ)方法（如圖5所示）進(jìn)行優(yōu)化，可得到圖6所示結(jié)果。

圖5 優(yōu)化前的擺放圖

圖6 優(yōu)化后的擺放圖

圖中（0，0）點(diǎn)表示備件艙出口，可以看出經(jīng)過(guò)優(yōu)化后的備件存放位置滿足f1和f2目標(biāo)函數(shù)最小化的要求，證明了NSGA-Ⅱ算法在求解備件存儲(chǔ)分配優(yōu)化問(wèn)題上具有可行性。

6 結(jié)語(yǔ)

本文以最低出庫(kù)時(shí)間和最低重心為目標(biāo)函數(shù)，考慮了基本約束、存放架高度和寬度對(duì)性能影響以及存取原則等方面的約束建立存儲(chǔ)分配模型。對(duì)某備件艙A 進(jìn)行優(yōu)化模型的計(jì)算與仿真，運(yùn)用NSGA-Ⅱ算法計(jì)算過(guò)程中可得到足夠多且分布均勻地Pareto 前沿，并與MPSO 算法計(jì)算結(jié)果進(jìn)行比較，證明其優(yōu)越性。NSGA-Ⅱ算法作為進(jìn)化算法中最成熟、應(yīng)用最廣泛的算法之一，其收斂速度快，約束表示靈活，算法的準(zhǔn)確性高穩(wěn)定性好。最后通過(guò)仿真得出優(yōu)化后的備件擺放圖，進(jìn)一步證明NSGA-Ⅱ算法在解決備件存儲(chǔ)分配優(yōu)化問(wèn)題中的可行性，為在艦上采用計(jì)算機(jī)輔助分配方法管理備件提供了參考。