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

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 29/06/2013, in .NET, C#, Evolucijski Algoritmi, GPdotNET and tagged , , , , , . Bookmark the permalink. 1 Comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s