| 講演名 | 1998/4/24 巡回セールスマン問題に対する並列遺伝的アルゴリズムの検討 片山 謙吾, 平林 永行, 成久 洋之, 池田 早人, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 数々の組合せ最適化問題に対してさまざまな遺伝的アルゴリズム(GA)が提案されている.近年では, GAにおける並列処理への実装の容易さなどから並列GAの有効性が検討されている.代表的な並列GAとしては, 地理的に独立した環境が与えられた典型的な一例であるIsland(島)での生物進化過程をヒントにしたIslandモデル等がある.本論文では, 巡回セールスマン問題(TSP)に対する三種類のタイプのIslandモデルを実装し, MIMD方式の並列計算機上にTSPのベンチマーク問題集TSPLIBを用いて各モデルの有効性を検討する. |
| 抄録(英) | Various types of the genetic algorithms (GA) for solving the combinatorial optimization problems were proposed. Recently, because it is easy to implement the parallel GA (PGA), the effectiveness of the PGA has been investigated. As typical PGA model, we can mention the island model. In this paper, we implement three types of this island model, and investigate effectiveness of each type using the benchmark instances of the traveling salesman problem on a parallel computer. |
| キーワード(和) | 並列遺伝的アルゴリズム / islandモデル / 巡回セールスマン問題 / 完全サブツアー交換交叉 / distance preserving crossover |
| キーワード(英) | parallel genetic algorithm / island model / traveling salesman problem / complete subtour exchange crossover / distance preserving crossover |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1998/4/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 巡回セールスマン問題に対する並列遺伝的アルゴリズムの検討 |
| サブタイトル（和） | |
| タイトル（英） | A Study of Parallel Genetic Algorithms for the Traveling Salesman Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 並列遺伝的アルゴリズム / parallel genetic algorithm |
| キーワード(2)（和/英） | islandモデル / island model |
| キーワード(3)（和/英） | 巡回セールスマン問題 / traveling salesman problem |
| キーワード(4)（和/英） | 完全サブツアー交換交叉 / complete subtour exchange crossover |
| キーワード(5)（和/英） | distance preserving crossover / distance preserving crossover |
| 第 1 著者 氏名（和/英） | 片山 謙吾 / Kengo KATAYAMA |
| 第 1 著者 所属（和/英） | 岡山理科大学工学部情報工学科 Department of Information & Computer Engineering, Faculty of Engineering, Okayama University of Science. |
| 第 2 著者 氏名（和/英） | 平林 永行 / Hisayuki HIRABAYASHI |
| 第 2 著者 所属（和/英） | 岡山理科大学工学部情報工学科 Department of Information & Computer Engineering, Faculty of Engineering, Okayama University of Science. |
| 第 3 著者 氏名（和/英） | 成久 洋之 / Hiroyuki NARIHISA |
| 第 3 著者 所属（和/英） | 岡山理科大学工学部情報工学科 Department of Information & Computer Engineering, Faculty of Engineering, Okayama University of Science. |
| 第 4 著者 氏名（和/英） | 池田 早人 / Hayato IKEDA |
| 第 4 著者 所属（和/英） | 岡山理科大学工学部情報工学科 Department of Information & Computer Engineering, Faculty of Engineering, Okayama University of Science. |
| 発表年月日 | 1998/4/24 |
| 資料番号 | |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 36 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |