New Approach of a Genetic Algorithm for TSP Using the Evaluation Function Considering Local Diversity Loss

DOI IR Web Site Web Site 5 Citations 24 References Open Access
  • Nagata Yuichi
    Graduate School of Information Science, Japan Advanced Institute of Science and Technology

Bibliographic Information

Other Title
  • 局所的多様性の損失を考慮した評価関数を用いたＧＡのＴＳＰへの適用
  • キョクショテキ タヨウセイ ノ ソンシツ オ コウリョ シタ ヒョウカ カンスウ オ モチイタ GA ノ TSP エ ノ テキヨウ

Search this article

Description

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.

Journal

Citations (5)*help

See more

References(24)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top