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

李緯天,薩日娜（內蒙古工業大學機械學院，呼和浩特 010051）

0 引言

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

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

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

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

1 加工中心布局方案預測模型

1.1 占地面積構建

圖1 二維布局示意圖

圖2 二維布局示意圖

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

1）單個部件的數學模型。加工中心所占區域為布局的研究對象，每一個與地面相接的部件的水平面投影近似為矩形，記作Bi。首先，建立直角坐標系x-o-y。在所研究的區域上分布著二維矩形布局圖元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}），設逆時針方向為正。平行于Di1Di2的向量記作αi=（cosα,sinαi），則與其正交的向量記作bi=（-sinαi,cosαi）。Bi的長與寬分別為2ai1和2ai2（ai1>ai2），記作ai=（ai1,ai2），如圖2所示。

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

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

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

圖4 干涉區域S（ψ）

1.2 設計約束建立

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

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

各個矩形之間不能存在干涉就是各個矩形所組成的封閉圖形不能存在交集，即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）相鄰。加工中心各個部件之間存在相鄰的關系，比如床身與立柱具有相鄰關系，刀庫與特定換刀位置相鄰，電氣柜與控制區相鄰等。這種相鄰關系用數學做出如下表達。存在于矩形區域邊界以及內部的點可表述為Bi，內部的點為intBi，所以邊界上的點為bou Bi=Bi-int Bi，任何一個與部件相鄰的點可記作P，就存在P∈bou Bi，所以任意兩矩形相鄰可以表述為bou Bi∩bouBj≠?，根據具體機床部件間的相鄰約束，記二維矩形圖元之間有相鄰約束為st（Ri，Rj），（i≠j，i，j∈In+m）。

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

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

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

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

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

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

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

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

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

圖6 神經網絡布局預測模型

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

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

2 布局模型預測方法

2.1 神經網絡布局預測模型

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

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

2.2 遺傳算法求解

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

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

3 實例分析

圖6 計算流程

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

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

圖7 Matlab中的數據采集

圖8 網絡訓練回歸線性度

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

具體優化結果以及迭代過程如圖9、圖10所示。

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

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

圖9 最終預測結果

圖10 迭代過程

表1 所有矩形圖元的型心坐標值及轉角大小

4 結 語

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

[參考文獻]

[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] 馮恩民,宮召華,劉重陽,等.帶性能約束的衛星艙布局問題改進遺傳算法[J].大連理工大學學報,2005(3)：459-463.

[6] 高澤旭.帶性能約束的氣象衛星艙布局優化設計[D].南京：南京信息工程大學,2013.

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

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

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

[10]韓澤光.機械系統運動與結構方案集成設計理論與方法[D].大連：大連理工大學,2008.

[11] 王偉,趙美英,趙鋒,等.基于人工神經網絡技術的結構布局優化設計[J].機械設計,2006(12)：7-10.

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

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

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

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

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