劉 萍，高 軍，丁筱玲

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

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

1 鋼構打字路徑尋優(yōu)方案設計

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

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

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

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

1）非負性：dij≥0；1≤i；j≤n；

2）對稱性：dij=dji；

3）對角線元素為 0：dij=0；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 應用GA求解TSP的實例仿真

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

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

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

6 結 論

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

[1]邊霞，米良.遺傳算法理論及其應用研究進展[J].計算機應用研究，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].計算機應用研究，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]張艷瓊.改進的云自適應粒子群優(yōu)化算法[J].計算機應用研究，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]呂明明，王平江.高速轉塔沖床專用數(shù)控系統(tǒng)的研究及開發(fā)[J].組合機床與自動化加工技術，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]羅宏保，董紅召.車削中心轉塔刀架布刀的GA優(yōu)化方法[J].農(nóng)業(yè)機械學報，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].大連：大連理工大學，2007.

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

[8]張雁，黃永宣，魏明海.一種求解最大團問題的自適應過濾局部搜索算法[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.