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

The Genetic Algorithm Framework – Part 6

Introduction

The following article describes an approach that develops the Genetic Algorithm design in stages by developing a GA to solve the Binary F6 function. Once the GA has been developed using the Binary F6 it can then be applied and further developed within the problem domain, thereby allowing for more domain specific needs. This approach was discussed in Davis (1991), see references below.

The developing and testing process involves creating a simple GA and improving this by the development of new and enhanced GA features. Seven GAs are developed (GA-A to GA-G) for use with the Binary F6 function. Each algorithm is summarised below. The graph shows the relative performance of GA-A to GA-D with respect to the number of evaluations. These four GAs represent the development from a simple generation replacement algorithm to an elitist approach with duplicate handling. GA-E to GA-G are steady state (Davis, 1991) algorithms. These are discussed separately.

Binary F6

The image shows a plot of the Binary F6 function (Shaffer, et. al., 1989), with an input range between -100 to +100. It has many local minima and is ideal for testing a GA. The basic code for solving the Binary F6 is shown at the bottom of the article.

Binary F6 3D Plot

Fitness and Terminate Functions

Before we get started creating the GA examples we need to create some suitable Fitness and Terminate functions. It is not necessary to understand these functions, we can simply make use of them. they can be found in the basic GA code at the bottom of the page.

GA Types Under Test

GA Type Operators Description
A Generational Replacement Crossover (0.65)
Mutation (0.008)
Starting point for the GA development process.
B Generational Replacement Crossover (0.65)
Mutation (0.008)
Same as A except that the Linear Normalisation was applied.
C Elitist Crossover (0.65)
Mutation (0.008)
Same as B except that an Elitist approach was adopted (5%).
D Elitist without duplicates Crossover (0.65)
Mutation (0.008)
Same as C except that duplicates were prevented from entering the population.
E Steady State Crossover (0.65)
Mutation (0.008)
Steady State where only two children were added to the population at each generation.
F Steady State without duplicates Crossover (0.65)
Mutation (0.008)
Same as E except that duplicates were prevented from entering the population.
G Steady State without duplicates Crossover (0.8)
Mutation (0.04)
Same as F except that the crossover and mutation parameters were modified.

Performance of GA A - D
Performance of GA E-G

Generational Replacement (GA-A)

The first algorithm, GA-A, is the simplest of the algorithm designs tested in this research. It uses the Single Point Crossover and Binary Mutation genetic operators. Each generation is subjected to the genetic operators to create a new generation. This new generation replaces the current generation. The Roulette Wheel parent selection method was chosen for these algorithms. Roulette Wheel parent selection provides a means by which the probability of a solution being selected as a parent, is related to the fitness value of that solution. Therefore, the fitter an individual is, the more likely they will be selected as a parent.

The advantage of this type of algorithm is that it is simple to implement. However, the disadvantage is that as each generation is replaced, any extremely fit individuals from one generation may not pass through to the next generation without being modified. Although probability factor is used to determine to what degree the operators are applied, there is no mechanism to protect the best individuals within the population.

Linear Normalisation (GA-B)

GA-B is similar to GA-A except it introduces linear normalisation. Linear normalisation, as implemented within the GAF, simply orders the solutions by decreasing evaluation, and creates a fitness based on this ordering. For example for a population of 100, the fittest would be 1.0 and each subsequent solution would decrease linearly in value down to the worst solution with a fitness of 0. The starting point and decrement parameters of this approach are fixed within the GAF.

To add linear normalisation, simply change the useLinearlyNormalisedFitness parameter to true in the constructor of the Population object.

Linearly normalising fitness in this way helps maintain natural selection. Natural selection occurs when the fittest individuals are selected, as parents for the next generation, proportionally to their fitness. However, in some problem domains, where the difference between the fitness value of the fittest and others within the solution is very small, each has a similar probability of being selected as a parent. By normalising the fitness of the population between a minimum and maximum value natural selection can be improved.

Elitism (GA-C)

GA-C expands upon GA-A and GA-B in that it introduces Elitism. Elitism allows the best solutions to pass through to the next generation without being modified. GA-C used a percentage value, 5%, which, with a population of 100, means that the top 5 individuals form part of the next generation. This means that any future generation is at least as good as the current generation.

GA-C helps protect good individuals. However, it can be shown that as the percentage of Elites is increased, the number of duplicates within the population increases. This is normal behaviour for an approach that does not explicitly handle duplicates and is simply due to the convergence of the algorithm (Davis, 1991). However, the GAF uses a globally unique identifier (GUID) for each chromosome, the GUID can be used to trace the origin of the chromosome and in this case highlights a different phenomenon to that of convergence. The following output represents the first 16 chromosomes from a run using GA-C. It can be seen that there are many cases of the same chromosome existing more than once. For example chromosomes 1 and 2 are the same solution but are derived from different chromosomes as the GUID is different, this is due to convergance. However, chromosomes 3 and 9 are the same chromosome, these have been duplicated due to the combination of Elitism and crossover probability settings.

GUID Chromosome
1 ccd5ba05-f0a6-43c9-a8b8-78f206dd6341 01111110010000110001010111110001100000110011
2 d16cfab2-797f-4821-a967-ee441a9ea33a 01111110010000110001010111110001100000110011
3 41b88bd6-c872-4c8e-ae0b-2944fa421fdc 01111110010000110001010111110001100000110011
4 bf9bbb00-da6d-40e9-9acd-ad1eb5df7d8d 01111110010000110001010111110001100000110011
5 4c9bc696-824f-471b-ad36-1584dfdcddee 01111110010000110001010111110001100000110011
6 227ec944-b8d7-4020-a046-a9f49293d9c8 01111110010000110001010111110001100000110011
7 948ba7b9-964f-46f6-8704-7c05786acffe 01111110010000110001010111110001100000110011
8 7b390c2c-9ab4-4ef8-bbe0-fa0b5992fb09 01111110010000110001010111110001100000110011
9 41b88bd6-c872-4c8e-ae0b-2944fa421fdc 01110110010000110001010111110001100000110011
10 bf9bbb00-da6d-40e9-9acd-ad1eb5df7d8d 01111110010000010001010111110001000000110011
11 4c9bc696-824f-471b-ad36-1584dfdcddee 01111110010000110001010111100001100000110001
12 227ec944-b8d7-4020-a046-a9f49293d9c8 01111110010000110001110111110001100000110011
13 948ba7b9-964f-46f6-8704-7c05786acffe 01111110010000110001010111111001110000110011
14 1d24c8d6-b6c7-4b6c-bb17-f9da544499f4 01111110010000010000010111010001100010111011
15 7b390c2c-9ab4-4ef8-bbe0-fa0b5992fb09 11111110010000100001010111110001110000110011

Further investigation shows that duplicates can occur due to the combination of both the Elite and Crossover genetic operators. The Elite implementation simply takes the top percentage of solutions based on fitness and adds them to the next generation’s population without modification. The remaining solutions were generated from parents selected using the Roulette Selection. Roulette selection favours the selection of the better solutions as parents, therefore in many cases the parents selected were those already identified as Elite. In cases where the probability of crossover was not satisfied, the selected parents were allowed to pass into the next generation’s population without modification. This process allows Elites to be added to the next generation’s population more than once.

Duplicate Handling (GA-D)

Modifying GA-C to prevent duplicates from being added to the population is simply a case of changing the constructor parameter for the appropriate operators.

Steady State Algorithm (GA-E)

The algorithm GA-E has been described as a Steady State Genetic Algorithms (Davis, 1991). This type of algorithm is designed to maintain a population through each generation, changing only one or two children where the children are considered to be fitter than the worst of those in the population. This approach has shown itself to be better when combined with techniques to prevent duplicates being added to the population. However, in the experiments carried out during this project, this could not be determined.

Steady State Algorithm without Duplicates (GA-F)

GA-F is the same as GA-E but with duplicates prevented from entering the population. Modifying GA-E to prevent duplicates from being added to the population is simply a case of changing the constructor parameter for the appropriate operators.

Steady State Algorithm without Duplicates (GA-G)

In the Steady State configuration, only a few children being added at each generation, therefore the majority of the population is protected from crossover and mutation, this means that the crossover and mutation probability values can be safely increased. GA-G is the same as GA-F except that the crossover and mutation probability settings are significantly increased. The results show the performance of these algorithms when used with the Binary F6 function.

Noisy Environments

The Binary F6 evaluation is not noisy, that is, the fitness value would not change if the solution were to be re-evaluated. In situations such as these, the evaluation process can be optimised not to re-evaluate each solution at each generation. The GAF handles this type of optimisation internally, as a result it can be shown that by adding only two children at each generation, there are only two evaluations at each generation. Naturally there are many more generations than the other algorithms described.

The disadvantage of this approach is that when using this GA with noisy evaluations, for example where a re-evaluation of a solution would return a different result from the previous evaluation, the optimisation described above, cannot be applied. The result is that each generation needs to be fully evaluated. Due to the large number of generations involved, this reduces the performance compared to algorithms GA-A to GA-D, described above.

For noisy environments each solution should be evaluated at each generation. This can be achieved by setting the reEvalutaeAll parameter in the constructor of the Population object.

  1. Davis, L. (1991) Handbook of Genetic Algorithms. New York: Van Nostrand Rienhold
  2. J. D. Schaffer, R. A. Caruana, L. J. Eshelman, and R. Das (1989) A study of control parameters affecting online performance of genetic algorithms for function optimization. In Davis, L. (1991) Handbook of Genetic Algorithms. New York: Van Nostrand Rienhold

This code and the supporting project is available from BitBucket.

using System;
using GAF;
using GAF.Operators;
        
namespace BinaryF6
{
  internal class Program
  {
    private static void Main(string[] args)
    {
      const double crossoverProbability = 0.85;
      const double mutationProbability = 0.08;
      const int elitismPercentage = 5;

      //create a Population of 100 random chromosomes of length 44
      var population = new Population(100, 44, false, false);

      //create the genetic operators 
      var elite = new Elite(elitismPercentage);

      var crossover = new Crossover(crossoverProbability, true)
      {
        CrossoverType = CrossoverType.SinglePoint
      };

      var mutation = new BinaryMutate(mutationProbability, true);

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

      //subscribe to the GAs Generation Complete event 
      ga.OnGenerationComplete += ga_OnGenerationComplete;

      //add the operators to the ga process pipeline 
      ga.Operators.Add(elite);
      ga.Operators.Add(crossover);
      ga.Operators.Add(mutation);

      //run the GA 
      ga.Run(TerminateAlgorithm);
    }

    public static double EvaluateFitness(Chromosome chromosome) 
    {
      double fitnessValue = -1;
      if (chromosome != null)
      {
        //this is a range constant that is used to keep the x/y range between -100 and +100
        var rangeConst = 200 / (System.Math.Pow(2, chromosome.Count / 2) - 1);

        //get x and y from the solution
        var x1 = Convert.ToInt32(chromosome.ToBinaryString(0, chromosome.Count / 2), 2);
        var y1 = Convert.ToInt32(chromosome.ToBinaryString(chromosome.Count / 2, chromosome.Count / 2), 2);

        //Adjust range to -100 to +100
        var x = (x1 * rangeConst) - 100;
        var y = (y1 * rangeConst) - 100;

        //using binary F6 for fitness.
        var temp1 = System.Math.Sin(System.Math.Sqrt(x * x + y * y));
        var temp2 = 1 + 0.001 * (x * x + y * y);
        var result = 0.5 + (temp1 * temp1 - 0.5) / (temp2 * temp2);

        fitnessValue = 1 - result;
      }
      else
      {
        //chromosome is null
        throw new ArgumentNullException("chromosome", "The specified Chromosome is null.");
      }

      return fitnessValue;
    }

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

    private static void ga_OnGenerationComplete(object sender, GaEventArgs e)
    {

      //get the best solution 
      var chromosome = e.Population.GetTop(1)[0];

      //decode chromosome

      //get x and y from the solution 
      var x1 = Convert.ToInt32(chromosome.ToBinaryString(0, chromosome.Count/2), 2);
      var y1 = Convert.ToInt32(chromosome.ToBinaryString(chromosome.Count/2, chromosome.Count/2), 2);

      //Adjust range to -100 to +100 
      var rangeConst = 200 / (System.Math.Pow(2, chromosome.Count / 2) - 1);
      var x = (x1 * rangeConst) - 100;
      var y = (y1*rangeConst) - 100;

      //display the X, Y and fitness of the best chromosome in this generation 
      Console.WriteLine("x:{0} y:{1} Fitness{2}", x, y, e.Population.MaximumFitness);
    }
  }
}

Using a GA in Intelligent Software Defined Radio

Introduction

A piece of research completed in conjunction with the De Montfort University in 2013 demonstrated how the Genetic Algorithm Framework (GAF) could be used with a Software Defined Radio (SDR) system, to provide automatic frequency control (AFC).

The aim of AFC is to ensure that a radio system stays tuned to the desired frequency in conditions where the frequency is subject to change. The research demonstrated that a genetic algorithm (GA) can perform this task. In addition, the research showed how the GA can also handle very large changes in frequency such as the doppler shift that can be experienced with satellite communications, and the channel hopping nature of Cognitive Radio systems.

The research report can be found here.. A summary of the activity is described below.

Software Defined Radio

Software Defined Radio (SDR) is a radio system that uses software in place of components that were traditionally implemented in hardware. With the increase in power of computer systems and digital electronics, it is now possible to present a large amount of the radio spectrum to computer software for processing. This processing effectively replaces traditional radio receiver hardware technologies.

SDR Radio Controller

Implementation

The basic aim is for the GA to find the desired signal within the frequency spectrum, tune the radio system to that signal and then remain ‘locked’ to that signal irrespective of any frequency changes large or small.

Within the research, the signal being tuned was a 620Hz bandwidth Radio Teletype (RTTY) transmission from the German Meteorological service known as DDK.

A wide bandwidth radio frequency signal was passed from an RFSpace SDR IQ radio receiver to the computer for tuning, filtering and demodulation by SDR Sharp software (SDR#). In order to provide the deeper integration required to utilise a GA for radio control, software, referred to as the ’GA Controller’, was developed and incorporated into the radio system. The GA Controller is responsible for integrating the SDR# software with the GAF.

The GA Controller was developed as a ’Plug In’ to the open source SDR# software and utilises the Genetic Algorithm Framework (GAF) to provide the GA based control.

Scope and Diversity Plots

The GA Controller includes a small Graphical User Interface (shown here) that allows the properties of the Genetic Operators of the GAF to be changed. With the genetic operators supplied in the GAF having thread safe parameters, the GUI can be used to change the operator parameters whilst the GA is running. This dynamic control of the GA was monitored using the GAF events to identify such things as general accuracy, error rate and diversity. Being able to monitor the error rate and diversity graphically, proved to be an extremely useful facility in determining the configuration for the GA and the respective operators.

Running the GA Framework on a Raspberry Pi using Mono.

It’s hard to ignore Mono these days, and like many I have played around with it using Xamarin Developer. However, my excitement grew when I noticed that Mono now supports the Hardware Floating Point of the Raspberry Pi, meaning that I can now write/re-use C# code on my collection of Raspberry Pis running Rasbian.

Assuming Debian/Raspian, the following command adds the latest version of Mono to the Pi.

$ sudo apt_get install mono-complete

Once this has completed the following command will confirm the installation.

$ mono --version
Mono JIT compiler version 3.2.8 (Debian 3.2.8+dfsg-4+rpi1)
Copyright (C) 2002-2014 Novell, Inc, Xamarin Inc and Contributors. www.mono-project.com
        TLS:           __thread
        SIGSEGV:       normal
        Notifications: epoll
        Architecture:  armel,vfp+hard
        Disabled:      none
        Misc:          softdebug
        LLVM:          supported, not enabled.
        GC:            sgen

To test the mono installation I simply copied the Visual Studio 2013 compiled binaries (TravelingSalesman.exe and GAF.dll) from the Traveling Salesman example project to the Raspberry Pi. Using the SCP command using the Mac Terminal program. I simply navigate to the bin folder where the binaries live and execute the scp command to copy the files over. I used the Mac Terminal program, but any SSH client should work.

$ scp *.exe pi@10.0.1.66:mono
$ scp *.dll pi@10.0.1.66:mono

Once the copy is complete, all that is required is to run the exe on the Raspberry Pi e.g.

$ mono TravellingSalesman.exe

The results are sown below.

GAF on Raspberry Pi 2

To see a .Net managed library, compiled for Windows, running perfectly on a Raspberry Pi is awesome.

Converting Latitude and Longitude to British National Grid in C#

Introduction

This article aims to demystify the concepts of transforming from one coordinate system to another. The article will walk through some C# examples, including how to convert from GPS coordinates to British National Grid and back again. The freely available GeoUK NuGet package is used for these examples. GeoUK was built as a Portable Class Library project (Profile 78) and as such can be added to Visual Studio or Xamarin and runs against .Net 4.5+, Windows Phone 8+, Xamarin.IOS/Android, Windows 8 Store Apps and so on. The product is licensed under the GNU Lesser General Public License (LGPL).

One thing I should mention is that this article is an greatly simplified discussion of a complex topic. Ordnance Survey provide detailed documentation in relation to coordinate systems used in the UK.

Latitude and Longitude

The earth is almost spherical. If you took a inflated beach ball, placed your foot on it and gently pressed, you would have a squashed sphere, referred to as an ellipsoid. The earth is ellipsoidal, albeit with a few lumps and bumps.

The Latitude and Longitude coordinate system can describe any point on earth, however, it can only do that if we have first defined the details of the earth such as the origins of the Latitude and Longitude system and the size and shape of the ellipsoid to be used. These definitions are referred to as a Datum. The thing is, different ellipsoids, and therefore different datums, are often used depending upon where in the world you are. In some cases several datums can be in use at the same location depending upon specific requirements. This means that Latitude and Longitude can only describe a point on the earth if we know which datum is being used. It can be shown that if a Latitude and Longitude based on the OSGB36 datum were entered into a GPS using a WGS84 datum, it would point to a different place. Therefore, being able to transform coordinates to and from different datums is essential, the examples shown later in the article will show how to do this in C# using the GeoUK package.

Why so Many Datums

Bumpy Earth

Before moving on to discuss coordinate systems it is worth explaining why we use different ellipsoids, and therefore different datums. WGS84 is a standard datum used as the default in most GPS systems, so why not simply use that? The figure below shows a rough image of the earth with all of its lumps and bumps. The large ellipsoid whilst not fitting perfectly gives us a general ellipsoid that can be used all over the world, think of this as WGS84. However, the smaller ellipsoid can be seen to be a better fit for a small part of the earth. Therefore, if you happen to be on this small part of the earth, using this smaller ellipsoid would give greater accuracy. Hence, multiple ellipsoids and the need to convert between them. If you are in the UK, this smaller ellipsoid would be the Airy Ellipsoid, part of the OSGB36 datum. The ellipsoid was originally defined by Sir George Airy in 1830.

Something else to consider is that the WGS84 position of any particular point on the Earth’s surface is changing continuously due to various effects, the most important of which is tectonic motion. So WGS84 itself is unsuitable for mapping as the ground would keep sliding across the surface of any WGS84 based mapping grid. This is not the case with a system that covers a small region as the mapping grid can move also. As a result there are datums, in various parts of the world, that were based on the WGS84 datum at one point in time (Epoch), but have diverged from it slightly in order to account for land mass movement. One such datum in Europe is called ETRS89. More of that later.

Different Coordinate Systems

The Latitude and Longitude system is probably the most well known coordinate system. However, here in the UK, Ordnance Survey maps often use Eastings and Northings (Map References) as a coordinate system. Cartesian coordinates (X, Y and Z) can also be very useful. It is not the intention to describe Cartesian coordinates here, however, the code detailed below will use them in intermediate steps.

It is important to understand that converting between coordinates occurs within the same datum. Converting an OSGB36 Easting and Northing to Latitude and Longitude, returns a Latitude and Longitude based on the same OSGB36 datum. To convert these coordinates to Latitude and Longitude for a GPS using WGS84, a datum transformation is also required. The examples shown below will show how to do this in C# using the GeoUK package.

Map showing Easting and Northing Coordinates

There is no accurate method for transforming datums, however, the Helmert transformation can be used as long as the accuracy required is not less than 5 metres. For centimetre accuracy, an altogether different approach needs to be taken. This is described in the section Obtaining Greater Accuracy.

Map Projections

Before we get into the actual code it would be worth quickly discussing Projections.

A projection can be thought of any function that transfers points on an ellipsoid onto a plane surface such as a Map. For our purposes we can consider this to mean converting a Latitude and Longitude to an Easting and Northing. What this means is that any conversion to or from Easting/Northing coordinates, needs a Projection specifying.

Getting Started

The GeoUK package is a PCL78 assembly and can be used with .Net and Mono. Add the package to Xamarin or Visual Studio using the NuGet Package Manager prompt.

> Install-Package GeoUK

The first example takes an Ordnance Survey map Easting/Northing and transforms it to a GPS (WGS84) Latitude and Longitude. Therefore, a coordinate conversion is required (Easting/Northing to Latitude/Longitude) and a datum transformation is also required (OSGB36 to WGS84). As previously mentioned the ETRS89 datum is the European version of WGS84. In 1989 these datums were aligned, since then they have diverged very slightly, however, for our purposes we can consider them to be the same.

First the coordinate conversion. The Easting/Northing is from an Ordnance Survey map and is therefore using the OSGB36 datum with the Airy ellipsoid and the British National Grid projection (BNG).

Step 1: Convert to Cartesian.

using GeoUK;
using GeoUK.Projections;
using GeoUK.Coordinates;
using GeoUK.Ellipsoids;
...

// Given an easting and northing in metres (see text)
const double easting = 651409.903;
const double northing = 313177.270;

// Convert to Cartesian
var cartesian = Convert.ToCartesian (new Airy1830 (),
    new BritishNationalGrid (),
    new EastingNorthing (
        easting, 
        northing));

These new Cartesian coordinates are still with reference to the OSGB datum. Once we have the coordinates as Cartesian, we can make the transformation to ETRS89 (WGS84).

Step 2: Transform from OSBB36 datum to ETRS89 datum (see article text).

var wgsCartesian = Transform.OSBB36ToEtrs89 (cartesian); //ETRS89 is effectively WGS84   

Now we have Cartesian results referencing the WGS84 datum (using the WGS84 ellipsoid) and can simply convert those to Latitude/Longitude.

Step 3: Convert back to Latitude/Longitude.

var wgsLatLong = Convert.ToLatitudeLongitude (new Wgs84 (), 
                                            wgsCartesian);

To summarise, for a datum change of Easting Northing coordinates from datum A to datum B, first convert to Cartesian coordinates using the ellipsoid of datum A. Then apply a transformation from datum A to datum B before converting back to latitude/longitude using the ellipsoid of datum B. The same process is used going the other way.

British National Grid Example

Transformation

The code below transforms from WGS84/ETRS89 Latitude/Longitude to OSGB36 Easting/Northing in the manner described above.

var latLong = new LatitudeLongitude(52.6579785974266, 1.71605194571289);

var cartesian = Convert.ToCartesian (new Wgs84 (), latLong);
var bngCartesian = Transform.Etrs89ToOsgb36 (cartesian);
var bngEN = Convert.ToEastingNorthing (new Airy1830 (), new BritishNationalGrid (), bngCartesian);

OS Map References

The map references (Easting/Northing) used in Ordnance Survey maps are divided into 500km squares which are sub-divided into 100km squares. These squares are given a two letter code. The first letter represents the 500km square and the second represents the 100km square within it. A six digit map reference would look something like TL123456 where the first two characters represents the 100km square as indicated on the map with the first three digits of the six representing the easting and the last three digits representing the northing. Using this system means that a map reference is quoted as an easting/northing (in metres) from the square’s origin. An EastingNorthing coordinate object, as returned from the transformation described above, can be converted to an OS map reference by using the Osgb36 class as follows.

// Convert to Osgb36 coordinates by creating a new object passing  
// in the EastingNorthing object to the constructor.
var osgb36EN = new Osgb36(bngEN);
var mapReference = osgb36EN.MapReference;

Height

Height is a complex topic and there are many ways to measure it. The term ‘sea level’ is often used in conversation but the sea changes all of the time, large land mass has an effect on gravity and this affects the sea. Consider also that some of the earths highest mountains can be found under the sea. As I said it all gets very tricky very quickly.

As we have seen above, we use an ellipsoid to represent the earth in our conversions, this means that height when represented within the LatitudeLongitude coordinates object is usually ellipsoid height. Ellipsoid height is not very useful as point A can have a greater ellipsoid height than point B while being downhill of B. This is due to the fact that an ellipsoid is not a level surface as it does not take account of the irregularities that exist with the earths surface.

Image showing Geoid model compared to the ellipsoid.

A level surface is a surface that is at right angles to gravity at all points. This means that it must take account of the various bumps and lumps that affect gravity. A Geoid is a level surface and can be useful to measure height. A height measured in this way is called an Orthometric Height. A Geoid can be global (usually stated with a capital ‘G’) or can be local to a country or region (usually stated with a lower case ‘g’).

Ordnance Survey mapping on the British mainland uses the Ordnance Datum Newlyn (ODN) vertical coordinate system. ODN corresponds to the average sea level measured by the tide-gauge at Newlyn, Cornwall between 1915 and 1921. Heights that refer to this particular ‘mean sea level’ as the point of zero height are called ODN heights. ODN is therefore a local geoid definition as mentioned above. ODN heights are used for all British mainland Ordnance Survey contours, spot heights and bench mark heights. Many islands around Britain have their own ‘mean sea level’ (local geoid) based on local tide-gauges.

In terms of the examples detailed here relating to the transformation from WGS84 to OSGB36, the WGS ellipsoid height is converted to something like ODN heights, accuracy is around 5 meters in all directions.

Obtaining Greater Accuracy

In order to obtain greater accuracy when transforming ETRS89 (WGS84) coordinates to British National Grid, the Ordnance Survey Geoid Model (OSGM02) needs to be used. The OSGM02 can be thought of as a large rubber sheet covering Great Britain, Northern Island and the Republic of Ireland. Special transformations are applied to the data within the OSGM02 to transform from ETRS89 and OSGB36. For Great Britain the transformation is called OSTN02. The OSTN02 transformations combined with the ETRS89 positions of active GPS network stations represents the official definition of OSGB36 and can give very accurate transformations.

This rubber sheet geoid is effectively a lookup table that can be used to determine Othometric (geoid) heights and, via the OSTN transformation, accurate Easting and Northing coordinates. It is worth noting that Northern Island and the Republic of Ireland use the same geoid model but with a different transformation (OSi/OSNI) which, for now at least, is outside of the scope of this article.

The GeoUK.OSTN Nuget package extends the GeoUK package to include OSGM02/OSTN02 functionality and provides a simple method to make an accurate one-way transformation from ETRS89 to BNG. The package can be added to a project using the following Package Manager command. The package is dependent upon the GeoUK package and will add it as required.

> Install-Package GeoUK.OSTN

It should be noted that the GeoUK.OSTN package contains the OSGM02 geoid and OSTN02 transformation, as a result is fairly large at 38Mb. In addition, transformations will be slower than using the Helmert transformations as in the examples above.

The example below converts an ETRS89 Latitude/Longitude/Ellipsoid height to BNG Easting and Northing and ODN Height to within 10 centimetres or so.

var latLong = new LatitudeLongitude(52.658007833, 1.716073973, 108.05);
var bng = GeoUK.OSTN.Transform.Etrs89ToOsgb (latLong);  

Summary

This article discussed the various elements to be considered when converting from GPS coordinates to British National Grid. The Helmert transformation was demonstrated with an accuracy of around 5 meters in all directions and a more accurate method, that followed the Ordnance Survey recommended approach by using the OSGM02 geoid model, was also shown.

The library is provided free of charge via NuGet with the primary aim of simplifying an otherwise complex problem. If you wish to use the library for a commercial project and require technical support or advice, please feel free to get in touch.

Source code is available here https://bitbucket.org/johnnewcombe/geouk/src

Enjoy!

The Genetic Algorithm Framework – Part 5

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

Introduction

There are two methods for producing a custom Genetic Operator for use with the GAF (Genetic Algorithm Framework for .Net 4.0). The first is the simplest and involves creating a C# class that implements the GAF.IGeneticOperator interface. The second method is to derive a new Genetic Operator from an existing one. This post will take a brief look at the first method before creating an ‘Auto-Mutate’ Genetic Operator using the second method.

Implementing IGeneticOperator

This is the simplest and most flexible way to create a Genetic Operator. The class SimpleOperator in the code shown below shows the simplest example.

Once the operator has been created it can be added to the Operators collection in the same way as the other built-in operators e.g.

ga.Operators.Add(simpleOperator)

The Invoke method will be called by the GAF and will present the current generations population (param: population) along with the next generation’s population (param: newPopulation). Each operator is responsible for either taking some solutions from the current population and transferring them to the new population. The way in which this is done is left to the implementer of the operator. For example the Crossover Operator takes two solutions from the current population, performs a single or double point crossover, and places these ‘children’ into the new population.

The GetOperatorInvokedEvaluations method is used during by the GAF to determine the number of evaluations an operator invokes. Therefore, the method should return the number of evaluations that the operator undertakes for each invocation.

For example, the built-in Crossover operator evaluates the population to determine which individuals to select. However, the built-in Mutation operator does not perform any evaluations. If an operator performed a single evaluation of each member of a population of say 100 individuals, the GetOperatorInvokedEvaluation method would return 100. For an operator that does not perform any evaluations the GetOperatorInvokedEvaluation method would return 0.

Things to Bear in Mind

  • Ensure that the new population is not larger than the current population.
  • Elites passed into the new population by the Elite Operator will be marked with the ‘IsElite’ property set to true. These should not normally be interfered with by subsequent operators.

Auto-Mutation

Watson (2003) discussed an approach that used a non-phenotype gene within the chromosome that could be used to increase the mutation probability. This additional gene was treated to the same genetic operations as the other genes, however, it was not used during chromosome decoding process. The gene was simply used to modify the mutation probability.

The class AutoMutate in the code below shows an Auto-Mutate operator that has been built by deriving from the existing BinaryMutate operator of the GAF. This process makes it very simple to create an operator that could increase the mutation probability depending upon the non-phenotype gene’s value.

In this implementation, a value of 1 increases the probability by a factor of 5, 10 or 20 depending upon the configuration. A value of 0 has no effect on the mutation probability. The code for this extended operator is shown below. As the non-phenotype gene is subject itself, to this increased probability, there is a greater probability that the gene will be changed from 1 to 0 than from 0 to 1. The effect therefore, is that as convergence occurs, less and less chromosomes are subject to this increased mutation rate. However, if the landscape changes significantly, other chromosomes not affected by genetic operators come in to play. Those with the non-phenotype gene will increase the mutation probability rate once again, until the GA converges towards the new solution. The process will continue in this manner at every significant change in landscape. This Auto-Mutation process is explained in greater detail in Watsons paper (see References below).

In this example the last gene is assumed to be the non-phenotype gene. In order to use this operator, simply create a chromosome with an extra gene. Set this gene to a random value and do not use the gene to store information (non-phenotype gene).

Enjoy!

References:

Watson, T. (2003) An Investigation into Cooperative Behaviour: Altrurism and Evolutionary Computing. Submitted in partial fulfilment of the requirements for the degree of Doctor Of Philosophy DeMontfort Universiity 2003

This code and the supporting project is available from BitBucket.

using System;
using GAF;

namespace Operators
{
  public class SimpleOperator : IGeneticOperator
  {
    public void Invoke(Population currentPopulation, ref Population newPopulation, FitnessFunction fitnesFunctionDelegate)
    {
      throw new NotImplementedException();
    }

    public int GetOperatorInvokedEvaluations()
    {
      throw new NotImplementedException();
    }

    public bool Enabled { get; set; }
  }
}

This code and the supporting project is available from BitBucket.

using System.Linq;
using GAF;
using GAF.Operators;

namespace Operators
{
  public class AutoMutate : BinaryMutate
  {
    private AutoMutateFactor _autoMutationFactorS;
    private readonly object _syncLock = new object();
    private int _geneCount;

    public AutoMutate(double mutationProbability, bool allowDuplicates)
      : base(mutationProbability, allowDuplicates)
    {
    }

    public override void Invoke(Population currentPopulation, ref Population newPopulation,
      FitnessFunction fitnesFunctionDelegate)
    {
      _geneCount = newPopulation.ChromosomeLength;
      base.Invoke(currentPopulation, ref newPopulation, fitnesFunctionDelegate);
    }

    protected override void Mutate(Chromosome chromosome, double mutationProbability)
    {
      //adjust and scale for AutoMutate Factor based on the value of the last gene
      var newMutationProbability = 0.0;
      var nonPhenotypeGene = chromosome.Genes.ElementAt(_geneCount - 1);

      if (nonPhenotypeGene.BinaryValue == 1)
      {
        newMutationProbability = mutationProbability * (int)AutoMutationFactor;
      }
      else
      {
        newMutationProbability = mutationProbability;
      }
      base.Mutate(chromosome, newMutationProbability);
    }

    public AutoMutateFactor AutoMutationFactor
    {
      get
      {
        lock (_syncLock)
        {
          return _autoMutationFactorS;
        }
      }
      set
      {
        lock (_syncLock)
        {
          _autoMutationFactorS = value;
        }
      }
    }
  }
}

This code and the supporting project is available from BitBucket.

namespace Operators
{
  public enum AutoMutateFactor
  {
    None = 1,
    Factor5 = 5,
    Factor10 = 10,
    Factor20 = 20,
    Factor50 = 50
  }
}

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

Hopfield Neural Network for Character Recognition in .Net and C#

Hopfield Network

This research activity, originally undertaken in conjunction with an MSc program at the DMU University (UK), was to develop some simple character and shape recognition software using .Net and C#.

The code and results are presented here as an example of how relatively simple C# code can be used to implement the Hopfield Artificial Neural Network to perform character recognition.

Artificial Intelligence techniques, in particular Artificial Neural Networks, are particularly suited to pattern recognition. They compare favourably with other methods of pattern analysis and in some cases they can outperform them. However, they are often computationally expensive.

The Hopfield artificial neural network is an example of an Associative Memory Feedback network that is simple to develop and is very fast at learning. The ability to learn quickly makes the network less computationally expensive than it’s multilayer counterparts [13]. This makes it ideal for mobile and other embedded devices. In addition the Hopfield network is simple to develop, and can be build without the need for third party libraries or toolsets thereby making it more attractive for use in mobile and embedded development.

John Hopfield, building on the work of Anderson [2], Kohohen [10] developed a complete mathematical analysis of the recurrent artificial neural network. For this reason this type of network is generally referred to as the Hopfield network [14].

Hopfield Demonstration

The Hopfield network [8] consists of a single layer of neurons in which each neuron is connected to every other neuron. If the network recognises a pattern it will return the pattern. However, it suffers the same drawbacks as other single layer networks in that t cannot represent non-linearly separable functions.

The first image shows how the outputs of the network are fed back to the inputs. This means that the outputs are some function of the current inputs and the previous outputs. The result is that an output causes the input to change, causing a corresponding change in output, which in turn changes the input and so on until the network enters a stable state and no further changes take place. The network requires a learning phase but this involves only one matrix calculation, is very short and therefore, computationally inexpensive.

Hopfield Grid

The Hopfield network for this study was implemented using Microsoft C# and Visual Studio 2010. The network and its associated classes were built into a single .Net assembly, whilst the test harness and unit testing utilities were created as separate projects that referenced this library.

The test harness (see screen shot) consisted of a small, graphical user interfaced based program. This test program allowed windows, containing grids of neurons, to be created. Each grid allowed patterns to be entered for training, and for results to be displayed. In addition the grids allowed for shapes to be drawn using a mouse. The code is available for download here.

The main assembly containing the Hopfield implementation, includes a matrix class that encapsulates matrix data and provides instance and static helper methods. The class implements all common matrix algorithms. Although not universally agreed [13], literature suggests that the neurons in a Hopfield network, should be updated in a random order. This has been incorporated into the Hopfield class through the use of a simple, Fisher-Yates, shuffle algorithm.

Results

When testing simple distinct patterns the network performed well, correctly identifying each pattern. However, as expected, as the patterns increased in similarity, the network often returned incorrect results. These additional states (local minima) dramatically affected the network’s ability to associate an input with the correct pattern.

Hopfield [8] stated that the number of patterns that can be stored was given by the following formula;

P = 0.15n (where P = number of patterns and n = number of neurons).

Based on this, a network of 64 Neurons could store 9.6 patterns. The relationship between the number of neurons and the amount of patterns stored, is not universally agreed, Crisanti et al. [5], suggests a value 8.77 patterns for a 64 neuron network, McEliece et al. [12] and Amari & Maginu [1] suggest 7.11 and 5.82 patterns respectively, for the same network. This suggests that to store and retrieve three patterns we could need as many as 33 neurons.

The network was subjectively tested using numeric digits. These tests involved training the network with binary patterns that resembled a numeric digit followed by a testing phase where numeric digits to be tested, were hand drawn using the computers mouse. The Hopfield network correctly identified each number and returned the correct character.

Whilst the experiments did not product a final working character recognition system, they do demonstrate what can be achieved with quite simple code. The code is available for download here.

Enjoy!

References

  • [1] Amari, S. & Maginul, K. Statistical neurodynamics of associative memory Neural Networks, 1, 63-74, 1988
  • [2] Anderson, J. A. Psych Rev., 84, 413-451, 1977
  • [3] Campadelli, P., Mora, P. & Schettini, R. Using Hopfield Networks in the Nominal Color Coding of Classified Images IEEE Universita‚Äô di Milano, 1051-4651/94, 112-116, 1994
  • [4] Chen, L., Fan, J. and Chen, Y. A High Speed Modified Hopfield Neural Network and A Design of Character Recognition System IEEE Chung-Yung Christian University, CH3031-2/91/0000-0308, 1991 308-314
  • [5] Crisanti, A., Amit, D. & Gutfreund, H. Saturation level of the Hopfield model for neural network Europhysics Letters, 2(4), 337-341, 1986
  • [6] Grant, P., & Sage, J. A comparison of neural network and matched filter processing for detecting lines in images Neural Networks for Computing, AIP Conf. Proc. 151, Snowbird, Utah, 194-199, 1986
  • [7] Heaton, J. Introduction to Neural Networks St Louis: Heaton Research, Inc, 2008
  • [8] Hopfield, J. Neural networks and physical systems with emergent collective computational abilities, Proceedings of the National Academy of Science, USA Biophysics, 79, 2554-2558 , 1982
  • [9] Kim, J., Yoon, S., Kim, Y., Park, E., Ntuen, C., Sohn, K. & Alexander, E. An efficient matching algorithm by a hybrid Hopfield network for object recognition IEEE North Carolina A&T State University, 0-7803- 0593-0/92 2888-2892, 1992
  • [10] Kohohen, T. Associative Memory-A System Theoretic Approach, New York: Springer, 1977
  • [11] Li, M., Qiao, J. & Ruan, X. A Modified Difference Hopfield Neural Network and Its Application Proceedings of the 6th World Congress on Intelligent Control and Automation, June 21-23, 2006
  • [12] McEliece, R., Posner, E., Rodemich, E. & Venkatesh, S. The capacity of the hopfield associative memory IEEE Transactions on Information Theory, 33(4), 461-482, 1987
  • [13] Picton, P. Neural Networks, 2nd ed. New York: Palgrave, 2000
  • [14] Popoviciu, N. & Boncut, M. On the Hopfield algorithm. Foundations and examples General Mathematics 13(2), 3550, 2005

The GPS Library for .Net

The GPS Library is a single .Net 4.0 Assembly designed to provide a simple object based interface to both the Garmin and Magellan range of GPS devices. In addition the GPS Library will support NMEA devices.

The GPS Library was originally sold as the Waymex GPS Library for .Net. Waymex IT Ltd no longer exists and the rights to this software now lie with me, the original author. The project, including latest version and source code is now available on BitBucket under the unrestricted BSD licence.

The GPS Library started life back in the late 90s as an experimental product written for the Aboriginal Land Management Office. They had a lot of land that needed mapping and their approach was to spend several weeks driving around the perimiter in a Land Rover, carrying a Garmin GPS. Following the success of this experiment, the component was opened up for general sale.

The code, originally written in VB6, was ported to .Net 1.1 and then converted from VB.net to C# in 2003. It was upgraded to .Net 4.0 in 2010. Despite the fact that the code was written before Generics, Linq, Lambdas and all the other features we know and love today, and Patterns and Practices were not what they are now, the product has performed well for many customers over many years. It continues to be used in applications around the world today.

Having said that, the resources required to maintain, develop and support this product in a decreasing market is simply not viable any longer. Waymex as a company no longer exists and I have for sometime been involved in other products and technologies. Understanding the needs of Waymex GPS Library customers, to support their own customers and projects, the GPS Library for .Net has been moved to BitBucket.

Enjoy!

Using Genetic Algorithm To Solve the ‘Perfect Matching’ Problem

Emre Ataseven, in his Codeproject article describes how the Genetic Algoritm Framework for .Net (GAF) can be used to solve the ‘Perfect Matching Problem’ in the context of Bridge teams.

Swiss Patton Image

In his article, Emre uses the GAF to generate team rounds in the game of Bridge.

Emre’s solution uses the GAF to match teams in Bridge game using the Swiss Patton technique. The aim was to generate n-1 rounds for n teams, the requirements were as follows;

  • team count shall be even;
  • each pair shall be matched only once;
  • matching close scoring teams;
  • create all possible rounds (i.e. If team count is n, n-1 possible rounds should be created).

The full solution and its similarities to the “Perfect Matching Problem” is described brilliantly by Emre in his article on Codeproject.