Difference between revisions of "TSP Example"

From jecoliwiki
Jump to: navigation, search
(Created page with "The '''Traveling Salesman Problem (TSP)''' is a classical problem in optimization, being used often as a way to test new approaches. ==== Problem Definition ==== The TSP can...")
 

Latest revision as of 16:00, 5 March 2013

The Traveling Salesman Problem (TSP) is a classical problem in optimization, being used often as a way to test new approaches.

[edit] Problem Definition

The TSP can be defined as: given a set of cities and the cost to travel between each pair, the aim is to find the way to visit all of the cities once and returning to your starting point, that minimizes the sum of the costs. The problem can be generalized to a graph where cities are the nodes and the costs represent the weights of the edges.

More information: see for instance [1]

[edit] Resolution

The Traveling Salesman Problem (TSP) is addressed using Evolutionary Algorithms (EAs) with permutation representations.

The implementation of this problem can be found in the package test/tsp, that contains two sub-packages:

  • libtsp - with all the code concerning the TSP related data and methods, supporting several types of TSP problems

(e.g. euclidian, geometrical, symmetrical and asymmetrical).

  • eatsp - including all the classes related to the application of EAs to solve the TSP.


Regarding this last sub-package the following classes are included:

  • TspEvaluationFunction - defines the fitness for the TSP, calculating the cost of a given solution (permutation)

(for more details see the how to: creating an evaluation function.

  • EATsp - allows to configure and run an EA to solve the TSP using permutation representations. any of the several reproduction operators defined for this case can be used. This class also allows to do several runs of an algorithm keeping the results in a location defined by the user, allowing the easy benchmarking of several alternatives (e.g. reproduction or selection operators).
  • TspGreedyCrossover - defines a crossover operator specific for the TSP; this can be used in the EATsp class along with the other general purpose permutation operators.
  • TwoOptLocalOptimizationOperator - defines a local optimization operator for the TSP; this can be used as a reproduction operator in the EATsp class along with the other general purpose permutation operators.
Personal tools