基于部件間的約束加工中心布局預(yù)測方法

李緯天,薩日娜（內(nèi)蒙古工業(yè)大學(xué)機械學(xué)院，呼和浩特 010051）

0 引言

加工中心具有功能復(fù)合化、結(jié)構(gòu)多樣化的特點，是典型的復(fù)雜機械系統(tǒng)，其總體布局的設(shè)計是帶有全局性的難題。加工中心總體布局合理與否直接影響其制造及操作使用，決定著生產(chǎn)企業(yè)的生產(chǎn)效率。國內(nèi)外學(xué)者對復(fù)雜產(chǎn)品布局方法進行了大量的研究。Lei Wu等[1]提出矩形外包面積最小的判斷問題廣泛存在于工業(yè)生產(chǎn)中，通過約束外包矩形的長寬比，使得矩形框的長寬比可以滿足要求。此外，通過約束中央矩形的中間中心性，中央矩形可以位于最后的布局的中心。Baochun Wang[2]提出矩形布局問題屬于NP難問題，本質(zhì)上是復(fù)雜的組合優(yōu)化。為了克服優(yōu)化算法的局限性，提出了一種自適應(yīng)混合算法。最后通過仿真結(jié)果驗證了布局優(yōu)化策略的有效性和推理結(jié)論的有效性。Armin Fügenschuh等[3]提出一種布局方式，在給定區(qū)域內(nèi)找到一個矩形排列的問題，它使所有內(nèi)外邊界線的總長度最小。YC Xu等[4]在二維布局優(yōu)化問題中，采用將不平等的加權(quán)矩在沒有重疊的情況下放置在一個圓形容器的建模方法，提出有序定位方法，結(jié)果表明該算法具有以往的啟發(fā)式局部搜索性能更好。馮恩民等[5]針對帶有性能約束的衛(wèi)星艙布局優(yōu)化問題，根據(jù)不干涉理論，設(shè)計了圖元之間干涉量的不干涉算法。通過實數(shù)編碼，對布局問題設(shè)計遺傳算法，該算法計算相應(yīng)問題提高了計算效率及精度。高澤旭[6]提出高效的優(yōu)化方法，即首先建立問題的數(shù)學(xué)模型，然后通過將一些啟發(fā)式的策略與全局優(yōu)化算法相結(jié)合，提出相應(yīng)的布局優(yōu)化方法。黃娟[7]根據(jù)不同對象，建立簡化布局模型的不同坐標(biāo)系，把帶有性能約束的布局問題轉(zhuǎn)化為不帶性能約束的布局問題，利用啟發(fā)式算法尋找布局的最優(yōu)解。徐義春等[8]提出一種定位法布局方案，即將一個矩形繞另外一個確定的矩形進行部署。由于圍繞著參照矩形部署時只考慮有限個可布局位置，所以定位法具有多項式時間復(fù)雜性。通過相應(yīng)的改進，在具有大規(guī)模測試用例的測試集上的計算結(jié)果表明，該布局方法比局部搜索方法有更優(yōu)良的計算性能。季美[9]研究了衛(wèi)星艙布局優(yōu)化問題，采用智能優(yōu)化技術(shù)，求解了矩形與多邊形的布局問題，并且通過算例驗證了所用方法的有效性。韓澤光[10]通過將機械運動方案設(shè)計與結(jié)構(gòu)方案設(shè)計相結(jié)合，對兩個設(shè)計進行數(shù)學(xué)描述，為機床布局方案提供了一種理論設(shè)計方法。王偉等[11]采用神經(jīng)網(wǎng)絡(luò)的高度非線性映射功能，建立了目標(biāo)函數(shù)與位置設(shè)計變量的映射關(guān)系，并對翼梁位置進行優(yōu)化。王軍等[12]首先建立了面向大型儀表板的雙機器人作業(yè)加工單元，為了保證機器人和工件不發(fā)生碰撞，提出了以雙機器人的工作空間重合率最大為目標(biāo)、基于遺傳算法的雙機器人加工中心優(yōu)化布局方法，建立了空間約束的數(shù)學(xué)模型。滕弘飛等[13]提出了相對運動的矩形圖形間的動態(tài)不干涉判別條件及其證明，用于處理處于兩矩形圖形之間不干涉判斷問題，即矩形的動態(tài)不干涉判斷問題。

以上研究對復(fù)雜產(chǎn)品布局設(shè)計方面提供了依據(jù)。但工程上布局方案的設(shè)計問題，大多布局問題存在位置約束，它們比無性能約束布局問題更為復(fù)雜，布局問題往往采用人工方式來解決,即由布局設(shè)計人員按照實際布局要求，通過布局模型或樣板根據(jù)自身經(jīng)驗進行試驗或擺放,經(jīng)過多次反復(fù),找出一個可行的布局方案。受復(fù)雜性和求解時間的限制,許多較好的方案在布局設(shè)計時往往無法被發(fā)現(xiàn)。當(dāng)布局規(guī)模比較大、布局物體形狀較為復(fù)雜、約束條件較多時，通過人工方式進行布局求解費時較多。

作為典型的復(fù)雜產(chǎn)品，加工中心是制造企業(yè)的主要設(shè)備。加工中心的布局問題可以看作是具有空間性能約束的布局問題，即將大小、體積不同的物體放入到某一個指定大小的空間。物體與物體、物體與空間外圍不僅互不干涉，他們還存在著干涉、相鄰約束。加工中心的布局問題主要是加工中心相對于地面的占地問題的布局，主要考慮機床各個部件之間的空間干涉以及相鄰約束。

針對以上問題，本文研究如何合理地布局各個部件，使加工中心的占地面積達到最小。本文在對機床的布局預(yù)測中考慮了位置約束性能與空間兩方面因素，對加工中心布局進行預(yù)測及優(yōu)化。加工中心與地面相接觸的各個部件的占地面積可以簡化為多個矩形，通過將三維的機床模型投影成多個二維矩形塊，作為布局預(yù)測的圖元，優(yōu)化目標(biāo)為加工中心所占矩形外包面積最小。采用BP神經(jīng)網(wǎng)絡(luò)對整體面積進行預(yù)測，判斷加工中心二維矩形塊之間的干涉和相鄰關(guān)系，綜合考慮占地面積、干涉、相鄰建立適應(yīng)度函數(shù)，通過遺傳算法對矩形圖元進行優(yōu)化，最終得到機床布局方案的優(yōu)化結(jié)果。

1 加工中心布局方案預(yù)測模型

1.1 占地面積構(gòu)建

圖1 二維布局示意圖

圖2 二維布局示意圖

加工中心不同部件的相對位置在設(shè)計之初是不確定的，確定這種位置關(guān)系就是加工中心的布局預(yù)測。布局預(yù)測過程中，先要將加工中心劃分成若干個獨立單元。加工中心與地面相接處的各個部件形狀可近似為矩形，所以將三維視圖的各個部件在水平面上投影，簡化為二維矩形布局（如圖1所示）?？紤]到操作人員占據(jù)一定的操作空間，加工中心各個部件在布局預(yù)測過程中不能與這些區(qū)域干涉，本文將這些操作空間與部件劃分開來，這些矩形所占的區(qū)域可記作D。經(jīng)過以上步驟，可得到若干個二維矩形布局區(qū)域和若干個二維矩形功能區(qū)域，再對矩形模型進行數(shù)學(xué)描述。

1）單個部件的數(shù)學(xué)模型。加工中心所占區(qū)域為布局的研究對象，每一個與地面相接的部件的水平面投影近似為矩形，記作Bi。首先，建立直角坐標(biāo)系x-o-y。在所研究的區(qū)域上分布著二維矩形布局圖元Bi，i∈In{1,2…，n}，Bi的型心為Ai=（xi,yi），xi,yi∈R。Bi的4個頂點沿逆時針方向分別記為Dik，k∈{1,2,3,4}。 x軸與矩形的長邊Di1Di2的夾角為αi，記作ai∈[0,π),i∈In{1,2,…,n}），設(shè)逆時針方向為正。平行于Di1Di2的向量記作αi=（cosα,sinαi），則與其正交的向量記作bi=（-sinαi,cosαi）。Bi的長與寬分別為2ai1和2ai2（ai1>ai2），記作ai=（ai1,ai2），如圖2所示。

根據(jù)以上定義，在平面上任意一個矩形的布局都有確定的表達，記Bi=Bi（Ai,αi,ai）={Ai+μ1ai+μ2bi|μk∈[-aik,aik],k=1,2}[14]，對于Bi邊界以及內(nèi)部的點都可以有此表示。因此第n個進行布局預(yù)測的部件可以記為Bi,i∈In。

2）加工中心整機模型。每個由矩形代表的部件都有一個型心和一個轉(zhuǎn)角，所以多個部件的布局可由這些型心和轉(zhuǎn)角來確定，每一個部件的布局可以記作Ci=（xi,yi,αi）,i∈In{1,2,…n}。即C=（c1,c2,…cn）為一個整機布局方案。每一個布局方案都會對應(yīng)一個最小外矩形包絡(luò)，對于所有研究對象的頂點Dik（x,y），必然存在某幾個頂點，使得通過這幾個頂點所組成的矩形可以包絡(luò)所有的部件，同時這個矩形也是最小外包矩形，如圖3所示。此矩形的面積盡可能小是布局原則。

圖3 最小矩形包絡(luò)面積A(C)

圖4 干涉區(qū)域S（ψ）

1.2 設(shè)計約束建立

機床設(shè)計主要存在的約束有不干涉以及相鄰這兩類約束。

1）干涉。機床在布局預(yù)測的過程中，各個部件之間不能存在干涉，操作人員的操作空間與部件不能存在干涉。用數(shù)學(xué)方法可做出以下表述。因在平面上任意一個矩形的布局都有確定的表達，所以內(nèi)部的點可以記為：

各個矩形之間不能存在干涉就是各個矩形所組成的封閉圖形不能存在交集，即int Bj∩int Bj=?（i≠j,i,j∈In+m），In+m{1,2,…,n+m}。

若所組成的圖形存在交集，intBi∩int Bj≠?,則2個矩形或多個矩形的面積存在重疊，記ψ=intBi∩int Bj，集合所形成的面積S（ψ）如圖4所示，用于表示Bi與Bj兩者之間的干涉程度，面積越大干涉程度越大。若使int Bi∩int Bj=?（i≠j,i,j∈In+m）成立，則有沖要條件，存在k′∈I4或者I′∈I4使得max{min{（Dj1-Dik′）Tnik′|I∈I4}}，min{(Dik-Dj1′)Tni1′|k∈I4)}≥0為4個頂點，Dik其中Di（4+1）=Di1。

滿足該條件則說明2個矩形之間是不干涉的。

2）相鄰。加工中心各個部件之間存在相鄰的關(guān)系，比如床身與立柱具有相鄰關(guān)系，刀庫與特定換刀位置相鄰，電氣柜與控制區(qū)相鄰等。這種相鄰關(guān)系用數(shù)學(xué)做出如下表達。存在于矩形區(qū)域邊界以及內(nèi)部的點可表述為Bi，內(nèi)部的點為intBi，所以邊界上的點為bou Bi=Bi-int Bi，任何一個與部件相鄰的點可記作P，就存在P∈bou Bi，所以任意兩矩形相鄰可以表述為bou Bi∩bouBj≠?，根據(jù)具體機床部件間的相鄰約束，記二維矩形圖元之間有相鄰約束為st（Ri，Rj），（i≠j，i，j∈In+m）。

根據(jù)李愛萍[15]提出的平面中某一點與矩形的相鄰度計算，記點P0與矩形Bi的相鄰度為s（P0），則s（P0）=min{|P0Pi|}，Pi∈bou Bi。

點與某一矩形的相鄰度計算步驟如下：

a.輸入點P0、Bi的x、y,轉(zhuǎn)角θi，相鄰度s（P0）=0;

b.判斷P0與某一矩形Bi是否存在干涉，可把P0看作是另一矩形的4個頂點，即

P0=Dik,k∈I4，如果存在干涉，則s（P0）=0，終止，如果不干涉，執(zhí)行以下步驟；

c.計算Bi的各個頂點Dik的坐標(biāo)和外法向量nik；

d.計算P0到各個頂點Dik之間的向量P0Dik，確定k′，并使|P0Dik′|min{|P0Dik|}；

e.檢驗P0Dikni（k′-1）≥0是否成立，如果成立，計算P0到Pk′Pk′+1所在的直線距離smin1，s（P0）=smin1，終止，如果不成立，執(zhí)行第十步；

圖5 s(P0)為矩形外某一點到矩形邊上的最小距離

圖6 神經(jīng)網(wǎng)絡(luò)布局預(yù)測模型

f.判斷P0Dik·ni（k′+1）≥0是否成立，如果成立，計算P0到Pk′+1Pk′所在的直線距離smin2，終止，如果不成立，則s（P0）=|P0Dik′|，終止。

相鄰關(guān)系可以直接通過確定某幾個矩形的頂點坐標(biāo)點來實現(xiàn)，存在相鄰關(guān)系的矩形圖元主要是集中于加工中心床身相近的部件與床身的距離關(guān)系。

2 布局模型預(yù)測方法

2.1 神經(jīng)網(wǎng)絡(luò)布局預(yù)測模型

對最小包絡(luò)矩形面積的大小所采用BP神經(jīng)網(wǎng)絡(luò)預(yù)測，人工神經(jīng)網(wǎng)絡(luò)算法有較強的擬合能力，可以映射復(fù)雜的線性或非線性關(guān)系，易于計算機實現(xiàn)。BP神經(jīng)網(wǎng)絡(luò)較為適合用較小的拓撲形狀變化，通過建立基本的神經(jīng)網(wǎng)絡(luò)模型，根據(jù)可以確定加工中心布局方案所需要的參數(shù)，對神經(jīng)網(wǎng)絡(luò)的輸入層進行設(shè)計，以面積的大小作為輸出層，在確定出隱藏層的個數(shù)即可完成神經(jīng)網(wǎng)絡(luò)的基本模型。通過MATLAB訓(xùn)練出符合預(yù)測所需的神經(jīng)網(wǎng)絡(luò)，即可實現(xiàn)神經(jīng)網(wǎng)絡(luò)對真實的輸入以及輸出的擬合，達到預(yù)測的目的。BP神經(jīng)網(wǎng)絡(luò)模型與其他算法相結(jié)合，能夠較快地找出區(qū)域中的最優(yōu)解，實現(xiàn)模型的快速優(yōu)化設(shè)計。

網(wǎng)絡(luò)的輸入層為每個二維圖元的型心坐標(biāo)值以及轉(zhuǎn)角αi。輸出層為總體的最小外包面積A（c）。隱藏層自身的參數(shù)包括權(quán)值wi和閾值θi，隱藏層節(jié)點數(shù)的確定可以通過經(jīng)驗公式：Nhid=2Nin+1，隱藏層的層數(shù)可先選單隱藏層，根據(jù)網(wǎng)絡(luò)的訓(xùn)練狀況可以對隱藏層的層數(shù)進行調(diào)整。若對2個矩形進行布局預(yù)測，則網(wǎng)絡(luò)結(jié)構(gòu)可示意為6-13-1（圖5），即輸入層6個節(jié)點，隱藏層13個節(jié)點，輸出層一個節(jié)點。隱藏層的確定不唯一，可以根據(jù)實際情況進行調(diào)整，也可以為雙隱含層的結(jié)構(gòu)，其節(jié)點的具體個數(shù)也不能僅依靠經(jīng)驗公式，還得多次人為修改、實驗。每個節(jié)點所使用的激活函數(shù)均為S型函數(shù)

2.2 遺傳算法求解

遺傳算法是一種通過模擬自然進化過程搜索最優(yōu)解的方法，它具備快速、隨機的搜索能力；具有全局搜索能力，不會陷入到局部最優(yōu)解。

針對加工中心布局預(yù)測問題，采用遺傳算法來尋找全局最優(yōu)解。遺傳算法的設(shè)計變量為2個矩形的型心坐標(biāo)及轉(zhuǎn)角，編碼方式為實數(shù)編碼，該種方法具有精度高、便于大空間搜索的優(yōu)點；交叉操作采用實數(shù)交叉法，即2個染色體在某個位置進行基因交換；變異操作則是從種群中隨機選取一個個體，再對該個體的某一個基因進行改變；整體流程為達到最大的進化代數(shù)或者迭代較高次數(shù)時，種群的質(zhì)量都沒有明顯變化為止。在該遺傳算法中，為了使布局滿足約束要求，設(shè)計了罰函數(shù)，與原目標(biāo)函數(shù)結(jié)合作為整體的適應(yīng)值函數(shù)F（x）=A（c）+w1s（P）+w2S（ψ），用來去除不滿足約束的布局方案，w1和w2為權(quán)重系數(shù)。選擇操作為從舊群體中選擇一定較優(yōu)個體組成新的群體，以便產(chǎn)生下一代個體，個體適應(yīng)度值越高，被選中的概率越大，采用輪盤賭注法進行選擇，則個體i被選擇的概率因采用實數(shù)編碼，實數(shù)交叉法操作為第k個染色體上的ak和第l個染色體上的a1在位置j上的交叉操作為aki=aij（1-b）+alib，ali=alj（1-b）+akjb,其中b為［0,1］的隨機數(shù)。變異操作采用Michaliwicz[16]闡述的方法，即從種群中選擇某一個體，從中選取某一位置進行變異，生成較優(yōu)個體。整體流程圖如圖6所示。

3 實例分析

圖6 計算流程

BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練采用非線性輸入和輸出數(shù)據(jù)訓(xùn)練神經(jīng)網(wǎng)絡(luò)，使訓(xùn)練后的網(wǎng)絡(luò)能夠預(yù)測非線性函數(shù)輸出。首先在滿足2個約束條件的情況下，系統(tǒng)隨機生成需要布局的矩形塊位置如圖7所示，并且記錄每一次確定矩形位置后，確定最小外包面積。為了提高計算效率，床身以及與床身相鄰的矩形相對于地面固定，2個矩形隨機生成，通過矩形的型心坐標(biāo)以及轉(zhuǎn)角和最小外包面積作為訓(xùn)練數(shù)據(jù)，用于網(wǎng)絡(luò)訓(xùn)練，隱藏層的層數(shù)設(shè)置為2層，每個共15個節(jié)點。選出10 000組作為測試數(shù)據(jù)，其中的，用于測試網(wǎng)絡(luò)的擬合性能。訓(xùn)練后觀察所訓(xùn)練網(wǎng)絡(luò)的回歸性，若回歸性（如圖8所示）較好可采用。

遺傳算法的具體參數(shù)可以設(shè)置為：進化次數(shù)2000、種群規(guī)模20、交叉隨機數(shù)b取0.6、變異概率0.05；變量就是兩個矩形的型心坐標(biāo)和轉(zhuǎn)角6個變量，為了使得算法更加高效，變量的范圍可以控制在其他矩形位置較近的區(qū)域。目標(biāo)函數(shù)就是整體的最小外包矩形，外包函數(shù)在Matlab中可以采凸點函數(shù)編寫。在本文中適應(yīng)函數(shù)可以是由目標(biāo)函數(shù)以及矩形間相鄰程度和干涉度構(gòu)成，尋優(yōu)目的就是為了找到最小外包面積以及不存在重合情況的布局變量。在此遺傳算法中，為了使每次迭代后所獲新布局的機床滿足性能要求，設(shè)計了2個罰函數(shù)，與原目標(biāo)函數(shù)結(jié)合作為整體的適應(yīng)值函數(shù)，采用層次分析法對2個懲罰數(shù)進行權(quán)重分配均為0.5。用來淘汰不滿足約束的布局方案。適應(yīng)度函數(shù)可以表示為

圖7 Matlab中的數(shù)據(jù)采集

圖8 網(wǎng)絡(luò)訓(xùn)練回歸線性度

T=A（c）+0.5s（P）+0.5S（ψ）。

具體優(yōu)化結(jié)果以及迭代過程如圖9、圖10所示。

本實例中，因為床身及其存在相鄰關(guān)系的部件相對于地面的位置是固定的，所以只需要找出2個矩形的設(shè)計變量即可得到2個矩形與其他矩形的相對位置關(guān)系，通過計算之后可得2個矩形的型心以及轉(zhuǎn)角如表1所示。

最終所得最小面積為8.847 m2。

圖9 最終預(yù)測結(jié)果

圖10 迭代過程

表1 所有矩形圖元的型心坐標(biāo)值及轉(zhuǎn)角大小

4 結(jié) 語

本文以相鄰、不干涉作為約束，提出了基于部件間約束的加工中心布局預(yù)測方法。以整機布局圖元外包矩形面積最小為優(yōu)化目標(biāo)，在滿足約束條件的情況下，給出了整機布局圖元外包矩形面積BP神經(jīng)網(wǎng)絡(luò)預(yù)測模型，考慮了部件間不干涉約束、相鄰約束，以布局圖元的型心及轉(zhuǎn)角為設(shè)計變量，設(shè)計布局預(yù)測適應(yīng)度函數(shù)，通過遺傳算法求解最優(yōu)布局方案。以某型號加工中心布局方案預(yù)測為例，對所提方法進行了驗證，該方法對提升占地使用率有重要意義。下一步對三維、多目標(biāo)的布局問題進行研究。

[參考文獻]

[1] WU Lei,ZHANG Liang,XIAO Wensheng,et al.A novel heuristic algorithm for two-dimensional rectangle packing area minimization problem with central rectangle[J].Computers&Industrial Engineering,2016,102：208-218.

[2] WANG Baochun.An Adaptive Genetic Algorithm for 2D Packing Problem[J].Modern Applied Science,2010,4(4)：107-110.

[3] FUGENSCHUH A,JUNOSZASZANIAWSKI K,LONC Z.Exact and approximation algorithms for a soft rectangle packing problem[J].Optimization,2014,63(11)：1637-1663.

[4] XU Y C,DONG F M,LIU Y,et al.Genetic algorithm for rectangle layout optimization with equilibrium constraints[J].Pattern Recognition&Artificial Intelligence,2010,23(6)：794-801.

[5] 馮恩民,宮召華,劉重陽,等.帶性能約束的衛(wèi)星艙布局問題改進遺傳算法[J].大連理工大學(xué)學(xué)報,2005(3)：459-463.

[6] 高澤旭.帶性能約束的氣象衛(wèi)星艙布局優(yōu)化設(shè)計[D].南京：南京信息工程大學(xué),2013.

[7] 黃娟.具有性能約束的簡化衛(wèi)星艙三維布局算法研究[D].南京：南京信息工程大學(xué),2016.

[8] 徐義春,董方敏,劉勇,等.帶平衡約束矩形布局優(yōu)化問題的遺傳算法[J].模式識別與人工智能,2010(6)：794-801.

[9] 季美.衛(wèi)星艙布局問題的求解研究[D].武漢：華中科技大學(xué),2011.

[10]韓澤光.機械系統(tǒng)運動與結(jié)構(gòu)方案集成設(shè)計理論與方法[D].大連：大連理工大學(xué),2008.

[11] 王偉,趙美英,趙鋒,等.基于人工神經(jīng)網(wǎng)絡(luò)技術(shù)的結(jié)構(gòu)布局優(yōu)化設(shè)計[J].機械設(shè)計,2006(12)：7-10.

[12] 王軍,曹春平,丁武學(xué),等.基于遺傳算法的雙機器人加工中心布局優(yōu)化[J].中國機械工程,2016(2)：173-178.

[13] 滕弘飛,劉峻,王秀梅,等.一種矩形的動態(tài)不干涉算法[J].中國圖像圖形學(xué)報,2001(3)：57-61.

[14] 翟金剛,馮恩民,李振民,等.帶性能約束布局問題的不干涉遺傳算法[J].大連理工大學(xué)學(xué)報,1999(3)：14-19.

[15]李愛平,何琪,劉雪梅.基于模塊間約束的機床布局優(yōu)化方法[J].制造技術(shù)與機床,2013(1)：109-114.

[16]MICHALEWIC Z.Genetic Algorithms+Data Structures=Evolution Programs.AISeries[M].New York：Springer Heidelberg,1994：89-120.