Some sample C# code on how a genetic algorithm can be applied to the linear assignment problem.
This problem can be efficiently solved using the Hungarian algorithm, but I wanted to demonstrate how the genetic algorithm can produce an optimal solution too.
This example is implemented as a simple console application using 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
The main program loop:
using System;
namespace LinearAssignmentProblem
{
class Program
{
static void Main(string[] args)
{
var tasks = 5;
var popSize = 100;
var rnd = new Random();
// Do we seek to maximise or minimise?
var maximise = false;
var alg = new Algorithm(rnd, popSize, tasks, maximise);
var matrix = new CostMatrix(tasks);
matrix.SetCost(0, 0, 11);
matrix.SetCost(0, 1, 7);
matrix.SetCost(0, 2, 10);
matrix.SetCost(0, 3, 17);
matrix.SetCost(0, 4, 10);
matrix.SetCost(1, 0, 13);
matrix.SetCost(1, 1, 21);
matrix.SetCost(1, 2, 7);
matrix.SetCost(1, 3, 11);
matrix.SetCost(1, 4, 13);
matrix.SetCost(2, 0, 13);
matrix.SetCost(2, 1, 13);
matrix.SetCost(2, 2, 15);
matrix.SetCost(2, 3, 13);
matrix.SetCost(2, 4, 14);
matrix.SetCost(3, 0, 18);
matrix.SetCost(3, 1, 10);
matrix.SetCost(3, 2, 13);
matrix.SetCost(3, 3, 16);
matrix.SetCost(3, 4, 14);
matrix.SetCost(4, 0, 12);
matrix.SetCost(4, 1, 8);
matrix.SetCost(4, 2, 16);
matrix.SetCost(4, 3, 19);
matrix.SetCost(4, 4, 10);
alg.Run(rnd, matrix, tasks);
}
}
}
CostMatrix.cs
Used to maintain the cost of each task for each worker.
using System;
using System.Collections.Generic;
namespace LinearAssignmentProblem
{
public class CostMatrix
{
private int[] _agents;
private int[,] _costArray;
private int _n;
public CostMatrix(int agents)
{
_agents = new int[agents];
_costArray = new int[agents, agents];
_n = agents;
for (int i = 0; i < agents; ++i)
{
for (int j = 0; j < agents; ++j)
{
SetCost(i, j, 0);
}
}
}
public CostMatrix(int agents, int cost)
{
_agents = new int[agents];
_costArray = new int[agents, agents];
_n = agents;
for (int i = 0; i < agents; ++i)
{
for (int j = 0; j < agents; ++j)
{
int value = cost * (j + 1);
SetCost(i, j, value);
}
cost += 1;
}
}
// Generate cost matrix of arbitrary costs
public CostMatrix(int agents, int tasks, Random rnd)
{
_agents = new int[agents];
_costArray = new int[agents, agents];
_n = agents;
for (int i = 0; i < agents; ++i)
{
for (int j = 0; j < tasks; ++j)
{
SetCost(i, j, rnd.Next(10, 100));
}
}
}
public void SetCost(int agent, int task, int cost)
{
if (agent < _n && task < _n)
{
_costArray[agent, task] = cost;
}
}
public int GetCost(int worker, int task)
{
return _costArray[worker, task];
}
public int GetChromosomeCost(Chromosome chromosome, bool maximise)
{
var totalCost = 0;
var assignments = new HashSet<int>();
for (int worker = 0; worker < _n; ++worker)
{
var task = chromosome.GetTask(worker);
assignments.Add(task);
totalCost += GetCost(worker, task);
}
// Penalise cost asccording to constraint violations
var violations = _n - assignments.Count;
return maximise ? totalCost - violations * 100 :
totalCost + violations * 100;
}
}
}
Chromosome.cs
Used to encode solutions.
using System;
namespace LinearAssignmentProblem
{
public class Chromosome
{
private int[] _workers;
private int _cost;
private int _size;
public Chromosome(Random rnd, int workers)
{
_size = workers;
_workers = new int[workers];
Generate(rnd, workers);
}
public Chromosome(int workers)
{
_size = workers;
_workers = new int[workers];
}
public void Print(int iteration)
{
Console.WriteLine("Iteration = " + iteration);
Console.WriteLine("Total cost = " + _cost);
for(var i = 0; i < _size; ++i)
{
Console.WriteLine("Worker[" + i + "] -> Task[" + _workers[i] + "]");
}
Console.WriteLine();
}
public Chromosome Crossover(Chromosome chr, Random rnd)
{
var child = new Chromosome(_size);
int index1 = rnd.Next(0, _size);
int index2 = rnd.Next(0, _size);
var diff = Math.Abs(index1 - index2);
while (index1 == index2 || diff + 1 >= _size )
{
index2 = rnd.Next(0, _size);
diff = Math.Abs(index1 - index2);
}
if (index2 < index1)
{
int tmp = index1;
index1 = index2;
index2 = tmp;
}
for (int i = 0; i < index1; ++i)
{
var task = GetTask(i);
child.Assign(i, task);
}
for (int i = index1; i <= index2; ++i)
{
var task = chr.GetTask(i);
child.Assign(i, task);
}
for (int i = index2 + 1; i < _size; ++i)
{
var task = GetTask(i);
child.Assign(i, task);
}
return child;
}
public void Mutation(Random rnd)
{
for (int i = 0; i < _size; ++i)
{
if (rnd.Next(0, 100) < 33)
Assign(i, GetRandomTask(rnd, _size));
}
}
public void Copy(Chromosome chr)
{
_cost = chr._cost;
_size = chr._size;
for(var i = 0; i < _size; ++i)
{
_workers[i] = chr._workers[i];
}
}
public int WorkerCost(int worker)
{
return _workers[worker];
}
public int Cost()
{
return _cost;
}
public int Size()
{
return _size;
}
public void SetCost(int cost)
{
_cost = cost;
}
public void Assign(int worker, int task)
{
_workers[worker] = task;
}
public int GetTask(int worker)
{
return _workers[worker];
}
public int GetRandomTask(Random rnd, int taskRange)
{
return rnd.Next(0, taskRange);
}
public void Generate(Random rnd, int taskRange)
{
int count = 0;
foreach (var worker in _workers)
{
Assign(count, rnd.Next(0, taskRange));
count++;
}
}
}
}
Population.cs
Used to maintain a population of solutions.
using System;
using System.Collections.Generic;
namespace LinearAssignmentProblem
{
public class Population
{
private List<Chromosome> _chromosomes;
private long _bestChromosomeCost;
private int _bestChromosomeIndex;
private Chromosome _bestChromosome;
private bool _maximise;
public Population(Random rnd, int populationSize, int taskSize, bool maximise=true)
{
_bestChromosomeCost = maximise ? -1 : 9999999999;
_bestChromosomeIndex = -1;
_chromosomes = new List<Chromosome>(populationSize);
_maximise = maximise;
CreateArbitraryPopulation(rnd, populationSize, taskSize);
}
public void CreateArbitraryPopulation(Random rnd, int populationSize, int taskSize)
{
for(var i = 0; i < populationSize; ++i)
{
_chromosomes.Add(new Chromosome(rnd, taskSize));
}
}
public void Evaluate(CostMatrix costMatrix, int iteration)
{
for (var i = 0; i < _chromosomes.Count; ++i)
{
var cost = costMatrix.GetChromosomeCost(_chromosomes[i], _maximise);
_chromosomes[i].SetCost(cost);
if (IsBetter(cost, _bestChromosomeCost))
{
_bestChromosomeCost = cost;
_bestChromosomeIndex = i;
_chromosomes[_bestChromosomeIndex].Print(iteration);
}
}
}
public void ApplyCrossover(Random rnd, int taskSize)
{
var size = _chromosomes.Count;
foreach (var chromosome in _chromosomes)
{
var prob = rnd.Next(0, 100);
if (prob < 50)
{
var index1 = rnd.Next(0, size);
var index2 = rnd.Next(0, size);
while (index1 == index2)
{
index2 = rnd.Next(0, size);
}
Crossover(index1, index2, rnd, taskSize);
}
}
}
public void Crossover(int parentIndex1, int parentIndex2, Random rnd, int taskSize)
{
var chr1 = _chromosomes[parentIndex1];
var chr2 = _chromosomes[parentIndex2];
var child1 = chr1.Crossover(chr2, rnd);
var child2 = chr2.Crossover(chr1, rnd);
_chromosomes[parentIndex1].Copy(child1);
_chromosomes[parentIndex2].Copy(child2);
}
public void Mutate(Random rnd)
{
foreach(var chromosome in _chromosomes)
{
var prob = rnd.Next(0, 100);
if (prob < 5)
{
chromosome.Mutation(rnd);
}
}
}
public void StoreBestSolution(int taskSize)
{
_bestChromosome = new Chromosome(taskSize);
_bestChromosome.Copy(_chromosomes[_bestChromosomeIndex]);
}
public void SeedBestSolution(Random rnd)
{
var index = rnd.Next(0, _chromosomes.Count);
while (index == _bestChromosomeIndex)
{
index = rnd.Next(0, _chromosomes.Count);
}
_chromosomes[index].Copy(_bestChromosome);
}
public void Selection(Random rnd)
{
var size = _chromosomes.Count;
for (var i = 0; i < size; ++i)
{
var prob = rnd.Next(0, 100);
if (prob < 20)
{
var index1 = rnd.Next(0, size);
var index2 = rnd.Next(0, size);
while (index1 == index2)
{
index2 = rnd.Next(0, size);
}
var cost1 = _chromosomes[index1].Cost();
var cost2 = _chromosomes[index2].Cost();
if (IsBetter(cost1, cost2))
{
_chromosomes[index2].Copy(_chromosomes[index1]);
}
else
{
_chromosomes[index1].Copy(_chromosomes[index2]);
}
}
}
}
private bool IsBetter(long cost1, long cost2)
{
return _maximise ? cost1 > cost2 : cost1 < cost2;
}
}
}
Algorithm.cs
Used to apply genetic operators.
using System;
namespace LinearAssignmentProblem
{
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, CostMatrix costMatrix, int tasks)
{
var iteration = 1;
_population.Evaluate(costMatrix, iteration);
while (iteration < 1000)
{
_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 I use the same problem as demonstrated by Prof.G.Srinivasan, Department of Management Studies, IIT Madras on his YouTube video, shown at the following link:
https://www.youtube.com/watch?v=BUGIhEecipE
In the example lesson the optimal solution is determined to be 51 by assigning the following tasks:
Worker 1 -> Task 1 = 11 +
Worker 2 -> Task 3 = 7 +
Worker 3 -> Task 4 = 13 +
Worker 4 -> Task 2 = 10 +
Worker 5 -> Task 5 = 10
= 51 total.
This solution is obtained at the 15th iteration of the genetic algorithm as demonstrated by the screenshot below, albeit using zero-based indexing:
Here is a Visual Studio C++ implementation of the Hungarian algorithm available from here:
https://www.technical-recipes.com/Downloads/HungarianAlgorithm.zip
