基于遺傳算法的三坐標測量機測量路徑規劃方法

周開俊　肖　軼　周小青

南通職業大學，南通，226007

?

基于遺傳算法的三坐標測量機測量路徑規劃方法

周開俊肖軼周小青

南通職業大學，南通，226007

摘要：針對現有三坐標測量機檢測路徑規劃方法的不足，提出和構建了零件檢測特征群數學模型和求解流程，在此基礎上，根據檢測工作平面、檢測測頭及檢測測針變動次數和檢測路徑構建優化目標函數，從宏觀和微觀兩個層面分別應用矩陣交叉遺傳算法和序列規劃遺傳算法進行零件檢測特征路徑的優化求解。最后以Hexagon公司檢測零件為例，說明了零件初始檢測信息的獲取以及算法的優化求解過程。實踐證明，該方法快速有效，且具有良好的工程應用價值。

關鍵詞：三坐標測量機；測量路徑規劃；遺傳算法；矩陣交叉；序列規劃

0引言

隨著裝備制造業向智能化、集成化、高端化方向發展，越來越多的機械制造企業開始使用三坐標測量機進行零件質量的監測和檢測。在單件測量中，測量路徑往往是靠操作人員的經驗和檢測偏好進行的，是否是最短路徑、是否是最短時間往往并不重要。然而在產品批量檢測時，測量機運行的時間往往對檢測成本有比較大的影響，同時也影響測量機的測量效率和自動化水平。因此如何規劃出高效的測量機行走方案，一直是國內外研究人員的研究熱點。

Ainsworth等[1]開發了一種測量路徑規劃系統，將CAD模型和采樣點作為輸入因子，利用開發的系統規劃測量路徑。Lee等[2]按特征的優先等級對特征進行分組，通過確定特征組的檢測順序和組內特征的檢測順序，生成了總體的檢測規劃。Albuquerque等[3]設計了一種自動的放置點和路徑規劃方法，通過放置點面的不斷細分迭代，能夠高效生成復雜零件的多個相交特征的無碰撞檢查路徑。Zhang等[4]開發了一種基于特征的三坐標測量工藝規劃系統，系統分為公差分析、可達性檢測、聚類算法、路徑規劃、檢測工藝規劃5個模塊。Lu等[5]、紀曉剛等[6]通過在被測特征間引入過渡點，建立各點之間的關系矩陣，然后利用遺傳算法求解測量了最短路徑。王世剛[7]從工藝規劃的角度，建立了測量路徑優化的數學模型，利用遺傳算法和禁忌搜索算法進行了優化求解。方憶湘等[8-9]以測點變換次數最少和路徑最短作為優化目標，運用多色集理論建立了測頭與待測特征之間的關系矩陣，利用現代優化算法對待測幾何特征進行了測量排序。總的來說上述研究大都偏重于求解最短測量路徑，而在三坐標實際測量過程中，某些同類或相近距離的特征互換測量順序對測量時間和測量路徑影響不大，因此無需按旅行者算法或其他優化算法尋找最短路徑。

路徑規劃的目的并不僅僅是為了尋找一條最短的檢測路徑，而是使測量機在測量時間、測量路徑和測量效益上達到一個綜合的優化效果。本文以此為目標，建立檢測特征群模型，根據檢測工作平面、檢測測頭及檢測測針變動次數和檢測路徑分別構建優化目標函數，從宏觀和微觀兩個層面應用遺傳算法尋找最優的檢測方案。

1檢測特征群模型的建立

三坐標測量機主要用來檢測零件的尺寸、形狀和位置精度，但是不管是尺寸、形狀，還是位置精度，最終均是由零件上的各種特征綜合形成和作用的結果，因此檢測的對象或信息的收集主要是零件上的相關檢測特征。一般來說，零件上的幾何特征不外乎點、線、面、圓、圓柱、圓錐、球這幾類特征。其中圓、圓柱、圓錐、球還有內外之分；曲線、曲面一般通過掃描輪廓點云來表示；而槽則是面、圓柱、圓錐等特征的復合體。精度檢測的本質則是根據檢測尺寸、形狀和位置精度要求，按照一定的順序和路徑收集相關特征的信息，將同類檢測特征放在一起檢測，以期檢測時間最短、坐標測量機的損耗最小、效益最高。

假設零件由n個關鍵特征組成，表示為F={F1,F2,…,Fn}(如果零件中存在多個相同的關鍵特征，在編號時以不同的編號加以標注)，被劃分成s個檢測群，表示為G={G1,G2,…,Gs}，每個檢測群內的特征數量為ki，則有

那么零件檢測特征群可以用數學方法描述成如下形示：

(1)

記為

G=R·F

2檢測初始信息獲取

為了獲取零件檢測特征的信息，三坐標測量機的測頭必須能無障礙地抵達被測特征表面。通常情況下，為了獲得高質量的測量信息，測針應沿被測點的法向量方向前進，即應保證測針上紅寶石球沿法向量方向與測點接觸，因此需要預先定義特征的檢測工作平面。根據笛卡兒坐標系，檢測工作平面一般為立方體除底面以外的5個平面，當然也可根據具體情況，設置與5個平面成夾角的斜面。

目前，三坐標測量機上使用的測頭分為兩類：一類是可旋轉式測頭(自動/手動，可完成A/B軸旋轉)；另一類是固定式測頭，配自動更換架。不管是第一類還是第二類，在更換工作平面時，均需改變測針的工作角度，差別在于前者移動至安全位置完成角度變換，后者必須回更換架，更換相應的吸盤。一般情況下，零件的檢測特征使用一種探針即可完成，但對于復雜零件，由于檢測精度的要求和檢測位置的限制，常常需要多根探針，此時可旋轉式測頭和固定式測頭都需回更換架更換測針。

因此，在規劃特征檢測路徑時，首先根據檢測零件的幾何結構、檢測要求及使用三坐標測量機的特點確定各檢測特征的工作平面、檢測角度及使用的測針要求信息。為了便于表述，現采用數學映射關系進行描述，如下所示：

S(Fi)=Φ(Pi,Ai,Mi)

(2)

式中，S(Fi)為Fi特征所處的檢測狀態；Φ(Pi,Ai,Mi)為其檢測狀態的映射值；Pi為檢測工作平面，其值為+Z、+X、+Y、-X、-Y5個檢測工作平面的一種；Ai為測針檢測角度，對于固定式測頭其值為直立吸盤、五方位吸盤、角度吸盤當中的一種；Mi為使用的測針型號，根據零件的檢測位置和檢測精度選用，一般測針紅寶石球直徑從0.5～10 mm，長度從20～100 mm不等。

顯然，式(2)的表達形式可很容易使用計算機進行表達，有利于后續的檢測路徑自動規劃處理。

3零件特征檢測路徑規劃流程

基于三坐標測量機的零件特征檢測路徑規劃問題，實際上就是根據零件幾何結構、檢測要求和所用三坐標測量機的特點確定檢測特征的先后順序問題。該問題可以分解為兩個部分：一是求解劃分檢測特征群的問題(宏觀)，即哪些特征放在一起檢測可使測量變換次數最少，也就是求解式(1)特征群劃分矩陣的問題；二是求解所劃分的檢測特征群內特征的先后檢測順序的問題(微觀)，即保證每個劃分特征群內特征檢測路徑最短的問題。由于零件檢測特征群矩陣R=(rij)s×n只存在0和1兩種元素，且每列具有只有一個1的特點，互換檢測特征群矩陣的列不僅可以改變特征群所屬特征的組成和個數，而且不會違反相關的約束條件，因此可將零件檢測特征群矩陣整體作為遺傳算法的基因編碼。另外，遺傳算法與傳統的優化方法(枚舉、啟發式等)相比較，在求解復雜問題時具有收斂性好、計算時間短、魯棒性高等優點[10]，因此本文選用遺傳算法進行求解。

圖1所示為基于三坐標測量機的零件特征檢測路徑規劃流程，檢測人員首先根據零件幾何結構、檢測要求和三坐標測量機的特點建立零件檢測特征群矩陣，獲取相關檢測初始信息，建立優化評價目標函數；然后利用矩陣交叉遺傳算法求解劃分檢測特征群；最后利序列規劃遺傳算法順序優化所獲得的每個檢測特征群，從而形成最終的優化規劃檢測路徑。

圖1　基于三坐標測量機的零件特征檢測路徑規劃流程

4適應度函數構造

為了獲得質量比較高的檢測路徑規劃，需要構造一個優化目標函數來度量不同檢測路徑規劃方案的優劣。

4.1檢測工作平面、更換測頭及測針變動次數

對于某一個檢測特征群Gj={…Fm，Fm+1…}，j=1,2,…，s，如果Φ(Pm,,)=Φ(Pm+1,,)，則令αi=1，反之則令αi=0；同理，如果Φ(,Am,)=Φ(,Am+1,)，則令βi=1，反之則令βi=0；如果Φ(,,Mm)=Φ(,,Mm+1)，則令γi=1，反之則令γi=0。其中i=1，2，…，ki。則整個特征群進行檢測時需要改變檢測工作平面、更換測頭及測針的次數之和可表示為

n(G)=n(P)+n(A)+n(M)=

(3)

式中,n(P)、n(A)、n(M)分別為所有檢測特征群改變檢測工作平面、更換測頭及測針的次數之和。

顯然n(G)越小，完成特征序列檢測時需要調整檢測角度、更換檢測測頭和測針的次數越少，三坐標測量機的損耗越小，檢測輔助時間越短。

4.2檢測特征間行走路徑

為了便于統計檢測特征之間的行走路徑，本文根據自動規劃的要求作如下簡化約定：①不管檢測哪一個的特征，檢測開始點均從該檢測特征工作平面的設定安全距離處開始；②任一特征檢測完畢后返回安全距離處再開始下一特征檢測；③檢測平面特征時，只計算安全距離處到達檢測平面法向量上行走的距離；④圓柱、圓錐、圓孔、檢測時，以其中心軸心與頂面的交點作為檢測控制點進行計算；⑤球特征以球心作為檢測控制點進行計算，盡管實際檢測時可能存在干涉；⑥更換工作平面時，行走距離增加原工作平面及新工作平面的安全距離之和。

那么，對于某一個檢測特征群序列Gj={…Fm，Fm+1…}，記特征Fm的檢測來回距離為d(Fm)，工作平面的安全距離為ds(假定每個工作平面的安全距離一致，實際檢測時按零件幾何結構設置)。更換測頭的距離比較遠，一般也是因為工藝和檢測要求需要，是必須行走的距離，因此不計入統計之中。則該特征群序列的總的檢測行走距離為

(4)

顯然，d(Gj)越小，遍列檢測特征群Gj行走距離最短，檢測過程中浪費的時間就最少。

4.3評價優化目標函數

根據第3節所述思路，在評價檢測路徑規劃質量的過程中，當優化求解檢測特征群劃分問題(宏觀)時，采用式(3)作為優化目標函數。為了使特征群的劃分更接近工程實際，劃分時要防止兩種傾向，一是所有檢測特征抱成一團，不作任何劃分，全部放在一個群中；二是防止過度劃分，一個檢測特征單獨劃分為一個群。這兩種現象，均失去了劃分的意義，因此在劃分時，對這兩種現象均應作適當懲罰。即當s=1和s=n時，n(G)=n(G)+ζ，ζ為懲罰系數，一般取劃分特征總數的2～3倍，這里取ζ=50。

當優化求解每個檢測特征群內的特征的檢測先后順序的問題(微觀)時，采用式(4)作為優化目標函數。在輸出最終檢測路徑時應注意相鄰兩劃分特征群的先后順序，必需綜合考慮前一檢測群內最后一個特征的坐標位置和后一檢測群內第一個特征的坐標位置，選擇路徑距離較短的檢測群作為后續檢測序列。

5遺傳算法操作

5.1矩陣交叉遺傳算法

(2)交叉重組[11]。為了保證種群的交叉效果，采用兩點部分列交叉并移位重組方法。隨機在兩交叉的染色體中選擇一個交配區域，如兩父代染色體及交配區域選定為A、B，然后將B的交配區域加到A的前面，A交配區域加到B的前面，再順次后移即得到兩子代染色體A′和B′，具體過程如圖2所示。這種方法的優點是無需考慮父代染色體情況，獲得的子代均會有一定程度的變異效果，有利于保持種群的多樣化。

圖2　兩點部分列交叉并移位重組方法示意圖

(3)變異技術。在設定的變異概率Pm下進行變異操作，一旦發生變異，即隨機產生兩個互換列的位置，對染色體的該兩列進行互換，互換次數也隨機產生。

5.2序列規劃遺傳算法

(1)編碼。以檢測特征群中檢測特征的序號作為種群染色體的基因編碼，種群的初始生成、交叉及變異操作保證檢測特征群中各檢測特征的序號只能出現一次，不得重復出現。

(2)交叉重組。采用如下的部分交叉重組方法[12]：①隨機在種群染色體中選擇一個交配區域，如兩父染色體及交配區域選定為

A=1 2 | 3 4 5 6 | 7 8 9

B=9 8 | 7 6 5 4 | 3 2 1

②將B的交配區域加到A的前面或后面，A的交配區域加到B的前面或后面得

A′=7 6 5 4 | 1 2 3 4 5 6 7 8 9

B′=3 4 5 6 | 9 8 7 6 5 4 3 2 1

③在A′中自交配區域后依次刪除與交配區相同的零部件編碼，得到最終的兩子染色體為

A″=7 6 5 4 1 2 3 8 9

B″=3 4 5 6 9 8 7 2 1

與其他方法相比，這種方法在兩父染色體相同的情況下仍能產生一定程度的變異效果，這對維持群體內的多樣化有一定的作用。交叉概率定為Pc。

(3)變異技術。每一代種群以變異概率Pm進行變異，一旦變異操作發生，則用隨機方法產生交換次數K，對所需變異操作的染色體基因進行K次對換(對換的兩基因位也是隨機產生的)。

6應用實例分析

為盡可能多地體現各類測量特征，以Hexagon公司提供的測量零件為例，說明特征檢測的路徑規劃過程。使用的三坐標測量機為Hexagon Global Classic SR 071007，配德國Leize公司LSP-X1C固定式掃描測頭，裝有三工位吸盤更換架，可裝有90°、五方位、60°斜角吸盤，使用測針均為φ3 mm測針，如圖3所示。圖4為零件三維結構圖，其特征信息如表1所示。該零件有外圓柱、外圓錐、外球、曲面、內圓柱、內圓錐、內球，覆蓋+Z、+X、-X、+Y、-Y5個工作面，為了減少測頭更換次數，主檢測測頭使用五方位吸盤，次檢測測頭使用60°斜角吸盤，根據測量要求一次性裝好。

(a)使用儀器

(b)LSP-X1C固定式掃描測頭圖3　零件檢測現場

圖4　零件三維結構圖(各特征信息見表1)

表1為檢測初始信息表，各工作面的安全距離均設為40 mm，測針直徑均為3 mm;零件三維輪廓尺寸分別為：lx=256 mm，ly=108 mm，lz=60 mm。根據第5節所述的遺傳算法操作方案，采用Borland C++編寫了算法原型程序。在種群大小為100，交叉概率為0.85，變異概率為0.15時，矩陣交叉遺傳算法于214代收斂，獲得最佳特征群劃分結果(因為是順序解析，所以特征群內特征的順序不代表檢測順序)：

(1 2 3 4 6 7 8 9 10 12 14 15 17 18 19 20)，

(16)，(11)，(5)，(13)

表1　零件初始信息表

再將特征群劃分結果輸入序列規劃遺傳算法，在種群大小為100，交叉概率為0.55，變異概率為0.45時，算法于360代收斂，獲得最優檢測順序如下：

20→1→19→18→17→15→14→12→10→8→

9→7→6→4→3→2→5→11→16→13

表2為優化路徑與幾種典型檢測路徑的對比分析表。三坐標測機開機后需要進行測頭校準，角度吸盤需在+Z方向校核完成的基礎上再進行校核，另外在進行特征檢測之前需要建立手工和DCC坐標系，必須由帶有+Z方向測針的吸盤完成，因此在完成上述過程后正式進行特征檢測時，三坐標上的吸盤是帶有+Z方向的吸盤，本例中即為五方位吸盤，此時直接進行角度特征檢測，會增加吸盤更換的次數。由表2可看出，本文算法優化獲得的結果在更換吸盤次數、檢測工作平面變動次數及測頭行走距離上均具有較大的優勢，說明本文優化結果與工程實際情況基本吻合，算法具有較好的普適性和工程應用價值。

7結語

零件檢測特征群模型和求解流程揭示了零件特征檢測路徑規劃的本質，規劃人員可根據檢測批量和檢測要求，結合使用三坐標儀器現狀，有側

表2　優化檢測路徑與幾種典型路徑的對比分析

重地提取零件檢測初始信息，如檢測角度變化對檢測精度影響大，更換檢測測頭效率低時，應偏重于檢測特征群的合理劃分，否則應偏重于檢測路徑的距離，在難以取舍時應兩者并重，利用矩陣交叉遺傳算法求解零件檢測特征群，再利用序列規劃遺傳算法求解群內特征的檢測順序。實踐證明該方法快速有效，且具有較高的工程應用價值。

參考文獻：

[1]AinsworthI，RisticM,BrujicD.CAD-basedMeasurementPathPlanningforFreeformShapesUsingContactProbes[J].InternationalJournalofAdvancedManufacturingTechnology, 2000, 16:23-31.

[2]LeeHonghee,Myeong-WooC,Gil-SangY,etal.AComputer-aidedInspectionPlanningSystemforOn-machineMeasurement-PartI:GlobalInspectionPlanning[J].KSMEInternationalJournal, 2004, 18(8):1349-1357.

[3]AlbuquerqueVA,LiouFW,MitchellOR.InspectionPointPlacementandPathPlanningAlgorithmsforAutomaticCMMInspection[J].InternationalJournalofComputerIntegratedManufacturing, 2000, 13(2):107-120.

[4]ZhangSG,AjmalA,WoottonJ,etal.AFeature-basedInspectionProcessPlanningSystemforCo-ordinateMeasuringMachine(CMM)[J].JournalofMaterialsProcessingTechnology, 2000, 107:111-118.

[5]LuCG,MortonD,WuMH,etal.GeneticAlgorithmModelingandSolutionofInspectionPathPlanningonaCoordinateMeasuringMachine(CMM)[J].TheInternationalJournalofAdvancedManufacturingTechnology, 1999, 15:409-416.

[6]紀小剛，龔光容. 三坐標測量機中基于遺傳算法的多特征測量路徑規劃研究[J]. 兵工學報, 2005,26(3):392-396.

JiXiaogang,GongGuangrong.GeneticAlgorithmBasedMulti-characterInspectionPathPlanninginCoordinateMeasuringMachines[J].AcatArmamentarii, 2005, 26(3):392-396.

[7]王世剛. 基于CMM測量路徑優化算法的研究[J]. 機械科學與技術, 2005，24(5):606-608.

WangShigang.ResearchonCMM-basedAlgorithmofMeasurementPathOptimization[J].MechanicalScienceandTechnology, 2005, 24(5):606-608.

[8]方憶湘，楊克強，黃風山.CMM測量中復雜零件的路徑規劃研究[J]. 制造業自動化, 2013，35(3):36-40.

FangYixiang,YangKeqiang,HuangFengshan.ResearchaboutComplexPartsMeasuringPathPlanningofCMM[J].ManufacturingAutomation, 2013, 35(3):36-48.

[9]黃風山，方憶湘，姜騰，等. 規則約束和蟻群算法三坐標測量路徑規劃研究[J]. 機械設計與制造, 2014(9):201-204.

HuangFengshan,FangYixiang,JiangTeng,etal.InspectionPathPlanningBasedonRulesandAntColonyAlgorithmforCoordinateMeasuringMachine[J].MachineryDesignandManufacture, 2014(9):201-204.

[10]邢文訓，謝金星. 現代優化計算方法[M]. 北京：清華大學出版社，2001.

[11]周開俊，貢智兵，童一飛. 面向再設計的產品模塊劃分方法[J]. 中國機械工程， 2015，26(15):2096-2102.

ZhouKaijun,GongZhibing,TongYifei.AModulePartitionMethodforProductRedesign[J].ChinaMechanicalEngineering,2015,26(15):2096-2102.

[12]周開俊，李東波，黃希. 基于遺傳算法的裝配序列規劃方法[J]. 機械設計，2006，23(2)：30-32.

ZhouKaijun,LiDongbo,HuangXi.AssemblySequencePlanningBasedonGeneticAlgorithm[J].JournalofMachineDesign, 2006，23(2)：30-32.

(編輯袁興玲)

收稿日期：2015-08-25

基金項目：江蘇省青藍工程資助項目(2014)；南通市科技計劃資助項目(CP22013002，BK2014027)

中圖分類號：TP391

DOI：10.3969/j.issn.1004-132X.2016.12.012

作者簡介：周開俊，男，1974年生。南通職業大學機械工程學院副教授、博士。主要研究方向為先進制造技術等。獲省部級科技進步二等獎1項。發表論文20余篇。肖軼，男，1980年生。南通職業大學機械工程學院副教授，博士。周小青，男，1974年生。南通職業大學機械工程學院副教授，博士。

AMethodforCMMInspectionPathPlanningBasedonGA

ZhouKaijunXiaoYiZhouXiaoqing

NantongVocationalUniversity,Nantong，Jiangsu，226007

Abstract:In order to improve the defects in present methods of CMM inspection path planning, a part measuring feature group model and solution processes were proposed. Then according to the characteristics of the mathematical model, a fitness function module was constructed based on the changing times of working planes, inspection angles, checking probe and the distance of detection paths. From macro and micro angles, the matrix crossover GA and sequence planning optimization GA were applied for solving optimization of inspection path planning. Finally, taking testing part of Hexagon Company for an example, the part initial checking data was acquired as well as the optimization algorithm for solving process was described. Practice proved that this method is fast and effective with good engineering application values.

Key words:coordinate measuring machine(CMM); inspection path planning; genetic algorithm(GA); matrix-cross; sequence planning