文档介绍：上海交通大学硕士学位论文数控等离子切割机的路径优化姓名:何汉武申请学位级别:硕士专业:控制工程指导教师:陈卫东;俞力生 20081130 上海交通大学工程硕士学位论文摘要第 I 页数控等离子切割机的路径优化 摘要 当今中国的船舶工业高速发展,各种先进的自动化设备广泛应用于生产以提高生产效率。钢材切割是船舶制造的第一道工序,先进的数控等离子切割机的使用不断增多。数控等离子切割机所使用程序的切割路径规划的好坏直接影响了切割的效率。本文对切割路径规划的优化进行研究,并提出两种不同的优化算法来优化切割路径,以减少切割空行长度,增加切割有效工作时间,从而提高切割效率。 在数学上切割路径优化问题可以转化为TSP问题。 TSP问题应用广泛, 是最经典的NP-hard 组合优化问题之一。由于其计算的复杂性较高,长期以来,研究者一直在寻求快速、高效的近似算法,以便在合理的时间内解决问题。 目前解决 TSP 问题一般采用传统启发式算法和现代启发式算法。都是依据经验或法则来搜索合理的解。在传统算法中本文提出贪婪算法来研究解决该问题。贪婪算法是一步算法,主要受贪婪法则的控制。它的实现过程相较简单,计算时间较短, 而且优化结果较好。为解决贪婪算法的解不与其它可行解比较的问题, 本文首次提出了在局部点内进行局部可行解之间比较求优的办法来求得更好的解。经过实验证明贪婪算法生成的切割路径相较于TRIBON 程序生成的路径的优化效果也比较明显。 遗传算法(GA)是借鉴生物选择和进化机制发展起来的一种高度并行、随机和自适应搜索的现代启发式算法。它特别适合于处理传统搜索算法上海交通大学工程硕士学位论文摘要第 II 页解决不好的复杂和非线性问题。遗传算法计算结果的好坏主要受到各遗传算法参数的影响,而计算复杂度主要受群体规模、遗传代数等参数控制。遗传算法在参数的选择上仍缺乏有力的理论证明,所以需要大量的试验来验证参数的合理性。本文在基本遗传算法的基础进行了改进,首先使用新的路径编码方式来减少路径编码长度、降低计算复杂程度;其次应用改进的选择算子,在运行初期减小不同个体的适应度差异避免早熟现象,后期增加个体的适应度差异来快速收敛,提高算法效率。通过实例有力验证了该算法的有效性,平均能够减少空行路径15%。 结论指出:贪婪算法和遗传算法在解决切割路径优化问题时都表现出一定的潜力,并取得了非常不错的效果。但他们都无法做到完美。实际上应该针对不同的需求和实际情况采用更合适的算法。最后对今后的研究提出展望。 关键词: 切割路径优化,数控等离子切割,TSP问题,贪婪算法, 遗传算法 上海交通大学工程硕士学位论文 ABSTRACT 第 III 页 PATH OPTIMIZATION OF NC PLASMA CUTTING MACHINE ABSTRACT Nowadays china’s shipbuilding indus try develops rapidly, and various advanced auto-machine is applied to manufacture in order to improve efficiency. Steel cutting is the first working procedure of shipbuilding, and advanced NC plasma cutt ing machine is used widely. The program’s path programming of NC plasma cutting ma chine affect the cutting efficiency directly. In this paper, we research the cutting path sche duling, and suggest two different optimization algorithm for the cutting path. And we expect that they can reduce the cutting blank line, incr ease effective cutting time, so as to improve the cutting efficiency. Cutting path optimization problem can be return or changed into TSP(Traveling Salesman Problem). TSP is one