局所的多様性の損失を考慮した評価関数を用いたＧＡのＴＳＰへの適用

DOI 機関リポジトリ Web Site Web Site 被引用文献5件 参考文献24件 オープンアクセス
  • 永田 裕一
    北陸先端科学技術大学院大学 情報科学研究科

書誌事項

タイトル別名
  • New Approach of a Genetic Algorithm for TSP Using the Evaluation Function Considering Local Diversity Loss
  • キョクショテキ タヨウセイ ノ ソンシツ オ コウリョ シタ ヒョウカ カンスウ オ モチイタ GA ノ TSP エ ノ テキヨウ

この論文をさがす

説明

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.

収録刊行物

被引用文献 (5)*注記

もっと見る

参考文献 (24)*注記

もっと見る

キーワード

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

問題の指摘

ページトップへ