田文奇

TIAN Wen-qi

（浙江交通職業(yè)技術學院 機電學院，杭州 311112）

0 引言

鋼邊箱設計的難點在其包邊鋼帶，看似簡單但約束條件較多，計算復雜。在包邊鋼帶上有扣子、沖齒、剪角、搭接點等多種元素，相互之間又有邊距、間距、長度、相互避讓等諸多約束要求，設計結果必須使鋼帶生產(chǎn)加工省時、省料、加工方便且布局合理。尤其是沖齒加工，為提高加工效率目前常用的加工模具只有6齒、5齒、4齒等三種類型，且條件允許的情況下最好是用6齒模具加工，大大增加了布局難度。

在目前的企業(yè)實踐中，鋼帶的設計主要有純手工排料布局和采用AutoCAD等通用CAD軟件進行手工繪圖輔助排料布局兩種方法，但這兩種方法均具有效率低、容易遺漏約束條件、設計結果未經(jīng)優(yōu)化、不利于信息交換及對技術人員要求高等局限性。若采用計算機算法實現(xiàn)鋼邊箱專用智能CAD系統(tǒng)進行自動計算，可使行業(yè)面貌大為改觀。但截止目前，還未有相關軟件算法研究報道和成熟應用系統(tǒng)。本文基于模擬退火、多邊形檢測算法，提出了一種鋼邊箱包邊鋼帶沖齒快速優(yōu)化布局算法。

1 沖齒布局問題

鋼邊箱包邊鋼帶由上下兩個邊框和垂直方向四根立條構成，起到連接加固鋼邊箱各膠合板的作用。立條設計較邊框設計要簡單，且絕大大部分細節(jié)相似，文中以鋼邊箱邊框設計為主闡述。鋼邊箱邊框鋼帶圍合后的結構示意如圖1所示：

圖1 鋼邊箱邊框鋼帶圍合示意圖

圖1所示為包邊鋼帶在實際使用時的圍合狀態(tài)，在生產(chǎn)加工時展開為一條鋼帶，且多個邊框和立條連續(xù)加工。沖齒加工時為成組加工，即模具一次沖壓成型多個沖齒，因此在布局時除需同時考慮整組沖齒及該組中每個齒的位置。考慮到安裝拆卸、載重受力等鋼邊箱功能需求，沖齒需在整個鋼帶上均勻合理分布，且不能有任何一齒打在剪角處，因為這樣在鋼帶圍合后會在剪角處形成缺口，影響鋼帶性能。在加工模具需跨剪角或在箱體尺寸較小的情況下，布局難度有所增加。

2 模擬退火求解步驟

模擬退火算法源于固體退火原理，是一種通用概率算法，用來在一個大的搜尋空間內(nèi)找尋命題的最優(yōu)解。模擬退火算法不需要有較好的近似值作為初值，有效避免了常規(guī)算法對初值的敏感性，且算法具有較好的穩(wěn)定性。

模擬退火算法求解的主要步驟描述如下[3]：

1）產(chǎn)生初始解狀態(tài)S，得到符合約束條件、但未經(jīng)優(yōu)化的工藝參數(shù)系列，設定初始溫度T0；2）按照特定規(guī)則在當前解基礎上隨機產(chǎn)生鄰域新解S’；3）計算新解與當前解的增量Δt’=C(S’)-C(S)，其中C(S)為評價函數(shù)。Δt’<0則接受S’作為新的當前解，否則以概率exp(-Δt’/T)接受S’作為新的當前解；4）按一定方式將T降溫，即Ti+1

算法中解空間的構成為沖齒加工布局工藝參數(shù)系列，主要包括左邊距、右邊距、各加工位的間距（即加工位置）及加工次數(shù)等，其中加工次數(shù)可根據(jù)其它參數(shù)直接算出。解空間中參數(shù)如圖2所示。

圖2 布局參數(shù)示意圖

圖2中沖齒組依加工模具的不同有6齒、5齒、4齒等不同規(guī)格，組中每個齒均不能與剪角位置相沖突，計算后沖齒組的數(shù)目即加工次數(shù)Cut_Num，右邊距Offset_R可根據(jù)最后一個齒組位置自動產(chǎn)生。由于不同的兩剪角間的加工模具間的間距可能并不同相同，圖2中所示的間距在整個鋼帶上并不是一致的，即解空間中包含若干個間距參數(shù)Gap1 、Gap2…Gapn。

3 剪角避讓

在沖齒加工時，不能在剪角處（即進行圍合時鋼帶折彎處）留下缺口，這樣影響鋼帶強度、應力分布以及美觀性，因此在進行沖齒布局時要使整個齒組的所有加工齒避開剪角折彎處。沖齒和剪角相互位置如圖3所示。

圖3 沖齒剪角相互位置

在展開狀態(tài)下，剪角呈三角形。由圖可知，沖齒與剪角的相互位置可總結為三種情況：1）沖齒完全處于剪角區(qū)域外部；2）沖齒完全處于剪角區(qū)域內(nèi)部；3）沖齒與剪角區(qū)域有交叉重疊但無相互完全包含關系。三種情況中，第三種情況為沖突狀態(tài)，在加工設計時應予以避免。

在將沖齒尖角處的小段圓弧以5段直線擬合的前提下，沖齒和剪角顯然均為凸多邊形，因此沖齒與剪角的沖突檢測可轉化為兩個凸多邊形的沖突檢測。設沖齒的頂點為P1P2…Pn，剪角的頂點為Q1Q2…Qn，由圖3可知，要檢測兩多邊形是否有交叉（相互包含情況除外），則只需判斷由多邊形1的任意連續(xù)兩個頂點構成的線段PiPi+1與多邊形2的任意兩個頂點構成的線段QjQj+1是否存在相交的情況，若均不存在相交情況，則可認為兩多邊形無沖突。

快速判斷兩線段是否相交可采用叉積法。兩有向線段相交的充分必要條件為點Pi、Pi+1位于線段QjQj+1的兩側，而點Qj、Qj+1亦位于線段PiPi+1的兩側，即兩線段相互跨立對方。在本例中若兩線段共線亦可視為交叉沖突的情況。若線段矢量PiPi+1跨立QjQj+1，則有：

式1中(Pi-Qj)×(Qj+1-Qj)為兩向量的叉積，其他同理。考慮到共線情況也視為沖突，則式1可改寫為：

線段矢量QjQj+1跨立PiPi+1同理可推出。依次對多邊形各線段進行相交測試，只要出現(xiàn)有線段相交情況，則可得出兩多邊形有沖突的結論。

在一個齒組中，只要有一個齒與剪角相沖突，即視為該齒組與剪角沖突，必須對整個齒組進行位置調(diào)整。在算法實現(xiàn)中，為提高執(zhí)行速度，在進行沖突檢測時可先期進行矩形檢測，即先判斷沖齒組的包絡矩形是否與剪角沖突，若無沖突則表明齒組中所有齒均不可能與剪角相沖突，不必進行進一步的逐齒檢測。

對于與剪角沖突的齒組，需先計算齒組中與剪角沖突的齒調(diào)整到不沖突狀態(tài)所需的距離（向左為負，向右為正），取絕對值較小者為整個齒組需要移動的距離。

4 初始狀態(tài)與相鄰狀態(tài)的產(chǎn)生

模擬退火算法必須先得到一個初始解，并以此為基礎進行演化。鋼帶沖齒布局初始狀態(tài)的計算描述如下：

1）在工藝要求允許的OffsetL_Min～OffsetL_Max范圍內(nèi)，隨機產(chǎn)生左邊距Offset_L和右邊距Offset_R，邊距的選擇直接影響后續(xù)實際參加計算的鋼帶長度；

2）根據(jù)箱體的設計載重W，推算出理想的加工齒組間距值Gap_Ref（此處可采用間距與載重間的行業(yè)經(jīng)驗系數(shù)），若計算出的Gap_Ref超出允許的工藝范圍，則直接取允許的最小值或最大值；依據(jù)Gap_Ref估算加工次數(shù)Cut_Num以及各加工位置的坐標，設鋼帶長度為Len，則Cut_Num=( Len-Offset_L-Offset_R)/ Gap_Ref，結果取整。需要說明的是此時各齒組間的間距為均勻的，即均為Gap_Ref；

3）按照第3節(jié)中提到的剪角避讓算法，對所有沖齒組進行剪角避讓計算，調(diào)整與剪角有沖突的所有沖齒組的位置，產(chǎn)生新的間距Gapi和加工坐標，Gap_Ref被替代；

4）無論沖齒組位置是向左還是向右移動，都將影響與其相鄰的加工位置的間距，導致局部間距不均勻。因此需要對相鄰兩剪角間的所有加工位置再次進行均一化處理，可先保持在步驟（3）中被調(diào)整過位置的沖齒組不動，根據(jù)相鄰剪角間距離和剩余的沖齒組數(shù)目計算局部均一化間距，并據(jù)此調(diào)整相應沖齒組位置。經(jīng)上述步驟即得到n個實際間距Gap1、Gap2…Gapn，n的大小取決于沖齒組的個數(shù)，亦即加工次數(shù)。

5）若Gap1、Gap2…Gapn有任一值超出工藝允許的間距范圍，則本次計算失敗，回到步驟1）重新計算。

通過上述方法得到初始解，已具備相當程度的實用性，且初始解是以理想間距值作為計算起點，可在一定程度上保證最終計算出各間距與理想值不會偏離太大，在本例中足以滿足要求。

初始狀態(tài)產(chǎn)生后，對決策變量Offset_L、Offset_R和Gap_Ref進行變換。決策變量新值產(chǎn)生函數(shù)為x’ =x±r*factor，其中r為0～1間的隨機數(shù)，factor為自適應鄰域因子，factor在每次迭代時應逐步減少。在新值產(chǎn)生后若超出工藝要求允許的范圍，則需重新產(chǎn)生。決策變量新值重復上述步驟3）和步驟4），計算間距值，若得到的Gap1…Gapn有任一值超出工藝允許的間距范圍，則視為本次演化失敗，需重新產(chǎn)生決策變量新值，并重新計算結果。

5 評價函數(shù)

沖齒布局除滿足加工工藝要求外，還希望分布均勻，即加工位置間距一致性好，選擇沖齒分布均勻性作為算法中模擬退火評價函數(shù)可保證得到優(yōu)化的計算結果。沖齒分布的均勻性可以標準差加以評價。標準差是一組數(shù)據(jù)平均值分散程度的一種度量。一個較大的標準差，代表大部分數(shù)值和其平均值之間差異較大；一個較小的標準差，代表這些數(shù)值較接近平均值。設評價函數(shù)為C(S)，則其計算公式為：

6 結束語

模擬退火算法在解決文中所及排料布局問題具有天然優(yōu)勢，應用實踐表明沖齒布局算法具有良好的性能和速度，能產(chǎn)生理想的放樣結果。若給定的箱體尺寸和模具類型在客觀上無法放樣，程序可自動選擇齒數(shù)更少的模具并重新計算。為滿足用戶的個性需求，在自動計算的基礎上增加交互編輯功能，使軟件具備良好的商用價值。在箱體尺寸和工藝參數(shù)范圍不是很大的前提下，采用遍歷搜索之類的方法亦可實現(xiàn)放樣布局，但此類方法不具有通用性，且結果沒有得到足夠的優(yōu)化。

[1] 周之平,張颯兵,吳介一等.基于矩形包圍盒的多邊形碰撞檢測算法[J].中國圖象圖形學報：A輯.2004,9(11)：1294-1303.

[2] 吳輝.求解兩個簡單多邊形碰撞距離的最優(yōu)算法[J].華中理工大學學報.1995,23(4)：89-91.

[3] 趙晶,唐煥文,朱動芝.模擬退火算法的一種改進及其應用研究[J].大連理工大學學報,2006,46(5)：775-780.

[4] 許小勇.混沌模擬退火算法在數(shù)值函數(shù)優(yōu)化中的應用[J].計算機與數(shù)字工程.2010,38(3)：37-40.

[5] 肖思和,魯紅英,范安東,宋弘.模擬退火算法在求解組合優(yōu)化問題中的應用研究[J].四川理工學院學報：自然科學版,2010,23(1)：116-118.

[6] 計華,于治樓.一種分階段優(yōu)化的排料算法[J].計算機應用,2008,28(B06)：333-336.

[7] 曹鋒,賈桂紅.基于VC＋＋的二維排料與數(shù)控自動編程系統(tǒng)的設計[J].機床與液壓.2008,36(9)：130-132.

[8] 毛美姣.基于遺傳規(guī)劃的連接板優(yōu)化排料算法的研究[J].機械科學與技術.2008,27(2)：180-183.