胡春雨，劉弘

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

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

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

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

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

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

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

1.1 遺傳算法的應用方式

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

1.1.1 染色體編碼方式

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

1.1.1.1 雙層結構染色體編碼方式

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

1.1.1.2 二進制染色體編碼方式

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

1.1.2 遺傳算子

1.1.2.1 雙層結構編碼遺傳算子

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

1.1.2.2 二進制編碼遺傳算子

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

1.1.3 個體的篩選

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

遺傳算法應用步驟:

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

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

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

步驟4:如果用戶不終止遺傳過程，則轉步驟2;否則，結束。

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

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

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

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

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

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

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

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

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

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

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

完整的算法偽代碼如下:

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

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

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

2 設計實例

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

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

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

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

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

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

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

圖8列出了一部分生成的風箏設計效果圖。

圖8 部分生成的風箏設計方案Fig.8 Design scheme of some generated kites

3 結語

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

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

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

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

［6］劉弘，劉希玉.支持外觀造型設計的進化計算方法［J］.計算機輔助設計與計算機圖形學學報，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)設計中的應用［J］.機械設計與研究，2006，22(5):88－91.

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

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

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

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

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

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