| 講演名 | 1999/3/19 アナログk-exchangeによる2次割当て問題の解法 新妻 弘崇, 石井 信, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本報告では, 新しいニューラルネットワークに基づく組合せ最適化問題の解法を提案する. 特に2次割り当て問題に対して適用する. 本手法は, 順列のk個以下の要素を同時に入れ替えるk-exchangeヒューリスティクスのアナログ版とみなすことができる. kの値としてk-exchangeヒューリスティクスが使えないような大きな値を使うことができるため, 中距離サーチと近距離サーチを同時に実行できる. 比較的大きな(N=80～150)2次割当て問題に対してこの手法の計算機実験を行った結果, 我々の新しい手法は今までのチャンピオンのアルゴリズムと同程度に良い近似解を計算できることが分かった. また, いくつかのベンチマークについては, 現在のチャンピオンのアルゴリズムよりも良い解が計算できることが分かった. |
| 抄録(英) | In this report, we propose aneural approach to the quadratic assignment problem (QAP). Our new approach is an analog version of k-exchange heuristic method, which exchanges elements whose number is smaller than k in a solution permutation. Since our approach can take a large k value, it realizes a middle-range and a short-range searches simultaneously. Experiments applied to relatively large-scale QAPs show that our approach is comparable to the present champion algorithms. Moreover, our approach can obtain better solutions than the previous champion algorithms for several benchmark problems. |
| キーワード(和) | 2次割当て問題 / λ-opt / k-exchange / 2重制約ネットワーク |
| キーワード(英) | quadratic assignment problem / λ-opt / k-exchange / doubly constrained network |
| 資料番号 | NC98-165 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NC |
|---|---|
| 開催期間 | 1999/3/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Neurocomputing (NC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | アナログk-exchangeによる2次割当て問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | Analog k-exchange approach for quadratic assignment problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 2次割当て問題 / quadratic assignment problem |
| キーワード(2)（和/英） | λ-opt / λ-opt |
| キーワード(3)（和/英） | k-exchange / k-exchange |
| キーワード(4)（和/英） | 2重制約ネットワーク / doubly constrained network |
| 第 1 著者 氏名（和/英） | 新妻 弘崇 / Hirotaka Niitstuma |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Nara Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 石井 信 / Shin Ishii |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Nara Institute of Science and Technology |
| 発表年月日 | 1999/3/19 |
| 資料番号 | NC98-165 |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 674 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |