artificial life

Chapter 5: Genetic Algorithms

5.5 Analysis of Results

A difficulty that arises with genetic algorithms is that it is never certain when an optimal solution is found. The instance in Figure 5.1 has an optimal solution of 155. The randomly generated solutions had a best individual with a fitness of 85, this is 55% of the optimal solution. A single crossover operation produced an individual with a fitness of 120, this is 77% of the optimal solution, showing an increase of 22% in one generation. Gains of this magnitude are certainly not maintainable. There is a point where the increase in fitness from one generation to the next becomes negligible and the cost of continuing the search outweighs the benefit of actually finding the optimal solution.

Figure 5.3 shows the progression of fitness values over 100 generations. This GA had a possible knapsack of 18 items and a population size of 50. The top set of points represents the fitness of the best individual in that generation. The bottom set of points is the average fitness of that generation. Even though this instance actually succeeds in finding the optimal solution (a fitness of 256 is found in the 97th generation) the genetic algorithm finds a nearly optimal solution very early on, and doesn’t make progress for a long while.

To naively search through all solutions of a 0-1 knapsack problem increases in complexity by the rate of 2n with n being the number of possible items to be put in the knapsack. For the example in Figure 5.1 there are 1024 possible solutions. In the instance graphed in Figure 5.3 there are 262144 possible solutions. In Figure 5.2 a solution of approximately 80% the optimal is found in the 8th generation. Since the population size was 50, the genetic algorithm found this solution after inspecting no more than 400 possible solutions. It inspected less than 2 tenths of one percent of the search space, yet found a solution that was 80% of the optimal solution. It actually found the optimal solution after less than 100 generations, checking fewer solutions than would be found in 2% of the total search space.

The performance of GA’s does not degrade as problems increase in complexity either. In fact, their performance is actually better as the problems increase in complexity. Figure 5.4 shows a graph similar to the one found in igure 5.3. The population size is still 50 and the GA still finds the optimal solution in less than 100 generations (around 40 this time). The difference is that there are now 23 possible items for the Knapsack. This produces a search space of 8388608 possible solutions.

The optimal solution is found in under 40 generations so at this point the GA has exhausted less than 5 hundredths of one percent of it’s search space.

The power of genetic algorithms is shown in their ability to give reasonably good solutions in a fraction of the time it would take otherwise.