Hybrid Genetic Algorithm with Simulated Annealing Based on Best-Fit Strategy for Rectangular Packing Problem
In this paper we address a rectangular packing problem (RPP), which is one of the most difficult NP-complete problems. Borrowing from the respective advantages of the two algorithms, a hybrid of genetic algorithm (GA) and simulated annealing (SA) is developed to solve the RPP. Firstly, we adopt and improve Burke’s best-fit (BF) placement strategy, which is not restricted to the first shape but may search the list for better candidate shapes for placement. Secondly, we propose a new crossover operator, named Improved Precedence Operation Crossover (IPOX), which can preserve the valuable characteristics of the previous generation. At last, using a new temperature and iterations strategy and Boltzmann-type operator, we propose SA to re-intensify search from the promising solutions. The computational results validate the quality and the effectiveness of hybrid algorithm.
L.Y. Xie, M.N. James, Y.X. Zhao and W.X. Qian
Y. Y. Zhou et al., "Hybrid Genetic Algorithm with Simulated Annealing Based on Best-Fit Strategy for Rectangular Packing Problem", Advanced Materials Research, Vols. 118-120, pp. 379-383, 2010