| 講演名 | 2013-03-14 二次割当問題の交換要素を適応的に決定するカオス的局所探索法 渡辺 明生, 黒田 佳織, 藤原 寛太郎, 池口 徹, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 二次割当問題はNP困難な組合せ最適化問題である.二次割当問題の特殊な例に,巡回セールスマン問題がある.巡回セールスマン問題に対する最も強力な近似解法の一つとしてLin-Kernighan法がある.Lin-Kernighan法における探索では,交換する枝数を適応的に決定するという特徴がある.本稿ではLin-Kernighan法の持つ特徴を二次割当問題に応用した新しい探索法を提案している.提案法では,交換する要素数を適応的に決定することで,計算時間を押さえつつ,効率の良い探索法を実現している.本稿ではさらに,提案手法が局所最適解に陥ることを避けるために,カオスダイナミクスを導入した手法も提案している.カオスダイナミクスの有効性を評価するために,既存の二次割当問題の局所探索法との性能比較を行う.数値実験の結果より,カオスダイナミクスを導入することで,効率良く局所最適解を抜け出すことができることが示された. |
| 抄録(英) | The quadratic assignment problem(QAP)is one of the NP-hard combinatorial optimization problems. Then, it is required to develop approximate algorithms for finding near optimal solutions in realistic time. 0n the other hand, to solve traveling salesman problems which is a special case of QAP, the Lin-Kernighan algorithm has been proposed. In this report, we propose an algorithm for solving QAPs by introducing characteristic property of searching process in the Lin-Kernighan algorithm. We also in- troduced chaotic dynamics into the proposed algorithm to escape undesirable local minima. To evaluate solving performance of the proposed method, we compared the performance of the proposed method with that of the conventional methods. As a result, the solving performance of the proposed method with chaotic dynamics exhibits smaller gaps from optimal solutions than the conventional algorithms. |
| キーワード(和) | 組合せ最適化 / 二次割当問題 / 局所探索法 |
| キーワード(英) | combinatorial optimization / quadratic assignment problems / local search |
| 資料番号 | NLP2012-145 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2013/3/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 二次割当問題の交換要素を適応的に決定するカオス的局所探索法 |
| サブタイトル（和） | |
| タイトル（英） | A Chaotic Local Search Algorithm with Adaptive Exchange of Elements for Quadratic Assignment Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 組合せ最適化 / combinatorial optimization |
| キーワード(2)（和/英） | 二次割当問題 / quadratic assignment problems |
| キーワード(3)（和/英） | 局所探索法 / local search |
| 第 1 著者 氏名（和/英） | 渡辺 明生 / Akio WATANABE |
| 第 1 著者 所属（和/英） | 埼玉大学工学部情報システム工学科 Faculty of Engineering, Saitama University |
| 第 2 著者 氏名（和/英） | 黒田 佳織 / Kaori KURODA |
| 第 2 著者 所属（和/英） | 埼玉大学大学院理工学研究科数理電子情報部門 Graduate School of Science and Engineering, Saitama University |
| 第 3 著者 氏名（和/英） | 藤原 寛太郎 / Kantaro FUJIWARA |
| 第 3 著者 所属（和/英） | 埼玉大学大学院理工学研究科数理電子情報部門 Graduate School of Science and Engineering, Saitama University |
| 第 4 著者 氏名（和/英） | 池口 徹 / Tohru IKEGUCHI |
| 第 4 著者 所属（和/英） | 埼玉大学大学院理工学研究科数理電子情報部門:埼玉大学総合研究機構脳科学融合研究センター Graduate School of Science and Engineering, Saitama University:Brain Science Institute, Saitama University |
| 発表年月日 | 2013-03-14 |
| 資料番号 | NLP2012-145 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 487 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |