分層實體制造技術(shù)中的技術(shù)問題

分層實體制造技術(shù)中的技術(shù)問題

1切割、粘結(jié)工藝設(shè)計層壓實體制造（lt）是一種快速生產(chǎn)的新技術(shù)。傳統(tǒng)的“研磨方法”將傳統(tǒng)的“去除材料”加工方法轉(zhuǎn)變?yōu)椤疤砑硬牧稀奔庸し椒?。通俗地講是將薄材料逐層激光切割成所需的形狀,然后疊加在一起的造型方法。其基本原理是將產(chǎn)品開發(fā)所獲得的三維CAD數(shù)模按一定方法得到一系列橫截面信息,然后用加熱輥和激光束對涂有融膠的薄片材料(如紙、塑料薄膜、金屬箔等)進行逐層切割和粘結(jié),以成型零件各層的輪廓,最終成型零件原型。在分層實體制造技術(shù)中,為了獲得較高的精度,要求每一層的厚度很薄(≤0.1mm),這樣一個零件需由成千上萬層粘結(jié)而成,為了縮短整個零件的制造時間,必須盡可能縮短每一層的制造時間,而分層制造時間是由該層的切割速度與切割路徑所確定的,當(dāng)切割工藝參數(shù)(如:切割功率、切割速度)確定之后,每一層制造的時間是由該層切割(掃描)路徑所花費的時間確定的。因此優(yōu)化切割(掃描)路徑對提高成型效率無疑有重要意義。2網(wǎng)格線切割路徑分層實體制造技術(shù)中切割(掃描)路徑包含兩方面內(nèi)容:每層中輪廓邊界線的有序切割路徑和廢料除去部分的網(wǎng)格線(含邊框)的有序切割路徑,如圖1。其中輪廓邊界線用粗實線表示,網(wǎng)格線部分皆為廢料除去部分,空白處為分層薄片圖形。當(dāng)前關(guān)于網(wǎng)格劃分及網(wǎng)格切割路徑的優(yōu)化討論得較多,也較成熟。而關(guān)于輪廓邊界線切割優(yōu)化的討論較少。本文將就輪廓邊界線的激光切割(掃描)路徑的優(yōu)化問題做進一步深入的研究。2.1封閉輪廓的圖元構(gòu)成圖2(a)為分層薄片截面圖,其剖面線部分為實體部分。每一層邊界的輪廓邊界線都是由一個或多個封閉的輪廓圖形所組成,見圖2(b)。對每一輪廓而言,一般是由一組封閉的首尾相連的多邊形輪廓組成。這是因為CAD實體數(shù)模目前最常見的是轉(zhuǎn)化為STL文件格式來表達,這種表達方法是由許多空間三角形面片類逼近的,故當(dāng)這種模型經(jīng)切片處理后,其截面輪廓不是由一組實際曲線組成,而是由一組封閉的首尾相連的多邊形(直線)所組成。但是對于那些把CAD實體模型直接切片處理得到的截面輪廓而言,則是由首尾連接的直線、圓弧等圖元所構(gòu)成。綜上所述,無論哪種情況每個輪廓邊界線都可看成是由首尾相連的直線、圓弧(圓)等圖元所構(gòu)成的。在這里定義有向有序邊首尾相連組成的封閉輪廓邊界線為環(huán),記為loop,組成環(huán)的基本元素稱之為邊(E),邊的端點稱之為頂點(V)。邊可以是直線、圓弧、圓等,而直線的頂點是直線的首尾兩端點,圓弧的頂點是圓弧的起點與終點。對圓而言,定義一個頂點,這個頂點是圓上的某一點,這點對切割而言,既是切割起點也是切割的終點。這里規(guī)定:任一環(huán)記為loopi,loopi對應(yīng)的頂點總數(shù)記為V(i),第k個環(huán)loopk對應(yīng)的第j個頂點記為Vkj(k=1,2,…,m;j=1,2,V(k)),所有環(huán)皆按整體逆時針方向,從某一頂點開始排列構(gòu)成,如圖2(b)。環(huán)集loop={loop1,loop2,…,loopm},頂點集V={V11,V12,…,V11V(1),…,Vij,…,VmV(k)}。2.2切割路徑規(guī)劃從上可知,激光切割輪廓邊界線是要切割出上面定義的所有環(huán),按實際切割工藝切割環(huán)時,首先以一個環(huán)上的某一頂點為切割起點,再按一定的方向(本文規(guī)定逆時針方向),依次切割完首尾相連的所有邊,最后又返回到起點。在這里定義loopi環(huán)上的開始切割的頂點為切割起點,并記為Pi(i=1,2,…,m),顯然Pi∈{Vi1,Vi2,…,ViV(k)},其整個切割過程可描述為激光割嘴從編程零點出發(fā),快速行進到某一環(huán)上的切割起點,然后開光,依次切割完該有向有序的封閉環(huán)即又回到切割起點,然后關(guān)光快速行進到下一個環(huán)上的切割起點上,重復(fù)前面類似過程直到切割完所有環(huán),再從最后一個環(huán)上的切割起點關(guān)光快速返回程序零點。在圖2(b)中假定程序零點為P0,環(huán)loop1切割起點P1為V11,loop2切割起點P2為V21,loop3切割起點P3為V31,loop4切割起點P4為V41,loop5切割起點P5為V51,則一個完整的切割路線可表示為Ρ0快速空移→Ρ1(V11)P0→快速空移P1(V11)(開光)切割→V12→V13→V14→V15→V16→V17→V18→Ρ1(V11)→切割V12→V13→V14→V15→V16→V17→V18→P1(V11)(關(guān)光)快速空移→Ρ2(V21)→快速空移P2(V21)(開光)切割→V22→V23→V24→Ρ2(V21)→切割V22→V23→V24→P2(V21)(關(guān)光)快速空移→Ρ3(V31)→快速空移P3(V31)(開光)切割→V32→V33→V34→Ρ3(V31)→切割V32→V33→V34→P3(V31)(關(guān)光)快速空移→Ρ4(V41)→快速空移P4(V41)(開光)切割→V42→V43→V44→Ρ4(V41)(關(guān)光)快速空移→Ρ5(V51)(開光)切割→V52→V53→V54→V55→V56→V57→V58→Ρ5(V51)(關(guān)光)快速空移→Ρ0。由于所有封閉的環(huán)必須切割,故無論從何頂點作為切割起點開始切割環(huán)的長度不變,即不存在路徑優(yōu)化問題,這樣激光切割邊界線路徑規(guī)劃就是指如何安排切割順序使激光切割過程中空行進的行程時間最短。對圖2(b)而言,就是從P0出發(fā)如何選擇P1,P2,P3,P4,P5及其加工順序所構(gòu)成的回路路徑最短。很顯然,每個環(huán)上的切割起點一定時,路徑優(yōu)化的問題就是最著名的旅行售貨員問題(TSP),然而環(huán)上的切割起點從切割工藝上講并不唯一,可以是環(huán)上的任一頂點,這樣切割起點在切割路徑的優(yōu)化算法中應(yīng)被考慮的總頂點數(shù)為所有環(huán)的頂點數(shù)ΜΣk=1V(k)個。為了給出切割路徑的數(shù)學(xué)表達式,設(shè)對所有切割起點P={P0,P1,P2,…,Pm}的一個訪問順序為T={P0,t1,t2,tm,P0},其中t1∈{P0,P1,P2,…,Pm};則切割路徑的數(shù)學(xué)模型為minL={d(p0?t1)+Μ-1Σi=1d(ti?ti+1)+d(tΜ?p0)}3基于非確定性利益機制的旅行售貨員問題當(dāng)切割起點確定后,路徑優(yōu)化問題相當(dāng)于一個旅行售貨員問題,此時切割路徑共有M!條,如考慮到切割起點的可變化性,切割路徑將為Μ!×ΜΠk=1V(k)條。其數(shù)目是十分巨大的,即使對于圖2這樣簡單的零件,切割路徑也有5!×8×4×4×4×8=491520條。從形式上看切割起點選擇及路徑優(yōu)化可被看作一個具有約束的離散變量的優(yōu)化問題,然而解決這一問題十分復(fù)雜。由于旅行售貨員問題本身就屬于著名的非確定性多項式算法(NP)問題,若再同時考慮打孔點變化,將使這一問題變得更加復(fù)雜。早期人們的研究為了簡化這一難題,采用直接讀取分層輪廓信息來確定切割起點及切割順序,即先提取環(huán)上的某一點為切割起點,并且該環(huán)先切割。然而分層處理提供的這些環(huán)的先后次序是隨機的,若按這種方法確定加工環(huán)的順序,勢必空行程增加很多。因為可能出現(xiàn)先加工離程序原點最遠的,接著加工離程序原點最近的環(huán)這類現(xiàn)象,從而增加空行程,降低加工效率。針對這一問題,提出了分級規(guī)劃的兩步方法,即先按改進最近鄰算法合理選擇切割起點,再按旅行售貨員問題進行路徑優(yōu)化,有效地解決了這一難題。3.1切割起點算法切割起點確定原則是一個環(huán)僅有一個切割起點,本文按切割工藝采用最近鄰算法的一個改進算法確定切割起點。這種算法充分考慮了切割起點選擇質(zhì)量對割嘴路徑優(yōu)化的影響。其具體步驟如下:1)從編程零點P0出發(fā),令Pk=P0,P={P0}。2)遍歷所有的待加工環(huán)loop={loop1,loop2,…,loopM}對應(yīng)的頂點集V={V11,V12,…,V1V(1),…,Vij,…,VMV(k)}。找到距Pk最近的頂點Pi=Vij(對應(yīng)環(huán)為loopi),并將Pi加入到切割起點集即Q=P+{Pj},然后在loop集中刪除loopi及l(fā)oopi對應(yīng)的頂點{Vi1,Vi2,…,ViV(i)}。3)繼續(xù)按步驟2思路,依次遍歷所有的未訪問的內(nèi)輪廓loop對應(yīng)的頂點集,找到切割起點,并加入切割起點集Q中,P=Q。4)直到最后一個環(huán)上找到距離最近的一個頂點即切割起點Pm,則得所有切割起點P={P0,P1,P2,…,Pm}。這里要說明的是當(dāng)環(huán)是圓時,按最近鄰算法,前一個切割起點與圓上最近點即切割起點,其求法是前一個切割起點與該圓圓心連線與圓的交點。為求解方便,對圓定義了圓心為虛頂點,以便標識及方便求解圓上的切割起點。3.2基于大數(shù)據(jù)的同步控制優(yōu)化算法對所有已知的切割起點P={P0,P1,P2,…,Pm},由2.2節(jié)可知路徑優(yōu)化問題等同于著名的旅行售貨員問題,這是一個典型的、易于描述卻難以處理的NP完全問題。目前針對旅行售貨員問題提出了多種解決辦法,典型的優(yōu)化算法有局部優(yōu)化、遺傳算法、模擬退火法、禁已搜索(tabusearch)、人工神經(jīng)網(wǎng)絡(luò)算法和蟻群系統(tǒng)(AntColonySystem,ACS)等啟發(fā)式搜索算法。蟻群系統(tǒng)是意大利學(xué)者MacroDorigo等于1996年對他們早期提出的螞蟻系統(tǒng)(AntSystem,AS)算法的改進算法,它克服了螞蟻系統(tǒng)算法進化速度較慢的缺點。改進后蟻群系統(tǒng)不僅能夠智能搜索、全局優(yōu)化,而且具有穩(wěn)健性(魯棒性),正反饋、分布式計算,易于與其他算法結(jié)合等特點,并在一系列復(fù)雜的組合優(yōu)化問題中取得成效,特別是求解旅行售貨員問題方面優(yōu)于其他算法。因此本文就采用蟻群系統(tǒng)算法求解分層實體制造技術(shù)中激光切割問題的旅行售貨員問題。3.2.1信息激素與自催化行為蟻群系統(tǒng)是一種新型啟發(fā)式的具有自組織能力的優(yōu)化算法,它吸收了昆蟲王國中的螞蟻行為,通過模仿生物界中螞蟻在沒有任何可見提示下尋找窩巢至食物源的最短路徑的能力,適應(yīng)地搜索問題的最優(yōu)解。其基本原理是螞蟻在尋找食物時,會在其走過的路徑上釋放出一種特有的分泌物——信息激素(pheromone)。螞蟻就是用這種物質(zhì)與其他螞蟻交流與合作。當(dāng)它們遇到一個還沒有走過的路口時,就隨機挑選一條路徑前行,同時釋放與路徑長度有關(guān)的信息素。路徑越長,釋放的信息素濃度越低。當(dāng)后來的螞蟻再次遇到這個路口時選擇信息素濃度較高的路徑概率就會相對較大。這樣大量螞蟻組成的蟻群集體行為便形成了一種信息正反饋現(xiàn)象。最優(yōu)路徑上的激素濃度越來越大,而其他路徑上的信息素濃度卻會隨時間的流逝而消減。最終整個蟻群會找到最優(yōu)路徑。不僅如此,螞蟻還能夠適應(yīng)環(huán)境變化,當(dāng)蟻群運動路線上突然出現(xiàn)障礙物時,螞蟻能夠很快地重新找到最優(yōu)路徑。螞蟻這種選擇路徑的過程被稱之為螞蟻的自催化行為(autocatalyticbehavior)。由于其原理是一種正反饋機制,因此也可將螞蟻王國理解為所謂的增強型學(xué)習(xí)系統(tǒng)(ReinforcementLearningSystem)。3.2.2切割起點viv對所有已知的切割起點P={P0,P1,P2,…,Pm},令切割中切割起點對應(yīng)為旅行售貨員問題的城市V,V={V1,V2,…,Vn},V∈P;邊集A={(r,s)|r,s∈V},與邊(r,s)∈A的有關(guān)花費drs是兩個切割起點的歐氏距離,它是由切割起點即城市Vi∈V的坐標(xi,yi)確定。旅行售貨員問題就是要找到一條經(jīng)過每一個城市(切割起點)一次且回到起點的最小花費的環(huán)游。3.2.3螞蟻群系統(tǒng)解決訂單銷售問題的算法蟻群系統(tǒng)算法的核心主要是三條規(guī)則:螞蟻的狀態(tài)轉(zhuǎn)移規(guī)則、局部信息激素更新規(guī)則、全局信息激素更新規(guī)則。1偽隨機概率選擇規(guī)則假設(shè)有n個城市,m只螞蟻。一個螞蟻在城市r要選擇前往城市s,s由下面公式確定s={argmax{[τ(r?s)?[η(r?s)]β}如果q≤q0u∈Jk(r)s否則(1)其中,τ(r,s)表示螞蟻在城市r與城市s之間留下的信息激素,η(r,s)=1/drs,q為[0,1]內(nèi)的隨機數(shù),q0為一個參數(shù)0≤q0≤1,β為決定信息激素相對路徑距離的相對重要性指數(shù)(β>0)。s由下式確定Ρk(r?s)={[τ(r?s)[η(r?s)β]ΣΖ∈Jk(r)[τ(r?s)][η(r?z)]β如果s∈Jk(r)0其他(2)Pk(r,s)表示螞蟻k從城市r選擇轉(zhuǎn)移到城市s的概率;Jk(r)表示螞蟻k在城市r時還沒有環(huán)游到的城市集合。上述公式確定螞蟻轉(zhuǎn)移至某城市的方法就是偽隨機概率選擇規(guī)則(pseudo-randomproportionalrule)。在這個規(guī)則下,每當(dāng)螞蟻要選擇向哪個城市移動時,就產(chǎn)生一個在[0,1]范圍內(nèi)的隨機數(shù)q,根據(jù)q按公式(1),(2)確定用哪種方法產(chǎn)生螞蟻轉(zhuǎn)移方向。該規(guī)則表明螞蟻在選擇路徑時,盡量選擇離自己距離較近且信息激素強度較大的方向。在這個規(guī)則里設(shè)置了類似于遺傳算法中的變異運算,q0是實現(xiàn)變異的參數(shù),變異運算的目的是為了避免運算陷入局部極小的陷阱。2環(huán)游路徑長度若螞蟻從城市r向城市s轉(zhuǎn)移,則規(guī)定螞蟻在經(jīng)過這條邊時運用下面的更新規(guī)則改變邊上的信息激素τ(r?s)←(1-ρ)τ(r?s)+ρτ0ρ為區(qū)間(0,1)上的參數(shù),τ0=(n·Lnn)-1,Lnn為由最近鄰算法而得的環(huán)游路徑長度。局部更新規(guī)則在所有螞蟻完成每一次轉(zhuǎn)移后執(zhí)行,它保證了避免搜索陷入局部極小陷阱,同時又給出了更短的環(huán)游增加信息激素。3基于局部更新規(guī)則的旅行售貨員問題一旦所有螞蟻都找到了自己的解,全局更新規(guī)則不再用于所有螞蟻,而是僅對每一次循環(huán)中最優(yōu)的螞蟻使用,其公式為τ(r?s)←(1-α)τ(r?s)+α(Lab)-1α為區(qū)間(0,1)上的參數(shù),Lab為算法已求出的m個螞蟻中最優(yōu)的環(huán)游路徑長度。由于全局更新規(guī)則只是讓實現(xiàn)最好環(huán)游的螞蟻的路徑上的信息激素變得更高,因此它只是在優(yōu)秀父輩完成的環(huán)游領(lǐng)域內(nèi)搜索,這使得求解速度大大提高。蟻群系統(tǒng)求解旅行售貨員問題的算法可敘述如下:初始化各參數(shù)初值按最近鄰算法求解LNNloop:每只螞蟻被放置在按一定策略選出的城市結(jié)點上loop1:m只螞蟻中的每一只螞蟻都要應(yīng)用狀態(tài)轉(zhuǎn)移規(guī)則移動使用局部更新規(guī)則使τ(r,s)更新。UNTIL1:每只螞蟻都進行一個完整的旅行回到自己的出發(fā)點找出這一代螞蟻環(huán)游的最短路徑,應(yīng)用全局更新規(guī)則更