基于遗传算法的轮廓切割顺序受限路径优化

2012年03月21日17:03:10 本网站我要评论(2)字号：T | T | T

关键字：应用

徐建明，林示麟，董　辉，俞　立
浙江工业大学信息工程学院，浙江杭州

摘　　　要：考虑一类轮廓切割顺序受限的加工路径优化问题。遵循由内到外的轮廓切割约束条件，以遍历所有待切割轮廓且刀头在轮廓间移动的空行程距离较短为优化目标，把约束条件转化到遗传算法编码问题。采用启发式搜索技术以加快遗传算法的爬山速度，并且能自适应调整交叉和变异概率。实际应用结果表明所提算法能有效缩短空行程。

关　键　词：路径优化；遗传算法；启发式搜索；轮廓切割

１　引　言
在服装、鞋、箱包的面料裁割过程中，刀头沿轮廓切割时间相对固定，通过路径优化，可以缩短刀头在轮廓间移动的空行程距离，以节省加工时间。轮廓加工顺序的不同以及加工起点的不一样都影响着加工路径的长度；因而不改变加工起点的优化是不充分的［１２］，不改变轮廓顺序的优化也不充分［３］。因而，需要在一定裁割顺序限制下，对轮廓裁割顺序和裁割起点进行优化选择，以缩短面料裁割加工时间。面料裁割加工路径的优化问题是一类广义旅行商问题（ＧＴＳＰ），当优化规模较大时，将ＧＴＳＰ转化为ＴＳＰ问题或采用数学规划直接求取方法往往难以处理［４］；而基于随机值的遗传算法［５］对ＧＴＳＰ问题求解却无法解决路径顺序受限问题。本文在轮廓切割顺序受限的情况下，采用分层法将轮廓分层构成染色体，把约束条件转化到染色体编码问题中，使得染色体解码后的路径切割顺序都是可行的，从而大大缩小搜索空间，排除产生不可行路径的可能。算法计算过程中结合了启发式搜索技术并采用了自适应调整交叉变异概率，加强了遗传算法的寻优能力并能根据实际情况适时退出遗传算法，达到优化效果与优化时间的折中。

登录网站后可下载文件

基于遗传算法的轮廓切割顺序受限路径优化

相关阅读: