劉 萍，高 軍，丁筱玲

（1.山東信息職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)系，山東 濰坊 261061；2.大慶油田電力集團(tuán) 電力營(yíng)銷公司配網(wǎng)檢修所，黑龍江 大慶 163451；3.山東農(nóng)業(yè)大學(xué) 機(jī)械與電子工程學(xué)院，山東 泰安 271018）

隨著經(jīng)濟(jì)的發(fā)展，各種機(jī)械產(chǎn)品的制造量大幅增加，產(chǎn)品信息標(biāo)記的必要性和重要性愈加突出，銘牌成為機(jī)械產(chǎn)品信息的載體，而鋼構(gòu)打字亦漸漸成為國(guó)內(nèi)外該行業(yè)的一個(gè)重要標(biāo)志。鋼結(jié)構(gòu)打字技術(shù)即在要標(biāo)識(shí)的鋼件上用沖壓動(dòng)力沖擊成型字模，沖壓的字體清晰，深度容易控制，并且字頭刀具壽命長(zhǎng)，成本低。在該過程中，刀具路徑的優(yōu)化起著至關(guān)重要的作用，高效的刀具路徑優(yōu)化算法能夠減少換刀次數(shù)和優(yōu)化刀具移動(dòng)軌跡，從而提高加工效率。刀具軌跡描述了加工過程中刀具和工件相對(duì)運(yùn)動(dòng)的具體位置與方式，包括有效的沖壓運(yùn)動(dòng)軌跡和輔助運(yùn)動(dòng)軌跡；輔助運(yùn)動(dòng)軌跡主要用于刀塔轉(zhuǎn)位、刀具定位等，雖不直接參與工件的成型，但卻是加工中不可缺少的過程，需要花費(fèi)一定的時(shí)間，因而對(duì)輔助運(yùn)動(dòng)軌跡進(jìn)行優(yōu)化極其必要。一般鋼構(gòu)打字屬于多點(diǎn)位加工，由于輔助運(yùn)動(dòng)軌跡數(shù)量多，其排列順序與加工路徑的類型密切相關(guān)，用傳統(tǒng)的路徑量計(jì)算方法尋找最優(yōu)路徑非常困難。因此，該研究將工業(yè)鋼構(gòu)打字路徑的優(yōu)化問題抽象為基于旅行商問題（traveling salesman problem，TSP）的多項(xiàng)式數(shù)學(xué)模型。文中在深入研究當(dāng)前刀具路徑優(yōu)化算法的基礎(chǔ)上，提出應(yīng)用遺傳算法（genetic algorithm，GA）進(jìn)行路徑尋優(yōu)的解決方案。

1 鋼構(gòu)打字路徑尋優(yōu)方案設(shè)計(jì)

由于數(shù)控機(jī)床加工中，換刀所用的時(shí)間相對(duì)于快速走刀時(shí)間要長(zhǎng)很多，所以要提高加工速度，就要優(yōu)先減少換刀次數(shù)。刀具路經(jīng)優(yōu)化一般需要考慮換刀次數(shù)、刀具移動(dòng)的長(zhǎng)度、加工時(shí)間、夾鉗干涉等四方面因素。這里假定：不考慮機(jī)器故障以及刀具的磨損，機(jī)床最多只分配一把同一規(guī)格的刀具；同時(shí)，在生成數(shù)控代碼的過程中，對(duì)字符加工的點(diǎn)位進(jìn)行優(yōu)化，盡可能縮短換刀、走刀路徑，減少空行程的時(shí)間，以提高加工效率?；谏鲜鲈?，該組合優(yōu)化系統(tǒng)采用一次換刀就不重復(fù)、不遺漏地加工完所有相同字符，再通過刀塔就近轉(zhuǎn)位換刀加工其他字符的加工方式，這就存在如何安排字符的加工路線，從而使刀具空行程最少的問題。該文選擇采用基于TSP的GA求解方法來規(guī)劃輔助運(yùn)動(dòng)軌跡，以期從一個(gè)全新的角度探討和研究關(guān)于工業(yè)鋼構(gòu)打字最優(yōu)路徑換刀技術(shù)問題。

2 路徑尋優(yōu)中TSP數(shù)學(xué)模型的建立

該文所涉及的鋼構(gòu)打字路徑優(yōu)化問題，可歸結(jié)為帶附加約束（即換刀次數(shù)最少）的旅行商問題（TSP）。TSP問題可描述為：一名商人欲到n個(gè)城市推銷商品，如何選擇一條路徑使得商人經(jīng)過每個(gè)城市一次且僅一次后回到出發(fā)點(diǎn)，并且所走的回路路徑最短。TSP是一個(gè)典型的、易于描述卻難于處理的問題，是許多領(lǐng)域內(nèi)出現(xiàn)的多種復(fù)雜問題的集中概括和簡(jiǎn)化形式。它的數(shù)學(xué)模型可建立如下：

式（1）表示總行程最短；式（2）、（3）要求某人從 i貨位出入貨位j只有一次；式（4）約束機(jī)械手在任何一個(gè)貨位子集中不形成圈；式（5）中Xij=1表示機(jī)械手選擇從貨位i到貨位j的路線，Xij=0表示機(jī)械手不選擇這條路線。設(shè)D=[dij]是貨位距離的鄰接矩陣，則表示貨位i、j之間距離的元素dij具有以下特征：

1）非負(fù)性：dij≥0；1≤i；j≤n；

2）對(duì)稱性：dij=dji；

3）對(duì)角線元素為 0：dij=0；

4）任意 3 個(gè)元素滿足三角不等式：dij+djk≥dik，1≤i，j，k≤n.

3 路徑尋優(yōu)TSP的一般求解

TSP是一個(gè)世界性的難題，人們?cè)岢隽嗽S許多多近似的解法試圖找到一個(gè)次優(yōu)的近似解。這些算法雖然求出的是近似最優(yōu)解，卻大大降低了計(jì)算量。傳統(tǒng)求解中，曾用優(yōu)化方法主要有以下幾種。

1）長(zhǎng)度優(yōu)化法 優(yōu)先考慮刀具移動(dòng)路徑的長(zhǎng)度，使其最小化。如圖1中的（a）所示；

2）刀具優(yōu)化法 優(yōu)先考慮刀具的換刀次數(shù)，使其最小化。如圖1中的（b）所示；

3）混合優(yōu)化法 綜合考慮路徑長(zhǎng)度與換刀次數(shù)，使加工時(shí)間最短。如圖1中的（c）所示。

圖1 長(zhǎng)度優(yōu)化法、刀具優(yōu)化法和混合優(yōu)化法Fig.1 The length optimization，the tool optimization and the hybrid optimization

4）X或Y單向優(yōu)化法 將待加工孔按照中心的X或Y坐標(biāo)排序，此方法較適合沖孔中存在直線均布或陣列分布，其排序按照僅沿著X向或Y向進(jìn)行刀具路徑的規(guī)劃，則又可分為X向路徑法和Y向路徑法2種。X向路徑法：將所有待加工孔中心按照其坐標(biāo)值進(jìn)行排序，排序原則是按X值從小到大的順序，當(dāng)X值相等時(shí)，按Y值排序，Y值的排序原則取決于上一點(diǎn)的Y值，當(dāng)上一點(diǎn)的Y值大于等于當(dāng)前點(diǎn)的Y值時(shí)，則按照從大到小的順序，否則按從小到大的順序。Y向路徑法：同樣也是將所有待加工孔的中心按照其坐標(biāo)值進(jìn)行排序，只是排序原則中首先按Y值排序，Y值相同時(shí)再按X值排序，其余的思想完全相同。X向沖孔路徑優(yōu)化實(shí)例如圖2所示，Y向沖孔路徑優(yōu)化實(shí)例如圖3所示。由于數(shù)控沖床本身的原因，機(jī)床結(jié)構(gòu)的幾何誤差導(dǎo)致在加工點(diǎn)處產(chǎn)生三維位置誤差，對(duì)加工工件精度影響很大。數(shù)控機(jī)床軸線的反向間隙會(huì)影響坐標(biāo)軸的定位精度，而定位精度的高低在孔群加工時(shí)，不但影響各孔之間中心距，還會(huì)由于定位精度不高，造成加工余量不均勻，引起幾何誤差。如果在加工過程中，刀具不斷地改變趨進(jìn)方向，就會(huì)把坐標(biāo)軸反向間隙帶入加工中，造成定位誤差增加，為提高加工精度，要求刀具的移動(dòng)是單向的，應(yīng)盡可能單向趨進(jìn)目標(biāo)點(diǎn)進(jìn)行加工，避免空回程誤差的引入。

圖2 X向沖孔路徑優(yōu)化法Fig.2 X-direction optimization

圖3 Y向沖孔路徑優(yōu)化法Fig.3 Y-direction optimization

5）鄰近優(yōu)化法 當(dāng)待加工孔的位置在二維平面內(nèi)任意排布時(shí)，為了簡(jiǎn)便易行，采用最近點(diǎn)路徑法，其基本步驟如下：以待加工孔中任一孔位為原點(diǎn)，先走到與其最鄰近的1點(diǎn)，然后繼續(xù)在沒有走過的點(diǎn)中選最鄰近點(diǎn)，直至將所有點(diǎn)都選過為止。 例如某零件上有 n個(gè)待加工孔 P1，P2，…，Pn，首先以 Pl作為起始點(diǎn)，在剩余的n－1個(gè)點(diǎn)中尋找距離Pl最近的點(diǎn)作為第2點(diǎn)，再在剩余的n－2個(gè)點(diǎn)中尋找距離P2最近的點(diǎn)作為第3點(diǎn)，依此類推直至將所有的點(diǎn)排序完為止，得到一條刀軌路徑；然后再分別以 P2，P3，...，Pn為起始點(diǎn)進(jìn)行排序，得到另外n－1條路徑。該方法在應(yīng)用于待加工孔分布密度比較均勻的情況下，能夠獲得比較理想的解。但當(dāng)待加工孔分布不均勻時(shí)，會(huì)出現(xiàn)刀具的跨越現(xiàn)象，增加空行程。鄰近優(yōu)化法實(shí)例如圖4所示。

圖4 鄰近優(yōu)化法Fig.4 Nearest neighbor optimization

最近鄰居點(diǎn)算法容易理解，編程簡(jiǎn)單，可靠性較高，是目前解TSP問題中最廣泛采用的方法。但這一方法的近似精度在組合數(shù)學(xué)中已被證明為n≤1/2（1n N+1），它在算法計(jì)算復(fù)雜性為。從近似精度看，這種方法有時(shí)也可能很差，遠(yuǎn)達(dá)不到次優(yōu)，應(yīng)用于多孔加工時(shí)具有較高的計(jì)算復(fù)雜性。

6）親近點(diǎn)優(yōu)化法 采用鄰近算法時(shí)，由于最后一點(diǎn)沒有與任何點(diǎn)進(jìn)行比較，故而需對(duì)最后一點(diǎn)進(jìn)行測(cè)試。例如有n個(gè)點(diǎn) Pl，P2...，Pn，以 Pl作為起始點(diǎn)得到最近鄰居路徑后，比較Pn－1Pn（表示點(diǎn) Pn－1到點(diǎn) Pn距離， 方向?yàn)辄c(diǎn) Pn－1指向點(diǎn) Pn）與P1Pn，如果 Pn－1Pn遠(yuǎn)大于 PlPn，則修改最近鄰居的路徑，將 Pn分別與 P1和 P2相連，即得到 PlPn與 PnPn－1，從而產(chǎn)生親近點(diǎn)優(yōu)化路徑，當(dāng)出現(xiàn)多個(gè)跳躍點(diǎn)時(shí)，親近點(diǎn)優(yōu)化法將失效。

7）蟻群算法 是對(duì)自然界螞蟻的尋徑方式進(jìn)行模擬而得出的一種仿生算法。蟻群在覓食時(shí)即使環(huán)境不斷改變，總能找出一條從食物到巢穴的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放一種特殊的信息素，當(dāng)他們遇到一個(gè)還沒有走過的路口時(shí)，就隨機(jī)地挑選一條路徑前行，同時(shí)釋放與路徑長(zhǎng)度有關(guān)的信息素，路徑越長(zhǎng)，釋放的信息素濃度越低。當(dāng)后來的螞蟻再次遇到這個(gè)路口時(shí)選擇信息素濃度較高的路徑概率就會(huì)相對(duì)較大，這樣大量螞蟻組成的蟻群集體行為便形成了一種信息正反饋現(xiàn)象，最優(yōu)路徑上的激素濃度越來越大，而其它路徑上的信息素濃度卻會(huì)隨時(shí)間的流逝而消減，最終整個(gè)蟻群會(huì)找到最優(yōu)路徑。

在以上算法中長(zhǎng)度優(yōu)化法、刀具優(yōu)化法、混合優(yōu)化法、最近鄰居點(diǎn)優(yōu)化法、親近點(diǎn)優(yōu)化法對(duì)沖壓特征較少的情況下比較適用，當(dāng)特征較多時(shí)容易陷入局部最優(yōu)解。

4 路徑尋優(yōu)TSP的GA求解

當(dāng)前經(jīng)典遺傳算法及各種改進(jìn)的遺傳算法作為解決TSP的一類有效方法，已經(jīng)得到不少應(yīng)用。它具有全局搜索能力和廣泛的適用性等優(yōu)點(diǎn)，解決的問題無(wú)論是否凸性的，理論上都能獲得最優(yōu)解，避免落入局部極小點(diǎn)。因此，該文采用改進(jìn)的遺傳算法尋找最優(yōu)換刀路徑，將選擇、交叉、變異等概念引入到算法中，通過對(duì)包含可能解的種群反復(fù)使用基于遺傳學(xué)的操作，這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣，其后代種群比前代更加適應(yīng)于環(huán)境，種群中的最優(yōu)個(gè)體經(jīng)過解碼，可以作為問題近似最優(yōu)解。

4.1 GA在路徑尋優(yōu)中的優(yōu)勢(shì)

GA就其本質(zhì)來說，主要是處理復(fù)雜問題的一種魯棒性強(qiáng)的啟發(fā)式隨機(jī)搜索算法，與傳統(tǒng)優(yōu)化方法相比，具有如下的優(yōu)點(diǎn)：1）遺傳算法的搜索過程不是直接作用在問題的變量上，而是作用在將變量編碼后的字符串上，即遺傳算法是一種間接的優(yōu)化方法而非直接的優(yōu)化方法；2）遺傳算法的搜索過程不是從一個(gè)點(diǎn)到另一個(gè)點(diǎn)，而是從一個(gè)群體到另一個(gè)群體，不易陷入局部最優(yōu)解；3）遺傳算法使用概率規(guī)則而非確定性規(guī)則指導(dǎo)搜索方向，屬于隨機(jī)性優(yōu)化方法而非確定性優(yōu)化方法；4）遺傳算法屬于非數(shù)值計(jì)算優(yōu)化方法，對(duì)所求解的問題的數(shù)學(xué)模型無(wú)特殊要求，既不要求問題的可行域是連通的、凸的，也不要求問題的目標(biāo)函數(shù)可微，只要求問題是可計(jì)算的；5）遺傳算法的搜索過程只依賴于個(gè)體的適應(yīng)度函數(shù)，不需要其它的輔助信息，具有很好的魯棒性和廣泛的適應(yīng)性；6）遺傳算法雖然每次處理的個(gè)體數(shù)量有限，但每次處理的數(shù)量遠(yuǎn)多于個(gè)體數(shù)量，即遺傳算法具有隱含并行性。

4.2 GA路徑尋優(yōu)工作流程

鋼構(gòu)打字過程中，需要對(duì)刀塔加工用的加工代碼文件進(jìn)行分析，將每次換刀后的路徑段作為一個(gè)路徑組，加工過程如下：從某一個(gè)給定的字符開始，換上對(duì)應(yīng)的刀具后，沿著該刀具總的空行程最短的軌跡，從一個(gè)字符點(diǎn)位移動(dòng)到另一點(diǎn)位，直到所有該字符都被加工完畢，再進(jìn)行下一字符的加工，如此循環(huán)。在這里，刀具實(shí)際上充當(dāng)了旅行商的角色，字符點(diǎn)位充當(dāng)了城市的角色，目標(biāo)為加工過程中刀具的空行程最短。該研究正是把打字點(diǎn)位看做TSP問題，利用遺傳算法特殊搜索方式，對(duì)工業(yè)鋼構(gòu)打字的刀具移動(dòng)軌跡進(jìn)行尋優(yōu)求解，得到了滿意的結(jié)果。圖5所示為遺傳算法的工作流程圖，表示一個(gè)迭代的過程，其需要完成的工作內(nèi)容和步驟如下：1）選擇編碼策略，隨機(jī)產(chǎn)生初始種群P；2）定義適應(yīng)度函數(shù)f（x），計(jì)算各染色體的適應(yīng)度值，以適應(yīng)度值對(duì)染色體進(jìn)行評(píng)價(jià)；3）選擇高適應(yīng)度值的染色體進(jìn)入下一代；4）按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，產(chǎn)生下一代群體；5）按照終止準(zhǔn)則判斷群體性能是否滿足某一指標(biāo)，或者已完成預(yù)定迭代次數(shù)，不滿足則重復(fù)2）～4）步，直到滿足性能要求或達(dá)到預(yù)定的進(jìn)化次數(shù)。

5 應(yīng)用GA求解TSP的實(shí)例仿真

圖5 遺傳算法的工作流程Fig.5 Flow chart of GA

Matlab系列軟件是工程數(shù)學(xué)計(jì)算特別是線性數(shù)學(xué)計(jì)算的得力工具，為檢驗(yàn)該研究的正確性及實(shí)用性，這里選擇使用Matlab7.0作為算法的運(yùn)行環(huán)境，用 Matlab工具箱對(duì)遺傳算法求解鋼構(gòu)打字過程中TSP問題的效果進(jìn)行驗(yàn)證。圖6所示即為某鋼板打字過程中，對(duì)其中某一字符進(jìn)行路徑尋優(yōu)的效果圖。經(jīng)仿真實(shí)驗(yàn)測(cè)得，未加改進(jìn)GA優(yōu)化后的路徑長(zhǎng)度為1 933.955 413 mm，用該研究選取的改進(jìn)型GA優(yōu)化后的路徑長(zhǎng)度1 803.558 802 mm，路徑縮短6.742 482%，優(yōu)化效果明顯。

圖6 路徑尋優(yōu)效果圖Fig.6 Path optimization rendering

6 結(jié) 論

研究基于TSP的數(shù)學(xué)模型和字符點(diǎn)群加工路徑優(yōu)化模型，結(jié)合轉(zhuǎn)塔打字實(shí)例，以刀具的非加工行進(jìn)成本最低為目標(biāo)建立了字符點(diǎn)群?jiǎn)文繕?biāo)路徑優(yōu)化模型，采用Matlab遺傳算法程序進(jìn)行了優(yōu)化求解，最終找到了最短路徑，實(shí)現(xiàn)了路徑優(yōu)化。而對(duì)于空間字符點(diǎn)群的加工，既要保證刀具行進(jìn)路徑最短，又要保證設(shè)備的空間變向次數(shù)最少，這樣才會(huì)最大限度地減少刀具的行進(jìn)時(shí)間、變向時(shí)間，從而大大地降低成本。

[1]邊霞，米良.遺傳算法理論及其應(yīng)用研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究，2010，27（7）:2425-2429.BIAN Xia，MILiang.Development on genetic algorithm theory and its applications[J].Application Research of Computers，2010，27（7）:2425-2429.

[2]譚躍，譚冠政，葉勇，等.具有混沌局部搜索策略的雙種群遺傳算法[J].計(jì)算機(jī)應(yīng)用研究，2011，28（2）:468-470.TAN Yue，TAN Guan-zheng，YE Yong， et al.Dual population genetic algorithm with chaotic local search strategy[J].Application Research of Computers，2011，28（2）:468-470.

[3]張艷瓊.改進(jìn)的云自適應(yīng)粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2010，27（9）:3250-3252.ZHANGYan-qiong.Improved adaptive particle swarmoptimization algorithmbased on cloud theory[J].Application Research of Computers，2010，27（9）:3250-3252.

[4]呂明明，王平江.高速轉(zhuǎn)塔沖床專用數(shù)控系統(tǒng)的研究及開發(fā)[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2011（5）:51-54.LV Ming-ming，WANG Ping-jiang.The research and development of the numerialcontrol system for high-speed turretpunch press[J].Modularm Achine Tool&Automaticm Anufacturing Technique，2011（5）:51-54.

[5]羅宏保，董紅召.車削中心轉(zhuǎn)塔刀架布刀的GA優(yōu)化方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2007，2（38）:172-175.LUO Hong-bao，DONG H ong-zhao.GA-based approach to optimize cutters arrangement on the turret post of turning center[J].Agricultural Machinery，2007，2（38）:172-175.

[6]朱林杰.基于TSP的遺傳算法優(yōu)化研究[D].大連：大連理工大學(xué)，2007.

[7]侯建花.TSP遺傳算法的改進(jìn)及其并行化研究[D].成都：成都理工大學(xué)，2004.

[8]張雁，黃永宣，魏明海.一種求解最大團(tuán)問題的自適應(yīng)過濾局部搜索算法[J].信息與控制，2011，40（4）:445-451.ZHANGYan，HUANGYong-xuan，WEIMing-hai.An adaptive filtered local search algorithmfor the maximumclique problem[J].Information and Control，2011，40（4）:445-451.