韓海峰 葉恒舟 黃鳳怡 郝 薇

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

0 引 言

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

為快速有效地響應(yīng)用戶訂單需求,文獻(xiàn)[6]在具有訂單配置不確定的CTO系統(tǒng)中,采用啟發(fā)式算法解決了在多個(gè)產(chǎn)品之間分配公共組件的問題。文獻(xiàn)[7]通過伸縮的靈活性來適應(yīng)客戶需求的變化,使用按工程訂單的生產(chǎn)模式(Engineering To Order,ETO)采用適應(yīng)性設(shè)計(jì)和產(chǎn)品平臺(tái)設(shè)計(jì)來解決,但ETO模式從產(chǎn)品設(shè)計(jì)、工藝準(zhǔn)備、采購(gòu)、制造都是按訂單操作,不可避免地增加了產(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è)計(jì)方法,并使用NSGAⅡ應(yīng)用在碳粉盒結(jié)構(gòu)設(shè)計(jì)的案例中證明該配置方法的有效性,但它僅僅從企業(yè)利益和社會(huì)利益考慮,忽略了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)域運(yùn)用廣泛。文獻(xiàn)[13] 針對(duì)傳統(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]針對(duì)傳統(tǒng)動(dò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)度問題,針對(duì)NSGAⅡ收斂性不足的缺陷,引入免疫平衡原理改進(jìn)NSGAⅡ的選擇策略和精英保留策略,成功避免了局部收斂問題,提高了算法的優(yōu)化性能。文獻(xiàn)[16]在水管的經(jīng)濟(jì)性的前提下兼顧可靠性指標(biāo)優(yōu)化水管網(wǎng),同時(shí)解決最優(yōu)解分布不均勻使得算法陷入局部最優(yōu)問題。

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

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

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

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

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

(1)

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

(2)

記pij為mij的價(jià)格,則某個(gè)配置清單對(duì)應(yīng)的功耗P可由式(3)計(jì)算,記為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)為每種配件恰好選擇一個(gè)選項(xiàng)。

2 MEPCTOR模型求解

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

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

2.1 種群初始化

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

2.2 非支配排序

對(duì)于每個(gè)染色體q設(shè)置一個(gè)集合sq和一個(gè)變量nq,sq為染色體q支配的個(gè)體集合,nq記錄染色體q被支配的個(gè)體數(shù)目?？焖俜侵渑判虿襟E如下:

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

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

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

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

2.3 擁擠度計(jì)算

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

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

2.4 交叉變異

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

以實(shí)數(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所示。多點(diǎn)變異類似于多點(diǎn)交叉,若圖2中染色體A的基因座1、4、6發(fā)生變異,則新染色體A的編碼為[**11 32**13**],**為從相對(duì)應(yīng)的基因座編碼空間中隨機(jī)選取的編碼。

圖2 染色體交叉

2.5 精英保留策略

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

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

由CTOR_NSGAⅡ得到的Pareto最優(yōu)前沿點(diǎn)集記錄在新種群Pn中,它們的獲取與用戶偏好無關(guān)。接下來可以根據(jù)用戶的偏好對(duì)新種群Pn進(jìn)行非支配排序,選擇非支配等級(jí)最低的非支配集。將非支配集中個(gè)體的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個(gè)目標(biāo)函數(shù)的測(cè)試函數(shù);Norw為當(dāng)前第w個(gè)目標(biāo)函數(shù)的歸一化函數(shù);fwi為當(dāng)前第w個(gè)目標(biāo)函數(shù)的第i個(gè)函數(shù)值;fwmax、fwmin為當(dāng)前第w個(gè)目標(biāo)函數(shù)在當(dāng)前數(shù)據(jù)庫中或當(dāng)前電子產(chǎn)品市場(chǎng)的最大值和最小值;α為可調(diào)參數(shù),該值是根據(jù)測(cè)試函數(shù)Testw的值所確定,可消除不同函數(shù)在歸一化后因數(shù)值差距過大而對(duì)用戶對(duì)權(quán)重的影響。

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

3 實(shí)驗(yàn)及仿真數(shù)據(jù)分析

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

為驗(yàn)證CTOR_NSGAⅡ?qū)EPCTOR模型的求解的可行性,本文考慮桌面級(jí)PC機(jī)為對(duì)象,使用網(wǎng)絡(luò)爬蟲技術(shù)從公開的網(wǎng)絡(luò)平臺(tái)爬取涉及顯示器、CPU、GPU、主板、內(nèi)存、硬盤、電源、鍵盤、鼠標(biāo)和耳機(jī)等10個(gè)配件的共計(jì)約348條記錄,其中單個(gè)配件的記錄最小23條、最高52條。實(shí)驗(yàn)主要在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Ⅱ在求解對(duì)MEPCTOR問題時(shí)具體參數(shù)設(shè)置如下:初始種群規(guī)模為N=20,染色體長(zhǎng)度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,其中遺傳步長(zhǎng)step=40。

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

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

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

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

為了驗(yàn)證算法的可靠性,SGA仿真實(shí)驗(yàn)在一次實(shí)驗(yàn)中取多個(gè)最優(yōu)解,CTOR_NSGAⅡ則在達(dá)到與SGA相同目標(biāo)遺傳代數(shù)的情況下,取最低Pareto等級(jí)的前幾個(gè)非支配解進(jìn)行分析。表1選取gmax=100的情況下,三種算法分別取5個(gè)基于用戶權(quán)值的電子產(chǎn)品CTO訂單推薦指數(shù),并計(jì)算數(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é)果對(duì)比表

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

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

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

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

4 結(jié) 語

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