Hybrid Genetic Algorithm with Simulated Annealing Based on Best-Fit Strategy for Rectangular Packing Problem

Abstract:

Article Preview

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.

Info:

Periodical:

Advanced Materials Research (Volumes 118-120)

Edited by:

L.Y. Xie, M.N. James, Y.X. Zhao and W.X. Qian

Pages:

379-383

DOI:

10.4028/www.scientific.net/AMR.118-120.379

Citation:

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

Online since:

June 2010

Export:

Price:

$35.00

In order to see related information, you need to Login.

In order to see related information, you need to Login.