Example Heuristics1: The Assignment Problem Using the Genetic Algorithm


The genetic algorithm is a heuristic method of finding approximate solutions to optimization problems.  This algorithm incorporates the evolutionary theory of the survival of the fittest, along with crossover and mutation, to create successive generations of individuals that evolve to a better solution.

Below is an assignment problem.  Each task must be performed by one person, A to M.  The table below shows how well each person performs each task.  Find the person-job assignment that produces the best score.  Note that in practice, this problem should be solved using linear programming!

The variables that may affect the outcome of the algorithm are the initial population size and the mutation rate.  You can adjust these variables and see how the outcome is affected.  You can also set the termination criteria.  Change the number of iterations the algorithm will do after a change in the incumbent, average fitness or fitness of the worst solution to see how the final result and the algorithm's speed  are affected.  The best possible result for this problem is 323.

Set the values of the variables below then press the Start button.  This will bring you to page displaying a graph of the results.

To return from this page, press the back button in your browser.  To re-run the algorithm with the same parameters, refresh the page.

12345678910
A34312027242418333519
B14142234261922292219
C22162127352530222323
D17212416312220272617
E17292231181926242514
F26293734372021252727
G30283728292319333021
H28213024352024243224
I19181928282726322322
J30222919302929212018
K29253529271830281923
L15191933222425313321
M27322729292119252027

Population:  Mutation Rate: Termination (iterations after last change):  
 


To obtain the code for the used to solve this problem, click on the links below:
Genetic Algorithm Code
Graphing Code