周開俊　肖　軼　周小青

南通職業(yè)大學(xué)，南通，226007

?

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

周開俊肖軼周小青

南通職業(yè)大學(xué)，南通，226007

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

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

0引言

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

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

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

1檢測特征群模型的建立

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

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

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

(1)

記為

G=R·F

2檢測初始信息獲取

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

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

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

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

(2)

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

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

3零件特征檢測路徑規(guī)劃流程

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

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

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

4適應(yīng)度函數(shù)構(gòu)造

為了獲得質(zhì)量比較高的檢測路徑規(guī)劃，需要構(gòu)造一個優(yōu)化目標函數(shù)來度量不同檢測路徑規(guī)劃方案的優(yōu)劣。

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

對于某一個檢測特征群Gj={…Fm，F(xiàn)m+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。則整個特征群進行檢測時需要改變檢測工作平面、更換測頭及測針的次數(shù)之和可表示為

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

(3)

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

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

4.2檢測特征間行走路徑

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

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

(4)

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

4.3評價優(yōu)化目標函數(shù)

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

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

5遺傳算法操作

5.1矩陣交叉遺傳算法

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

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

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

5.2序列規(guī)劃遺傳算法

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

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

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

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

②將B的交配區(qū)域加到A的前面或后面，A的交配區(qū)域加到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′中自交配區(qū)域后依次刪除與交配區(qū)相同的零部件編碼，得到最終的兩子染色體為

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

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

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

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

6應(yīng)用實例分析

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

(a)使用儀器

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

圖4　零件三維結(jié)構(gòu)圖(各特征信息見表1)

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

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

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

表1　零件初始信息表

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

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

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

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

7結(jié)語

零件檢測特征群模型和求解流程揭示了零件特征檢測路徑規(guī)劃的本質(zhì)，規(guī)劃人員可根據(jù)檢測批量和檢測要求，結(jié)合使用三坐標儀器現(xiàn)狀，有側(cè)

表2　優(yōu)化檢測路徑與幾種典型路徑的對比分析

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

參考文獻：

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

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

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

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

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

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

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

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

[10]邢文訓(xùn)，謝金星. 現(xiàn)代優(yōu)化計算方法[M]. 北京：清華大學(xué)出版社，2001.

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

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

[12]周開俊，李東波，黃希. 基于遺傳算法的裝配序列規(guī)劃方法[J]. 機械設(shè)計，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年生。南通職業(yè)大學(xué)機械工程學(xué)院副教授、博士。主要研究方向為先進制造技術(shù)等。獲省部級科技進步二等獎1項。發(fā)表論文20余篇。肖軼，男，1980年生。南通職業(yè)大學(xué)機械工程學(xué)院副教授，博士。周小青，男，1974年生。南通職業(yè)大學(xué)機械工程學(xué)院副教授，博士。

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