基于NSGA-Ⅱ算法的備件存儲分配優化研究?

柴志君 歐陽中輝 劉文彪

（1.海軍航空大學岸防兵學院研究生大隊 煙臺 264001）（2.海軍航空大學岸防兵學院304教研室 煙臺 264001）

1 引言

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

2 備件存儲分配的優化

2.1 基本原則

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

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

2.2 建立數學模型

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

其中:Ch為h 類備件存儲所需的容量，fh為h 類備件的出庫頻率。

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

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

式中:f1為備件所在層編號與質量mij之商。

2）為實現備件使用效率最大化，所有備件的COI 值就應與其所分配的備件區編號的乘積之和盡可能?。?～10］，即:

2.3 約束條件

1）在文獻［7］中，POTRC 對貨架寬度與高度之比對立體倉庫性能產生的影響進行了討論，這里作為備件存放架性能的參考，根據文中的計算結果，設寬度為L，高度為H，則理想比值為

2）備件在任意兩點（i1，j1）和（i2，j2）進行存放作業時，存放次序應該滿足由近及遠的原則，即:i1≤i2，j1≤j2。 而備件在任意兩點（i3，j3）和（i4，j4）進行取出操作時，則應滿足由遠及近的原則，即:

3）在存放備件時，要保證備件所存儲的位置為空，即:

對備件存儲分配的優化，需要同時滿足式（2）～（3）的要求。這兩個公式一般情況下是相互矛盾的，所以優化問題的求解就是一個多目標優化問題。加入約束條件（4）～（6）后，該問題就成為一個約束多目標優化問題。對于約束多目標優化問題的求解，一般可以采用如下數學模型進行描述［11］:

3 NSGA-II多目標優化算法介紹

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

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

NSGA-II 是NSGA 算法的改進版，其改進主要是針對以下三個方面:

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

2）引進精英策略，以確保在進化過程中某些優良的種群個體不會被丟棄，從而提高了優化結果的準確度；

3）采用擁擠度和擁擠度比較算子，不但克服了NSGA 中需要人為指定共享參數的缺陷，而且將其作為種群中個體間的比較標準，使得準Pareto 域中的個體能均勻地擴展到整個Pareto 域，保證了種群的多樣性［14～16］。

4 備件存儲分配優化模型計算及仿真

鑒于NSGA-II 的以上優點和在處理多目標約束優化問題上的成功應用，本文基于NSGA-Ⅱ算法對模型進行求解，并將結果與多目標粒子群算法（MPSO）對比說明?？疾炷硞浼揂 存放架為6排、10層，架寬為20cm，備件編號、數量、質量、使用頻率等信息情況如表1所示。

表1 備件信息統計表

本文針對該備件艙存儲分配優化模型應用NSGA-Ⅱ算法求解的總流程圖如圖1所示。

該求解過程的主要步驟有以下幾點［17］:

1）隨機產生種群大小為200的初始種群P0；

2）計算種群Pt目標函數值并進行非劣排序；

3）對種群Pt執行遺傳操作（模擬二進制交叉和多項式變異）得到子代種群Qt；

4）種群合并Rt=Pt∪Ut對Rt中的個體進行非劣排序、擁擠度距離計算；

5）運用錦標賽規則選擇并保留精英個體選取前N 個個體作為父代種群Pt+1；

6）循環執行程序并進行終止條件判斷，按照事先設置好最大遺傳代數判斷，若t＞400算法終止。

在試驗中，取種群最大規模為200，交叉概率pc=0.7，變異概率pm=0.1，最大允許進化代數Genmax=400，采用Matlab 平臺構造備件存儲分配優化模型并進行仿真［18～21］，可得目標函數f1和f2的迭代曲線如圖2和圖3所示。

圖1 模型求解總流程圖

圖2 目標函數f1 的迭代曲線

圖3 目標函數f2 的迭代曲線

5 結果分析

本文在對備件艙A 備件存儲分配優化過程中，求解模型時采用了NSGA-Ⅱ算法和MPSO 算法來進行效果比較，得到兩種算法的帕累托（Pareto）前沿如圖4所示。

圖4 帕累托前沿比較圖

從圖4 可以看出NSGA-Ⅱ算法的帕累托前沿點數多于MPSO 算法的點數，說明NSGA-Ⅱ算法的求解效果要優于MPSO 求解結果，證明該算法在求解備件存儲分配優化問題上具有優越性。

通過NSGA-Ⅱ算法求解對表1 中備件原存儲方法（如圖5所示）進行優化，可得到圖6所示結果。

圖5 優化前的擺放圖

圖6 優化后的擺放圖

圖中（0，0）點表示備件艙出口，可以看出經過優化后的備件存放位置滿足f1和f2目標函數最小化的要求，證明了NSGA-Ⅱ算法在求解備件存儲分配優化問題上具有可行性。

6 結語

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