Presentation | 2002/6/20 Acceleration of Packing by Move Restriction in Simulated Annealing Seiji UCHIDA, Atsushi TAKAHASHI, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Since two-dimensional packing problem is NP-hard, simulated annealing methods that select a best solution among a number of created solutions have become popular. In simulated annealing, a move candidate that changes a solution to another one is randomly selected from the move set and tested whether it is accepted. However, some kinds of moves are rarely accepted when the current solution is near optimal. In this paper, we propose an acceleration technique of simulated annealing that selects a move from the move set excluding moves with low acceptance possibility as a candidate. In experiments that uses a parametric-BSG as a date structure, moves of pairwise interchange of blocks are excluded according to the balance of the two blocks and the area ratio of the current solution. By experiments, the proposed technique is confirmed effective when moves are properly excluded. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Simulated annealing methods / Parametric-BSG / two-dimensional packing / move |
Paper # | CAS2002-17 |
Date of Issue |
Conference Information | |
Committee | CAS |
---|---|
Conference Date | 2002/6/20(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Circuits and Systems (CAS) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Acceleration of Packing by Move Restriction in Simulated Annealing |
Sub Title (in English) | |
Keyword(1) | Simulated annealing methods |
Keyword(2) | Parametric-BSG |
Keyword(3) | two-dimensional packing |
Keyword(4) | move |
1st Author's Name | Seiji UCHIDA |
1st Author's Affiliation | Department of Communications and Integrated Systems, Tokyo Institute of Technology() |
2nd Author's Name | Atsushi TAKAHASHI |
2nd Author's Affiliation | Department of Communications and Integrated Systems, Tokyo Institute of Technology |
Date | 2002/6/20 |
Paper # | CAS2002-17 |
Volume (vol) | vol.102 |
Number (no) | 161 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |