recentpopularlog in

charlesarthur : travellingsalesman   1

Using self-organizing maps to solve the Traveling Salesman Problem •
Diego Vicente:
<p><img src="https://diego.codes/img/som-tsp-uruguay.gif" width="100%" />
To evaluate the implementation, we will use some instances provided by the aforementioned National Traveling Salesman Problem library. These instances are inspired in real countries and also include the optimal route for most of them, which is a key part of our evaluation. The evaluation strategy consists in running several instances of the problem and study some metrics:

• Execution time invested by the technique to find a solution.<br />• Quality of the solution, measured in function of the optimal route: a route that we say is "10% longer that the optimal route" is exactly 1.1 times the length of the optimal one.

The parameters used in the evaluation are the ones found by parametrization of the technique, by using the ones provided in previous works 2 as a starting point. These parameters are:

• A population size of 8 times the cities in the problem.<br />• An initial learning rate of 0.8, with a discount rate of 0.99997.<br />• An initial neighbourhood of the number of cities, decayed by 0.9997.

These parameters were applied to the following instances:

Qatar, containing 194 cities with an optimal tour of 9352.<br />• Uruguay, containing 734 cities with an optimal tour of 79114.<br />• Finland, containing 10639 cities with an optimal tour of 520527.<br />• Italy, containing 16862 cities with an optimal tour of 557315.</p>


It gets pretty close to the ideal - within 10% on a couple. (Worse on others.) The GIF above is for Uruguay, where it hit 7.5% of the ideal.
maps  algorithms  travellingsalesman 
january 2018 by charlesarthur

Copy this bookmark:





to read