数控PCB钻机-最短路径计算

毕业设计（论文）设计题目：数控PCB钻机最短路径计算所属院（系）：电子信息工程2012年06月14目录TOC\o"1-3"\h\z\u摘要 IIIABSTRACT IV第一章钻孔机 11.1PCB钻孔机结构介绍 11.1.1数控机床的介绍 11.1.2数控机床的组成部分 11.2PCB钻孔机用途介绍 21.2.1PCB的概念 21.2.2数控机床的特点 21.2.3PCB在各种电子设备中有如下功能 3第二章最短路径相关知识 42.1图 42.1.1图的定义及基本术语 42.1.2图的存储结构 52.1.3图的遍历 52.1.4图的应用--单源最短路径 62.2最短路径问题 72.2.1最短路径 72.2.2算法具体的形式 72.3最短路径的思想及算法 72.3.1求最短路径的算法思想 72.3.2从源点到各终点的最短路径的算法描述如下 82.3.3求以V0为源点的最短路径算法如下： 8第三章几种最短路径算法的介绍 133.1求网络图形最短路径的问题上的算法 133.1.1路径算法 133.1.2最常用的路径算法 133.1.3统一的归纳总结与分析比较 133.2几种主要的最短路径算法的介绍 133.2.1Dijkstra算法 133.2.2Floyed算法 203.2.3遗传算法 23第四章基于遗传算法的最短路径的实现 344.1PCB钻孔走刀路径的最短路径问题的引入 344.2最佳走刀路径模型的建立 344.3遗传算法及走刀路径算法没计 354.3.1遗传算法概述 354.3.2走刀路径优化算法设计 364.3.3染色体编码方式 364.3.4适应度函数 364.3.5选择算子 374.3.6交叉算子 374.3.7变异算子 374.4走刀路径优化算法流程 38总结 40参考文献 41致谢 42摘要印刷电路板(PrintedCircuitBoard，PCB)是电子设备中最重要的组成部分之一。而PCB的钻孔工序是PCB制造过程中重要的一个环节。其中钻孔路径即走刀的路径是否最短对于提高加工效率来说是至关重要的。而现有的PCB设计软件虽然具有自动生成钻孔NC程序的功能，但是其生成的走刀路径并非最短路径。这样会影响加工效率。PCB钻孔走刀最短路径问题可以简化为旅行商(TravelSalesmanProblem，TSP)问题。旅行商问题，即TSP问题（TravelingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。遗传算法(Ge—neticAlgorithm)是解决这类问题的一个非常实用的算法。采用遗传算法可以快速而有效地找到全局最优解，极大地减少运算量，能够很好地解决PCB钻孔走刀的最短路径问题。目前，已经有一些学者做过关于用遗传算法解决PCB钻孔走刀的最短路径问题的现有的研究中，并没有很好地根据数控钻床钻头的运动特点确定目标函数，并且没有就算法中变异算子以及变异概率对路径最短结果的影响进行进一步的阐述。本文在采用遗传算法解决走刀的最短路径问题的基础上，对上述问题进行了更详细的论述和分析，使遗传算法更加符合数控钻机走刀路径的特点，从而得到最短路径。关键字:PCB数控钻机，最短路径算法，Dijkstra算法，Floyed算法，遗传算法。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，Floyedalgorithm,Geneticalgorithm.第一章钻孔机1.1PCB钻孔机结构介绍1.1.1数控机床的介绍数控机床是数字控制机床（Computernumericalcontrol）的简称，是一种装有程序控制系统的自动化机床。该控制系统能够逻辑地处理具有控制编码或其他符号指令规定的程序，并将其译码，从而使机床动作并加工零件。图1.1PCB钻孔机1.1.2数控机床的组成部分：1)．主机，它他是数控机床的主体，包括机床身、立柱、主轴、进给机构等机械部件。它是用于完成各种切削加工的机械部件。2)．数控装置，是数控机床的核心，包括硬件（印刷电路板、CRT显示器、键盒、纸带阅读机等）以及相应的软件，用于输入数字化的零件程序，并完成输入信息的存储、数据的变换、插补运算以及实现各种控制功能。3)．驱动装置，它是数控机床执行机构的驱动部件，包括主轴驱动单元、进给单元、主轴电机及进给电机等。它在数控装置的控制下通过电气或电液伺服系统实现主轴和进给驱动。当几个进给联动时，可以完成定位、直线、平面曲线和空间曲线的加工。4)．辅助装置，指数控机床的一些必要的配套部件，用以保证数控机床的运行，如冷却、排屑、润滑、照明、监测等。它包括液压和气动装置、排屑装置、交换工作台、数控转台和数控分度头，还包括刀具及监控检测装置等等。5)．编程及其他附属设备，可用来在机外进行零件的程序编制、存储等等。1.2PCB钻孔机用途介绍1.2.1PCB的概念PCB为PrintedCircuitBoard印制板.1936年，英国Eisler博士提出印制电路（PrintedCircuit）这个概念。他首创在绝缘基板上全面覆盖金属箔，在其金属箔上涂上耐蚀刻油墨后再将不需要的金属箔腐蚀掉的PCB制造基本技术。1942年，Eisler博士制造出世界上第一块纸质层压绝缘基板，用于收音机的印制板。1.2.2数控机床的特点数控机床的操作和监控全部在这个数控单元中完成，它是数控机床的大脑。与普通机床相比，数控机床有如下特点：1)．加工精度高，具有稳定的加工质量；2)．可进行多坐标的联动，能加工形状复杂的零件；3)．加工零件改变时，一般只需要更改数控程序，可节省生产准备时间；4)．机床本身的精度高、刚性大,可选择有利的加工用量，生产率高（一般为普通机床的3~5倍）；5)．机床自动化程度高，可以减轻劳动强度；6)．对操作人员的素质要求较高，对维修人员的技术要求更高。1.2.3PCB在各种电子设备中有如下功能1).提供集成电路等各种电子元器件固定、装配的机械支撑。2).实现集成电路等各种电子元器件之间的布线和电气连接（信号传输）或电绝缘。提供所要求的电气特性，如特性阻抗等。3).为自动装配提供阻焊图形，为元器件插装、检查、维修提供识别字符和图形。PCB数控钻铣床是一种典型的点位运动控制系统，是印制电路板精密导通孔加工的关键设备。随着电子产品向微型化、小型化方向发展，印制电路板对导通孔的孔径、线宽、线距的要求越来越高。相应地，PCB数控系统正朝高速、高精度、高可靠性、系统集成化、柔性化、智能化程度高的开放式方向发展。第二章最短路径相关知识2.1图2.1.1图的定义及基本术语1.定义(1)图图是有顶点集合V和顶点之间关系集合R组成，记作G=(V,R)其中V是图中顶点的非空有穷集合,V={v1,v2,…vn}:R是两个顶点之间关系的集合,它是定点的有序或无序对,记作<vi,vj>或<vj,vi>.(2)无向图当图中顶点之间的关系为无序对时称为无向图.无序对<vi,vj>=<vj,vi>称为边E(edge)无向图记作G=(V,E)(3)有向图当图中顶点之间的关系为有序对时称为有向图。<vi,vj>称为有向图中一条弧A(arc)称vi为弧尾或初始点,称vj为弧头或终端点,<vi,vj>和<vj,vi>是表示不同的弧.有向图记作G=(V,A)2.有关图的基本术语(1)子图假如有两个图G=(V，E)和G=(V’，E’)，如果满足V’包含于V且E’包含于E，则称图G’为G的子图.(2)度在无向图中，与某个顶点相连的边的数目称为该顶点的度。在有向图中，以某个顶点为初始点的弧的数目，称为该顶点的出度。以某个顶点为终端的弧数目称为该顶点的入度。（3）路径和回路在无向图中，从顶点vp到顶点vq的路径是顶点序列(vp,vil，vi2,…vik,viq)且（vp，vi1）…(vik,viq)均是E中的边。在有向图，则由顶点的弧组成有向路径路径。路径上的边或弧的数目称为路径长度。网络的路径长度定义为路径上权值的和。除第一个和最后一个顶点外，序列中其余顶点各不相同的路径称为简单路径。第一个顶点和最后一个顶点相同的简单路径称为简单回路。（4）连通图和连通分量在无向图中，如果从vi到vj存在有路径，则称vi和vj是连通的。若在顶点集合V中每一对不同顶点vi和vj都连通，称G为连通图。否则，将其中的极大连通子图称为连通分量。2.1.2图的存储结构1．邻接矩阵存储结构1.1有向图的邻接矩阵具有n个顶点的有向图可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当<vi,vj>是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中"1"的个数；入度为第i列中"1"的个数，并且有向图弧的条数等于矩阵中"1"的个数。1．2无向图的邻接矩阵具有n个顶点的无向图也可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该无向图中的一条边时，M[i,j]=M[j,i]=1；否则，M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i行中"1"的个数或第i列中"1"的个数。图中边的数目等于矩阵中"1"的个数的一半，这是因为每条边在矩阵中描述了两次.2．邻接表邻接表是图的一种链式存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的边，每个链结点由三部分组成：邻接域（adjvex）表示与是顶点vi邻接的点的序号，链域(nextare)表示下一条边或弧的结点，数据域（data）存储和边或弧相关的信息，如权值等。2.1.3图的遍历常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。（1）深度优先遍历深度优先遍历的基本思想是：从图的某一个顶点v0出发进行遍历，首先访问起始点v0，然后依次从v0的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v0有路径相通的顶点都被访问完为止。对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；而对于有向图可以遍历到起始顶点v0能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测（2）广度优先遍历对图的广度优先遍历的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…,vik，并均标记已访问过，然后再按照vi1,vi2,…,vik的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。实现广度优先遍历算法需要考虑的几个问题：（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点访问顺序，就可以利用队列结构的操作特点，将访问的每个顶点入队，然后，再依次出队，并访问它们的邻接点；（2）在广度优先遍历过程中同深度优先遍历一样，为了避免重复访问某个顶点，也需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。2.1.4图的应用--单源最短路径1．单源最短路径的问题背景单源元最短路径的问题背景:从一个给定的城市出发，能否到达其他各城市，走那几条公路花费最少，我们用一个有向网表示城市的公路网，顶点表示城市，弧代表公路段，弧上的权值代表两城市的距离，或运输所需的代价。习惯上称给定的出发点为原点，其其他的点称为终点。单元最短路径问题一般提法是从有向网的原点到其他各终点是否有路径？最短路径是什么？最短路径的长度是多少？2.我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。3．从原点到终点的最短路径有三种情况：（1）没有路径；（2）只有一条路径，即位最短路径；（3），有几条路径，其中有一条为最短路径。4．所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。2.2最短路径问题2.2.1最短路径最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的中两结点之间的最短路径。2.2.2算法具体的形式算法具体的形式包括：1)确定起点的最短路径问题-即已知起始结点，求最短路径的问题。2)确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。3)确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径。4)全局最短路径问题-求图中所有的最短路径。2.3最短路径的思想及算法2.3.1求最短路径的算法思想先找出从原点到各终点的直达路径，即通过一条弧到达的路径。从这些路径中找出一条最短的路径最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题-即已知起始结点，求最短路径的问题。确定终点的最短路径问题-与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题-即已知起点和终点，求两结点之间的最短路径。全局最短路径问题-求图中所有的最短路径。，然后对其余各条路径做适当调整。2.3.2从源点到各终点的最短路径的算法描述如下1.设AS[1:n,1:n]为有向网的带权邻接矩阵，AS[I,j]表示弧<Vi,Vj>上的权值，若<Vi,Vj>不存在，则AS[I,j]为无穷。DIST[1：n]为各终点当前找到的最短路径的长度，它的初始值为DIST[i]=AS[V0，i]2.选择u,使得DIST[u]=min{DIST[w]/w不属于S，w属于V}S=S并{u}其中V为有向图的顶点集。3.对于所有不在S中的终点w，若DIST[u]+AS[u,w]<DIST[w]则修改DIST[w]为DIST[w]DIST[u]+AS[u,w]4.重复操作2.和3.共n-1次，由此求得从V0到各终点的最短路径。此外为了得到从源点到各终点的最短路径的最短路径，设置一个路径向量PATH[1:n]2.3.3求以V0为源点的最短路径算法如下：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为已找到的最短路径的终点集合//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为已找到最短路径的终点//fori=1tonif(notIinS)and(DIST[u]+AS[u,i]<DIST[I])thenDIST[i]-DIST[u]+AS[u,i]PATH[i]}end（i）//调整S集各点之间的最短路径//end(k)fori=1ton//输出结果//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核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为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)算法结束：D即为所有点对的最短路径矩阵算法过程把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。时间复杂度O(n^3)优缺点分析Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。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算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。编辑本段算法概述单独一条边的路径也不一定是最佳路径。从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比己知的路径更短。如果是更新它。不可思议的是，只要按排适当，就能得到结果。//dist(i,j)为从节点i到节点j的最短距离Fori←1tondoForj←1tondodist(i,j)=weight(i,j)Fork←1tondo//k为“媒介节点”{一定要先枚举媒介节点}Fori←1tondoForj←1tondoif(dist(i,k)+dist(k,j)<dist(i,j))then//是否是更短的路径？dist(i,j)=dist(i,k)+dist(k,j)这个算法的效率是O(V)。它需要邻接矩阵来储存图。这个算法很容易实现，只要几行。即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。第三章几种最短路径算法的介绍3.1求网络图形最短路径的问题上的算法3.1.1路径算法用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。3.1.2最常用的路径算法Dijkstra算法、逐次逼近算法、矩阵算法、Floyed算法,遗传算法等等，它们分别出现在数据结构、运筹学、图论等课程中。其中前两种算法都是求图上从某一点至另一点的最短路径，而后三种算法是求出网络图上所有节点之间的最短路径。3.1.3统一的归纳总结与分析比较Dijkstra算法与逐次逼近算法解决的是从某一个节点到另一节点之间的最短路径问题，算法的时间复杂度是O(n)。如果想得到每一对节点之间的最短路径，则需要多次调用之间的最短距离就显得过于麻烦。矩阵算法与Floyed算法较好地解决了这方面的问题，它可以通过算法的一次调用直接计算出网络中每一对节点之间的最短路径值，因而弥补了前两种算法在这方面的不足。它们通过一个图的权值矩阵求出每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i，j)]n×n开始，逐渐扩展，最终找到所有节点间的最短路径。矩阵算法与Floyed算法的时间复杂度是O(n)。3.2几种主要的最短路径算法的介绍3.2.1Dijkstra算法1.Dijkstra算法的定义:Dijkstra(迪杰斯特拉)算法是典型的最短路径路算法，是Dijkstra提出的一个按路径长度递增的顺序逐步产生最短路径的算法，用于计算一个节点到其他所有节点的最短路径。Dijkstra算法又称为单源最短路径算法。2.Dijkstra算法的主要特点Dijkstra算法的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。3.Dijkstra算法的基本思想是：设置两个顶点的集合T和S，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到的最短路径的顶点。初始状态时，集合S中只包含原点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入集合S，集合S中每加入一个新的顶点u，都要修改定点v0到集合T中剩余顶点的最短路径长度值，集合T中每个顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。该过程不断重复，直到集合T的顶点全部加入到集合S为止。4.Dijkstra算法一般的表述的两种方式(1)Dijkstra算法一般的表述通常有两种方式:一种用永久和临时标号方式；一种是用OPEN,CLOSE表方式。(2)Dijkstra算法采用的是贪心法的算法策略大概过程：创建两个表，OPEN,CLOSE：OPEN表示保存所有已生成而未访问的节点，CLOSED表中记录已访问过的节点。1)访问路网中距离起始点最近且没有被访问过的点，把这个点放入OPEN组中等待访问。2)从OPEN表中找出距离起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。3)遍历访问这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。4)重复第2）和第3）步,直到OPEN表为空，或找到目标点。5.Dijstra算法的算法描述:1)假设用带权的邻接矩阵edges来表示带权有向图，edges[i][j]表示弧<Vi,Vj>上的权值。若<Vi,Vj>不存在，则置edges[i][j]=∞（计算机上用一个允许的最大值代替）。S为已经找到的从Vs出发的最短路径的终点的集合，它的初始化为空集。那么，从Vs出发到图上其余各顶点Vi可能达到的最短路径长度的初值为：D[i]=edges[s][i]Vi∈V2)选择Vj，使得D[j]=Min{D[i]|Vi∈V-S}，Vj就是当前求得的一条从Vs出发的最短路径的终点。令S=S∪{Vj}3)修改从Vs出发到集合V-S上任一顶点Vk可达的最短路径长度。如果D[j]+edges[j][k]<D[k]则修改D[k]为D[k]=D[j]+edges[j][k]重复操作(2)(3)共n-1次。由此求得从Vs到图上其余各顶点的最短路径。6.Dijstra算法的具体步骤1）初始时，S只包含源点，即S＝v0的距离为0。U包含除v0外的其他顶点，U中顶点u距离v0边上的权（若v与u有边或若u不是v的出边邻接点）。2）从U中选取一个距离v0最小的顶点k，把k加入S中（该选定的距离就是v0到k的最短路径长度）。3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v0到顶点u（u∈U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。4）重复步骤2）和3）直到所有顶点都包含在S中。Dijkstra算法的时间复杂度为O(n2)；空间复杂度取决于存储方式，为O(n2)7.Dijkstra算法举例说明如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）Dijkstra无向图图3.1DIJKSTRA无向图算法执行步骤如下表：表1步骤S集合中U集合中1选入QUOTE此时S=（A）此时最短路径AQUOTEA=0，以QUOTE为中间点，从QUOTE开始找。U=（B,C,D,E,F）AQUOTEB=6AQUOTEC=3AQUOTE发现AQUOTE权值为最短。2选入QUOTE此时S=(A,C)此时最短路径AQUOTEA=0,AQUOTEC=3以C为中间点，从AQUOTEC=3这条最短路径开始找。U=（B,D,E,F）AQUOTECQUOTEB=5此时到B模值为AQUOTECQUOTEB=5AQUOTECQUOTEB=6AQUOTECQUOTEB=7AQUOTECQUOTE其他U中的顶点=QUOTE发现AQUOTECQUOTEB=5权值为最短。3选入QUOTE此时S=(A,C,B)此时最短路径AQUOTEA=0,AQUOTEC=3，AQUOTECQUOTEB=5以B为中间点，从AQUOTECQUOTEB=5这条最短路径开始找。U=（D,E,F）QUOTEEQUOTED=10此时到D权值更改为QUOTED=6AQUOTECQUOTEBQUOTE其他U中的顶点=QUOTE发现QUOTED=6权值为最短4选入QUOTE此时S=(A,C,B,D)此时最短路径AQUOTEA=0,AQUOTEC=3，AQUOTECQUOTEB=5，QUOTED=6以D为中间点从QUOTED这条最短路径开始找。U=(E,F)QUOTEDQUOTE此时到E权值更改为QUOTEE=7QUOTEDQUOTEF=9发现QUOTEE=7权值为最短5选入QUOTE此时S=(A,C,B,D,E)此时最短路径AQUOTEA=0,AQUOTEC=3，AQUOTECQUOTEB=5，QUOTED=6，QUOTEE=7以E为中间点从QUOTEE=7这条最短路径开始找U=(F)QUOTEEQUOTE此时到F权值更改为QUOTEDQUOTE发现QUOTEDQUOTE权值为最短。6选入QUOTE此时S=(A,C,B,D,E,F)此时最短路径AQUOTEA=0,AQUOTEC=3，AQUOTECQUOTEB=5，QUOTED=6，QUOTEE=7。QUOTEDQUOTEF=9以F为中间点从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{每循环一次加入一个离1集合最近的结点并调整其他结点的参数}min:=maxint;u:=0;{u记录离1集合最近的结点}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可达的顶点距离值}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个顶点全部加入第一组为止}end;procedureprint_dij(i:integer);beginifi=xthenwrite(x:3)elsebeginprint_dij(d[i].pre);write(d[i].len,'')end;end;proceduremain_dij;begin//输入顶点数readln(x);//输入顶点间的距离矩阵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算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。Floyd算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。注意单独一条边的路径也不一定是最佳路径。2.Floyd算法的基本思想是:从邻接矩阵A开始进行n次迭代，第一次迭代后a[i,j]的值是从vi到vj且中间不经过变化大于1的顶点的最短路径长度；第k次迭代后a[i,j]的值是从vi到vj且中间不经过变化大于k的顶点的最短路径长度；第n次迭代后a[i,j]的值就是从vi到vj的最短路径长度。3.Floyd算法的核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)……最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。由于采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);4.Floyd算法的算法描述1).初始化：将除源点外的所有顶点的最短距离估计值d[v]←+∞,d[s]←0;2).迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离（运行|v|-1次）；3).检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点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)算法结束：D即为所有点对的最短路径矩阵5.Floyd算法的算法过程1．把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G[i,j]=空值。2．定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。3．把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值变小，则D[i,j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短路径的信息。时间复杂度O(n^3)6.Floyd算法优缺点分析Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点：时间复杂度比较高，不适合计算大量数据。7.Floyd算法最短路径算法{floyed算法求解所有可达顶点对之间的最短路径：o(n^3)}constn0=1000;varp:array[1..n0,1..n0]of0..n0;{path,p[i,j]表示i到j的最短路径上j的前驱结点}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的最短路径上j的前驱结点}fork:=1tondo{枚举中间结点}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）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最短路径的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。1.遗传算法的基本概念遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导路径最短的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。2.遗传算法的数学规划模型对于一个求函数最小值的优化问题(求函数最大值也类同)，一般可以描述为下列数学规划模型式中为决策变量，为目标函数式：式1-2、1-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。3.遗传算法的基本运算过程如下:a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价:计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。4.遗传算法定义遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。5.遗传算法特点(1)遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。(2)许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。（3）遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。(4)遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。6.遗传算法的应用由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学7.遗传算法的一些主要应用领域：1)．函数优化函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。2)．组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。8.遗传算法的现状进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（EvolutionProgramming,EP）以及进化策略（EvolutionStrategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacencybasedcrossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随机迭代遗传爬山法（StochasticIteratedGeneticHill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法（simplexmethod）结合起来，形成了一种叫单一操作的多亲交叉算子（simplexcrossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-blockCodedParallelGA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。9.遗传算法的一般算法1)．创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。2)．评估适应度对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。3)．繁殖(包括子代突变)带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。4)．下一代如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。5)．并行计算非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。10.术语说明由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是我们将会用来的一些术语说明：1)染色体(Chromosome)染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。2)基因(Gene)基因是串中的元素，基因用于表示个体的特征。例如有一个串S=1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alleles)。3)基因地点(Locus)基因地点在算法中表示一个基因在串中的位置称为基因位置(GenePosition)，有时也简称基因位。基因位置由串的左向右计算，例如在串S=1101中，0的基因位置是3。4)基因特征值(GeneFeature)在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。5)适应度(Fitness)各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数.这个函数是计算个体在群体中被使用的概率。11.运算过程遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度(适应度评估)施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题

图3.2遗传运算过程图的解，一代又一代地优化，并逼进最优解。遗传操作包括以下三个基本遗传算子(geneticoperator):选择(selection)；交叉(crossover)；变异(mutation)。这三个遗传算子有如下特点:个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。遗传操作的效果和上述三个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。遗传算法的下几种:适应度比例方法、随机遍历抽样法、局部选择法。其中轮盘赌选择法（roulettewheelselection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i被选择的概率,为遗传算法显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例.个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个[0，1]之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。交叉在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法：a)实值重组（realvaluedrecombination）1)离散重组（discreterecombination）；2)中间重组（intermediaterecombination）；3)线性重组（linearrecombination）；4)扩展线性重组（extendedlinearrecombination）。b)二进制交叉（binaryvaluedcrossover）1)单点交叉（single-pointcrossover）；2)多点交叉（multiple-pointcrossover）；3)均匀交叉（uniformcrossover）；4)洗牌交叉（shufflecrossover）；5)缩小代理交叉（crossoverwithreducedsurrogate）。最常用的交叉算子为单点交叉(one-pointcrossover)。具体操作是:在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：个体A：1001↑111→1001000新个体个体B：0011↑000→0011111新个体变异变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：a)实值变异；b)二进制变异。一般来说，变异算子操作的基本步骤如下:a)对群中所有个体以事先设定的编译概率判断是否进行变异；b)对进行变异的个体随机选择变异位进行变异。遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动(以变异概率P.做变动)，(0，1)二值码串中的基本变异操作如下:基因位下方标有*号的基因发生变异。变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小遗传算法的值，一般取0.001－0.1。终止条件当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。GA的流程图GA的流程图如右图遗传算法图3.3GA流程图适应度函数进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值.由此可见，在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。适应度函数的设计主要满足以下条件：a）单值、连续、非负、最大化；b)合理、一致性；c）计算量小；d）通用性强。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。初始群体的选取遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略:a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。第四章基于遗传算法的最短路径的实现4.1PCB钻孔走刀路径的最短路径问题的引入PCB钻孔走刀路径的优化问题可以简化为旅行商(TravelSalesmanProblem，TSP)问题。TSP问题是一个容易定义但难于处理的问题，属于NP完备问题。遗传算法(Ge—neticAlgorithm)是解决这类问题的一个非常实用的算法。采用遗传算法可以快速有效地找到全局最优解，极大地减少运算量，能够很好地解决PCB钻孔走刀路径优化的问题。目前，已经有一些学者做过关于用遗传算法解决PCB钻孔走刀路径优化问题的研究.现有的研究中，并没有很好地根据数控钻床钻头的运动特点确定目标函数，并且没有就算法中变异算子以及变异概率对优化结果的影响进行进一步的阐述。本文在采用遗传算法解决走刀路径最短问题的基础上，对上述问题进行了更详细的论述和分析，使遗传算法更加符合数控钻床走刀路径的特点，从而得到更好的优化结果。4.2最佳走刀路径模型的建立PCB上通常有许多不同直径的孔，PCB钻孔问题可以描述为：从换刀点出发，不重复不遗漏地加工完所有同一直径的孔后回到换刀点进行换刀操作，再加工另一直径的孔，直到完成所有待加工的孔。所以钻孔路径优化问题可以按照不同直径的孔分别进行优化处理。对于数控编程来说，就存在如何选择加工路径的问题，最好的加工路径应该使生产效率最高、空行程时间最短，即最佳的钻孔路径。显然，这一问题可以归结为旅行商问题，其中钻头代表旅行商，待加工的孔表示旅行商途径的城市，而最佳走刀路线的目标函数即为刀具的空行程花费时间最短。由于PCB数控钻机属于点位控制的机床，这种机床的刀具由一点运动到另一点的过程中，通常是沿X、Y轴同时移动。当两点之间的方向距离与Y方向距离不相等的时候，刀具在距离较小的方向上先完成运动，达到某一中间点。然后，在距离较大的方向上，刀具从中间点继续向终点运动。例如，刀具由换刀点开始按照1—2—3—4一