-
Notifications
You must be signed in to change notification settings - Fork 3
Solving the Travelling Salesman Problem and Using Ready Made Components
In this tutorial, we'll see how a genetic algorithm can be used to solve the Travelling Salesman Problem. This tutorial will be using ready-made-components - so it will also show how to use those.
In the Travelling Salesman Problem (TSP), we have a list of cities. A salesman must visit each city exactly once. The TSP tries to find the shortest route that will accomplish this. You can find the Wikipedia page here.
For our example we'll use 10 cities. Each city will be marked by a letter between "a" to "j". A chromosome is a list of 10 cities. The chromosome defines a route by visiting each city in the order it appears. For instance, the chromosome "abcdefghij" would define the route: a -> b -> c -> d -> e -> f -> g -> h -> i -> j. Since the salesman must visit each city exactly once, for a chromosome to be a legal route, it must contain each city exactly once.
Let's start by creating a class that will calculate the distance traveled for a chromosome (route). The class will receive a dictionary with the coordinates of each city, and it will use the Math.Sqrt(Math.Pow(X1 - X2, 2) + Math.Pow(Y1 - Y2, 2)) equation to calculate the distance.
class DistanceCalclator
{
private readonly IDictionary<string, Tuple<int, int>> locations;
public DistanceCalclator(IDictionary<string, Tuple<int, int>> locations)
{
this.locations = locations;
}
public double GetDistance(IChromosome chromosome)
{
var totalDistance = 0.0;
var cityVector = ((VectorChromosome<string>)chromosome).GetVector();
for (int i = 0; i < cityVector.Length - 1; i++)
totalDistance += GetDistance(cityVector[i], cityVector[i + 1]);
return totalDistance;
}
private double GetDistance(string city1, string city2) =>
Math.Sqrt(Math.Pow(locations[city1].Item1 - locations[city2].Item1, 2) + Math.Pow(locations[city1].Item2 - locations[city2].Item2, 2));
}Let's use our DistanceCalclator to implement the IEvaluator class. One thing to note here is that a chromosome with a short route should give a high evaluation. This is why we subtract the route length from a number that is greater than the longest possible path to create the evaluation.
class DistanceEvaluator : IEvaluator
{
private readonly DistanceCalclator distanceCalclator;
private readonly double maxDistance;
public DistanceEvaluator(IDictionary<string, Tuple<int, int>> locations)
{
distanceCalclator = new DistanceCalclator(locations);
maxDistance = 1500 * locations.Count;
}
// Note that a shorter route should give a better evaluation
public double Evaluate(IChromosome chromosome) =>
maxDistance - distanceCalclator.GetDistance(chromosome);
}For a mutation manager, we'll use the ready-made ExchangeMutationManager<T>. This mutation manager swaps two genomes in the chromosome. This will ensure that after the mutation the chromosome still contains each city exactly once.
IMutationManager<string> mutationManager = new ExchangeMutationManager<string>();For our ICrossoverManager, we'll again use a ready-made component. We need a manager that will ensure that the children will contain each genome (city) exactly once. There are a number of ready-made crossover manages that met this constraint. For our example we'll use the OrderCrossover<string>. You can read about how it works here.
ICrossoverManager crossoverManager = new OrderCrossover<string>(mutationManager, evaluator);We need each chromosome to contain each city exactly once. For that, we can use the read-made AllElementsVectorChromosomePopulationGenerator<T>. This PopulationGenerator receives a collection in its constructor, and creates chromosomes that each contain every element from the collection exactly once.
string[] cities = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"};
IPopulationGenerator populationGenerator =
new AllElementsVectorChromosomePopulationGenerator<string>(cities, mutationManager, evaluator);Let's put everything together and run an actual search.
class Program
{
private const int POPULATION_SIZE = 100;
private const int GENERATIONS = 100;
private static string[] cities = {"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"};
private static Dictionary<string, Tuple<int, int>> locations = new Dictionary<string, Tuple<int, int>>
{
{"a", new Tuple<int, int>(10, 10)},
{"b", new Tuple<int, int>(10, 200)},
{"c", new Tuple<int, int>(1000, 10)},
{"d", new Tuple<int, int>(500, 476)},
{"e", new Tuple<int, int>(200, 800)},
{"f", new Tuple<int, int>(80, 199)},
{"g", new Tuple<int, int>(455, 78)},
{"h", new Tuple<int, int>(511, 907)},
{"i", new Tuple<int, int>(230, 400)},
{"j", new Tuple<int, int>(611, 801)},
};
private static DistanceCalclator distanceCalclator = new DistanceCalclator(locations);
static void Main(string[] args)
{
Console.WriteLine("Started!");
IMutationManager<string> mutationManager = new ExchangeMutationManager<string>();
IEvaluator evaluator = new DistanceEvaluator(locations);
ICrossoverManager crossoverManager = new OrderCrossover<string>(mutationManager, evaluator);
IPopulationGenerator populationGenerator =
new AllElementsVectorChromosomePopulationGenerator<string>(cities, mutationManager, evaluator);
GeneticSearchEngine engine =
new GeneticSearchEngineBuilder(POPULATION_SIZE, GENERATIONS, crossoverManager, populationGenerator)
.SetMutationProbability(0.1).SetElitePercentage(0.02).Build();
engine.OnNewGeneration += (Population p, IEnvironment e) => PrintBestChromosome(p);
GeneticSearchResult result = engine.Run();
Console.WriteLine("Finished!");
Console.WriteLine(result.BestChromosome + ": " + distanceCalclator.GetDistance(result.BestChromosome));
Console.ReadLine();
}
private static void PrintBestChromosome(Population population)
{
var bestEvaluation = 0.0;
ChromosomeEvaluationPair bestPair = null;
foreach (ChromosomeEvaluationPair chromosomeEvaluationPair in population)
if (chromosomeEvaluationPair.Evaluation > bestEvaluation)
{
bestEvaluation = chromosomeEvaluationPair.Evaluation;
bestPair = chromosomeEvaluationPair;
}
Console.WriteLine(bestPair.Chromosome + ": " + distanceCalclator.GetDistance(bestPair.Chromosome));
}
}