| 講演名 | 1997/5/22 複雑さの制御による問題解決 : 大規模巡回セールスマン問題の求解 新妻 清三郎, 中島 努, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文は、帰納的アルゴリズムと呼ばれる一種のメタヒューリステックスについて述べる。本アルゴリズムはナップサック問題や数百都市から成る巡回セールスマン問題(略して、TSP)等組合せ最適化問題に適用され、良好な結果を得ている。本論文では、数万都市より成る大規模なTSPへの適用を目指す。組合せ的爆発を抑えるため、問題の複雑さの制御という視点が導入される。複雑さの制御は抽象化とスコープの設定によって実現される。帰納的アルゴリズムは三つのパラメータを含む。本アルゴリズムがこれらのパラメータに対して安定であることおよび各パラメータに対する推奨値が示される。また、85,900都市問題を含むベンチマーク問題(TSP.LIB)に対する実験結果が示される。 |
| 抄録(英) | This paper describes a meta-heuristics called an Inductive Algorithm, which is a problem-solving paradigm based on abstraction and analogical reasoning. The algorithm have been applied to combinatorial optimization prob-lems, for example, knapsack problems and traveling salesman problems (TSP) including hundreds of cities. The algorithm is developed which makes it possible to solve large scale TSPs consisting of scores of thousands of cities. To prevent a combinatorial explosion from happening, a vew point of control of problem complexity is introduced. The control is done by abstraction and setting scopes. The modified algolithm is applicable to TSP including 85,900 cities. Inductive Algorithm contains three kinds of parameters. This paper provides experimental results which show the algorithm to be stable for variations of parameters and give appropriate values for these parameters. |
| キーワード(和) | メタヒューリステックス / 帰納的アルゴリズム / 抽象化 / 類比推論 / 巡回セールスマン問題 |
| キーワード(英) | meta-heuristics / inductive algorithm / abstraction / analogical reasoning / traveling salesman problem |
| 資料番号 | AI97-4 |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 1997/5/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 複雑さの制御による問題解決 : 大規模巡回セールスマン問題の求解 |
| サブタイトル（和） | |
| タイトル（英） | Problem Solving based on the Control of Complexity : for Solving the Large Scale Traveling Salesman Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | メタヒューリステックス / meta-heuristics |
| キーワード(2)（和/英） | 帰納的アルゴリズム / inductive algorithm |
| キーワード(3)（和/英） | 抽象化 / abstraction |
| キーワード(4)（和/英） | 類比推論 / analogical reasoning |
| キーワード(5)（和/英） | 巡回セールスマン問題 / traveling salesman problem |
| 第 1 著者 氏名（和/英） | 新妻 清三郎 / Seizaburo Niitsuma |
| 第 1 著者 所属（和/英） | 静岡大学工学部システム工学科 Department of Systems Engineering, Faculty of Engineering, Shizuoka University |
| 第 2 著者 氏名（和/英） | 中島 努 / Tsutomu Nakashima |
| 第 2 著者 所属（和/英） | 静岡大学工学部システム工学科 Department of Systems Engineering, Faculty of Engineering, Shizuoka University |
| 発表年月日 | 1997/5/22 |
| 資料番号 | AI97-4 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 63 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |