图7 “S字型”路径效果图
混合遗传算法实现
⑴混合遗传算法的思路。
图8 遗传算法流程图
图9 插入操作流程图
启发式算法简单有效，思路清晰简洁，但是切割路径的效果会随排样图的变化发生很大的差异，而且所得的结果单一，有时候并不能满足实际的需求。路径的优化类似于TSP问题，如果将解决TSP问题的部分方法加以引用和改进，然后再辅助于其他在路径优化中已使用的方法，那么我们是很有可能获得一种更好的优化方法的。
具有实际意义的TSP都会考虑城市与城市之间的可到达和不可到达问题，所以针对性的引入了边*的概念，在切割路径优化中零件之间明显具有可到达和不可到达的问题，所以边*对于解决切割路径有很大的意义。
排样零件的大小各异，而太过于微小的零件对于大零件来说，几乎可以忽略，最近插入法就是可以针对这类微小件来进行处理的。
⑵混合遗传算法的实现。
1）对排样图中的所有零件进行分析，去掉相对于周围紧邻零件来说属于微小件的零件，然后应用边*和轮盘赌，求取一定数量的可行解，形成初始解种群；
2）对形成的初始解应用最近插入法，将去掉的微小零件按照一定的原则插入到初始解中；
3）对插入后的种群进行评估，保优；
4）应用选择，交叉和变异操作来对种群进行遗传操作以生成下一代的个体。
遗传算法和插入操作流程图，如图8、图9所示。
混合遗传算法求得的切割路径效果图，如图10所示。
图10 混合算法效果图
特殊切割路径优化共边切割路径优化
共边切割是在优化排样时按照一定规则将具有长边的零件尽可能以长边对长边的方式排列在一起，在生成切割指令时对这些零件外轮廓的公共边部分只进行一次切割。共边切割的优化方式对排样图有一定的要求，针对不同的排样图提出了“一笔画”和“阶梯型”两种特殊的共边切割方式，打孔点分布在废料区域。
共边切割优化的主要目标是减少激光切割行程和穿孔次数，以此来减少激光切割的时间，同时兼顾激光的切割空行程。
⑴一般共边切割算法。
对于一个常规的排料图来说，也常常会碰到两个零件长边对长边的情况，此时对于这两个零件可以进行共边切割。此时共边切割的算法步骤为：
1）根据实际割缝大小对零件图形进行刀补偏置（按1/2的割缝值对零件外轮廓等距放大，对内轮廓等距缩小）；
2）对具有公共边的相邻零件进行位置调整，使刀补后的轮廓公共边几何重合；
3）按轮廓顺序生成轮廓切割路径时进行公共边判断，如果该轮廓的某公共边已经切割，则不重复形成切割路径（此时需要改变轮廓切割起点，形成不封闭的一段或数段切割轨迹）。
如图11所示，如果按轮廓顺序，先切割右边零件，后切割左边零件。则实际的切割路径为：1→2→3→4→5→6→7→8→9。右边零件切割路径是完整轮廓，左边零件切割路径则是去除公共边（1和2）以后的不封闭轮廓，并且切割起点自动调整到位置5。
