标题 | 基于模拟退火算法的PCB孔群加工路径优化 |
范文 | 苟辉 周玉婷 汪忠林 摘要:为改善印制电路板孔群的加工质量与效率,该文采用模拟退火算法对孔群的加工路径进行了优化。文中通过PCB孔群实例详细描述了模拟退火算法的实现过程,结果表明,利用模拟退火算法可有效提升PCB孔群加工效率以及质量,降低孔群加工中的空行程比例。 关键词:模拟退火算法;路径优化;PCB孔群 中图分类号:TP32 文献标识码:A 文章编号:1009-3044(2018)27-0247-02 Optimization of PCB Path Processing Based on Simulated Annealing Algorithm GOU Hui, ZHOU Yu-ting, WANG Zhong-lin (Computing Technique Research Institute, Aviation Industry Corporation of China, Xi'an 710068, China) Abstract: In order to improve the processing quality and efficiency of the hole group of the printed circuit board, the simulated annealing algorithm was used to optimize the processing path of the hole group. In this paper, the implementation of simulated annealing algorithm is described in detail through examples, and the results show that the use of simulated annealing algorithm can effectively improve the processing efficiency and quality of PCB clusters, and reduce the empty stroke ratio in cluster machining. Key words: simulated annealing algorithm; path Optimization; PCB cluster 21世紀伊始,伴随着电子电路技术的飞速发展、提升电子类仪器集成度以及印制电路板(PCB)制作效率的要求,对印制电路板的制作工艺提出了新的挑战[1-2]。在改善印制电路板生产效率中,孔群的加工尤为重要,它所需要的加工时间主要包含孔的加工时间和刀具换位、更换刀具等辅助时间。其中,刀具换位的运动时间占孔群加工的70%[3]。因此,为减少PCB孔群加工过程中刀具换位时间与提升PCB制作效率,本文将展开基于模拟退火算法的孔群加工路径优化方案设计。 1 模拟退火算法 模拟退火算法是一种十分常用的优化算法,它的设计思想主要是参考固体物质的退火过程。假如固体的温度过高,将会因其内能较大而使物质内部粒子处于快速无序运动状态;随着温度降低,内能将不断减小,继而使粒子运动逐渐趋于有序状态。然后,当物质处于常温时,内能最小,粒子的运动状态也最为稳定。模拟退火算法的设计流程如图1所示。 Metropolis算法又名Metropolis抽样,它是构成模拟退火算法的基础。使用模拟退火算法时,必须确定初始温度,Metropolis的链长S,降温速率v和结束温度Tend。假设初始解是X,扰动系统,产生新的解X`;相应的,解的函数由f(X)变为f(X`)。如果f(X`)小于等于f(X),则系统接受新解;否则以概率[exp-f(X`)-f(X)T]接受新解,直至完成迭代。然后检测是否满足终止条件,若不满足则降低温度重新进行求解,直至满足结束条件,终止算法。 2 路径优化算法设计 结合上文中有关模拟退火算法的设计流程可将PCB孔群加工路径优化步骤分为以下几个部分: (1) 编号:首先,采用自然数序列对印制电路板需待加工孔的坐标位置进行编号,假设有8个小孔,因此它们的编号为{1,2,3,4,5,6,7,8 }。 (2) 设置算法控制参数:影响模拟退火算法实现过程的主要参数有:降温速率v、初始温度 Tstart、结束温度 Tend 以及 Metropolis 链长S。 (3) 初始解:本文通过产生随机序列的方式产生模拟退火算法需要的初始解X1,假若是对包含8个孔的印制电路板进行加工路径优化,所产生的初始解就是对这些孔的排序,每个数字就是对应孔的编号,即2|4|1|5|8|3|6|7就是一个合法解。 (4) 扰动生成新解:本文利用三变换法对初始解X1进行扰动产生新的路径排序,即是新的可行解X2。三变换法:任选序号u,v和ω(u≤vω),将u和v之间的路径插到ω之后访问,若交换前的解为[Xi=(a1,a2,...,au,...,av,...,aω,...,an)],因此交换后的新路径为:[Xi`=(a1,...,au-1,...,av+1,...,aω,au,...,av,aω+1,...,an)]。例如, PCB 板上有8个孔。产生三个[1,8] 区间内的随机整数r1、r2和r3,确定三个位置,如 r1 = 2,r2 = 5,r3=7,则根据三变换法序列6 |3| 7 1 |4| 8 |2| 5变换后,得到的新解为6 8 |2| |3| 7 1 |4| 5。 (5) Metropolis准则:如果加工路径总长度的函数为f(X),则当前解的路径长度为f(X),新解的路径长度为 f(X`),路径长度差为[Δ]f(X`)-f(X) ,则 Metropolis 准则为: [P=1, Δf<0exp-ΔfT, Δf0] 如果[Δf]< 0,则以概率1接受新的路径解;否则以概率 exp( -[Δf/T]) 接受新的路径解。 (6) 降温:利用降温速率v进行降温,即T`= vT,若T` (7) 加工路径优化:把钻孔机钻头初始化位置当作原点位置,确定孔群位置信息时始终将原点位置的序号定为1。如果通过模拟退火算法优化出来的路径编号序列为: 8 5 7 2 4 8 3 6 1 8,则需要将其转换为从编号 1 开始的路径为: 1 8 5 7 2 4 8 3 6 1。 3 基于matlab的仿真实验 实验平台为64位Win8操作系统,matlab r2014a版本和绘制电路原理图软件Altium Designer13。本次实验通过利用模拟退火算法对一个实例进行路径优化设计以验证算法的有效性与可行性。利用AD设计一块49.28mm*49.40mm大小的印制電路板,如图2所示。以左下角作为坐标原点,测量各小孔相对于原点的位置信息,并将其作为孔的坐标。然后将坐标输入至模拟退火算法中对孔群的加工路径进行优化。 结合模拟退火算法的设计思想以及文献资料,本文设计的基于模拟退火算法的matlab程序中各参数如下:加工孔群数目为38再加上坐标原点,因此退火算法中的城市数目为39;初始温度Tstart为97℃,降温速率为0.99℃/代,结束温度Tend为3℃,链长S为10000mm。 将孔群中小孔的坐标矩阵代入模拟退火算法进行优化,可得优化前的一个随机加工路径如图3所示,该加工路径长度为965.2156mm。 4 结论 通过本次仿真实验结果可以得出:模拟退火算法可有效对PCB孔群的加工路径进行优化,总距离由优化前的965.2156mm变为235.8965mm,缩短为原来的24.40%。并且通过多次实验发现退火算法参数对优化过程有较大的影响,接下来将着重研究具体参数对优化结果的影响,以获得最佳参数的范围。根据实验结果可以看出,模拟退火算法能够有效优化加工路径,为提升PCB孔群加工效率提供了可行的设计方案。 参考文献: [1] 颜国霖.基于TSP的孔群加工路径优化算法[J].延边大学学报:自然科学版,2014,40(4):370-374. [2] 肖人彬,陶振武.孔群加工路径规划问题的进化求解[J].计算机集成制造系统,2005(5):725-732. [3] 杨婷,贾朝川.基于模拟退火算法的PCB钻孔机空行路径优化[J].蚌埠学院学报,2016,5(5):6-9. [通联编辑:代影] |
随便看 |
|
科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。