基于GA的矩阵式TSP算法及在飞针测试机上的应用研究
|
摘要
飞针测试机是一个在制造环境测试PCB(印刷电路板)的系统。它用探针代替车床，在X-Y机构上装有4-8个由电机驱动的可分别快速移动的探针，利用探针在Z方向的移动同PCB的焊点进行接触并进行电气测量。测试人员把设计工程师的CAD数据转换成可使用的文件，这些文件包含了需要测试的焊点的坐标(X，Y)及焊点在PCB中的网络值，由此决定驱动各个探针的X、Y、Z电机的移动．通常，一块PCB上可能有上千个焊点，如果探针不按一种最优或较优的路径移动进行测试，可能会耗费数倍的测试时间，延误生产。把旅行商问题(Traveling Salesman Problem，简记为TSP)应用到该系统上，很好的解决了探针移动轨迹优化的问题。
TSP属于组合数学中一个古老而又困难的问题。有效的解决它，在可计算理论上具有重要的理论意义，同时也具有重要的实际应用价值。
首先，基于本文的研究背景，引出了TSP在飞针测试机上应用的意义和价值。随后叙述了TSP的一般提法，描述了其数学模型，综合介绍了关于解决TSP的相关算法，并做了性能比较。
其次，把不完全算法中的遗传算法应用到TSP中。对其中关键的交叉算子介绍了一种针对TSP的改进措施。此外，基于局部寻优的思想，介绍了一种特殊的矩阵式TSP的解决方法。
最后，介绍了飞针测试机控制系统的开发过程，包括硬件系统和软件设计两个部分。此外，把遗传寻优和矩阵式TSP综合应用于探针路径优化问题上。把需要测试的焊点看作是各个城市，探针看作旅行商，而“旅行的费用”就是探针遍历所有焊点所行走的距离，实际运行结果表明，飞针测试机控制系统达到了测试功能，且路径优化算法能够找到最优解或次最优解。
Flying probe tester is a system to finish testing Printed Circuit Board in manufacturing environment. It is an improvement based on traditional machine tool. It makes use of probe to replace the machine tool and sets up 4-8 quick step-motor-driven probes in X-Y framework. It finishes test by making contact between probe and PCB. The probe is driven to move in Z direction. The testers convey the CAD files into useful files for testing. These files include the coordinate and value in network of the solder-points, which decide the movement of the probes. Generally, there are thousands of solder-point in a PCB. If the probes don't move in an optimum track or inferior optimum track, it will waste lots of time. To solve this problem, TSP is used in this system.
Traveling Salesman Problem (TSP) is considered as an old and difficult problem in combinatorics. To solve it effectively has not only great theoretical function, but also very important pragmatic value in the filed of calculable theory.
Firstly, the actual using value of TSP in flying probe tester is introduced based on the using background. Then Traveling Salesman Problem is described and its mathematics model is provided. Some correlative algorithms are introduced and their capability of solving TSP is compared.
Secondly, Genetic Algorithms is used in TSP. A method for the improvement on crossover operator aiming at TSP is introduced. Furthermore, a method to solve a special type of TSP - the Matrix Type of TSP is introduced based on the thought of local optimizing.
Finally, the exploitation process of the controlling system for flying probe tester, including hardware and software, is introduced. The solder-points is considered as cities in TSP, as well as, probe as salesman, the total length among all solder-points as the cost of travel. The TSP is used to optimize this cost. As is shown, the software for flying probe tester has the right testing function and the TSP has been rightly used in the path optimizing for the probe.
TSP属于组合数学中一个古老而又困难的问题。有效的解决它，在可计算理论上具有重要的理论意义，同时也具有重要的实际应用价值。
首先，基于本文的研究背景，引出了TSP在飞针测试机上应用的意义和价值。随后叙述了TSP的一般提法，描述了其数学模型，综合介绍了关于解决TSP的相关算法，并做了性能比较。
其次，把不完全算法中的遗传算法应用到TSP中。对其中关键的交叉算子介绍了一种针对TSP的改进措施。此外，基于局部寻优的思想，介绍了一种特殊的矩阵式TSP的解决方法。
最后，介绍了飞针测试机控制系统的开发过程，包括硬件系统和软件设计两个部分。此外，把遗传寻优和矩阵式TSP综合应用于探针路径优化问题上。把需要测试的焊点看作是各个城市，探针看作旅行商，而“旅行的费用”就是探针遍历所有焊点所行走的距离，实际运行结果表明，飞针测试机控制系统达到了测试功能，且路径优化算法能够找到最优解或次最优解。
Flying probe tester is a system to finish testing Printed Circuit Board in manufacturing environment. It is an improvement based on traditional machine tool. It makes use of probe to replace the machine tool and sets up 4-8 quick step-motor-driven probes in X-Y framework. It finishes test by making contact between probe and PCB. The probe is driven to move in Z direction. The testers convey the CAD files into useful files for testing. These files include the coordinate and value in network of the solder-points, which decide the movement of the probes. Generally, there are thousands of solder-point in a PCB. If the probes don't move in an optimum track or inferior optimum track, it will waste lots of time. To solve this problem, TSP is used in this system.
Traveling Salesman Problem (TSP) is considered as an old and difficult problem in combinatorics. To solve it effectively has not only great theoretical function, but also very important pragmatic value in the filed of calculable theory.
Firstly, the actual using value of TSP in flying probe tester is introduced based on the using background. Then Traveling Salesman Problem is described and its mathematics model is provided. Some correlative algorithms are introduced and their capability of solving TSP is compared.
Secondly, Genetic Algorithms is used in TSP. A method for the improvement on crossover operator aiming at TSP is introduced. Furthermore, a method to solve a special type of TSP - the Matrix Type of TSP is introduced based on the thought of local optimizing.
Finally, the exploitation process of the controlling system for flying probe tester, including hardware and software, is introduced. The solder-points is considered as cities in TSP, as well as, probe as salesman, the total length among all solder-points as the cost of travel. The TSP is used to optimize this cost. As is shown, the software for flying probe tester has the right testing function and the TSP has been rightly used in the path optimizing for the probe.
引文
1．刑文训，谢金星，现代优化计算方法，清华大学出版社，1999
2．徐光辉，运筹学基础手册。科学出版社，1999
3．马良，旅行推销员问题的算法综述，数学的实践与认识，2000．4
4．周培德，寻求中国货担郎问题最短回路的多项式时间算法，北京理工大学学报，VOL．20，NO．2
5. Dan Gusfield etc. Graph traversals, genes and matroids: an efficient case of the traveling salesman problem. Discrete Applies mathematics,88(1998), 167-180
6．张文修，梁怡，遗传算法的数学基础，西安交通大学出版社，2000
7．云庆夏，进化算法，冶金工业出版社，2000
8．齐欢，数学模型方法，华中理工大学出版社，1997
9．Dorit S.Hochbaum,Approximation Algorithms for NP-Hard Problems NP难题问题的近似算法，世界图书出版公司，1998
10．蒋长浩，图论与网络流，中国林业出版社，2001
11．陈江华，林爱文，杨明，龚健，遗传算法求解TSP问题的研究进展，昆明理工大学学报200(理工版)，2003．8
12．郝志峰，刘海，林智勇，矩阵式旅行商问题的最优解，计算机应用研究，2003．4
13．刘海，郝志峰，林智勇，改进遗传交叉算子求解TSP问题，华南理工大学学报(自然科学版)，2002．12
14．段禅伦，斯勤夫，关于旅行推销员问题的一个算法，内蒙古大学学报(自然科学版)，2001．11
15. Held M, Karp R M, Thetraveling-salesmanproblemandminimumspanningtrees 1971
16．戴一奇，胡冠章，陈卫，图与代数结构，清华大学出版社出版，1995
17．卢开澄，组合数学．算法与分析，清华大学出版社出版，1983
18. Dantzig G B, Solution for a Large Scale Traveling Salesman Problem, Operations Research, 1954
19. Miller C E, Integer Programming Formulation and Traveling Salesman Problem, J.ACM, 1960
20．焦李成，神经网络计算，西安电子科技大学出版社，1995
21．刘勇，非数值并行算法——遗传算法，科学出版社，1995
22．马良，多准则货郎问题及其算法，运筹学的理论与应用，西安电子科技大学出版社，1996
23．刘军，三维限制TSP的退火模拟算法，电子科技大学学报，1992
24．王东生，改进TSP神经网络的收敛性，计算机学报，1992
25．尚奕，唐志敏，一种用于求解TSP问题的遗传交换操作，计算机研究与发展，1992
26．杨国兴，一种特殊类型的多出发点多旅行商问题的研究，运筹与决策(第一卷)，成都科技大学出版社，1992
27. 马良，王龙德，TSP Model and Algorithm in Aids-to-Navigation nspection, Proc.of the 5th Sino-Japanese Int. Conf. on Computer Applications, 1992
28．网络和图的最优化算法，中国铁道出版社，1992
29．孙焕纯，王跃方，货担郎问题的人工智能—人机交换解法，系统工程理论与实践，2000．5
30．卢朝阳，吴可柯，陆心如，优化TSP算法的完善及推广，电子学报，1994．1
31．汪林林，张林，对“货担郎问题”的深入解析，计算机科学，2002．1
32．陈沐天，蔡和熙，货担郎问题的几何分块算法及China TSP问题的最终解决，计算机工程与科学，1998．1
33．鲜飞，飞针测试的特点及应用，世界电子元气件，2002．6
34．李兵、隋连升、蒋庄德，基于误差补偿的虚拟网格二维影射标定法，西安交通大学学报，2003．3
35．李献勇，Visual C++串口通信技术与工程实践，人民邮电出版社，2002
36. Tung C T. A Multi-criteria Pareto-Optimal Algorithm for the Traveling Salesman Problem, Asia-Pacific Journal of Operational Research, 11,1994
37．朱洪，算法设计和分析，上海科学技术文献出版社，1989
38．马良，最小Hamilton路问题的算法，计算机工程与应用，1992．1
39．唐策善，梁维发，并行图论算法，中国科学技术大学出版社，1991
40. Nurmi K. Traveling Salesman Problem Tools for Microcomputers, Computers and Operations Research, 1991
41．陈国良，神经网络用于求解组合优化问题，中国神经网络首届学术大会论文集，北京，1990，122～129
42．徐心和，旅行商问题的一种新解法，东北工学院学报，1990．1
43．余道衡，关于用人工神经网络解货郎问题(TSP)的探讨，中国神经网络首届学术大会论文集，北京，1990．116～121
44．刘昆焱，余道衡，微机上200城市TSP人工神经网络解的实现，中国神经网络首届学术大会论文集，北京，1990，887～890
45．Burkard R E，旅行商问题的一些特殊情况和启发式算法，运筹学杂志，1989．2，1～13
46．Microsoft，Visual C++技术内幕6.0，北京希望电子出版社
2．徐光辉，运筹学基础手册。科学出版社，1999
3．马良，旅行推销员问题的算法综述，数学的实践与认识，2000．4
4．周培德，寻求中国货担郎问题最短回路的多项式时间算法，北京理工大学学报，VOL．20，NO．2
5. Dan Gusfield etc. Graph traversals, genes and matroids: an efficient case of the traveling salesman problem. Discrete Applies mathematics,88(1998), 167-180
6．张文修，梁怡，遗传算法的数学基础，西安交通大学出版社，2000
7．云庆夏，进化算法，冶金工业出版社，2000
8．齐欢，数学模型方法，华中理工大学出版社，1997
9．Dorit S.Hochbaum,Approximation Algorithms for NP-Hard Problems NP难题问题的近似算法，世界图书出版公司，1998
10．蒋长浩，图论与网络流，中国林业出版社，2001
11．陈江华，林爱文，杨明，龚健，遗传算法求解TSP问题的研究进展，昆明理工大学学报200(理工版)，2003．8
12．郝志峰，刘海，林智勇，矩阵式旅行商问题的最优解，计算机应用研究，2003．4
13．刘海，郝志峰，林智勇，改进遗传交叉算子求解TSP问题，华南理工大学学报(自然科学版)，2002．12
14．段禅伦，斯勤夫，关于旅行推销员问题的一个算法，内蒙古大学学报(自然科学版)，2001．11
15. Held M, Karp R M, Thetraveling-salesmanproblemandminimumspanningtrees 1971
16．戴一奇，胡冠章，陈卫，图与代数结构，清华大学出版社出版，1995
17．卢开澄，组合数学．算法与分析，清华大学出版社出版，1983
18. Dantzig G B, Solution for a Large Scale Traveling Salesman Problem, Operations Research, 1954
19. Miller C E, Integer Programming Formulation and Traveling Salesman Problem, J.ACM, 1960
20．焦李成，神经网络计算，西安电子科技大学出版社，1995
21．刘勇，非数值并行算法——遗传算法，科学出版社，1995
22．马良，多准则货郎问题及其算法，运筹学的理论与应用，西安电子科技大学出版社，1996
23．刘军，三维限制TSP的退火模拟算法，电子科技大学学报，1992
24．王东生，改进TSP神经网络的收敛性，计算机学报，1992
25．尚奕，唐志敏，一种用于求解TSP问题的遗传交换操作，计算机研究与发展，1992
26．杨国兴，一种特殊类型的多出发点多旅行商问题的研究，运筹与决策(第一卷)，成都科技大学出版社，1992
27. 马良，王龙德，TSP Model and Algorithm in Aids-to-Navigation nspection, Proc.of the 5th Sino-Japanese Int. Conf. on Computer Applications, 1992
28．网络和图的最优化算法，中国铁道出版社，1992
29．孙焕纯，王跃方，货担郎问题的人工智能—人机交换解法，系统工程理论与实践，2000．5
30．卢朝阳，吴可柯，陆心如，优化TSP算法的完善及推广，电子学报，1994．1
31．汪林林，张林，对“货担郎问题”的深入解析，计算机科学，2002．1
32．陈沐天，蔡和熙，货担郎问题的几何分块算法及China TSP问题的最终解决，计算机工程与科学，1998．1
33．鲜飞，飞针测试的特点及应用，世界电子元气件，2002．6
34．李兵、隋连升、蒋庄德，基于误差补偿的虚拟网格二维影射标定法，西安交通大学学报，2003．3
35．李献勇，Visual C++串口通信技术与工程实践，人民邮电出版社，2002
36. Tung C T. A Multi-criteria Pareto-Optimal Algorithm for the Traveling Salesman Problem, Asia-Pacific Journal of Operational Research, 11,1994
37．朱洪，算法设计和分析，上海科学技术文献出版社，1989
38．马良，最小Hamilton路问题的算法，计算机工程与应用，1992．1
39．唐策善，梁维发，并行图论算法，中国科学技术大学出版社，1991
40. Nurmi K. Traveling Salesman Problem Tools for Microcomputers, Computers and Operations Research, 1991
41．陈国良，神经网络用于求解组合优化问题，中国神经网络首届学术大会论文集，北京，1990，122～129
42．徐心和，旅行商问题的一种新解法，东北工学院学报，1990．1
43．余道衡，关于用人工神经网络解货郎问题(TSP)的探讨，中国神经网络首届学术大会论文集，北京，1990．116～121
44．刘昆焱，余道衡，微机上200城市TSP人工神经网络解的实现，中国神经网络首届学术大会论文集，北京，1990，887～890
45．Burkard R E，旅行商问题的一些特殊情况和启发式算法，运筹学杂志，1989．2，1～13
46．Microsoft，Visual C++技术内幕6.0，北京希望电子出版社