GPdotNET v3.0 is out


GPdotNET3.0Beta1

I am very proud to announce GPdotNET v3.0, the new version which brings 3 new solvers based on Genetic Algorithm and several new features. In previous posts I was  writing about those new features:

1. TSP and vector based chromosome implementation in GPdotNET

2. Exporting GP Model in to Wolfram Mathematica

3. Matrix based chromosome implementation

4. Introduction to Assignment and transportation problems based on Genetic Algorithm

The source code and Click Once installation are uploaded in codeplex site, so go and grab the new version. hppt://gpdotnet.codeplex.com

I am asking for feedback and bug reports. If you find something strange post a comment here on anywhere in blog site or codeplex site. I will try to answer as quickly as possible.

Here are screenshots with new Assignment and Transportation solvers in GPdotNET:

GPdotNET3.0Beta1sl3
Loaded  training data of Assignment problem

GPdotNET3.0Beta1sl4

Simulation Tab page with optimal result of Assignment problem

GPdotNET3.0Beta1sl5

Loaded  training data of Transportation problem

GPdotNET3.0Beta1sl6
Simulation Tab page with optimal result of Transportation problem

C# Matrix Chromosome implementation in Genetic Algorithm


The next version of GPdotNET will be extended with 3 new solvers:

– Traveling Salesman Problem (TSP),
– Assignment problem (AP) and
– Transportation Problem (TP)

More or less the first two solvers are already presented in previous posts. Both TSP and AP can be implemented with vector based representation, which is already posted here. For transportation problem new chromosome representation have to be implemented. Before we go in to the implementation let give short introduction of Transportation problems.

Transportation problem is one of the simplest combinatorial problem. It searches the determination of a minimum cost transportation plan for a single commodity from a number of sources to a number of destinations. It requires the specification of the level of supply at each source, the amount of demand at each destination, and the transportation cost from each source to each destination. Solution is to find the amount to be shipped from each source to each destination in such a way that the total transportation cost have to be minimized.
Let’s assume we have n sources and k destinations. Let’s also assume that amount of supply at source i is SRC(i) and demand at destination j is DST(j). The unit transportation cost between source i and destination j is CST(i,j). Let x_{ij} is the amount transported from source i to destination j transportation problem can be formulated like the following:
Minimize:

min { \sum_{i=1}^{n}\sum_{j=1}^{m} c_{ij} x_{ij}}

{ \sum_{i=1}^{n} x_{ij}=a_i}, (i=1,...,n)

{ \sum_{j=1}^{m} x_{ij}=b_j, (j=1,...,m)}

{ x_{ij}>=0, (i=1,...,n), (j=1,...m)}

A typical transformation problem is shown in picture below. In this example we have 3 sources and 4 destination. The supply is shown on Supply column, and destination cost is shown on the last row. Total supply and demand is 45. The unit transportation cost is shown on central table.

transportProblem1

The optimal solution is shown in picture below. The total cost is 315.

transportProblem2

The most natural way to represent this kind of problem is 2 dimensional matrix, because our solution must be presented as picture show above in tabular data.

Theory behind matrix representation chromosome is beyond this blog post, so in the next section it will be shows only C# implementation with some description. If you want more information behind this implementation you can find it in the book: Genetics Algorithm + Data Structure = Evolution Programs which can be see at Google books at pages 187-191.

Implementation of main method: GenerateMatrix:

///
/// Initialize randomly matrix chromosome for transport problem based on book
/// Genetic Algorithm+Data Structure= Evolution programs
///
///r- number of rows (sources)
///c- number of columns (destination)
///src[] - source values
///dest[] - destination values
/// Cost matrix cost(i,j)
internal static int[][] GenerateMatrix(int r, int c, int[] src, int[] dest)
{
    //initi values
    int tot = r * c;
    var lst = new List(tot);

    //prepare values for generation
    int counter = 0;
    var vals = new int[r][];
    for (int i = 0; i < r; i++)
    {
        vals[i] = new int[c];
        for (int j = 0; j < c; j++)
        {
            lst.Add(counter);
            counter++;
        }
    }

    while (true)
    {
        //exit from while must be before list is empty
        if (lst.Count == 0)
            throw new Exception("null");

        int ind = Globals.radn.Next(lst.Count);
        int q = lst[ind];

        int i = (int)Math.Floor((double)(q) / (double)(c));
        int j = q % c;

        //if element is visited generate again random number
        if (vals[i][j] != 0)
            continue;

        lst.RemoveAt(ind);

        int val = Math.Min(src[i], dest[j]);
        vals[i][j] = val;
        src[i] = src[i] - val;
        dest[j] = dest[j] - val;

        bool canBreak = true;
        for (int k = 0; k < r; k++)
            if (src[k] != 0)
            {
                canBreak = false;
                break;
            }

        if (canBreak == false)
            continue;

        for (int k = 0; k < c; k++)
            if (dest[k] != 0)
            {
                canBreak = false;
                break;
            }
        //if all sources and destination are zero, generation is finished
        if (canBreak)
            return vals;
    }
}

This is main function for this type of chromosome because all other operations is based on this method.
The second implementation is Crossover.

///
// Crossover based on Book Genetic Algorithm +Data Structure = Evolution Programs.
public void Crossover(IChromosome parent2)
{

GAMChromosome ch2= parent2 as GAMChromosome;
if(ch2==null)
throw new Exception("ch2 cannot be null!");

int[] srcREM1 = new int[rows];
int[] destREM1 = new int[cols];
int[] srcREM2 = new int[rows];
int[] destREM2 = new int[cols];

for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
double m1 = value[i][j] + ch2.value[i][j];
double d = Math.Floor(m1 / 2.0);
int r = (((int)m1) % 2);

value[i][j] = (int)d;
ch2.value[i][j] = (int)d;
srcREM1[i] += r;
destREM1[j] += r;
srcREM2[i] += r;
destREM2[j] += r;
}
}
for (int i = 0; i < rows; i++)
{
srcREM1[i] /= 2;
srcREM2[i] /= 2;
}
for (int j = 0; j < cols; j++)
{
destREM1[j] /= 2;
destREM2[j] /= 2;
}
var mat1 = GenerateMatrix(rows, cols, srcREM1, destREM1);
var mat2 = GenerateMatrix(rows, cols, srcREM2, destREM2);
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
value[i][j] += mat1[i][j];
ch2.value[i][j] += mat2[i][j];
}
}
return;
}

As we can see crossover method contain two calls for GenerateMatrix method which randomly initialize sub matrix chromosome.

Mutation operation also depends of  GenerateMatrix because it randomly choose location which needs to be recreated. The following code contains two Mutate methods where the second one calls GenerateMatrix for subMatrix random generation.

///  Mutation based on Book Genetic Algorithm +Data Structure = Evolution Programs.
public void Mutate()
{
    //choose random number of cols and rows
    int locRows = Globals.radn.Next(1,rows);
    int locCols = Globals.radn.Next(1,cols);
    //define array for holding random indexs
    var localRows = new int[locRows];
    var localCols = new int[locCols];

    //generate random source
    int counter = 0;
    while (true)
    {
        var num = Globals.radn.Next(rows);

        var found = false;
        for (var i = 0; i < localRows.Length; i++)
        {
            if (localRows[i] == num)
            {
                found = true;
                break;
            }
        }
        if (!found)
        {
            localRows[counter] = num;
            counter++;
        }
        if (counter  == localRows.Length)
            break;
    }
    //generate random destination
    counter = 0;
    while (true)
    {
        var num = Globals.radn.Next(cols);

        var found = false;
        for (var i = 0; i < localCols.Length; i++)
        {
            if (localCols[i] == num)
            {
                found = true;
                break;
            }
        }
        if (!found)
        {
            localCols[counter] = num;
            counter++;
        }
        if (counter == localCols.Length)
            break;
    }
    //perform mutation
    Mutate(locRows, locCols, localRows, localCols, this);

}

internal static int[][] Mutate(int r, int c, int[] rs, int[] cs, GAMChromosome ch)
{
    var source = new int[r];
    var destination = new int[c];
    //calculate Source for random submatrix
    for (int i = 0; i < rs.Length; i++)
        for (int j = 0; j < cs.Length; j++)
            source[i]+= ch.value[rs[i]][cs[j]];

    //calculate Destination for random submatrix
    for (int i = 0; i < cs.Length; i++)
        for (int j = 0; j < rs.Length; j++)
            destination[i] += ch.value[rs[j]][cs[i]];

    var subMatrix= GAMChromosome.GenerateMatrix(r, c, source, destination);

    //merge generated submatrix to matrix
    for (int i = 0; i < rs.Length; i++)
        for (int j = 0; j < cs.Length; j++)
            ch.value[rs[i]][cs[j]] = subMatrix[i][j];

        return subMatrix;
}

This was the code implementation around Matrix based Chromosome representation for Genetic Algorithm. The full source code about it will be published with the first beta of GPdotNET v3.0. I can promisse that the first beta will be out for less that month.
Stay tuned

GPdotNET vNext: Assignment and Transportation problems


GPdotNET Logo

GPdotNET vNext

Recently I wrote blog post  about implementation of TSP problem in GPdotNET. I got positive feedback about implementation, but there were people saying if can I implement more problems based on linear programming and optimization. So I have decided to implement Assignment and Transportation problems in GPdotNET. With existing 4,  the next version of GPdotNET 2.5 will contains in total the following problem domains:

1. Modelling discrete data set with GP,

2. Modelling and optimization discrete data set with combination of GP and GA,

3. Modelling Time series data set with GP,

4. Optimization of Analytic function with GA,

5. Traveling Salesman Problem with GA,

6. Assignment Problem with GA,

7. Transportation problem with GA.

In order to implement those problems it has to be implemented two new chromosome types:

1. Vector based GA chromosome for solving TSP and Assigment problem

2. Matrix based GA chromosome for solving Transport problem.

gpdotnetvnext

The first one (vector based chromosome type) is already implemented and needs to be modified for accepting different format data, in order to fully support TSP and Assignment problems at the same time. For second type there are several solutions for implementation for Matrix based chromosome, one of my favorite is published in the book “Genetic Algorithms + Data Structures = Evolution Programs”.

I can say this would be an exciting summer. :)