Slope-to-optimal-solution-based evaluation of the hardness of travelling salesman problem instances

Logic Journal of the IGPL 28 (1):45-57 (2020)
  Copy   BIBTEX

Abstract

The travelling salesman problem is one of the most popular problems in combinatorial optimization. It has been frequently used as a benchmark of the performance of evolutionary algorithms. For this reason, nowadays practitioners request new and more difficult instances of this problem. This leads to investigate how to evaluate the intrinsic difficulty of the instances and how to separate ease and difficult instances. By developing methodologies for separating easy- from difficult-to-solve instances, researchers can fairly test the performance of their combinatorial optimizers. In this work, a methodology for evaluating the difficulty of instances of the travelling salesman problem near the optimal solution is proposed. The question is if the fitness landscape near the optimal solution encodes enough information to separate instances in function of their intrinsic difficulty. This methodology is based on the use of a random walk to explore the closeness of the optimal solution. The optimal solution is modified by altering one connection between two cities at each step, at the same time that the fitness of the altered solution is evaluated. This permits evaluating the slope of the fitness landscape. Later, and using the previous information, the difficulty of the instance is evaluated with random forests and artificial neural networks. In this work, this methodology is confronted with a wide set of instances. As a consequence, a methodology to separate the instances of the travelling salesman problem by their degree of difficulty is proposed and evaluated.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 103,314

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

巡回セールスマン問題における地形構造の解析.橋本 周司 吉澤 大樹 - 2001 - Transactions of the Japanese Society for Artificial Intelligence 16:309-315.
Cas: カニングアントを用いた aco の提案.Tsutsui Shigeyoshi - 2007 - Transactions of the Japanese Society for Artificial Intelligence 22 (1):29-36.

Analytics

Added to PP
2021-02-03

Downloads
13 (#1,365,941)

6 months
4 (#864,415)

Historical graph of downloads
How can I increase my downloads?