A Switching Condition of Search Stages and a Multi-start Strategy in GA-EAX for TSPs

• YAMAKOSHI Kota

  Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology

• NAGATA Yuichi

  Faculty of Engineering, The University of Tokushima

• ONO Isao

  Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology

Bibliographic Information

Other Title

• TSPのためのGA-EAXにおける探索ステージ切換条件とマルチスタート戦略の提案
• TSP ノ タメ ノ GA-EAX ニ オケル タンサク ステージ キリカエ ジョウケン ト マルチスタート センリャク ノ テイアン

Abstract

This paper presents a new genetic algorithm (GA) using the edge assembly crossover (EAX) to remedy a problem of the genetic algorithm with EAX (GA-EAX) for traveling salesman problems (TSPs). GA-EAX is one of the most powerful approximation algorithms. GA-EAX executes two search stages sequentially. The first search stage improves tours locally in the population, preserving a diversity of the population. The second search stage takes the population of the last generation of the first search stage as an initial population and improves tours globally to find better tours than the first stage does. GA-EAX has reportedly succeeded in updating the world records of 100,000-city-scale instances. However, GA-EAX fails to find optimal solutions or known best ones with a high probability on some several-thousand-city-scale instances. In order to overcome the problem of GA-EAX, we propose an improved GA-EAX that employs a new switching condition of the two search stages taking account of a rate of failing to improve tours and a multi-start strategy for the second stage. Through some numerical experiments, we confirmed that the proposed method succeeds in finding the optimal solutions or the known best ones with up to five times higher probabilities than the original GA-EAX. Furthermore, the proposed method succeeds in reducing the number of generations to find the optimal solutions or the known best ones by up to 24.7% in comparison with the original GA-EAX.

Journal

• Transactions of the Society of Instrument and Control Engineers

  Transactions of the Society of Instrument and Control Engineers 52 (4), 242-248, 2016

  The Society of Instrument and Control Engineers

Keywords

• traveling salesman problems
• genetic algorithms
• edge assembly crossover

Details

• CRID: 1390282679485961088
• NII Article ID: 130005145125
• NII Book ID: AN00072392
• DOI: 10.9746/sicetr.52.242
• ISSN: 18838189
• ISSN: 04534654
• NDL BIB ID: 027327502
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I027327502
• Web Site: https://www.jstage.jst.go.jp/article/sicetr/52/4/52_242/_pdf
• Text Lang: ja
• Data Source:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed