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

毕业设计（论文）设计题目数控PCB钻机最短路径计算所属院（系）电子信息工程2012年06月14目录摘要IIIABSTRACTIV第一章钻孔机111PCB钻孔机结构介绍1111数控机床的介绍1112数控机床的组成部分112PCB钻孔机用途介绍2121PCB的概念2122数控机床的特点2123PCB在各种电子设备中有如下功能3第二章最短路径相关知识421图4211图的定义及基本术语4212图的存储结构5213图的遍历5214图的应用单源最短路径622最短路径问题7221最短路径7222算法具体的形式723最短路径的思想及算法7231求最短路径的算法思想7232从源点到各终点的最短路径的算法描述如下8233求以V0为源点的最短路径算法如下8第三章几种最短路径算法的介绍1331求网络图形最短路径的问题上的算法13311路径算法13312最常用的路径算法13313统一的归纳总结与分析比较1332几种主要的最短路径算法的介绍13321DIJKSTRA算法13322FLOYED算法20323遗传算法23第四章基于遗传算法的最短路径的实现3441PCB钻孔走刀路径的最短路径问题的引入3442最佳走刀路径模型的建立3443遗传算法及走刀路径算法没计35431遗传算法概述35432走刀路径优化算法设计36433染色体编码方式36434适应度函数36435选择算子37436交叉算子37437变异算子3744走刀路径优化算法流程38总结40参考文献41致谢42摘要印刷电路板PRINTEDCIRCUITBOARD，PCB是电子设备中最重要的组成部分之一。而PCB的钻孔工序是PCB制造过程中重要的一个环节。其中钻孔路径即走刀的路径是否最短对于提高加工效率来说是至关重要的。而现有的PCB设计软件虽然具有自动生成钻孔NC程序的功能，但是其生成的走刀路径并非最短路径。这样会影响加工效率。PCB钻孔走刀最短路径问题可以简化为旅行商TRAVELSALESMANPROBLEM，TSP问题。旅行商问题，即TSP问题（TRAVELINGSALESMANPROBLEM）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。遗传算法GENETICALGORITHM是解决这类问题的一个非常实用的算法。采用遗传算法可以快速而有效地找到全局最优解，极大地减少运算量，能够很好地解决PCB钻孔走刀的最短路径问题。目前，已经有一些学者做过关于用遗传算法解决PCB钻孔走刀的最短路径问题的现有的研究中，并没有很好地根据数控钻床钻头的运动特点确定目标函数，并且没有就算法中变异算子以及变异概率对路径最短结果的影响进行进一步的阐述。本文在采用遗传算法解决走刀的最短路径问题的基础上，对上述问题进行了更详细的论述和分析，使遗传算法更加符合数控钻机走刀路径的特点，从而得到最短路径。关键字PCB数控钻机，最短路径算法，DIJKSTRA算法，FLOYED算法，遗传算法。ABSTRACTPRINTEDCIRCUITBOARDPCBMARITIMEBOARD,THEVEHICLEISTHEELECTRONICEQUIPMENTINTHEMOSTIMPORTANTPARTOFANDPCBDRILLINGPROCESSISPCBMANUFACTURINGPROCESSIMPORTANTLINKSAMONGTHEMISDRILLINGPATHTOOLPATHTOIMPROVEMANUFACTURINGEFFICIENCYOPTIMIZATIONOFITISOFVITALIMPORTANCEWHILETHEEXISTINGPCBDESIGNSOFTWAREALTHOUGHHASTHEAUTOMATICGENERATIONOFDRILLINGNCPROGRAMFUNCTION,BUTITSGENERATIONTOOLPATHISNOTTHEBESTPATHTHISWILLAFFECTMACHININGEFFICIENCYFORMASSPRODUCTION,THEMANUFACTURERFOR,ITSINFLUENCEISQUITEOBVIOUSPCBDRILLINGTOOLPATHCANSIMPLIFYTHEOPTIMIZATIONPROBLEMFORTRAVELINGSALESMANSALESMAN,TSPMYPROMOTIONTHETSPPROBLEMISANEASYTODEFINEBUTDIFFICULTTODEALWITHPROBLEMS,ISNPCOMPLETEPROBLEMSGENETICALGORITHMGENETICDONETOSOLVETHISKINDOFPROBLEMISAVERYPRACTICALALGORITHMKEYWORDSPCBDRILLINGMACHINE,ASHORTESTPATHALGORITHM,DIJKSTRAALGORITHM，FLOYEDALGORITHM,GENETICALGORITHM第一章钻孔机11PCB钻孔机结构介绍111数控机床的介绍数控机床是数字控制机床（COMPUTERNUMERICALCONTROL）的简称，是一种装有程序控制系统的自动化机床。该控制系统能够逻辑地处理具有控制编码或其他符号指令规定的程序，并将其译码，从而使机床动作并加工零件。图11PCB钻孔机112数控机床的组成部分1主机，它他是数控机床的主体，包括机床身、立柱、主轴、进给机构等机械部件。它是用于完成各种切削加工的机械部件。2数控装置，是数控机床的核心，包括硬件（印刷电路板、CRT显示器、键盒、纸带阅读机等）以及相应的软件，用于输入数字化的零件程序，并完成输入信息的存储、数据的变换、插补运算以及实现各种控制功能。3驱动装置，它是数控机床执行机构的驱动部件，包括主轴驱动单元、进给单元、主轴电机及进给电机等。它在数控装置的控制下通过电气或电液伺服系统实现主轴和进给驱动。当几个进给联动时，可以完成定位、直线、平面曲线和空间曲线的加工。4辅助装置，指数控机床的一些必要的配套部件，用以保证数控机床的运行，如冷却、排屑、润滑、照明、监测等。它包括液压和气动装置、排屑装置、交换工作台、数控转台和数控分度头，还包括刀具及监控检测装置等等。5编程及其他附属设备，可用来在机外进行零件的程序编制、存储等等。12PCB钻孔机用途介绍121PCB的概念PCB为PRINTEDCIRCUITBOARD印制板1936年，英国EISLER博士提出印制电路（PRINTEDCIRCUIT）这个概念。他首创在绝缘基板上全面覆盖金属箔，在其金属箔上涂上耐蚀刻油墨后再将不需要的金属箔腐蚀掉的PCB制造基本技术。1942年，EISLER博士制造出世界上第一块纸质层压绝缘基板，用于收音机的印制板。122数控机床的特点数控机床的操作和监控全部在这个数控单元中完成，它是数控机床的大脑。与普通机床相比，数控机床有如下特点1加工精度高，具有稳定的加工质量；2可进行多坐标的联动，能加工形状复杂的零件；3加工零件改变时，一般只需要更改数控程序，可节省生产准备时间；4机床本身的精度高、刚性大,可选择有利的加工用量，生产率高（一般为普通机床的35倍）；5机床自动化程度高，可以减轻劳动强度；6对操作人员的素质要求较高，对维修人员的技术要求更高。123PCB在各种电子设备中有如下功能1提供集成电路等各种电子元器件固定、装配的机械支撑。2实现集成电路等各种电子元器件之间的布线和电气连接（信号传输）或电绝缘。提供所要求的电气特性，如特性阻抗等。3为自动装配提供阻焊图形，为元器件插装、检查、维修提供识别字符和图形。PCB数控钻铣床是一种典型的点位运动控制系统，是印制电路板精密导通孔加工的关键设备。随着电子产品向微型化、小型化方向发展，印制电路板对导通孔的孔径、线宽、线距的要求越来越高。相应地，PCB数控系统正朝高速、高精度、高可靠性、系统集成化、柔性化、智能化程度高的开放式方向发展。第二章最短路径相关知识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度在无向图中，与某个顶点相连的边的数目称为该顶点的度。在有向图中，以某个顶点为初始点的弧的数目，称为该顶点的出度。以某个顶点为终端的弧数目称为该顶点的入度。（3）路径和回路在无向图中，从顶点VP到顶点VQ的路径是顶点序列VP,VIL，VI2,VIK,VIQ且（VP，VI1）VIK,VIQ均是E中的边。在有向图，则由顶点的弧组成有向路径路径。路径上的边或弧的数目称为路径长度。网络的路径长度定义为路径上权值的和。除第一个和最后一个顶点外，序列中其余顶点各不相同的路径称为简单路径。第一个顶点和最后一个顶点相同的简单路径称为简单回路。（4）连通图和连通分量在无向图中，如果从VI到VJ存在有路径，则称VI和VJ是连通的。若在顶点集合V中每一对不同顶点VI和VJ都连通，称G为连通图。否则，将其中的极大连通子图称为连通分量。212图的存储结构1邻接矩阵存储结构11有向图的邻接矩阵具有N个顶点的有向图可以用一个NN的方形矩阵表示。假设该矩阵的名称为M，则当是该有向图中的一条弧时，MI,J1；否则MI,J0。第I个顶点的出度为矩阵中第I行中“1“的个数；入度为第I列中“1“的个数，并且有向图弧的条数等于矩阵中“1“的个数。12无向图的邻接矩阵具有N个顶点的无向图也可以用一个NN的方形矩阵表示。假设该矩阵的名称为M，则当（VI,VJ）是该无向图中的一条边时，MI,JMJ,I1；否则，MI,JMJ,J0。第I个顶点的度为矩阵中第I行中“1“的个数或第I列中“1“的个数。图中边的数目等于矩阵中“1“的个数的一半，这是因为每条边在矩阵中描述了两次2邻接表邻接表是图的一种链式存储结构，在邻接表中，对图中每个顶点建立一个单链表，第I个单链表中的节点表示依附于顶点VI的边，每个链结点由三部分组成邻接域（ADJVEX）表示与是顶点VI邻接的点的序号，链域NEXTARE表示下一条边或弧的结点，数据域（DATA）存储和边或弧相关的信息，如权值等。213图的遍历常见的图遍历方式有两种深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。（1）深度优先遍历深度优先遍历的基本思想是从图的某一个顶点V0出发进行遍历，首先访问起始点V0，然后依次从V0的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与V0有路径相通的顶点都被访问完为止。对于无向图，这个算法可以遍历到V顶点所在的连通分量中的所有顶点，而与V顶点不在一个连通分量中的所有顶点遍历不到；而对于有向图可以遍历到起始顶点V0能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测（2）广度优先遍历对图的广度优先遍历的基本思想是首先访问初始点VI，并将其标记为已访问过，接着访问VI的所有未被访问过的邻接点VI1,VI2,VIK，并均标记已访问过，然后再按照VI1,VI2,VIK的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点VI有路径相通的顶点都被访问过为止。实现广度优先遍历算法需要考虑的几个问题（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点访问顺序，就可以利用队列结构的操作特点，将访问的每个顶点入队，然后，再依次出队，并访问它们的邻接点；（2）在广度优先遍历过程中同深度优先遍历一样，为了避免重复访问某个顶点，也需要创建一个一维数组VISITED0N1（N是图中顶点的数目），用来记录每个顶点是否已经被访问过。214图的应用单源最短路径1单源最短路径的问题背景单源元最短路径的问题背景从一个给定的城市出发，能否到达其他各城市，走那几条公路花费最少，我们用一个有向网表示城市的公路网，顶点表示城市，弧代表公路段，弧上的权值代表两城市的距离，或运输所需的代价。习惯上称给定的出发点为原点，其其他的点称为终点。单元最短路径问题一般提法是从有向网的原点到其他各终点是否有路径最短路径是什么最短路径的长度是多少2我们可以发现有这样一个事实如果P是G中从VS到VJ的最短路，VI是P中的一个点，那么，从VS沿P到VI的路是从VS到VI的最短路。3从原点到终点的最短路径有三种情况（1）没有路径；（2）只有一条路径，即位最短路径；（3），有几条路径，其中有一条为最短路径。4所谓单源最短路径问题是指已知图G（V，E），我们希望找出从某给定的源结点SV到V中的每个结点的最短路径。22最短路径问题221最短路径最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的中两结点之间的最短路径。222算法具体的形式算法具体的形式包括1确定起点的最短路径问题即已知起始结点，求最短路径的问题。2确定终点的最短路径问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。3确定起点终点的最短路径问题即已知起点和终点，求两结点之间的最短路径。4全局最短路径问题求图中所有的最短路径。23最短路径的思想及算法231求最短路径的算法思想先找出从原点到各终点的直达路径，即通过一条弧到达的路径。从这些路径中找出一条最短的路径最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括确定起点的最短路径问题即已知起始结点，求最短路径的问题。确定终点的最短路径问题与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。确定起点终点的最短路径问题即已知起点和终点，求两结点之间的最短路径。全局最短路径问题求图中所有的最短路径。，然后对其余各条路径做适当调整。232从源点到各终点的最短路径的算法描述如下1设AS1N,1N为有向网的带权邻接矩阵，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需要经过的点，初始化DI,JJ。把各个顶点插入图中，比较插点后的距离与原来的距离，GI,JMINGI,J,GI,KGK,J，如果GI,J的值变小，则DI,JK。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D5,13则说明从V5到V1经过V3，路径为V5,V3,V1，如果D5,33，说明V5与V3直接相连，如果D3,11，说明V3与V1直接相连。时间复杂度ON3优缺点分析FLOYD算法适用于APSPALLPAIRSSHORTESTPATHS，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次DIJKSTRA算法。优点容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点时间复杂度比较高，不适合计算大量数据。VIEWPLAINCOPYTOCLIPBOARDPRINTINCLUDEUSINGNAMESPACESTDCONSTINTN101CONSTINTMAX32767INTMAPNNINTMAININTNINTI,J,KINTASKX,ASKYCINNCINASKXASKYFORI1IMAPIJIFMAPIJ0MAPIJMAXFORK1KFLOYDWARSHALL算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。编辑本段算法概述单独一条边的路径也不一定是最佳路径。从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。对于每一对顶点U和V，看看是否存在一个顶点W使得从U到W再到V比己知的路径更短。如果是更新它。不可思议的是，只要按排适当，就能得到结果。/DISTI,J为从节点I到节点J的最短距离FORI1TONDOFORJ1TONDODISTI,JWEIGHTI,JFORK1TONDO/K为“媒介节点”一定要先枚举媒介节点FORI1TONDOFORJ1TONDOIFDISTI,KDISTK,J上的权值。若不存在，则置EDGESIJ（计算机上用一个允许的最大值代替）。S为已经找到的从VS出发的最短路径的终点的集合，它的初始化为空集。那么，从VS出发到图上其余各顶点VI可能达到的最短路径长度的初值为DIEDGESSIVIV2选择VJ，使得DJMINDI|VIVS，VJ就是当前求得的一条从VS出发的最短路径的终点。令SSVJ3修改从VS出发到集合VS上任一顶点VK可达的最短路径长度。如果DJEDGESJKMAXINTTHENDIPREXELSEDIPRE0ENDAX,X1REPEAT每循环一次加入一个离1集合最近的结点并调整其他结点的参数MINMAXINTU0U记录离1集合最近的结点FORI1TONDOIFAI,I0ANDDILEN0THENBEGINAU,U1FORI1TONDO修正第二组中U可达的顶点距离值IFAI,I0ANDAU,IDULENXANDDILENMAXINT若I与X间有通路，则输出它们之间的最短距离和路径方案THENBEGINWRITELNDILENPRINT_DIJIENDWRITELNENDEND322FLOYED算法1FLOYD算法的定义FLOYD算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。FLOYD算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。注意单独一条边的路径也不一定是最佳路径。2FLOYD算法的基本思想是从邻接矩阵A开始进行N次迭代，第一次迭代后AI,J的值是从VI到VJ且中间不经过变化大于1的顶点的最短路径长度；第K次迭代后AI,J的值是从VI到VJ且中间不经过变化大于K的顶点的最短路径长度；第N次迭代后AI,J的值就是从VI到VJ的最短路径长度。3FLOYD算法的核心思路通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵AAI,JNN开始，递归地进行N次更新，即由矩阵D0A，按一个公式，构造出矩阵D1；又用同样地公式由D1构造出D2最后又用同样的公式由DN1构造出矩阵DN。矩阵DN的I行J列元素便是I号顶点到J号顶点的最短路径长度，称DN为图的距离矩阵，同时还可引入一个后继节点矩阵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需要经过的点，初始化DI,JJ。3把各个顶点插入图中，比较插点后的距离与原来的距离，GI,JMINGI,J,GI,KGK,J，如果GI,J的值变小，则DI,JK。在G中包含有两点之间最短道路的信息，而在D中则包含了最短路径的信息。时间复杂度ON36FLOYD算法优缺点分析FLOYD算法适用于APSPALLPAIRSSHORTESTPATHS，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次DIJKSTRA算法。优点容易理解，可以算出任意两个节点之间的最短距离，代码编写简单；缺点时间复杂度比较高，不适合计算大量数据。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）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导路径最短的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。2遗传算法的数学规划模型对于一个求函数最小值的优化问题求函数最大值也类同，一般可以描述为下列数学规划模型式中为决策变量，为目标函数式式12、13为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。3遗传算法的基本运算过程如下A初始化设置进化代数计数器T0，设置最大进化代数T，随机生成M个个体作为初始群体P0。B个体评价计算群体PT中各个个体的适应度。C选择运算将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。D交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。E变异运算将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体PT经过选择、交叉、变异运算之后得到下一代群体PT1。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年DWHITEY在他的论文中提出了基于领域交叉的交叉算子（ADJACENCYBASEDCROSSOVER），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。DHACKLEY等提出了随机迭代遗传爬山法（STOCHASTICITERATEDGENETICHILLCLIMBING，SIGH）采用了一种复杂的概率选举机制，此机制中由M个“投票者”来共同决定新个体的值（M表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。HBERSINI和GSERONT将遗传算法与单一方法（SIMPLEXMETHOD）结合起来，形成了一种叫单一操作的多亲交叉算子（SIMPLEXCROSSOVER），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。国内也有不少的专家和学者对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（BUILDINGBLOCKCODEDPARALLELGA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。9遗传算法的一般算法1创建一个随机的初始状态初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。2评估适应度对每一个解染色体指定一个适应度的值，根据问题求解的实际接近程度来指定以便逼近求解问题的答案。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。3繁殖包括子代突变带有较高适应度值的那些染色体更可能产生后代后代产生后也将发生突变。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。4下一代如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。5并行计算非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。10术语说明由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是我们将会用来的一些术语说明1染色体CHROMOSOME染色体又可以叫做基因型个体INDIVIDUALS,一定数量的个体组成了群体POPULATION,群体中个体的数量叫做群体大小。2基因GENE基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因ALLELES。3基因地点LOCUS基因地点在算法中表示一个基因在串中的位置称为基因位置GENEPOSITION，有时也简称基因位。基因位置由串的左向右计算，例如在串S1101中，0的基因位置是3。4基因特征值GENEFEATURE在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。5适应度FITNESS各个个体对环境的适应程度叫做适应度FITNESS。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数这个函数是计算个体在群体中被使用的概率。11运算过程遗传操作是模拟生物基因遗传的做法。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群体的个体按照它们对环境适应度适应度评估施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度而言，遗传操作可使问题图32遗传运算过程图的解，一代又一代地优化，并逼进最优解。遗传操作包括以下三个基本遗传算子GENETICOPERATOR选择SELECTION；交叉CROSSOVER；变异MUTATION。这三个遗传算子有如下特点个体遗传算子的操作都是在随机扰动情况下进行的。因此，群体中个体向最优解迁移的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的高效有向的搜索而不是如一般随机搜索方法所进行的无向搜索。遗传操作的效果和上述三个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。遗传算法的下几种适应度比例方法、随机遍历抽样法、局部选择法。其中轮盘赌选择法（ROULETTEWHEELSELECTION）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为N，其中个体I的适应度为，则I被选择的概率,为遗传算法显然，概率反映了个体I的适应度在整个群体的个体适应度总和中所占的比例个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个0，1之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。交叉在自然界生物进化过程中起核心作用的是生物遗传基因的重组加上变异。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法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新个体变异变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法A实值变异；B二进制变异。一般来说，变异算子操作的基本步骤如下A对群中所有个体以事先设定的编译概率判断是否进行变异；B对进行变异的个体随机选择变异位进行变异。遗传算法引入变异的目的有两个一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。基本变异算子是指对群体中的个体码串随机挑选一个或多个基因座并对这些基因座的基因值做变动以变异概率P做变动，0，1二值码串中的基本变异操作如下基因位下方标有号的基因发生变异。变异率的选取一般受种群大小、染色体长度等因素的影响，通常选取很小遗传算法的值，一般取000101。终止条件当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100500代。GA的流程图GA的流程图如右图遗传算法图33GA流程图适应度函数进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函数来进行评估的。遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值由此可见，在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。适应度函数的设计主要满足以下条件A）单值、连续、非负、最大化；B合理、一致性；C）计算量小；D）通用性强。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。初始群体的选取遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略A根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。B先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。第四章基于遗传算法的最短路径的实现41PCB钻孔走刀路径的最短路径问题的引入PCB钻孔走刀路径的优化问题可以简化为旅行商TRAVELSALESMANPROBLEM，TSP问题。TSP问题是一个容易定义但难于处理的问题，属于NP完备问题。遗传算法GENETICALGORITHM是解决这类问题的一个非常实用的算法。采用遗传算法可以快速有效地找到全局最优解，极大地减少运算量，能够很好地解决PCB钻孔走刀路径优化的问题。目前，已经有一些学者做过关于用遗传算法解决PCB钻孔走刀路径优化问题的研究现有的研究中，并没有很好地根据数控钻床钻头的运动特点确定目标函数，并且没有就算法中变异算子以及变异概率对优化结果的影响进行进一步的阐述。本文在采用遗传算法解决走刀路径最短问题的基础上，对上述问题进行了更详细的论述和分析，使遗传算法更加符合数控钻床走刀路径的特点，从而得到更好的优化结果。42最佳走刀路径模型的建立PCB上通常有许多不同直径的孔，PCB钻孔问题可以描述为从换刀点出发，不重复不遗漏地加工完所有同一直径的孔后回到换刀点进行换刀操作，再加工另一直径的孔，直到完成所有待加工的孔。所以钻孔路径优化问题可以按照不同直径的孔分别进行优化处理。对于数控编程来说，就存在如何选择加工路径的问题，最好的加工路径应该使生产效率最高、空行程时间最短，即最佳的钻孔路径。显然，这一问题可以归结为旅行商问题，其中钻头代表旅行商，待加工的孔表示旅行商途径的城市，而最佳走刀路线的目标函数即为刀具的空行程花费时间最短。由于PCB数控钻机属于点位控制的机床，这种机床的刀具由一点运动到另一点的过程中，通常是沿X、Y轴同时移动。当两点之间的方向距离与Y方向距离不相等的时候，刀具在距离较小的方向上先完成运动，达到某一中间点。然后，在距离较大的方向上，刀具从中间点继续向终点运动。例如，刀具由换刀点开始按照1234一5的顺序进行加工，再回到换刀点的轨迹如图1所示。图41钻头运动轨迹示意图如图所示，刀具从换刀点开始，先运动到中间点A，然后运动到第一个孔的位置、下钻，完成钻孔切削后刀具运动到中间点B，再运动到第二个孔的位置、下钻，重复上述过程直到刀具回到换刀点。所以刀具在加工中的运动轨迹为折线，而非直接运动到待加工孔的位置。两点问的空行程的时间为TI,JMAX,其中VX和VY分别为钻头在X轴和Y轴方向上的速度，一般来说两者相等，这样，对于同一直径孔的加工，寻找最优走刀路径就可以转化为找到一个路径使MAXIXI一XI1L，IYI一YI1L最小的问题，其中I1，2，3，N