Applying a genetic algorithm to the Linear Assignment Problem

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: [code language="csharp"] 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); } } } [/code] CostMatrix.cs Used to maintain the cost of each task for each worker. [code language="csharp"] 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; } } } [/code] Chromosome.cs Used to encode solutions. [code language="csharp"] 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++; } } } } [/code] Population.cs Used to maintain a population of solutions. [code language="csharp"] 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; } } } [/code] Algorithm.cs Used to apply genetic operators. [code language="csharp"] 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++; } } } } [/code] 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