| 講演名 | 2012-11-27 先見近傍解生成による焼きなまし法の並列化手法(最適化,デザインガイア2012-VLSI設計の新しい大地-) 太田 悠介, 伊藤 和人, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 最適化組み合わせ問題の解を探索するメタヒューリスティックアルゴリズムである焼きなまし法(SA)は,現在の解候補からランダムに近傍解を生成し,評価関数値を比較して改善時,または確率的に近傍解を新たな解候補とする手法であり,近傍解の生成と評価関数計算を多数繰り返すため長い時間を要する.本研究では,SA高速化のため,複数の近傍解を生成し,その評価関数計算を並列に行うことで実行時間の短縮を図る.さらに,単一チェーンSAの並列化を目的とし,先見的な近傍解の生成パターンを適応的に変化させることで本来到達しない無駄な近傍解の生成数を削減する手法を提案する. |
| 抄録(英) | Simulated annealing (SA) is a general method to solve combinational optimization problems. SA generates a neighbor solution from a current solution randomly and evaluates the solution by a cost function. If a neighbor solution is better than a current solution, or otherwise stochastically, the neighbor solution is accepted as a new current solution. SA needs long execution time because it must iterate generating and evaluating a neighbor solution many times. We propose a fast SA method where some neighbor solutions are generated at a time in a look-ahead manner and evaluated in parallel. A method to adaptively generate neighbor solutions is proposed to reduce void solutions which are not used in a SA chain. |
| キーワード(和) | 組み合わせ最適化 / 焼きなまし法 / 並列化 / 先見 / 近傍解生成 |
| キーワード(英) | combinational optimization / simulated annealing / parallelize / look-ahead / neighbor solution generation |
| 資料番号 | VLD2012-73,DC2012-39 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2012/11/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 先見近傍解生成による焼きなまし法の並列化手法(最適化,デザインガイア2012-VLSI設計の新しい大地-) |
| サブタイトル（和） | |
| タイトル（英） | A Method to Parallelize Simulated Annealing Algorithm by Generating Look-ahead Neighbor Solutions |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組み合わせ最適化 / combinational optimization |
| キーワード(2)（和/英） | 焼きなまし法 / simulated annealing |
| キーワード(3)（和/英） | 並列化 / parallelize |
| キーワード(4)（和/英） | 先見 / look-ahead |
| キーワード(5)（和/英） | 近傍解生成 / neighbor solution generation |
| 第 1 著者 氏名（和/英） | 太田 悠介 / Yusuke OTA |
| 第 1 著者 所属（和/英） | 埼玉大学大学院理工学研究科 Graduate School of Science and Engineering Saitama University |
| 第 2 著者 氏名（和/英） | 伊藤 和人 / Kazuhito ITO |
| 第 2 著者 所属（和/英） | 埼玉大学大学院理工学研究科 Graduate School of Science and Engineering Saitama University |
| 発表年月日 | 2012-11-27 |
| 資料番号 | VLD2012-73,DC2012-39 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 320 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |