基于模拟退火算法的一维下料研究

Research on one-dimensional cutting stock problem based on simulated annealing algorithm

模拟退火算法是求解一维下料问题的有效方法之一。但传统模拟退火算法具有易于陷入局部最优解的缺点,其性能好坏除了与一些参数设置有关外,特别依赖于邻域结构设计和编码机制的效率。为设计高效的求解一维下料问题的模拟退火算法,提出了新的基于一维下料问题特征的变异算子和解码策略。通过实验计算,与文献中的3组案例进行比较,结果优于部分既有文献的结果,验证了所提算法的有效性。

Simulated annealing is one of the most efficient algorithms to solve one-dimensional cutting stock problem.However,traditional simulated annealing algorithms have the weakness of obtaining local optimal solutions.In addition to some parameters,its performance relies on neighborhood structure and decoding strategy.Based on the problem-knowledge,the new mutation operator and decoding strategy are presented to improve simulated annealing algorithm.By computational experiments with three instances,some better results comparing to those of in literatures are obtained,and the efficiency of presented algorithm is verified.