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

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

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