Genetic Algorithms

Like memory-based reasoning and neural networks, genetic algorithms are based on an analogy to biological processes. Evolution and natural selection have, over the course of millions of years, resulted in adaptable, specialized species that are highly suited to their environments. Evolution optimizes the fitness of individuals over succeeding generations by propagating the genetic material in the fittest individuals of one generation to the next generation.

Genetic algorithms apply the same idea to problems where the solution can be expressed as an optimal individual and the goal is to maximize the fitness of individuals. Many problems can be described in this way; the challenge is encoding the problem in the right fashion. For instance, one application of genetic algorithms is to the training of neural networks. An individual is then a set of values for the weights inside the network; the fitness of an individual is the accuracy of the neural network having those weights on the training set. The training proceeds in an evolutionary way, by having more fit individuals propagate their weights to succeeding generations. Less fit individuals-and their genetic material-do not survive. Although chance plays a significant role in the survival of any particular individual, over a larger population there are enough examples of different types of individuals for natural selection to propagate the genetic material that produces the fittest individuals.

Genetic algorithms, which are also called evolutionary algorithms, have been applied to optimization problems in various industries, including complex scheduling problems, resource optimization in large factories, and classification

problems involving complex data types. They have also been used in combination with other data mining algorithms, including determining the best topology for neural networks, determining the scoring function for memory-based reasoning, and, as already mentioned, optimizing weights in neural networks. However, genetic algorithms are not commonly found in general data mining packages.

OPTIMIZATION

Optimization problems have three features:

♦ A set of parameters (which for GAs are called genomes or chromosomes)

♦ A function that combines the parameters into a single value (the fitness function)

♦ A set of constraints on the parameters (for GAs these are incorporated into the fitness function)

The goal is to find the parameters that maximize or minimize the fitness function, subject to the constraints. Searching through all combinations of parameters that meet the constraints is too cumbersome for even the most advanced computers; even for a small number of parameters, the number of combinations is too large to search.

Genetic algorithms are one approach to solving such problems, but not the only one. When the fitness function satisfies some specific mathematical conditions, then differential calculus can be used to find the optimal solution. Although few functions in practice are differentiable, calculus also includes ideas for estimating solutions in other cases. The conjugate-gradient method for training neural networks is based on such ideas, as is the solver capability in Excel.

Another approach arises with linear programming problems. These are problems where the fitness function is linear and all the constraints are also linear. These constraints are often met in resource allocation problems, such as: A company produces widgets in a set of factories. Each factory has a capacity, a cost of production, and a cost for transporting widgets to customers. How many widgets should each factory produce to satisfy customer demand at minimal cost? The standard method for solving such problems is called the Simplex method, and it is computationally efficient. Such problems have been solved with thousands of variables. Further information on linear programming type problems is available on the linear programming FAQ at www-unix.mcs.anl. gov/otc/Guide/faq/linear-programming-faq.html.

Another approach is called simulated annealing. This uses an analogy to a physical process: some liquids cool and form crystalline patterns as they cool. The crystal minimizes certain types of energy, and this happens across the entire crystal. Scientists studying physical properties are the most common users of simulated annealing.

Team-Fly®