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	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

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

Previous Example

Main Menu

Next Example

	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

	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

	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