# Problems with the Genetic Algorithm

## Problems with the Genetic Algorithm

The genetic algorithm is not without its problems. This section will discuss some of the issues that should be understood when applying the genetic algorithm.

### Premature Convergence

The problem of premature convergence is one of a lack of diversity within the population. When a majority of the chromosomes in the population is similar, the selection process has less material to work with and the rate of fitness increase slows. Premature convergence can be detected by comparing the average fitness of the population with the maximum fitness. If they are fairly close to one another, then premature convergence has occurred.

The most common reason for premature convergence is a population that is too small for the problem. Increasing the size of the population easily solves this problem. Another common reason is the selection algorithm used. If an elitist algorithm is used, only the highest-fit chromosomes may be selected, leading to a population that is likely descendent from a small percentage of the initial population. One solution here is called restart. This simply means that if the population has prematurely converged without finding a decent solution, simply start over. The desire is that by restarting, new material will be introduced into the population that may not have a small number of dominating chromosomes.

### Epistasis

Epistasis is defined as the interdependence among the variables (genes) encoded in the chromosome. If no gene is related to another in the chromosome, epistasis is small or non-existent. If genes are dependent on one another, epistasis is high and can create difficulties for the recombination algorithms.

A common solution to the problem is to keep genes (variables) that are related close to one another in the chromosome. Grouping the dependent genes means they are much less likely to be disrupted during operators such as crossover.

### The "No-Free-Lunch" Theorem

The "No-Free-Lunch" theorem is based upon the idea that there is no optimal optimization method. Any encoding, selection-method, and set of parameter probabilities will not blindly work for all classes of problems. The key is to use knowledge of the problem at hand to choose the best approach [Shaffer 1993].

## Other Applications

The genetic algorithm can be used in a variety of optimization problems. Since the usefulness of the genetic algorithm depends most highly on the representation of the solution, any number of numerical and symbolic problems may be optimized. For example, in addition to simple function optimization, symbolic problems such as the Towers of Hanoi problem can be very easily solved .

Genetic algorithms have been applied to many other practical applications, such as:

• Computer-Aided Design

• Scheduling Problems

• Economics and Game Theory

• many others

The author has applied the genetic algorithm, as part of star tracker research, to the problem of absolute attitude determination using a star tracker. In this application, star quadrilaterals were matched from an onboard star catalog to a set of stars in the star-tracker's field of view to determine where the spacecraft was pointing.

## Summary

In this chapter, we've had our first look at the genetic algorithm. We discussed the general operation of the algorithm and a saw sample run through the algorithm to demonstrate initialization, fitness evaluation, selection, and recombination. We then discussed source code that implements an evolver for instruction sequences and looked at some of the sample equations that were solved with it. Since the GA knows nothing about the equations themselves , only if it's correct in solving them, the GA provides alternate solutions to the problem (within the defined instruction set) that demonstrated an optimization of the actual algorithm. Finally, we discussed the parameters that can be tweaked for the genetic algorithm and some of the problems that the algorithm presents .