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

Yu Yu Zhou; Yun Qing Rao; Chao Yong Zhang; Liang Gao

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

Paper Titles

Optimizing of Turning Parameters Using Multi-Objective Genetic Algorithm
p.359

Bifurcation of Non-Semi-Simple Zero Eigenvalues at the Critical Point of the Statical Bifurcation of Nonlinear Rotor System
p.364

A Novel Variable Neighborhood Genetic Algorithm for Multi-Objective Flexible Job-Shop Scheduling Problems
p.369

Failure Rate Analysis and Model Consisting of Four Elements for Components
p.374

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

The Application of MARS on Crashworthiness Improvement
p.384

Design of Double-Deck Isolation Systems
p.389

Bearing Parameter Optimization of a Compressor Rotor System Based on Orthogonal Experimental Design
p.394

An Approach Based on Enhanced Collaborative Optimization and Kriging Approximation in Multidisciplinary Design Optimization
p.399

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 118-120Hybrid Genetic Algorithm with Simulated Annealing...

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

Abstract:

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.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 118-120)

Pages:

379-383

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.118-120.379

Citation:

Cite this paper

Online since:

June 2010

Authors:

Yu Yu Zhou, Yun Qing Rao, Chao Yong Zhang, Liang Gao

Keywords:

Genetic Algorithm (GA), Hybrid, Rectangular Packing, Simulated Annealing (SA)

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] S. Jakobs: European Journal of Operational Research Vol. 88 (1996), p.169.

Google Scholar

[2] K.K. Lai and W.M. Chan: International Journal of Industrial Engineering Vol. 4 (1997), p.135.

Google Scholar

[3] T.W. Leung, C.K. Chan, and M. Troutt, in: Comparison of meta-heuristics for the two dimensional orthogonal packing problem, Working Paper, Department of Applied Mathematics, Hong Kong Ploytechnic University, Hong Kong (2000).

DOI: 10.3934/jimo.2008.4.53

Google Scholar

[4] E. Hopper and B.C.H. Turton: European Journal of Operational Research Vol. 128 (2001), pp.34-40.

Google Scholar

[5] A. Soke and Z. Bingul: Engineering Applications of Artificial Intelligence Vol. 19 (2006), p.560.

Google Scholar

[6] T.W. Leung, C.K. Chan, and M.D. Troutt: European Journal of Operational Research Vol. 145 (2003), p.535.

Google Scholar

[7] E. Burke, G. Kendall, and G. Whitwell: Operations Research Vol. 52 (2004), p.664.

Google Scholar

[8] F.G. Ortmann, N. Ntene and J.H.V. Vuuren: European Journal of Operational Research Vol. 203 (2010).

Google Scholar