基于SP的模拟退火算法在装箱问题中的应用

Application of SP-Based Simulated Annealing Alogrithm in Bin Packing Problem

在传统模拟退火算法的基础上,对装箱问题的优化算法进行了研究。结合装箱问题的具体特点,采用SP序列对来描述模块间的拓扑关系,并通过精细的模拟退火策略(精细的降温策略,提前退出策略),以及增量式的新解评估策略对算法进行优化。试验结果表明,相比传统的模拟退火框架,改进的算法能够取得较好的运行时间与面积利用率。

A new algorithm to solve the bin packing problem is formulated within the simulated annealing framework.Sequence pair is adopted to represent the topological relationship among the modules.In view of the characteristics of the bin packing problem,the paper improves the algorithm by incorporating the elaborate annealing strategy and a novel incremental solution evaluating algorithm.The experiment that follows shows that,compared with the traditional framework,the algorithm can arrive an a better area utility rate in shorter time.