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.
- The blue line
represents
the fitness of the incumbent.
- The green
line represents the average fitness of the current population.
- The red line represents the lowest fitness in the current population.
To return from this page, press the back button in your
browser. To re-run the algorithm with the same
parameters, refresh the page.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
A | 34 | 31 | 20 | 27 | 24 | 24 | 18 | 33 | 35 | 19 |
B | 14 | 14 | 22 | 34 | 26 | 19 | 22 | 29 | 22 | 19 |
C | 22 | 16 | 21 | 27 | 35 | 25 | 30 | 22 | 23 | 23 |
D | 17 | 21 | 24 | 16 | 31 | 22 | 20 | 27 | 26 | 17 |
E | 17 | 29 | 22 | 31 | 18 | 19 | 26 | 24 | 25 | 14 |
F | 26 | 29 | 37 | 34 | 37 | 20 | 21 | 25 | 27 | 27 |
G | 30 | 28 | 37 | 28 | 29 | 23 | 19 | 33 | 30 | 21 |
H | 28 | 21 | 30 | 24 | 35 | 20 | 24 | 24 | 32 | 24 |
I | 19 | 18 | 19 | 28 | 28 | 27 | 26 | 32 | 23 | 22 |
J | 30 | 22 | 29 | 19 | 30 | 29 | 29 | 21 | 20 | 18 |
K | 29 | 25 | 35 | 29 | 27 | 18 | 30 | 28 | 19 | 23 |
L | 15 | 19 | 19 | 33 | 22 | 24 | 25 | 31 | 33 | 21 |
M | 27 | 32 | 27 | 29 | 29 | 21 | 19 | 25 | 20 | 27 |
To obtain the code for the used to solve this problem, click on the links below:
Genetic Algorithm Code
Graphing Code