一维下料及二维数据集匹配优化的研究
|
摘要
最优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术，作为一个重要的科学分支一直受到人们的重视，并广泛应用于诸多工程领域，如系统控制、人工智能、模式识别、VLSI技术、计算机工程等等。优化理论和算法的研究是一项既有重要理论意义又有实际应用价值的重要课题。
本文主要研究了一维下料优化及二维数据集最佳匹配两大问题。
最大限度的节约材料，提高材料的利用率，是实际生产中的一个指导原则。一维下料优化是讨论从一种规格的材料中，分切出各种不同长度尺寸的坯料，以使材料的利用率最高。虽然，这是一个老课题，研究者已提出过各种算法，但是，效果还不十分满意。针对这类问题的特点，本文提出一种基于启发式多级序列线性优化思想的新算法。计算实践表明，此算法与目前常用的线性整数规划或遗传算法相比较，有算法简明，计算速度快，节材效果好的优点。
全文介绍了作者承担开发的网格钢窗CAD系统的设计，将整个系统分为人机界面、几何计算、结构设计、下料优化和打印输出等五个模块。其中的关键技术是棒材的下料优化，将基于启发式多级序列线性优化思想的新算法应用到下料优化模块中。实践表明，该算法大大简化了求解一维下料优化问题的规模和复杂度，优化效果明显。
近来，二维数据集的最佳匹配也受到普遍关注，并且在如图形相似性的判断和匹配检索中得到广泛的应用。传统的模板匹配是基于相关准则的，当两个形状具有平移、旋转、尺度变化时，需要极长的计算时间，使得该方法难以得到实际使用。本文提出将修正Hausdorff距离作为形状轮廓相似性的测度，避免了噪声的影响；并用遗传算法进行最佳形状匹配的快速搜索；根据遗传搜索的结果再进行一次线性搜索，从而提高解的精度。对于形心距较远的物体和模板，先进行一次预处理。实验表明，本文提出的方法搜索速度和精度都有了很大的提高，是一种有效的形状匹配算法。
Based on mathematics optimization technology deals with the solving approach for various engineering problems. As an important scientific branch, it has been paid much attention and has been generally applied in many engineering fields, such as system control, artificial intelligence, pattern recognition, VLSI technology, computer engineering, etc. Therefore, the research of optimization techniques possesses important significancy both in theories and practical applications.
One-dimensional cutting stock optimization and two-dimensional data sets optimal matching problem are mainly researched in this thesis.
It' s a principle in practice to make full use of materials. One-dimensional cutting stock optimization is such a problem that discusses cutting sticks in different lengths from one kind of stock and maximizing the material using ratio. This is a long-standing problem, with a substantial body of papers published. Yet, most of the algorithms currently in use are not effective enough. Based on the best-first strategy, a heuristic algorithm with multi-sequential linear programming is proposed. Numerical examples demonstrate that it is advantageous in simplifying the program and elevating computation speed significantly, compared with the conventional methods of linear integer programming or Genetic Algorithm.
Design of steel window grid CAD system is introduced in this thesis. The whole system is composed of five functional modules such as human-machine interface, geometric computation, structure design, cutting stock optimization and printout. The key point of the system is cutting stock optimization module in which the new heuristic algorithm is used. The application indicates that this new algorithm can effectively decrease the scale of original problem and the computation complexity, and ensure the quality of solution.
Matching between two data sets is often needed especially in estimating and searching of similar shapes. Template matching, which is the most principle approach for shape matching, is time consuming in case of variation in position, rotation and scale. In this thesis, an improved algorithm for 2D shape matching based on Modified Hausdorff Distance is proposed. Hausdorff Distance is used to measure the degree of similarity between two objects to make matching more effectively. A high dimensional, non-differentiable and multi-modal objective function can be derived based on Hausdorff Distance. Although Genetic Algorithm is a powerful and attractive procedure for function optimization, the solution generated by the procedure does not guarantee to be the global optimal. A follow-up optimization scheme such as the linear search method is applied, which is capable of finding the minimum value of a uni-modal function over a finite
search interval. Initially the non-differentiable function is solved using multi-point stochastic search, and the solution is further improved by executing a sequence of successive linear searches that approach the optimal to a pre-determined precision. A pretreatment step is used if the center distance of two objects is very large. The experimental results show that the proposed method is capable of matching 2D shapes with higher speed and precision.
本文主要研究了一维下料优化及二维数据集最佳匹配两大问题。
最大限度的节约材料，提高材料的利用率，是实际生产中的一个指导原则。一维下料优化是讨论从一种规格的材料中，分切出各种不同长度尺寸的坯料，以使材料的利用率最高。虽然，这是一个老课题，研究者已提出过各种算法，但是，效果还不十分满意。针对这类问题的特点，本文提出一种基于启发式多级序列线性优化思想的新算法。计算实践表明，此算法与目前常用的线性整数规划或遗传算法相比较，有算法简明，计算速度快，节材效果好的优点。
全文介绍了作者承担开发的网格钢窗CAD系统的设计，将整个系统分为人机界面、几何计算、结构设计、下料优化和打印输出等五个模块。其中的关键技术是棒材的下料优化，将基于启发式多级序列线性优化思想的新算法应用到下料优化模块中。实践表明，该算法大大简化了求解一维下料优化问题的规模和复杂度，优化效果明显。
近来，二维数据集的最佳匹配也受到普遍关注，并且在如图形相似性的判断和匹配检索中得到广泛的应用。传统的模板匹配是基于相关准则的，当两个形状具有平移、旋转、尺度变化时，需要极长的计算时间，使得该方法难以得到实际使用。本文提出将修正Hausdorff距离作为形状轮廓相似性的测度，避免了噪声的影响；并用遗传算法进行最佳形状匹配的快速搜索；根据遗传搜索的结果再进行一次线性搜索，从而提高解的精度。对于形心距较远的物体和模板，先进行一次预处理。实验表明，本文提出的方法搜索速度和精度都有了很大的提高，是一种有效的形状匹配算法。
Based on mathematics optimization technology deals with the solving approach for various engineering problems. As an important scientific branch, it has been paid much attention and has been generally applied in many engineering fields, such as system control, artificial intelligence, pattern recognition, VLSI technology, computer engineering, etc. Therefore, the research of optimization techniques possesses important significancy both in theories and practical applications.
One-dimensional cutting stock optimization and two-dimensional data sets optimal matching problem are mainly researched in this thesis.
It' s a principle in practice to make full use of materials. One-dimensional cutting stock optimization is such a problem that discusses cutting sticks in different lengths from one kind of stock and maximizing the material using ratio. This is a long-standing problem, with a substantial body of papers published. Yet, most of the algorithms currently in use are not effective enough. Based on the best-first strategy, a heuristic algorithm with multi-sequential linear programming is proposed. Numerical examples demonstrate that it is advantageous in simplifying the program and elevating computation speed significantly, compared with the conventional methods of linear integer programming or Genetic Algorithm.
Design of steel window grid CAD system is introduced in this thesis. The whole system is composed of five functional modules such as human-machine interface, geometric computation, structure design, cutting stock optimization and printout. The key point of the system is cutting stock optimization module in which the new heuristic algorithm is used. The application indicates that this new algorithm can effectively decrease the scale of original problem and the computation complexity, and ensure the quality of solution.
Matching between two data sets is often needed especially in estimating and searching of similar shapes. Template matching, which is the most principle approach for shape matching, is time consuming in case of variation in position, rotation and scale. In this thesis, an improved algorithm for 2D shape matching based on Modified Hausdorff Distance is proposed. Hausdorff Distance is used to measure the degree of similarity between two objects to make matching more effectively. A high dimensional, non-differentiable and multi-modal objective function can be derived based on Hausdorff Distance. Although Genetic Algorithm is a powerful and attractive procedure for function optimization, the solution generated by the procedure does not guarantee to be the global optimal. A follow-up optimization scheme such as the linear search method is applied, which is capable of finding the minimum value of a uni-modal function over a finite
search interval. Initially the non-differentiable function is solved using multi-point stochastic search, and the solution is further improved by executing a sequence of successive linear searches that approach the optimal to a pre-determined precision. A pretreatment step is used if the center distance of two objects is very large. The experimental results show that the proposed method is capable of matching 2D shapes with higher speed and precision.
引文
[1] 臧勇．现代机械设计方法．北京：冶金工业出版社，1998
[2] 王凌．智能优化算法及其应用．北京：清华大学出版社，2001
[3] 张勇传，瞿继恂．组合最优化-计算机算法和复杂性．武汉：华中理工大学出版社，1994．6
[4] 钱志勤．人机交互的演化设计方法及其在航天器舱布局方案设计中的应用[博士论文]．大连：大连理工大学，2001
[5] Gilmore P. C, Gomory R. E. A linear programming approach to the cutting stock problem (Part Ⅰ) [J]. Operations Research, 1961, 9: 849～859
[6] Gilmore P. C, Gomory R. E. A linear programming approach to the cutting stock problem (Part Ⅱ) [J]. Operations Research, 1963, 11 : 863～887
[7] Dyckhoff H. A New Linear Programming Approach to the Cutting Stock Problem [J]. Operations Research, 1981, 29(6): 1094～1104
[8] Dyckhoff H. A typology of cutting and packing problems [J]. European Journal of Operational Research, 1990, (44): 145～159
[9] Valerio de Carvalho JM, etal. ALP-based approach to a two-stage cutting stock problem [J]. European Journal of Operational Research, 1995, 84:580～589
[10] Beasley JE. An exact two-dimensional non-guillotine cutting tree search procedure [J]. Operations Research, 1985, 33 (1) : 49～64
[11] 聂义勇，申志勇，王宏，文成秀，张福顺．考虑库存余材利用的杆材下料方案[J]．小型微型计算机系统，2001，22(7)，830～832
[12] 贾志新，殷国富，胡晓兵，舒斌．一维下料方案的遗传算法优化．西安交通大学学报，2002．9
[13] Mitchell W J, Steadman JP, Liggett R S. Synthesis and optimization of small rectangular floor plans [J]. Environment and Planning B, 1976, 3:37～70
[14] Roth J, Hashimshony R, Wachman A. Turning a graph into a rectangular floor plan [J]. Building and Environment, 1982, 17:163～173
[15] Dowsland K A. An exact algorithm for the pallet-loading problem [J]. European Journal of Operational Research, 1987, 31 : 78～84
[16] 吴慧中，王英林．一种立体空间布局模型及其布局算法[J]．计算机学报，1994，17(11)：835～841
[17] 查建中．智能工程[M]．北京：机械工业出版社，1992
[18] Albano A. A method to improve two-dimensional layout [J]. Computer-Aided Design, 1977, 9(1): 48～52
[19] 孙守迁，唐明，潘云鹤．面向人机工程的布局设计方法的研究[J]．计算机辅助设计与图形学学报，2000，12(11)：870～872
[20] 曾芬芳．虚拟现实技术[M]．上海交通大学出版社，1997
[21] Sarker B R. An optimum solution for one dimensional slitting problems: A Dynamic Programming Approach [J]. Jopl Res Soc, 1988, 39(8): 749～755
[22] 袁忠良．最优化下料方法与程序[M]．天津大学出版社，1989
[23] Julien Antonio, Fabrice Chauvet, Chengbin Chu, etal. The cutting stock problem with mixed objectives: Two heuristics based on dynamic programming [J]. European Journal of Operational Research, 1999, 114:395～402
[24] Paolo Toth. Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems [J]. European Journal of Operational Research,
2000, 125:222～238
[25] Hopfield JJ. Neurous with graded response have collective computational properties like those of two-state neurous [J]. Proc Natl Acad Sci USA, 1984, 81: 3088～3092
[26] 曹月东．二维布局优化神经计算方法研究[D]．北京：北方交通大学，1999
[27] Garey M R, Johnson D S. Computer and Intractability: A Guide to the Theory of NP-Completeness [M]. New York:. Freeman, 1979
[28] Andr'as P'eter, Andr'as Andr'as, and Szab'o Zsuzsa. A genetic solution for the cutting stock problem [J]. Soft Computing, 1996, 87～92
[29] 于洋，查建中，唐晓君．基于学习的遗传算法及其在布局中的应用[J]．计算机学报，2001，24(12)：1242～1249
[30] 金升平，陈定方，张翔，戴诗亮．一维优化下料问题的基因遗传算法[J]．武汉交通科技大学学报，1997，21(2)：168～172
[31] 徐德兴．利用仿真退火算法求解不规则对象排列及切割问题[D]．大叶大学工业工程研究所硕士论文，2000
[32] 张泽增．NPC理论导引．贵阳：贵州人民出版社，1989
[33] Rosenfeld A. Axial representations of shape. CVGIP, 1986, 2(33): 156～173
[34] Ogniewicz R L, Kubler O. Hierarchic voronoiskeletons. Pattern Recognition, 1995, 28(3): 343～359
[35] TariZ S G, Shah J, Pien H. Extraction of shape skeletons from grayscale images. CVIU, 1997, 66(2): 133～146
[36] Mumford David. Mathematic theories of shape: Do they model perception? In: Proc. Geometric Methods in Computer Vision, SPIE, 1991, 1570:2～10
[37] Ballard D H. Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognition, 1981, 13(2): 111～112
[38] Ansafi N, Delp E J. On the distribution of a deforming triangle. Pattern Recognition, 1990, 23(12): 1333～1341
[39] 黎倩，陈迪，吴健康．神经网络图像匹配．模式识别于人工智能，1992，5(3)：221～228
[40] Young Susan S, Scott Peter D, NasrabadiNasserM. Object recognition using multiplayer Hopfield neural network. IEEE Trans. Image Processing, 1997, 6 (3) : 357～372
[41] He Yang, Kundu Amlan. 2-D shape classification using hidden Markov model. IEEE Trans. PAMI, 1991, 13(11): 1172～1184
[42] Kasyap R L, Chellappa R. Stochastic models for closed boundary analysis: Representation and reconstruction. IEEE Trans. Inform. Theory, 1981, 27(5): 627～637
[43] 刘勇，康立山等．非数值并行算法——遗传算法．北京：科学出版社，1995．1
[44] 周明，孙树栋．遗传算法原理与应用．北京：国防工业出版社，1996
[45] Cartwright H M and Mott G F. Looking Around: using Clues from the Data Space to Guide Genetic Algorithm Searches. Proc of ICGA, 1991, 108～114
[46] Saad M.A. Suliman. Pattern generating procedure for the cutting stock problem. Production Economics, 2001
[47] 刘勇彪．等界面长条类材料下料方案的最优化设计．机械设计与制造，1994
[48] 唐焕文，秦学志．最优化方法．大连理工大学出版社，1994
[49] 陈国良遗传算法及其应用[M]．北京：人民邮电出版社，1996
[50] Rosenfeld A, Kak A C. Digital picture processing, second edition. New York: Academic Press, 1982
[51] Csaszar A. General Topology. Bristol: Adam Hilger, 1978
[52] 张文景，许晓鸣，苏键锋．基于Hausdorff距离的2D形状匹配改进算法．中国图像图形学报，2000．2
[53] Huttenlocher D P, Klanderman. G A, Rucklidge W J. Comparing images using the Hausdorff distance [J]. IEEE Transactions on PAMI, 1993, 15(9): 850～863
[54] Donald Hearn, M. Pauline Baker著，蔡士杰等译．计算机图形学．北京：电子工业出版社，1998
[55] Goldberg D E. Genetic Algorithms in Search, Optimization & Machining. Addison-Wesley Publishing, 1989
[56] 毕红军，裘正定，杜锡钰．等汉明距离编码的研究．北方交通大学学报，1997．10
[57] 李敏强，寇纪淞，林丹，李书全．遗传算法的基本理论与应用．科学出版社，2002
[58] 韦春荣，张孝飞，陈洪波，王强．基于轮廓提取的医学图像配准方法．广西师范大学学报，2003．6
[2] 王凌．智能优化算法及其应用．北京：清华大学出版社，2001
[3] 张勇传，瞿继恂．组合最优化-计算机算法和复杂性．武汉：华中理工大学出版社，1994．6
[4] 钱志勤．人机交互的演化设计方法及其在航天器舱布局方案设计中的应用[博士论文]．大连：大连理工大学，2001
[5] Gilmore P. C, Gomory R. E. A linear programming approach to the cutting stock problem (Part Ⅰ) [J]. Operations Research, 1961, 9: 849～859
[6] Gilmore P. C, Gomory R. E. A linear programming approach to the cutting stock problem (Part Ⅱ) [J]. Operations Research, 1963, 11 : 863～887
[7] Dyckhoff H. A New Linear Programming Approach to the Cutting Stock Problem [J]. Operations Research, 1981, 29(6): 1094～1104
[8] Dyckhoff H. A typology of cutting and packing problems [J]. European Journal of Operational Research, 1990, (44): 145～159
[9] Valerio de Carvalho JM, etal. ALP-based approach to a two-stage cutting stock problem [J]. European Journal of Operational Research, 1995, 84:580～589
[10] Beasley JE. An exact two-dimensional non-guillotine cutting tree search procedure [J]. Operations Research, 1985, 33 (1) : 49～64
[11] 聂义勇，申志勇，王宏，文成秀，张福顺．考虑库存余材利用的杆材下料方案[J]．小型微型计算机系统，2001，22(7)，830～832
[12] 贾志新，殷国富，胡晓兵，舒斌．一维下料方案的遗传算法优化．西安交通大学学报，2002．9
[13] Mitchell W J, Steadman JP, Liggett R S. Synthesis and optimization of small rectangular floor plans [J]. Environment and Planning B, 1976, 3:37～70
[14] Roth J, Hashimshony R, Wachman A. Turning a graph into a rectangular floor plan [J]. Building and Environment, 1982, 17:163～173
[15] Dowsland K A. An exact algorithm for the pallet-loading problem [J]. European Journal of Operational Research, 1987, 31 : 78～84
[16] 吴慧中，王英林．一种立体空间布局模型及其布局算法[J]．计算机学报，1994，17(11)：835～841
[17] 查建中．智能工程[M]．北京：机械工业出版社，1992
[18] Albano A. A method to improve two-dimensional layout [J]. Computer-Aided Design, 1977, 9(1): 48～52
[19] 孙守迁，唐明，潘云鹤．面向人机工程的布局设计方法的研究[J]．计算机辅助设计与图形学学报，2000，12(11)：870～872
[20] 曾芬芳．虚拟现实技术[M]．上海交通大学出版社，1997
[21] Sarker B R. An optimum solution for one dimensional slitting problems: A Dynamic Programming Approach [J]. Jopl Res Soc, 1988, 39(8): 749～755
[22] 袁忠良．最优化下料方法与程序[M]．天津大学出版社，1989
[23] Julien Antonio, Fabrice Chauvet, Chengbin Chu, etal. The cutting stock problem with mixed objectives: Two heuristics based on dynamic programming [J]. European Journal of Operational Research, 1999, 114:395～402
[24] Paolo Toth. Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems [J]. European Journal of Operational Research,
2000, 125:222～238
[25] Hopfield JJ. Neurous with graded response have collective computational properties like those of two-state neurous [J]. Proc Natl Acad Sci USA, 1984, 81: 3088～3092
[26] 曹月东．二维布局优化神经计算方法研究[D]．北京：北方交通大学，1999
[27] Garey M R, Johnson D S. Computer and Intractability: A Guide to the Theory of NP-Completeness [M]. New York:. Freeman, 1979
[28] Andr'as P'eter, Andr'as Andr'as, and Szab'o Zsuzsa. A genetic solution for the cutting stock problem [J]. Soft Computing, 1996, 87～92
[29] 于洋，查建中，唐晓君．基于学习的遗传算法及其在布局中的应用[J]．计算机学报，2001，24(12)：1242～1249
[30] 金升平，陈定方，张翔，戴诗亮．一维优化下料问题的基因遗传算法[J]．武汉交通科技大学学报，1997，21(2)：168～172
[31] 徐德兴．利用仿真退火算法求解不规则对象排列及切割问题[D]．大叶大学工业工程研究所硕士论文，2000
[32] 张泽增．NPC理论导引．贵阳：贵州人民出版社，1989
[33] Rosenfeld A. Axial representations of shape. CVGIP, 1986, 2(33): 156～173
[34] Ogniewicz R L, Kubler O. Hierarchic voronoiskeletons. Pattern Recognition, 1995, 28(3): 343～359
[35] TariZ S G, Shah J, Pien H. Extraction of shape skeletons from grayscale images. CVIU, 1997, 66(2): 133～146
[36] Mumford David. Mathematic theories of shape: Do they model perception? In: Proc. Geometric Methods in Computer Vision, SPIE, 1991, 1570:2～10
[37] Ballard D H. Generalizing the Hough transform to detect arbitrary shapes. Pattern Recognition, 1981, 13(2): 111～112
[38] Ansafi N, Delp E J. On the distribution of a deforming triangle. Pattern Recognition, 1990, 23(12): 1333～1341
[39] 黎倩，陈迪，吴健康．神经网络图像匹配．模式识别于人工智能，1992，5(3)：221～228
[40] Young Susan S, Scott Peter D, NasrabadiNasserM. Object recognition using multiplayer Hopfield neural network. IEEE Trans. Image Processing, 1997, 6 (3) : 357～372
[41] He Yang, Kundu Amlan. 2-D shape classification using hidden Markov model. IEEE Trans. PAMI, 1991, 13(11): 1172～1184
[42] Kasyap R L, Chellappa R. Stochastic models for closed boundary analysis: Representation and reconstruction. IEEE Trans. Inform. Theory, 1981, 27(5): 627～637
[43] 刘勇，康立山等．非数值并行算法——遗传算法．北京：科学出版社，1995．1
[44] 周明，孙树栋．遗传算法原理与应用．北京：国防工业出版社，1996
[45] Cartwright H M and Mott G F. Looking Around: using Clues from the Data Space to Guide Genetic Algorithm Searches. Proc of ICGA, 1991, 108～114
[46] Saad M.A. Suliman. Pattern generating procedure for the cutting stock problem. Production Economics, 2001
[47] 刘勇彪．等界面长条类材料下料方案的最优化设计．机械设计与制造，1994
[48] 唐焕文，秦学志．最优化方法．大连理工大学出版社，1994
[49] 陈国良遗传算法及其应用[M]．北京：人民邮电出版社，1996
[50] Rosenfeld A, Kak A C. Digital picture processing, second edition. New York: Academic Press, 1982
[51] Csaszar A. General Topology. Bristol: Adam Hilger, 1978
[52] 张文景，许晓鸣，苏键锋．基于Hausdorff距离的2D形状匹配改进算法．中国图像图形学报，2000．2
[53] Huttenlocher D P, Klanderman. G A, Rucklidge W J. Comparing images using the Hausdorff distance [J]. IEEE Transactions on PAMI, 1993, 15(9): 850～863
[54] Donald Hearn, M. Pauline Baker著，蔡士杰等译．计算机图形学．北京：电子工业出版社，1998
[55] Goldberg D E. Genetic Algorithms in Search, Optimization & Machining. Addison-Wesley Publishing, 1989
[56] 毕红军，裘正定，杜锡钰．等汉明距离编码的研究．北方交通大学学报，1997．10
[57] 李敏强，寇纪淞，林丹，李书全．遗传算法的基本理论与应用．科学出版社，2002
[58] 韦春荣，张孝飞，陈洪波，王强．基于轮廓提取的医学图像配准方法．广西师范大学学报，2003．6