| 講演名 | 2010-03-09 Lin-Kernighanアルゴリズムの二次割当問題解法への応用 柴田 和亮, 堀尾 喜彦, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 二次割当問題(QAP)の優れた解法として,カオスニューロンモデルを用いたニューラルネットワークによるカオスダイナミクスで2-opt局所探索を駆動する,指数減衰カオスタブーサーチが提案されている.一方,巡回セールスマン問題(TSP)においては,Lin-Kernighanアルゴリズムをカオスニューラルネットワークで駆動する方法が提案され,2-opt法をカオスニューラルネットワークで駆動する方法よりも優れた性能を示している.我々は,QAPの解法において,指数減衰カオスタブーサーチの2-opt局所探索の代わりに,Lin-Kernighanアルゴリズムを導入することを目的としている.しかし,Lin-KernighanアルゴリズムはTSPを解く局所探索アルゴリズムであるため,そのままではQAPを解くための指数減衰カオスタブーサーチに導入することはできない.そこで,本稿では,Lin-Kernighanアルゴリズムを指数減衰カオスタブーサーチに導入するための準備として,Lin-Kernighanアルゴリズムの考え方をQAPの解法に適用したアルゴリズムを提案する.また,シミュレーション実験により,提案した手法と2-opt法の解探索能力を比較・検討する.さらに,提案手法に用いるLin-Kernighan的アルゴリズムでの割り当て回数を変更した場合の解法能力について検討する. |
| 抄録(英) | A 2-opt local search driven by a chaotic neural network (exponential chaotic tabu search) was proposed for quadratic assignment problems (QAPs). The exponential chaotic tabu search has been demonstrated to have a high ability to solve QAPs. For traveling salesman prolems (TSPs), a chaos driven Lin-Kernighan algorithm was proposed, and further, showed a better performance than chaos driven 2-opt algorithm. Our final goal is to apply the Lin-Kernighan algorithm to the exponential chaotic tabu search for QAPs instead of the 2-opt algorithm. We, however, cannot directly apply the Lin-Kernighan algorithm to QAPs because the algorithm was originally for TSPs. Therefore, in this paper, we propose a technique to solve QAPs based on the Lin-Kernighan algorithm before applying it to the exponential tabu search. We show numerical simulation results to compare the performances of the proposed technique and the 2-opt algorithm. Furthermore, we show simulation results with a different number of exchanges in the Lin-Kernighan algorithm used in the proposed technique. |
| キーワード(和) | 二次割当問題 / Lin-Kernighanアルゴリズム |
| キーワード(英) | Quadratic Assignment Problems / Lin-Kernighan Algorithm |
| 資料番号 | NLP2009-164 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NLP |
|---|---|
| 開催期間 | 2010/3/2(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Nonlinear Problems (NLP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Lin-Kernighanアルゴリズムの二次割当問題解法への応用 |
| サブタイトル（和） | |
| タイトル（英） | An Application of Lin-Kernighan Algorithm to Quadratic Assignment Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 二次割当問題 / Quadratic Assignment Problems |
| キーワード(2)（和/英） | Lin-Kernighanアルゴリズム / Lin-Kernighan Algorithm |
| 第 1 著者 氏名（和/英） | 柴田 和亮 / Kazuaki SHIBATA |
| 第 1 著者 所属（和/英） | 東京電機大学大学院工学研究科 Graduate School of Engineering, Tokyo Denki University |
| 第 2 著者 氏名（和/英） | 堀尾 喜彦 / Yoshihiko HORIO |
| 第 2 著者 所属（和/英） | 東京電機大学大学院工学研究科 Graduate School of Engineering, Tokyo Denki University |
| 発表年月日 | 2010-03-09 |
| 資料番号 | NLP2009-164 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 458 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |