基于改進遺傳算法的電子產品CTO訂單推薦

韓海峰,葉恒舟,張 路

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

0 引 言

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

在需求獲取方面,但斌等研究了一種需求智能獲取方法,該方法關注用戶表達需求的異質性,提供與用戶的個人特征和使用情景相適應的需求表達方式,從而幫助用戶提高需求描述的客觀性和準確性[2]。Carulli等通過建立產品虛擬樣機和虛擬現實環境,在早期幫助客戶直觀感知產品,以輔助用戶與專業設計人員溝通[3]。

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

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

1 電子產品CTOR模型

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

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

1.1 功能定位目標貼近度

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

(1)

其中, |SSi|、 |CSi|分別表示集合SSi、CSi中元素的個數。

例如, 設商務手機的標準GPU型號定位在集合{530, 540}中, 而GPU型號可選集為{430, 530, 540, 630, 640}。 若用戶選擇的型號為430, 則SS集為{430}, GPU功能定位目標貼近度為1-1/5=0.8; 若用戶選擇為530, 則SS集為空, GPU功能定位目標貼近度為1; 若用戶選擇640, 則SS集為{630, 640}, GPU功能定位目標貼近度為1-2/5=0.6。

總體的功能定位目標貼近度μ為

(2)

1.2 CTOR模型

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

目標: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)描述價格約束,prij為第i個配件的第j種選擇的價格,pr0為加工等成本, 認為是一個常數, [prcl,prcu]為用戶約定的產品價格區間; 式(4)描述功耗約束,pcij為第i個配件的第j種選擇的配件功耗(有些配件的功耗很小, 可以忽略不計, 即取值為0),pcc為用戶約定的產品功耗上限; 式(5)描述根據用戶的選擇計算功能定位中某種指標值的方法。

2 改進遺傳算法求解CTOR模型

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

2.1 簡單遺傳算法

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

(8)

其中，fi(t)為第i個個體的適應度。

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

以實數編碼為例, 染色體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], 如圖1所示。 多點變異類似于多點交叉,若圖1中染色體A的基因座1、 4、 6發生變異,則新染色體A的編碼為[**11 32 **13 ** ], ** 為從相對應的基因座編碼空間中隨機選取的編碼。

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

2.2 自適應遺傳算子設計

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

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

(9)

2.2.2 自變異算子設計 類似于交叉算子的設計理念,由第i個染色體的自變異概率為

(10)

其中,pm為標準遺傳的變異概率;γ為可調系數。

2.3 種群多樣性檢測與維護

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

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

(11)

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

(12)

矩陣中的每一行代表一個個體, 每一列代表相同基因座上的等位基因。 因為所有第1位等位基因中, 基因編碼相同的最大數量是2(基因編碼為3的數量最大), 故d1(t)=2； 類似可知，d2(t)=1、d3(t)=3、d4(t)=4。

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

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

(13)

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

2.4 求解CTOR模型

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

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

3 實驗仿真與分析

3.1 實驗環境與參數取值

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

經過多次參數調節和統計數據發現，采用如表2所示的參數設置時，實驗效果最佳。

表2 最佳參數設置組合Table 2 Parameter settings

3.2 實驗結果分析

實驗對比了標準遺傳算法(SGA)、在SGA的基礎上添加2.2節設計的自適應遺傳算子后的遺傳算法(DGA)、本文算法(在DGA的基礎上加入2.3節多樣性檢測與維護策略后的遺傳算法, 記為ADM-GA)3種算法的性能。 為提升實驗數據的可靠性, 實驗結果為測試50次后的各相關指標數值(適應度、 遺傳代數、 迭代時間)的均值或標準差。

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

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

圖4對比了3種算法所獲得的最佳適應度的標準差?？梢?，標準差越小, 穩定性越好。 3種算法的穩定性總體上為: ADM-GA>SGA>DGA。 DGA的穩定性弱于SGA, 是因為引入自適應交叉和自變異算子后, 雖然在收斂速度上有所加快, 但更容易陷于局部收斂； 而ADM-GA在DGA的基礎上, 加入了多樣性檢測與恢復機制, 較好地克服了局部收斂問題, 穩定性較好。

圖4 3種算法的適應度標準差Fig.4 Fitness standard deviation of the three algorithms

表3對比了3種算法達到相應的目標適應度值時所需要的遺傳代數及時間開銷。 其中, 時間開銷僅統計了種群初始化、 選擇、 交叉、 變異、 適應度計算、 多樣性檢測與維護等操作, 而沒有統計編碼解碼的時間開銷(因為該過程的時間開銷較大, 且3種算法所花時間是相同的)。 可見，3種算法的時間開銷均隨著目標適應度的增加而增加, 但DGA與ADM-GA的增速比SGA緩慢很多; 達到同一目標適應度, ADM-GA所需要的迭代次數與時間開銷均是最低的, DGA次之, SGA最高。

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

4 結 論

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