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.
Rectangular packing Genetic algorithm Simulated Annealing Hybrid
Yuyu Zhou Yunqing Rao Chaoyong Zhang Liang Gao
The State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of S The State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of S
国际会议
沈阳
英文
379-383
2010-07-28（万方平台首次上网日期，不代表论文的发表时间）