第13卷第7期2001年7月计算机辅助设计与图形学学报JO U RN A L OF CO M P U T ER -A IDED D ESI GN &CO M PU T ER G RA PHICSV o l.13,N o.7July ,2001PCB 数控钻孔最佳走刀路线的建模与求解王　霄 刘会霞(江苏理工大学机械工程学院　镇江　212013)摘要　目前,采用PCB 数控钻自动编程系统生成的钻孔路线并非最佳走刀路线.通过分析,将P CB 数控钻孔最佳走刀路线问题归结为大型T SP 问题,其目标函数定为钻头的总走刀时间最短.由于T SP 问题在理论上属于N P 完备问题,因此很难用一般的算法求解.文中详细介绍了用模拟退火方法求解该问题的具体算法,并以此为基础开发了P CB 最优化的自动编程系统.关键词　PCB,最佳走刀路线,T SP 问题,模拟退火方法中图法分类号　T P 391.73Modeling and Solving Optimal Moving Path for NC Drilling of PCBWANG Xiao LIU H ui-Xia(S chool of M ec hanical E ngineering ,Jiang su Univ er sity of S cience and T echnology ,Zh enj iang 212013)Abstract U p to now ,the gener ation of drilling path by automatic prog ramm ing system for pr inted circuit bo ards (PCB)did not give optim al solutio n.T he problem of optimizing the m oving path of NC drilling fo r PCB can be formulated as a larg e scale trav elling salesm an problem (T SP),and the g oal function is defined as the shortest total tim e o f mo ving drill.Because T SP is know n to be a NP-co mplete pro blem ,it w ould be too difficult to tackle it w ith traditional opti-mization metho ds.In this paper,an algo rithm of solving TSP for PCB by sim ulated annealing is pr esented in detail.Based on the research,an optim al autom atic pr ogram ming system for PCB is developed.Key words PCB ,optimal m oving path ,T SP ,Sim ulated Annealing (SA ) 原稿收到日期:2000-03-25;修改稿收到日期:2001-03-05.王　霄,男,1964年生,讲师,主要研究方向为CAD/CAM 、虚拟制造.刘会霞,女,1964年生,副教授,主要研究方向为网络辅助设计与制造、多媒体CAI .1　引 言目前,国内外广泛采用PROT EL ,T ANGO ,ORCAD,P-CADEE 等印刷电路板CAD 软件设计PCB .将PCB -CAD 生成的PCB 图形文件输入光绘仪可获得光绘正片;生成的钻孔数控文件经自动编程处理生成NC 指令,以供PCB 专用数控钻床进行敷铜版焊盘孔的加工.然而在生成NC 指令方面,现有的PCB 自动编程软件采用按孔位的X Y 坐标以某种约定逐次编排的方法确定钻孔的走刀顺序.显然,这样生成的钻孔走刀路线并非最佳路线,影响生产效率.这对于那些年产几千块到几十万块PCB 的中、大批量生产规模的专用生产厂家来说,其影响相当可观.关于这一问题,国外学者进行了不少研究与探讨,足见其整体工艺过程优化的强烈意识.2　最佳走刀路线模型的建立PCB 上通常有多种不同直径的孔,对某一种孔径所构成的孔系,PCB 数控钻问题可描述为:从换刀点出发,不重复又不遗漏地加工完所有孔,再回到换刀点,进行下一种孔径换刀和加工.这对数控编程而言,就存在如何安排孔的加工顺序(路线),使空程移动时间最短,即所谓最佳走刀路线问题.显然,这一问题可归结为著名的旅行售货员问题,其中钻头扮演了售货员的角色,而最佳走刀路线的目标函数可选为刀具的空行程最短或空行程花费的时间最短.现讨论分析:PCB 数控钻都是具有点位控制的数控机床,这种机床的刀具由一点(孔)运动到另一点(孔)时,通常是沿X Y 轴方向同时快速移动.当沿X Y 轴各自距离不同时,坐标值小者先完成运动,到达某一中间点(如图1中由0点到A 点).另一坐标将沿坐标轴方向从中间点继续向终点(如图1中1点)运动,由换刀点0经过1→2→3→4→5返回换刀点0的运动轨迹如图1所示.从图1可知,刀具从一孔到另一孔,其快速移动的走刀路线一般不是直线,而是折线.以0到1为例,其两点间的空行程S (0,1)=S 0a +S a 1=(X 1-X 0)/co s45°+[(Y 1-Y 0)-(X 1-X 0)×tan45°],而两点间的空行程时间t (I ,J )=m ax{ûX J -X I û/V X ,ûY J -Y I û/V Y }.其中,V 为工作台相对刀具的X 或Y 方向的快移速度,一般V X =V Y =V .由于求最短路线的目的是为了减少空程时间,因此,采用计算比较简单的最短空程时间作为衡量最佳走刀路线的目标函数能提高计算效率.显然,最小化t (I ,J )相对于最小化DT (I ,J )=max {ûX J -X I û,ûY J -Y I û}作为衡量最佳走刀路线的目标函数更简化.3　最佳走刀路线的求解方法TSP 问题是实际应用中出现的复杂问题的集中概括和简化形式,是一个容易定义但难于处理的问题,属于NP 完备问题.在迄今所提出的TSP 的各种解法中基本可分为3类:精确求解法、启发式求解法以及神经网络算法.精确求解法仅能解较小规模的T SP 问题,显然对PCB 问题不适合.PCB 的最佳走刀路线问题属于大规模T SP 问题.国外学者对这一问题作了不少研究[2—5],基本上都是采用启发式求解法,并且其算法都建立在两点间欧几里德距离的基础上,即d I J =SQRT [(X J -X I )2+(Y J -Y I )2].从前面分析可知,这与数控钻所走的路径不符.这样,利用其位置信息或利用三角不等式的几何特征提出的算法就很难有效地解决这一问题.本系统以空行程时间为目标函数,采用模拟退火方法[1,6]有效地解决了这一问题.3.1　模拟退火算法SA (Simulated Annealing )SA 算法将组合优化问题与统计力学中的热平衡问题相类比,开辟了一条求解组合优化问题的新途径.它通过模拟退火过程,可以找到全局(或近似)最优解.SA 算法是基于M ontecar lo 迭代求解法的一种启发式随机搜索算法.设S ={s 1,…,s k }为所有可能的组合状态集合,C :S →R 为非负目标函数,即C (s i )≥0反映取状态s i 为解的代价,则组合优化问题可形式地表述为寻找s *∈S ,使得C (s *)=m in C (s i ),P s i ∈S .SA 算法的基本思想是:将每种组合状态s i 看成某一物体体系的微观状态,C (s i )看成该物质体系在状态s i 下的能量,并用控制参数T 表示伪温度.让T 从一个足够高的值慢慢下降,对每个T ,用M etropolis 抽样法模拟该体系在此T 下的热平衡状态,即对当前状态s 做随机扰动,生成一个新状态s ′,计算增量$C ′=C (s ′)-C (s ),并以概率ex p(-$C /bT )接受s ′作为新的当前状态.当这样的随机扰动重复足够多的次数后,系统将达到该温度下的热平衡状态,并且系统的状态将导致Bo ltzmann 分布,b 是Boltzm ann 常数.SA 算法的主要步骤描述如下.算法1.SA-Algo rithmpr ocedur e SA _A lgor ithm (i 0,T 0);/*s i 0为任一初态,T 0为初始控制参数*/beg in(1)s ←s i 0;C *←C i ;k ←0/*简记C i =C (s i ),C *为当前代价值.*/(2)repeat (2.1)repeat5917期王　霄等:P CB 数控钻孔最佳走刀路线的建模与求解　(2.1.1)s j←Gener ate(s);(2.1.2)if C j≤C*then s←s j else if A ccep t(j,s)t hen s←s j endifendif(2.1.3)until　内循环结束条件;(2.2)T K+1←Up date(T k);k←k+1(3)until T k≤Eend其中,(1)为初始化;(2.1.1)的Gener ate(s)表示从s的邻域中随机产生下一个状态s j.若C j≤C*,则接受j为新的当前状态;否则仅以一定的概率接受j为新的当前状态,这也就是Accep t(j,s)函数的功能;(2.1.3)中的内循环结束条件是指在每一度T k下迭代多少次以达到平衡态;(2.2)中的Up date(T k)函数则表示温度每次下降的速率.由此可知,SA算法有3个重要函数:产生函数Gen-erate,接受函数A ccep t和温度更新函数Up d ate.在实际应用中,初始温度T0、内循环次数和终止条件也是影响SA算法性能的重要参数.3.2　用SA算法求解TSP问题传统的启发式算法主要有两种:一种是先自顶向下的分而治之,再自底向上的组合求解的分治法;第二种是步步贪心,以达到全局最优的迭代法.SA 算法可看成是上述两种方法的综合.在高温下,它是大粒度的分治法;而在低温下,是细粒度的贪心法.由于SA算法中能做概率性的扰动以跳出局部极小,因而可获得全局最优解.用SA求解T SP问题的关键是如何确定函数形式与各参数.(1)目标函数.设R=(i0,i1,…,i N)为顶点的一个排列,则优化目标函数就可取为路径长度,即c(s i)=∑j ‖A j A Ri(j)‖,j∈[1,N].(2)产生函数Gener ate.function T SP-Gener ate(s i);/*令s i=(i1,…,i N)*/begini←Rando m(1,N-1);j←R andom(i+1,N);ret ur n(S wap(i,j,s i,s j))end它表示交换顶点A i和A j,看能否产生较短的周游路径,即可用弧(X i-1,X j),(X j,X i+1),(X j-1,X i), (X i,X j+1)去替代弧(X i-1,X i),(X i,X i+1),(X j-1,X j),(X j,X j+1).(3)接受函数A ccep t.A ccep t函数通常取如下形式functio n A ccep t(j,s);begin$C′←C j-C*;if ex p(-$C′/bT K)>Ra ndom(0,1)/*b为Boltzmann常数*/then A ccep t←tr ueelse A ccep t←falseendifend(4)温度更新函数Up date.Up date实质就是退火策略,这种策略的选择是最关键的,因为算法中影响解收敛质量的温度由退火策略控制.常见的退火策略有:a.T k+1=AõT K (0<A<1),b.T k+1=T k/(H BõT k)　(B<<T0),c.T k+1=T kõex p(0.7T k/R) (R为目标函数值的标准偏差[6]).其中c是一种自适应的退火策略,本文即选用这种退火策略.SA算法是一个通用的、与领域无关的具有概率爬山的、能逃离局部最优的强有力的组合优化算法,对T SP而言,它是较好的模型之一,目前能处理的城市数目已达6000个之多.3.3　运行实例算法1用Visual C++ 5.0编写,在奔腾III处理器650M Hz计算机上调试并运行通过.图2是某一PCB(N o.Citys=64)按一般PCB-CAD软件所生成的钻孔走刀路线图.图3是利用本文算法生成的钻孔走刀路线图.比较图2,3可以看出,其走刀空行程缩短了36.5%.通过大量实例比较,发现用该算法所得的优化走刀路线比用一般PCB-CAD软件按孔位的X Y坐标,以某种约定逐次编排的方法确592计算机辅助设计与图形学学报2001年定的走刀路线节省的行程显著,一般在25%以上,该方法实用、可靠并能获得较好的解.4　PCB 最优数控编程系统PCB 数控钻孔最佳走刀路线的确定,有效地解决了PCB 加工工艺过程的优化数控编程问题.在此基础上开发了PCB 自动编程系统,其工作流程如图4所示.图4的工作原理是将不同类型的PCB-CAD 系统中生成的不同格式的PCB 钻孔数据文件交给前置处理器.前置处理器的作用是分析识别不同CAD 系统产生的钻孔数据文件内容,并按不同孔径族提取位置信息,将其转化为统一的数据文件形式,作为确定某一钻头最佳走刀路线模型的数据源;再经最佳走刀路线模块确定钻孔的最佳走刀路线,然后交给后置处理器处理.后置处理器的任务是由扫描器读入不同的钻头直径、最佳走刀路线模型位置信息及具体数控机床的数控特性文件,由语义分析器进行分析并产生对应数控机床的数控指令,最后由DNC 通讯程序将数控指令传输给对应的数控机床.5　结束语本文将PCB 数控钻孔最佳路线归结为TSP 问题,给出了利用SA 算法求解最佳走刀路线的目标函数及3个重要函数:产生函数Gener ate 、接受函数A ccep t 及温度更新函数Up date .其中,退火策略在模拟退火中起重要作用,直接影响TSP 解的质量.该算法已成功应用于激光数控打孔中,并在PCB 数控钻孔CAM 系统中试用.该算法有效地解决了多孔加工中刀具路径冗长、空行程导致加工效率低的问题,使数控钻孔加工工艺得以优化.参考文献1S Kirk patrick,et al .Optimiz ation by simu lated an nealing.S ci-ence,1983,220(4598):671-6802Conley W C.Programming an au tomated pun ch or drill.In ter-national J ou rnal of Systems Science,1991,22(11):2039-20563J D litke.An improved solution to the traveling salesman prob-lem w ith thous ands of n munications of the ACM ,1984,2(12):1227-12364Vangelis F M agirou.T he efficient dr illing of printed cir cuit boards .Inter faces ,1988,16(4):13-235S urya Danusaputro,et al .An efficient algorithm for drilling printed circu it boards .Computer s and Indus trial Engin eering ,1990,18(2):145-1516S zykman S ,Cagan J .A s imulated annealing -based approach to three-d imens ional componentpacking.T ransaction of theAS M E ,1995,117(3):308-3145937期王　霄等:P CB 数控钻孔最佳走刀路线的建模与求解。