Please use this identifier to cite or link to this item:
標題: 遺傳演算法於多探頭三次元量床路徑規劃
The Path Planning for multi-probe Coordinate Measuring Machine on the Genetic Algorithm
作者: 張凱勝
Chang, Kai-Sheng
關鍵字: Coordinate Measuring Machines;三次元量床;Path Planning;Traveling Salesman Problem;Genetic Algorithm;路徑規劃;旅行者問題;遺傳演算法
出版社: 機械工程學系所
引用: 1.Hassan, J. H., Med1, A. J., Mullineux, G. and Sittas, E., “An Intelligent link between CAD and Automatic Inspection”, Annals of CIRP, pp.335-341,1993 2.Lee, S. S. G. and khoo, L. P., “An Approach to Feature-based Inspection Planning”, Annals of CIRP, pp.329-333, 1993 3.Chen, F.L., Shiau, C.W. and Chiang, Y.M., “CMM Inspection Planning from CAD Model”,Journal of Chinese Institute of Industrial Engineers, Vol.15, No.5, pp.439-447,1998 4.Hsu, G. J., Juster, N. P. and Pennington, A. D., “The Selection of Surfaces in Inspection Planning for Coordinate Measuring Machines”, Annals of CIRP, pp.321-328,1993 5.Moroni, G. and Polini, W., “Knowledge based method for touch probe configuration in an automated inspection system”, Journal of Materials Processing Technology, Vol.76, Issue.1-3, pp.153-160, 1998 6.Yau, Hong-Tzong and Menq, CHia Hsiang, “Path Planning for Automated Dimensional Inspection Using Coordinate Measuring Machines”, Proceedings of the IEEE International Conference on Robotics and Automation, pp.1934-1939, April 7-12, 1991 7.Fan, Kuang-Chao and Leu, Ming C., “Intelligent planning of CAD-directed inspection for Coordinate Measuring Machines”, Computer Integrated Manufacturing System, Vol.11, Issue:1-2, pp.43-51,1998 8.林宏達、許裕隆;“應用反應曲面技術於三次元座標量測儀量測點數與量測點位置分佈之規劃”,朝陽學報第七期,pp.207-229,2002 9.林宏達、許裕隆;“基因演算法應用於三次元座標量測儀之量測路徑選擇規劃”,朝陽科技大學學報,第八期,pp.111-140,2003/09. 10.Goldberg, D. E. (1989), Genetic algorithms in search, optimization and machine learning, Reading, MA: Addison Wesley. 11.Thierens, D. and Goldberg, D. (1994), Convergence models of genetic algorithm selection schemes, Parallel Problem Solving from Nature: PPSN III, Springer-Verlag, Berlin, pp.119-129. 12.Bach, F.Q., and Perov, V.L., "New Evolutionary Genetic Algorithms for NP-complete Combinatorial Optimization Problems", Biology Cybernet, Vol.69, 1993, pp.229-234. 13.Escudero, L.F., Guignard, M., and Malik, K., "A Lagrangean Relax -and-cut Approach for The Sequential Ordering Problem with Precedence Constraints", Annals of Operations Research, Vol.50, pp.219-237 ,1994. 14.Mingozzi, A., Bianco, L., and Ricciardelli, S., "Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints ",Operations Research, Vol.45, No.3, pp.45-53, 1997. 15.Gambardella, L., and Dorigo, M., "Hybrid Ant System for the Sequential Ordering Problem", Technical Report IDSIA, pp.11-97, 1997. 16.Oumlzel. Tugrul, “Precision tracking control of a horizontal arm coordinate measuring machine in the presence of dynamic flexibilities,” International Journal of Advanced Manufacturing Technology. Vol. 27, Issue 9/10, pp. 960-968 ,2006. 17.Adam and Dobosz. Marek, “ Influence of measured objects parameters on CMM touch trigger probe accuracy of probing,” Precision Engineering. Vol. 29, Issue 3, pp. 290-297 ,2005. 18.Adam and Dobosz. Marek, “Factors Influencing Probing Accuracy of a Coordinate Measuring Machine,” IEEE Transactions on Instrumentation & Measurement. Vol. 54, Issue 6, pp. 2540-2548 ,2005. 19.G. Dantzig, R. Fulkerson, and S. Johnson “ SOLUTION OF A LARGE-SCALE TRAVELING-SALESMAN PROBLEM” 20.Held, Michal & Richard M. Karp, "A Dynamic Programming Approach to Sequencing Problems", Journal of the Society for Industrial and Applied Mathematics 10 (1): pp.196-210,1962. 21.Bodin, L., B.L. Golden, A. Assad & M. Ball, “Routing and Scheduling of Vehicle and Crew: The State of Art,” Special Issue of Computers and Operations Research, Vol.10, No.2, pp.63-211,1983. 22.T. Yoichi and F. Nobuo,“An Improved Genetic Algorithm Using the Convex Hull for Traveling Salesman problem”,Transactions on Systems,Man,and Cybernetics,(3),pp.2279-2284, 1998. 23.Ravindra K. Ahuja, James B. Orlin, and Ashish Tiwari(1997),“A Greedy Genetic Algorithm for the Quadratic Assignment Problem”. 24.Merz and B. Freisleben(1997),“Genetic Local Search for the TSP: New Results”,Proceedings of the 1997 IEEE International Conference on Evolutionary Computation,IEEE Press,pp.159-164. 25.Hsiao-Lan Fang(1994),“Genetic Algorithms in Timetabling and Scheduling”,Ph.D. Thesis,Department of Artificial Intelligence,University of Edinburgh,Scotland. 26.Gen, M. and Cheng R. (1997), Genetic Algorithms & Engineering Design, New York: John Wiley & Sons, Inc. 27.Riccardo Poli and W. B. Langdon. Genetic programming with one-point crossover. In P. K. Chawdhry, R. Roy, and R. K. Pant, editors, Second On-line World Conference on Soft Computing in Engineering Design and Manufacturing. Springer-Verlag London, 23-27 June 1997. 28.Rawlins, G. J. E.: Foundations of Genetic Algorithms, San Mateo, California, USA: Morgan Kaufmann Publishers, 1991. 29.Schaffer, J. D.: Proceedings of the Third International Conference on Genetic Algorithms, San Mateo, California, USA: Morgan Kaufmann Publishers, 1989. 30.Syswerda, G. (1989), Uniform crossover in genetic algorithms, Proceedings of the third international conference on genetic algorithms and their applications, San Mateo, CA: Morgan Kaufmann, pp.2-9.
隨著科技工業的發展,東西越來越細緻與精小,當我們要針對加工元件進行量測時,工業界上普遍使用三次元量床(coordinate measuring machines,CMM)來進行量測。本研究針對三次元量床進行量測路徑的規劃,接觸式量床量測精度高,也方便撰寫量測程式,更可以修改量測路徑做彈性的應用。我們利用遺傳演算法求解旅行者問題最短拜訪路徑的概念,撰寫一個遺傳演算法的程式,藉由輸入距離矩陣的設計,我們可以將原本的單純量測點群排序問題擴張為考慮多種探頭的情況下,進行的最短路徑規畫。

This research focuses on CMM with planning of route, the CMM with contact-type probe have high precision, and it is convenient for person to write procedure. It also revise examine route that make elastic application even usefully. We solve the Traveling Salesman Problem with a general idea of Genetic Algorithm, and perform of Genetic algorithm. We can extend examine original simple distance matrix for considering multi-probe with the design of new matrix, and show the rule of shorting path.
With the development of scientific and technological industry, the parts are more careful and attentive. We usually use coordinate measuring machines to examine to the process parts on industry. This research is divided into two parts, one part is write a form to solve Traveling Salesman Problem by Genetic algorithm, and we use the idea of greedy algorithm to modify the crossover operator. We check the result of algorithm by the case of TSPLIB.
The Second part, we plan the measure points with the rule of geometry, and we count the distance between measure points. Then we put the result into the algorithm to find the best route of measuring and path value. Finally we analysis the result and discuss.
其他識別: U0005-2608200916355600
Appears in Collections:機械工程學系所

Show full item record

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.