多目標(biāo)產(chǎn)品配置優(yōu)化研究

詹鈞凱，石宇強(qiáng)，陳柏志，蔡躍坤

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

1 引言

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

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

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

2 多目標(biāo)產(chǎn)品配置模型

2.1 問題描述

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

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

2.2 目標(biāo)函數(shù)

最大化產(chǎn)品性能：

式中：whlk—零部件實(shí)例Ohlk與客戶需求的性能相關(guān)度。

最小化產(chǎn)品成本[8]：

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

最小化交貨期：

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

2.3 約束條件

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

式中：Tmax—交貨期時(shí)間上限。

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

關(guān)系約束，包含相容和互斥2 種情況，相容的零部件在產(chǎn)品中必須同時(shí)存在，互斥則不能同時(shí)存在。

個(gè)性化約束，即顧客指定產(chǎn)品中必須有或不能有的零部件。

3 改進(jìn)的NSGA-Ⅱ算法設(shè)計(jì)

3.1 編碼設(shè)計(jì)

采用十進(jìn)制編碼法。每一個(gè)體表示一個(gè)產(chǎn)品配置方案，個(gè)體編碼如下：Code=V11kV12kLV1M1kV21kV22kLV2M2k

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

3.2 適應(yīng)度函數(shù)

將最大化產(chǎn)品性能指標(biāo)F 乘以-1 轉(zhuǎn)化為求最小值指標(biāo)，產(chǎn)品性能、成本和交貨期適應(yīng)度函數(shù)如下：

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

式中：g、gmax—當(dāng)前和最大迭代次數(shù)；φ—懲罰因子，取φ=5。

若違反產(chǎn)品性能約束，則按式（14）調(diào)整。若違反成本約束，則按式（15）調(diào)整；若違反交貨期約束，則按式（16）調(diào)整。

3.3 選擇操作

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

選擇步驟如下：

（1）從父種群中隨機(jī)選擇2 個(gè)個(gè)體；

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

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

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

3.4 交叉操作

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

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

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

3.5 變異操作

采用自適應(yīng)交叉概率相似原理，設(shè)計(jì)自適應(yīng)變異概率Pm。

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

將交叉操作后的個(gè)體進(jìn)行多項(xiàng)式變異得到新的個(gè)體。

3.6 模擬退火操作

采用改進(jìn)的Metropolis 準(zhǔn)則判斷是否接受變異操作后的個(gè)體。由于Metropolis 準(zhǔn)則無法對多目標(biāo)問題的新解進(jìn)行接受判斷，因此需要對Metropolis 準(zhǔn)則進(jìn)行改進(jìn)[10]。

設(shè)變異操作前后個(gè)體分別為vold、vnew，對應(yīng)的第m 個(gè)目標(biāo)的函數(shù)值分別為fm（vold）、fm（vnew），接受vnew的概率P 為：

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

改進(jìn)后的 Metropolis 準(zhǔn)則說明：若 fm（vnew）＜fm（vold），則接受vnew；若 vnew和 vold互不支配，則同時(shí)接受 vnew和 vold；當(dāng) fm（φnew）＞fm（φold）時(shí)，若則接受 vnew，若＜rand 則不接受 vnew。

3.7 算法步驟

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

（2）計(jì)算種群Pg的適應(yīng)度函數(shù)值，對違反約束個(gè)體進(jìn)行動(dòng)態(tài)罰函數(shù)調(diào)整，并進(jìn)行非支配排序和擁擠距離計(jì)算；

（3）通過二元錦標(biāo)賽方法從種群中選擇N/2 個(gè)個(gè)體，進(jìn)行算術(shù)交叉和多項(xiàng)式變異操作，并按改進(jìn)的Metropolis 準(zhǔn)則接受新個(gè)體，得到子代種群；

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

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

改進(jìn)的NSGA-Ⅱ算法流程，如圖1 所示。

圖1 改進(jìn)的NSGA-Ⅱ算法流程Fig.1 Improved NSGA-ⅡAlgorithm Flow

4 產(chǎn)品配置方案推薦

根據(jù)顧客偏好對各產(chǎn)品配置目標(biāo)賦予權(quán)重wi（i=1，2，3），并采用綜合線性加權(quán)法計(jì)算第y 種產(chǎn)品配置方案的綜合指標(biāo)fy，將fmax對應(yīng)的產(chǎn)品配置方案推薦跟顧客。

式中：Fy、Cy、Ty—第y 種產(chǎn)品配置方案對應(yīng)的產(chǎn)品性能、成本和交貨期目標(biāo)函數(shù)值。

5 算法驗(yàn)證與實(shí)例應(yīng)用

5.1 算法驗(yàn)證

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

表1 仿真結(jié)果對比Tab.1 Comparison of Simulation Results

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

圖2 產(chǎn)品性能目標(biāo)函數(shù)變化曲線Fig.2 Product Performance Objective Function Variation Curve

圖3 產(chǎn)品成本目標(biāo)函數(shù)變化曲線Fig.3 Product Cost Objective Function Variation Curve

圖4 產(chǎn)品交貨期目標(biāo)函數(shù)變化曲線Fig.4 Product Due Date Objective Function Change Curve

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

5.2 實(shí)例應(yīng)用

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

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

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

仿真運(yùn)行10 次，將求解結(jié)果合并去重，共得到78 個(gè)符合顧客需求的配置方案。

根據(jù)顧客偏好設(shè)定產(chǎn)品性能、成本和交貨期目標(biāo)權(quán)重，由式（21）計(jì)算得到推薦方案，如表3 所示。

表3 產(chǎn)品配置推薦方案Tab.3 Product Configuration Recommendation Scheme

6 結(jié)語

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

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