切割路径优化问题的自适应大邻域搜索退火算法

发布时间：2024-05-18 02:23

　　针对定义为广义旅行商问题(GTSP)的激光切割工艺路径优化问题,提出了一种自适应大邻域搜索算法(ALNS)与改进模拟退火算法相结合的混合算法。该算法提出一种融合最近、最远和随机插入操作的统一插入操作和统一最坏删除操作,通过在算法中反复进行删除和插入操作来优化自适应大邻域搜索算法,再运用改进模拟退火算法接受最优解,求得满足工艺约束的最短切割路径。通过GTSP-Lib数据库中的算例和实际切割案例对算法进行验证。结果表明,提出的算法在准确性上与最优算法的误差只有0.31%,但计算速度提高了12%,证明了该算法在求解小规模切割路径问题上有很强的适用性。

【文章页数】：9 页

【部分图文】：

图1切割路径实例示意图

在零件轮廓的完整切割中，激光束通过在轮廓的给定轨迹上移动，到在激光束返回到切割特征点之前在轮廓周长上或其附近打通一个特征点来开始切割[10]。由于激光器始终打开并在整个过程中进行连续切割，因此被认为是有成效的工作状态。相反，当激光切割头在关闭的情况下从一个切割特征点移至另一个切割....

图2自适应大邻域搜索算法框图

如图2所示，根据算法框架确定改进的核心思想是:在定义好初始种群的情况下，通过改善邻域搜索操作中的算子，使算法更快地产生新解，以数值优化为目标接受更优解，对新解进行多次迭代达到最优。将算法分解成独立的功能模块，便于明确各模块目的来进行程序设计。再运用优化判定准则，在多约束条件下获得....

图314st70算例优化路径示意图

该算法求解了25个来自GTSP-Lib数据库的算例，结果如表1所示，达到最优解的解用黑体表示。通过对比发现，在解决小对象规模问题时，该算法具有较好的求解质量，与已知解相比，平均误差仅为0.31%。随着对象规模的增加，最优解获得概率和求解效果都有所下降。对达到最优解的算例14st7....

图414st70算例优化过程

图314st70算例优化路径示意图表1中数据来自于GTSP-Lib数据库，其中计算偏差率=[(改进算法-最佳解决方案)/最佳解决方案]×100%。通过数据可以发现，改进算法在求解小规模问题时，精确度极高，几乎没有误差，平均最优解获得率达到90%。但当问题规模大于45个种簇时，算....

本文编号：3976315