June | 2013 | Bahrudin Hrnjica Blog

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.

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

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

Some times ago, I had to find problematically full path of Logging file, and open it through the Shell execute. I thought it will be easy, just get the file path from configuration file and open the file with shell execute. But things are different, because you cannot reach system.diagnostic section regularly.

Suppose we have configuration file with diagnostic section defined similar like picture above.

The solution must be very common. Open the config file, find section about logging, and read the path of logging file. The code snippet below shows how to achieve this.

string logFileName="";

//Define XMLDocument for reading config file in to XML doc.
XmlDocument xdoc = new XmlDocument();
xdoc.Load(AppDomain.CurrentDomain.SetupInformation.ConfigurationFile);

//Filter desired section
XmlNode xnodes = xdoc.SelectSingleNode("/configuration/system.diagnostics/sharedListeners");

//enumerate nodes in the section
foreach (XmlNode xnn in xnodes.ChildNodes)
{
    //when the right node is met
    if (xnn.Name == "add")
    {
        //enumerate all itc atrubutes
        foreach(var att in xnn.Attributes)
        {
            var a= att as XmlAttribute;
            if (a != null)
            {
               //and get the right one
                if (a.Name == "fileName")
                {
                    //store file path in the variable
                    logFileName = a.Value;
                }
            }
        }
    }
}

//Open the log file from shell.
ProcessStartInfo psi = new ProcessStartInfo(openFileDialog1.FileName);
psi.UseShellExecute = true;
Process.Start(psi);

Bahrudin Hrnjica Blog

All about technology: ML, .NET, EA, FEM, Math…

Monthly Archives: June 2013

C# Matrix Chromosome implementation in Genetic Algorithm

Get log file from system.diagnostic.sharedListeners section of a config file