數(shù)控PCB鉆機(jī)-最短路徑計算

畢業(yè)設(shè)計（論文）設(shè)計題目：數(shù)控PCB鉆機(jī)最短路徑計算所屬院（系）：電子信息工程2012年06月14目錄TOC\o"1-3"\h\z\u摘要 IIIABSTRACT IV第一章鉆孔機(jī) 11.1PCB鉆孔機(jī)結(jié)構(gòu)介紹 11.1.1數(shù)控機(jī)床的介紹 11.1.2數(shù)控機(jī)床的組成部分 11.2PCB鉆孔機(jī)用途介紹 21.2.1PCB的概念 21.2.2數(shù)控機(jī)床的特點(diǎn) 21.2.3PCB在各種電子設(shè)備中有如下功能 3第二章最短路徑相關(guān)知識 42.1圖 42.1.1圖的定義及基本術(shù)語 42.1.2圖的存儲結(jié)構(gòu) 52.1.3圖的遍歷 52.1.4圖的應(yīng)用--單源最短路徑 62.2最短路徑問題 72.2.1最短路徑 72.2.2算法具體的形式 72.3最短路徑的思想及算法 72.3.1求最短路徑的算法思想 72.3.2從源點(diǎn)到各終點(diǎn)的最短路徑的算法描述如下 82.3.3求以V0為源點(diǎn)的最短路徑算法如下： 8第三章幾種最短路徑算法的介紹 133.1求網(wǎng)絡(luò)圖形最短路徑的問題上的算法 133.1.1路徑算法 133.1.2最常用的路徑算法 133.1.3統(tǒng)一的歸納總結(jié)與分析比較 133.2幾種主要的最短路徑算法的介紹 133.2.1Dijkstra算法 133.2.2Floyed算法 203.2.3遺傳算法 23第四章基于遺傳算法的最短路徑的實(shí)現(xiàn) 344.1PCB鉆孔走刀路徑的最短路徑問題的引入 344.2最佳走刀路徑模型的建立 344.3遺傳算法及走刀路徑算法沒計 354.3.1遺傳算法概述 354.3.2走刀路徑優(yōu)化算法設(shè)計 364.3.3染色體編碼方式 364.3.4適應(yīng)度函數(shù) 364.3.5選擇算子 374.3.6交叉算子 374.3.7變異算子 374.4走刀路徑優(yōu)化算法流程 38總結(jié) 40參考文獻(xiàn) 41致謝 42摘要印刷電路板(PrintedCircuitBoard，PCB)是電子設(shè)備中最重要的組成部分之一。而PCB的鉆孔工序是PCB制造過程中重要的一個環(huán)節(jié)。其中鉆孔路徑即走刀的路徑是否最短對于提高加工效率來說是至關(guān)重要的。而現(xiàn)有的PCB設(shè)計軟件雖然具有自動生成鉆孔NC程序的功能，但是其生成的走刀路徑并非最短路徑。這樣會影響加工效率。PCB鉆孔走刀最短路徑問題可以簡化為旅行商(TravelSalesmanProblem，TSP)問題。旅行商問題，即TSP問題（TravelingSalesmanProblem）又譯為旅行推銷員問題、貨郎擔(dān)問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。遺傳算法(Ge—neticAlgorithm)是解決這類問題的一個非常實(shí)用的算法。采用遺傳算法可以快速而有效地找到全局最優(yōu)解，極大地減少運(yùn)算量，能夠很好地解決PCB鉆孔走刀的最短路徑問題。目前，已經(jīng)有一些學(xué)者做過關(guān)于用遺傳算法解決PCB鉆孔走刀的最短路徑問題的現(xiàn)有的研究中，并沒有很好地根據(jù)數(shù)控鉆床鉆頭的運(yùn)動特點(diǎn)確定目標(biāo)函數(shù)，并且沒有就算法中變異算子以及變異概率對路徑最短結(jié)果的影響進(jìn)行進(jìn)一步的闡述。本文在采用遺傳算法解決走刀的最短路徑問題的基礎(chǔ)上，對上述問題進(jìn)行了更詳細(xì)的論述和分析，使遺傳算法更加符合數(shù)控鉆機(jī)走刀路徑的特點(diǎn)，從而得到最短路徑。關(guān)鍵字:PCB數(shù)控鉆機(jī)，最短路徑算法，Dijkstra算法，F(xiàn)loyed算法，遺傳算法。ABSTRACTPrintedCircuitBoard(PCB)maritimeBoard,thevehicleistheelectronicequipmentinthemostimportantpartof.AndPCBdrillingprocessisPCBmanufacturingprocessimportantlinks.Amongthemisdrillingpathtoolpathtoimprovemanufacturingefficiencyoptimizationofitisofvitalimportance.WhiletheexistingPCBdesignsoftwarealthoughhastheautomaticgenerationofdrillingNCprogramfunction,butitsgenerationtoolpathisnotthebestpath.Thiswillaffectmachiningefficiencyformassproduction,themanufacturerfor,itsinfluenceisquiteobvious.PCBdrillingtoolpathcansimplifytheoptimizationProblemfortravelingSalesman(Salesman,TSP)mypromotion.TheTSPproblemisaneasytodefinebutdifficulttodealwithproblems,isNPcompleteproblems.GeneticAlgorithm(Ge-neticdone)tosolvethiskindofproblemisaverypracticalAlgorithm.KeyWords:PCBdrillingmachine,ashortestpathalgorithm,Dijkstraalgorithm，F(xiàn)loyedalgorithm,Geneticalgorithm.第一章鉆孔機(jī)1.1PCB鉆孔機(jī)結(jié)構(gòu)介紹1.1.1數(shù)控機(jī)床的介紹數(shù)控機(jī)床是數(shù)字控制機(jī)床（Computernumericalcontrol）的簡稱，是一種裝有程序控制系統(tǒng)的自動化機(jī)床。該控制系統(tǒng)能夠邏輯地處理具有控制編碼或其他符號指令規(guī)定的程序，并將其譯碼，從而使機(jī)床動作并加工零件。圖1.1PCB鉆孔機(jī)1.1.2數(shù)控機(jī)床的組成部分：1)．主機(jī)，它他是數(shù)控機(jī)床的主體，包括機(jī)床身、立柱、主軸、進(jìn)給機(jī)構(gòu)等機(jī)械部件。它是用于完成各種切削加工的機(jī)械部件。2)．?dāng)?shù)控裝置，是數(shù)控機(jī)床的核心，包括硬件（印刷電路板、CRT顯示器、鍵盒、紙帶閱讀機(jī)等）以及相應(yīng)的軟件，用于輸入數(shù)字化的零件程序，并完成輸入信息的存儲、數(shù)據(jù)的變換、插補(bǔ)運(yùn)算以及實(shí)現(xiàn)各種控制功能。3)．驅(qū)動裝置，它是數(shù)控機(jī)床執(zhí)行機(jī)構(gòu)的驅(qū)動部件，包括主軸驅(qū)動單元、進(jìn)給單元、主軸電機(jī)及進(jìn)給電機(jī)等。它在數(shù)控裝置的控制下通過電氣或電液伺服系統(tǒng)實(shí)現(xiàn)主軸和進(jìn)給驅(qū)動。當(dāng)幾個進(jìn)給聯(lián)動時，可以完成定位、直線、平面曲線和空間曲線的加工。4)．輔助裝置，指數(shù)控機(jī)床的一些必要的配套部件，用以保證數(shù)控機(jī)床的運(yùn)行，如冷卻、排屑、潤滑、照明、監(jiān)測等。它包括液壓和氣動裝置、排屑裝置、交換工作臺、數(shù)控轉(zhuǎn)臺和數(shù)控分度頭，還包括刀具及監(jiān)控檢測裝置等等。5)．編程及其他附屬設(shè)備，可用來在機(jī)外進(jìn)行零件的程序編制、存儲等等。1.2PCB鉆孔機(jī)用途介紹1.2.1PCB的概念PCB為PrintedCircuitBoard印制板.1936年，英國Eisler博士提出印制電路（PrintedCircuit）這個概念。他首創(chuàng)在絕緣基板上全面覆蓋金屬箔，在其金屬箔上涂上耐蝕刻油墨后再將不需要的金屬箔腐蝕掉的PCB制造基本技術(shù)。1942年，Eisler博士制造出世界上第一塊紙質(zhì)層壓絕緣基板，用于收音機(jī)的印制板。1.2.2數(shù)控機(jī)床的特點(diǎn)數(shù)控機(jī)床的操作和監(jiān)控全部在這個數(shù)控單元中完成，它是數(shù)控機(jī)床的大腦。與普通機(jī)床相比，數(shù)控機(jī)床有如下特點(diǎn)：1)．加工精度高，具有穩(wěn)定的加工質(zhì)量；2)．可進(jìn)行多坐標(biāo)的聯(lián)動，能加工形狀復(fù)雜的零件；3)．加工零件改變時，一般只需要更改數(shù)控程序，可節(jié)省生產(chǎn)準(zhǔn)備時間；4)．機(jī)床本身的精度高、剛性大,可選擇有利的加工用量，生產(chǎn)率高（一般為普通機(jī)床的3~5倍）；5)．機(jī)床自動化程度高，可以減輕勞動強(qiáng)度；6)．對操作人員的素質(zhì)要求較高，對維修人員的技術(shù)要求更高。1.2.3PCB在各種電子設(shè)備中有如下功能1).提供集成電路等各種電子元器件固定、裝配的機(jī)械支撐。2).實(shí)現(xiàn)集成電路等各種電子元器件之間的布線和電氣連接（信號傳輸）或電絕緣。提供所要求的電氣特性，如特性阻抗等。3).為自動裝配提供阻焊圖形，為元器件插裝、檢查、維修提供識別字符和圖形。PCB數(shù)控鉆銑床是一種典型的點(diǎn)位運(yùn)動控制系統(tǒng)，是印制電路板精密導(dǎo)通孔加工的關(guān)鍵設(shè)備。隨著電子產(chǎn)品向微型化、小型化方向發(fā)展，印制電路板對導(dǎo)通孔的孔徑、線寬、線距的要求越來越高。相應(yīng)地，PCB數(shù)控系統(tǒng)正朝高速、高精度、高可靠性、系統(tǒng)集成化、柔性化、智能化程度高的開放式方向發(fā)展。第二章最短路徑相關(guān)知識2.1圖2.1.1圖的定義及基本術(shù)語1.定義(1)圖圖是有頂點(diǎn)集合V和頂點(diǎn)之間關(guān)系集合R組成，記作G=(V,R)其中V是圖中頂點(diǎn)的非空有窮集合,V={v1,v2,…vn}:R是兩個頂點(diǎn)之間關(guān)系的集合,它是定點(diǎn)的有序或無序?qū)?記作<vi,vj>或<vj,vi>.(2)無向圖當(dāng)圖中頂點(diǎn)之間的關(guān)系為無序?qū)r稱為無向圖.無序?qū)?lt;vi,vj>=<vj,vi>稱為邊E(edge)無向圖記作G=(V,E)(3)有向圖當(dāng)圖中頂點(diǎn)之間的關(guān)系為有序?qū)r稱為有向圖。<vi,vj>稱為有向圖中一條弧A(arc)稱vi為弧尾或初始點(diǎn),稱vj為弧頭或終端點(diǎn),<vi,vj>和<vj,vi>是表示不同的弧.有向圖記作G=(V,A)2.有關(guān)圖的基本術(shù)語(1)子圖假如有兩個圖G=(V，E)和G=(V’，E’)，如果滿足V’包含于V且E’包含于E，則稱圖G’為G的子圖.(2)度在無向圖中，與某個頂點(diǎn)相連的邊的數(shù)目稱為該頂點(diǎn)的度。在有向圖中，以某個頂點(diǎn)為初始點(diǎn)的弧的數(shù)目，稱為該頂點(diǎn)的出度。以某個頂點(diǎn)為終端的弧數(shù)目稱為該頂點(diǎn)的入度。（3）路徑和回路在無向圖中，從頂點(diǎn)vp到頂點(diǎn)vq的路徑是頂點(diǎn)序列(vp,vil，vi2,…vik,viq)且（vp，vi1）…(vik,viq)均是E中的邊。在有向圖，則由頂點(diǎn)的弧組成有向路徑路徑。路徑上的邊或弧的數(shù)目稱為路徑長度。網(wǎng)絡(luò)的路徑長度定義為路徑上權(quán)值的和。除第一個和最后一個頂點(diǎn)外，序列中其余頂點(diǎn)各不相同的路徑稱為簡單路徑。第一個頂點(diǎn)和最后一個頂點(diǎn)相同的簡單路徑稱為簡單回路。（4）連通圖和連通分量在無向圖中，如果從vi到vj存在有路徑，則稱vi和vj是連通的。若在頂點(diǎn)集合V中每一對不同頂點(diǎn)vi和vj都連通，稱G為連通圖。否則，將其中的極大連通子圖稱為連通分量。2.1.2圖的存儲結(jié)構(gòu)1．鄰接矩陣存儲結(jié)構(gòu)1.1有向圖的鄰接矩陣具有n個頂點(diǎn)的有向圖可以用一個n′n的方形矩陣表示。假設(shè)該矩陣的名稱為M，則當(dāng)<vi,vj>是該有向圖中的一條弧時，M[i,j]=1；否則M[i,j]=0。第i個頂點(diǎn)的出度為矩陣中第i行中"1"的個數(shù)；入度為第i列中"1"的個數(shù)，并且有向圖弧的條數(shù)等于矩陣中"1"的個數(shù)。1．2無向圖的鄰接矩陣具有n個頂點(diǎn)的無向圖也可以用一個n′n的方形矩陣表示。假設(shè)該矩陣的名稱為M，則當(dāng)（vi,vj）是該無向圖中的一條邊時，M[i,j]=M[j,i]=1；否則，M[i,j]=M[j,j]=0。第i個頂點(diǎn)的度為矩陣中第i行中"1"的個數(shù)或第i列中"1"的個數(shù)。圖中邊的數(shù)目等于矩陣中"1"的個數(shù)的一半，這是因?yàn)槊織l邊在矩陣中描述了兩次.2．鄰接表鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，在鄰接表中，對圖中每個頂點(diǎn)建立一個單鏈表，第i個單鏈表中的節(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊，每個鏈結(jié)點(diǎn)由三部分組成：鄰接域（adjvex）表示與是頂點(diǎn)vi鄰接的點(diǎn)的序號，鏈域(nextare)表示下一條邊或弧的結(jié)點(diǎn)，數(shù)據(jù)域（data）存儲和邊或弧相關(guān)的信息，如權(quán)值等。2.1.3圖的遍歷常見的圖遍歷方式有兩種：深度優(yōu)先遍歷和廣度優(yōu)先遍歷，這兩種遍歷方式對有向圖和無向圖均適用。（1）深度優(yōu)先遍歷深度優(yōu)先遍歷的基本思想是：從圖的某一個頂點(diǎn)v0出發(fā)進(jìn)行遍歷，首先訪問起始點(diǎn)v0，然后依次從v0的未被訪問的鄰接點(diǎn)出發(fā)繼續(xù)深度優(yōu)先遍歷圖中的其余頂點(diǎn)，直至圖中所有與v0有路徑相通的頂點(diǎn)都被訪問完為止。對于無向圖，這個算法可以遍歷到v頂點(diǎn)所在的連通分量中的所有頂點(diǎn)，而與v頂點(diǎn)不在一個連通分量中的所有頂點(diǎn)遍歷不到；而對于有向圖可以遍歷到起始頂點(diǎn)v0能夠到達(dá)的所有頂點(diǎn)。若希望遍歷到圖中的所有頂點(diǎn)，就需要在上述深度優(yōu)先遍歷算法的基礎(chǔ)上，增加對每個頂點(diǎn)訪問狀態(tài)的檢測（2）廣度優(yōu)先遍歷對圖的廣度優(yōu)先遍歷的基本思想是：首先訪問初始點(diǎn)vi，并將其標(biāo)記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點(diǎn)vi1,vi2,…,vik，并均標(biāo)記已訪問過，然后再按照vi1,vi2,…,vik的次序，訪問每一個頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)，并均標(biāo)記為已訪問過，依次類推，直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問過為止。實(shí)現(xiàn)廣度優(yōu)先遍歷算法需要考慮的幾個問題：（1）在廣度優(yōu)先遍歷中，要求先被訪問的頂點(diǎn)其鄰接點(diǎn)也被優(yōu)先訪問，因此，必須對每個頂點(diǎn)的訪問順序進(jìn)行記錄，以便后面按此順序訪問各頂點(diǎn)的鄰接點(diǎn)。應(yīng)利用一個隊列結(jié)構(gòu)記錄頂點(diǎn)訪問順序，就可以利用隊列結(jié)構(gòu)的操作特點(diǎn)，將訪問的每個頂點(diǎn)入隊，然后，再依次出隊，并訪問它們的鄰接點(diǎn)；（2）在廣度優(yōu)先遍歷過程中同深度優(yōu)先遍歷一樣，為了避免重復(fù)訪問某個頂點(diǎn)，也需要創(chuàng)建一個一維數(shù)組visited[0..n-1]（n是圖中頂點(diǎn)的數(shù)目），用來記錄每個頂點(diǎn)是否已經(jīng)被訪問過。2.1.4圖的應(yīng)用--單源最短路徑1．單源最短路徑的問題背景單源元最短路徑的問題背景:從一個給定的城市出發(fā)，能否到達(dá)其他各城市，走那幾條公路花費(fèi)最少，我們用一個有向網(wǎng)表示城市的公路網(wǎng)，頂點(diǎn)表示城市，弧代表公路段，弧上的權(quán)值代表兩城市的距離，或運(yùn)輸所需的代價。習(xí)慣上稱給定的出發(fā)點(diǎn)為原點(diǎn)，其其他的點(diǎn)稱為終點(diǎn)。單元最短路徑問題一般提法是從有向網(wǎng)的原點(diǎn)到其他各終點(diǎn)是否有路徑？最短路徑是什么？最短路徑的長度是多少？2.我們可以發(fā)現(xiàn)有這樣一個事實(shí)：如果P是G中從vs到vj的最短路，vi是P中的一個點(diǎn)，那么，從vs沿P到vi的路是從vs到vi的最短路。3．從原點(diǎn)到終點(diǎn)的最短路徑有三種情況：（1）沒有路徑；（2）只有一條路徑，即位最短路徑；（3），有幾條路徑，其中有一條為最短路徑。4．所謂單源最短路徑問題是指：已知圖G＝（V，E），我們希望找出從某給定的源結(jié)點(diǎn)S∈V到V中的每個結(jié)點(diǎn)的最短路徑。2.2最短路徑問題2.2.1最短路徑最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的中兩結(jié)點(diǎn)之間的最短路徑。2.2.2算法具體的形式算法具體的形式包括：1)確定起點(diǎn)的最短路徑問題-即已知起始結(jié)點(diǎn)，求最短路徑的問題。2)確定終點(diǎn)的最短路徑問題-與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。3)確定起點(diǎn)終點(diǎn)的最短路徑問題-即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。4)全局最短路徑問題-求圖中所有的最短路徑。2.3最短路徑的思想及算法2.3.1求最短路徑的算法思想先找出從原點(diǎn)到各終點(diǎn)的直達(dá)路徑，即通過一條弧到達(dá)的路徑。從這些路徑中找出一條最短的路徑最短路徑問題是圖論研究中的一個經(jīng)典算法問題，旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。算法具體的形式包括：確定起點(diǎn)的最短路徑問題-即已知起始結(jié)點(diǎn)，求最短路徑的問題。確定終點(diǎn)的最短路徑問題-與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。確定起點(diǎn)終點(diǎn)的最短路徑問題-即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。全局最短路徑問題-求圖中所有的最短路徑。，然后對其余各條路徑做適當(dāng)調(diào)整。2.3.2從源點(diǎn)到各終點(diǎn)的最短路徑的算法描述如下1.設(shè)AS[1:n,1:n]為有向網(wǎng)的帶權(quán)鄰接矩陣，AS[I,j]表示弧<Vi,Vj>上的權(quán)值，若<Vi,Vj>不存在，則AS[I,j]為無窮。DIST[1：n]為各終點(diǎn)當(dāng)前找到的最短路徑的長度，它的初始值為DIST[i]=AS[V0，i]2.選擇u,使得DIST[u]=min{DIST[w]/w不屬于S，w屬于V}S=S并{u}其中V為有向圖的頂點(diǎn)集。3.對于所有不在S中的終點(diǎn)w，若DIST[u]+AS[u,w]<DIST[w]則修改DIST[w]為DIST[w]DIST[u]+AS[u,w]4.重復(fù)操作2.和3.共n-1次，由此求得從V0到各終點(diǎn)的最短路徑。此外為了得到從源點(diǎn)到各終點(diǎn)的最短路徑的最短路徑，設(shè)置一個路徑向量PATH[1:n]2.3.3求以V0為源點(diǎn)的最短路徑算法如下：SHORTPATH（AS,DIST,PATH,n,V0）1，fori=1ton2，DIST[i]AS[V0,i]3，ifDIST[i]<MAXthenPATH[i]V04，end(i)//對DIST[1:n]置初值//5，S{V0};//S為已找到的最短路徑的終點(diǎn)集合//6，fork=1to(n-1)7，wmMAX；uV0;8，fori=1ton9，if(notiinS)and(DIST[I]<wm)then{uI;wmDIST[i]}end(i)//在DIST[i]中找到最小值//SS+{u};u為已找到最短路徑的終點(diǎn)//fori=1tonif(notIinS)and(DIST[u]+AS[u,i]<DIST[I])thenDIST[i]-DIST[u]+AS[u,i]PATH[i]}end（i）//調(diào)整S集各點(diǎn)之間的最短路徑//end(k)fori=1ton//輸出結(jié)果//if（IinS）then{kI;Whilek≠Vodo{WRITE(k,＇＇)；kPATH[k]}；WRITE（Vo）；WRITE（DISTE[i]；}//輸出Vo到Vi最短路徑//ElseWRITE（＇notpath＇）；WRITE（＇max＇）；}//輸出Vo到Vi無路徑//end(i)return核心思路通過一個圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=[a(i,j)]n×n開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點(diǎn)到j(luò)號頂點(diǎn)的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點(diǎn)矩陣path來記錄兩點(diǎn)間的最短路徑。采用的是松弛技術(shù)，對在i和j之間的所有其他點(diǎn)進(jìn)行一次松弛。所以時間復(fù)雜度為O(n^3);算法描述a)初始化：D[u,v]=A[u,v]b)Fork:=1tonFori:=1tonForj:=1tonIfD[i,j]>D[i,k]+D[k,j]ThenD[i,j]:=D[i,k]+D[k,j];c)算法結(jié)束：D即為所有點(diǎn)對的最短路徑矩陣算法過程把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達(dá)，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。定義一個矩陣D用來記錄所插入點(diǎn)的信息，D[i,j]表示從Vi到Vj需要經(jīng)過的點(diǎn)，初始化D[i,j]=j。把各個頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來的距離，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點(diǎn)之間最短道路的信息，而在D中則包含了最短通路徑的信息。比如，要尋找從V5到V1的路徑。根據(jù)D，假如D(5,1)=3則說明從V5到V1經(jīng)過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。時間復(fù)雜度O(n^3)優(yōu)缺點(diǎn)分析Floyd算法適用于APSP(AllPairsShortestPaths)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。優(yōu)點(diǎn)：容易理解，可以算出任意兩個節(jié)點(diǎn)之間的最短距離，代碼編寫簡單；缺點(diǎn)：時間復(fù)雜度比較高，不適合計算大量數(shù)據(jù)。viewplaincopytoclipboardprint?#include<iostream>usingnamespacestd;constintN=101;constintMAX=32767;intmap[N][N];intmain(){intn;inti,j,k;intaskx,asky;cin>>n;cin>>askx>>asky;for(i=1;i<=n;i++){cin>>map[i][j];if(map[i][j]==0)map[i][j]=MAX;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(map[i][k]+map[k][j]<=map[i][j])map[i][j]=map[i][k]+map[k][j];}cout<<map[askx][asky];system("pause");}</P<p>Floyd-Warshall算法用來找出每對點(diǎn)之間的最短距離。它需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。編輯本段算法概述單獨(dú)一條邊的路徑也不一定是最佳路徑。從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，或者無窮大，如果兩點(diǎn)之間沒有邊相連。對于每一對頂點(diǎn)u和v，看看是否存在一個頂點(diǎn)w使得從u到w再到v比己知的路徑更短。如果是更新它。不可思議的是，只要按排適當(dāng)，就能得到結(jié)果。//dist(i,j)為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離Fori←1tondoForj←1tondodist(i,j)=weight(i,j)Fork←1tondo//k為“媒介節(jié)點(diǎn)”{一定要先枚舉媒介節(jié)點(diǎn)}Fori←1tondoForj←1tondoif(dist(i,k)+dist(k,j)<dist(i,j))then//是否是更短的路徑？dist(i,j)=dist(i,k)+dist(k,j)這個算法的效率是O(V)。它需要鄰接矩陣來儲存圖。這個算法很容易實(shí)現(xiàn)，只要幾行。即使問題是求單源最短路徑，還是推薦使用這個算法，如果時間和空間允許(只要有放的下鄰接矩陣的空間，時間上就沒問題)。第三章幾種最短路徑算法的介紹3.1求網(wǎng)絡(luò)圖形最短路徑的問題上的算法3.1.1路徑算法用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時被簡稱作“路徑算法”。3.1.2最常用的路徑算法Dijkstra算法、逐次逼近算法、矩陣算法、Floyed算法,遺傳算法等等，它們分別出現(xiàn)在數(shù)據(jù)結(jié)構(gòu)、運(yùn)籌學(xué)、圖論等課程中。其中前兩種算法都是求圖上從某一點(diǎn)至另一點(diǎn)的最短路徑，而后三種算法是求出網(wǎng)絡(luò)圖上所有節(jié)點(diǎn)之間的最短路徑。3.1.3統(tǒng)一的歸納總結(jié)與分析比較Dijkstra算法與逐次逼近算法解決的是從某一個節(jié)點(diǎn)到另一節(jié)點(diǎn)之間的最短路徑問題，算法的時間復(fù)雜度是O(n)。如果想得到每一對節(jié)點(diǎn)之間的最短路徑，則需要多次調(diào)用之間的最短距離就顯得過于麻煩。矩陣算法與Floyed算法較好地解決了這方面的問題，它可以通過算法的一次調(diào)用直接計算出網(wǎng)絡(luò)中每一對節(jié)點(diǎn)之間的最短路徑值，因而彌補(bǔ)了前兩種算法在這方面的不足。它們通過一個圖的權(quán)值矩陣求出每兩點(diǎn)間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=[a(i，j)]n×n開始，逐漸擴(kuò)展，最終找到所有節(jié)點(diǎn)間的最短路徑。矩陣算法與Floyed算法的時間復(fù)雜度是O(n)。3.2幾種主要的最短路徑算法的介紹3.2.1Dijkstra算法1.Dijkstra算法的定義:Dijkstra(迪杰斯特拉)算法是典型的最短路徑路算法，是Dijkstra提出的一個按路徑長度遞增的順序逐步產(chǎn)生最短路徑的算法，用于計算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。Dijkstra算法又稱為單源最短路徑算法。2.Dijkstra算法的主要特點(diǎn)Dijkstra算法的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點(diǎn)很多，所以效率低。3.Dijkstra算法的基本思想是：設(shè)置兩個頂點(diǎn)的集合T和S，集合S中存放已找到最短路徑的頂點(diǎn)，集合T中存放當(dāng)前還未找到的最短路徑的頂點(diǎn)。初始狀態(tài)時，集合S中只包含原點(diǎn)v0，然后不斷從集合T中選取到頂點(diǎn)v0路徑長度最短的頂點(diǎn)u加入集合S，集合S中每加入一個新的頂點(diǎn)u，都要修改定點(diǎn)v0到集合T中剩余頂點(diǎn)的最短路徑長度值，集合T中每個頂點(diǎn)新的最短路徑長度值為原來的最短路徑長度值與頂點(diǎn)u的最短路徑長度值加上u到該頂點(diǎn)的路徑長度值中的較小值。該過程不斷重復(fù)，直到集合T的頂點(diǎn)全部加入到集合S為止。4.Dijkstra算法一般的表述的兩種方式(1)Dijkstra算法一般的表述通常有兩種方式:一種用永久和臨時標(biāo)號方式；一種是用OPEN,CLOSE表方式。(2)Dijkstra算法采用的是貪心法的算法策略大概過程：創(chuàng)建兩個表，OPEN,CLOSE：OPEN表示保存所有已生成而未訪問的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。1)訪問路網(wǎng)中距離起始點(diǎn)最近且沒有被訪問過的點(diǎn)，把這個點(diǎn)放入OPEN組中等待訪問。2)從OPEN表中找出距離起始點(diǎn)最近的點(diǎn)，找出這個點(diǎn)的所有子節(jié)點(diǎn)，把這個點(diǎn)放到CLOSE表中。3)遍歷訪問這個點(diǎn)的子節(jié)點(diǎn)。求出這些子節(jié)點(diǎn)距起始點(diǎn)的距離值，放子節(jié)點(diǎn)到OPEN表中。4)重復(fù)第2）和第3）步,直到OPEN表為空，或找到目標(biāo)點(diǎn)。5.Dijstra算法的算法描述:1)假設(shè)用帶權(quán)的鄰接矩陣edges來表示帶權(quán)有向圖，edges[i][j]表示弧<Vi,Vj>上的權(quán)值。若<Vi,Vj>不存在，則置edges[i][j]=∞（計算機(jī)上用一個允許的最大值代替）。S為已經(jīng)找到的從Vs出發(fā)的最短路徑的終點(diǎn)的集合，它的初始化為空集。那么，從Vs出發(fā)到圖上其余各頂點(diǎn)Vi可能達(dá)到的最短路徑長度的初值為：D[i]=edges[s][i]Vi∈V2)選擇Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是當(dāng)前求得的一條從Vs出發(fā)的最短路徑的終點(diǎn)。令S=S∪{Vj}3)修改從Vs出發(fā)到集合V-S上任一頂點(diǎn)Vk可達(dá)的最短路徑長度。如果D[j]+edges[j][k]<D[k]則修改D[k]為D[k]=D[j]+edges[j][k]重復(fù)操作(2)(3)共n-1次。由此求得從Vs到圖上其余各頂點(diǎn)的最短路徑。6.Dijstra算法的具體步驟1）初始時，S只包含源點(diǎn)，即S＝v0的距離為0。U包含除v0外的其他頂點(diǎn)，U中頂點(diǎn)u距離v0邊上的權(quán)（若v與u有邊或若u不是v的出邊鄰接點(diǎn)）。2）從U中選取一個距離v0最小的頂點(diǎn)k，把k加入S中（該選定的距離就是v0到k的最短路徑長度）。3）以k為新考慮的中間點(diǎn)，修改U中各頂點(diǎn)的距離；若從源點(diǎn)v0到頂點(diǎn)u（u∈U）的距離（經(jīng)過頂點(diǎn)k）比原來距離（不經(jīng)過頂點(diǎn)k）短，則修改頂點(diǎn)u的距離值，修改后的距離值為頂點(diǎn)k的距離加上邊上的權(quán)。4）重復(fù)步驟2）和3）直到所有頂點(diǎn)都包含在S中。Dijkstra算法的時間復(fù)雜度為O(n2)；空間復(fù)雜度取決于存儲方式，為O(n2)7.Dijkstra算法舉例說明如下圖，設(shè)A為源點(diǎn)，求A到其他各頂點(diǎn)（B、C、D、E、F）的最短路徑。線上所標(biāo)注為相鄰線段之間的距離，即權(quán)值。（注：此圖為隨意所畫，其相鄰頂點(diǎn)間的距離與圖中的目視長度不能一一對等）Dijkstra無向圖圖3.1DIJKSTRA無向圖算法執(zhí)行步驟如下表：表1步驟S集合中U集合中1選入QUOTE此時S=（A）此時最短路徑AQUOTEA=0，以QUOTE為中間點(diǎn)，從QUOTE開始找。U=（B,C,D,E,F）AQUOTEB=6AQUOTEC=3AQUOTE發(fā)現(xiàn)AQUOTE權(quán)值為最短。2選入QUOTE此時S=(A,C)此時最短路徑AQUOTEA=0,AQUOTEC=3以C為中間點(diǎn)，從AQUOTEC=3這條最短路徑開始找。U=（B,D,E,F）AQUOTECQUOTEB=5此時到B模值為AQUOTECQUOTEB=5AQUOTECQUOTEB=6AQUOTECQUOTEB=7AQUOTECQUOTE其他U中的頂點(diǎn)=QUOTE發(fā)現(xiàn)AQUOTECQUOTEB=5權(quán)值為最短。3選入QUOTE此時S=(A,C,B)此時最短路徑AQUOTEA=0,AQUOTEC=3，AQUOTECQUOTEB=5以B為中間點(diǎn)，從AQUOTECQUOTEB=5這條最短路徑開始找。U=（D,E,F）QUOTEEQUOTED=10此時到D權(quán)值更改為QUOTED=6AQUOTECQUOTEBQUOTE其他U中的頂點(diǎn)=QUOTE發(fā)現(xiàn)QUOTED=6權(quán)值為最短4選入QUOTE此時S=(A,C,B,D)此時最短路徑AQUOTEA=0,AQUOTEC=3，AQUOTECQUOTEB=5，QUOTED=6以D為中間點(diǎn)從QUOTED這條最短路徑開始找。U=(E,F)QUOTEDQUOTE此時到E權(quán)值更改為QUOTEE=7QUOTEDQUOTEF=9發(fā)現(xiàn)QUOTEE=7權(quán)值為最短5選入QUOTE此時S=(A,C,B,D,E)此時最短路徑AQUOTEA=0,AQUOTEC=3，AQUOTECQUOTEB=5，QUOTED=6，QUOTEE=7以E為中間點(diǎn)從QUOTEE=7這條最短路徑開始找U=(F)QUOTEEQUOTE此時到F權(quán)值更改為QUOTEDQUOTE發(fā)現(xiàn)QUOTEDQUOTE權(quán)值為最短。6選入QUOTE此時S=(A,C,B,D,E,F)此時最短路徑AQUOTEA=0,AQUOTEC=3，AQUOTECQUOTEB=5，QUOTED=6，QUOTEE=7。QUOTEDQUOTEF=9以F為中間點(diǎn)從QUOTEDQUOTEF=9這條最短路徑開始找。U集合完畢，查找完畢。8.Dijkstra算法最短路徑算法constn0=1000;typepath=recordlen:longint;pre:0..n0end;vard:array[1..n0]ofpath;{路徑集合dist}i,j,x:integer;proceduredijkstra(x:integer);varmin,u:integer;beginfillchar(a,sizeof(a),0);fori:=1tondobegind[i].len:=a[x,i];ifd[i].len<>maxintthend[i].pre:=xelsed[i].pre:=0end;a[x,x]:=1;repeat{每循環(huán)一次加入一個離1集合最近的結(jié)點(diǎn)并調(diào)整其他結(jié)點(diǎn)的參數(shù)}min:=maxint;u:=0;{u記錄離1集合最近的結(jié)點(diǎn)}fori:=1tondoif(a[i,i]=0)and(d[i].len<min)thenbeginu:=i;min:=d[i].lenend;ifu<>0thenbegina[u,u]:=1;fori:=1tondo{修正第二組中u可達(dá)的頂點(diǎn)距離值}if(a[i,i]=0)and(a[u,i]+d[u].len<d[i].len)thenbegind[i].len:=a[u,i]+d[u].len;d[i].pre:=uendend;untilu=0{直至n個頂點(diǎn)全部加入第一組為止}end;procedureprint_dij(i:integer);beginifi=xthenwrite(x:3)elsebeginprint_dij(d[i].pre);write(d[i].len,'')end;end;proceduremain_dij;begin//輸入頂點(diǎn)數(shù)readln(x);//輸入頂點(diǎn)間的距離矩陣dijkstra(x);fori:=1tondobeginif(i<>x)and(d[i].len<>maxint){若i與x間有通路，則輸出它們之間的最短距離和路徑方案}thenbeginwriteln(d[i].len);print_dij(i)end;writelnend;end;3.2.2Floyed算法1.Floyd算法的定義Floyd算法又稱為弗洛伊德算法，插點(diǎn)法，是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法。Floyd算法用來找出每對點(diǎn)之間的最短距離。它需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。注意單獨(dú)一條邊的路徑也不一定是最佳路徑。2.Floyd算法的基本思想是:從鄰接矩陣A開始進(jìn)行n次迭代，第一次迭代后a[i,j]的值是從vi到vj且中間不經(jīng)過變化大于1的頂點(diǎn)的最短路徑長度；第k次迭代后a[i,j]的值是從vi到vj且中間不經(jīng)過變化大于k的頂點(diǎn)的最短路徑長度；第n次迭代后a[i,j]的值就是從vi到vj的最短路徑長度。3.Floyd算法的核心思路通過一個圖的權(quán)值矩陣求出它的每兩點(diǎn)間的最短路徑矩陣。從圖的帶權(quán)鄰接矩陣A=[a(i,j)]n×n開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)……最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點(diǎn)到j(luò)號頂點(diǎn)的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點(diǎn)矩陣path來記錄兩點(diǎn)間的最短路徑。由于采用的是松弛技術(shù)，對在i和j之間的所有其他點(diǎn)進(jìn)行一次松弛。所以時間復(fù)雜度為O(n^3);4.Floyd算法的算法描述1).初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計值d[v]←+∞,d[s]←0;2).迭代求解：反復(fù)對邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個頂點(diǎn)v的最短距離估計值逐步逼近其最短距離（運(yùn)行|v|-1次）；3).檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false，表明問題無解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在d[v]中。算法語言:a)初始化：D[u,v]=A[u,v]b)Fork=1tonFori=1tonForj=1tonIfD[i,j]>D[i,k]+D[k,j]ThenD[i,j]=D[i,k]+D[k,j];c)算法結(jié)束：D即為所有點(diǎn)對的最短路徑矩陣5.Floyd算法的算法過程1．把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達(dá)，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。2．定義一個矩陣D用來記錄所插入點(diǎn)的信息，D[i,j]表示從Vi到Vj需要經(jīng)過的點(diǎn)，初始化D[i,j]=j。3．把各個頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來的距離，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點(diǎn)之間最短道路的信息，而在D中則包含了最短路徑的信息。時間復(fù)雜度O(n^3)6.Floyd算法優(yōu)缺點(diǎn)分析Floyd算法適用于APSP(AllPairsShortestPaths)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法。優(yōu)點(diǎn)：容易理解，可以算出任意兩個節(jié)點(diǎn)之間的最短距離，代碼編寫簡單；缺點(diǎn)：時間復(fù)雜度比較高，不適合計算大量數(shù)據(jù)。7.Floyd算法最短路徑算法{floyed算法求解所有可達(dá)頂點(diǎn)對之間的最短路徑：o(n^3)}constn0=1000;varp:array[1..n0,1..n0]of0..n0;{path,p[i,j]表示i到j(luò)的最短路徑上j的前驅(qū)結(jié)點(diǎn)}a:array[1..n0,1..n0]ofinteger;{最短路徑矩陣，圖的輸入略}i,j,k:integer;procedurefloyed;beginfori:=1tondoforj:=1tondoifa[i,j]>0{最短路徑矩陣，初始時為有向圖的鄰接矩陣}thenp[i,j]:=ielsep[i,j]:=0;{p[i,j]表示i到j(luò)的最短路徑上j的前驅(qū)結(jié)點(diǎn)}fork:=1tondo{枚舉中間結(jié)點(diǎn)}fori:=1tondoforj:=1tondoifa[i,k]+a[j,k]<a[i,j]thenbegina[i,j]:=a[i,k]+a[k,j];p[i,j]:=p[k,j]end;end;procedureprint_floyed(i,j:integer);beginifi=jthenwrite(i:3)elseifp[i,j]=0thenwriteln('nowayfrom',i,'to',j)elsebeginprint_floyed(i,p[i,j]);write(j:3)end;end;proceduremain_floyed;begin//輸入圖信息floyed;fori:=1tondoforj:=1tondoifp[i,j]<>0thenbeginprint_floyed(i,j);writelnend3.2.3遺傳算法遺傳算法（GeneticAlgorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型，是一種通過模擬自然進(jìn)化過程搜索最短路徑的方法，它最初由美國Michigan大學(xué)J.Holland教授于1975年首先提出來的，并出版了頗有影響的專著《AdaptationinNaturalandArtificialSystems》，GA這個名稱才逐漸為人所知，J.Holland教授所提出的GA通常為簡單遺傳算法（SGA）。1.遺傳算法的基本概念遺傳算法（GeneticAlgorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法。其主要特點(diǎn)是直接對結(jié)構(gòu)對象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)路徑最短的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計算中的關(guān)鍵技術(shù)。2.遺傳算法的數(shù)學(xué)規(guī)劃模型對于一個求函數(shù)最小值的優(yōu)化問題(求函數(shù)最大值也類同)，一般可以描述為下列數(shù)學(xué)規(guī)劃模型式中為決策變量，為目標(biāo)函數(shù)式：式1-2、1-3為約束條件，U是基本空間，R是U的子集。滿足約束條件的解X稱為可行解，集合R表示所有滿足約束條件的解所組成的集合，稱為可行解集合。3.遺傳算法的基本運(yùn)算過程如下:a)初始化:設(shè)置進(jìn)化代數(shù)計數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個個體作為初始群體P(0)。b)個體評價:計算群體P(t)中各個個體的適應(yīng)度。c)選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的。d)交叉運(yùn)算；將交叉算子作用于群體。所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。e)變異運(yùn)算:將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體P(t1)。f)終止條件判斷:若tT,則以進(jìn)化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，終止計算。4.遺傳算法定義遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體(individual)組成。每個個體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度（fitness）大小選擇（selection）個體，并借助于自然遺傳學(xué)的遺傳算子（geneticoperators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。5.遺傳算法特點(diǎn)(1)遺傳算法從問題解的串集開始嫂索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。(2)許多傳統(tǒng)搜索算法都是單點(diǎn)搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進(jìn)行評估，減少了陷入局部最優(yōu)解的風(fēng)險，同時算法本身易于實(shí)現(xiàn)并行化。（3）遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評估個體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。(4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)他的搜索方向。(5)具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過程獲得的信息自行組織搜索時，適應(yīng)度大的個體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。6.遺傳算法的應(yīng)用由于遺傳算法的整體搜索策略和優(yōu)化搜索方法在計算是不依賴于梯度信息或其它輔助知識，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)，所以遺傳算法提供了一種求解復(fù)雜系統(tǒng)問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于許多科學(xué)7.遺傳算法的一些主要應(yīng)用領(lǐng)域：1)．函數(shù)優(yōu)化函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評價的常用算例，許多人構(gòu)造出了各種各樣復(fù)雜形式的測試函數(shù)：連續(xù)函數(shù)和離散函數(shù)、凸函數(shù)和凹函數(shù)、低維函數(shù)和高維函數(shù)、單峰函數(shù)和多峰函數(shù)等。對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結(jié)果。2)．組合優(yōu)化隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇增大，有時在目前的計算上用枚舉法很難求出最優(yōu)解。對這類復(fù)雜的問題，人們已經(jīng)意識到應(yīng)把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對于組合優(yōu)化中的NP問題非常有效。例如遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用。此外，GA也在生產(chǎn)調(diào)度問題、自動控制、機(jī)器人學(xué)、圖象處理、人工生命、遺傳編碼和機(jī)器學(xué)習(xí)等方面獲得了廣泛的運(yùn)用。8.遺傳算法的現(xiàn)狀進(jìn)入90年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但它的應(yīng)用領(lǐng)域擴(kuò)大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高，同時產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中。此外一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴(kuò)展到了許多更新、更工程化的應(yīng)用方面。隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法。這一新的學(xué)習(xí)機(jī)制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其它智能計算方法相互滲透和結(jié)合，這對開拓21世紀(jì)中新的智能計算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進(jìn)化規(guī)劃（EvolutionProgramming,EP）以及進(jìn)化策略（EvolutionStrategy,ES）等進(jìn)化計算理論日益結(jié)合。EP和ES幾乎是和遺傳算法同時獨(dú)立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進(jìn)化機(jī)制的智能計算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。1991年D.Whitey在他的論文中提出了基于領(lǐng)域交叉的交叉算子（Adjacencybasedcrossover），這個算子是特別針對用序號表示基因的個體的交叉，并將其應(yīng)用到了TSP問題中，通過實(shí)驗(yàn)對其進(jìn)行了驗(yàn)證。D.H.Ackley等提出了隨機(jī)迭代遺傳爬山法（StochasticIteratedGeneticHill-climbing，SIGH）采用了一種復(fù)雜的概率選舉機(jī)制，此機(jī)制中由m個“投票者”來共同決定新個體的值（m表示群體的大?。?shí)驗(yàn)結(jié)果表明，SIGH與單點(diǎn)交叉、均勻交叉的神經(jīng)遺傳算法相比，所測試的六個函數(shù)中有四個表現(xiàn)出更好的性能，而且總體來講，SIGH比現(xiàn)存的許多算法在求解速度方面更有競爭力。H.Bersini和G.Seront將遺傳算法與單一方法（simplexmethod）結(jié)合起來，形成了一種叫單一操作的多親交叉算子（simplexcrossover），該算子在根據(jù)兩個母體以及一個額外的個體產(chǎn)生新個體，事實(shí)上他的交叉結(jié)果與對三個個體用選舉交叉產(chǎn)生的結(jié)果一致。同時，文獻(xiàn)還將三者交叉算子與點(diǎn)交叉、均勻交叉做了比較，結(jié)果表明，三者交叉算子比其余兩個有更好的性能。國內(nèi)也有不少的專家和學(xué)者對遺傳算法的交叉算子進(jìn)行改進(jìn)。2002年，戴曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題2004年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（Building-blockCodedParallelGA，BCPGA）。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識別出可能的基因塊，然后用基因塊作為新的基因單位對染色體重新編碼，產(chǎn)生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。2005年，江雷等針對并行遺傳算法求解TSP問題,探討了使用彈性策略來維持群體的多樣性,使得算法跨過局部收斂的障礙,向全局最優(yōu)解方向進(jìn)化。9.遺傳算法的一般算法1)．創(chuàng)建一個隨機(jī)的初始狀態(tài)初始種群是從解中隨機(jī)選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代，這和符號人工智能系統(tǒng)的情況不一樣，在那里問題的初始狀態(tài)已經(jīng)給定了。2)．評估適應(yīng)度對每一個解(染色體)指定一個適應(yīng)度的值，根據(jù)問題求解的實(shí)際接近程度來指定(以便逼近求解問題的答案)。不要把這些“解”與問題的“答案”混為一談，可以把它理解成為要得到答案，系統(tǒng)可能需要利用的那些特性。3)．繁殖(包括子代突變)帶有較高適應(yīng)度值的那些染色體更可能產(chǎn)生后代(后代產(chǎn)生后也將發(fā)生突變)。后代是父母的產(chǎn)物，他們由來自父母的基因結(jié)合而成，這個過程被稱為“雜交”。4)．下一代如果新的一代包含一個解，能產(chǎn)生一個充分接近或等于期望答案的輸出，那么問題就已經(jīng)解決了。如果情況并非如此，新的一代將重復(fù)他們父母所進(jìn)行的繁衍過程，一代一代演化下去，直到達(dá)到期望的解為止。5)．并行計算非常容易將遺傳算法用到并行計算和群集環(huán)境中。一種方法是直接把每個節(jié)點(diǎn)當(dāng)成一個并行的種群看待。然后有機(jī)體根據(jù)不同的繁殖方法從一個節(jié)點(diǎn)遷移到另一個節(jié)點(diǎn)。另一種方法是“農(nóng)場主/勞工”體系結(jié)構(gòu)，指定一個節(jié)點(diǎn)為“農(nóng)場主”節(jié)點(diǎn)，負(fù)責(zé)選擇有機(jī)體和分派適應(yīng)度的值，另外的節(jié)點(diǎn)作為“勞工”節(jié)點(diǎn)，負(fù)責(zé)重新組合、變異和適應(yīng)度函數(shù)的評估。10.術(shù)語說明由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的搜索算法，所以在這個算法中會用到很多生物遺傳學(xué)知識，下面是我們將會用來的一些術(shù)語說明：1)染色體(Chromosome)染色體又可以叫做基因型個體(individuals),一定數(shù)量的個體組成了群體(population),群體中個體的數(shù)量叫做群體大小。2)基因(Gene)基因是串中的元素，基因用于表示個體的特征。例如有一個串S=1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因(Alleles)。3)基因地點(diǎn)(Locus)基因地點(diǎn)在算法中表示一個基因在串中的位置稱為基因位置(GenePosition)，有時也簡稱基因位。基因位置由串的左向右計算，例如在串S=1101中，0的基因位置是3。4)基因特征值(GeneFeature)在用串表示整數(shù)時，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。5)適應(yīng)度(Fitness)各個個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù).這個函數(shù)是計算個體在群體中被使用的概率。11.運(yùn)算過程遺傳操作是模擬生物基因遺傳的做法。在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務(wù)就是對群體的個體按照它們對環(huán)境適應(yīng)度(適應(yīng)度評估)施加一定的操作，從而實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過程。從優(yōu)化搜索的角度而言，遺傳操作可使問題

圖3.2遺傳運(yùn)算過程圖的解，一代又一代地優(yōu)化，并逼進(jìn)最優(yōu)解。遺傳操作包括以下三個基本遺傳算子(geneticoperator):選擇(selection)；交叉(crossover)；變異(mutation)。這三個遺傳算子有如下特點(diǎn):個體遺傳算子的操作都是在隨機(jī)擾動情況下進(jìn)行的。因此，群體中個體向最優(yōu)解遷移的規(guī)則是隨機(jī)的。需要強(qiáng)調(diào)的是，這種隨機(jī)化操作和傳統(tǒng)的隨機(jī)搜索方法是有區(qū)別的。遺傳操作進(jìn)行的高效有向的搜索而不是如一般隨機(jī)搜索方法所進(jìn)行的無向搜索。遺傳操作的效果和上述三個遺傳算子所取的操作概率，編碼方法，群體大小，初始群體以及適應(yīng)度函數(shù)的設(shè)定密切相關(guān)。遺傳算法的下幾種:適應(yīng)度比例方法、隨機(jī)遍歷抽樣法、局部選擇法。其中輪盤賭選擇法（roulettewheelselection）是最簡單也是最常用的選擇方法。在該方法中，各個個體的選擇概率和其適應(yīng)度值成比例。設(shè)群體大小為n，其中個體i的適應(yīng)度為，則i被選擇的概率,為遺傳算法顯然，概率反映了個體i的適應(yīng)度在整個群體的個體適應(yīng)度總和中所占的比例.個體適應(yīng)度越大。其被選擇的概率就越高、反之亦然。計算出群體中各個個體的選擇概率后，為了選擇交配個體，需要進(jìn)行多輪選擇。每一輪產(chǎn)生一個[0，1]之間均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針來確定被選個體。個體被選后，可隨機(jī)地組成交配對，以供后面的交叉操作。交叉在自然界生物進(jìn)化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。交叉算子根據(jù)交叉率將種群中的兩個個體隨機(jī)地交換某些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。根據(jù)編碼表示方法的不同，可以有以下的算法：a)實(shí)值重組（realvaluedrecombination）1)離散重組（discreterecombination）；2)中間重組（intermediaterecombination）；3)線性重組（linearrecombination）；4)擴(kuò)展線性重組（extendedlinearrecombination）。b)二進(jìn)制交叉（binaryvaluedcrossover）1)單點(diǎn)交叉（single-pointcrossover）；2)多點(diǎn)交叉（multiple-pointcrossover）；3)均勻交叉（uniformcrossover）；4)洗牌交叉（shufflecrossover）；5)縮小代理交叉（crossoverwithreducedsurrogate）。最常用的交叉算子為單點(diǎn)交叉(one-pointcrossover)。具體操作是:在個體串中隨機(jī)設(shè)定一個交叉點(diǎn)，實(shí)行交叉時，該點(diǎn)前或后的兩個個體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個新個體。下面給出了單點(diǎn)交叉的一個例子：個體A：1001↑111→1001000新個體個體B：0011↑000→0011111新個體變異變異算子的基本內(nèi)容是對群體中的個體串的某些基因座上的基因值作變動。依據(jù)個體編碼表示方法的不同，可以有以下的算法：a)實(shí)值變異；b)二進(jìn)制變異。一般來說，變異算子操作的基本步驟如下:a)對群中所有個體以事先設(shè)定的編譯概率判斷是否進(jìn)行變異；b)對進(jìn)行變異的個體隨機(jī)選擇變異位進(jìn)行變異。遺傳算法引入變異的目的有兩個:一是使遺傳算法具有局部的隨機(jī)搜索能力。當(dāng)遺傳算法通過交叉算子已接近最優(yōu)解鄰域時，利用變異算子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂。顯然，此種情況下的變異概率應(yīng)取較小值，否則接近最優(yōu)解的積木塊會因變異而遭到破壞。二是使遺傳算法可維持群體多樣性，以防止出現(xiàn)未成熟收斂現(xiàn)象。此時收斂概率應(yīng)取較大值。遺傳算法中，交叉算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過交叉和變異這對相互配合又相互競爭的操作而使其具備兼顧全局和局部的均衡搜索能力。所謂相互配合.是指當(dāng)群體在進(jìn)化中陷于搜索空間中某個超平面而僅靠交叉不能擺脫時，通過變異操作可有助于這種擺脫。所謂相互競爭，是指當(dāng)通過交叉已形成所期望的積木塊時，變異操作有可能破壞這些積木塊。如何有效地配合使用交叉和變異操作，是目前遺傳算法的一個重要研究內(nèi)容?；咀儺愃阕邮侵笇θ后w中的個體碼串隨機(jī)挑選一個或多個基因座并對這些基因座的基因值做變動(以變異概率P.做變動)，(0，1)二值碼串中的基本變異操作如下:基因位下方標(biāo)有*號的基因發(fā)生變異。變異率的選取一般受種群大小、染色體長度等因素的影響，通常選取很小遺傳算法的值，一般取0.001－0.1。終止條件當(dāng)最優(yōu)個體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個體的適應(yīng)度和群體適應(yīng)度不再上升時，或者迭代次數(shù)達(dá)到預(yù)設(shè)的代數(shù)時，算法終止。預(yù)設(shè)的代數(shù)一般設(shè)置為100-500代。GA的流程圖GA的流程圖如右圖遺傳算法圖3.3GA流程圖適應(yīng)度函數(shù)進(jìn)化論中的適應(yīng)度，是表示某一個體對環(huán)境的適應(yīng)能力，也表示該個體繁殖后代的能力。遺傳算法的適應(yīng)度函數(shù)也叫評價函數(shù)，是用來判斷群體中的個體的優(yōu)劣程度的指標(biāo)，它是根據(jù)所求問題的目標(biāo)函數(shù)來進(jìn)行評估的。遺傳算法在搜索進(jìn)化過程中一般不需要其他外部信息，僅用評估函數(shù)來評估個體或解的優(yōu)劣，并作為以后遺傳操作的依據(jù)。由于遺傳算法中，適應(yīng)度函數(shù)要比較排序并在此基礎(chǔ)上計算選擇概率，所以適應(yīng)度函數(shù)的值要取正值.由此可見，在不少場合，將目標(biāo)函數(shù)映射成求最大值形式且函數(shù)值非負(fù)的適應(yīng)度函數(shù)是必要的。適應(yīng)度函數(shù)的設(shè)計主要滿足以下條件：a）單值、連續(xù)、非負(fù)、最大化；b)合理、一致性；c）計算量??；d）通用性強(qiáng)。在具體應(yīng)用中，適應(yīng)度函數(shù)的設(shè)計要結(jié)合求解問題本身的要求而定。適應(yīng)度函數(shù)設(shè)計直接影響到遺傳算法的性能。初始群體的選取遺傳算法中初始群體中的個體是隨機(jī)產(chǎn)生的。一般來講，初始群體的設(shè)定可采取如下的策略:a)根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。b)先隨機(jī)生成一定數(shù)目的個體，然后從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)達(dá)到了預(yù)先確定的規(guī)模。第四章基于遺傳算法的最短路徑的實(shí)現(xiàn)4.1PCB鉆孔走刀路徑的最短路徑問題的引入PCB鉆孔走刀路徑的優(yōu)化問題可以簡化為旅行商(TravelSalesmanProblem，TSP)問題。TSP問題是一個容易定義但難于處理的問題，屬于NP完備問題。遺傳算法(Ge—neticAlgorithm)是解決這類問題的一個非常實(shí)用的算法。采用遺傳算法可以快速有效地找到全局最優(yōu)解，極大地減少運(yùn)算量，能夠很好地解決PCB鉆孔走刀路徑優(yōu)化的問題。目前，已經(jīng)有一些學(xué)者做過關(guān)于用遺傳算法解決PCB鉆孔走刀路徑優(yōu)化問題的研究.現(xiàn)有的研究中，并沒有很好地根據(jù)數(shù)控鉆床鉆頭的運(yùn)動特點(diǎn)確定目標(biāo)函數(shù)，并且沒有就算法中變異算子以及變異概率對優(yōu)化結(jié)果的影響進(jìn)行進(jìn)一步的闡述。本文在采用遺傳算法解決走刀路徑最短問題的基礎(chǔ)上，對上述問題進(jìn)行了更詳細(xì)的論述和分析，使遺傳算法更加符合數(shù)控鉆床走刀路徑的特點(diǎn)，從而得到更好的優(yōu)化結(jié)果。4.2最佳走刀路徑模型的建立PCB上通常有許多不同直徑的孔，PCB鉆孔問題可以描述為：從換刀點(diǎn)出發(fā)，不重復(fù)不遺漏地加工完所有同一直徑的孔后回到換刀點(diǎn)進(jìn)行換刀操作，再加工另一直徑的孔，直到完成所有待加工的孔。所以鉆孔路徑優(yōu)化問題可以按照不同直徑的孔分別進(jìn)行優(yōu)化處理。對于數(shù)控編程來說，就存在如何選擇加工路徑的問題，最好的加工路徑應(yīng)該使生產(chǎn)效率最高、空行程時間最短，即最佳的鉆孔路徑。顯然，這一問題可以歸結(jié)為旅行商問題，其中鉆頭代表旅行商，待加工的孔表示旅行商途徑的城市，而最佳走刀路線的目標(biāo)函數(shù)即為刀具的空行程花費(fèi)時間最短。由于PCB數(shù)控鉆機(jī)屬于點(diǎn)位控制的機(jī)床，這種機(jī)床的刀具由一點(diǎn)運(yùn)動到另一點(diǎn)的過程中，通常是沿X、Y軸同時移動。當(dāng)兩點(diǎn)之間的方向距離與Y方向距離不相等的時候，刀具在距離較小的方向上先完成運(yùn)動，達(dá)到某一中間點(diǎn)。然后，在距離較大的方向上，刀具從中間點(diǎn)繼續(xù)向終點(diǎn)運(yùn)動。例如，刀具由換刀點(diǎn)開始按照1—2—3—4一