一種基于復(fù)雜網(wǎng)絡(luò)技術(shù)的產(chǎn)品約束建模及求解方法*

馬裕港，劉夫云，劉秀娟，蘇其杰

(桂林電子科技大學(xué) 機電工程學(xué)院，廣西 桂林 541004)

一種基于復(fù)雜網(wǎng)絡(luò)技術(shù)的產(chǎn)品約束建模及求解方法*

馬裕港，劉夫云，劉秀娟，蘇其杰

(桂林電子科技大學(xué) 機電工程學(xué)院，廣西 桂林 541004)

針對變型設(shè)計中的工程約束滿足問題，將工程參數(shù)與尺寸參數(shù)放入同一個網(wǎng)絡(luò)，建立了包含尺寸約束和工程約束的網(wǎng)絡(luò)模型。對該模型進行去環(huán)和分層，使其與有向樹圖有著相似的拓撲結(jié)構(gòu)。通過子圖的搜索，在子圖中運用回溯算法進行網(wǎng)絡(luò)的約束求解，使產(chǎn)品滿足工程約束條件。最后以軸的設(shè)計為例，通過與尺寸驅(qū)動的變型設(shè)計方法相對比，驗證了上述方法的可行性。

變型設(shè)計；工程約束；約束求解

0 引言

隨著產(chǎn)品數(shù)字化設(shè)計的發(fā)展，變型設(shè)計大大縮短了企業(yè)的產(chǎn)品設(shè)計周期?，F(xiàn)有的以尺寸驅(qū)動的變型設(shè)計很好的表達了幾何尺寸與參數(shù)之間的關(guān)系[1]。目前國內(nèi)劉夫云將復(fù)雜網(wǎng)絡(luò)理論應(yīng)用于大批量定制的產(chǎn)品配置領(lǐng)域，在構(gòu)建的產(chǎn)品尺寸關(guān)系網(wǎng)絡(luò)中，使用子網(wǎng)搜索算法與簡單路徑搜索算法快速查找需要修改的模塊與尺寸[2]。郭于明[3]從變型設(shè)計需控制設(shè)計變更傳播的范圍等特性出發(fā)，依據(jù)變型設(shè)計的時間與資源約束條件，給出節(jié)點評價方案。滿足產(chǎn)品設(shè)計質(zhì)量需求的同時，也能保證控制變型設(shè)計傳播范圍的需求。徐新勝[4-5]等提出基于貝葉斯方法的尺寸變化概率分配模型以及重用零件實例的產(chǎn)品變型設(shè)計方法。上述方法是以幾何尺寸為基礎(chǔ)對產(chǎn)品進行參數(shù)配置來實現(xiàn)的變型設(shè)計，其中缺少了對尺寸與工程約束之間關(guān)系的表達。

但在產(chǎn)品變型設(shè)計中，尺寸參數(shù)修改往往要受到涉及不同學(xué)科的多個工程約束條件[6](如強度、剛度、熱力學(xué)、零件幾何中心等物理約束)的限制。潘雙夏[7]對產(chǎn)品尺寸與工程約束進行分析給出了，有效解決工程設(shè)計約束的分類及其動態(tài)化和智能化處理的方案。劉小平[8]引入了多元約束圖，提出了最小約束度優(yōu)先和最小值域范圍優(yōu)先的約束求解算法大大縮小了搜索范圍。但都沒有給出尺寸參數(shù)與工程約束之間的傳遞關(guān)系。本文以尺寸驅(qū)動的參數(shù)化模型為基礎(chǔ)，將工程參數(shù)與尺寸參數(shù)放入同一個網(wǎng)絡(luò)，建立了包含尺寸約束和工程約束的網(wǎng)絡(luò)模型。用網(wǎng)絡(luò)遍歷算法對參數(shù)進行傳遞，用回溯算法對模型進行求解；使產(chǎn)品在變型設(shè)計成功后能滿足網(wǎng)絡(luò)中的工程約束條件。

1 建立網(wǎng)絡(luò)

變形設(shè)計是指提取已存在的設(shè)計或設(shè)計計劃、作特定的修改以產(chǎn)生一個和原設(shè)計相似的新產(chǎn)品，其過程一般不考慮尺寸和工程約束的關(guān)系。因此在建立網(wǎng)絡(luò)模型時將尺寸間的約束簡化為線性約束。但是在實際過程中的變型設(shè)計，尺寸間的約束關(guān)系并非都是線性的。其中包括尺寸與尺寸之間的，尺寸與工程條件之間的等非線性關(guān)系。也就是說尺寸在變型設(shè)計過程中不能完全脫離尺寸與工程約束之間的關(guān)系。

為了建立面向工程的約束網(wǎng)絡(luò)能有效的表達，先要對約束進行分類表示。面向工程的約束在設(shè)計過程中可以分為二大類：幾何約束模型和知識約束模型。幾何約束模型中的約束主要為尺寸約束，其處理不涉及復(fù)雜的設(shè)計計算和邏輯判斷。幾何約束模型在網(wǎng)絡(luò)中的構(gòu)建方法[9]：以零件尺寸參數(shù)為節(jié)點，以參數(shù)之間的約束為為邊，邊取加權(quán)有向邊，約束方向按照尺寸之間的數(shù)學(xué)約束關(guān)系直接轉(zhuǎn)化。例如有約束關(guān)系A(chǔ)=0.5B+C+12，從約束關(guān)系中可以得到B和C是已知的，A是通過B和C計算得到的。因此在尺寸參數(shù)關(guān)系網(wǎng)絡(luò)中，從已知的B出發(fā)指向待求的A；從C已知的出發(fā)指向待求的A。

在知識約束模型中包括領(lǐng)域設(shè)計知識約束和強度剛度約束。其分配過程不涉及任何零部件尺寸參數(shù)，但是在設(shè)計過程中是非常重要的一步。不同的產(chǎn)品有著不同的領(lǐng)域設(shè)計知識，因此其約束的形式也不同。其主要是將產(chǎn)品的性能參數(shù)通過數(shù)據(jù)處理或函數(shù)來表達，但是其數(shù)據(jù)最后還是流向零部件的尺寸參數(shù)。強度剛度約束是產(chǎn)品設(shè)計中必須滿足的，它是產(chǎn)品最基本的約束。約束與尺寸參數(shù)有直接關(guān)系，一般為約束目標(biāo)參數(shù)必須大于或少于約束源參數(shù)所構(gòu)成的表達式的值。工程約束相對尺寸約束來說其復(fù)雜體現(xiàn)在二個方面：一是其約束的復(fù)雜性，在工程約束中大多為非線性約束；有些甚至不能用數(shù)學(xué)表達式來表達。二是其約束關(guān)系的復(fù)雜性，在工程約束關(guān)系中常常會出現(xiàn)約束沖突、耦合等情況。因此在建立網(wǎng)絡(luò)時只保留保留其節(jié)點之間的約束拓撲關(guān)系。

通過對網(wǎng)絡(luò)的節(jié)點度的統(tǒng)計規(guī)律發(fā)現(xiàn)，屬于無標(biāo)度網(wǎng)絡(luò)。它具有二個重要的特征增長與擇優(yōu)連接。該網(wǎng)絡(luò)與樹有著類似的網(wǎng)絡(luò)統(tǒng)計參數(shù)和拓撲結(jié)構(gòu)，繼承了樹的一些特性。

2 網(wǎng)絡(luò)模型相關(guān)算法描述

2.1 分層

當(dāng)約束從線性變成非線性時，就很難用一個通用的公式去表達二個節(jié)點之間的約束關(guān)系。為了讓節(jié)點參數(shù)在網(wǎng)絡(luò)中傳遞，本文提出了一種基于遍歷的參數(shù)傳遞方法。當(dāng)兩節(jié)點之間的參數(shù)無法直接傳遞時，先通過節(jié)點之間的路徑搜索得到一條路徑后，再在此路徑上一個節(jié)點一節(jié)點進行參數(shù)傳遞。如有如圖1所示的一條路徑。

當(dāng)X1=20時，X2=314，X3=5024，X4≈0.08。雖然參數(shù)無法直接從X1傳到X4，但是通過分步可以讓網(wǎng)絡(luò)適應(yīng)比較復(fù)雜的約束條件。

按照上述方法在網(wǎng)絡(luò)中進行參數(shù)傳遞，參數(shù)的傳遞其實是對網(wǎng)絡(luò)節(jié)點的一種遍歷。在圖論中對有向圖的沒有給出明確的遍歷算法，但是對于樹給出了相應(yīng)的遍歷算法。對于無向樹的遍歷有前序遍歷、中序遍歷與后序遍歷，對與有向樹的遍歷算法卻沒有說明。利用無向樹的遍歷算法對上述網(wǎng)絡(luò)進行遍歷，存在一個問題：給出的遍歷算法是從根到葉的搜索，在這種情況下往往會遇到枝沒有被確定的時候?qū)θ~進行計算。上述問題產(chǎn)生的原因是建立的網(wǎng)絡(luò)不滿足樹的定義，不是嚴格意義上的樹；主要是因為網(wǎng)絡(luò)中的約束并不都是二元，即存在簡單回路。但是網(wǎng)絡(luò)圖依然有著樹圖的拓撲結(jié)構(gòu)。

本文在樹高的定義上得到啟發(fā)，提出了一種分層遍歷搜索算法。該方法先對樹進行分層確定其樹高，再對每一層的節(jié)點進行遍歷。其特點就是在遍歷完每一層后再去遍歷下一層。如圖2所示的無向樹，對其進行遍歷。

圖2 無向樹圖

用前序遍歷得到的結(jié)果為：

a

用中序遍歷得到的結(jié)果為：

g

用后序遍歷得到的結(jié)果為：

g

用分層遍歷得到的結(jié)果為：

a

前序遍歷的方法在于深度優(yōu)先進行遍歷。雖然每條路徑中的節(jié)點被遍歷的順序是滿足先后要求的；但是在設(shè)計過程中約束關(guān)系比較復(fù)雜，這使前序遍歷在參數(shù)傳遞過程中不能保證其深度優(yōu)先。分層遍歷對節(jié)點參數(shù)在網(wǎng)絡(luò)中傳遞是有效的，在有向樹中可以得到想要的結(jié)果。

區(qū)別于樹圖的樹高確定根據(jù)路徑而來，網(wǎng)絡(luò)中層高的確定是根據(jù)約束關(guān)系來的。因為樹圖中的有向邊只有結(jié)構(gòu)關(guān)系、沒有約束關(guān)系。

2.2 去環(huán)

在網(wǎng)絡(luò)的分層中參數(shù)的同向傳遞和逆向傳遞使網(wǎng)絡(luò)的分層遇到問題。對其進行分析發(fā)現(xiàn)，參數(shù)發(fā)生同向傳遞與逆向傳遞是因為網(wǎng)絡(luò)中存在環(huán)。網(wǎng)絡(luò)中的環(huán)存在二種不同的形式，這里分別將其稱為開環(huán)與閉環(huán)(如圖3所示)。

圖3 網(wǎng)絡(luò)中環(huán)的形式

環(huán)的出現(xiàn)不僅僅使分層出現(xiàn)問題，二點之間的所有簡單路徑變的搜索也變的非常困難，至今仍沒有找到好的解決方法。網(wǎng)絡(luò)中的邊為產(chǎn)品設(shè)計的約束條件，刪除邊來實現(xiàn)的去環(huán)可能會丟失產(chǎn)品在設(shè)計中的約束條件。通過節(jié)點的分層，找到引起參數(shù)同向傳遞或逆向傳遞的邊。為了消除這種現(xiàn)象的同時保留其約束條件，將約束條件進行延時處理。延時處理是將約束暫時不放入?yún)?shù)網(wǎng)絡(luò)傳遞中去，等參數(shù)傳遞完成時再回來考慮其約束是否滿足要求。這樣做的目的是為了保證參數(shù)在網(wǎng)絡(luò)中快速準(zhǔn)確傳遞的同時不丟失約束條件。當(dāng)網(wǎng)絡(luò)在分層中遇到環(huán)時，對相應(yīng)的約束進行延時處理。在實際產(chǎn)品設(shè)計時發(fā)生環(huán)的情況一般為約束滿足判斷或是對之前預(yù)設(shè)的尺寸進行確認。其不對節(jié)點再次賦值，對其約束延時不影響網(wǎng)絡(luò)中的參數(shù)傳遞。

3 約束求解

變型設(shè)計是在原有模型的基礎(chǔ)上對其進行修改。然而當(dāng)某個或某幾個尺寸發(fā)生變化時，新的模型不能保證其各個尺寸都是滿足其原來的約束條件。為了使新的模型能滿足其原來的約束，同時不對模型的每個尺寸進行調(diào)整。通過搜索變量節(jié)點的子圖來減少節(jié)點數(shù)。因為如果一個解X={x1,x2,…,xn}是滿足圖G的一個解，那么X也滿足圖G的任何一個子圖。當(dāng)搜索出子圖G′的所有解X′時，X?X′。在網(wǎng)絡(luò)中除了可變參數(shù)外導(dǎo)出參數(shù)與不變參數(shù)對網(wǎng)絡(luò)沖突的影響不大，因此子圖G'的解X′與圖G的解X相差不是很大。通過對子圖G′搜索可以減少回溯算法中節(jié)點數(shù)量。

因為所建立的網(wǎng)絡(luò)與樹有著類似的網(wǎng)絡(luò)統(tǒng)計參數(shù)和拓撲結(jié)構(gòu)。所以以有向樹為例，對網(wǎng)絡(luò)回溯進行求解。在傳遞過程中不是所有節(jié)點對傳遞的影響都很大，其影響主要來源于幾個參數(shù)。而這些參數(shù)之間存在一定的適應(yīng)性。該適應(yīng)性表現(xiàn)為：假設(shè)一個位于4層的節(jié)點f。

圖4 分層后的有向圖

當(dāng)節(jié)點f發(fā)生修改時，如果它滿足了上下層之間的約束，那么它的改變對整個網(wǎng)絡(luò)的影響并不大。當(dāng)打破這個適應(yīng)能力時，它的改變對網(wǎng)絡(luò)的影響可以會擴散到整個網(wǎng)絡(luò)。如果當(dāng)4層節(jié)點f的變化打破與3層節(jié)點b之間的約束時；為了滿足3、4層之間的約束對3層參數(shù)進行修改后，就會擴散到2層。當(dāng)4層節(jié)點f的變化打破與6層的節(jié)點h之間的約束時，修改就會向下層擴散；為了滿足4、6層之間的約束對6層參數(shù)進行修改后，就會擴散到7層。因此，在節(jié)點f修改后，對其進行節(jié)點的入度進行遍歷。遍歷出節(jié)點f之上的二層對其直接影響的參數(shù)如圖5所示。

圖5 節(jié)點f的上層節(jié)點的子圖

該回溯算法的關(guān)鍵在于，對子圖進行約束求解。與原有的回溯算法不同，在子圖中，回溯算法用來搜索出上一層節(jié)點b和c在不引起節(jié)點a變化時的取值對節(jié)點f的修改進行適應(yīng)性的取值。在路徑唯一時該算法與傳統(tǒng)的回溯算法沒有區(qū)別。

從以上參數(shù)傳遞的影響來看，參數(shù)之間有著一定的適應(yīng)性與影響區(qū)域。從整個網(wǎng)絡(luò)中看參數(shù)影響區(qū)域包括了其出度的各個支路，直到出現(xiàn)下層的可變參數(shù)或支路的終點。因此在對網(wǎng)絡(luò)修改時為了不讓局部的修改影響到整個網(wǎng)絡(luò)的修改，對幾個主要節(jié)點之間的參數(shù)調(diào)整非常關(guān)鍵。

4 工程實例

以輸出軸尺寸為例，對輸出軸(如圖6所示)中的20個尺寸進行尺寸約束網(wǎng)絡(luò)建立，可得如圖7所示的網(wǎng)絡(luò)。

圖6 輸出軸

圖7 軸的尺寸約束關(guān)系網(wǎng)絡(luò)

加入工程約束時將得到圖8所示的網(wǎng)絡(luò)。

圖8 軸的約束關(guān)系網(wǎng)絡(luò)

對圖7、圖8中的節(jié)點出度進行統(tǒng)計得出其節(jié)點度分布圖9。

(a)尺寸約束關(guān)系 (b)工程約束關(guān)系圖9 網(wǎng)絡(luò)節(jié)點度分布圖

隨著網(wǎng)絡(luò)中節(jié)點的增加，其度的分布滿足冪律分布，因此該網(wǎng)絡(luò)是無標(biāo)度網(wǎng)絡(luò)的一種。

當(dāng)對軸進行變型時(其他零件的尺寸約束不變的情況下)，已知變型的n=93.61r/min，T=900N·m。傳統(tǒng)的變型設(shè)計方法通過計算最小軸徑計算得到dmin=52.1mm并考慮聯(lián)軸器的型號取d=55mm，從而得到鍵的尺寸為16×10×70。但是σp=129MPa是不符合許用擠壓應(yīng)力[σp]=120MPa>σp的要求。當(dāng)鍵不滿足強度要求時，通過回溯將對φ1進行修改。當(dāng)其增大為60mm時，σp≈100MPa<[σp]滿足擠壓應(yīng)力的要求。

5 結(jié)束語

本文通過建立了一種同時包含尺寸約束和工程約束的網(wǎng)絡(luò)模型。在此基礎(chǔ)上，用回溯法算法對模型進行約束求解，使產(chǎn)品在變型過程中能滿足工程約束條件。以軸的設(shè)計為例，驗證了方法的可行性。對于樹形約束結(jié)構(gòu)下的約束求解，可以實現(xiàn)滿足工程約束的零件變型設(shè)計。為下一步實現(xiàn)滿足工程約束條件的變型設(shè)計提供了關(guān)鍵技術(shù)支撐。

[1] 鄧偉剛.面向?qū)ο蟮呐渲卯a(chǎn)品變型設(shè)計方法研究與實現(xiàn)[D].武漢:武漢理工大學(xué)，2010.

[2] 劉夫云,祁國寧,車宏安.復(fù)雜網(wǎng)絡(luò)中簡單路徑搜索算法及其應(yīng)用研究[J].系統(tǒng)工程理論與實踐,2006(4):9-13,84.

[3] 郭于明,王堅.復(fù)雜產(chǎn)品開發(fā)網(wǎng)絡(luò)中變型設(shè)計節(jié)點方案評價[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2014,26(2),320-328.

[4] 徐新勝,何曉柯,李丹.基于貝葉斯方法的尺寸變化概率分配及其在產(chǎn)品變型設(shè)計中的應(yīng)用[J].中國機械工程,2011,22(15):1847-1852.

[5] 徐新勝,李丹,嚴天宏.面向柔性客戶需求的產(chǎn)品變型設(shè)計方法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2012,24(3):394-399.

[6] 侯文彬, 王增飛, 張偉, 等. 基于復(fù)雜工程約束的車身梁截面優(yōu)化設(shè)計[J]. 機械工程學(xué)報, 2014, 50(18): 127-133.

[7] 潘雙夏,張帥.基于工程約束的產(chǎn)品參數(shù)化建模策略研究[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報,2001,13(9):840-845.

[8] 劉小平,黃永紅.工程約束表示模型與求解算法研究[J].計算機學(xué)報,1999,22(11):1153-1157.

[9] 孫吉貴, 高健, 張永剛. 一個基于最小沖突修補的動態(tài)約束滿足求解算法[J]. 計算機研究與發(fā)展, 2007,44(12): 2078-2084.

(編輯 李秀敏)

A Method of Product Constraint Modeling and Solving Based on Complex Network Technology

MA Yu-gang, LIU Fu-yun, LIU Xiu-juan, SU Qi-jie

(School of Mechanical and Electrical Engineering,Guilin University of Electronic Technology, Guilin Guangxi 541004, China)

Aiming at the problem of the engineering constrain satisfaction of variant design engineering parameters and dimension parameters are put into a same network and then a network model including parameter constraints and dimension constraints is established. The network model is performed for delete-loop and layering for the sake of its topology similar to directed tree graph’s. In order to make product meet the engineering constraints backtracking algorithm is used for conflict resolution of sub-graph. In the end, compared with variant design method of dimension driven, the feasibility of the method above is verified by taking an example of a shaft.

variant design; engineering constraints; conflict resolution

1001-2265(2017)01-0066-04

10.13462/j.cnki.mmtamt.2017.01.018

2016-03-05；

2016-04-13

國家自然科學(xué)基金項目(51265006)；桂林電子科技大學(xué)研究生創(chuàng)新項目(GDYCSZ201440)

馬裕港(1990—)，男，浙江紹興人，桂林電子科技大學(xué)碩士研究生，研究方向為數(shù)字化設(shè)計，(E-mail)421956751@qq.com。

TH166;TG506

A