Example 1: 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
2345
678910
A3431
20272424
18333519
B1414
22342619
22292219
C2216
21273525
30222323
D1721
24163122
20272617
E1729
22311819
26242514
F2629
37343720
21252727
G3028
37282923
19333021
H2821
30243520
24243224
I1918
19282827
26322322
J3022
29193029
29212018
K2925
35292718
30281923
L1519
19332224
25313321
M2732
27292921
19252027
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