| 講演名 | 1998/1/29 巡回セールスマン問題の遺伝的アルゴリズムに対する凸包の応用 竹中 要一, 船曳 信生, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では, 巡回セールスマン問題の遣伝的アルゴリズムに対して凸包による訪問順序制限定理を用いた求解性能向上方法の提案を行う. 凸包とは点集合の任意の2要素を結ぶ閉線分を内部に含む最小の凸多角形であり, 要素数nの点集合の凸包を求めるアルゴリズムの計算量の下界はO (n log n) である. 訪問順序制限定理は凸包を用いてユークリッド平面上の巡回セールスマン問題の最短巡回路となる為の必要条件を示している. また, 遣伝的アルゴリズムは自然界の自然淘汰の過程をモデルとした解法であり, 巡回セールスマン問題の近似解探索アルゴリズムの中でも優れた解法の一つとして知られている. 本論文では, 凸包によって与えられる最短巡回路の必要条件を充足する巡回路を初期染色体とする事により, 遺伝的アルゴリズムの求解性能の向上を図る. ベンチマーク問題を用いたシミュレーションによる性能評価の結果, 都市数の大きい問題において訪問順序制限定理を用いた解法の求解精度が向上した. |
| 抄録(英) | In this paper, we propose an application of the "visiting order restriction theorem" to Pal's algorithm, a genetic algorithm for the traveling salesman problem (TSP). The visiting order restriction theorem gives a necessary condition for the shortest tour of TSP on the Euclidean plane by using the convex hull. The convex hull of a set of points S on a plane is defined as the smallest convex polygon that encloses S. The O (|S|log|S|)-time algorithm has been known to find the convex hull of a set of points S. The genetic algorithm, which simulates the process of the natural selection, is known as one of best approximate algorithms for TSP. In our method, the initial tours are produced to satisfy the necessary condeition for the shortest path in order to improve the solution quality. The simulation results using benchmark problems show our genetic algorithm finds shorter tours than P'al's algorithm at the large size benchmark problems. |
| キーワード(和) | 巡回セールスマン問題 / 訪問順序制限定理 / 遣伝的アルゴリズム / 凸包 / 近似解探索アルゴリズム |
| キーワード(英) | Traveling Salesman Problem / Visiting Order Restriction Theorem / Genetic Algorithm / Convex Hull / Approximate Algorithms |
| 資料番号 | SS97-48 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 1998/1/29(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 巡回セールスマン問題の遺伝的アルゴリズムに対する凸包の応用 |
| サブタイトル（和） | |
| タイトル（英） | An Application of Convex Hull to Genetic Algorithm for Traveling Salesman Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 巡回セールスマン問題 / Traveling Salesman Problem |
| キーワード(2)（和/英） | 訪問順序制限定理 / Visiting Order Restriction Theorem |
| キーワード(3)（和/英） | 遣伝的アルゴリズム / Genetic Algorithm |
| キーワード(4)（和/英） | 凸包 / Convex Hull |
| キーワード(5)（和/英） | 近似解探索アルゴリズム / Approximate Algorithms |
| 第 1 著者 氏名（和/英） | 竹中 要一 / Yoichi TAKENAKA |
| 第 1 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Division of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University |
| 第 2 著者 氏名（和/英） | 船曳 信生 / Nobuo FUNABIKI |
| 第 2 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Division of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University |
| 発表年月日 | 1998/1/29 |
| 資料番号 | SS97-48 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 521 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |