Research On One-Dimensional Cutting-stock And Two-Dimensional Data Sets Matching Optimization

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.