周 盛 李 瑞 汪 洋

（武漢理工大學能源與動力學院1） 武漢 430063） （大連理工大學船舶工程學院2） 大連 116024）

（大連中遠船塢工程有限公司3） 大連 116113）

在船體建造過程中，鋼料劃線和切割主要由數(shù)控切割機來完成，但是在大多數(shù)船廠中，在切割零件上標注零件編號、裝配符號等施工信息時仍由手工完成，效率較低，有的船廠采用數(shù)控噴字設備來完成鋼板上零件的噴字標注，相對于人工標注，數(shù)控噴字設備的使用提高了噴字效率，但是，零件的噴字順序往往人為給定，容易造成數(shù)控噴頭空行路徑過長，因此，為了減少噴頭空走路徑，提高設備的效率，本文根據(jù)鋼板上噴字的坐標位置和字符長度，對噴頭行走路徑進行了優(yōu)化研究．

旅行商問題（traveling salesman problem，TSP）是計算機科學中的一個典型問題［1］，本文將數(shù)控噴字路徑優(yōu)化問題與旅行商問題進行了對比分析，將旅行商問題中節(jié)點間路徑的優(yōu)化擴展為數(shù)控噴字路徑中有向線段間路徑的優(yōu)化，在此基礎上，建立了數(shù)控噴字路徑優(yōu)化數(shù)學模型，并采用遺傳算法對其進行了求解．

1 問題描述與分析

1.1 TSP問題描述［2－3］

旅行商路徑問題可描述為：已知n個城市各城市間的距離，某一旅行商從某個城市出發(fā)訪問每個城市一次且僅一次，最后回到出發(fā)城市，怎樣安排才使其所走路線最短．

其數(shù)學模型為：對于城市ti的一個訪問順序為T＝（t1，t2，…，tn），則旅行商問題為求商人所行的最短路徑，即為

式中：Ω為n個城市不重復排列的所有可能的回路．因此，旅行商問題實際上即是給定的一組離散點，求不重復連接所有離散點的最短路徑．

1.2 數(shù)控噴字路徑數(shù)學模型

數(shù)控噴字路徑優(yōu)化與旅行商問題類似，可以抽象為求不重復連接所有字符串的最短路徑，二者的區(qū)別是旅行商問題是基于一組離散點，每個離散點的特征屬性僅是點坐標；數(shù)控噴字路徑優(yōu)化問題是基于一組字符串，每個字符串的特征屬性根據(jù)數(shù)控噴字的指令文件有起始點坐標、字符串與X軸角度和字符串長度，因此，可以將每個字符串看成是一條有向線段，數(shù)控噴字路徑優(yōu)化問題再次抽象為求不重復連接所有有向線段的最短路徑，見圖1a）是給定的一組有向線段，見圖1b）是這一組有向線段的路徑圖．數(shù)控噴字路徑的優(yōu)化就是確定這組有向線段的順序，使得噴頭按這一順序所行的空行路徑最短．

圖1 噴字路徑示意圖

1.3 噴字路徑優(yōu)化分析

根據(jù)上述對數(shù)控噴字路徑優(yōu)化問題的描述及其數(shù)學模型的建立，從中可以發(fā)現(xiàn)其問題的求解思路、方法與求解TSP問題有相似之處．通過把數(shù)控噴字優(yōu)化問題與TSP問題進行對比分析可知，它們都是一個如何合理安排路徑的問題，所以可以把噴字路徑優(yōu)化問題歸結(jié)為特殊的TSP問題進行求解．

數(shù)控噴字路徑優(yōu)化在TSP問題下可以描述為：對于一組待噴字符段，數(shù)控噴頭首先從原點（未啟動的停放位置）開始，在工作臺平面上沿著使總空行路徑最短的軌跡，空走移動到待噴字符段的起始點上，然后按照數(shù)控程序指令進行噴字，噴完該段標注字符后，再移動到其他的噴字字符段重復該噴字過程．直到所有噴字字符段都噴完，然后噴頭回到原點位置．

因此，可以根據(jù)每個字符串的起始點坐標、與X軸的角度和字符串長度，求出每個字符串的終點坐標，這樣，就可以將數(shù)控噴字路徑優(yōu)化問題轉(zhuǎn)化為一一對應的一組起始點和終點的TSP問題，增加約束條件為：數(shù)控噴頭行走到一個起始點后，下一步只能行走到與其對應的終點位置，再下一步的路徑，只能以剩下的起始點為目標，以此類推．優(yōu)化目標即是使數(shù)控噴頭的空行程最短．

2 遺傳算法求解特殊TSP問題

遺傳算法是一種搜索最優(yōu)解的方法［4－6］，該方法是通過模擬生物進化過程實現(xiàn)的．遺傳算法以群體中的所有個體為對象，對解空間的每一個個體進行編碼，通過遺傳操作選擇、交叉、變異等迭代從解空間尋找含有最優(yōu)解或較優(yōu)解的組合．在進行個體優(yōu)劣的判斷時，利用由目標函數(shù)構(gòu)造的適應度函數(shù)來進行判斷．通過對每一代群體都進行遺傳迭代操作，那么解空間中的解就向最優(yōu)解逼近，到遺傳算法終止，則所得可行解即為最接近最優(yōu)解的解．

1）編碼 本文使用路徑順序表達形式．這種表達方法是TSP問題的最自然、最簡單的表示方法．例如：對于一個有9個噴字字符段的的待加工零件，其噴字順序為1－3－2－5－4－7－6－9－8可簡單表示為［1 3 2 5 4 7 6 9 8］，表示從1號字符段出發(fā)依次經(jīng)過3，2，5，4，7，6，9，8字符段最后返回1號字符段的一條路徑．并且這種表達方式滿足TSP問題的約束條件．保證了每個字符段經(jīng)過且只經(jīng)過一次．

2）生成初始群體 種群規(guī)模越大，種群的多樣性越好，算法越容易跳出局部最優(yōu)．但隨著種群規(guī)模的增大，計算量增大，算法易產(chǎn)生早熟，一般都是隨機生成規(guī)模為N的初始群體，N的值取為20～200．

3）適應度函數(shù) 對于求解最小值問題，采用如下變換

式中：cmax為一個適當大的數(shù)．cmax取為群體中最差個體的路徑長度，就相當于差個體淘汰制．

4）確定交叉算子 目前己有多種交叉算子，如部分映射交叉算子，序交叉算子、循環(huán)交叉算子，其中啟發(fā)式交叉和邊重組交叉相對有效．本文選用啟發(fā)式交叉算子．

3 數(shù)控噴字路徑優(yōu)化實例

應用Matlab編寫基于遺傳算法的數(shù)控噴字路徑優(yōu)化程序，以某塊船體外板上30個噴字字符段為例，首先確定以下參數(shù)如下：種群大小N＝30；最大進化代數(shù)T＝100；交叉概率Pc＝0．65；變異概率Pm＝0．01；賭輪盤選擇算子；啟發(fā)式交叉算子；變異算子．

經(jīng)過遺傳算法50代后的結(jié)果就得到了較大的改進，已開始在接近最優(yōu)近似解．在60代之后兩代中最好解之間的誤差不超過5%，為了在更短的時間內(nèi)得到較滿意的解，即可在60代時終止遺傳進化．這在連續(xù)處理較多數(shù)量鋼板的噴字路徑優(yōu)化時，時間上的優(yōu)勢會比較明顯．

對于未集成路徑優(yōu)化算法的噴字設備，其原始噴字路徑圖見圖2，圖3是采用遺傳算法路徑優(yōu)化計算結(jié)果的路徑圖．優(yōu)化后空行路徑比未優(yōu)化的路徑減少了22%．

圖2 原始路徑圖

圖3 遺傳算法優(yōu)化后路徑圖

4 結(jié)束語

將數(shù)控噴字路徑優(yōu)化問題與計算科學中經(jīng)典的TSP問題進行了對比分析，根據(jù)噴字特征，將噴字字符串抽象為有向線段，因此，將數(shù)控噴字路徑優(yōu)化問題抽象為一一對應的一組起始點和終點的特殊的TSP問題，建立了數(shù)控噴字路徑優(yōu)化的有向線段路徑優(yōu)化模型，以噴字空行路徑最短為目標，利用遺傳算法進行了求解．

通過實例計算結(jié)果表明，基于遺傳算法的數(shù)控噴字路徑優(yōu)化方法，能夠大幅減少數(shù)控噴頭的空行路徑，由此提高數(shù)控噴字設備的加工效率．

［1］邢文訓，謝金星．現(xiàn)代優(yōu)化計算方法［M］．北京：清華大學出版社，1999．

［2］ALBERTO G，RICARDO G．A particale swarm－based met heuristic to solve the traveling salesman problem［C］／／Procedings of the 2006International Conference on Artificial Intelligence，2006：698－702．

［3］HANG，NA S．A study on torch path planning in laser cutting process，part 2：cutting path optimization using simulated annealing［J］．Journal of Manufacturing Process，1999（1）：62－70．

［4］孫惠文．遺傳算法求解旅行商問題［J］．西南交通大學學報，1996，31（5）：550－554．

［5］喻 菡．遺傳算法求解TSP的研究［D］．成都：西南交通大學，2006．

［6］GREFENSTETTE J，COPAL R，ROSIMAITA B．Genetic algorithms for the traveling salesman problem［C］／／Proc Int Genetic Algorithms and Their Applications Conference，1985：160－168．