面向產品配置設計的改進交互式遺傳算法

朱佳棟 蘇少輝 陳 昌 劉桂英

杭州電子科技大學機械工程學院，杭州，310018

0 引言

隨著大規模定制的飛速發展和新產品的不斷涌現，產品配置作為實現大規模定制的一個重要手段，越來越受到企業的關注。產品配置的過程中，企業大多是先分解和分析用戶的需求和偏好，再將其轉化成為設計參數并作為產品配置的輸入，使得用戶不能積極地參與到產品配置過程，導致設計出來的產品不能完全滿足用戶的偏好和需求。

為在產品配置中更快和更有效地獲取用戶需求，同時降低成本、提高效率，人們將一系列互動進化計算（IEC）方法用于產品定制。TSENG等［1］提出的方法可以在有效縮短時間和降低設計成本的前提下，生產令用戶滿意的新產品。KIM等［2］、尤海峰［3］開發了一種能在產品定制中使用交互式遺傳算法（interactive genetic algorithm，IGA）進行服裝設計的系統。

雖然IGA可以有效地解決一些不能由函數來進行直接計算的隱性性能優化問題［4］，但是，IGA在使用中還存在著一個顯著的問題——用戶疲勞。目前，改善用戶疲勞的方法有幾種，如縮短評估的時間、減少進化代數、加速收斂算法等［5］。盡管這些方法可以在一定程度上減少用戶疲勞，但忽視了不同用戶有不同偏好的實際情況，不能有效地用于產品配置。本文根據IGA的特點，對IGA進行改進優化，減少用戶疲勞，并在產品配置中可以更有效地獲得用戶偏好和需求。

1 產品配置

企業想要在激烈的市場競爭中站穩腳跟，就必須滿足用戶的不同需求，加快產品的創新，生產出能夠滿足不同用戶的產品。因此，大規模定制的概念也隨之產生，產品配置作為實現大規模定制的重要手段和方法，是為了在滿足用戶需求的同時，提高企業的效率，降低成本。

產品配置過程比較復雜，具體的流程如圖1所示。產品配置的求解就是利用現有資源，根據用戶的偏好需求，配置出符合用戶要求的產品［6］。如何快速找出用戶偏好的產品組件，并將它們配置成令用戶滿意的產品，這其中包括了如何處理組件的組裝、使用和外觀等多方面的問題。

圖1 產品配置框架Fig.1 Product configuration framework

通過產品配置可以實現產品的多樣化，從而滿足不同的用戶需求。產品配置是產品創新的一個重用手段，產品配置過程中，可以運用交互式遺傳算法對用戶需求進行處理。通過對產品的拆分和分類，運用IGA對產品的每個組件或模塊進行分類編碼，根據每個用戶對產品的不同要求，配置出具有相應功能的產品。與此同時，IGA可以應用于配置結果的評價中，運用算法可以得到每個配置的結果，并將這些結果進行反饋。最終對這些配置結果進行評價，得到每個配置結果的適應度，通過適應度來識別配置結果符合用戶需求的程度。

2 算法的優化設計

傳統IGA的流程如圖2所示，用戶通過IGA來評價個體的適應值［7］，長時間、大量重復的評價必然會造成用戶疲勞，因此需要對其進行優化和改進。首先，從用戶對種群的認識角度來看，整個種群是逐漸從簡單演變到復雜的，初始階段的種群相對簡單，因此用戶獲得關于種群的知識也相對簡單，可以有效地避免由于用戶對種群認知的局限而對進化的種群作出不準確的評價；其次，從產品配置的角度來看，用戶也可以像設計師一樣逐漸參與到產品配置過程中。

圖2 交互式遺傳算法流程圖Fig.2 Interactive genetic algorithm flow chart

假設fn（x)是用戶評估進化個體x的適應度，S為個體x的搜索空間，n表示種群進化的階段，通過求適應度的最大值來優化算法：

max fn（x）x∈S

2.1 變異個體的改進設計

遺傳算法中，變異體現為變量的改變，即把1變成0，或0變成1［8］，例如10位變量的第5位發生了翻轉，從0111011010變異為0111111010。

為了讓種群在進化的過程當中，在獲得優良個體的基礎上提高局部的搜索效率，并保持個體的差異性，防止發生提前收斂，對變異算子進行了改進。

種群中個體發生變異的概率

式中，pm為原始變異的概率；L為位串長度。

對于給定的均勻隨機變量x∈［0，1］，如果x≤Pm（xi（t）），那么個體就產生變異，反之則不產生變異。

應保證整個種群在傳統變異概率的期望次數（nLpm）與新的基因變異概率期望次數相同，即

在第s代種群選擇、交叉所產生的結果當中，對選擇的個體進行隨機變異操作的表達式為

由于Pm(xi(t))?1，所以相比傳統變異方式，新變異方式減少了計算量。為了獲得更合適的變異個體，通過引入黃金分割變異來得到最適變異個體［9］：

2.2 遺傳操作的改進設計

不同階段，種群的復雜性不同。與傳統的交互式遺傳算法相比，通過添加參數N來表示新的進化階段。雖然算法過程會變得復雜，卻更具有方向性。隨著演變的不斷進行，用戶可以對不同階段的產品配置有更好的了解，也會有更好的評價。

對于遺傳操作，隨著新模塊的出現，將分為兩個步驟：

（1）選擇在每個種群最后階段具有高度適應的進化個體，并且由

（2）選擇新的基因型模塊。新基因型模塊的等位基因適應度不固定，因此通過第一步選擇的個體來判斷用戶偏好。系統將搜索相似偏好的用戶，并根據步驟（1）的評估值來產生等位基因。

經過上述步驟后，最后一代進化個體與隨機選擇的基因型模板一一對應，并且相應產生新階段的第一代群體。

2.3 改進后的算法流程圖

由算法流程圖（圖3）可以看到，相比于傳統的IGA，本文所提算法的控制參數是根據不同進化階段進行設置的；該算法比傳統IGA更容易確定終止的進化代數，體現了遺傳算法的核心特征。此外，當進入新階段時，系統將搜索具有相似偏好的用戶以實現多用戶的協作演進，來減輕用戶疲勞，提高局部搜索效率。

圖3 改進后的算法流程圖Fig.3 Improved algorithm flow chart

3 應用實例

由于不同用戶對產品的需求不同，因此以多功能液壓千斤頂產品配置為例［10］，對改進后的算法進行應用驗證。

3.1 編碼

合適的編碼對算法運算求解有著比較大的影響，根據用戶需求，將多功能千斤頂產品配置的編碼大致設定為四個部分：起重質量；起重行程；是否有照明系統；最大舉升高度。

根據多功能液壓千斤頂的三維圖及用戶的需求，將配置要求用二進制編碼表示出來。起重質量的編碼為0000、0001、0010、…；起重行程的編碼為0000、0001、…；是否有照明系統的編碼為01、10；最大舉升高度的編碼為00000、00001、00010。每個個體的編碼共有15位，多功能千斤頂的基因編碼如圖4所示。

圖4 多功能液壓千斤頂基因編碼圖Fig.4 Multi-functional hydraulic jack gene coding map

3.2 參數設置

為了更好地找到最優個體，每一代的規模既不能太大，也不能太小，太大使搜索空間變大，導致用戶容易產生疲勞；太小容易局部收斂。所以本文選擇種群大小Ns=5，令同一階段的交叉概率為0.8，突變概率為0.09；令跨階段的交叉概率為1，突變概率為0。進化終止條件如下：種群終止的階段數為5，在終止階段之前，若有用戶滿意的個體產生，則用戶可終止種群的進化。

3.3 實驗

通過上述編碼和參數設置，對其產品配置進行實驗，通過實驗來檢驗改進IGA是否符合要求。

3.3.1 適應度函數

將用戶的評價分為三種：符合（3分）、一般（2分）、不符合（1分），再將每一位用戶的評價相加，得出總分數。當總結果相同時，可以通過應用共識度標準來得出適應度［11］。

設共識度為G，則可以得到

3.3.2 實驗結果

為了檢驗所提出的算法，根據用戶1的需求偏好：起重質量為3 t，起重行程為250 mm，需要照明系統，最大舉升高度為400 mm，得到配置結果，如表1所示。

用戶2的需求偏好：起重質量為2 t，起重行程為350 mm，無照明系統，最大舉升高度為500 mm，配置結果如表2所示。

表1 用戶1配置結果Tab.1 User 1 configuration results

表2 用戶2配置結果Tab.2 User 2 configuration results

通過用戶評價，對新舊IGA算法的進化代、評估的個體數目、評估的時間以及適應度進行比較，結果數據如表3所示。

表3 傳統的交互式遺傳算法與新的交互式遺傳算法的比較Tab.3 Comparison of traditional interactive genetic algorithm with new interactive genetic algorithm

比較和分析新舊IGA的運算結果，對它們的平均進化代比較可知，傳統IGA高于新IGA；其次，對于平均評價的個體數目，傳統IGA也高得多。

通過用戶評價得出個體適應度，并令X軸表示進化代，Y軸表示進化個體在每一代的適應度，可得到圖5所示的結果。

圖5 進化個體適應度的比較Fig.5 Evolution of individual fitness

比較兩種IGA可知，在產品配置中，新IGA可以大大縮短用戶評價產品配置結果的時間，更快配置出令用戶滿意的產品，減少用戶疲勞。隨著進化代的不斷增加，配置出產品結果的適應度也不斷提高，相應的用戶滿意度也隨之提高。將新IGA運用到產品配置中，可以有效地提高企業的生產效率并降低生產成本，增強了企業的市場競爭力。

4 結語

改進的交互式算法可以根據進化階段，將個體分成不同的遺傳單元，通過具有相似偏好的用戶來進行多用戶協同配置設計，可以較好地減少用戶疲勞，還可以快速方便地獲得用戶要求，配置出令用戶滿意的產品。但是，所提出的算法進行的實驗較少，在后續的研究中，還需要通過更多的實驗進行測試和研究，進而完善算法，從而更好地滿足不同用戶的需求。