基于NSGAⅡ的多目標(biāo)電子產(chǎn)品CTO訂單推薦

韓海峰 葉恒舟 黃鳳怡 郝 薇

(桂林理工大學(xué)廣西嵌入式技術(shù)與智能系統(tǒng)重點實驗室 廣西 桂林 541006)

0 引 言

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

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

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

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

1 多目標(biāo)電子產(chǎn)品CTO訂單推薦模型

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

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

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

(1)

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

(2)

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

(3)

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

目標(biāo)函數(shù):Maxf1;Minf2; Minf3。

約束條件:

(4)

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

(5)

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

2 MEPCTOR模型求解

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

圖1 基于NSGAⅡ的電子產(chǎn)品CTO訂單推薦流程

2.1 種群初始化

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

2.2 非支配排序

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

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

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

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

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

2.3 擁擠度計算

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

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

2.4 交叉變異

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

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

圖2 染色體交叉

2.5 精英保留策略

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

2.6 基于用戶權(quán)值的非支配集排序

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

Norw=α+(1-α)·Testw

(8)

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

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

3 實驗及仿真數(shù)據(jù)分析

3.1 實驗環(huán)境及參數(shù)取值

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

3.2 仿真結(jié)果與分析

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

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

圖3 CTOR_NSGAⅡPareto最優(yōu)前沿面

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

表1 三種算法推薦指數(shù)結(jié)果對比表

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

圖4 三種算法的電子產(chǎn)品CTO訂單推薦指數(shù)均值

為了進(jìn)一步驗證兩種算法的魯棒性,測得各代結(jié)果的標(biāo)準(zhǔn)差如圖5所示。CTOR_NSGAⅡ和ADM_GA相對于SGA標(biāo)準(zhǔn)差更低,魯棒性相對較強(qiáng),推薦指數(shù)更具平穩(wěn)性。

圖5 三種算法的電子產(chǎn)品CTO訂單推薦指數(shù)標(biāo)準(zhǔn)差

4 結(jié) 語

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