多级规约算法在PCB钻孔路径优化中的应用  

Application of multilevel reduction algorithm to PCB path optimization

作　　者：程森林[1] 曾伟[1] 

机构地区：[1]重庆大学自动化学院,重庆400044

出　　处：《计算机工程与应用》2012年第16期212-215,共4页Computer Engineering and Applications

摘　　要：以求解PCB(PrintedCircuitBoard)钻孔路径优化这一大规模复杂的TSP(TravelingSalesmanProblem)问题为背景,研究了一种改进的多级规约算法(EMR)。该算法依据工程应用中实用性、通用性的特点重新设计了多级规约算法(MR)的规约和细化算子并增加了控制参数以提高算法的灵活性;针对算法中会产生大量部分解集且难以储存这一问题,设计了一种类似人类族谱的数据结构。实验结果以及与循环LK算法和蚁群算法的对比分析表明,EMR算法兼顾了实用性和通用性,且有较高的优化质量和优化效率。The PCB（Printed Circuit Board）path optimization is a large-scale TSP（Traveling Salesman Problem）problem.An Enhanced Multilevel Reduction algorithm（EMR）is proposed to solve this problem.The proposed algorithm redesigns the reduction operator and brings a control parameter to improve its flexibility.Meanwhile,in view of the difficulties of saving the results produced by reduction operator,a new data structure like human family tree is presented.Experimental results,compared with the other method,demonstrate that EMR outperforms in practicability and generality with higher quality and efficiency of optimization.

关 键 词：旅行商问题TSP 印制线路板PCB 多级归约算法 路径优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]