基于NSGAⅡ的多目標電子產品CTO訂單推薦

韓海峰 葉恒舟 黃鳳怡 郝 薇

(桂林理工大學廣西嵌入式技術與智能系統重點實驗室 廣西 桂林 541006)

0 引 言

隨著客戶對產品需求的不斷提高,按訂單配置(CTO)成為滿足用戶需求不確定性和復雜性的關鍵。CTO模式雖然可為用戶在產品選擇方面提供多種選擇,但這要求企業要能夠利用產品結構之間的約束和配置規則等相關算法[1-5]實現產品設計、工藝準備、組織生產,以滿足用戶的特殊需求。

為快速有效地響應用戶訂單需求,文獻[6]在具有訂單配置不確定的CTO系統中,采用啟發式算法解決了在多個產品之間分配公共組件的問題。文獻[7]通過伸縮的靈活性來適應客戶需求的變化,使用按工程訂單的生產模式(Engineering To Order,ETO)采用適應性設計和產品平臺設計來解決,但ETO模式從產品設計、工藝準備、采購、制造都是按訂單操作,不可避免地增加了產品的生產周期和成本。在與CTO模式相似的按訂單裝配(Assemble To Order,ATO)模式下,文獻[8]考慮的是不確定需求和不確定裝配能力的ATO模式下的裝配決策問題。與本文類似,文獻[9]從CTO產品的經濟和環境性角度考慮,提出了一種基于多生命周期的多目標產品配置設計方法,并使用NSGAⅡ應用在碳粉盒結構設計的案例中證明該配置方法的有效性,但它僅僅從企業利益和社會利益考慮,忽略了CTO產品是為了滿足客戶自身需求。文獻[10]從用戶角度建立了電子產品CTO訂單推薦的單目標優化模型,并使用改進的遺傳算法求解該模型。

傳統的將多目標問題轉化為單目標優化問題存在著權值分配主觀性強[11]、目標函數復雜[12]、度量單位不一致和搜索效率低等問題。多目標優化算法具有較優的搜索效率和魯棒性,在諸多領域運用廣泛。文獻[13] 針對傳統優化算法的目標權重人為選擇以及常規NSGAⅡ的局部收斂等問題,提出將正態分布交叉(Normal Distribution Crossover,NDX)算子引入到NSGAⅡ中,借助NDX算子加強算法的全局搜索能力,優化出最佳的電網規劃方案。文獻[14]針對傳統動力學模型難以滿足精度和穩定性要求,提出一種采用神經網絡作為代理模型,建立以馬氏距離和魯棒性為不確定性量化指標的多目標優化模型,并使用NSGAⅡ多目標進化算法求解。文獻[15]圍繞柔性車間調度問題,針對NSGAⅡ收斂性不足的缺陷,引入免疫平衡原理改進NSGAⅡ的選擇策略和精英保留策略,成功避免了局部收斂問題,提高了算法的優化性能。文獻[16]在水管的經濟性的前提下兼顧可靠性指標優化水管網,同時解決最優解分布不均勻使得算法陷入局部最優問題。

綜上所述,雖然NSGAⅡ已經得到諸多應用,也已經提出了諸多改進方法,但在應用于具體某個優化模型時,仍有必要進行針對性的優化。本文圍繞電子產品CTO訂單,建立以功能定位目標貼近度、功耗和成本三項指標為目標優化模型,將NSGAⅡ應用到電子產品CTO訂單推薦多目標優化求解中去,通過用戶對Pareto非支配集的權重排序為用戶實現電子產品的CTO訂單推薦。

1 多目標電子產品CTO訂單推薦模型

電子產品CTO訂單推薦的目標是根據用戶的個性化需求,為其推薦產品的配置清單,即為生產該產品所需要的每個配件推薦合適的品牌與型號。用戶的個性化需求有些是局部的或者可以容易轉化為局部約束,如內存應大于等于4 GB、屏幕分辨率要不低于2 048×1 080、產品外觀為黑色等。這類需求可以通過淘汰特定的配件的可行品牌或型號滿足。因而,在構建CTO訂單推薦模型時,僅需考慮全局性的個性化需求,如功能定位目標貼近度、成本和功耗等。

設某電子產品的產品配置清單涉及m個配件,si為第i個配件的可選項個數(已經根據個性化需求的相關局部約束進行了篩選),mij(i=1,2,…,m;j=1,2,…,si)為第i個配件的第j個可選項,xij(i=1,2,…,m;j=1,2,…,si)為一個 0-1 決策變量,當為第i個配件選擇mij時,xij=1,否則,xij=0。

設t1,t2,…,tu等u個指標被用來描述產品的功能定位目標,用f(tk,mij)度量mij與tk的貼近度。記f(tk,0)=0,可用式(1)確定某個配置清單的功能定位目標貼近度μ,記為f1。

(1)

某個配置清單的成本由相應配件的成本及加工成本確定。記cij為mij的價格,c0為加工成本,則某個配置清單對應的成本C可由式(2)計算,記為f2。

(2)

記pij為mij的價格,則某個配置清單對應的功耗P可由式(3)計算,記為f3。

(3)

以最大化功能定位目標貼近度、最小化成本和能耗為優化目標,則多目標電子產品的CTO訂單推薦模型(Multi-target Electronic Products CTO Order Recommendation,MEPCTOR)可以描述如下:

目標函數:Maxf1;Minf2; Minf3。

約束條件:

(4)

xij∈{0,1}i=1,2,…,n,j=1,2,…,pi

(5)

式(4)和式(5)表明應為每種配件恰好選擇一個選項。

2 MEPCTOR模型求解

MEPCTOR模型是一種多目標優化模型,是NP難的。諸如非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm,NSGA)是求解這類模型的有效方法。本文采用基于NSGAⅡ[17-19]求解MEPCTOR模型,并采用分配權重的非支配集排序策略對求得的非支配最優解進行排序,該算法(CTOR_NSGAⅡ)主要步驟流程如圖1所示,主要包括:種群初始化、非支配排序、擁擠度計算、交叉變異和精英保留策略等。

圖1 基于NSGAⅡ的電子產品CTO訂單推薦流程

2.1 種群初始化

種群染色體采用實數編碼方式。一個染色體由十個基因組組成,共二十個實數編碼,每兩個編碼為一個基因組,基因組的編碼表示電子產品所選擇的對應配件,初始種群的染色體基因組編碼隨機產生。

2.2 非支配排序

對于每個染色體q設置一個集合sq和一個變量nq,sq為染色體q支配的個體集合,nq記錄染色體q被支配的個體數目。快速非支配排序步驟如下:

(1) 初始化種群,設置染色體q對應的sq={},nq=0。

(2) 遍歷種群P中的每個染色體q,比較f1、f2、f3函數,找出種群中nq=0的所有個體,并保存在當前集合F0中,記錄當前支配等級為0。

(3) 遍歷當前F0層的所有染色體,從其支配的染色體集合sq中選擇染色體執行nq=nq-1操作,若nq=0,則將個體保存在下一個F1中,記錄當前支配等級為1。

(4) 依次執行步驟(2)、步驟(3)操作,直至所有染色體完成分級。

2.3 擁擠度計算

擁擠度是表示種群中個體周圍的染色體的密集程度,每條染色體擁擠度是根據周圍染色體的距離決定,距離越大表明該染色體所處區域密度越小。因此計算擁擠度是保證種群多樣性的一個關鍵環節。染色體擁擠度的計算如下:

式中:fw(i)表示當前等級下的第i個染色體的第w個目標函數值;fwmax、fwmin分別為當前等級下的第w個目標函數的最大與最小值。當前等級的兩端的個體的id=∞。當染色體非支配等級相同的時候,擁擠度大的個體會有更大概率被選擇進入下一代,從而保證種群染色體集的多樣性。該計算方式可以消除不同量級函數的單位限制,提升染色體擁擠度的計算精度,保證種群多樣性的可靠性。

2.4 交叉變異

交叉與變異是種群產生新染色體的主要方式,也是種群進化的重要部分。種群的交叉變異主要采用多點交叉的方式:即從每個基因座編碼的起始點(上一個基因座的末尾)到下一個基因座的起始點。每個染色體的基因都有固定的交叉變異概率pc、pm。

以實數編碼為例,染色體A的基因編碼為[03 11 32 08 13 26],染色體B的編碼為[19 25 07 15 02 22],發生交叉互換的位置分別在基因座1、4和6上,那么交叉過后的新染色體A編碼為[19 11 32 15 13 22],新染色體B編碼為[03 25 07 08 02 26],如圖2所示。多點變異類似于多點交叉,若圖2中染色體A的基因座1、4、6發生變異,則新染色體A的編碼為[**11 32**13**],**為從相對應的基因座編碼空間中隨機選取的編碼。

圖2 染色體交叉

2.5 精英保留策略

種群Pn和經過遺傳操作得到的子種群Qn合并為2N個染色體的解空間。對該空間進行非支配排序,根據非支配等級從低到高依次向新種群Pn+1中添加非支配集,直至新種群Pn+1染色體數量大于等于N。若個體大于N,則從最大的等級中的個體進行擁擠度比較,依次添加個體直至新種群Pn+1個體為N;若個體等于N,則操作結束。

2.6 基于用戶權值的非支配集排序

由CTOR_NSGAⅡ得到的Pareto最優前沿點集記錄在新種群Pn中,它們的獲取與用戶偏好無關。接下來可以根據用戶的偏好對新種群Pn進行非支配排序,選擇非支配等級最低的非支配集。將非支配集中個體的f1、f2、f3目標函數值進行歸一化處理,歸一化標準按照式(7),根據用戶偏好設置目標函數權重,按大小依次排序,得到基于權重的非支配解排序,即為基于用戶的電子產品CTO訂單推薦。

Norw=α+(1-α)·Testw

(8)

式中:Testw是第w個目標函數的測試函數;Norw為當前第w個目標函數的歸一化函數;fwi為當前第w個目標函數的第i個函數值;fwmax、fwmin為當前第w個目標函數在當前數據庫中或當前電子產品市場的最大值和最小值;α為可調參數,該值是根據測試函數Testw的值所確定,可消除不同函數在歸一化后因數值差距過大而對用戶對權重的影響。

整個推薦過程可以分為兩大步驟:由CTOR_NSGAⅡ得到Pareto最優前沿點集;根據用戶偏好對Pareto最優前沿點集進行排序,擇優向用戶推薦。前者雖然耗時較多,但與用戶偏好無關;后者耗時較小,可以方便用戶隨時調整自己的偏好。

3 實驗及仿真數據分析

3.1 實驗環境及參數取值

為驗證CTOR_NSGAⅡ對MEPCTOR模型的求解的可行性,本文考慮桌面級PC機為對象,使用網絡爬蟲技術從公開的網絡平臺爬取涉及顯示器、CPU、GPU、主板、內存、硬盤、電源、鍵盤、鼠標和耳機等10個配件的共計約348條記錄,其中單個配件的記錄最小23條、最高52條。實驗主要在Intel (R) Core (TM)i7-9750H、2.6 GHz CPU、16 GB RAM、64 bit Windows 10操作系統的PC端進行,算法采用Python3.7編程。CTOR_NSGAⅡ在求解對MEPCTOR問題時具體參數設置如下:初始種群規模為N=20,染色體長度l=10,交叉概率pc=0.50,突變概率pm=0.20,指標權重wi=0.1(i=1,2,…,l),起始目標遺傳代數g=40,最大目標遺傳代數gmax=200,其中遺傳步長step=40。

3.2 仿真結果與分析

為了驗證基于MEPCTOR模型的CTOR_NSGAⅡ的有效性,仿真測試結果主要與簡單遺傳算法(Simple Genetic Algorithm,SGA)以及基于遺傳算法改進的ADM_GA[10]對比,該算法根據用戶需求將功能定位目標貼近度、電子產品功耗值、電子產品成本值分別賦予權值,該值的歸一化處理也按照式(8)計算。

在gmax=100的情況下,選取CTOR_NSGAⅡ所得的Pareto最優前沿點集,并對點集的目標函數f2和f3采用式(7)進行歸一化處理,得到Pareto最優前沿點集分布圖,如圖3所示。

圖3 CTOR_NSGAⅡPareto最優前沿面

為了驗證算法的可靠性,SGA仿真實驗在一次實驗中取多個最優解,CTOR_NSGAⅡ則在達到與SGA相同目標遺傳代數的情況下,取最低Pareto等級的前幾個非支配解進行分析。表1選取gmax=100的情況下,三種算法分別取5個基于用戶權值的電子產品CTO訂單推薦指數,并計算數學期望與標準差。從表1中不難看出,CTOR_NSGAⅡ在推薦指數上均優于SGA和ADM_GA,均值均優于SGA和ADM_GA,且算法所得推薦指數的標準差低于其他兩種算法。

表1 三種算法推薦指數結果對比表

圖4給出了三種算法各代電子產品CTO訂單推薦指數的數學期望,CTOR_NSGAⅡ的推薦指數期望值最高,CTOR_NSGAⅡ與ADM_GA推薦指數期望值隨遺傳代數呈緩慢增長趨勢,電子產品CTO訂單推薦的有效性也隨之增強,而SGA緩慢增長后呈逐漸平穩趨勢,電子產品CTO訂單推薦效果劣于ADM_GA與CTOR_NSGAⅡ。

圖4 三種算法的電子產品CTO訂單推薦指數均值

為了進一步驗證兩種算法的魯棒性,測得各代結果的標準差如圖5所示。CTOR_NSGAⅡ和ADM_GA相對于SGA標準差更低,魯棒性相對較強,推薦指數更具平穩性。

圖5 三種算法的電子產品CTO訂單推薦指數標準差

4 結 語

電子產品CTO訂單是按照其產品BOM中的多個模塊組件組裝而成,因此電子產品的綜合指標受組裝BOM影響較大。本文針對電子產品CTO訂單推薦問題,建立了以功能定位目標貼近度、電子產品功耗和成本值為多目標優化模型,采用CTOR_NSGAⅡ求解該模型,并基于用戶權值排序的方式供用戶選擇。實驗證明,該算法較基于權重的SGA和ADM_GA具有較強的魯棒性和靈活性。