|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/7827
|
| タイトル: | 局所的多様性の損失を考慮した評価関数を用いたGAのTSPへの適用 |
| 著者: | 永田, 裕一 |
| キーワード: | genetic algorithm
TSP
EAX
local diversity loss
evaluation function |
| 発行日: | 2006 |
| 出版者: | 人工知能学会 |
| 誌名: | 人工知能学会論文誌 |
| 巻: | 21 |
| 号: | 2 |
| 開始ページ: | 195 |
| 終了ページ: | 204 |
| DOI: | 10.1527/tjsai.21.195 |
| 抄録: | The edge assembly crossover (EAX) is considered the best available crossover for traveling salesman problems (TSPs). In this paper, a modified EAX algorithm is proposed. The key idea is to maintain population diversity by eliminating any exchanges of edges by the crossover that does not contribute to an improved evaluation value. For this, a new evaluation function is designed considering local diversity loss of the population. The proposed method is applied to several benchmark instances with up to 4461 cities. Experimental results show that the proposed method works better than other genetic algorithms using other improvements of the EAX. The proposed method can reach optimal solutions for most benchmark instances with up to 2392 cities with probabilities higher than 90%. For an instance called fnl4461, this method can reach an optimal solution with probability 60% when the population size is set to 300 -- an extremely small population compared to that needed in previous studies. |
| Rights: | Copyright (C) 2006 人工知能学会. 永田 裕一, 人工知能学会論文誌, 21(2), 2006, 195-204. |
| URI: | http://hdl.handle.net/10119/7827 |
| 資料タイプ: | publisher |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| A7584.pdf | | 694Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
