Clone wiki

GAF / Solving the Travelling Salesman Problem

Solving the Travelling Salesman Problem

Introduction

The Traveling Salesman problem is a well used problem in AI circles. Given a list of cities, a salesman has to identify the most efficient route that visits every city once and only once. Any city can be the starting point.

It is possible to solve this problem using 'brute force', that is, calculating every combination of routes. However, with 16 cities we would have to test 20,922,789,888,000 possible routes. With 20 cities the number of routes increases to 432,902,008,176,640,000. A brute force approach is simply impractical.

Using the GAF to Solve the Problem

To solve this with a GA is reasonably straight forward. For the example here, a console application has been created (shown below). The Genetic Algorithm Framework (GAF) was added to this project using the NuGet command:

PM> Install-Package GAF

Typically the chromosome in a genetic algorithm is created from a binary string. However, there are cases where a simple binary string is not the most straightforward approach. The Traveling Salesman problem (TSP) is an example of this as it relies on the chromosome representing a route and each gene representing a city.

The GAF supports various gene types including integers, real numbers and objects. In this TSP example, the chromosome will store a potential route with each gene being responsible for storing a city object (code shown below).

In this example the chromosome is a special case as it needs to contain each city only once. Therefore, it is not possible just to create random chromosomes (routes) as was the case with the Solving the Binary F6 Function example. It is necessary to create the population manually. This was done in the Main function in this example.

It is necessary to create the population manually. This was done in the Main function in this example.

As mentioned earlier, the chromosome must contain every city. Therefore, it is not possible to use the traditional crossover method. In most cases a traditional single or double point crossover would corrupt the route leaving duplicate cities and others missing.

The GAF supports a form of crossover called 'Double Point Ordered'. This type of crossover creates a child from a single parent. Two parents are selected and two random points along the chromosome are selected. The genes between the points are passed to the child. The remaining genes are transferred from the same parent, but in the order that they appear in the second parent. The result is that the child contains all of the values from a single parent but includes ordering, and therefore traits, from both parents.

Similarly, the Binary Mutate operator used in previous examples is not suitable in this example. We have to maintain the complete set of values within the chromosome. Therefore, the 'Swap Mutate' operator has been used. This operator simply takes two genes at random and swaps their position within the chromosome.

For the fitness delegate, the CalculateFitness function has been created. This function simply calls CalculateDistance in order to calculate the total distance between each city in the order specified by the chromosome. The return value of this function needs to be between 0 and 1 with the better fitness (shorter route) being the higher number. The approach taken here is a little crude but it works well.

The terminate delegate function simply stops the GA when 400 generations have taken place.

A couple of things to note regarding the City object. The Equals method has been overloaded, this is simply to ensure that the Swap Mutate operator functions correctly. If you are not using Swap Mutate then this step could be ignored. For completeness I have implemented GetHashCode also.

Results

Running the GA gave the following results. Most of the work has been done after 154 generations although leaving the GA running showed a very slight improvement in route distance after 368 generations. The shortest distance discovered by the GA was approximately 1629 miles. It is worth noting that this was the result from the first run, no optimisation of the GA was carried out. Adjusting the parent selection method or Crossover/Mutation probability could improve the performance of the GA. I will leave this to you to experiment. Enjoy!

Generation: 10, Fitness: 0.751764339552472, Distance: 2482.35660447528
Generation: 11, Fitness: 0.751764339552472, Distance: 2482.35660447528
Generation: 12, Fitness: 0.776179966270441, Distance: 2238.20033729559
Generation: 16, Fitness: 0.778498506612512, Distance: 2215.01493387488
Generation: 20, Fitness: 0.778792498460299, Distance: 2212.07501539701
Generation: 21, Fitness: 0.779983453246518, Distance: 2200.16546753482
Generation: 22, Fitness: 0.791472961088518, Distance: 2085.27038911482
Generation: 26, Fitness: 0.806022227954872, Distance: 1939.77772045128
Generation: 27, Fitness: 0.806721914946973, Distance: 1932.78085053027
Generation: 28, Fitness: 0.80946570810232, Distance: 1905.3429189768
Generation: 36, Fitness: 0.81391858503094, Distance: 1860.8141496906
Generation: 39, Fitness: 0.820262019460363, Distance: 1797.37980539637
Generation: 46, Fitness: 0.825307565772963, Distance: 1746.92434227037
Generation: 85, Fitness: 0.825532111167778, Distance: 1744.67888832222
Generation: 93, Fitness: 0.832642679433738, Distance: 1673.57320566262
Generation: 154, Fitness: 0.836884868024645, Distance: 1631.15131975355
Generation: 368, Fitness: 0.83710941341946, Distance: 1628.9058658054

The route selected by the GA was as follows.

  1. Canterbury
  2. London
  3. Bristol
  4. Cardiff
  5. Exeter
  6. Falmouth
  7. Swansea
  8. Birmingham
  9. Liverpool
  10. Manchester
  11. Leeds
  12. Hull
  13. Newcastle
  14. Carlisle
  15. Glasgow
  16. Edinburgh

This code and the compiled assembly is available via [Docker and BitBucket]

using System;
using System.Collections.Generic;
using System.Linq;
using GAF;
using GAF.Extensions;
using GAF.Operators;

namespace TravellingSalesman
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            const int populationSize = 100;

            //get our cities
            var cities = CreateCities().ToList();

            //Each city is an object the chromosome is a special case as it needs 
            //to contain each city only once. Therefore, our chromosome will contain 
            //all the cities with no duplicates

            //we can create an empty population as we will be creating the 
            //initial solutions manually.
            var population = new Population();

            //create the chromosomes
            for (var p = 0; p < populationSize; p++)
            {

                var chromosome = new Chromosome();
                foreach (var city in cities)
                {
                    chromosome.Genes.Add(new Gene(city));
                }

                var rnd = GAF.Threading.RandomProvider.GetThreadRandom();
                chromosome.Genes.ShuffleFast(rnd);

                population.Solutions.Add(chromosome);
            }

            //create the elite operator
            var elite = new Elite(5);

            //create the crossover operator
            var crossover = new Crossover(0.8)
            {
                CrossoverType = CrossoverType.DoublePointOrdered
            };

            //create the mutation operator
            var mutate = new SwapMutate(0.02);

            //create the GA
            var ga = new GeneticAlgorithm(population, CalculateFitness);

            //hook up to some useful events
            ga.OnGenerationComplete += ga_OnGenerationComplete;
            ga.OnRunComplete += ga_OnRunComplete;

            //add the operators
            ga.Operators.Add(elite);
            ga.Operators.Add(crossover);
            ga.Operators.Add(mutate);

            //run the GA
            ga.Run(Terminate);

            Console.Read();
        }

        static void ga_OnRunComplete(object sender, GaEventArgs e)
        {
            var fittest = e.Population.GetTop(1)[0];
            foreach (var gene in fittest.Genes)
            {
                Console.WriteLine(((City)gene.ObjectValue).Name);
            }
        }

        private static void ga_OnGenerationComplete(object sender, GaEventArgs e)
        {
            var fittest = e.Population.GetTop(1)[0];
            var distanceToTravel = CalculateDistance(fittest);
            Console.WriteLine("Generation: {0}, Fitness: {1}, Distance: {2}", e.Generation, fittest.Fitness, distanceToTravel);

        }

        private static IEnumerable<City> CreateCities()
        {
            var cities = new List<City>
            {
                new City("Birmingham", 52.486125, -1.890507),
                new City("Bristol", 51.460852, -2.588139),
                new City("London", 51.512161, -0.116215),
                new City("Leeds", 53.803895, -1.549931),
                new City("Manchester", 53.478239, -2.258549),
                new City("Liverpool", 53.409532, -3.000126),
                new City("Hull", 53.751959, -0.335941),
                new City("Newcastle", 54.980766, -1.615849),
                new City("Carlisle", 54.892406, -2.923222),
                new City("Edinburgh", 55.958426, -3.186893),
                new City("Glasgow", 55.862982, -4.263554),
                new City("Cardiff", 51.488224, -3.186893),
                new City("Swansea", 51.624837, -3.94495),
                new City("Exeter", 50.726024, -3.543949),
                new City("Falmouth", 50.152266, -5.065556),
                new City("Canterbury", 51.289406, 1.075802)
            };

            return cities;
        }

        public static double CalculateFitness(Chromosome chromosome)
        {
            var distanceToTravel = CalculateDistance(chromosome);
            return 1 - distanceToTravel / 10000;
        }

        private static double CalculateDistance(Chromosome chromosome)
        {
            var distanceToTravel = 0.0;
            City previousCity = null;

            //run through each city in the order specified in the chromosome
            foreach (var gene in chromosome.Genes)
            {
                var currentCity = (City)gene.ObjectValue;

                if (previousCity != null)
                {
                    var distance = previousCity.GetDistanceFromPosition(currentCity.Latitude,
                                                                        currentCity.Longitude);
                    distanceToTravel += distance;
                 }

                previousCity = currentCity;
            }

            return distanceToTravel;
        }

        public static bool Terminate(Population population, int currentGeneration, long currentEvaluation)
        {
            return currentGeneration > 400;
        }

    }
}

This code and the compiled assembly is avalaible via [Docker and BitBucket].

using System;

namespace TravellingSalesman
{
    public class City
    {
        public City(string name, double latitude, double longitude)
        {
            Name = name;
            Latitude = latitude;
            Longitude = longitude;
        }

        public string Name { set; get; }
        public double Latitude { get; set; }
        public double Longitude { get; set; }

        public double GetDistanceFromPosition(double latitude, double longitude)
        {
            var R = 6371; // radius of the earth in km
            var dLat = DegreesToRadians(latitude - Latitude);
            var dLon = DegreesToRadians(longitude - Longitude);
            var a =
                Math.Sin(dLat / 2) * Math.Sin(dLat / 2) +
                Math.Cos(DegreesToRadians(Latitude)) * Math.Cos(DegreesToRadians(latitude)) *
                Math.Sin(dLon / 2) * Math.Sin(dLon / 2)
                ;
            var c = 2 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1 - a));
            var d = R * c; // distance in km
            return d;
        }

        private static double DegreesToRadians(double deg)
        {
            return deg * (System.Math.PI / 180);
        }

        public override string ToString ()
        {
            return Name;
        }

        public override bool Equals(object obj)
        {
            var item = obj as City;
            return Equals(item);
        }

        protected bool Equals(City other)
        {
            return string.Equals(Name, other.Name) && Latitude.Equals(other.Latitude) && Longitude.Equals(other.Longitude);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                int hashCode = (Name != null ? Name.GetHashCode() : 0);
                hashCode = (hashCode * 397) ^ Latitude.GetHashCode();
                hashCode = (hashCode * 397) ^ Longitude.GetHashCode();
                return hashCode;
            }
        }
    }
}

Updated