Heuristics1:
Genetic Algorithm
A genetic algorithm is a heuristic method for finding approximate solutions to optimization problems. It maintains a population of solutions at all times, not just a single solution. The individuals in these populations change over time, and at termination the algorithm returns the best solution that it has seen in any population since the beginning. Genetic algorithms use ideas from evolutionary theory, including survival of the fittest, combining characteristics from parents to create children, and mutation, to create successive generations of individuals that evolve to better solutions.
An assignment problem is described below. Note that assignment problems can be solved quickly and accurately using linear programming, but we use this example because it is easy to understand. 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 maximum score. Note that there are 10 jobs but 13 people, so 3 people are not assigned a job. The genetic algorithm is formulated as follows:
The chromosome string consists of a permutation of the numbers 1-13, indicating which job each person gets, where jobs 11, 12, and 13 mean the person is not assigned a job at all. For example, this string: 9-2-5-4-1-11-3-12-6-13-8-7-10 indicates that person A does job 9, person B does job 2, person C does job 5, etc. Persons F, H, and J are not give jobs at all (they are assigned to phantom jobs 11, 12, and 13).
The fitness value is calculated from the table, given the assignment in the string.
To make sure that every string is a permutation of the numbers 1-13 with no elements missing or repeated, we use partially matched crossover.
There are two possibilities for the initial population:
Random initial population. Strings are random permutations of the numbers 1-13.
High quality initial population. Choose a person at random and assign them to the task with the highest return. Remove the person and the task from consideration. Repeat until all persons and tasks are assigned.
Stopping conditions are: (i) a specified maximum number of generations, or (ii) a set number of populations in a row for which the worst member of the population does not change.
The control parameters that affect the solution are the initial population type and size, the mutation rate, and the two stopping conditions. You can adjust these parameters and see how the outcome is affected. The best possible result for this problem is 323. Run the algorithm multiple times to see how close it comes to this maximum value, and how long it takes to do so.
Running the Genetic Algorithm Solver:
Set the values of the control parameters below and press the Start button. This will bring you to page displaying a graph of the results.
The green line shows the fitness of the incumbent (best solution ever seen).
The blue line shows the average fitness of the current population.
The red line shows 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 control parameter values, refresh the page.
Experiments to Try:
With the random initial population, try altering the population size, mutation rate, and termination conditions to see which set of parameters most often gives the best result the quickest. For comparison, a good set of parameter settings is population size 100, mutation rate 1%, maximum generations 1000, and worst value iterations 15.
Now switch to the high quality initial population and notice whether the initial best solution and final solution are generally better than with the random initial population. Recall that the best possible solution has a score of 323.