基于改進(jìn)遺傳算法的電子產(chǎn)品CTO訂單推薦

韓海峰,葉恒舟,張 路

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

0 引 言

按訂單配置(configure to order，CTO)起源于用戶需求與偏好, 目標(biāo)是快速、有效地滿足用戶的個(gè)性化需求,提升企業(yè)的核心競(jìng)爭(zhēng)力。產(chǎn)品配置是實(shí)現(xiàn)CTO的關(guān)鍵,配置過程開展的前提是準(zhǔn)確地獲取客戶需求。由于定制產(chǎn)品的復(fù)雜性不斷提高,加上客戶對(duì)產(chǎn)品結(jié)構(gòu)、性能等認(rèn)識(shí)不充分,往往僅能提出與自身體驗(yàn)和偏好相關(guān)的需求,因此具有模糊性和不確定性[1]。特別是對(duì)于電子產(chǎn)品,其物料清單(bill of material, BOM)往往包含數(shù)十項(xiàng)核心配件,每個(gè)配件有諸多品牌與型號(hào)可供選擇,且產(chǎn)品更新較快,若采用過程式產(chǎn)品配置,需要用戶對(duì)這些配置非常熟悉。在BOM選擇過程中,難以滿足全局性需求,也易忽略企業(yè)庫存等影響因素。因此,有必要根據(jù)用戶提出的局部和全局約束以及功能性需求,為客戶推薦產(chǎn)品配置清單,幫助用戶明確滿足自身需求同時(shí)兼顧企業(yè)利益的CTO訂單。

在需求獲取方面,但斌等研究了一種需求智能獲取方法,該方法關(guān)注用戶表達(dá)需求的異質(zhì)性,提供與用戶的個(gè)人特征和使用情景相適應(yīng)的需求表達(dá)方式,從而幫助用戶提高需求描述的客觀性和準(zhǔn)確性[2]。Carulli等通過建立產(chǎn)品虛擬樣機(jī)和虛擬現(xiàn)實(shí)環(huán)境,在早期幫助客戶直觀感知產(chǎn)品,以輔助用戶與專業(yè)設(shè)計(jì)人員溝通[3]。

以客戶需求與企業(yè)資源為驅(qū)動(dòng),研究產(chǎn)品配置模型及求解算法是一個(gè)研究熱點(diǎn)。傳統(tǒng)CTO產(chǎn)品平臺(tái)僅能滿足已知的客戶需求,文獻(xiàn)[4]提出面向訂單設(shè)計(jì)(engineering-to-order, ETO)的配置方法,在維持個(gè)性化需求的同時(shí)增強(qiáng)了設(shè)計(jì)重用性,提升了產(chǎn)品配置的適應(yīng)能力；文獻(xiàn)[5]在CTO和ETO模型的基礎(chǔ)上,基于適應(yīng)性開放體系結(jié)構(gòu)產(chǎn)品平臺(tái),以個(gè)性化自行車配置過程為例,提出了一種個(gè)性化分布式產(chǎn)品配置過程；文獻(xiàn)[6]基于ETO,從產(chǎn)品系列、產(chǎn)品部件、產(chǎn)品細(xì)節(jié)3個(gè)層面關(guān)注產(chǎn)品配置的價(jià)格與利潤關(guān)聯(lián)；文獻(xiàn)[7]考慮了訂單的緊急程度,以綜合收益最大化為目標(biāo),將產(chǎn)品配置方案建模為一個(gè)多目標(biāo)優(yōu)化問題,并采用蟻群優(yōu)化算法求解,該方法認(rèn)為訂單已經(jīng)存在, 關(guān)注的是大規(guī)模個(gè)性化訂單的整體調(diào)度問題;文獻(xiàn)[8]探討了多情境及需求的不確定性情況下大規(guī)模定制訂單的優(yōu)化配置問題。考慮到為用戶定制一些復(fù)雜產(chǎn)品繁瑣費(fèi)時(shí)，文獻(xiàn)[9]在產(chǎn)品配置過程中,采用基于基尼指數(shù)的問答導(dǎo)航屬性選擇策略,幫助設(shè)計(jì)人員更好地獲取用戶需求與偏好；文獻(xiàn)[10]討論了云制造環(huán)境下個(gè)性化產(chǎn)品配置,重點(diǎn)是基于關(guān)聯(lián)規(guī)則挖掘的產(chǎn)品初步配置以及基于蟻群算法的產(chǎn)品完整配置；文獻(xiàn)[11]在產(chǎn)品配置時(shí)重點(diǎn)關(guān)注了用戶的感性需求；文獻(xiàn)[12]也根據(jù)用戶需求為用戶推薦產(chǎn)品配置結(jié)果,將其應(yīng)用到多功能液壓千斤頂?shù)呐渲迷O(shè)計(jì),但它強(qiáng)調(diào)的是規(guī)則匹配,而所采用的交互式遺傳算法需要用戶來評(píng)價(jià)種群個(gè)體適應(yīng)度,交互過程復(fù)雜冗長。

綜上可知,現(xiàn)有關(guān)于CTO產(chǎn)品配置的研究大多是考慮如何在用戶個(gè)性化需求及生產(chǎn)成本的基礎(chǔ)上,將大量的CTO訂單進(jìn)行整合獲取BOM,而忽略了CTO訂單本身如何根據(jù)用戶的個(gè)性化需求而明確化。針對(duì)這一問題,本文根據(jù)用戶的個(gè)性化需求描述,通過一種半交互過程幫助用戶高效確定CTO訂單,其核心是構(gòu)建一個(gè)針對(duì)電子產(chǎn)品的CTO訂單推薦(CTO order recommendation, CTOR)模型, 并采用一種支持自適應(yīng)多樣性維護(hù)特性的改進(jìn)遺傳算法(adaptive diversity maintenance of genetic algorithms, ADM-GA)求解該模型。

1 電子產(chǎn)品CTOR模型

設(shè)某電子產(chǎn)品的BOM包含n個(gè)配件,每個(gè)配件有若干個(gè)品牌,每個(gè)品牌有若干個(gè)型號(hào)可供選擇。CTO訂單推薦就是要為每個(gè)配件選擇某個(gè)品牌下的某個(gè)型號(hào),以滿足用戶的個(gè)性化需求,并兼顧企業(yè)庫存等信息。

用戶的個(gè)性化需求可以歸結(jié)為3類:1)功能定位性需求,如定位為商務(wù)型; 2)針對(duì)配件或可分解為針對(duì)配件的局部需求, 如內(nèi)存不小于4 G、 CPU是Intel、 配色為銀白等; 3)針對(duì)全部或多個(gè)配件的全局約束,如對(duì)價(jià)格、 功耗、 重量等的要求。 由于第2類的局部需求只需要對(duì)各個(gè)配件的候選集作篩選, 而企業(yè)庫存則可以通過調(diào)整配件價(jià)格來體現(xiàn)(如對(duì)于庫存中沒有的配件適當(dāng)提高價(jià)格),因此,要滿足用戶的個(gè)性化需求,可以考慮以功能定位目標(biāo)貼近度為優(yōu)化目標(biāo),價(jià)格及功耗等為約束條件構(gòu)建配件清單推薦模型,并通過求解該模型為用戶推薦滿足其個(gè)性化需求的訂單。

1.1 功能定位目標(biāo)貼近度

假設(shè)描述某種功能定位涉及r1,r2, …,ru等u個(gè)指標(biāo), 指標(biāo)ri(i=1, 2, …,u)的既定目標(biāo)屬于{ai, …,bi}。 設(shè)指標(biāo)ri的可選集CSi={vi1，vi2, …,vid}, 即該指標(biāo)可以有d個(gè)不同的選擇值(或區(qū)間), 而用戶為該指標(biāo)選擇值(或區(qū)間)為vi, 記集合SSi={v|v∈CSi∧((vi≤v∧v

(1)

其中, |SSi|、 |CSi|分別表示集合SSi、CSi中元素的個(gè)數(shù)。

例如, 設(shè)商務(wù)手機(jī)的標(biāo)準(zhǔn)GPU型號(hào)定位在集合{530, 540}中, 而GPU型號(hào)可選集為{430, 530, 540, 630, 640}。 若用戶選擇的型號(hào)為430, 則SS集為{430}, GPU功能定位目標(biāo)貼近度為1-1/5=0.8; 若用戶選擇為530, 則SS集為空, GPU功能定位目標(biāo)貼近度為1; 若用戶選擇640, 則SS集為{630, 640}, GPU功能定位目標(biāo)貼近度為1-2/5=0.6。

總體的功能定位目標(biāo)貼近度μ為

(2)

1.2 CTOR模型

設(shè)某電子產(chǎn)品的選配清單涉及n個(gè)配件, 第i個(gè)配件有pi種選擇(每種選擇對(duì)應(yīng)某個(gè)品牌下的某個(gè)型號(hào)),xij(i=1, 2, …,n;j=1, 2, …,pi)為0-1變量,xij=1表示第i個(gè)配件作出第j種選擇, 則可以將該電子產(chǎn)品的CTOR模型構(gòu)建為如下的多維多選擇背包問題(multidimensional multiple-choice knapsack problem, MMKP)[13]:

目標(biāo):maxμ

約束條件:

(3)

(4)

vr=fr(xij),r=r1,r2,…,ru;

(5)

(6)

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

(7)

其中, 式(3)描述價(jià)格約束,prij為第i個(gè)配件的第j種選擇的價(jià)格,pr0為加工等成本, 認(rèn)為是一個(gè)常數(shù), [prcl,prcu]為用戶約定的產(chǎn)品價(jià)格區(qū)間; 式(4)描述功耗約束,pcij為第i個(gè)配件的第j種選擇的配件功耗(有些配件的功耗很小, 可以忽略不計(jì), 即取值為0),pcc為用戶約定的產(chǎn)品功耗上限; 式(5)描述根據(jù)用戶的選擇計(jì)算功能定位中某種指標(biāo)值的方法。

2 改進(jìn)遺傳算法求解CTOR模型

CTOR模型是一個(gè)MMKP問題,諸如蟻群算法[14]、粒子群優(yōu)化算法[15]等進(jìn)化算法可以有效求解這類問題。其中遺傳算法[16-17]具有分布式的全局搜索能力,對(duì)于多維組合優(yōu)化問題具有良好的應(yīng)用前景，不足在于收斂速度較慢以及存在局部收斂問題,通過調(diào)整遺傳算子、構(gòu)建多樣性維護(hù)策略可以改善上述問題。

2.1 簡(jiǎn)單遺傳算法

簡(jiǎn)單遺傳算法(simple genetic algorithm, SGA)主要涉及編碼、 設(shè)定初始種群、 適應(yīng)度函數(shù)、 種群遺傳操作(選擇、 交叉、 變異)等核心要素。 種群個(gè)體采用實(shí)數(shù)編碼方式。 染色體中的每個(gè)基因位對(duì)應(yīng)一種配件, 基因的編碼值代表該配件的選項(xiàng)序號(hào)(按照價(jià)格參數(shù)排序)。 種群的初始化隨機(jī)產(chǎn)生, 僅保留滿足約束條件的個(gè)體, 初始化種群個(gè)體的數(shù)量為N。 個(gè)體的適應(yīng)度由功能定位目標(biāo)貼近度確定。 種群選擇采用回放式等概率采樣的方式, 即輪盤賭。 第i個(gè)個(gè)體被選中的概率為

(8)

其中，fi(t)為第i個(gè)個(gè)體的適應(yīng)度。

SGA中交叉變異最主要的兩點(diǎn):概率和方式。種群的交叉、變異概率為固定值(pc、pm)。交叉和變異方式均采用多點(diǎn)形式。多點(diǎn)交叉中,每個(gè)基因座的交叉起始點(diǎn)設(shè)在編碼的起始(上一個(gè)基因座的末尾),交叉結(jié)束點(diǎn)在該基因座編碼的末尾,每個(gè)個(gè)體的基因座都以概率pc發(fā)生交叉行為。變異方式類似交叉。

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

圖1 染色體交叉Fig.1 Chromosome crossings

2.2 自適應(yīng)遺傳算子設(shè)計(jì)

在SGA中, 遺傳算子(選擇算子、 交叉算子、 變異算子)是影響算法收斂速度的重要因素, 本文主要在交叉算子、 變異算子上采用自適應(yīng)變化策略。

2.2.1 交叉算子設(shè)計(jì) 在SGA中,任意兩個(gè)父代染色體的交叉變異概率是相同且固定的。如果采用差異化的交叉變異概率,即父代染色體的適應(yīng)度越高,它們交叉變異的概率越低,有望使得適應(yīng)度高的染色體更多地保留在下一代種群中,從而提高新種群的總體適應(yīng)度。另一方面,對(duì)于適應(yīng)度較低的染色體,在迭代前期的交叉變異概率應(yīng)比迭代后期大;而對(duì)于適應(yīng)度較高的染色體,在迭代前期的交叉變異概率應(yīng)比迭代后期小。如此,在迭代前期可以擴(kuò)大搜索范圍,提升種群多樣性,以避免早收斂;而在迭代后期,可以避免破壞種群收斂,提升尋優(yōu)效果?；谝陨侠砟?以種群的適應(yīng)度均值為參照,設(shè)計(jì)了確定交叉算子的計(jì)算式：

(9)

2.2.2 自變異算子設(shè)計(jì) 類似于交叉算子的設(shè)計(jì)理念,由第i個(gè)染色體的自變異概率為

(10)

其中,pm為標(biāo)準(zhǔn)遺傳的變異概率;γ為可調(diào)系數(shù)。

2.3 種群多樣性檢測(cè)與維護(hù)

遺傳算法中的多樣性可從染色體或基因多樣性角度考慮。維持種群多樣性是降低種群陷入局部最優(yōu)的有效策略[18-19]。為避免破壞其收斂,每隔10代進(jìn)行一次種群多樣性檢測(cè),并根據(jù)檢測(cè)結(jié)果判定是否進(jìn)行維護(hù)。

第t代種群的多樣性D(t)可度量為

(11)

其中,di(t)表示t代中所有個(gè)體的第i位上的等位基因出現(xiàn)頻率最多的基因的次數(shù)；N為種群中染色體的個(gè)數(shù)；l為染色體的基因串的長度。 這種度量方式是從基因多樣性的角度測(cè)量種群多樣性。假設(shè)存在種群矩陣

(12)

矩陣中的每一行代表一個(gè)個(gè)體, 每一列代表相同基因座上的等位基因。 因?yàn)樗械?位等位基因中, 基因編碼相同的最大數(shù)量是2(基因編碼為3的數(shù)量最大), 故d1(t)=2； 類似可知，d2(t)=1、d3(t)=3、d4(t)=4。

由種群的多樣性D(t)和g/step(g、step分別為當(dāng)前迭代次數(shù)、 目標(biāo)總迭代次數(shù))共同確定種群更替占比ρ(表1)。 每次迭代后需要更新的個(gè)體數(shù)為ε·ρ·N(ε為可調(diào)參數(shù))。 這些個(gè)體以一種新輪盤賭的方式選取, 并向種群中添加新生成的個(gè)體：

表1 種群更替占比ρ的確定Table 1 Determination of population replacement percentage ρ

(13)

式中，pk(t)表示t代種群中第k個(gè)染色體的中間概率;fk(t)表示t代種群中第k個(gè)染色體的適應(yīng)度;fbest(t)表示t代種群中最佳的個(gè)體適應(yīng)度。然后,利用中間概率作為染色體被選中的概率,進(jìn)行輪盤賭選擇。

2.4 求解CTOR模型

為了快速有效地求解CTOR模型，針對(duì)SGA收斂速度慢、收斂精度不足等缺點(diǎn)，進(jìn)行了以下改進(jìn)：①采用2.2節(jié)的方法設(shè)計(jì)自適應(yīng)交叉算子與自變異算子，以提升遺傳進(jìn)化速度；②采用2.3節(jié)的方法加入種群多樣性檢測(cè)與維護(hù)機(jī)制，以保持種群多樣性，緩解局部收斂問題。圖 2為ADM-GA求解CTOR模型的流程。

圖2 ADM-GA算法求解CTOR模型流程Fig.2 Solving CTOR model process with ADM-GA algorithm

3 實(shí)驗(yàn)仿真與分析

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

實(shí)驗(yàn)PC機(jī)主要配置為：Intel(R)Core(TM)i7-9750H、2.6 GHz CPU、16 GB內(nèi)存，64位Windows 10操作系統(tǒng)，編程語言為Java 1.7。實(shí)驗(yàn)時(shí)，考慮PC機(jī)的個(gè)性化訂單問題。從公開的網(wǎng)絡(luò)平臺(tái)爬取了涉及顯示器、CPU、GPU、主板、內(nèi)存、硬盤、電源、鍵盤、鼠標(biāo)、耳機(jī)等10個(gè)配件共計(jì)約348條記錄，其中單個(gè)配件的最小記錄條數(shù)為23條，最高為52條。

經(jīng)過多次參數(shù)調(diào)節(jié)和統(tǒng)計(jì)數(shù)據(jù)發(fā)現(xiàn)，采用如表2所示的參數(shù)設(shè)置時(shí)，實(shí)驗(yàn)效果最佳。

表2 最佳參數(shù)設(shè)置組合Table 2 Parameter settings

3.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)對(duì)比了標(biāo)準(zhǔn)遺傳算法(SGA)、在SGA的基礎(chǔ)上添加2.2節(jié)設(shè)計(jì)的自適應(yīng)遺傳算子后的遺傳算法(DGA)、本文算法(在DGA的基礎(chǔ)上加入2.3節(jié)多樣性檢測(cè)與維護(hù)策略后的遺傳算法, 記為ADM-GA)3種算法的性能。 為提升實(shí)驗(yàn)數(shù)據(jù)的可靠性, 實(shí)驗(yàn)結(jié)果為測(cè)試50次后的各相關(guān)指標(biāo)數(shù)值(適應(yīng)度、 遺傳代數(shù)、 迭代時(shí)間)的均值或標(biāo)準(zhǔn)差。

圖3對(duì)比了各代種群的歷史最佳適應(yīng)度。 可見，3種算法在迭代前期(<200代)都能較快地趨近最優(yōu)解, 200代之后逐漸緩慢。 在到達(dá)相同的迭代次數(shù)時(shí), ADM-GA比SGA和DGA可以獲得更好的適應(yīng)度。

圖3 3種算法的歷史最佳適應(yīng)度值Fig.3 Historical optimal fitness values of the three algorithms

圖4對(duì)比了3種算法所獲得的最佳適應(yīng)度的標(biāo)準(zhǔn)差。可見，標(biāo)準(zhǔn)差越小, 穩(wěn)定性越好。 3種算法的穩(wěn)定性總體上為: ADM-GA>SGA>DGA。 DGA的穩(wěn)定性弱于SGA, 是因?yàn)橐胱赃m應(yīng)交叉和自變異算子后, 雖然在收斂速度上有所加快, 但更容易陷于局部收斂； 而ADM-GA在DGA的基礎(chǔ)上, 加入了多樣性檢測(cè)與恢復(fù)機(jī)制, 較好地克服了局部收斂問題, 穩(wěn)定性較好。

圖4 3種算法的適應(yīng)度標(biāo)準(zhǔn)差Fig.4 Fitness standard deviation of the three algorithms

表3對(duì)比了3種算法達(dá)到相應(yīng)的目標(biāo)適應(yīng)度值時(shí)所需要的遺傳代數(shù)及時(shí)間開銷。 其中, 時(shí)間開銷僅統(tǒng)計(jì)了種群初始化、 選擇、 交叉、 變異、 適應(yīng)度計(jì)算、 多樣性檢測(cè)與維護(hù)等操作, 而沒有統(tǒng)計(jì)編碼解碼的時(shí)間開銷(因?yàn)樵撨^程的時(shí)間開銷較大, 且3種算法所花時(shí)間是相同的)。 可見，3種算法的時(shí)間開銷均隨著目標(biāo)適應(yīng)度的增加而增加, 但DGA與ADM-GA的增速比SGA緩慢很多; 達(dá)到同一目標(biāo)適應(yīng)度, ADM-GA所需要的迭代次數(shù)與時(shí)間開銷均是最低的, DGA次之, SGA最高。

表3 3種算法迭代次數(shù)及時(shí)間開銷Table 3 Iteration times and time cost of the three algorithms

4 結(jié) 論

確定電子產(chǎn)品的CTO訂單是實(shí)現(xiàn)個(gè)性化設(shè)計(jì)與生產(chǎn)的重要基礎(chǔ),其目標(biāo)是根據(jù)用戶的個(gè)性化需求確定產(chǎn)品所涉及的每個(gè)配件的品牌與型號(hào)。CTO訂單推薦可輔助用戶與專業(yè)設(shè)計(jì)人員溝通,以快速、準(zhǔn)確地確定CTO訂單。通過形式化度量功能定位目標(biāo)貼近度指標(biāo),電子產(chǎn)品CTO訂單推薦被建模為一個(gè)多維多選擇背包問題。為了克服經(jīng)典遺傳算法存在局部收斂及收斂速度較慢等不足,在用遺傳算法求解該問題時(shí),提出了新的遺傳算子自適應(yīng)調(diào)節(jié)方法及種群多樣性檢測(cè)與維護(hù)策略。當(dāng)前的CTO訂單推薦,僅從用戶的角度進(jìn)行了優(yōu)化,同時(shí)從用戶與生產(chǎn)商角度(如優(yōu)先利用現(xiàn)有庫存、 推薦和優(yōu)化現(xiàn)有生產(chǎn)線加工產(chǎn)品等)進(jìn)行優(yōu)化,是下一階段的研究方向。