詹鈞凱，石宇強，陳柏志，蔡躍坤

（西南科技大學制造科學與工程學院，四川 綿陽 621010）

1 引言

隨著全球化市場競爭的加劇和顧客需求的多樣化，賣方市場轉變?yōu)橘I方市場，快速響應并提供滿足顧客個性化需求的高性能、低成本、短交貨期的產品配置方案逐漸成為企業(yè)的戰(zhàn)略選擇，產品配置是實施大規(guī)模定制的核心環(huán)節(jié)，其實現依賴于靈活的配置模型和高效的求解方法[1]。

配置模型方面：文獻[2]在模塊和目標約束下以性能、成本、交貨期為目標建立配置模型。文獻[3]考慮互斥和依耐性約束以響應時間、成本和質量為目標構建配置模型。上述研究缺乏對顧客個性化需求約束的考慮；配置模型求解方面：文獻[4]采用改進的線性加權和算法求解多目標配置模型。文獻[5]采用線性加權方法將多目標轉化為單目標，并應用遺傳算法求解配置模型。文獻[6]采用改進的蟻群算法進行配置求解。文獻[7]應用NSGA-Ⅱ算法對成本、響應時間和綜合服務性能進行配置優(yōu)化。上述研究存在算法有效性不佳的問題。

針對以上研究存在的不足，在考慮顧客個性化需求等約束，建立以性能、成本和交貨期為目標的產品配置模型，設計了一種改進的NSGA-Ⅱ算法求解配置模型，并根據顧客偏好推薦配置方案。

2 多目標產品配置模型

2.1 問題描述

針對模塊化產品族S，產品配置過程為：根據顧客需求從必選配置模塊的每個配置單元中選取1 個零部件，從可選配置模塊的每個配置單元中至多選取1 個零部件，最終構成一個產品性能最大化，成本和交貨期最小化，且滿足一定約束的產品。

設Ohlk為第h 配置模塊（h=1 為必選配置模塊，h=2 為可選配置模塊）的第l（l=1，2，L，Mh）個配置單元的第k（k=1，2，L，Dhl）個零部件實例。決策變量xhlk如下：

2.2 目標函數

最大化產品性能：

式中：whlk—零部件實例Ohlk與客戶需求的性能相關度。

最小化產品成本[8]：

式中：Chlk—零部件實例Ohlk的采購成本；Ca—零部件間的平均裝配成本系數；CF—固定成本。

最小化交貨期：

式中：Thlk—零部件實例Ohlk的制造工期；Ta—零部件間的平均裝配工時系數；Tr—物流運輸時間。

2.3 約束條件

式中：a—企業(yè)利潤率；Cmax—成本上限。

式中：Tmax—交貨期時間上限。

基本約束，即從必選配置模塊的每個配置單元中只選取1個零部件，從可選配置模塊的每個配置單元中至多選取1 個零部件。

關系約束，包含相容和互斥2 種情況，相容的零部件在產品中必須同時存在，互斥則不能同時存在。

個性化約束，即顧客指定產品中必須有或不能有的零部件。

3 改進的NSGA-Ⅱ算法設計

3.1 編碼設計

采用十進制編碼法。每一個體表示一個產品配置方案，個體編碼如下：Code=V11kV12kLV1M1kV21kV22kLV2M2k

基因Vhlk表示第h（h=1 為必選配置模塊，h=2 為可選配置模塊）配置模塊的第l（l=1，2，L，Mh）個配置單元的第k 個零部件實例。每個基因Vhlk表示一個配置單元，基因占位長度由該配置單元所含零部件數決定，基因值為k，當配置單元沒有零部件被選中時，用0 占位。

3.2 適應度函數

將最大化產品性能指標F 乘以-1 轉化為求最小值指標，產品性能、成本和交貨期適應度函數如下：

對違反約束的配置方案采用動態(tài)罰函數β 進行調整。算法迭代前期采用較小罰函數避免破壞種群多樣性，迭代后期采用較大罰函數快速淘汰不滿足約束個體使算法快速收斂，設計動態(tài)罰函數β 如下：

式中：g、gmax—當前和最大迭代次數；φ—懲罰因子，取φ=5。

若違反產品性能約束，則按式（14）調整。若違反成本約束，則按式（15）調整；若違反交貨期約束，則按式（16）調整。

3.3 選擇操作

首先對初始化的種群進行非支配排序和擁擠距離計算，然后采用二元錦標賽方法進行選擇。

選擇步驟如下：

（1）從父種群中隨機選擇2 個個體；

（2）判斷兩個個體的支配關系，將非支配個體添加到子種群，若兩個個體互不支配，則跳到（3）；

（3）判斷兩個個體的擁擠距離，將擁擠距離大的個體添加到子種群，若擁擠距離相同，則隨機選擇一個個體添加到子種群；

（4）返回（1），并循環(huán)，直到子種群規(guī)模達到父種群規(guī)模一半，則算法終止。

3.4 交叉操作

算法迭代前期，應保持較大的交叉概率來擴大尋優(yōu)范圍，迭代后期為避免破壞較優(yōu)個體應用較小交叉概率[9]，自適應交叉概率Pc如下：

式中：Pcmax、Pcmax—最大和最小交叉概率，取 Pcmax=0.9，Pcmin=0.6；g、gmax—當前和最大迭代次數。

式中：a、b—［0，1］區(qū)間上均勻分布的隨機數。

3.5 變異操作

采用自適應交叉概率相似原理，設計自適應變異概率Pm。

式中：Pmmax、Pmmin—最大和最小變異概率，取 Pmmax=0.1，Pmmin=0.01；g、gmax—當前和最大迭代次數。

將交叉操作后的個體進行多項式變異得到新的個體。

3.6 模擬退火操作

采用改進的Metropolis 準則判斷是否接受變異操作后的個體。由于Metropolis 準則無法對多目標問題的新解進行接受判斷，因此需要對Metropolis 準則進行改進[10]。

設變異操作前后個體分別為vold、vnew，對應的第m 個目標的函數值分別為fm（vold）、fm（vnew），接受vnew的概率P 為：

式中：T0—初始溫度，取 T0=100；T0—冷卻系數，取 a=0.9；k—降溫次數，即為迭代次數。

改進后的 Metropolis 準則說明：若 fm（vnew）＜fm（vold），則接受vnew；若 vnew和 vold互不支配，則同時接受 vnew和 vold；當 fm（φnew）＞fm（φold）時，若則接受 vnew，若＜rand 則不接受 vnew。

3.7 算法步驟

（1）參數設置，包括種群大小N，最大遺傳代數gmax，初始溫度 T0，冷卻系數 a 等，初始化種群 P0，g=1；

（2）計算種群Pg的適應度函數值，對違反約束個體進行動態(tài)罰函數調整，并進行非支配排序和擁擠距離計算；

（3）通過二元錦標賽方法從種群中選擇N/2 個個體，進行算術交叉和多項式變異操作，并按改進的Metropolis 準則接受新個體，得到子代種群；

（4）將父代Pg和子代種群合并，得到臨時種群Rg，對臨時種群Rg進行非支配排序和擁擠距離計算，采用精英保留策略選出N 個個體，得到新一代種群Pg+1；

（5）判斷是否 g=gmax，否則返回（2），并 g=g+1，T=agT0；是則算法終止，輸出滿足約束的結果。

改進的NSGA-Ⅱ算法流程，如圖1 所示。

圖1 改進的NSGA-Ⅱ算法流程Fig.1 Improved NSGA-ⅡAlgorithm Flow

4 產品配置方案推薦

根據顧客偏好對各產品配置目標賦予權重wi（i=1，2，3），并采用綜合線性加權法計算第y 種產品配置方案的綜合指標fy，將fmax對應的產品配置方案推薦跟顧客。

式中：Fy、Cy、Ty—第y 種產品配置方案對應的產品性能、成本和交貨期目標函數值。

5 算法驗證與實例應用

5.1 算法驗證

采用文獻[8]中的實驗數據，以NSGA-Ⅱ算法為比較算法，設定交叉概率為0.9，變異概率為0.1，種群大小為100，最大迭代代數為100，最大交貨期為75 天，最大成本為6000 元，企業(yè)利潤率為0.15；仿真環(huán)境為Intel（R）Core（TM）i5-3210M，CPU@2.50GHz，RAM 6GB，系統(tǒng)Windows 10；仿真平臺Matlab2015a。仿真結果，如表1 所示。各個目標函數變化曲線，如圖2～圖4 所示。

表1 仿真結果對比Tab.1 Comparison of Simulation Results

由表1 可知：改進的NSGA-Ⅱ算法比NSGA-Ⅱ算法求解問題平均耗時少，算法求解效率更高，且得到的平均非支配解個數更多，求解結果更好，算法對比優(yōu)勢明顯。

圖2 產品性能目標函數變化曲線Fig.2 Product Performance Objective Function Variation Curve

圖3 產品成本目標函數變化曲線Fig.3 Product Cost Objective Function Variation Curve

圖4 產品交貨期目標函數變化曲線Fig.4 Product Due Date Objective Function Change Curve

從圖2～圖4 可知，改進的NSGA-Ⅱ算法的各目標函數變化曲線收斂速度明顯快于NSGA-Ⅱ算法，并且曲線的末端值更小，得到的解的質量更好。因此，改進的NSGA-Ⅱ算法在配置問題求解上優(yōu)于NSGA-Ⅱ算法。

5.2 實例應用

某模塊化產品族S，擁有4個必選配置單元和2 個可選配置單元，其零部件實例特征屬性值，如表2 所示。顧客需求：產品性能至少600，最長交貨期20 天，最高成本8000 元企業(yè)數據：裝配成本系數50，裝配工期系數0.5，企業(yè)利潤率0.15，物流運輸時間2 天；設置改進的NSGA-Ⅱ算法參數：種群大小100，最大迭代代數100。產品配置模型求解結果，如圖5 所示。

表2 零部件實例特征屬性值表Tab.2 Component Example Feature Attribute Value Table

圖5 產品配置模型Pareto 最優(yōu)解集Fig.5 Pareto Optimal Solution Set of Product Configuration Model

仿真運行10 次，將求解結果合并去重，共得到78 個符合顧客需求的配置方案。

根據顧客偏好設定產品性能、成本和交貨期目標權重，由式（21）計算得到推薦方案，如表3 所示。

表3 產品配置推薦方案Tab.3 Product Configuration Recommendation Scheme

6 結語

針對多目標產品配置優(yōu)化問題，考慮個性化等約束，以產品性能最大化、成本和交貨期最小化為目標建立產品配置模型，使得配置模型能夠滿足顧客的個性化需求；設計了一種改進的NSGA-Ⅱ算法求解配置模型，該算法采用自適應交叉和變異概率提高算法收斂速度，對變異操作結果進行模擬退火操作，避免了算法陷入局部最優(yōu)解；根據顧客偏好推薦配置方案，避免顧客因配置方案過多導致的選擇困難。

通過與NSGA-Ⅱ算法對比，證明改進NSGA-Ⅱ算法在配置問題求解上性能更優(yōu)，具有一定理論意義；通過實例應用，證明本模型有效可行，具有一定的推廣應用價值。