基于遺傳算法的產(chǎn)品創(chuàng)新設(shè)計

胡春雨，劉弘

(山東師范大學(xué)信息科學(xué)與工程學(xué)院，山東 濟南 250014)

隨著全球經(jīng)濟的迅速發(fā)展，產(chǎn)品的市場占有率對企業(yè)的生存和發(fā)展起到了舉足輕重的作用，而產(chǎn)品的創(chuàng)新性又決定了其市場占有份額。實踐證明，在產(chǎn)品設(shè)計過程中概念設(shè)計是產(chǎn)品設(shè)計中最關(guān)鍵、最復(fù)雜、最有決定性和創(chuàng)新性的階段［1］。計算機輔助設(shè)計(CAD)技術(shù)改變了傳統(tǒng)的設(shè)計方式，而且正朝著智能化的方向發(fā)展［2］。如何利用CAD來實現(xiàn)概念設(shè)計的自動化，減輕設(shè)計者的壓力成為計算機圖形學(xué)領(lǐng)域面臨的挑戰(zhàn)。

進化設(shè)計方法作為一種新方法已經(jīng)得到了廣泛的應(yīng)用［3］。遺傳算法作為進化計算的重要組成部分更是受到了越來越多的關(guān)注。1975年，Holland［4］首先提出了遺傳算法這一概念。到20世紀80年代后期，由于在經(jīng)濟預(yù)測等應(yīng)用領(lǐng)域獲得成功，進化計算成為十分熱門的研究話題［5］。目前，國內(nèi)外已經(jīng)將遺傳算法應(yīng)用于產(chǎn)品創(chuàng)新設(shè)計領(lǐng)域并做了大量的研究。文獻［6］提出了一種用進化計算及可視化技術(shù)支持概念創(chuàng)新的方法，并將其運用于臺燈造型設(shè)計。文獻［7］運用遺傳算法設(shè)計出新穎的建筑平面圖，同時展示了進化計算可以使智能體獲得學(xué)習(xí)能力，生成新的建筑物。文獻［8］在討論人機交互的特性的基礎(chǔ)上，利用遺傳算法應(yīng)用生成了輪椅靠背曲面形態(tài)。文獻［9］和文獻［10］也在遺傳算法的基礎(chǔ)上分別實現(xiàn)了家具造型以及汽車造型的創(chuàng)新設(shè)計。

在產(chǎn)品創(chuàng)新設(shè)計領(lǐng)域，遺傳編碼作為應(yīng)用遺傳算法時非常重要的一部分，其研究與應(yīng)用起到了十分重要的作用。目前在該領(lǐng)域中應(yīng)用較多的編碼方式有樹形結(jié)構(gòu)編碼、實數(shù)編碼、二進制編碼等等，這些編碼方式都很好的實現(xiàn)了設(shè)計者的創(chuàng)新要求［11］。

本文介紹了一種基于遺傳算法進行產(chǎn)品創(chuàng)新設(shè)計的方法，以及該方法運用于產(chǎn)品外觀設(shè)計的過程。對于編碼方式，本文采用了文獻［12］提出的雙層結(jié)構(gòu)編碼方式，雖然這種編碼方式在產(chǎn)品外觀造型創(chuàng)新設(shè)計領(lǐng)域還未得到廣泛應(yīng)用，但十分適合對控制點坐標(biāo)進行編碼，將其應(yīng)用于產(chǎn)品外觀輪廓線的設(shè)計十分方便、直觀。在VC++6.0及三維建模引擎ACIS可視化平臺的基礎(chǔ)上，將以上方法應(yīng)用于風(fēng)箏的設(shè)計過程中，得到了很多設(shè)計方案。

1 基于遺傳算法的產(chǎn)品外觀造型創(chuàng)新設(shè)計

為充分發(fā)揮雙層結(jié)構(gòu)與二進制結(jié)構(gòu)兩種編碼方式的優(yōu)勢，針對不同類型的產(chǎn)品，在充分了解其造型特征的基礎(chǔ)之上，劃分為兩類:可分割類型(例如臺燈、手機等)和不可分割類型(例如洗衣機、風(fēng)箏等)，并針對兩種類型提出一種可以通用的產(chǎn)品造型創(chuàng)新設(shè)計方法。

1.1 遺傳算法的應(yīng)用方式

遺傳算法既可以對產(chǎn)品整體進行進化計算，也可以對產(chǎn)品的部件單獨進行進化計算［2］，對于外觀造型可分割為獨立組件的產(chǎn)品，可以首先采用雙層結(jié)構(gòu)的遺傳算法對單個組件進行形態(tài)造型設(shè)計，然后使用二進制編碼遺傳算法對不同組件生成組合方案。對于形態(tài)造型不可分割為獨立組件的產(chǎn)品，可選擇出對外觀造型產(chǎn)生重要影響的主要部件，采用雙層結(jié)構(gòu)的遺傳算法對該部件進行造型設(shè)計。

1.1.1 染色體編碼方式

通過對已有的各種編碼方式的優(yōu)缺點進行比較，本文選擇了兩種編碼方式:一種是標(biāo)準(zhǔn)遺傳算法中通常采用的二進制編碼方式，這種編碼方式雖然表達不夠靈活，但其基因表達細膩，可用于產(chǎn)品不同部件的組合搭配之中;另一種編碼方式為雙層結(jié)構(gòu)的編碼方式，對于產(chǎn)品中一些不可分割的部件或整體，可以將其形態(tài)看做整體的外部輪廓線，通過對外部輪廓線提取控制點，并對控制點坐標(biāo)進行交叉、變異操作，從而實現(xiàn)曲線形態(tài)的改變。

1.1.1.1 雙層結(jié)構(gòu)染色體編碼方式

雙層結(jié)構(gòu)編碼方式充分模擬了生物體中承載遺傳機制的染色體結(jié)構(gòu)，將染色體劃分為兩層:上層表示產(chǎn)品的控制點序列，對應(yīng)生物體中的染色體;下層表示控制點的坐標(biāo)信息，即對應(yīng)生物體中DNA上所攜帶的遺傳信息。其具體的編碼方式見圖1。

1.1.1.2 二進制染色體編碼方式

二進制編碼方式所使用的編碼符號集是由二進制符號0和1所組成的二值符號集{0，1}，它所構(gòu)成的個體基因型是一個二進制編碼符號串［13］。將二進制編碼應(yīng)用于產(chǎn)品不同組件的組裝時，可以給每種部件賦以一定數(shù)位的二進制編碼，圖2給出了兩個有二進制編碼的產(chǎn)品部件組合。

1.1.2 遺傳算子

1.1.2.1 雙層結(jié)構(gòu)編碼遺傳算子

在雙層結(jié)構(gòu)的編碼方式下，交叉算子和變異算子都是對控制點進行的，控制點的不同組合對應(yīng)著不同的產(chǎn)品形態(tài)曲線。對于雙層結(jié)構(gòu)編碼的遺傳算子，本文將以風(fēng)箏造型的創(chuàng)新設(shè)計為例來說明其交叉與變異過程(本文中的設(shè)計實例所涉及到的控制點太多，無法一一列出，對稱控制點只列出一個且只列出主要的控制點坐標(biāo))。圖3詳細地說明了這種編碼方式的交叉過程，變異過程與此類似，在此沒有畫出詳細的圖示。為形象說明這種編碼方式，圖4與圖5以風(fēng)箏造型的設(shè)計實例介紹了該遺傳操作過程。

1.1.2.2 二進制編碼遺傳算子

在二進制編碼方式下，交叉算子和變異算子都是對二進制字符串中的位進行的。據(jù)此設(shè)計的交叉和變異過程分別見圖6(以圖2中的‘M’點為交叉點)、圖7(以圖2中的‘N’點為變異作用點)。(該遺傳編碼方式的操作過程較為常見，可參考文獻［5］中圖11的臺燈組裝方案)

1.1.3 個體的篩選

在遺傳算法中，個體的篩選通常是由適應(yīng)度函數(shù)來決定的。由于產(chǎn)品的創(chuàng)新性以及外形是否美觀通常來自于人的主觀感受，無法用統(tǒng)一的公式或函數(shù)來確定，本文采用人機交互與文獻［14］所提出的Agent技術(shù)相結(jié)合的方式來進行評價。在設(shè)計的初始階段由設(shè)計人員給出產(chǎn)品的適應(yīng)度值，并由Agent將適應(yīng)度值作為知識保存到知識庫中，當(dāng)后續(xù)再次遇到類似的情況時，系統(tǒng)直接給出適應(yīng)度值，從而逐漸減少人機交互的次數(shù)，減少設(shè)計者的工作量，實現(xiàn)智能化處理。

遺傳算法應(yīng)用步驟:

步驟1:生成初始化種群。在進行部件外觀設(shè)計時，利用雙層結(jié)構(gòu)遺傳算法，通過使用掃描儀或數(shù)碼相機取得產(chǎn)品外觀造型的輪廓曲線，或者在直接獲取的造型輪廓曲線中提取控制點坐標(biāo)，生成初始個體。在進行部件組裝時，利用二進制遺傳算法，利用已有產(chǎn)品個體生成初始種群。

步驟2:通過人機交互對初始種群中的個體進行評價并設(shè)定適應(yīng)度值。

步驟3:利用上述提到的方法對種群進行交叉、變異和篩選。

步驟4:如果用戶不終止遺傳過程，則轉(zhuǎn)步驟2;否則，結(jié)束。

1.2 產(chǎn)品外形的分割方法

首先，通過人機交互判斷產(chǎn)品外觀是否可分割，對于外觀不可分割的產(chǎn)品選出影響其外觀造型的主要部件。而對于外觀可分割的產(chǎn)品，由于組件的劃分和個體的篩選類似，通常依靠人的主觀意識進行判斷，很難依靠計算機直接進行判斷，這里采用文獻［9］中介紹的“支持創(chuàng)新概念設(shè)計的多Agent系統(tǒng)”所具有的任務(wù)分解功能對產(chǎn)品進行組件劃分，將產(chǎn)品整體作為一個任務(wù)，利用任務(wù)分解功能將其劃分為多個不同的組件。具體的應(yīng)用過程可參考文獻［9］第4部分的花瓶的設(shè)計分解模型。

1.3 產(chǎn)品外觀創(chuàng)新設(shè)計的具體步驟

(1)選擇要進行外觀創(chuàng)新設(shè)計的產(chǎn)品，判斷產(chǎn)品的外觀是否可劃分為不同的組件。

(2)對于外觀不可分割的產(chǎn)品選出影響其外觀造型的主要部件，然后轉(zhuǎn)向步驟(4);對于外觀可分割的產(chǎn)品利用1.2中所介紹的分割方法進行組件的劃分，然后轉(zhuǎn)向步驟(3)。

(3)在劃分出的眾多部件中選出要進行造型設(shè)計的部件。

(4)利用雙層結(jié)構(gòu)的遺傳算法(包括生成初始種群、選擇、交叉、變異、篩選等步驟)對產(chǎn)品部件進行外觀創(chuàng)新設(shè)計。

(5)判斷產(chǎn)品的所有部件是否都已完成設(shè)計，若是，轉(zhuǎn)向步驟(6);若不是，轉(zhuǎn)向步驟(3)。

(6)判斷產(chǎn)品外觀是否經(jīng)過分割，若是，轉(zhuǎn)向步驟(7);若不是，轉(zhuǎn)向步驟(8)。

(7)利用二進制編碼的遺傳算法進行部件組裝。

(8)通過人機交互對產(chǎn)品進行修改和改進，至此產(chǎn)品的設(shè)計過程完成。

完整的算法偽代碼如下:

利用二進制編碼的遺傳算法進行部件組裝;

Else選擇對產(chǎn)品外觀產(chǎn)生最重要影響的部件;

利用雙層結(jié)構(gòu)編碼的遺傳算法對產(chǎn)品部件進行外觀設(shè)計;通過人機交互對產(chǎn)品進行修改;End;

2 設(shè)計實例

下面介紹風(fēng)箏的設(shè)計實例，說明如何運用遺傳算法進行產(chǎn)品外觀創(chuàng)新設(shè)計。

(1)選擇風(fēng)箏作為要進行產(chǎn)品外觀創(chuàng)新設(shè)計的產(chǎn)品，然后判斷產(chǎn)品類型。風(fēng)箏外觀形態(tài)不易分割，且對其外觀形態(tài)影響較大的部件即為風(fēng)箏面，本例中主要對風(fēng)箏的輪廓線進行造型設(shè)計，系統(tǒng)根據(jù)設(shè)計要求設(shè)定風(fēng)箏的尺寸大小，為后續(xù)設(shè)計計算作參考。

(2)設(shè)定產(chǎn)品參數(shù)及遺傳算法參數(shù)。

(3)選擇已有的風(fēng)箏造型作為初始種群，并通過系統(tǒng)與設(shè)計人員的人機交互設(shè)定個體的適應(yīng)度值。

(4)根據(jù)當(dāng)前種群的適應(yīng)度值，利用雙層結(jié)構(gòu)的遺傳算法對產(chǎn)品進行創(chuàng)新設(shè)計，此過程包括了交叉和變異兩種操作。

(5)重復(fù)第(3)步操作，直到設(shè)計人員得到了滿意的產(chǎn)品造型才選擇停止操作。

(6)人機交互對生成的產(chǎn)品作進一步的修改，生成最終的產(chǎn)品造型。

圖8列出了一部分生成的風(fēng)箏設(shè)計效果圖。

圖8 部分生成的風(fēng)箏設(shè)計方案Fig.8 Design scheme of some generated kites

3 結(jié)語

將遺傳算法應(yīng)用于產(chǎn)品創(chuàng)新設(shè)計之中具有十分重要的現(xiàn)實意義，本文提出的這種應(yīng)用遺傳算法進行產(chǎn)品創(chuàng)新設(shè)計的方法主要適用于進行簡單產(chǎn)品的不規(guī)則外觀造型設(shè)計，為設(shè)計師進行造型設(shè)計提供依據(jù)，目前主要應(yīng)用于工藝品設(shè)計領(lǐng)域。未來仍需進行的工作是進一步完善該方法，并將其應(yīng)用到更多種類的產(chǎn)品創(chuàng)新設(shè)計之中，充分擴展其應(yīng)用范圍。

［1］原霞飛，劉希玉，劉鳳鳴.關(guān)于產(chǎn)品外型概念設(shè)計方法的研究［J］.網(wǎng)絡(luò)安全技術(shù)及應(yīng)用，2011(2):39－40.

［2］王吉華，劉弘.基于特征幾何體的零件進化設(shè)計基因組研究［J］.計算機集成制造系統(tǒng)，2009，15(1):21－27.

［3］易鵬飛，魏小鵬，趙婷婷.基于遺傳算法和非均勻有理B樣條表達的產(chǎn)品外型創(chuàng)新設(shè)計［J］.計算機集成制造系統(tǒng)，2008，14，(2):221 －225，233.

［4］HOLLAND J H.Adaptation in Natural and Artificial System［M］.US:University of Michigan Press，1975.

［5］朝瑞鋒.遺傳算法原理與應(yīng)用實例［M］.北京:兵器工業(yè)出版社，2009.

［6］劉弘，劉希玉.支持外觀造型設(shè)計的進化計算方法［J］.計算機輔助設(shè)計與計算機圖形學(xué)學(xué)報，2006，118(11):101－107.

［7］GERO J S，KAZAKOV V.An exploration-based evolutionary model of generative design process［J］.Microcomputers in Civil Engineering，1996，11(4):209 －216.

［8］馬劍鴻，楊隨先.遺傳算法在產(chǎn)品人機形態(tài)設(shè)計中的應(yīng)用［J］.機械設(shè)計與研究，2006，22(5):88－91.

［9］董春龍，劉希玉.基于遺傳算法的家具造型創(chuàng)新設(shè)計［J］.南京師范大學(xué)學(xué)報:工程技術(shù)版，2010，10(3):78－81.

［10］陳珂，劉弘.基于遺傳算法的汽車外觀造型創(chuàng)新設(shè)計術(shù)［J］.計算機應(yīng)用研究，2008，25(1):203－205.

［11］吳海龍，劉希玉，向來生.基于遺傳算法的骨骼結(jié)構(gòu)模型概念創(chuàng)新設(shè)計［J］.計算機應(yīng)用，2011，31，(4):1155－1158.

［12］劉佳星，余隋懷.基于組合遺傳算法的產(chǎn)品形態(tài)創(chuàng)新設(shè)計研究［J］.計算機應(yīng)用研究，2009，26(4):1244－1245，1268.

［13］劉濤.基于進化計算技術(shù)的剪紙圖案創(chuàng)新設(shè)計研究與實現(xiàn)［D］.濟南:山東師范大學(xué)，2009.

［14］邱莉榕，劉弘.支持創(chuàng)新概念設(shè)計的多 agent系統(tǒng)［J］.計算機集成制造系統(tǒng)，2003，9(Z1):38－42，52.