| 講演名 | 2002/3/15 遺伝的アルゴリズムとヒューリスティクスの融合による巡回セールスマン問題の一解法 小室 信二, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 遺伝的アルゴリズム(GA)とヒューリスティクスを融合することにより,巡回セールスマン問題(TSP)の探索を効率的に行う手法を提案する.TSPは代表的な組合せ最適化問題であり,多くの応用例のある実用上でも重要な問題である.一方,GAは生物進化の原理に着想を得たアルゴリズムであり,TSPに対する有効性が知られている.しかし,TSPで都市の数が多い場合は組合せ爆発を起こしてしまい,GAを用いても膨大な探索時間を必要とする.本研究では,GAで解の候補を表す各個体に知識を持たせ,各個体が個体の生成等の判断を行うことにより効率的な探索の実現を図る.また,従来のGAを用いた手法との比較を行い,この手法の有効性を検証する. |
| 抄録(英) | We propose a method for solving the Traveling Salesman Problem (TSP) by combining the genetic algorithm (GA) and heuristics. TSP is a typical combinatorial optimization problem. On the other hand, GA is an algorithm that is based on the analogy of biological evolution. It is known that GA is useful for the TSP, but it becomes inefficient according to the increase of the number of cities. In this research, candidates for solutions are encoded by individuals and each individual has knowledge for efficient searching. As a result each individual evolves itself and the system realizes efficient searches as a whole. We compare our method with the conventional methods using the GA, and the validity of our method is verified. |
| キーワード(和) | 遺伝的アルゴリズム / ヒューリスティクス / 巡回セールスマン問題 / 組合せ最適化問題 |
| キーワード(英) | Genetic Algorithm / Heuristics / Traveling Salesman Problem / Combinatorial Optimization Problem |
| 資料番号 | KBSE2001-66 |
| 発行日 |
| 研究会情報 | |
| 研究会 | KBSE |
|---|---|
| 開催期間 | 2002/3/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Knowledge-Based Software Engineering (KBSE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 遺伝的アルゴリズムとヒューリスティクスの融合による巡回セールスマン問題の一解法 |
| サブタイトル（和） | |
| タイトル（英） | A Solution for the Traveling Salesman Problem by Combining the Genetic Algorithm and Heuristics |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 遺伝的アルゴリズム / Genetic Algorithm |
| キーワード(2)（和/英） | ヒューリスティクス / Heuristics |
| キーワード(3)（和/英） | 巡回セールスマン問題 / Traveling Salesman Problem |
| キーワード(4)（和/英） | 組合せ最適化問題 / Combinatorial Optimization Problem |
| 第 1 著者 氏名（和/英） | 小室 信二 / Shinji OMURO |
| 第 1 著者 所属（和/英） | 和歌山大学システム工学部 Faculty of Systems Engineering, Wakayama University |
| 発表年月日 | 2002/3/15 |
| 資料番号 | KBSE2001-66 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 743 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |