書誌事項
- タイトル別名
-
- 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.
収録刊行物
-
- 計測自動制御学会論文集
-
計測自動制御学会論文集 52 (4), 242-248, 2016
公益社団法人 計測自動制御学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282679485961088
-
- NII論文ID
- 130005145125
-
- NII書誌ID
- AN00072392
-
- ISSN
- 18838189
- 04534654
-
- NDL書誌ID
- 027327502
-
- 本文言語コード
- ja
-
- データソース種別
-
- JaLC
- NDL
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可