遺傳編程的機構運動鏈進化設計

華爾天 周 猛 李生輝 鹿 浩

1.浙江工業大學機械工程學院，杭州，3100232.浙江水利水電學院，杭州，310018

0 引言

智能設計正處于由常規設計、聯想設計向進化設計突破的關鍵階段，傳統機構創新設計方法已經不能滿足智能設計的發展要求。進化設計是由進化思想指導的設計方法，優良樣本的交叉、變異是設計創新的源泉，其優勢在于對環境知識依賴較少，在創新求解問題上有很大的發展空間。已有很多進化設計方法應用在各個設計領域和設計階段。馮毅雄等[1-2]提出零件結構進化模型重構的聯動式進化算法，實現對零件結構進化模型的動態編輯；將基于語義單元的創新進化設計理論應用于實際產品開發中，取得良好的效果。章安良等[3-6]將進化設計應用到聲表面波技術領域中，針對聲表面波濾波器、抽指加權叉指和電容加權叉指換能器等設計過程進行改進，均取得了良好的效果。隨著國內外學者對進化設計的深入研究，針對不同的應用領域，對進化設計做出相應的改進。針對進化設計方法在設計理論上的不足，李洪杰等[7]提出基于功能構造的基因模型的框架結構，實現產品的自底向上的適應性設計方式；任尊茂等[8]提出基于單層進化的產品客戶化設計方法，通過適應度函數的評價，使進化后的設計方案滿足客戶的定制需求；針對當前基于幾何約束關系的CAD系統不能很好地解決面向方案設計的機構運動模型表示問題，程錦等[9]提出一種新的基于功能語義的運動進化建模方法，為機構運動進化設計過程的自動求解提供有效手段；王吉華等[10]為提高零件進化設計的效率，提出一種基于特征幾何體應用程序接口函數的零件基因組模型，并取得良好的效果；針對進化設計中生成解的不可預測性，趙婷婷等[11]提出一種改進的遺傳算法——蔓延遺傳算法，通過適應度選擇生成解并且自動對形狀進行可視化。

綜上所述，進化設計在許多設計領域已有良好發展。但在機構創新設計領域，卻還沒有相對完善的進化設計方法。本文將進化算法與傳統機構創新設計方法相結合，提出了一種基于遺傳編程的機構運動鏈進化設計方法。

1 機構運動鏈進化設計的理論基礎

1.1 再生運動鏈法

傳統機構創新設計方法中，基于類型綜合創新法是根據現有機構，歸納其基本的拓撲特性，通過類型綜合方法得到滿足基本拓撲特性的所有運動鏈鏈型，最后確定可行的鏈型并進行合理變換，得到滿足設計要求的新機構。顏鴻森[12]對該方法進行深入研究后，提出了一種新的創新設計方法——再生運動鏈法。該方法是在類型綜合創新法的基礎上，提出的一種更加完備、系統的機構方案創新設計方法，具體實現過程如圖1所示。

圖1 再生運動鏈法設計流程圖Fig.1 Design flow chart of regenerative motion chain method

近年來，諸多學者運用再生運動鏈法解決了許多機構設計問題。宋萌萌等[13]在分析玥瑪鎖具機構的基礎上，應用再生運動鏈法對鎖芯機構進行設計，得到新的鎖芯機構方案簡圖；王強等[14]應用再生運動鏈法對現有的一種內螺紋加工裝置進行機構創新設計，將可行解進行機構拓撲特性分析與比較，篩選符合要求的可行運動鏈。機構再生運動鏈法逐漸成為機構創新設計的一種指導方法。但該方法也存在著自身局限性，數綜合方法[15]設計的新機構與原機構必須具有相同構件數和運動副數，無法得出能夠實現相同功能的不同構件數和運動副數組合，限制了可行解的范圍，導致具有不同構件數和運動副數的可行解被遺漏，不能保證新機構為滿足設計要求的最優解；同時，當構件和運動副數量較大時，運用數綜合方法得出的桿件組合較多，但滿足設計要求的解僅有一小部分，工作量較大、效率低。

1.2 遺傳編程

進化設計的核心是進化算法。遺傳編程[16]是進化算法的一個分支，1992年由Koza提出并進行深入的研究。遺傳編程的基本思想是：隨機產生可行解的初始種群，構成該種群的個體都有一定的適應度，依據適者生存的原則對高適應度值個體進行遺傳操作，產生新可行解形成下一代種群；循環該過程即可在某一代出現最優解。具體過程如圖2所示。

圖2 遺傳編程流程圖Fig.2 Flow chart of genetic programming

遺傳編程與一般遺傳算法的主要區別在于：遺傳編程的解為樹狀結構，而遺傳算法的解為固定長度的字符串。兩者相比，前者具有若干優勢，包括：不需要預先給定問題解的結構形式、不定長的樹狀結構編碼可以靈活表示各類問題對象、編碼結構可以攜帶語義信息等。因此，遺傳編程能夠完成層次化問題的描述，不必像其他進化算法必須通過編碼預先定義解空間，適合處理開放解的創新設計問題。

2 設計模型的建立

2.1 機構運動鏈進化設計流程圖

在智能設計的大環境下，現階段設計方法按照設計能力大致可分為三類：常規設計、聯想設計和進化設計[17]。本文提出機構運動鏈進化設計方法的導圖見圖3。

圖3 機構運動鏈進化設計導圖Fig.3 Evolutionary design map of mechanism kinematics chain

基于遺傳編程的機構運動鏈進化設計，首先將原機構一般化得到一般化運動鏈，接著將一般化運動鏈用遺傳編程個體樹表達，然后通過遺傳編程替代數綜合方法生成滿足設計要求的最優解，最后將最優解進行具體化操作，流程如圖4所示。

圖4 機構運動鏈進化設計流程圖Fig.4 Flow chart of mechanism kinematics chain evolutionary design

運用上述設計流程解決問題時，需要注意：①編碼解碼方式；②初始群體的生成；③適應度函數的設計；④選擇策略與遺傳操作；⑤終止準則與相關控制參數的設定。

2.2 機構運動鏈進化設計數學模型

根據圖4所示的設計流程對目標機構進行運動鏈進化設計，需要根據設計要求與約束，在一般化鏈中分配特定類型的構件和連接。通過分析設計要求和約束，能夠確定可行解的類型，對初始種群的生成設定規則，提高創新設計的效率。機構運動鏈的設計要求與約束主要包括桿件數和運動副數，以及桿件間的附隨關系。本文結合機構設計理論對桿件數和運動副數的約束進行分析，將該約束通過數學方程組的方式表達；同時，結合圖論對模型表達方式以及機構創新設計中對圖論的應用經驗，使用鄰接矩陣來表達桿件間的附隨關系。

對于一個合理機構來說，除去機架外，必然包括一個或多個必備構件和非必備構件，其中必備構件必須存在，而非必備構件可以被其他相似類型的構件取代。結合設計要求與約束，分析運動鏈中的必備構件個數，確定必備構件的運動副數，保證通過該進化設計得到的新機構滿足原機構的功能特性，并通過數學式表達。

結合圖論的知識，將一般化運動鏈轉化為拓撲圖，以頂點表示機構運動鏈的構件，以邊表示機構運動鏈的運動副，并定義如下鄰接矩陣A：該矩陣A的行和列均由V(G)進行索引，當i≠j時，若頂點vi和vj不相鄰，則A的元素(i，j)取值為0；反之，若頂點vi和vj相鄰，則A的元素(i，j)取值為1。當i=j時，即A的對角線上元素(i，i)均為構件(頂點)vi的運動副數。

例如：1個單自由度6桿7副運動鏈，其中包含必備構件5個，必備構件中要求有2個為三副桿或三副以上的構件，且必備構件1和必備構件2相關聯，必備構件3和必備構件4相關聯，必備構件1與必備構件5必定不關聯。設nt為構件總數，n1為二副桿數，n2為三副桿數，n3為四副桿數，pt為總運動副數，F為自由度數，綜合所給約束可得：

(1)

(2)

式中，a為必備構件數，a=5；b為原運動鏈構件總數，b=6；c為設計要求中必備構件的最小多副桿總數，c=2；F取值為1；nt、n1、n2、n3、pt均為非負整數；xij均為非負整數，x12=x34=1，x15=0。

3 機構運動鏈進化設計

3.1 編碼解碼方式

編碼是信息從一種形式轉換為另一種形式的過程，解碼是編碼的逆過程。在對機構構件進行編碼時，使用編號對應各類桿件，以便計算機錄入數據。同時，還需要考慮各類桿件的運動副數，因此采用結構體變量根據構件的運動副數定義各類桿件，構件結構體中包含運動副數量信息，具體如表1所示。

表1 桿件編碼信息

Tab.1 Member coding information

序號桿件編碼信息Ⅰ2Ⅱ3Ⅲ4???Ni

3.2 一般化過程

再生運動鏈法中一般化是將含有不同類型構件與運動副的原機構，轉化為只含連桿和轉動副的一般化運動鏈。機構的一般化需要遵循一般化原則，一般化原則包括：①非剛性構件一般化為剛性構件；②非連桿形狀的構件一般化為連桿；③高副一般化為低副；④非轉動副一般化為轉動副；⑤解除固定桿的約束；⑥原機構與其所對應的一般化機構，其自由度數應保持不變。

現以飛機鼻輪起落架收放機構為例，對一般化過程和初始化種群進行說明，其機構簡圖見圖5。該機構是一個8桿10副單自由度平面機構，其中連接g為移動副，p、q為復合鉸鏈。

圖5 飛機鼻輪起落架收放機構簡圖Fig.5 Schematic diagram of aircraft nose wheel landing gear operating mechanism

根據一般化原則，對該機構進行一般化。具體過程如下：①將機架(構件1)一般化為三副桿1；②將連接g一般化為轉動副。經過轉化后得到圖6所示的一般化鏈。

圖6 一般化運動鏈Fig.6 Generalized kinematic chain

3.3 初始化種群

初始群體由眾多初始個體組成，初始個體為所要解決問題的各種可能個體樹，它通過隨機方法產生。針對圖6中的一般化運動鏈，通過整理各零件的運動副數得到對應該一般化運動鏈的各構件屬性表，如表2所示。

表2 各構件屬性表

為方便遺傳編程個體的表達，選擇某個確定的必備構件作為個體的根，通過該方法可將圖6所示的一般化運動鏈表示為樹狀結構。其中構件2為必備構件，用于連接機架1與固定鼻輪，選取構件2為個體的根。采用層序遍歷的方式來表達個體樹，最終得到如圖7所示的樹。

圖7 遺傳編程樹狀解Fig.7 Tree solution of genetic programming

分析該飛機鼻輪起落架收放機構的設計要求和約束，總結出該機構的必備構件數量以及必備多副桿數量，以確定可行解的構件數量和多副桿個數可變動范圍，將滿足式(1)中各條件的可行解按照事先參數設定的群體數生成相應數量的個體，即完成了遺傳編程的初始化過程。

3.4 適應度評價函數

遺傳編程適應度評價函數的好壞，直接影響遺傳編程所得最佳個體的優劣。根據實際生產需求可選擇不同的評價因子，本文主要以構件總數和多副桿數作為衡量指標來建立適應度函數。

公理設計包括獨立、信息兩大公理[18]，其中，信息公理指出：在所有滿足獨立性公理的設計中，信息含量最少的設計是最好的設計。因此，設計得到的機構應在滿足設計要求的前提下盡可能減少構件總數，使得機構整體信息量最小化；同時，多副桿相對于二副桿而言，其包含的信息量較大。本文根據信息公理的要求，期望得到具有較小構件總數和較小多副桿數的可行解。

通過上述對構件總數和多副桿數的分析，對各評價指標進行加權，確定目標函數：

(3)

式中，f1為構件總數；f2為多副桿數(包括三副桿、四副桿等)，f2+1是為了防止存在f2值為0的情況，即多副桿個數為0；w1和w2分別為f1和f2的權重；a為調節系數。

3.5 選擇策略

遺傳編程中，個體被選擇進行遺傳操作的機會取決于其適應度值的大小，選擇策略影響個體進化的速度和趨勢。因此，個體過早收斂等問題的主要因素往往是由于選擇策略的不當導致。

結合機構創新設計的特點，本文采用錦標賽選擇法，錦標賽選擇法的特點在于其以個體適應度的相對值為選擇標準，能夠有效地避免群體中個別或極少數特殊個體的影響，防止進化過程中發生早熟現象。

3.6 遺傳操作

復制、交叉和變異是遺傳編程的三種主要遺傳操作。根據機構創新設計的特點以及實際設計過程中可能存在的問題，本文對遺傳操作進行了改進。

(1)復制操作。從當前群體中，以適應度值的大小為指標，從種群中隨機選擇一個適應度值較大的個體作為親代個體，該個體不經任何變化完整地復制到下一代群體中，具體步驟：①根據預先設定的概率隨機選取群體中的個體Xi；②復制Xi得到X′i；③將個體X′i直接作為子代個體并保留。

(2)交叉操作。從當前群體中，以適應度值的大小為指標，從種群中隨機選擇兩個適應度值較大的個體作為親代個體，兩個父代個體的不同部分重新組合產生新的子代個體，具體步驟：①隨機選出兩個個體Xi和Xj；②對Xi和Xj分別復制得到X′i和X′j；③對X′i和X′j分別隨機選取交叉點，然后X′i和X′j交換交叉點的子樹得到Yi和Yj；④若子代生成的個體為可行解則保留Yi和Yj，同時標記父代個體Xi和Xj已交配；若不是正確個體，則保留父代個體Xi和Xj并標記已交配；⑤檢查是否群體中的所有個體都已經交配，否則返回步驟①。具體流程如圖8所示。

圖8 交叉操作流程圖Fig.8 Flow chart of cross

(3)變異操作。從當前群體中，以適應度值的大小為指標，從種群中隨機選擇一個個體作為親代個體，該個體隨機在某一結點處發生變異形成新個體，并將得到的新個體完整地復制到下一代群體中。具體步驟：①根據預先設定的概率隨機選取群體中的個體Xi；②隨機選取個體樹上的一個結點(即突變點)，將突變點變異為另外一個適度大小的新子樹，以取代該結點以下的子樹而形成一個新的個體樹X′i；③對新生成的個體X′i進行判斷，若為可行解則保留，否則保留原有個體Xi。具體流程如圖9所示。

圖9 變異操作流程圖Fig.9 Flow chart of variation

3.7 終止準則及算法相關參數設定

遺傳編程并行計算的本質在于：在適應度評價指標的驅動下，種群不斷地適應環境的變化，向著對環境適應性更好的方向發展，若使算法停止則需給出終止準則。一般而言，常見的幾種終止準則包括：達到最大進化代數或最大計算次數；經過n代后個體適應度值沒有得到改善；得到滿足問題預先設定解。

由于本文經過遺傳操作得到的個體有些可能不符合設計要求與約束，因此采用預設最大進化代數為終止條件。

綜上所述，該機構運動鏈創新設計進化方法需要設定的相關參數包括種群規模N、交叉率α、變異率β、進化代數n。

4 應用實例及結果分析

4.1 對比分析

為驗證本文方法的有效性，以文獻[13]中的鎖芯機構創新設計為例，與再生運動鏈法進行對比分析。該文獻中將玥瑪空轉鎖芯一般化后，得到8桿10副單自由度一般化運動鏈。通過分析可歸納出該機構的設計要求與約束情況包括：①必備構件有機架、內圈桿、鑰匙、彈片、整體鍵子、凸輪副；②內圈桿為三副桿或四副桿，彈片為三副桿，整體鍵子為多副桿；③機架與內圈有附隨關系，同時機架不可能與鑰匙有附隨關系，內圈桿與葉片桿、鑰匙存在附隨關系，彈片與鑰匙存在附隨關系，整體鍵子與鎖芯后節以及彈片存在附隨關系，但與鑰匙不存在附隨關系。

整理以上設計要求和約束并給定相關信息：①機構的構件數量可變動范圍為6～8；②多副桿數量不小于3。

使用再生運動鏈法進行設計時，考慮6桿和7桿的可能情況，做出如下分析：

(1)6桿單自由度：

F=3(nt-1)-2pt

(4)

通過式(4)計算得6桿單自由度時pt=7。綜合構件總數和總運動副數得到6桿7副單自由度的所有可能桿件組合，如表3所示。

表3 桿件組合表

由于設計要求與約束中規定多副桿數量不小于3，而表3中組合均不滿足設計要求，故排除6桿單自由度的可能。

(2)7桿單自由度。通過式(4)計算得7桿單自由度時pt=8.5。由于pt為正整數，故排除7桿單自由度的可能。

使用本文提出的機構運動鏈進化設計方法進行設計時，將設計要求中的各參數代入式(1)與式(2)，可得

(5)

(6)

式中，x22取3或4，x44≥ 3，且x44為正整數。

設定相關參數：種群大小為100，交叉概率為0.5，變異概率為0.3，進化代數設為20。

適應度函數根據式(3)，綜合考慮所選評價因子(桿件總數和多副桿數)之間的權重比例，確保兩個評價因子權重的平衡性，通過多組數據的計算，確定該組數據為最佳數據，式中各參數取值：a=1.5，w1=8，w2=1。

選取必備構件鑰匙為個體樹的根，結合設計要求，最終得到最佳個體如圖10所示。個體樹中各結點的信息整理如表4所示。

圖10 鎖芯機構最佳個體樹Fig.10 Optimal individual of locking mechanism

構件號運動副數構件號運動副數1224324352627283

最終，結合設計要求和約束以及表4中的信息，可將圖10的最佳個體樹轉化為圖11中的一般化鏈。該結果與文獻[13]中通過再生運動鏈法設計的結果相同。

圖11 鎖芯機構最佳個體一般化鏈Fig.11 The generalized kinematic chain of optimal individual of locking mechanism

4.2 案例應用

下面以一種玻璃模具開合機構為例，利用本文方法進行創新設計。該玻璃模具開合機構簡圖見圖12，它是一個12桿16副單自由度機構，由驅動件液壓缸和各桿件的相互作用，實現模具的開合動作。

圖12 玻璃模具開合機構簡圖Fig.12 A schematic diagram of retractable mechanism of glass mold

首先對原機構的功能特性進行分析，確定該玻璃模具開合機構的設計要求與約束如下：①必備構件有模具、液壓缸、機架、兩個三副桿且其中一個必與機架關聯；②機架的運動副數大于等于3；③模具與液壓缸必定不附隨。將設計要求中的參數代入式(1)、式(2)，可得

(7)

(8)

式中，x11為不小于3的正整數。

接著選取必備構件液壓缸為個體樹的根，并給定相關參數：種群大小為100，交叉概率為0.5，變異概率為0.3，進化代數設為20。適應度函數根據式(3)，式中各參數取值：a=1.5，w1=8，w2=1。結合設計要求，最終得到最佳個體如圖13所示。

圖13 開合機構最佳個體樹Fig.13 Optimal individual of retractable mechanism

結合設計要求和約束以及表1中的信息，可將圖13的最佳個體樹轉化為圖14中的一般化鏈。并將該一般化鏈結合設計要求經過具體化規則，得到圖15所示8桿10副單自由度的新機構。實踐證明，新機構為符合設計要求的可行解，同時新機構與原機構相比，總桿數由12減少至8，總運動副數由16減少至10。

圖14 開合機構最佳個體一般化鏈Fig.14 The generalized kinematic chain of optimal individual of retractable mechanism

圖15 新機構具體化簡圖Fig.15 Schematic diagram of the materialization of new mechanism

對比分析新機構和原機構的運動特性可得：新機構上模具與機架焊接，通過液壓缸的驅動和各桿件的相互作用，帶動下模具轉動，從而實現模具的開合動作。通過這一案例驗證了新機構和原機構具有相同的功能和效果。

5 結論

(1)采用遺傳編程替代數綜合方法，在保證新機構滿足原機構功能特性的條件下，實現新機構與原機構不同構件數和運動副數的進化設計。

(2)結合線性代數和圖論的內容，將可行解的桿件和運動副數組合與桿件間的附隨關系分別通過不等式方程組和拓撲鄰接矩陣的方式表達，結合兩種約束形式，建立具有通用性的數學模型。

(3)結合實際問題對進化算法進行優化改進，分別設計了合適的編碼解碼方式、適應度評價函數以及合理的遺傳操作，確保整個方法流程的合理運行。

(4)本文的研究為機構運動進化設計提供了一種可行的方案，但仍存在一些問題有待研究。例如，可根據生產實際的需求，對適應度評價函數進行改進，考慮增加更實際的適應度評價因子，使設計的最佳個體品質更優良，以及本文提出的方法是否適用于所有的機構創新設計還有待進一步驗證。