摘要
以求解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.
出处
《计算机工程与应用》
CSCD
2012年第16期212-215,共4页
Computer Engineering and Applications
关键词
旅行商问题TSP
印制线路板PCB
多级归约算法
路径优化
Traveling Salesman Problem（TSP）
Printed Circuit Board（PCB）
multilevel reduction algorithm
path optimization
