The Genetic Algorithm Framework – Part 4

UPDATE: This article has now been updated and integrated into the GAF documentation. The documentation can be found here.

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, I simply created a console application (shown below) and added the Genetic Algorithm Framework (GAF) using the NuGet command:

PM> Install-Package GAF

Each city can be identified by an integer within the range 0-15. (Addendum: Please see the article Object Based Genes which addresses the Traveling Salesman problem using a gene to represent a City rather than an integer referenced element in an external list). The approach taken was to create and store list of 16 cities in a member variable. The chromosome would store a series of numbers in the range 0 to 15. The chromosome would represent a potential route. However, 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 previous examples. 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.

The example listing shown below is available for download from BitBucket.

In addition to the Main function, I created a method to populate the member variable ‘_cities’ and implemented the two events to report progress.

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.

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

Addendum

Please see the article Object Based Genes which addresses the Traveling Salesman problem using a gene to represent a City rather than a referenced element in an external list.

This code and the supporting project is available from 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 List<City> _cities;

  private static void Main(string[] args)
  {
    //get our cities
    _cities = CreateCities().ToList();

    //Each city can be identified by an integer within the range 0-15
    //our chromosome is a special case as it needs to contain each city 
    //only once. Therefore, our chromosome will contain all the integers
    //between 0 and 15 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 < 100; p++)
    {

    var chromosome = new Chromosome();
    for (var g = 0; g < 16; g++)
    {
      chromosome.Genes.Add(new Gene(g));
    }

    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(_cities[(int)gene.RealValue].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 = _cities[(int) gene.RealValue];

    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 supporting project is available from 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 byte[] ToBinaryString()
    {
      var result = new byte[6];
      return result;
    }
  }
}