Research on Optimization Algorithm of Sheet Cutting Path板件切割路线优化算法的研究.doc

广西工学院 毕业设计（论文）说明书 课题名称 板件切割路线优化算法的研究 Research on Optimization Algorithm of Sheet Cutting Path 系 别 电子信息与控制工程 专 业 自动化 班 级 043 学 号 2004031141 姓 名 魏玉峰 指导教师 胡 波 2008年 05月 30日 摘 要 在工厂车间作业中，板件加工极为常见，加工中的切割路径不同将导致生产效率有所差异，从而切割路径的优化便直接影响到工厂效益。 针对此类路径优化问题，新近的寻优解法常用模拟生物进化优化的算法。首先，本论文先给出了相应的数学模型，利用改进的最近邻算法选定各个零件的切割起始点，把切割路径优化问题转换成基于各切割起始点的TSP问题。然后，再利用遗传算法求解此TSP问题而得出最优切割路径。从给出的运行实例可以发现，此种切割路径优化方法切实有效、可行，而提高了板件加工的效率。最后，又初步探讨了基于改进的遗传算法进行切割路径优化的方法。 关键词： 板件加工；路径优化；最近邻算法；切割起始点；遗传算法 Abstract Sheet processing is very common in workshop operation of a factory, the change of cutting path in the processing would affect the manufacturing efficiency, therefore, the optimization of cutting path directly impact on profitability of the factory. Aimed at the this kind of cutting-path optimization problem, the optimization algorithm by simulated evolution is frequently utilized as an up-to-date method of optimization. First, the corresponding mathametics model is offered. An improved nearest neighbor algorithm is established to decide cutting start points for each part, by doing so, cutting path optimization could be converted into the TSP based on each cutting start point. Then genetic algorithm is utilized to solve the TSP problem to obtain the opitmal cutting path. This method of cutting-path optimization is very effective and feasible by improving the efficiency of sheet processing according to the examples revealed in this paper. In the end, this paper probes into the method of cutting-path optimization based on improved genetic algorithm. Key words: sheet processing; path optimization; nearest neighbor algorithm; cutting start point; genetic algorithm. 目 录 1 绪论 1 1.1 切割路径优化的目的和意义 1 1.2 板件切割路径优化问题的研究现状 1 1.3 本论文的主要内容 2 2 切割路径问题的定义 3 2.1 零件的几何表达及定义 3 2.2 路径问题数学模