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




Visual Basic Developer
Visual Basic Developers Guide to ASP and IIS: Build Powerful Server-Side Web Applications with Visual Basic. (Visual Basic Developers Guides)
ISBN: 0782125573
EAN: 2147483647
Year: 1999
Pages: 175

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net