華爾天 周 猛 李生輝 鹿 浩

1.浙江工業(yè)大學(xué)機(jī)械工程學(xué)院，杭州，3100232.浙江水利水電學(xué)院，杭州，310018

0 引言

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

綜上所述，進(jìn)化設(shè)計(jì)在許多設(shè)計(jì)領(lǐng)域已有良好發(fā)展。但在機(jī)構(gòu)創(chuàng)新設(shè)計(jì)領(lǐng)域，卻還沒(méi)有相對(duì)完善的進(jìn)化設(shè)計(jì)方法。本文將進(jìn)化算法與傳統(tǒng)機(jī)構(gòu)創(chuàng)新設(shè)計(jì)方法相結(jié)合，提出了一種基于遺傳編程的機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)方法。

1 機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)的理論基礎(chǔ)

1.1 再生運(yùn)動(dòng)鏈法

傳統(tǒng)機(jī)構(gòu)創(chuàng)新設(shè)計(jì)方法中，基于類(lèi)型綜合創(chuàng)新法是根據(jù)現(xiàn)有機(jī)構(gòu)，歸納其基本的拓?fù)涮匦裕ㄟ^(guò)類(lèi)型綜合方法得到滿足基本拓?fù)涮匦缘乃羞\(yùn)動(dòng)鏈鏈型，最后確定可行的鏈型并進(jìn)行合理變換，得到滿足設(shè)計(jì)要求的新機(jī)構(gòu)。顏鴻森[12]對(duì)該方法進(jìn)行深入研究后，提出了一種新的創(chuàng)新設(shè)計(jì)方法——再生運(yùn)動(dòng)鏈法。該方法是在類(lèi)型綜合創(chuàng)新法的基礎(chǔ)上，提出的一種更加完備、系統(tǒng)的機(jī)構(gòu)方案創(chuàng)新設(shè)計(jì)方法，具體實(shí)現(xiàn)過(guò)程如圖1所示。

圖1 再生運(yùn)動(dòng)鏈法設(shè)計(jì)流程圖Fig.1 Design flow chart of regenerative motion chain method

近年來(lái)，諸多學(xué)者運(yùn)用再生運(yùn)動(dòng)鏈法解決了許多機(jī)構(gòu)設(shè)計(jì)問(wèn)題。宋萌萌等[13]在分析玥瑪鎖具機(jī)構(gòu)的基礎(chǔ)上，應(yīng)用再生運(yùn)動(dòng)鏈法對(duì)鎖芯機(jī)構(gòu)進(jìn)行設(shè)計(jì)，得到新的鎖芯機(jī)構(gòu)方案簡(jiǎn)圖；王強(qiáng)等[14]應(yīng)用再生運(yùn)動(dòng)鏈法對(duì)現(xiàn)有的一種內(nèi)螺紋加工裝置進(jìn)行機(jī)構(gòu)創(chuàng)新設(shè)計(jì)，將可行解進(jìn)行機(jī)構(gòu)拓?fù)涮匦苑治雠c比較，篩選符合要求的可行運(yùn)動(dòng)鏈。機(jī)構(gòu)再生運(yùn)動(dòng)鏈法逐漸成為機(jī)構(gòu)創(chuàng)新設(shè)計(jì)的一種指導(dǎo)方法。但該方法也存在著自身局限性，數(shù)綜合方法[15]設(shè)計(jì)的新機(jī)構(gòu)與原機(jī)構(gòu)必須具有相同構(gòu)件數(shù)和運(yùn)動(dòng)副數(shù)，無(wú)法得出能夠?qū)崿F(xiàn)相同功能的不同構(gòu)件數(shù)和運(yùn)動(dòng)副數(shù)組合，限制了可行解的范圍，導(dǎo)致具有不同構(gòu)件數(shù)和運(yùn)動(dòng)副數(shù)的可行解被遺漏，不能保證新機(jī)構(gòu)為滿足設(shè)計(jì)要求的最優(yōu)解；同時(shí)，當(dāng)構(gòu)件和運(yùn)動(dòng)副數(shù)量較大時(shí)，運(yùn)用數(shù)綜合方法得出的桿件組合較多，但滿足設(shè)計(jì)要求的解僅有一小部分，工作量較大、效率低。

1.2 遺傳編程

進(jìn)化設(shè)計(jì)的核心是進(jìn)化算法。遺傳編程[16]是進(jìn)化算法的一個(gè)分支，1992年由Koza提出并進(jìn)行深入的研究。遺傳編程的基本思想是：隨機(jī)產(chǎn)生可行解的初始種群，構(gòu)成該種群的個(gè)體都有一定的適應(yīng)度，依據(jù)適者生存的原則對(duì)高適應(yīng)度值個(gè)體進(jìn)行遺傳操作，產(chǎn)生新可行解形成下一代種群；循環(huán)該過(guò)程即可在某一代出現(xiàn)最優(yōu)解。具體過(guò)程如圖2所示。

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

遺傳編程與一般遺傳算法的主要區(qū)別在于：遺傳編程的解為樹(shù)狀結(jié)構(gòu)，而遺傳算法的解為固定長(zhǎng)度的字符串。兩者相比，前者具有若干優(yōu)勢(shì)，包括：不需要預(yù)先給定問(wèn)題解的結(jié)構(gòu)形式、不定長(zhǎng)的樹(shù)狀結(jié)構(gòu)編碼可以靈活表示各類(lèi)問(wèn)題對(duì)象、編碼結(jié)構(gòu)可以攜帶語(yǔ)義信息等。因此，遺傳編程能夠完成層次化問(wèn)題的描述，不必像其他進(jìn)化算法必須通過(guò)編碼預(yù)先定義解空間，適合處理開(kāi)放解的創(chuàng)新設(shè)計(jì)問(wèn)題。

2 設(shè)計(jì)模型的建立

2.1 機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)流程圖

在智能設(shè)計(jì)的大環(huán)境下，現(xiàn)階段設(shè)計(jì)方法按照設(shè)計(jì)能力大致可分為三類(lèi)：常規(guī)設(shè)計(jì)、聯(lián)想設(shè)計(jì)和進(jìn)化設(shè)計(jì)[17]。本文提出機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)方法的導(dǎo)圖見(jiàn)圖3。

圖3 機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)導(dǎo)圖Fig.3 Evolutionary design map of mechanism kinematics chain

基于遺傳編程的機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)，首先將原機(jī)構(gòu)一般化得到一般化運(yùn)動(dòng)鏈，接著將一般化運(yùn)動(dòng)鏈用遺傳編程個(gè)體樹(shù)表達(dá)，然后通過(guò)遺傳編程替代數(shù)綜合方法生成滿足設(shè)計(jì)要求的最優(yōu)解，最后將最優(yōu)解進(jìn)行具體化操作，流程如圖4所示。

圖4 機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)流程圖Fig.4 Flow chart of mechanism kinematics chain evolutionary design

運(yùn)用上述設(shè)計(jì)流程解決問(wèn)題時(shí)，需要注意：①編碼解碼方式；②初始群體的生成；③適應(yīng)度函數(shù)的設(shè)計(jì)；④選擇策略與遺傳操作；⑤終止準(zhǔn)則與相關(guān)控制參數(shù)的設(shè)定。

2.2 機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)數(shù)學(xué)模型

根據(jù)圖4所示的設(shè)計(jì)流程對(duì)目標(biāo)機(jī)構(gòu)進(jìn)行運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)，需要根據(jù)設(shè)計(jì)要求與約束，在一般化鏈中分配特定類(lèi)型的構(gòu)件和連接。通過(guò)分析設(shè)計(jì)要求和約束，能夠確定可行解的類(lèi)型，對(duì)初始種群的生成設(shè)定規(guī)則，提高創(chuàng)新設(shè)計(jì)的效率。機(jī)構(gòu)運(yùn)動(dòng)鏈的設(shè)計(jì)要求與約束主要包括桿件數(shù)和運(yùn)動(dòng)副數(shù)，以及桿件間的附隨關(guān)系。本文結(jié)合機(jī)構(gòu)設(shè)計(jì)理論對(duì)桿件數(shù)和運(yùn)動(dòng)副數(shù)的約束進(jìn)行分析，將該約束通過(guò)數(shù)學(xué)方程組的方式表達(dá)；同時(shí)，結(jié)合圖論對(duì)模型表達(dá)方式以及機(jī)構(gòu)創(chuàng)新設(shè)計(jì)中對(duì)圖論的應(yīng)用經(jīng)驗(yàn)，使用鄰接矩陣來(lái)表達(dá)桿件間的附隨關(guān)系。

對(duì)于一個(gè)合理機(jī)構(gòu)來(lái)說(shuō)，除去機(jī)架外，必然包括一個(gè)或多個(gè)必備構(gòu)件和非必備構(gòu)件，其中必備構(gòu)件必須存在，而非必備構(gòu)件可以被其他相似類(lèi)型的構(gòu)件取代。結(jié)合設(shè)計(jì)要求與約束，分析運(yùn)動(dòng)鏈中的必備構(gòu)件個(gè)數(shù)，確定必備構(gòu)件的運(yùn)動(dòng)副數(shù)，保證通過(guò)該進(jìn)化設(shè)計(jì)得到的新機(jī)構(gòu)滿足原機(jī)構(gòu)的功能特性，并通過(guò)數(shù)學(xué)式表達(dá)。

結(jié)合圖論的知識(shí)，將一般化運(yùn)動(dòng)鏈轉(zhuǎn)化為拓?fù)鋱D，以頂點(diǎn)表示機(jī)構(gòu)運(yùn)動(dòng)鏈的構(gòu)件，以邊表示機(jī)構(gòu)運(yùn)動(dòng)鏈的運(yùn)動(dòng)副，并定義如下鄰接矩陣A：該矩陣A的行和列均由V(G)進(jìn)行索引，當(dāng)i≠j時(shí)，若頂點(diǎn)vi和vj不相鄰，則A的元素(i，j)取值為0；反之，若頂點(diǎn)vi和vj相鄰，則A的元素(i，j)取值為1。當(dāng)i=j時(shí)，即A的對(duì)角線上元素(i，i)均為構(gòu)件(頂點(diǎn))vi的運(yùn)動(dòng)副數(shù)。

例如：1個(gè)單自由度6桿7副運(yùn)動(dòng)鏈，其中包含必備構(gòu)件5個(gè)，必備構(gòu)件中要求有2個(gè)為三副桿或三副以上的構(gòu)件，且必備構(gòu)件1和必備構(gòu)件2相關(guān)聯(lián)，必備構(gòu)件3和必備構(gòu)件4相關(guān)聯(lián)，必備構(gòu)件1與必備構(gòu)件5必定不關(guān)聯(lián)。設(shè)nt為構(gòu)件總數(shù)，n1為二副桿數(shù)，n2為三副桿數(shù)，n3為四副桿數(shù)，pt為總運(yùn)動(dòng)副數(shù)，F(xiàn)為自由度數(shù)，綜合所給約束可得：

(1)

(2)

式中，a為必備構(gòu)件數(shù)，a=5；b為原運(yùn)動(dòng)鏈構(gòu)件總數(shù)，b=6；c為設(shè)計(jì)要求中必備構(gòu)件的最小多副桿總數(shù)，c=2；F取值為1；nt、n1、n2、n3、pt均為非負(fù)整數(shù)；xij均為非負(fù)整數(shù)，x12=x34=1，x15=0。

3 機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)

3.1 編碼解碼方式

編碼是信息從一種形式轉(zhuǎn)換為另一種形式的過(guò)程，解碼是編碼的逆過(guò)程。在對(duì)機(jī)構(gòu)構(gòu)件進(jìn)行編碼時(shí)，使用編號(hào)對(duì)應(yīng)各類(lèi)桿件，以便計(jì)算機(jī)錄入數(shù)據(jù)。同時(shí)，還需要考慮各類(lèi)桿件的運(yùn)動(dòng)副數(shù)，因此采用結(jié)構(gòu)體變量根據(jù)構(gòu)件的運(yùn)動(dòng)副數(shù)定義各類(lèi)桿件，構(gòu)件結(jié)構(gòu)體中包含運(yùn)動(dòng)副數(shù)量信息，具體如表1所示。

表1 桿件編碼信息

Tab.1 Member coding information

序號(hào)桿件編碼信息Ⅰ2Ⅱ3Ⅲ4???Ni

3.2 一般化過(guò)程

再生運(yùn)動(dòng)鏈法中一般化是將含有不同類(lèi)型構(gòu)件與運(yùn)動(dòng)副的原機(jī)構(gòu)，轉(zhuǎn)化為只含連桿和轉(zhuǎn)動(dòng)副的一般化運(yùn)動(dòng)鏈。機(jī)構(gòu)的一般化需要遵循一般化原則，一般化原則包括：①非剛性構(gòu)件一般化為剛性構(gòu)件；②非連桿形狀的構(gòu)件一般化為連桿；③高副一般化為低副；④非轉(zhuǎn)動(dòng)副一般化為轉(zhuǎn)動(dòng)副；⑤解除固定桿的約束；⑥原機(jī)構(gòu)與其所對(duì)應(yīng)的一般化機(jī)構(gòu)，其自由度數(shù)應(yīng)保持不變。

現(xiàn)以飛機(jī)鼻輪起落架收放機(jī)構(gòu)為例，對(duì)一般化過(guò)程和初始化種群進(jìn)行說(shuō)明，其機(jī)構(gòu)簡(jiǎn)圖見(jiàn)圖5。該機(jī)構(gòu)是一個(gè)8桿10副單自由度平面機(jī)構(gòu)，其中連接g為移動(dòng)副，p、q為復(fù)合鉸鏈。

圖5 飛機(jī)鼻輪起落架收放機(jī)構(gòu)簡(jiǎn)圖Fig.5 Schematic diagram of aircraft nose wheel landing gear operating mechanism

根據(jù)一般化原則，對(duì)該機(jī)構(gòu)進(jìn)行一般化。具體過(guò)程如下：①將機(jī)架(構(gòu)件1)一般化為三副桿1；②將連接g一般化為轉(zhuǎn)動(dòng)副。經(jīng)過(guò)轉(zhuǎn)化后得到圖6所示的一般化鏈。

圖6 一般化運(yùn)動(dòng)鏈Fig.6 Generalized kinematic chain

3.3 初始化種群

初始群體由眾多初始個(gè)體組成，初始個(gè)體為所要解決問(wèn)題的各種可能個(gè)體樹(shù)，它通過(guò)隨機(jī)方法產(chǎn)生。針對(duì)圖6中的一般化運(yùn)動(dòng)鏈，通過(guò)整理各零件的運(yùn)動(dòng)副數(shù)得到對(duì)應(yīng)該一般化運(yùn)動(dòng)鏈的各構(gòu)件屬性表，如表2所示。

表2 各構(gòu)件屬性表

為方便遺傳編程個(gè)體的表達(dá)，選擇某個(gè)確定的必備構(gòu)件作為個(gè)體的根，通過(guò)該方法可將圖6所示的一般化運(yùn)動(dòng)鏈表示為樹(shù)狀結(jié)構(gòu)。其中構(gòu)件2為必備構(gòu)件，用于連接機(jī)架1與固定鼻輪，選取構(gòu)件2為個(gè)體的根。采用層序遍歷的方式來(lái)表達(dá)個(gè)體樹(shù)，最終得到如圖7所示的樹(shù)。

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

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

3.4 適應(yīng)度評(píng)價(jià)函數(shù)

遺傳編程適應(yīng)度評(píng)價(jià)函數(shù)的好壞，直接影響遺傳編程所得最佳個(gè)體的優(yōu)劣。根據(jù)實(shí)際生產(chǎn)需求可選擇不同的評(píng)價(jià)因子，本文主要以構(gòu)件總數(shù)和多副桿數(shù)作為衡量指標(biāo)來(lái)建立適應(yīng)度函數(shù)。

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

通過(guò)上述對(duì)構(gòu)件總數(shù)和多副桿數(shù)的分析，對(duì)各評(píng)價(jià)指標(biāo)進(jìn)行加權(quán)，確定目標(biāo)函數(shù)：

(3)

式中，f1為構(gòu)件總數(shù)；f2為多副桿數(shù)(包括三副桿、四副桿等)，f2+1是為了防止存在f2值為0的情況，即多副桿個(gè)數(shù)為0；w1和w2分別為f1和f2的權(quán)重；a為調(diào)節(jié)系數(shù)。

3.5 選擇策略

遺傳編程中，個(gè)體被選擇進(jìn)行遺傳操作的機(jī)會(huì)取決于其適應(yīng)度值的大小，選擇策略影響個(gè)體進(jìn)化的速度和趨勢(shì)。因此，個(gè)體過(guò)早收斂等問(wèn)題的主要因素往往是由于選擇策略的不當(dāng)導(dǎo)致。

結(jié)合機(jī)構(gòu)創(chuàng)新設(shè)計(jì)的特點(diǎn)，本文采用錦標(biāo)賽選擇法，錦標(biāo)賽選擇法的特點(diǎn)在于其以個(gè)體適應(yīng)度的相對(duì)值為選擇標(biāo)準(zhǔn)，能夠有效地避免群體中個(gè)別或極少數(shù)特殊個(gè)體的影響，防止進(jìn)化過(guò)程中發(fā)生早熟現(xiàn)象。

3.6 遺傳操作

復(fù)制、交叉和變異是遺傳編程的三種主要遺傳操作。根據(jù)機(jī)構(gòu)創(chuàng)新設(shè)計(jì)的特點(diǎn)以及實(shí)際設(shè)計(jì)過(guò)程中可能存在的問(wèn)題，本文對(duì)遺傳操作進(jìn)行了改進(jìn)。

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

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

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

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

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

3.7 終止準(zhǔn)則及算法相關(guān)參數(shù)設(shè)定

遺傳編程并行計(jì)算的本質(zhì)在于：在適應(yīng)度評(píng)價(jià)指標(biāo)的驅(qū)動(dòng)下，種群不斷地適應(yīng)環(huán)境的變化，向著對(duì)環(huán)境適應(yīng)性更好的方向發(fā)展，若使算法停止則需給出終止準(zhǔn)則。一般而言，常見(jiàn)的幾種終止準(zhǔn)則包括：達(dá)到最大進(jìn)化代數(shù)或最大計(jì)算次數(shù)；經(jīng)過(guò)n代后個(gè)體適應(yīng)度值沒(méi)有得到改善；得到滿足問(wèn)題預(yù)先設(shè)定解。

由于本文經(jīng)過(guò)遺傳操作得到的個(gè)體有些可能不符合設(shè)計(jì)要求與約束，因此采用預(yù)設(shè)最大進(jìn)化代數(shù)為終止條件。

綜上所述，該機(jī)構(gòu)運(yùn)動(dòng)鏈創(chuàng)新設(shè)計(jì)進(jìn)化方法需要設(shè)定的相關(guān)參數(shù)包括種群規(guī)模N、交叉率α、變異率β、進(jìn)化代數(shù)n。

4 應(yīng)用實(shí)例及結(jié)果分析

4.1 對(duì)比分析

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

整理以上設(shè)計(jì)要求和約束并給定相關(guān)信息：①機(jī)構(gòu)的構(gòu)件數(shù)量可變動(dòng)范圍為6～8；②多副桿數(shù)量不小于3。

使用再生運(yùn)動(dòng)鏈法進(jìn)行設(shè)計(jì)時(shí)，考慮6桿和7桿的可能情況，做出如下分析：

(1)6桿單自由度：

F=3(nt-1)-2pt

(4)

通過(guò)式(4)計(jì)算得6桿單自由度時(shí)pt=7。綜合構(gòu)件總數(shù)和總運(yùn)動(dòng)副數(shù)得到6桿7副單自由度的所有可能桿件組合，如表3所示。

表3 桿件組合表

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

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

使用本文提出的機(jī)構(gòu)運(yùn)動(dòng)鏈進(jìn)化設(shè)計(jì)方法進(jìn)行設(shè)計(jì)時(shí)，將設(shè)計(jì)要求中的各參數(shù)代入式(1)與式(2)，可得

(5)

(6)

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

設(shè)定相關(guān)參數(shù)：種群大小為100，交叉概率為0.5，變異概率為0.3，進(jìn)化代數(shù)設(shè)為20。

適應(yīng)度函數(shù)根據(jù)式(3)，綜合考慮所選評(píng)價(jià)因子(桿件總數(shù)和多副桿數(shù))之間的權(quán)重比例，確保兩個(gè)評(píng)價(jià)因子權(quán)重的平衡性，通過(guò)多組數(shù)據(jù)的計(jì)算，確定該組數(shù)據(jù)為最佳數(shù)據(jù)，式中各參數(shù)取值：a=1.5，w1=8，w2=1。

選取必備構(gòu)件鑰匙為個(gè)體樹(shù)的根，結(jié)合設(shè)計(jì)要求，最終得到最佳個(gè)體如圖10所示。個(gè)體樹(shù)中各結(jié)點(diǎn)的信息整理如表4所示。

圖10 鎖芯機(jī)構(gòu)最佳個(gè)體樹(shù)Fig.10 Optimal individual of locking mechanism

構(gòu)件號(hào)運(yùn)動(dòng)副數(shù)構(gòu)件號(hào)運(yùn)動(dòng)副數(shù)1224324352627283

最終，結(jié)合設(shè)計(jì)要求和約束以及表4中的信息，可將圖10的最佳個(gè)體樹(shù)轉(zhuǎn)化為圖11中的一般化鏈。該結(jié)果與文獻(xiàn)[13]中通過(guò)再生運(yùn)動(dòng)鏈法設(shè)計(jì)的結(jié)果相同。

圖11 鎖芯機(jī)構(gòu)最佳個(gè)體一般化鏈Fig.11 The generalized kinematic chain of optimal individual of locking mechanism

4.2 案例應(yīng)用

下面以一種玻璃模具開(kāi)合機(jī)構(gòu)為例，利用本文方法進(jìn)行創(chuàng)新設(shè)計(jì)。該玻璃模具開(kāi)合機(jī)構(gòu)簡(jiǎn)圖見(jiàn)圖12，它是一個(gè)12桿16副單自由度機(jī)構(gòu)，由驅(qū)動(dòng)件液壓缸和各桿件的相互作用，實(shí)現(xiàn)模具的開(kāi)合動(dòng)作。

圖12 玻璃模具開(kāi)合機(jī)構(gòu)簡(jiǎn)圖Fig.12 A schematic diagram of retractable mechanism of glass mold

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

(7)

(8)

式中，x11為不小于3的正整數(shù)。

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

圖13 開(kāi)合機(jī)構(gòu)最佳個(gè)體樹(shù)Fig.13 Optimal individual of retractable mechanism

結(jié)合設(shè)計(jì)要求和約束以及表1中的信息，可將圖13的最佳個(gè)體樹(shù)轉(zhuǎn)化為圖14中的一般化鏈。并將該一般化鏈結(jié)合設(shè)計(jì)要求經(jīng)過(guò)具體化規(guī)則，得到圖15所示8桿10副單自由度的新機(jī)構(gòu)。實(shí)踐證明，新機(jī)構(gòu)為符合設(shè)計(jì)要求的可行解，同時(shí)新機(jī)構(gòu)與原機(jī)構(gòu)相比，總桿數(shù)由12減少至8，總運(yùn)動(dòng)副數(shù)由16減少至10。

圖14 開(kāi)合機(jī)構(gòu)最佳個(gè)體一般化鏈Fig.14 The generalized kinematic chain of optimal individual of retractable mechanism

圖15 新機(jī)構(gòu)具體化簡(jiǎn)圖Fig.15 Schematic diagram of the materialization of new mechanism

對(duì)比分析新機(jī)構(gòu)和原機(jī)構(gòu)的運(yùn)動(dòng)特性可得：新機(jī)構(gòu)上模具與機(jī)架焊接，通過(guò)液壓缸的驅(qū)動(dòng)和各桿件的相互作用，帶動(dòng)下模具轉(zhuǎn)動(dòng)，從而實(shí)現(xiàn)模具的開(kāi)合動(dòng)作。通過(guò)這一案例驗(yàn)證了新機(jī)構(gòu)和原機(jī)構(gòu)具有相同的功能和效果。

5 結(jié)論

(1)采用遺傳編程替代數(shù)綜合方法，在保證新機(jī)構(gòu)滿足原機(jī)構(gòu)功能特性的條件下，實(shí)現(xiàn)新機(jī)構(gòu)與原機(jī)構(gòu)不同構(gòu)件數(shù)和運(yùn)動(dòng)副數(shù)的進(jìn)化設(shè)計(jì)。

(2)結(jié)合線性代數(shù)和圖論的內(nèi)容，將可行解的桿件和運(yùn)動(dòng)副數(shù)組合與桿件間的附隨關(guān)系分別通過(guò)不等式方程組和拓?fù)溧徑泳仃嚨姆绞奖磉_(dá)，結(jié)合兩種約束形式，建立具有通用性的數(shù)學(xué)模型。

(3)結(jié)合實(shí)際問(wèn)題對(duì)進(jìn)化算法進(jìn)行優(yōu)化改進(jìn)，分別設(shè)計(jì)了合適的編碼解碼方式、適應(yīng)度評(píng)價(jià)函數(shù)以及合理的遺傳操作，確保整個(gè)方法流程的合理運(yùn)行。

(4)本文的研究為機(jī)構(gòu)運(yùn)動(dòng)進(jìn)化設(shè)計(jì)提供了一種可行的方案，但仍存在一些問(wèn)題有待研究。例如，可根據(jù)生產(chǎn)實(shí)際的需求，對(duì)適應(yīng)度評(píng)價(jià)函數(shù)進(jìn)行改進(jìn)，考慮增加更實(shí)際的適應(yīng)度評(píng)價(jià)因子，使設(shè)計(jì)的最佳個(gè)體品質(zhì)更優(yōu)良，以及本文提出的方法是否適用于所有的機(jī)構(gòu)創(chuàng)新設(shè)計(jì)還有待進(jìn)一步驗(yàn)證。