【作者】 王小东；

【导师】 欧宗瑛；

【作者基本信息】 大连理工大学 ， 机械设计及理论， 2004， 硕士

【摘要】 最优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术，作为一个重要的科学分支一直受到人们的重视，并广泛应用于诸多工程领域，如系统控制、人工智能、模式识别、VLSI技术、计算机工程等等。优化理论和算法的研究是一项既有重要理论意义又有实际应用价值的重要课题。 本文主要研究了一维下料优化及二维数据集最佳匹配两大问题。 最大限度的节约材料，提高材料的利用率，是实际生产中的一个指导原则。一维下料优化是讨论从一种规格的材料中，分切出各种不同长度尺寸的坯料，以使材料的利用率最高。虽然，这是一个老课题，研究者已提出过各种算法，但是，效果还不十分满意。针对这类问题的特点，本文提出一种基于启发式多级序列线性优化思想的新算法。计算实践表明，此算法与目前常用的线性整数规划或遗传算法相比较，有算法简明，计算速度快，节材效果好的优点。 全文介绍了作者承担开发的网格钢窗CAD系统的设计，将整个系统分为人机界面、几何计算、结构设计、下料优化和打印输出等五个模块。其中的关键技术是棒材的下料优化，将基于启发式多级序列线性优化思想的新算法应用到下料优化模块中。实践表明，该算法大大简化了求解一维下料优化问题的规模和复杂度，优化效果明显。 近来，二维数据集的最佳匹配也受到普遍关注，并且在如图形相似性的判断和匹配检索中得到广泛的应用。传统的模板匹配是基于相关准则的，当两个形状具有平移、旋转、尺度变化时，需要极长的计算时间，使得该方法难以得到实际使用。本文提出将修正Hausdorff距离作为形状轮廓相似性的测度，避免了噪声的影响；并用遗传算法进行最佳形状匹配的快速搜索；根据遗传搜索的结果再进行一次线性搜索，从而提高解的精度。对于形心距较远的物体和模板，先进行一次预处理。实验表明，本文提出的方法搜索速度和精度都有了很大的提高，是一种有效的形状匹配算法。更多还原

【Abstract】 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 finitesearch 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.更多还原