模拟退火在印刷电路板最佳走刀问题中的应用

张洪雨，叶艳，杨小燕

（成都理工大学管理科学学院，成都610059）

模拟退火在印刷电路板最佳走刀问题中的应用

张洪雨，叶艳，杨小燕

（成都理工大学管理科学学院，成都610059）

电路板（PCB）走刀路线问题可以归结为大型TSP问题。在构造了电路板走刀路线问题的模型后，采用加权的哈密顿图方法，结合模拟退火策略对该问题进行分析求解。重点介绍了模拟退火解决这个问题的具体算法和过程。仿真试验结果表明:采用模拟退火算法求解TSP问题效果更好，与有关算法相比有更好的可操作性。

印刷电路板；哈密顿圈；蒙特卡洛方法；模拟退火

关于印刷电路板走刀问题，当前，国内外广泛采用CAD软件来设计PCB。通过这种软件生成的钻孔数控文件经自动编程处理生成NC指令以供PCB专用数控钻床进行加工。现有的自动编程软件采用按孔位的XY坐标以某种约定的逐次编排方法确定钻孔走刀顺序，这样生成的钻孔走刀路线显然并非最佳路线，对于大批量生产规模的专用生产来说其影响生产效率相当可观，足见其整体过程优化的重要性。本文通过综合分析，建立了最佳走刀路线模型，运用模拟退火算法，较好地解决了这一问题［1］。

1 电路板走刀问题中的数学规则模型

电路板通常是由许多不同直径的孔，对某一确定的孔径构成的孔系来说，PCB问题可以描述为∶从换刀点出发既不重复又不遗漏地加工完所有的孔再回到换刀点。所谓最佳走刀问题，就是如何安排孔的加工顺序使空程移动距离最短。该问题很显然可以归结为著名的旅行商问题（TSP），其中钻头扮演了旅行商人的角色，而目标函数就是刀具行程最短的路线［2］。

对电路板问题，首先要建立一个数学规则模型∶设电路板钻孔的个数为n，dij是两个钻孔i和j之间的距离，xij=0或1（1表示两个钻孔连通，0表示没有连通）。则有目标函数min∑i≠jdijxij使得∶

这样就很好地用数学表达式描述了电路板走刀问题的约束条件和最终的目标函数，建立了电路板走刀问题的数学模型。

2 电路板走刀问题的求解方法

本文分别用哈密顿通路和模拟退火两种算法对印刷电路板的钻孔问题进行优化处理，钻孔在平面上的坐标位置见表1。

为了产生明显的对比，本文给出一个随机状态下的路径图，如图1所示［3］。显然这是一个十分混乱的路径，在实际生产中就会影响生产效率，对于大批量生产电路板的厂家来说，对成本的影响会相当显著，很有必要找个最优的走刀路径来解决这个问题。

2.1 哈密顿通路算法解决电路板走刀问题

哈密顿通路就是通过图的每个结点一次，且仅一次的通路，就是哈密顿通路。上述问题实际上就是在赋权的哈密顿图中找到一个最小权的哈密顿圈。对于上述问题的一个有效办法是先求一个哈密顿圈C，然后修改C以得到较小权的另一个哈密顿圈。这叫做改良圈算法［5］，其一般思路如下∶

设初始圈C=v1v2…vnv1。对于1≤i＜i+1＜j≤n，构造新的哈密顿圈Cij=v1v2…vivjvj-1…vi+1vj+1vj+2…vnv1，新构造的这个哈密顿圈是由初始圈C删去边vivi+1和vjvj+1、添加边vivj和vi+1vj+1得到，若d（vivj）+ d（vi+1vj+1）＜d（vivi+1）+d（vjvj+1），用Cij代替C，成为C圈的改良圈。重复这一操作直到无法改进。用matlab编程对上述描述进行实现，得到的最优路径为4.5443，编号排序∶1 3 30 2 4 5 18 19 29 27 28 26 24 25 23 21 22 20 16 17 15 6 11 9 13 14 12 10 8 7 1。由此可得到哈密顿最优路径图（图2）。

哈密顿图在最小路径中应用的时候，是利用局部最优，然后逐步到全局最优，对于比较大的数据量，很难求得全局最优解。选择不同的初始哈密顿圈，通过实验得到了不同的结果。把哈密顿算法的思路引入到模拟退火过程中，就可以得到模拟退火解决这个问题的方法。

2.2 模拟退火算法

模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法，编写程序相对简单。目前此法已开始用于解决非线性地球物理反问题等领域，并取得了较好的效果。

模拟退火原理∶模拟退火算法源于统计物理学，据统计热力学，物理中的每个分子的状态服从Gibbs分布，即∶

式中∶E（ri）为第i个分子的能量函数；ri为第i个分子所处的状态；k为玻尔兹曼常数，T表示温度；ρ（ri）为第i个分子的概率密度。为了计算方便，令k=1。理论上可证明，它是一个全局最优算法，并且以概率1接近最优值。

算法源于对实际固体退火过程的模拟，即先将固体加温至充分高，再逐渐冷却。加温时，固体内部粒子变为无序状态，内能增大；而逐渐降温时，粒子趋于有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。因此，算法实际上是将优化问题类比为退火过程中能量的最低状态，也就是温度达到最低点时，概率分布中具有最大概率的状态［6］。

2.2.1模拟退火步骤与实现

假设材料在状态i之下能量为E（i），那么材料在温度T时状态从i进入状态j遵循这样的规律∶

ΔE=E（j）-E（i）

模拟退火过程为∶

（1）如果▽E≤0，则新状态j被接受；

（4）重复步骤（1）～（3），直到满足条件为止［4］。

2.2.2模拟退火算法过程描述

（1）解空间S可表示为｛1，2，3…n，n+1｝的所有的固定起点和终点排列的集合，为了方面编程，把出发地定为编号1，最后回到出发地的编号定为n+1，即∶S=｛（v1，v2，v3…vn，vn+1）|v1，（v2，v3，…，vn）的循环排列，vn+1｝，其中vi=i。这样始发地和终点分别确定，中间地点的编号用蒙特卡洛方法获得。

（2）目标函数∶

（3）新解产生∶

由蒙特卡洛方法得到初始解，设为∶｛v1，…，vu-1，vu，vu+1，…，vw-1，vw，vw+1，…，vn+1｝任意选择序号u，w，交换顺序使之成为逆序∶｛v1，…，vu-1，vw，vw-1，…，vu+1，vu，vw+1，…，vn+1｝可以得到两个路径的距离差∶

Δf=（dvu-1vw

+dvuvw+1）-（dvu-1vu

+dvwvw+1）

但是，范文芳（2007）提出，语法隐喻的产生必然涉及与一致式不同的选择，但并非不同的选择就导致隐喻的产生。比如，[11a]是一致式，虽然[11b]和[11c]都选择了不同的过程，却只有[11c]是隐喻式。这也符合张德禄和赵静（2008）提出的形似性原则④。可见，在形式变体的问题上，我们对不同的体现形式要作进一步的区分，并且参考形似性原则来判定一致式和隐喻式。形似性原则能为范文芳（2017）的判断和类似问题提供直接、有效的依据。

（5）降温∶利用降温系数k进行降温，每次取T=kT作为新的温度，k＜1，这里k越接近1降温越缓慢，效果越好，但是耗时会较长。

（6）结束条件∶选定一个终止的温度e，这里e＞0，e越接近0所得的结果最优。T＜e时结束过程，输出此时的状态［5］。

对于电路板最佳走刀问题，解空间分别对应表1中的编号，通过两点间的距离公式求得两个孔之间的距离d，按照上述模拟退火过程通过matlab工具编程实现，得到最优路径长度为4.1151，编号排列为∶1 3 30 2 4 5 8 10 13 12 14 19 18 29 27 23 21 25 28 26 24 22 20 16 17 15 6 11 9 7 31。最优路径如图3所示。

因此，利用模拟退火算法求解电路板走刀问题是可行有效的［6］。

3 算法分析

一般情况下，模拟退火算法采取的是随机地选取坐标的方法，本文为了提高算法的执行效率，将原本随机选取初始值的方式改为尽可能找出一个有用的初始值。实际中，可以结合哈密顿图方法，先利用哈密顿图方法求得一个相对好的结果，以此作为模拟退火算法中的初始路径，这样，既能保证得到一个最优结果，在时间上，求解过程也可以更快完成［7］。

4 结束语

本文将PCB数控钻孔最佳走刀问题归结为TSP问题，引入模拟退火算法对其求解。与其它算法相比较，模拟退火算法是一种描述简单、使用灵活、较少受到初始条件约束的拟物型随机近似算法。通过模拟退火算法，有效地解决了电路板走刀加工中刀具路径冗长、空行程导致加工效率低的问题。在实际应用中，为了更好的应用模拟退火算法，可以预先搜寻最佳的冷却温度和升温达到的最高温度范围，从而在保证良好结果的基础上，获得更好的时间效益［8］。

［1］莫愿斌'陈德钊'胡上序.动态规划粒子群算法解PCB数控钻孔最佳走刀路线问题［J］.机床与液压' 2006(8）:18-21.

［2］王银年'葛洪伟.求解TSP问题的改进模拟退火遗传算法［J］.计算机工程与应用'2010'46(5）:44-47'85.

［3］苗连英'王萃琦.图论及其算法［M］.徐州:中国矿业大学出版社'2012.

［4］司守奎'孙玺菁.数学建模算法与应用［M］.北京:国防工业出版社'2011.

［5］朱颢东'钟勇.一种改进的模拟退火算法［J］.计算机技术与发展'2009'19(6）:32-35.

［6］张盛意'蔡之华'占志刚.基于改进模拟退火的遗传算法求解0-1背包问题［J］.微电子学与计算机' 2011'28(2）:61-64.

［7］蒋龙聪'刘江平.模拟退火算法及其改进［J］.工程地球物理学报'2007'4(2）:135-140.

［8］郎茂祥.装卸混合车辆路径问题的模拟退火算法研究［J］.系统工程学报'2005'20(5）:485-491.

Application of Simulated Annealing in the Best Feeding Problems of Printed Circuit Board

ZHANG Hongyu，YE Yan，YANG Xiaoyan
（College of Management Science，Chengdu University of Technology，Chengdu 610059，China）

The feeding line problem of printed circuitboard（PCB）can be regarded as a large-scale TSP problem.After the circuit board feeding route problem model is constructed，the weighted Hamiltonian graph method and the simulated annealing strategy are used to analyze and resolve the problem.The concrete algorithms and process of simulated annealing in solving the problem aremainly introduced.The simulation results show that the simulated annealing algorithm performs better in solving TSP problem，and it has bettermaneuverability compared with other algorithms.

Printed circuit board；Hamiltonian cycle；Monte Carlomethod；simulated annealing

TN41

A

1673-1549（2014）01-0045-04

10.11863/j.suse.2014.01.12

2013-09-25

张洪雨（1988-），男，河北沧州人，硕士生，主要从事数学地质方面的研究，（E-mail）zhanghongyu_198827@126.com