Some sample C# code on how a genetic algorithm can be applied to the quadratic assignment problem.
The quadratic assignment problem (QAP) is a combinatorial optimization problem that models the following real-life problem:
Given a set of n facilities and a set of n locations, specify a distance for each pair of locations and a flow for each pair of facilities, the objective is to assign each facility to a different location such that the sum of the distances multiplied by the corresponding flows is minimised.
The problem statement resembles that of the assignment problem, except that the cost function is expressed in terms of quadratic inequalities, hence the name.
This example is implemented as a simple console application using C# code developed in Microsoft Visual Studio. To help break down the problem a little, I develop a number of classes for the purposes of encoding potential solutions as chromosomes, maintaining a population of chromosome and applying genetic operators to the population of solutions in the form of crossover, mutation and selection.
Code samples as follows:
Program.cs
using System;
namespace QuadraticAssignment
{
class Program
{
static void Main(string[] args)
{
const int tasks = 5;
int[,] flows = new int[tasks, tasks] { {0, 10, 15, 0, 7 },
{10, 0, 5, 6, 0 },
{15, 5, 0, 4, 2 },
{0, 6, 4, 0, 5 },
{7, 0, 2, 5, 0 } };
int[,] distances = new int[tasks, tasks] { {0, 3, 6, 4, 2 },
{3, 0, 2, 3, 3 },
{6, 2, 0, 3, 4 },
{4, 3, 3, 0, 1 },
{2, 3, 4, 1, 0 } };
var matrix = new Matrix(tasks, flows, distances);
var rnd = new Random();
var alg = new Algorithm(rnd, 200, tasks, false);
alg.Run(rnd, matrix, tasks);
}
}
}
Matrix.cs
Used to maintain the distances between locations, the flows between facilities and calculate the sum of the distances multiplied by flows. In the cost calculation I apply a factor to penalise solutions according to the number of constraint violations. If for example a location has more than one facility assigned to it, then it is heavily penalised and likely to die away in favour of superior solutions.
namespace QuadraticAssignment
{
public class Matrix
{
private int[,] _flow; // flow between facilities
private int[,] _distance; // distance between locations
private int[,] _cost;
public Matrix(int size, int[,] flow, int[,] distance)
{
InitDistanceMatrix(distance);
InitFlowMatrix(flow);
_cost = new int[size, size];
}
public void InitDistanceMatrix(int[,] array)
{
_distance = array;
}
public void InitFlowMatrix(int[,] array)
{
_flow = array;
}
private int IsFacilityAtLocation(int facility_i, int location_j, Chromosome chromosome)
{
var facility = chromosome.GetFacility(location_j);
return facility == facility_i ? 1 : 0;
}
public int GetChromosomeCost(Chromosome chromosome, bool maximise)
{
var totalCost = 0;
var size = chromosome.Size();
for (var i = 0; i < size; ++i)
{
for (var j = 0; j < size; ++j)
{
var fi = chromosome.GetLocation(i);
var fj = chromosome.GetLocation(j);
var flow = _flow[i, j];
var distance = _distance[fi, fj];
totalCost += distance * flow;
}
}
return totalCost;
}
public int GetCost(int factory, int task)
{
return _cost[factory, task];
}
}
}
Chromosome.cs
Used to encode solutions.
using System;
using System.Collections.Generic;
namespace QuadraticAssignment
{
public class Chromosome
{
// Assignments of facilities to locations
private List<int> _assignment;
private int _cost;
public Chromosome(int size, Random rnd)
{
GenerateArbitraryAssignment(size, rnd);
}
public int GetCost()
{
return _cost;
}
public int Size()
{
return _assignment.Count;
}
public Chromosome(int size)
{
_assignment = new List<int>(new int[size]);
}
public void SetCost(int cost)
{
_cost = cost;
}
private void GenerateArbitraryAssignment(int size, Random rnd)
{
_assignment = new List<int>();
for (int i = 0; i < size; i++)
{
_assignment.Add(i);
}
// Shuffle the array
for (int i = 0; i < _assignment.Count; ++i)
{
int randomIndex = rnd.Next(_assignment.Count);
int temp = _assignment[randomIndex];
_assignment[randomIndex] = _assignment[i];
_assignment[i] = temp;
}
}
public void Print(int iteration)
{
Console.WriteLine("Iteration = " + iteration);
Console.WriteLine("Total cost = " + _cost);
for (var i = 0; i < _assignment.Count; ++i)
{
var location = i + 1;
var facility = _assignment[i] + 1;
Console.WriteLine("Location[" + location + "] -> Task[" + facility + "]");
}
Console.WriteLine();
}
public void Assign(int city, int factory)
{
_assignment[city] = factory;
}
public int GetFacility(int city)
{
return _assignment[city];
}
public int GetLocation(int facility)
{
var location = -1;
for (int i = 0; i < _assignment.Count; ++i)
{
if (_assignment[i] == facility)
{
location = i;
break;
}
}
return location;
}
public void Crossover(Chromosome chr1, Chromosome chr2, Random rnd)
{
var size = _assignment.Count;
int index1 = rnd.Next(0, size);
var f1 = chr1.GetFacility(index1);
int index2 = rnd.Next(0, size);
var f2 = chr2.GetFacility(index2);
var l1 = chr1.GetLocation(f2);
var l2 = chr2.GetLocation(f1);
chr1.Assign(index1, f2);
chr1.Assign(l1, f1);
chr2.Assign(index2, f1);
chr2.Assign(l2, f2);
}
public void Mutation(Random rnd)
{
var selection = rnd.Next(0, 100);
// Randomise two items
if (selection < 40)
{
var size = _assignment.Count;
int i1 = rnd.Next(0, size);
int i2 = rnd.Next(0, size);
while (i1 == i2)
{
i2 = rnd.Next(0, size);
}
int v1 = _assignment[i1];
int v2 = _assignment[i2];
Assign(i1, v2);
Assign(i2, v1);
}
// Randomise 3 items
if (selection < 80)
{
var size = _assignment.Count;
int i1 = rnd.Next(0, size);
int i2 = rnd.Next(0, size);
int i3 = rnd.Next(0, size);
while (i1 == i2 || i1 == i3 || i2 == i3)
{
i2 = rnd.Next(0, size);
i3 = rnd.Next(0, size);
}
int v1 = _assignment[i1];
int v2 = _assignment[i2];
int v3 = _assignment[i3];
int choose = rnd.Next(2);
if (choose == 0)
{
Assign(i1, v2);
Assign(i2, v3);
Assign(i3, v1);
}
else
{
Assign(i1, v3);
Assign(i2, v1);
Assign(i3, v2);
}
}
else
{
// Shuffle the array
for (int i = 0; i < _assignment.Count; ++i)
{
int randomIndex = rnd.Next(_assignment.Count);
int temp = _assignment[randomIndex];
_assignment[randomIndex] = _assignment[i];
_assignment[i] = temp;
}
}
}
public int GetRandomFactory(Random rnd, int taskRange)
{
return rnd.Next(0, taskRange);
}
public void Copy(Chromosome chr)
{
_cost = chr._cost;
for (var i = 0; i < _assignment.Count; ++i)
{
_assignment[i] = chr._assignment[i];
}
}
}
}
Algorithm.cs
Used to apply the genetic operators and the population of chromosomes.
using System;
namespace QuadraticAssignment
{
public class Algorithm
{
private Population _population;
public Algorithm(Random rnd, int populationSize, int tasks, bool maximise)
{
_population = new Population(rnd, populationSize, tasks, maximise);
}
public void Run(Random rnd, Matrix costMatrix, int tasks)
{
var iteration = 1;
_population.Evaluate(costMatrix, iteration);
while (iteration < 10000)
{
_population.StoreBestSolution(tasks);
_population.Mutate(rnd);
_population.ApplyCrossover(rnd, tasks);
_population.SeedBestSolution(rnd);
_population.Evaluate(costMatrix, iteration);
_population.Selection(rnd);
iteration++;
}
}
}
}
Running the algorithm
As an example we apply the genetic algorithm on a QAP problem with a known optimal solution, described at the following link:
https://pdfs.semanticscholar.org/7b58/cadd8ce2e0f16daa9a7b2d73108381884ee9.pdf
The problem is illustrated as follows:
Matrices A and B represent the distance and flow matrices respectively:
The optimal assignment of facilities to locations is [2,4,5,3,1].
And this permutation of [2,4,5,3,1] was achieved in iteration 2 by the genetic algorithm as shown by the console application output:
Some more example test problems
Some example test problems are given at the following link:
To check that this program works efficiently (and calculates the costs correctly) I compare the results of the GA with that given by the calculator at this website link on clicking the ‘Optimal’ button:
On running the genetic algorithm in the console application the optimal solution is obtained as shown:
More optimal solutions to test problems are given the following link:
QAP problem instances and solutions
One such problem is by A.N. Elshafei – “Els19”
The data describe the distances of 19 different facilities of a hospital in Cairo, Egypt and the flow of patients between those locations.
The distance and flow data is given at the following link:
The optimal solution is
cost = 17212548 (OPT)
permutation = [9,10,7,18,14,19,13,17,6,11,4,5,12,8,15,16,1,2,3]
The genetic algorithm was run using the following usage:
Program.cs
using System;
namespace QuadraticAssignment
{
class Program
{
static void Main(string[] args)
{
const int tasks = 19;
int[,] flows = new int[tasks, tasks]
{ { 0, 76687, 0, 415, 545, 819, 135, 1368, 819, 5630, 0, 3432, 9082, 1503, 0, 0, 13732, 1368, 1783 },
{ 76687, 0, 40951, 4118, 5767, 2055, 1917, 2746, 1097, 5712, 0, 0, 0, 268, 0, 1373, 268, 0, 0 },
{ 0, 40951, 0, 3848, 2524, 3213, 2072, 4225, 566, 0, 0, 404, 9372, 0, 972, 0, 13538, 1368, 0 },
{ 415, 4118, 3848, 0, 256, 0, 0, 0, 0, 829, 128, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 545, 5767, 2524, 256, 0, 0, 0, 0, 47, 1655, 287, 0, 42, 0, 0, 0, 226, 0, 0 },
{ 819, 2055, 3213, 0, 0, 0, 0, 0, 0, 926, 161, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 135, 1917, 2072, 0, 0, 0, 0, 0, 196, 1538, 196, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1368, 2746, 4225, 0, 0, 0, 0, 0, 0, 0, 301, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 819, 1097, 566, 0, 47, 0, 196, 0, 0, 1954, 418, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 5630, 5712, 0, 829, 1655, 926, 1538, 0, 1954, 0, 0, 282, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 128, 287, 161, 196, 301, 418, 0, 0, 1686, 0, 0, 0, 0, 226, 0, 0 },
{ 3432, 0, 404, 0, 0, 0, 0, 0, 0, 282, 1686, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 9082, 0, 9372, 0, 42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1503, 268, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 972, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 99999, 0, 0, 0 },
{ 0, 1373, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 99999, 0, 0, 0, 0 },
{ 13732, 268, 13538, 0, 226, 0, 0, 0, 0, 0, 226, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1368, 0, 1368, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 1783, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
int[,] distances = new int[tasks, tasks]
{ { 0, 12, 36, 28, 52, 44, 110, 126, 94, 63, 130, 102, 65, 98, 132, 132, 126, 120, 126 },
{ 12, 0, 24, 75, 82, 75, 108, 70, 124, 86, 93, 106, 58, 124, 161, 161, 70, 64, 70 },
{ 36, 24, 0, 47, 71, 47, 110, 73, 126, 71, 95, 110, 46, 127, 163, 163, 73, 67, 73 },
{ 28, 75, 47, 0, 42, 34, 148, 111, 160, 52, 94, 148, 49, 117, 104, 109, 111, 105, 111 },
{ 52, 82, 71, 42, 0, 42, 125, 136, 102, 22, 73, 125, 32, 94, 130, 130, 136, 130, 136 },
{ 44, 75, 47, 34, 42, 0, 148, 111, 162, 52, 96, 148, 49, 117, 152, 152, 111, 105, 111 },
{ 110, 108, 110, 148, 125, 148, 0, 46, 46, 136, 47, 30, 108, 51, 79, 79, 46, 47, 41 },
{ 126, 70, 73, 111, 136, 111, 46, 0, 69, 141, 63, 46, 119, 68, 121, 121, 27, 24, 36 },
{ 94, 124, 126, 160, 102, 162, 46, 69, 0, 102, 34, 45, 84, 23, 80, 80, 69, 64, 51 },
{ 63, 86, 71, 52, 22, 52, 136, 141, 102, 0, 64, 118, 29, 95, 131, 131, 141, 135, 141 },
{ 130, 93, 95, 94, 73, 96, 47, 63, 34, 64, 0, 47, 56, 54, 94, 94, 63, 46, 24 },
{ 102, 106, 110, 148, 125, 148, 30, 46, 45, 118, 47, 0, 100, 51, 89, 89, 46, 40, 36 },
{ 65, 58, 46, 49, 32, 49, 108, 119, 84, 29, 56, 100, 0, 77, 113, 113, 119, 113, 119 },
{ 98, 124, 127, 117, 94, 117, 51, 68, 23, 95, 54, 51, 77, 0, 79, 79, 68, 62, 51 },
{ 132, 161, 163, 104, 130, 152, 79, 121, 80, 131, 94, 89, 113, 79, 0, 10, 113, 107, 119 },
{ 132, 161, 163, 109, 130, 152, 79, 121, 80, 131, 94, 89, 113, 79, 10, 0, 113, 107, 119 },
{ 126, 70, 73, 111, 136, 111, 46, 27, 69, 141, 63, 46, 119, 68, 113, 113, 0, 6, 24 },
{ 120, 64, 67, 105, 130, 105, 47, 24, 64, 135, 46, 40, 113, 62, 107, 107, 6, 0, 12 },
{ 126, 70, 73, 111, 136, 111, 41, 36, 51, 141, 24, 36, 119, 51, 119, 119, 24, 12, 0 } };
var matrix = new Matrix(tasks, flows, distances);
var rnd = new Random();
var alg = new Algorithm(rnd, 500, tasks, false);
alg.Run(rnd, matrix, tasks);
}
}
}
In this experiment the genetic algorithm managed to obtain the known optimal solution of cost = 17212548 in 482 iterations using a mutation rate of 10%, a crossover rate of 15% and a population size of 1000:
Obtain the Visual Studio project from the following Selz link:
