|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/7826
|
| タイトル: | 局所的な交叉EAXを用いたGAの高速化とTSPへの適用 |
| 著者: | 永田, 裕一 |
| キーワード: | genetic algorithm
TSP, EAX
localized crossover
population diversity |
| 発行日: | 2007 |
| 出版者: | 人工知能学会 |
| 誌名: | 人工知能学会論文誌 |
| 巻: | 22 |
| 号: | 5 |
| 開始ページ: | 542 |
| 終了ページ: | 552 |
| DOI: | 10.1527/tjsai.22.542 |
| 抄録: | We propose an genetic algorithm (GA) that applies to the traveling salesman problem (TSP). The GA uses edge assembly crossover (EAX), which is known to be effective for solving the TSP. We first propose a fast implementation of a localized EAX where localized edge exchanges are used in the EAX procedure. We also propose a selection model with an effective combination of the localized EAX that can maintain population diversity at negligible computational costs. Edge entropy measure is used to evaluate population diversity. We demonstrate that the proposed GA is comparable to state-of-the-art heuristics for the TSP. Especially, the GA is superior to them on large instances more than 10,000 cities. For example, the GA found an optimal solution of brd14051 (14,051 cities instance) with a reasonable computational cost. The results are quite impressive because the GA does not use Lin-Kernighan local search (LKLS) even though almost all existing state-of-the-art heuristics for the TSP based on LKLS and its variants. |
| Rights: | Copyright (C) 2007 人工知能学会. 永田 裕一, 人工知能学会論文誌, 22(5), 2007, 542-552. |
| URI: | http://hdl.handle.net/10119/7826 |
| 資料タイプ: | publisher |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| A10929.pdf | | 299Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
