畢業(yè)設計（論文）設計題目數(shù)控PCB鉆機最短路徑計算所屬院（系）電子信息工程2012年06月14目錄摘要IIIABSTRACTIV第一章鉆孔機111PCB鉆孔機結構介紹1111數(shù)控機床的介紹1112數(shù)控機床的組成部分112PCB鉆孔機用途介紹2121PCB的概念2122數(shù)控機床的特點2123PCB在各種電子設備中有如下功能3第二章最短路徑相關知識421圖4211圖的定義及基本術語4212圖的存儲結構5213圖的遍歷5214圖的應用單源最短路徑622最短路徑問題7221最短路徑7222算法具體的形式723最短路徑的思想及算法7231求最短路徑的算法思想7232從源點到各終點的最短路徑的算法描述如下8233求以V0為源點的最短路徑算法如下8第三章幾種最短路徑算法的介紹1331求網(wǎng)絡圖形最短路徑的問題上的算法13311路徑算法13312最常用的路徑算法13313統(tǒng)一的歸納總結與分析比較1332幾種主要的最短路徑算法的介紹13321DIJKSTRA算法13322FLOYED算法20323遺傳算法23第四章基于遺傳算法的最短路徑的實現(xiàn)3441PCB鉆孔走刀路徑的最短路徑問題的引入3442最佳走刀路徑模型的建立3443遺傳算法及走刀路徑算法沒計35431遺傳算法概述35432走刀路徑優(yōu)化算法設計36433染色體編碼方式36434適應度函數(shù)36435選擇算子37436交叉算子37437變異算子3744走刀路徑優(yōu)化算法流程38總結40參考文獻41致謝42摘要印刷電路板PRINTEDCIRCUITBOARD，PCB是電子設備中最重要的組成部分之一。而PCB的鉆孔工序是PCB制造過程中重要的一個環(huán)節(jié)。其中鉆孔路徑即走刀的路徑是否最短對于提高加工效率來說是至關重要的。而現(xiàn)有的PCB設計軟件雖然具有自動生成鉆孔NC程序的功能，但是其生成的走刀路徑并非最短路徑。這樣會影響加工效率。PCB鉆孔走刀最短路徑問題可以簡化為旅行商TRAVELSALESMANPROBLEM，TSP問題。旅行商問題，即TSP問題（TRAVELINGSALESMANPROBLEM）又譯為旅行推銷員問題、貨郎擔問題，是數(shù)學領域中著名問題之一。遺傳算法GENETICALGORITHM是解決這類問題的一個非常實用的算法。采用遺傳算法可以快速而有效地找到全局最優(yōu)解，極大地減少運算量，能夠很好地解決PCB鉆孔走刀的最短路徑問題。目前，已經(jīng)有一些學者做過關于用遺傳算法解決PCB鉆孔走刀的最短路徑問題的現(xiàn)有的研究中，并沒有很好地根據(jù)數(shù)控鉆床鉆頭的運動特點確定目標函數(shù)，并且沒有就算法中變異算子以及變異概率對路徑最短結果的影響進行進一步的闡述。本文在采用遺傳算法解決走刀的最短路徑問題的基礎上，對上述問題進行了更詳細的論述和分析，使遺傳算法更加符合數(shù)控鉆機走刀路徑的特點，從而得到最短路徑。關鍵字PCB數(shù)控鉆機，最短路徑算法，DIJKSTRA算法，F(xiàn)LOYED算法，遺傳算法。ABSTRACTPRINTEDCIRCUITBOARDPCBMARITIMEBOARD,THEVEHICLEISTHEELECTRONICEQUIPMENTINTHEMOSTIMPORTANTPARTOFANDPCBDRILLINGPROCESSISPCBMANUFACTURINGPROCESSIMPORTANTLINKSAMONGTHEMISDRILLINGPATHTOOLPATHTOIMPROVEMANUFACTURINGEFFICIENCYOPTIMIZATIONOFITISOFVITALIMPORTANCEWHILETHEEXISTINGPCBDESIGNSOFTWAREALTHOUGHHASTHEAUTOMATICGENERATIONOFDRILLINGNCPROGRAMFUNCTION,BUTITSGENERATIONTOOLPATHISNOTTHEBESTPATHTHISWILLAFFECTMACHININGEFFICIENCYFORMASSPRODUCTION,THEMANUFACTURERFOR,ITSINFLUENCEISQUITEOBVIOUSPCBDRILLINGTOOLPATHCANSIMPLIFYTHEOPTIMIZATIONPROBLEMFORTRAVELINGSALESMANSALESMAN,TSPMYPROMOTIONTHETSPPROBLEMISANEASYTODEFINEBUTDIFFICULTTODEALWITHPROBLEMS,ISNPCOMPLETEPROBLEMSGENETICALGORITHMGENETICDONETOSOLVETHISKINDOFPROBLEMISAVERYPRACTICALALGORITHMKEYWORDSPCBDRILLINGMACHINE,ASHORTESTPATHALGORITHM,DIJKSTRAALGORITHM，F(xiàn)LOYEDALGORITHM,GENETICALGORITHM第一章鉆孔機11PCB鉆孔機結構介紹111數(shù)控機床的介紹數(shù)控機床是數(shù)字控制機床（COMPUTERNUMERICALCONTROL）的簡稱，是一種裝有程序控制系統(tǒng)的自動化機床。該控制系統(tǒng)能夠邏輯地處理具有控制編碼或其他符號指令規(guī)定的程序，并將其譯碼，從而使機床動作并加工零件。圖11PCB鉆孔機112數(shù)控機床的組成部分1主機，它他是數(shù)控機床的主體，包括機床身、立柱、主軸、進給機構等機械部件。它是用于完成各種切削加工的機械部件。2數(shù)控裝置，是數(shù)控機床的核心，包括硬件（印刷電路板、CRT顯示器、鍵盒、紙帶閱讀機等）以及相應的軟件，用于輸入數(shù)字化的零件程序，并完成輸入信息的存儲、數(shù)據(jù)的變換、插補運算以及實現(xiàn)各種控制功能。3驅動裝置，它是數(shù)控機床執(zhí)行機構的驅動部件，包括主軸驅動單元、進給單元、主軸電機及進給電機等。它在數(shù)控裝置的控制下通過電氣或電液伺服系統(tǒng)實現(xiàn)主軸和進給驅動。當幾個進給聯(lián)動時，可以完成定位、直線、平面曲線和空間曲線的加工。4輔助裝置，指數(shù)控機床的一些必要的配套部件，用以保證數(shù)控機床的運行，如冷卻、排屑、潤滑、照明、監(jiān)測等。它包括液壓和氣動裝置、排屑裝置、交換工作臺、數(shù)控轉臺和數(shù)控分度頭，還包括刀具及監(jiān)控檢測裝置等等。5編程及其他附屬設備，可用來在機外進行零件的程序編制、存儲等等。12PCB鉆孔機用途介紹121PCB的概念PCB為PRINTEDCIRCUITBOARD印制板1936年，英國EISLER博士提出印制電路（PRINTEDCIRCUIT）這個概念。他首創(chuàng)在絕緣基板上全面覆蓋金屬箔，在其金屬箔上涂上耐蝕刻油墨后再將不需要的金屬箔腐蝕掉的PCB制造基本技術。1942年，EISLER博士制造出世界上第一塊紙質層壓絕緣基板，用于收音機的印制板。122數(shù)控機床的特點數(shù)控機床的操作和監(jiān)控全部在這個數(shù)控單元中完成，它是數(shù)控機床的大腦。與普通機床相比，數(shù)控機床有如下特點1加工精度高，具有穩(wěn)定的加工質量；2可進行多坐標的聯(lián)動，能加工形狀復雜的零件；3加工零件改變時，一般只需要更改數(shù)控程序，可節(jié)省生產(chǎn)準備時間；4機床本身的精度高、剛性大,可選擇有利的加工用量，生產(chǎn)率高（一般為普通機床的35倍）；5機床自動化程度高，可以減輕勞動強度；6對操作人員的素質要求較高，對維修人員的技術要求更高。123PCB在各種電子設備中有如下功能1提供集成電路等各種電子元器件固定、裝配的機械支撐。2實現(xiàn)集成電路等各種電子元器件之間的布線和電氣連接（信號傳輸）或電絕緣。提供所要求的電氣特性，如特性阻抗等。3為自動裝配提供阻焊圖形，為元器件插裝、檢查、維修提供識別字符和圖形。PCB數(shù)控鉆銑床是一種典型的點位運動控制系統(tǒng)，是印制電路板精密導通孔加工的關鍵設備。隨著電子產(chǎn)品向微型化、小型化方向發(fā)展，印制電路板對導通孔的孔徑、線寬、線距的要求越來越高。相應地，PCB數(shù)控系統(tǒng)正朝高速、高精度、高可靠性、系統(tǒng)集成化、柔性化、智能化程度高的開放式方向發(fā)展。第二章最短路徑相關知識21圖211圖的定義及基本術語1定義1圖圖是有頂點集合V和頂點之間關系集合R組成，記作GV,R其中V是圖中頂點的非空有窮集合,VV1,V2,VNR是兩個頂點之間關系的集合,它是定點的有序或無序對,記作或2無向圖當圖中頂點之間的關系為無序對時稱為無向圖無序對稱為邊EEDGE無向圖記作GV,E3有向圖當圖中頂點之間的關系為有序對時稱為有向圖。稱為有向圖中一條弧AARC稱VI為弧尾或初始點,稱VJ為弧頭或終端點,和是表示不同的弧有向圖記作GV,A2有關圖的基本術語1子圖假如有兩個圖GV，E和GV，E，如果滿足V包含于V且E包含于E，則稱圖G為G的子圖2度在無向圖中，與某個頂點相連的邊的數(shù)目稱為該頂點的度。在有向圖中，以某個頂點為初始點的弧的數(shù)目，稱為該頂點的出度。以某個頂點為終端的弧數(shù)目稱為該頂點的入度。（3）路徑和回路在無向圖中，從頂點VP到頂點VQ的路徑是頂點序列VP,VIL，VI2,VIK,VIQ且（VP，VI1）VIK,VIQ均是E中的邊。在有向圖，則由頂點的弧組成有向路徑路徑。路徑上的邊或弧的數(shù)目稱為路徑長度。網(wǎng)絡的路徑長度定義為路徑上權值的和。除第一個和最后一個頂點外，序列中其余頂點各不相同的路徑稱為簡單路徑。第一個頂點和最后一個頂點相同的簡單路徑稱為簡單回路。（4）連通圖和連通分量在無向圖中，如果從VI到VJ存在有路徑，則稱VI和VJ是連通的。若在頂點集合V中每一對不同頂點VI和VJ都連通，稱G為連通圖。否則，將其中的極大連通子圖稱為連通分量。212圖的存儲結構1鄰接矩陣存儲結構11有向圖的鄰接矩陣具有N個頂點的有向圖可以用一個NN的方形矩陣表示。假設該矩陣的名稱為M，則當是該有向圖中的一條弧時，MI,J1；否則MI,J0。第I個頂點的出度為矩陣中第I行中“1“的個數(shù)；入度為第I列中“1“的個數(shù)，并且有向圖弧的條數(shù)等于矩陣中“1“的個數(shù)。12無向圖的鄰接矩陣具有N個頂點的無向圖也可以用一個NN的方形矩陣表示。假設該矩陣的名稱為M，則當（VI,VJ）是該無向圖中的一條邊時，MI,JMJ,I1；否則，MI,JMJ,J0。第I個頂點的度為矩陣中第I行中“1“的個數(shù)或第I列中“1“的個數(shù)。圖中邊的數(shù)目等于矩陣中“1“的個數(shù)的一半，這是因為每條邊在矩陣中描述了兩次2鄰接表鄰接表是圖的一種鏈式存儲結構，在鄰接表中，對圖中每個頂點建立一個單鏈表，第I個單鏈表中的節(jié)點表示依附于頂點VI的邊，每個鏈結點由三部分組成鄰接域（ADJVEX）表示與是頂點VI鄰接的點的序號，鏈域NEXTARE表示下一條邊或弧的結點，數(shù)據(jù)域（DATA）存儲和邊或弧相關的信息，如權值等。213圖的遍歷常見的圖遍歷方式有兩種深度優(yōu)先遍歷和廣度優(yōu)先遍歷，這兩種遍歷方式對有向圖和無向圖均適用。（1）深度優(yōu)先遍歷深度優(yōu)先遍歷的基本思想是從圖的某一個頂點V0出發(fā)進行遍歷，首先訪問起始點V0，然后依次從V0的未被訪問的鄰接點出發(fā)繼續(xù)深度優(yōu)先遍歷圖中的其余頂點，直至圖中所有與V0有路徑相通的頂點都被訪問完為止。對于無向圖，這個算法可以遍歷到V頂點所在的連通分量中的所有頂點，而與V頂點不在一個連通分量中的所有頂點遍歷不到；而對于有向圖可以遍歷到起始頂點V0能夠到達的所有頂點。若希望遍歷到圖中的所有頂點，就需要在上述深度優(yōu)先遍歷算法的基礎上，增加對每個頂點訪問狀態(tài)的檢測（2）廣度優(yōu)先遍歷對圖的廣度優(yōu)先遍歷的基本思想是首先訪問初始點VI，并將其標記為已訪問過，接著訪問VI的所有未被訪問過的鄰接點VI1,VI2,VIK，并均標記已訪問過，然后再按照VI1,VI2,VIK的次序，訪問每一個頂點的所有未被訪問過的鄰接點，并均標記為已訪問過，依次類推，直到圖中所有和初始點VI有路徑相通的頂點都被訪問過為止。實現(xiàn)廣度優(yōu)先遍歷算法需要考慮的幾個問題（1）在廣度優(yōu)先遍歷中，要求先被訪問的頂點其鄰接點也被優(yōu)先訪問，因此，必須對每個頂點的訪問順序進行記錄，以便后面按此順序訪問各頂點的鄰接點。應利用一個隊列結構記錄頂點訪問順序，就可以利用隊列結構的操作特點，將訪問的每個頂點入隊，然后，再依次出隊，并訪問它們的鄰接點；（2）在廣度優(yōu)先遍歷過程中同深度優(yōu)先遍歷一樣，為了避免重復訪問某個頂點，也需要創(chuàng)建一個一維數(shù)組VISITED0N1（N是圖中頂點的數(shù)目），用來記錄每個頂點是否已經(jīng)被訪問過。214圖的應用單源最短路徑1單源最短路徑的問題背景單源元最短路徑的問題背景從一個給定的城市出發(fā)，能否到達其他各城市，走那幾條公路花費最少，我們用一個有向網(wǎng)表示城市的公路網(wǎng)，頂點表示城市，弧代表公路段，弧上的權值代表兩城市的距離，或運輸所需的代價。習慣上稱給定的出發(fā)點為原點，其其他的點稱為終點。單元最短路徑問題一般提法是從有向網(wǎng)的原點到其他各終點是否有路徑最短路徑是什么最短路徑的長度是多少2我們可以發(fā)現(xiàn)有這樣一個事實如果P是G中從VS到VJ的最短路，VI是P中的一個點，那么，從VS沿P到VI的路是從VS到VI的最短路。3從原點到終點的最短路徑有三種情況（1）沒有路徑；（2）只有一條路徑，即位最短路徑；（3），有幾條路徑，其中有一條為最短路徑。4所謂單源最短路徑問題是指已知圖G（V，E），我們希望找出從某給定的源結點SV到V中的每個結點的最短路徑。22最短路徑問題221最短路徑最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結點和路徑組成的中兩結點之間的最短路徑。222算法具體的形式算法具體的形式包括1確定起點的最短路徑問題即已知起始結點，求最短路徑的問題。2確定終點的最短路徑問題與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的確定起點的問題。3確定起點終點的最短路徑問題即已知起點和終點，求兩結點之間的最短路徑。4全局最短路徑問題求圖中所有的最短路徑。23最短路徑的思想及算法231求最短路徑的算法思想先找出從原點到各終點的直達路徑，即通過一條弧到達的路徑。從這些路徑中找出一條最短的路徑最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。算法具體的形式包括確定起點的最短路徑問題即已知起始結點，求最短路徑的問題。確定終點的最短路徑問題與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的確定起點的問題。確定起點終點的最短路徑問題即已知起點和終點，求兩結點之間的最短路徑。全局最短路徑問題求圖中所有的最短路徑。，然后對其余各條路徑做適當調(diào)整。232從源點到各終點的最短路徑的算法描述如下1設AS1N,1N為有向網(wǎng)的帶權鄰接矩陣，ASI,J表示弧上的權值，若不存在，則ASI,J為無窮。DIST1N為各終點當前找到的最短路徑的長度，它的初始值為DISTIASV0，I2選擇U,使得DISTUMINDISTW/W不屬于S，W屬于VSS并U其中V為有向圖的頂點集。3對于所有不在S中的終點W，若DISTUASU,WDI,KDK,JTHENDI,JDI,KDK,JC算法結束D即為所有點對的最短路徑矩陣算法過程把圖用鄰接矩陣G表示出來，如果從VI到VJ有路可達，則GI,JD，D表示該路的長度；否則GI,J空值。定義一個矩陣D用來記錄所插入點的信息，DI,J表示從VI到VJ需要經(jīng)過的點，初始化DI,JJ。把各個頂點插入圖中，比較插點后的距離與原來的距離，GI,JMINGI,J,GI,KGK,J，如果GI,J的值變小，則DI,JK。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。比如，要尋找從V5到V1的路徑。根據(jù)D，假如D5,13則說明從V5到V1經(jīng)過V3，路徑為V5,V3,V1，如果D5,33，說明V5與V3直接相連，如果D3,11，說明V3與V1直接相連。時間復雜度ON3優(yōu)缺點分析FLOYD算法適用于APSPALLPAIRSSHORTESTPATHS，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權可正可負。此算法簡單有效，由于三重循環(huán)結構緊湊，對于稠密圖，效率要高于執(zhí)行|V|次DIJKSTRA算法。優(yōu)點容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單；缺點時間復雜度比較高，不適合計算大量數(shù)據(jù)。VIEWPLAINCOPYTOCLIPBOARDPRINTINCLUDEUSINGNAMESPACESTDCONSTINTN101CONSTINTMAX32767INTMAPNNINTMAININTNINTI,J,KINTASKX,ASKYCINNCINASKXASKYFORI1IMAPIJIFMAPIJ0MAPIJMAXFORK1KFLOYDWARSHALL算法用來找出每對點之間的最短距離。它需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。編輯本段算法概述單獨一條邊的路徑也不一定是最佳路徑。從任意一條單邊路徑開始。所有兩點之間的距離是邊的權，或者無窮大，如果兩點之間沒有邊相連。對于每一對頂點U和V，看看是否存在一個頂點W使得從U到W再到V比己知的路徑更短。如果是更新它。不可思議的是，只要按排適當，就能得到結果。/DISTI,J為從節(jié)點I到節(jié)點J的最短距離FORI1TONDOFORJ1TONDODISTI,JWEIGHTI,JFORK1TONDO/K為“媒介節(jié)點”一定要先枚舉媒介節(jié)點FORI1TONDOFORJ1TONDOIFDISTI,KDISTK,J上的權值。若不存在，則置EDGESIJ（計算機上用一個允許的最大值代替）。S為已經(jīng)找到的從VS出發(fā)的最短路徑的終點的集合，它的初始化為空集。那么，從VS出發(fā)到圖上其余各頂點VI可能達到的最短路徑長度的初值為DIEDGESSIVIV2選擇VJ，使得DJMINDI|VIVS，VJ就是當前求得的一條從VS出發(fā)的最短路徑的終點。令SSVJ3修改從VS出發(fā)到集合VS上任一頂點VK可達的最短路徑長度。如果DJEDGESJKMAXINTTHENDIPREXELSEDIPRE0ENDAX,X1REPEAT每循環(huán)一次加入一個離1集合最近的結點并調(diào)整其他結點的參數(shù)MINMAXINTU0U記錄離1集合最近的結點FORI1TONDOIFAI,I0ANDDILEN0THENBEGINAU,U1FORI1TONDO修正第二組中U可達的頂點距離值IFAI,I0ANDAU,IDULENXANDDILENMAXINT若I與X間有通路，則輸出它們之間的最短距離和路徑方案THENBEGINWRITELNDILENPRINT_DIJIENDWRITELNENDEND322FLOYED算法1FLOYD算法的定義FLOYD算法又稱為弗洛伊德算法，插點法，是一種用于尋找給定的加權圖中頂點間最短路徑的算法。FLOYD算法用來找出每對點之間的最短距離。它需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。注意單獨一條邊的路徑也不一定是最佳路徑。2FLOYD算法的基本思想是從鄰接矩陣A開始進行N次迭代，第一次迭代后AI,J的值是從VI到VJ且中間不經(jīng)過變化大于1的頂點的最短路徑長度；第K次迭代后AI,J的值是從VI到VJ且中間不經(jīng)過變化大于K的頂點的最短路徑長度；第N次迭代后AI,J的值就是從VI到VJ的最短路徑長度。3FLOYD算法的核心思路通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。從圖的帶權鄰接矩陣AAI,JNN開始，遞歸地進行N次更新，即由矩陣D0A，按一個公式，構造出矩陣D1；又用同樣地公式由D1構造出D2最后又用同樣的公式由DN1構造出矩陣DN。矩陣DN的I行J列元素便是I號頂點到J號頂點的最短路徑長度，稱DN為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣PATH來記錄兩點間的最短路徑。由于采用的是松弛技術，對在I和J之間的所有其他點進行一次松弛。所以時間復雜度為ON34FLOYD算法的算法描述1初始化將除源點外的所有頂點的最短距離估計值DV,DS02迭代求解反復對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點V的最短距離估計值逐步逼近其最短距離（運行|V|1次）；3檢驗負權回路判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法返回FALSE，表明問題無解；否則算法返回TRUE，并且從源點可達的頂點V的最短距離保存在DV中。算法語言A初始化DU,VAU,VBFORK1TONFORI1TONFORJ1TONIFDI,JDI,KDK,JTHENDI,JDI,KDK,JC算法結束D即為所有點對的最短路徑矩陣5FLOYD算法的算法過程1把圖用鄰接矩陣G表示出來，如果從VI到VJ有路可達，則GI,JD，D表示該路的長度；否則GI,J空值。2定義一個矩陣D用來記錄所插入點的信息，DI,J表示從VI到VJ需要經(jīng)過的點，初始化DI,JJ。3把各個頂點插入圖中，比較插點后的距離與原來的距離，GI,JMINGI,J,GI,KGK,J，如果GI,J的值變小，則DI,JK。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短路徑的信息。時間復雜度ON36FLOYD算法優(yōu)缺點分析FLOYD算法適用于APSPALLPAIRSSHORTESTPATHS，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權可正可負。此算法簡單有效，由于三重循環(huán)結構緊湊，對于稠密圖，效率要高于執(zhí)行|V|次DIJKSTRA算法。優(yōu)點容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單；缺點時間復雜度比較高，不適合計算大量數(shù)據(jù)。7FLOYD算法最短路徑算法FLOYED算法求解所有可達頂點對之間的最短路徑ON3CONSTN01000VARPARRAY1N0,1N0OF0N0PATH,PI,J表示I到J的最短路徑上J的前驅結點AARRAY1N0,1N0OFINTEGER最短路徑矩陣，圖的輸入略I,J,KINTEGERPROCEDUREFLOYEDBEGINFORI1TONDOFORJ1TONDOIFAI,J0最短路徑矩陣，初始時為有向圖的鄰接矩陣THENPI,JIELSEPI,J0PI,J表示I到J的最短路徑上J的前驅結點FORK1TONDO枚舉中間結點FORI1TONDOFORJ1TONDOIFAI,KAJ,K0THENBEGINPRINT_FLOYEDI,JWRITELNEND323遺傳算法遺傳算法（GENETICALGORITHM）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最短路徑的方法，它最初由美國MICHIGAN大學JHOLLAND教授于1975年首先提出來的，并出版了頗有影響的專著ADAPTATIONINNATURALANDARTIFICIALSYSTEMS，GA這個名稱才逐漸為人所知，JHOLLAND教授所提出的GA通常為簡單遺傳算法（SGA）。1遺傳算法的基本概念遺傳算法（GENETICALGORITHM）是一類借鑒生物界的進化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機制）演化而來的隨機化搜索方法。其主要特點是直接對結構對象進行操作，不存在求導和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導路徑最短的搜索空間，自適應地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質，已被人們廣泛地應用于組合優(yōu)化、機器學習、信號處理、自適應控制和人工生命等領域。它是現(xiàn)代有關智能計算中的關鍵技術。2遺傳算法的數(shù)學規(guī)劃模型對于一個求函數(shù)最小值的優(yōu)化問題求函數(shù)最大值也類同，一般可以描述為下列數(shù)學規(guī)劃模型式中為決策變量，為目標函數(shù)式式12、13為約束條件，U是基本空間，R是U的子集。滿足約束條件的解X稱為可行解，集合R表示所有滿足約束條件的解所組成的集合，稱為可行解集合。3遺傳算法的基本運算過程如下A初始化設置進化代數(shù)計數(shù)器T0，設置最大進化代數(shù)T，隨機生成M個個體作為初始群體P0。B個體評價計算群體PT中各個個體的適應度。C選擇運算將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。D交叉運算；將交叉算子作用于群體。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。E變異運算將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體PT經(jīng)過選擇、交叉、變異運算之后得到下一代群體PT1。F終止條件判斷若TT,則以進化過程中所得到的具有最大適應度個體作為最優(yōu)解輸出，終止計算。4遺傳算法定義遺傳算法是從代表問題可能潛在的解集的一個種群（POPULATION）開始的，而一個種群則由經(jīng)過基因（GENE）編碼的一定數(shù)目的個體INDIVIDUAL組成。每個個體實際上是染色體CHROMOSOME帶有特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（GENERATION）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度（FITNESS）大小選擇（SELECTION）個體，并借助于自然遺傳學的遺傳算子（GENETICOPERATORS）進行組合交叉（CROSSOVER）和變異（MUTATION），產(chǎn)生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（DECODING），可以作為問題近似最優(yōu)解。5遺傳算法特點1遺傳算法從問題解的串集開始嫂索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。2許多傳統(tǒng)搜索算法都是單點搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風險，同時算法本身易于實現(xiàn)并行化。（3）遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應度函數(shù)值來評估個體，在此基礎上進行遺傳操作。適應度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設定。這一特點使得遺傳算法的應用范圍大大擴展。4遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導他的搜索方向。5具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索時，適應度大的個體具有較高的生存概率，并獲得更適應環(huán)境的基因結構。6遺傳算法的應用由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計算是不依賴于梯度信息或其它輔助知識，而只需要影響搜索方向的目標函數(shù)和相應的適應度函數(shù)，所以遺傳算法提供了一種求解復雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于許多科學7遺傳算法的一些主要應用領域1函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應用領域，也是遺傳算法進行性能評價的常用算例，許多人構造出了各種各樣復雜形式的測試函數(shù)連續(xù)函數(shù)和離散函數(shù)、凸函數(shù)和凹函數(shù)、低維函數(shù)和高維函數(shù)、單峰函數(shù)和多峰函數(shù)等。對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結果。2組合優(yōu)化隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優(yōu)解。對這類復雜的問題，人們已經(jīng)意識到應把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法對于組合優(yōu)化中的NP問題非常有效。例如遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。此外，GA也在生產(chǎn)調(diào)度問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。8遺傳算法的現(xiàn)狀進入90年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳算法的應用研究顯得格外活躍，不但它的應用領域擴大，而且利用遺傳算法進行優(yōu)化和規(guī)則學習的能力也顯著提高，同時產(chǎn)業(yè)應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應用研究已從初期的組合優(yōu)化求解擴展到了許多更新、更工程化的應用方面。隨著應用領域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向一是基于遺傳算法的機器學習，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴展到具有獨特的規(guī)則生成功能的嶄新的機器學習算法。這一新的學習機制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓21世紀中新的智能計算技術將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結構的研究都是十分重要的。四是遺傳算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進化規(guī)劃（EVOLUTIONPROGRAMMING,EP）以及進化策略（EVOLUTIONSTRATEGY,ES）等進化計算理論日益結合。EP和ES幾乎是和遺傳算法同時獨立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，即同遺傳算法具有相同之處，也有各自的特點。目前，這三者之間的比較研究和彼此結合的探討正形成熱點。1991年DWHITEY在他的論文中提出了基于領域交叉的交叉算子（ADJACENCYBASEDCROSSOVER），這個算子是特別針對用序號表示基因的個體的交叉，并將其應用到了TSP問題中，通過實驗對其進行了驗證。DHACKLEY等提出了隨機迭代遺傳爬山法（STOCHASTICITERATEDGENETICHILLCLIMBING，SIGH）采用了一種復雜的概率選舉機制，此機制中由M個“投票者”來共同決定新個體的值（M表示群體的大?。?。實驗結果表明，SIGH與單點交叉、均勻交叉的神經(jīng)遺傳算法相比，所測試的六個函數(shù)中有四個表現(xiàn)出更好的性能，而且總體來講，SIGH比現(xiàn)存的許多算法在求解速度方面更有競爭力。HBERSINI和GSERONT將遺傳算法與單一方法（SIMPLEXMETHOD）結合起來，形成了一種叫單一操作的多親交叉算子（SIMPLEXCROSSOVER），該算子在根據(jù)兩個母體以及一個額外的個體產(chǎn)生新個體，事實上他的交叉結果與對三個個體用選舉交叉產(chǎn)生的結果一致。同時，文獻還將三者交叉算子與點交叉、均勻交叉做了比較，結果表明，三者交叉算子比其余兩個有更好的性能。國內(nèi)也有不少的專家和學者對遺傳算法的交叉算子進行改進。2002年，戴曉明等應用多種群遺傳并行進化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題2004年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（BUILDINGBLOCKCODEDPARALLELGA，BCPGA）。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識別出可能的基因塊，然后用基因塊作為新的基因單位對染色體重新編碼，產(chǎn)生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。2005年，江雷等針對并行遺傳算法求解TSP問題,探討了使用彈性策略來維持群體的多樣性,使得算法跨過局部收斂的障礙,向全局最優(yōu)解方向進化。9遺傳算法的一般算法1創(chuàng)建一個隨機的初始狀態(tài)初始種群是從解中隨機選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號人工智能系統(tǒng)的情況不一樣，在那里問題的初始狀態(tài)已經(jīng)給定了。2評估適應度對每一個解染色體指定一個適應度的值，根據(jù)問題求解的實際接近程度來指定以便逼近求解問題的答案。不要把這些“解”與問題的“答案”混為一談，可以把它理解成為要得到答案，系統(tǒng)可能需要利用的那些特性。3繁殖包括子代突變帶有較高適應度值的那些染色體更可能產(chǎn)生后代后代產(chǎn)生后也將發(fā)生突變。后代是父母的產(chǎn)物，他們由來自父母的基因結合而成，這個過程被稱為“雜交”。4下一代如果新的一代包含一個解，能產(chǎn)生一個充分接近或等于期望答案的輸出，那么問題就已經(jīng)解決了。如果情況并非如此，新的一代將重復他們父母所進行的繁衍過程，一代一代演化下去，直到達到期望的解為止。5并行計算非常容易將遺傳算法用到并行計算和群集環(huán)境中。一種方法是直接把每個節(jié)點當成一個并行的種群看待。然后有機體根據(jù)不同的繁殖方法從一個節(jié)點遷移到另一個節(jié)點。另一種方法是“農(nóng)場主/勞工”體系結構，指定一個節(jié)點為“農(nóng)場主”節(jié)點，負責選擇有機體和分派適應度的值，另外的節(jié)點作為“勞工”節(jié)點，負責重新組合、變異和適應度函數(shù)的評估。10術語說明由于遺傳算法是由進化論和遺傳學機理而產(chǎn)生的搜索算法，所以在這個算法中會用到很多生物遺傳學知識，下面是我們將會用來的一些術語說明1染色體CHROMOSOME染色體又可以叫做基因型個體INDIVIDUALS,一定數(shù)量的個體組成了群體POPULATION,群體中個體的數(shù)量叫做群體大小。2基因GENE基因是串中的元素，基因用于表示個體的特征。例如有一個串S1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因ALLELES。3基因地點LOCUS基因地點在算法中表示一個基因在串中的位置稱為基因位置GENEPOSITION，有時也簡稱基因位?；蛭恢糜纱淖笙蛴矣嬎?，例如在串S1101中，0的基因位置是3。4基因特征值GENEFEATURE在用串表示整數(shù)時，基因的特征值與二進制數(shù)的權一致；例如在串S1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。5適應度FITNESS各個個體對環(huán)境的適應程度叫做適應度FITNESS。為了體現(xiàn)染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數(shù)，叫適應度函數(shù)這個函數(shù)是計算個體在群體中被使用的概率。11運算過程遺傳操作是模擬生物基因遺傳的做法。在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務就是對群體的個體按照它們對環(huán)境適應度適應度評估施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進化過程。從優(yōu)化搜索的角度而言，遺傳操作可使問題圖32遺傳運算過程圖的解，一代又一代地優(yōu)化，并逼進最優(yōu)解。遺傳操作包括以下三個基本遺傳算子GENETICOPERATOR選擇SELECTION；交叉CROSSOVER；變異MUTATION。這三個遺傳算子有如下特點個體遺傳算子的操作都是在隨機擾動情況下進行的。因此，群體中個體向最優(yōu)解遷移的規(guī)則是隨機的。需要強調(diào)的是，這種隨機化操作和傳統(tǒng)的隨機搜索方法是有區(qū)別的。遺傳操作進行的高效有向的搜索而不是如一般隨機搜索方法所進行的無向搜索。遺傳操作的效果和上述三個遺傳算子所取的操作概率，編碼方法，群體大小，初始群體以及適應度函數(shù)的設定密切相關。遺傳算法的下幾種適應度比例方法、隨機遍歷抽樣法、局部選擇法。其中輪盤賭選擇法（ROULETTEWHEELSELECTION）是最簡單也是最常用的選擇方法。在該方法中，各個個體的選擇概率和其適應度值成比例。設群體大小為N，其中個體I的適應度為，則I被選擇的概率,為遺傳算法顯然，概率反映了個體I的適應度在整個群體的個體適應度總和中所占的比例個體適應度越大。其被選擇的概率就越高、反之亦然。計算出群體中各個個體的選擇概率后，為了選擇交配個體，需要進行多輪選擇。每一輪產(chǎn)生一個0，1之間均勻隨機數(shù)，將該隨機數(shù)作為選擇指針來確定被選個體。個體被選后，可隨機地組成交配對，以供后面的交叉操作。交叉在自然界生物進化過程中起核心作用的是生物遺傳基因的重組加上變異。同樣，遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。交叉算子根據(jù)交叉率將種群中的兩個個體隨機地交換某些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。根據(jù)編碼表示方法的不同，可以有以下的算法A實值重組（REALVALUEDRECOMBINATION）1離散重組（DISCRETERECOMBINATION）；2中間重組（INTERMEDIATERECOMBINATION）；3線性重組（LINEARRECOMBINATION）；4擴展線性重組（EXTENDEDLINEARRECOMBINATION）。B二進制交叉（BINARYVALUEDCROSSOVER）1單點交叉（SINGLEPOINTCROSSOVER）；2多點交叉（MULTIPLEPOINTCROSSOVER）；3均勻交叉（UNIFORMCROSSOVER）；4洗牌交叉（SHUFFLECROSSOVER）；5縮小代理交叉（CROSSOVERWITHREDUCEDSURROGATE）。最常用的交叉算子為單點交叉ONEPOINTCROSSOVER。具體操作是在個體串中隨機設定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新個體。下面給出了單點交叉的一個例子個體A10011111001000新個體個體B00110000011111新個體變異變異算子的基本內(nèi)容是對群體中的個體串的某些基因座上的基因值作變動。依據(jù)個體編碼表示方法的不同，可以有以下的算法A實值變異；B二進制變異。一般來說，變異算子操作的基本步驟如下A對群中所有個體以事先設定的編譯概率判斷是否進行變異；B對進行變異的個體隨機選擇變異位進行變異。遺傳算法引入變異的目的有兩個一是使遺傳算法具有局部的隨機搜索能力。當遺傳算法通過交叉算子已接近最優(yōu)解鄰域時，利用變異算子的這種局部隨機搜索能力可以加速向最優(yōu)解收斂。顯然，此種情況下的變異概率應取較小值，否則接近最優(yōu)解的積木塊會因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。此時收斂概率應取較大值。遺傳算法中，交叉算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過交叉和變異這對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合是指當群體在進化中陷于搜索空間中某個超平面而僅靠交叉不能擺脫時，通過變異操作可有助于這種擺脫。所謂相互競爭，是指當通過交叉已形成所期望的積木塊時，變異操作有可能破壞這些積木塊。如何有效地配合使用交叉和變異操作，是目前遺傳算法的一個重要研究內(nèi)容?；咀儺愃阕邮侵笇θ后w中的個體碼串隨機挑選一個或多個基因座并對這些基因座的基因值做變動以變異概率P做變動，0，1二值碼串中的基本變異操作如下基因位下方標有號的基因發(fā)生變異。變異率的選取一般受種群大小、染色體長度等因素的影響，通常選取很小遺傳算法的值，一般取000101。終止條件當最優(yōu)個體的適應度達到給定的閥值，或者最優(yōu)個體的適應度和群體適應度不再上升時，或者迭代次數(shù)達到預設的代數(shù)時，算法終止。預設的代數(shù)一般設置為100500代。GA的流程圖GA的流程圖如右圖遺傳算法圖33GA流程圖適應度函數(shù)進化論中的適應度，是表示某一個體對環(huán)境的適應能力，也表示該個體繁殖后代的能力。遺傳算法的適應度函數(shù)也叫評價函數(shù)，是用來判斷群體中的個體的優(yōu)劣程度的指標，它是根據(jù)所求問題的目標函數(shù)來進行評估的。遺傳算法在搜索進化過程中一般不需要其他外部信息，僅用評估函數(shù)來評估個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。由于遺傳算法中，適應度函數(shù)要比較排序并在此基礎上計算選擇概率，所以適應度函數(shù)的值要取正值由此可見，在不少場合，將目標函數(shù)映射成求最大值形式且函數(shù)值非負的適應度函數(shù)是必要的。適應度函數(shù)的設計主要滿足以下條件A）單值、連續(xù)、非負、最大化；B合理、一致性；C）計算量??；D）通用性強。在具體應用中，適應度函數(shù)的設計要結合求解問題本身的要求而定。適應度函數(shù)設計直接影響到遺傳算法的性能。初始群體的選取遺傳算法中初始群體中的個體是隨機產(chǎn)生的。一般來講，初始群體的設定可采取如下的策略A根據(jù)問題固有知識，設法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設定初始群體。B先隨機生成一定數(shù)目的個體，然后從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)達到了預先確定的規(guī)模。第四章基于遺傳算法的最短路徑的實現(xiàn)41PCB鉆孔走刀路徑的最短路徑問題的引入PCB鉆孔走刀路徑的優(yōu)化問題可以簡化為旅行商TRAVELSALESMANPROBLEM，TSP問題。TSP問題是一個容易定義但難于處理的問題，屬于NP完備問題。遺傳算法GENETICALGORITHM是解決這類問題的一個非常實用的算法。采用遺傳算法可以快速有效地找到全局最優(yōu)解，極大地減少運算量，能夠很好地解決PCB鉆孔走刀路徑優(yōu)化的問題。目前，已經(jīng)有一些學者做過關于用遺傳算法解決PCB鉆孔走刀路徑優(yōu)化問題的研究現(xiàn)有的研究中，并沒有很好地根據(jù)數(shù)控鉆床鉆頭的運動特點確定目標函數(shù)，并且沒有就算法中變異算子以及變異概率對優(yōu)化結果的影響進行進一步的闡述。本文在采用遺傳算法解決走刀路徑最短問題的基礎上，對上述問題進行了更詳細的論述和分析，使遺傳算法更加符合數(shù)控鉆床走刀路徑的特點，從而得到更好的優(yōu)化結果。42最佳走刀路徑模型的建立PCB上通常有許多不同直徑的孔，PCB鉆孔問題可以描述為從換刀點出發(fā)，不重復不遺漏地加工完所有同一直徑的孔后回到換刀點進行換刀操作，再加工另一直徑的孔，直到完成所有待加工的孔。所以鉆孔路徑優(yōu)化問題可以按照不同直徑的孔分別進行優(yōu)化處理。對于數(shù)控編程來說，就存在如何選擇加工路徑的問題，最好的加工路徑應該使生產(chǎn)效率最高、空行程時間最短，即最佳的鉆孔路徑。顯然，這一問題可以歸結為旅行商問題，其中鉆頭代表旅行商，待加工的孔表示旅行商途徑的城市，而最佳走刀路線的目標函數(shù)即為刀具的空行程花費時間最短。由于PCB數(shù)控鉆機屬于點位控制的機床，這種機床的刀具由一點運動到另一點的過程中，通常是沿X、Y軸同時移動。當兩點之間的方向距離與Y方向距離不相等的時候，刀具在距離較小的方向上先完成運動，達到某一中間點。然后，在距離較大的方向上，刀具從中間點繼續(xù)向終點運動。例如，刀具由換刀點開始按照1234一5的順序進行加工，再回到換刀點的軌跡如圖1所示。圖41鉆頭運動軌跡示意圖如圖所示，刀具從換刀點開始，先運動到中間點A，然后運動到第一個孔的位置、下鉆，完成鉆孔切削后刀具運動到中間點B，再運動到第二個孔的位置、下鉆，重復上述過程直到刀具回到換刀點。所以刀具在加工中的運動軌跡為折線，而非直接運動到待加工孔的位置。兩點問的空行程的時間為TI,JMAX,其中VX和VY分別為鉆頭在X軸和Y軸方向上的速度，一般來說兩者相等，這樣，對于同一直徑孔的加工，尋找最優(yōu)走刀路徑就可以轉化為找到一個路徑使MAXIXI一XI1L，IYI一YI1L最小的問題，其中I1，2，3，N