TSPのためのGA-EAXにおける探索ステージ切換条件とマルチスタート戦略の提案

DOI Web Site Web Site 参考文献18件 オープンアクセス

書誌事項

タイトル別名
  • A Switching Condition of Search Stages and a Multi-start Strategy in GA-EAX for TSPs
  • TSP ノ タメ ノ GA-EAX ニ オケル タンサク ステージ キリカエ ジョウケン ト マルチスタート センリャク ノ テイアン

この論文をさがす

説明

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.

収録刊行物

参考文献 (18)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ