After only 2 months of releasing GPdotNET v2.0 the new update is coming. Architecture of GPdotNET v2 allows implementation of wide range of GA & GP based problems. For this first update, it is implementation of Traveling Salesman Problem (TSP). Short description of this problem is to find the shortest path by visiting all cities only once. More info can be found here.  This problem is implemented just for several hours, because all important phases are already implemented.

The main implementations for this problem were:

1. TSPChromosome – class for chromosome representation
2. TSP Fitness – implementation
3. Other parts like selection, simulation of the result are mostly implemented.

TSPChromosome class implementation

Instead of binary value, TSP chromosome must be array of integers by representing path around cities. The main problem with this chromosome type is genetic operations, because you cannot implement it easily.

For example standard Crossover in GA takes random point and split parents in two parts, see picture below. One part goes to first offspring, the second one goes to second offspring. The same action is performed for the second parent. The picture below shows standard crossover in GA.

Unfortunately this operation cannot be applied to TSP, because every city can be visited only once. But how can we perform crossover at all? There are several methods can be found on internet. The method applied in GPdotNET is the following.

Choose different random points for Parent 1 and Parent 2.

Offspring 1 is created based on the left part of Parent 1, and sub permutation of the rest of cities.

Offspring 2 is created based on the right part of Parent 2 and sub permutation of rest of the cities.

Picture below show crossover used in GPdotNET.

The problem with this crossover is that offsprings are not created based on genetic material from both parents.

Implementation of TSPChromosome crossover method is presented below:

public void Crossover(IChromosome ch2)
{
    var ch22 = ch2 as GATSPChromosome;
    if (ch22 == null)
        throw new Exception("Chromosome cannot be null!");

    Order(true);
    ch22.Order(false);

    int randInd1 = Globals.radn.Next(length);
    int randInd2 = Globals.radn.Next(length);

    for (int i = 0; i < randInd1; i++)
    {
        int rand1 = Globals.radn.Next(randInd1);
        int rand2 = Globals.radn.Next(randInd1);

        var temp = value[randInd1];
        value[randInd1] = value[randInd2];
        value[randInd2] = temp;
    }

    for (int i = randInd2; i < length; i++)
     {
         int rand1 = Globals.radn.Next(randInd2,length);
         int rand2 = Globals.radn.Next(randInd2,length);
         var temp = ch22.Value[randInd1];
         ch22.Value[randInd1] = ch22.Value[randInd2];
         ch22.Value[randInd2] = temp;
     }
 }

Mutation operation for this chromosome can be implemented so that we randomly choose two cities and swap their positions in the path. Implementation for this operation is presented in code below:

 public void Mutate() {     int randInd1 = Globals.radn.Next(length);     int randInd2 = Globals.radn.Next(length);     if(randInd1>randInd2)
    {
        int temp= randInd2;
        randInd2=randInd1;
        randInd1=temp;
    }
    int j = 0;
    for (int i = randInd1; i <= randInd2; i++,j++)
     {
         if (i > (randInd2 - j))
            break;
        var temp1 = value[i];
        var temp2 = value[randInd2-j];
        value[i] = temp2;
        value[randInd2 - j] = temp1;
    }
}

Fitness of TSP

Fitness function is relatively simple. It calculates total path based on Chromosome array of cities. Fitness will be better if the path is shorter.

public float Evaluate(IChromosome chromosome, IFunctionSet functionSet)
{
    var ch = chromosome as GATSPChromosome;
    if (ch == null)
        return 0;
    else
    {
        double y = 0, fitness;
        double[] p1 = null;
        double[] p2 = null;
        int rCount = ch.Length;
        for (int i = 0; i < rCount; i++)
        {
            p1 = Globals.GetTerminalRow(ch.Value[i]);
            if (i + 1 == rCount)
                p2 = Globals.GetTerminalRow(ch.Value[0]);
            else
                p2 = Globals.GetTerminalRow(ch.Value[i+1]);

            // calculate distance betwee two points and make the sum
            y += Math.Sqrt((p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]));

            // check for correct numeric value
            if (double.IsNaN(y) || double.IsInfinity(y))
                return float.NaN;
        }
        //with this value we always search for maximum value of fitness
        fitness = ((1.0 / (1.0 + y)) * 1000.0);

        return (float)fitness;
    }
}

Loading City Map

TSP Solver needs City data of points in (X;Y) format. It must be loaded by CSV file format, the same as GPdotNET uses for loding data for modelling and optimization. The following data represent corect format:

CityMap data format:

How to run TSP Solver on GPdotNET

Running TSP solver with GPdotNET is relatively easy. The procedure follows global convention for creating new model or solver.

1. Choose New.. from mainpanel.

2.  Choose Traveling Salesman Problem, and click OK button.

3. Open Load Data tab, (if it not opened), press Load Cities Map button, choose CityMap.CSV, and press OK. Data is presented on picture below.

4. Sett GA parameters on Setting Tab panel:

5. Open Simulation Tab panel. You can see graphically representation of loaded map, and set of simulation parameters.

6. Press Run ribon button, and Solver will start. During simulation you can see that the path length is becoming shorter and shorter

7. As final result, Solver find the path which is the shortest or very close to shorter one.

8. Exit and Save your solution.

We have seen how easy is to implement such a problem, base on existing foundation of the GPdotNET. More problems based on GA/GP is cumming in the GPdotNET.  Application is posted on codeplex.com, as GPdotNET v2.1 beta 1.