| 講演名 | 2002/6/20 Moveの制限によるシミュレイティッド・アニーリング法を用いたパッキングの高速化 内田 誠司, 高橋 篤司, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 2次元パッキング間題はNP困難であるので,制約を満たす多数の解を生成し,その中から評価が最良の解を選び出すSimulated Annealing法(SA法)などの探索的手法がよく用いられている.SA法では,ある解を別の解に変換するMove集合が定義され,Move集合からランダムにMoveを候補として選択し,そのMoveを採用するかどうかテストする.しかし,ある種のMoveは解が準最適解に近い場合ほとんど採用されず,そのようなMoveを候補とすることは計算時間の無駄となっている.そこで本研究では,SA法において,解の評価値と採用されるMoveの特徴を統計的に調べ,採用される確率の低いMoveを候補としないことによってMoveが採用される確率を高め,計算時間を短縮する手法を提案する.提案手法の有効性を確認するために,2次元パッキングを表現するデータ構造としてParametric-BSGを用い,ブロック対交換Moveをブロック対の差と解の評価値により,Move候補としない制限を加えた実験を行った.実験結果から,適切な制限を加えることで提案手法により,良質なパッキングを短時間で得ることを確認した. |
| 抄録(英) | 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. |
| キーワード(和) | Simulated Annealing法 / Parametric-BSG / 2次元パッキング / Move |
| キーワード(英) | Simulated annealing methods / Parametric-BSG / two-dimensional packing / move |
| 資料番号 | CAS2002-17 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CAS |
|---|---|
| 開催期間 | 2002/6/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Circuits and Systems (CAS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Moveの制限によるシミュレイティッド・アニーリング法を用いたパッキングの高速化 |
| サブタイトル（和） | |
| タイトル（英） | Acceleration of Packing by Move Restriction in Simulated Annealing |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Simulated Annealing法 / Simulated annealing methods |
| キーワード(2)（和/英） | Parametric-BSG / Parametric-BSG |
| キーワード(3)（和/英） | 2次元パッキング / two-dimensional packing |
| キーワード(4)（和/英） | Move / move |
| 第 1 著者 氏名（和/英） | 内田 誠司 / Seiji UCHIDA |
| 第 1 著者 所属（和/英） | 東京工業大学大学院集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 高橋 篤司 / Atsushi TAKAHASHI |
| 第 2 著者 所属（和/英） | 東京工業大学大学院集積システム専攻 Department of Communications and Integrated Systems, Tokyo Institute of Technology |
| 発表年月日 | 2002/6/20 |
| 資料番号 | CAS2002-17 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 161 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |