The Genetic Algorithm Framework – Part 7

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

Typically the chromosome in a genetic algorithm is created from a binary string. In other words each gene in the chromosome contains a 1 or a 0. However, there are cases where this is inappropriate. The Traveling Salesman problem (TSP) is an example of this as it relies on each gene being an integer in order to determine elements in an externally defined list of cities.

The GAF has always supported genes that represent integers and real numbers, however, from Version 2, a gene can also represent an object. Instead of storing an integer to represent an element of an array as in the TSP, the gene can now store the city itself. In fact each gene could store a list of objects allowing multidimensional chromosomes if so desired. The gene’s type is given by the Gene.GeneType property. This property returns an enumerated value of one of the following C# types. Binary, Integer, Real or Object.

To demonstrate this I have re-coded the Traveling Salesman problem to use an object based Gene. The code is shown below.

A couple of things to note is that the City object has been modified (see Genetic Algorithms in C# – Part 4). 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.

Enjoy!

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 ObjectBasedGene
{
  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 supporting project is available from BitBucket.

using System;

namespace ObjectBasedGene
{
    [Serializable]
    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;
      }

      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;
        }
      }
    }
}

2 thoughts on “The Genetic Algorithm Framework – Part 7

  1. Saeed says:

    Dear John,

    first, Thank you very much for the great job you did and the helpful article.
    I am going to use this package as a part of my PhD project which is a simulation-based optimization in Rhino/Grasshopper for energy efficiency in buildings.
    In Grasshopper I need to get the results in a list (or double), I tried several times to find a way to change the code and put the outputs in a list but it was not successful. (I am an architect and new in these kinds of topics!)
    I would appreciate it if you could give me some clues that how I can do that.
    I do appreciate a lot in advance for your time and consideration.

    Regards,
    Saeed

    • john says:

      By outputs, I presume you mean fittest Chromosome. The Chromosome can be in any form you wish, including a list. In fact it is by default a list of Gene objects. Genes can represent a real number, an integer, a binary digit (bool) or even another list.

      The above example shows the output of the TSP as a list of City objects.

Leave a Reply

Your email address will not be published. Required fields are marked *