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 
Minimize:
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 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
.
.
Bahrudin Hrnjica Blog 