基于改进蚁群算法的PCB孔加工路径优化

王捷晨 路林吉

(上海交通大学电子信息与电气工程学院)

基于改进蚁群算法的PCB孔加工路径优化

王捷晨 路林吉

(上海交通大学电子信息与电气工程学院)

针对于印制电路板(PCB)孔加工过程中刀具的路径规划问题，提出了一种改进的蚁群算法，使信息素浓度可以更好地反映路径信息，解决了经典蚁群算法易收敛到局部最优解的问题。仿真实验结果表明：改进算法不仅增强了对于解空间的搜索能力，而且提高了搜索到全局最优解的概率。

蚁群算法 孔加工 路径优化 信息素

近几年随着越来越多的手持电子设备和工业自动化的蓬勃发展,印制电路板(PCB)得到了广泛的应用。而PCB的加工过程中必然少不了钻孔加工环节。钻孔加工一般是用不同尺寸的刀具对PCB打孔。Merchant的调查显示，刀具和工件的运动在加工过程中占用总加工时间的70%[1]。因此，对刀具的打孔路径进行有效规划，就能提高打孔效率，进而提高生成效率。

长期以来人们一直在研究路径规划问题的解决方法。大部分传统算法都存在算法复杂度太高的问题，当孔个数较多时，问题就得不到良好的解决，这使得传统算法难以应用在实际生产过程当中。而最近出现的一些人工智能算法，给路径规划问题的求解带来了新的希望。蚁群算法作为一种独特的模拟自然界中蚂蚁集群智能的仿生算法，与传统优化方法相比具有鲁棒性强、分布性广、无须依赖具体问题及算法时间复杂度较低等优点，使蚁群算法拥有了广阔的应用领域。笔者在传统的经典蚁群算法的基础上提出了一些改进意见，以便于更好地解决PCB打孔路径规划问题。

1 问题描述与蚁群算法的原理

1.1 问题描述

在对PCB进行打孔加工时，加工过程可描述为：对某一类给定尺寸的孔径，数控钻铣床换上对应尺寸的刀具后，从第1个孔开始加工，沿着程序给定的路径对剩下的孔依次进行加工，直到PCB上所有该尺寸的孔都被加工完毕，如此循环,直到所有孔径的过孔都被加工完毕[2]。通过上述对问题的阐述，笔者把PCB孔加工问题总结为如下数学模型：

a. 变量说明。设有n个孔的集合V={v1,v2, …,vn}，dij表示任意两个待钻孔vi、vj之间的直线距离。

b. 约束条件。刀具遍历所有该尺寸孔对象，并且每个孔对象只被遍历一次，加工完所有孔之后再回到起点换刀具继续加工。

1.2 蚁群算法的原理

蚁群算法是意大利学者Colorni A 等于1991年提出的一种智能搜索优化算法[3]，该算法的提出主要是受到了自然界中蚂蚁觅食行为的启发。

蚁群算法基本模型的变量可以表述如下：给定N节点有向图，m只蚂蚁，用变量dij(i、j=1,2, …，N)表示节点i和节点j之间的距离，τij(t)表示第t次迭代边(i,j)上的信息素浓度。

经典蚁群算法的主要实现步骤如下[4]：

a. 信息素初始化。将m只蚂蚁随机分配在节点当中并且初始化信息素浓度。在初始化信息素浓度时，各边上的信息素浓度相同，即τij(0)=c(c为常数)。

2 改进蚁群算法

经过1.2节对经典蚁群算法原理的描述可发现，蚁群算法具有良好的鲁棒性，但是也存在搜索易出现停滞的问题，算法收敛于次优解，即使增加最大迭代次数也不能搜索到最优解。这个问题的产生主要是由算法对信息素浓度的更新不能准确反映路径信息引起的[5]，如果信息素浓度能够完全反映出路径信息，最终算法将收敛到全局最优解。所以问题的核心就是信息素浓度的设置和更新。笔者针对此问题进行了优化，使信息素浓度能更为客观地反映出路径信息。

2.1 信息素初始化改进

在经典蚁群算法中，初始化信息素浓度时，各个边上的信息素浓度相等，为定值。这样设置会导致算法积累启发因子影响相同，蚁群算法在开始搜索路径时没有目的性，产生大量的无关路径，导致算法开始时信息素浓度更新混乱。而这些混乱的信息素浓度最终会影响以后迭代的搜索，且容易使算法陷入局部最优解[6]。为了解决这个问题，笔者提出的改进蚁群算法在初始化信息素浓度时利用路径信息，加入方向引导，使蚁群算法刚开始进行搜索时就能够找到比较好的路径，路径初始化信息素浓度公式修改为：

τij(0)=Q/(dSj+djE)

(1)

其中dSj和djE分别为节点j到起点S与终点E的直线距离(终点E设置为距离起点S最近的节点)；Q为给定参数，是每只蚂蚁每次遍历时的总信息素浓度。由式(1)可知，当节点j越趋向于连线SE时，τij(0)越大，蚂蚁就倾向于选择该点作为自己的目的节点。这样就抑制了对无关路径的搜索，避免了信息素初始化时的无目的性。

2.2 信息素局部更新规则的改进

信息素局部更新指的是对完成遍历全部节点的蚂蚁经过路径上进行信息素浓度的增强。然而单只蚂蚁的遍历很容易出现偏差，这使得偏差路径上的信息素浓度增强，使得路径上信息素浓度混乱。针对于上述问题，笔者提出一种局部信息素浓度更新方法。对于第(k+1)只蚂蚁局部信息素浓度的更新，不仅仅考虑第(k+1)只蚂蚁的路径，也把前k只蚂蚁的路径考虑进来，更新规则为：

(2)

从式(2)中可以看出，笔者将前k只蚂蚁的信息素浓度进行了挥发，并与第(k+1)只蚂蚁的信息素浓度进行了加权求平均，重新分配，减弱了单只蚂蚁的无关路径对搜索全局最优路径的影响。

2.3 信息素全局更新规则的改进

经典蚁群算法全局更新规则对单次迭代中最短路径上的信息素浓度进行增强。然而，单次迭代得到的路径有好有差，对于较差路径上信息素浓度的增强容易让算法收敛于次优解。另一方面，单次迭代最优解路径往往与全局最优路径有较大的关系，应该充分利用单次迭代的路径信息[7]。

笔者在全局信息素更新规则中引入自适应动态因子σ(σ∈(0，1))，以自适应地调整较好解和较差解对信息素浓度更新的影响，更新规则为：

τij(t+1)=τij(t)+μσΔτij

(3)

由sigmoid函数式可知，当前迭代搜索到的最优路径越长，动态因子σ就越接近于0，减小了较差路径对于信息素浓度的影响；而当前迭代搜索到的路径越短，动态因子σ就越接近于1，增强了较好路径对于信息素浓度的影响。所以当采用sigmoid函数对单次迭代的最优路径进行信息素浓度自适应更新后，算法不会很快收敛于局部最优解，保留了解空间的多样性。

3 算法仿真与分析

针对笔者提出的改进蚁群算法(I-ACS)、经典蚁群算法(ACS)、最大最小蚁群算法(MMAS)和文献[8]提出的蚁群算法，笔者先仿真一块PCB采用不同蚁群算法进行路径优化，再对打孔数不同的PCB板采用不同算法进行路径优化，来对比不同蚁群算法的计算结果和性能。图1所示为一块待打孔的PCB，图1a中空心圆标记的是需要用加工的过孔，总共有51个。图1b为已证明的最短路径，且最短路径长度Lbest=423.9005。

a. PCB待加工过孔

b. PCB过孔加工最优路径

笔者把各个蚁群算法的迭代次数都设置为100次，对算法的结果和性能进行对比。笔者提出的改进蚁群算法(I-ACS)的实验参数见表1。

表1 改进蚁群算法(I-ACS)的实验参数

在重复实验30次的情况下，实验仿真了各个蚁群算法，根据30次实验最优路径的分布绘制出了图2。由图2可知，经典蚁群算法和最大最小蚁群算法搜索到的路径长度主要集中在较差路径(440～470)之间，文献[8]中提到的改进蚁群算法得到的最优路径结果有所提高，但仍然集中在次优路径，而笔者提出的I-ACS算法搜索到的路径结果则主要集中在最优路径附近。

图2 各算法30次实验结果分布

其次对各个算法的收敛性进行仿真分析。在30次重复实验当中，选择了搜索到最优路径的那次实验进行了收敛性分析。各个蚁群算法均迭代了100次，笔者根据各个蚁群算法100次迭代的收敛结果，绘制了图3。从图3中可以看出，各个算法在到达最大迭代次数之前都收敛了，由于笔者提出的算法会利用路径信息初始化信息素浓度，所以一开始就能找到较短的路径，而且笔者提出的I-ACS算法在局部和全局信息素浓度更新时进行了改进，能持续搜索解空间，在迭代次数较高时才收敛，增加了找到最优解的概率。

图3 各算法收敛性对比

最后，针对不同个数的节点对各个算法进行了重复30次的仿真实验。在仿真实验中，分别仿真了30、50、70、90个节点的PCB来进行各个蚁群算法的性能对比，对比结果见表2、3。

表2 最优占比统计结果 %

表3 平均迭代次数统计结果

表2中的最优占比，指的是在30次重复实验中，各个算法的结果当中与最优结果距离不超过10的实验次数所占的百分比，占比越高，说明算法的结果越好，越容易找到最优解。

表3中的平均迭代次数指的是平均经过多少次的迭代后算法收敛于局部最优解，反映的是算法对解空间的搜索能力，平均迭代次数越大，说明算法越不容易收敛于局部最优解，对解空间的搜索能力越强，有更大概率搜索到全局最优解。

从表2、3中可以看出，笔者提出的改进蚁群算法对解空间的搜索能力较强，而且也有较大概率搜索到最优解，相对于其他算法具有一定的优势。

4 结束语

主要解决了PCB打孔加工过程中刀具走刀的路径规划问题。首先对走刀的路径规划问题进行了数学描述，接着对经典蚁群算法提出了一些改进意见，来避免经典蚁群算法过早收敛于局部最优解。改进的核心是使信息素浓度尽可能客观地反映出路径信息。基于这一原则，笔者提出了3个方面的改进，一是在初始化信息素浓度时引入方向信息，减少了无关路径对搜索最优路径的影响；二是在信息素浓度局部更新的过程中利用先前蚂蚁的信息素浓度进行加权平均，使算法不因为个别蚂蚁的偏差路径误入歧途；三是在信息素浓度全局更新过程中，利用sigmoid函数自适应地调整每次迭代路径上的信息素浓度更新，增强较短路径影响力，抑制较差路径影响力。最后的算法仿真结果表明笔者提出的改进蚁群算法对解空间的搜索能力更强大，有更大的概率找到最优解。

[1] 周琨,邵华.基于Hopfield算法的孔群加工路径规划[J].模具技术,2003, 21(1): 48～50．

[2] 邢启明.基于最短路径算法的PCB板插接优化[J].江苏科技信息,2014，(16):31～34.

[3] Colorni A, Dorigo M, Maniezzo V. Distributed Optimization by Ant Colonies[C]. Proceedings of the First European Conference on Artificial Life. Paris: Elsevier Publishing,1991:134～142.

[4] Gambardella L M, Dorigo M. Solving Symmetric and Asymmetric TSPs by Colonies[C]. Proceedings of the IEEE Conference on Evolutionary Computation. Piscataway,NJ:IEEE，1996: 622～627.

[5] 袁亚博,刘羿,吴斌.改进蚁群算法求解最短路径问题[J].计算机应用与工程,2016，52(6):8～12.

[6] 郑卫国,田其冲,张磊.基于信息素强度的改进蚁群算法[J].计算机仿真,2010，27(7):191～193.

[7] 张学敏,张航.基于改进蚁群算法的最短路径问题研究[J].自动化技术与应用,2009，28(6):4～7.

[8] 何小虎.基于改进蚁群算法在粮食物流配送路径优化的应用研究[J].电子设计工程, 2016，24(9):39～41.

PCBDrillingPathOptimizationBasedonImprovedAntColonyAlgorithm

WANG Jie-chen, LU Lin-ji

(School of Electronic Information and Electrical Engineering, Shanghai Jiaotong University)

As for the tool’s path planning in the PCB drilling process, an improved ant colony algorithm was proposed to make pheromone concentration reflect the path information better and to solve the problem that the classic ant colony algorithm is easy to fall into local optimal solution. The simulation results show that the improved algorithm not only strengthens the ability to search solution space, but also increases the probability of finding the global optimal solution.

ant colony algorithm, drilling manufacturing, path optimization, pheromone

TP14

A

1000-3932(2017)05-0434-05

王捷晨(1991-)，硕士研究生，从事数字图像处理、PCB自动布线、PCB打孔机路径规划的研究。

联系人路林吉(1965-)，副教授，从事工业自动化软硬件设计、数字图像处理、机器人技术及应用的研究，lulinji2002@163.com。

2016-11-21，

2017-03-15)