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

胡春雨，劉弘

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

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

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

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

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

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

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

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

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

1.1.1 染色體編碼方式

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

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

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

1.1.1.2 二進(jìn)制染色體編碼方式

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

1.1.2 遺傳算子

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

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

1.1.2.2 二進(jìn)制編碼遺傳算子

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

1.1.3 個(gè)體的篩選

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

完整的算法偽代碼如下:

利用二進(jìn)制編碼的遺傳算法進(jìn)行部件組裝;

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

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

2 設(shè)計(jì)實(shí)例

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

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

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

［3］易鵬飛，魏小鵬，趙婷婷.基于遺傳算法和非均勻有理B樣條表達(dá)的產(chǎn)品外型創(chuàng)新設(shè)計(jì)［J］.計(jì)算機(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)用實(shí)例［M］.北京:兵器工業(yè)出版社，2009.

［6］劉弘，劉希玉.支持外觀造型設(shè)計(jì)的進(jìn)化計(jì)算方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與計(jì)算機(jī)圖形學(xué)學(xué)報(bào)，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)品人機(jī)形態(tài)設(shè)計(jì)中的應(yīng)用［J］.機(jī)械設(shè)計(jì)與研究，2006，22(5):88－91.

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

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

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

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

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

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