尋求零件相似度的優(yōu)化模型及梯度遺傳算法

王 科

(成都工業(yè)學(xué)院 信息與計(jì)算科學(xué)系，成都 611730)

尋求零件相似度的優(yōu)化模型及梯度遺傳算法

王 科*

(成都工業(yè)學(xué)院 信息與計(jì)算科學(xué)系，成都 611730)

零件相似度的高效、精確的計(jì)算對(duì)于汽車的制造工藝有重要的實(shí)際意義。本文利用離散化的方法將零件相似性的問(wèn)題轉(zhuǎn)變?yōu)榍笙嗨贫茸畲蟮姆蔷€性優(yōu)化問(wèn)題，然后通過(guò)構(gòu)造拉格朗日函數(shù)將有約束優(yōu)化轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，并結(jié)合梯度遺傳算法對(duì)優(yōu)化模型進(jìn)行求解。最后，通過(guò)一些實(shí)例驗(yàn)證，說(shuō)明該算法計(jì)算相對(duì)比較簡(jiǎn)單，收斂效果好。

零件相似度；優(yōu)化模型；梯度遺傳算法

由于當(dāng)前國(guó)內(nèi)汽車發(fā)展迅速，車型變化很快。在中國(guó)，一個(gè)主機(jī)廠至少每年要推出兩款不同的車型，基本上才能趕上車市的變化節(jié)奏。而模具又是汽車開(kāi)發(fā)周期的一個(gè)瓶頸，一個(gè)車型就沖壓模具而言至少300多個(gè)沖壓件，上千套模具，各個(gè)制件都有其成型特點(diǎn)。而對(duì)于一個(gè)車系來(lái)講，雖然款式不同但其同類零件具有相似性，也有不同類別的車型在同類零件具有相似性。因此，對(duì)于模具供應(yīng)商來(lái)講，如果將其已經(jīng)制作過(guò)的模具能夠?qū)崿F(xiàn)數(shù)字化庫(kù)，而新接單的模具如果在這個(gè)庫(kù)內(nèi)能夠查出相似的零件，那么這個(gè)制件所需模具的制作就可以借鑒庫(kù)內(nèi)的工藝方案。這樣就節(jié)省了設(shè)計(jì)費(fèi)用、縮短整個(gè)模具制造周期。因此對(duì)零件相似度的比對(duì)工藝的研究可以更好更快地查找到相似的零件，從而縮短設(shè)計(jì)周期。而且它還可以推廣到其他相同或相似性產(chǎn)品的查找中，具有極強(qiáng)的推廣意義。

零件相似度的比對(duì)本質(zhì)上是三維形狀相似的比較，也是當(dāng)前搜索技術(shù)研究的熱點(diǎn)。常用的三維相似算法有基于譜函數(shù)的相似算法[1]、基于概率統(tǒng)計(jì)的相似算法[2-3]以及基于目標(biāo)識(shí)別的相似算法[3]、角點(diǎn)變換相似法[4]、遞歸分割生成有序滿二叉樹(shù)方法[5]等。基于譜函數(shù)的相似法通常使用傅里葉級(jí)數(shù)將離散的三維模型分解為前n階項(xiàng)級(jí)數(shù)的近似和，雖然該方法具有很高的效率，但卻不能分辨出相似的形狀?；诟怕式y(tǒng)計(jì)的相似算法將采樣點(diǎn)的數(shù)目和計(jì)算的花費(fèi)進(jìn)行了折中，采取減少采樣點(diǎn)的數(shù)目來(lái)提高計(jì)算的效率，但計(jì)算精度也會(huì)隨之降低?；谀繕?biāo)識(shí)別的相似算法只能測(cè)量有限的儲(chǔ)存形態(tài)，并且要付出較高的儲(chǔ)存和計(jì)算代價(jià)。角點(diǎn)變換通過(guò)角點(diǎn)匹配找到兩張圖相似的3個(gè)角點(diǎn)，由這3個(gè)角點(diǎn)為一個(gè)平面，在該平面下建立直接坐標(biāo)系進(jìn)行變換，這樣就可以使得圖形的形狀與位置無(wú)關(guān)。而對(duì)于一個(gè)三維圖形，要尋找角點(diǎn)，首先需要建立MLS平面，再通過(guò)角點(diǎn)匹配變換將兩個(gè)不同坐標(biāo)系下的圖形變換到同一坐標(biāo)下，然后通過(guò)梯度變換對(duì)圖形進(jìn)行細(xì)微調(diào)整，這樣可以使減少圖形的損失率，但角度變換的MLS平面和曲率的計(jì)算比較困難。遞歸分割生成有序滿二叉樹(shù)方法，即生成模型凸包圍盒獲取機(jī)械零件的初始位置并對(duì)其進(jìn)行歸一化變換，再生成自適應(yīng)有界分割面對(duì)實(shí)體進(jìn)行分割，檢測(cè)分割過(guò)程中實(shí)體的幾何和拓?fù)鋮?shù)變化，遞歸建立有序滿二叉樹(shù)，結(jié)合工程特征構(gòu)建特征矢量，比較特征矢量的相似性獲得非根結(jié)點(diǎn)實(shí)體的相似度，從而獲得各機(jī)械零件三維形狀結(jié)構(gòu)的相似度。但該方法分解起來(lái)比較困難，而且容易陷入局部最優(yōu)解。

本文利用離散化的方法將零件相似性的問(wèn)題轉(zhuǎn)變?yōu)榍笙嗨贫茸畲蟮姆蔷€性優(yōu)化模型，然后通過(guò)構(gòu)造拉格朗日函數(shù)將約束優(yōu)化轉(zhuǎn)化為無(wú)約束優(yōu)化和梯度遺傳算法相結(jié)合對(duì)優(yōu)化模型進(jìn)行求解，相對(duì)圖形比較方法，該方法更高效，精度更高。

1 問(wèn)題提出

在工程軟件獲取已有模具掃描圖的數(shù)據(jù)的基礎(chǔ)上，比較模具的相似度即對(duì)于任意的兩件產(chǎn)品，當(dāng)產(chǎn)品1與產(chǎn)品2放在同一朝向、同一平面上時(shí)，其高度差在2 cm內(nèi)的區(qū)域面積。由于掃描過(guò)程中，產(chǎn)品擺放的位置不同、方向不同(見(jiàn)圖1)。因此，根據(jù)工程需要，在定義的相似度原則下，將通過(guò)圖形的旋轉(zhuǎn)、平移來(lái)進(jìn)行搜索查找。然而對(duì)于三維數(shù)據(jù)，數(shù)據(jù)量較多，如果采用窮舉的方法在坐標(biāo)系下直接進(jìn)行旋轉(zhuǎn)、平移是無(wú)法實(shí)現(xiàn)的。需要快速而準(zhǔn)確的找到一個(gè)沖壓模恰當(dāng)?shù)姆较蚝妥鴺?biāo)來(lái)與其他模具進(jìn)行比較是解決該問(wèn)題的關(guān)鍵。

圖1 任意2件產(chǎn)品的擺放方式

2 模型分析與建立

對(duì)于任意的兩件產(chǎn)品，設(shè)產(chǎn)品1為將要設(shè)計(jì)的零件，產(chǎn)品2為比對(duì)的零件。要判斷產(chǎn)品2是否可用來(lái)設(shè)計(jì)產(chǎn)品1，問(wèn)題轉(zhuǎn)化為計(jì)算這兩件產(chǎn)品的相似程度。由于產(chǎn)品大小不一，使得相似度的比較沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)。

2.1 目標(biāo)函數(shù)的確定

設(shè)Sr表示絕對(duì)相似的面積，S1表示參照零件的總面積，以絕對(duì)相似面積與總面積之比定義為2個(gè)零件的相似度，則產(chǎn)品的相似度W可表示為

W=Sr/S1。

為了便于計(jì)算，將2件產(chǎn)品按照一定的距離進(jìn)行離散化處理，產(chǎn)品2相對(duì)于產(chǎn)品1可用點(diǎn)的總數(shù)為絕對(duì)相似面積，產(chǎn)品1包含的點(diǎn)的總數(shù)為總面積。設(shè)產(chǎn)品1含有m個(gè)點(diǎn)，產(chǎn)品2含有n個(gè)點(diǎn)，則wij為m×n的0-1矩陣，顯然m和n不宜取得過(guò)大。又由于相似的要求是高度差在2cm內(nèi)的區(qū)域的面積，則L可適當(dāng)取大一點(diǎn)，這里不妨取L=2.1 cm。將產(chǎn)品1投影到一個(gè)平面上，若長(zhǎng)寬分別為l1和l2，則所取點(diǎn)數(shù)m應(yīng)小于l1·l2/4。從而，

(1)

其中：1表示該點(diǎn)可用;0表示該點(diǎn)不可用。顯然，相似度越大，則說(shuō)明產(chǎn)品2的可用程度越高。則目標(biāo)函數(shù)表示為：

2.2 約束條件

對(duì)于相似度的比較，主要問(wèn)題是零件擺放的位置和零件旋轉(zhuǎn)的角度。以其中一個(gè)零件作為參考零件，另外一個(gè)零件作為候選零件，將候選零件進(jìn)行旋轉(zhuǎn)、平移，直到使得候選零件的相似度取得最大為止。所以，零件相似度的比較需要用到三維坐標(biāo)的平移和旋轉(zhuǎn)。

2.2.1 三維坐標(biāo)的變換準(zhǔn)備

1)三維坐標(biāo)的平移變換

表示成矩陣的形式為：

2)三維坐標(biāo)的旋轉(zhuǎn)變換：

①設(shè)繞x軸旋轉(zhuǎn)α

③設(shè)繞z軸旋轉(zhuǎn)γ可表示為：

則三維坐標(biāo)的變換公式為：(x′y′z′ 1)=PABCT

則

x′=tx-sinγ(ycosα-zsinα)+

cosγ(sinβ(zcosα+ysinα)+xcosβ)

y′=ty+sinγ(sinβ(zcosα+ysinα)+xcosβ)+

cosγ(ycosα-zsinα)

z′=tz-xsinβ+cosβ(zcosα+ysinα)

2.2.2 相同位置上的兩點(diǎn)距離小于L為相似

其中：M是一個(gè)非常大的數(shù)，即wij=1，該條件成立；wij=0時(shí)，該條件不成立。

2.2.3 優(yōu)化模型的建立

綜上所述，可建立優(yōu)化模型為：

L2+(1-wij)M

x′=tx-sinγ(ycosα-zsinα)+

cosγ(sinβ(zcosα+ysinα)+xcosβ)

y′=ty+sinγ(sinβ(zcosα+ysinα)+xcosβ)+

cosγ(ycosα-zsinα)

z′=tz-xsinβ+cosβ(zcosα+ysinα)

其中：α,β,γ分別是繞x,y,z軸的旋轉(zhuǎn)角。

3 算法分析

算法的關(guān)鍵是將不同三維圖形通過(guò)平移、旋轉(zhuǎn)變換，快速的轉(zhuǎn)換到同一坐標(biāo)下，以便進(jìn)行比較。首先，將零件進(jìn)行離散化處理，由于采集的圖形點(diǎn)并不是規(guī)則的網(wǎng)格節(jié)點(diǎn)，本文采用反距離加權(quán)平均值法來(lái)生成均勻的網(wǎng)格節(jié)點(diǎn)。其次，對(duì)于非線性優(yōu)化模型的求解，這里有旋轉(zhuǎn)的三個(gè)方向的角度和平移的距離，考慮使用近似算法求解，但近似算法的收斂速度較慢，無(wú)法快速的得到最優(yōu)解。于是，本文結(jié)合遺傳算法的靈活性和梯度算法收斂速度快的優(yōu)點(diǎn)，使用梯度遺傳算法進(jìn)行求解。

作拉格朗日輔助函數(shù)：

λ[(x′-x)2+(y′-y)2+(z′-z)2-L2-(1-wij)M]

(2)

3.1 反距離加權(quán)平均插值法

插值法是離散函數(shù)逼近的重要方法，利用它可通過(guò)函數(shù)在有限個(gè)點(diǎn)處的取值狀況估算出函數(shù)在其他點(diǎn)處的近似值。常見(jiàn)的插值方法有拉格朗日(Lagrange)插值、分段線性插值、Hermite及三次樣條插值、反距離加權(quán)平均插值法。

反距離加權(quán)平均插值法是一種局部插值法，其假設(shè)前提是未知值的點(diǎn)受較近觀測(cè)點(diǎn)的影響比較遠(yuǎn)觀測(cè)點(diǎn)的影響更大。由于水質(zhì)的變化具有連續(xù)性特征，且越近的觀測(cè)點(diǎn)其水質(zhì)越接近，這里采用反距離加權(quán)平均插值法。

反距離加權(quán)插值指計(jì)算一個(gè)格網(wǎng)結(jié)點(diǎn)時(shí)給予一個(gè)特定數(shù)據(jù)點(diǎn)的權(quán)值與指定方次的從結(jié)點(diǎn)到觀測(cè)點(diǎn)的該結(jié)點(diǎn)被賦予距離倒數(shù)成比例。當(dāng)計(jì)算一個(gè)格網(wǎng)結(jié)點(diǎn)時(shí)，配給的權(quán)重是一個(gè)分?jǐn)?shù)，所有權(quán)重的總和等于1.0。當(dāng)一個(gè)觀測(cè)點(diǎn)與一個(gè)格網(wǎng)結(jié)點(diǎn)重合時(shí)，該觀測(cè)點(diǎn)被給予一個(gè)實(shí)際為1.0的權(quán)重，所有其它觀測(cè)點(diǎn)被給予一個(gè)幾乎為0.0的權(quán)重。換言之，該結(jié)點(diǎn)被賦給與觀測(cè)點(diǎn)一致的值。其計(jì)算公式為：

(3)

其中：f(x,y)為坐標(biāo)在點(diǎn)(x,y)插值后的值；fk為與點(diǎn)(x,y)間距為rk的觀測(cè)點(diǎn)的值。

3.2 梯度遺傳算法

1)生成初始種群α,β,γ,tx,ty,tz；

2)利用公式(2)計(jì)算各組值中對(duì)應(yīng)的值；

3)以F值作為適應(yīng)度函數(shù)，對(duì)α,β,γ,tx,ty,tz進(jìn)行選擇、交叉、變異；

5)使用梯度算法對(duì)以上結(jié)果進(jìn)行優(yōu)化；

6)重復(fù)步驟2—5有限次，則可求出該問(wèn)題的近似最優(yōu)解。

4 計(jì)算實(shí)例

本文數(shù)據(jù)來(lái)源于我校模具實(shí)驗(yàn)中心。以其中的10個(gè)零件為例，產(chǎn)品與產(chǎn)品經(jīng)過(guò)旋轉(zhuǎn)平移后的圖形如圖2—圖10所示。

圖2 旋轉(zhuǎn)平移后產(chǎn)品2與產(chǎn)品1相似度為79.57%

圖3 旋轉(zhuǎn)平移后產(chǎn)品3與產(chǎn)品1相似度為32.03%

圖4 旋轉(zhuǎn)平移后產(chǎn)品4與產(chǎn)品1相似度為23.89%

圖5 旋轉(zhuǎn)平移后產(chǎn)品5與產(chǎn)品1相似度為21.47%

圖6 旋轉(zhuǎn)平移后產(chǎn)品6與產(chǎn)品1相似度為62.73%

圖7 旋轉(zhuǎn)平移后產(chǎn)品7與產(chǎn)品1相似度為31.51%

圖8 旋轉(zhuǎn)平移后產(chǎn)品8與產(chǎn)品1相似度為8.14%

圖9 旋轉(zhuǎn)平移后產(chǎn)品9與產(chǎn)品1相似度為6.13%

圖10 旋轉(zhuǎn)平移后產(chǎn)品10與產(chǎn)品1相似度為8.22%

從以上結(jié)果可以看出，通過(guò)旋轉(zhuǎn)、平移的零件基本與比對(duì)的零件達(dá)到了使相似度達(dá)到最大的平面。

通過(guò)梯度遺傳算法能夠有效求解由零件相似度建立的優(yōu)化模型，并且所涉及的理論和計(jì)算相對(duì)比較簡(jiǎn)單，收斂效果好。

[1] KAZHDAN M,FUNKHOUSER T,RUSINKIEWICZ S.Rotation invariant spherical harmonic representation of 3D shape descriptors[C]// Eurographics/acm SIGGRAPH Symposium on Geometry Processing.Eurographics Association,2003:156-164.

[2] OSADA R, FUNKHOUSER T, CHAZELLE B, et al.Shape distributions[J].ACM Transactions on Graphics, 2002,21(4):807-832.

[3] HONG T, LEE K, KIM S.Similarity comparison of mechanical parts to reuse existing designs[J].Computer-Aided Design,2006,38(9):973-984.

[4] CYR C M, KIMIA B B.3D object recognition using shape similiarity-based aspect graph[C]// Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on.IEEE,2001:254.

[5] 陳德明,孫光民,許磊,等.基于角點(diǎn)檢測(cè)的圖像分割算法及在三維重建中的應(yīng)用[J].計(jì)算機(jī)測(cè)量與控制,2009,17(1):173-176.

[6] 徐敬華,張樹(shù)有.基于遞歸分割的機(jī)械零件三維形狀結(jié)構(gòu)檢索方法[J].機(jī)械工程學(xué)報(bào),2009,45(11):182-189.

[7] 李秀娟.求解多目標(biāo)優(yōu)化問(wèn)題的隨機(jī)梯度遺傳算法[J].南京航空航天大學(xué)學(xué)報(bào),2003,35(4):455-458.

Optimization Model and Gradient Genetic Algorithm for the Similarity of Parts

WANGKe*

(Department of Science and Information, Chengdu Technological University, Chengdu 611730, China)

Efficient and accurate calculation of parts similarity is of great practical significance to the automobile manufacturing process. In this paper, we used the method of discreting parts to translate similarity problem of nonlinear optimization model to its maximum similarity, then the constrained optimization into unconstrained optimization problem by constructing the Lagrange function. And it combined with the gradient genetic algorithm to solve the optimization model. Finally, it is proved that the algorithm is relatively simple and the convergence effect is good through some examples.

similarity of parts; optimization model; gradient genetic algorithm

10.13542/j.cnki.51-1747/tn.2016.04.020

2016-11-20

四川省教育廳項(xiàng)目“沖壓模具產(chǎn)品尋求相似度模型及算法研究”(13ZB0044)

王科(1977— )，男(漢族)，四川金堂人，副教授，碩士，研究方向：模型與算法、數(shù)據(jù)分析、優(yōu)化控制，通信作者郵箱：475169513@qq.com。

O242

A

2095-5383(2016)04-0078-05