局所的な交叉ＥＡＸを用いたＧＡの高速化とＴＳＰへの適用

• 永田 裕一

  北陸先端科学技術大学院大学 情報科学研究科

書誌事項

タイトル別名

• Fast Implementation of Genetic Algorithm by Localized EAX Crossover for the Traveling Salesman Problem
• キョクショテキナ コウサ EAX オ モチイタ GA ノ コウソクカ ト TSP エノ テキヨウ

抄録

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.

収録刊行物

• 人工知能学会論文誌

  人工知能学会論文誌 22 (5), 542-552, 2007

  一般社団法人 人工知能学会

キーワード

• genetic algorithm
• TSP
• EAX
• localized crossover
• population diversity

詳細情報

• CRID: 1390001205108326656
• NII論文ID: 10022008102
• NII書誌ID: AA11579226
• DOI: 10.1527/tjsai.22.542
• ISSN: 13468030
• ISSN: 13460714
• NDL書誌ID: 9604238
• Web Site: http://hdl.handle.net/10119/7826
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I9604238
• Web Site: http://www.jstage.jst.go.jp/article/tjsai/22/5/22_5_542/_pdf
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • IRDB
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可