An Improved Simulated Annealing for 3D Packing with Sequence Triple and Quintuple Representations

概要

論文の詳細を見る
The 3D packing for VLSI physical design is facing big challenges to get better solution quality with less computational time. In this paper, we propose 2-stage simulated annealing with crossover operator (2-SA-X) to solve a general rectangular 3D-packing problem by using sequence-k-tuple representation, where k is defined by 3 and 5. The basic ideas of this research are to reuse the information of past solution by integrating the crossover operator from genetic algorithm and to improve the global search ability by using two different stages. The first stage mainly focuses on the global search by moving methods with big changes, including the crossover, while the second stage focuses on local search by the moving methods with small changes. Based on the experiment using ami98_3D benchmark, the computational performance of 3D packing is considerably improved. The paper shows how much the 3D-packing ratio of volume and the computational time can be improved by using the proposed 2-SA-X algorithm, comparing with normal 2-stage simulated annealing (2-SA) without the crossover operator.
2011-11-21