Industrial Applications of Genetic Algorithms:Genetic Algorithms in the Engineer's Toolbox

Previous | Table of Contents | Next

New populations of candidate solutions are generated by implementing operators inspired by natural genetic variation. The three most popular operators used in almost all GAs, are:

  1. selection,
  2. recombination (often termed crossover), and
  3. mutation.

Selection is a process through which high quality candidate solutions are chosen to form a basis for subsequent generations of solutions. Selection operators are generally driven by probabilistic decisions that ensure the best solutions are given the greatest consideration. Recombination is an operation by which the attributes of two quality solutions are combined to form a new, often better solution. This operator plays a key role in determining how the quality attributes of the candidate solutions are combined. Mutation is an operation that provides a random element to the search. It allows for various attributes of the candidate solutions to be occasionally altered. Together, these three operators produce an efficient search mechanism that generally converges rapidly to near-optimal solutions.

Given a coding scheme, a fitness function, and specific genetic operators, it is rather straightforward to develop a GA that mimics natural evolution to effectively drive toward near-optimal solutions. Despite the fact that the particulars of any GA application may vary, the basic approach is the same. The fundamental algorithm is summarized as follows:

  1. Generate a random initial population of candidate solutions in the form of chromosomes.
  2. Evaluate each chromosome in the population according to a pre-defined fitness function.
  3. Employ a selection operator to create new chromosomes. The selection operator biases the new generation of chromosomes toward higher quality solutions. As the chromosomes mate, genetic operators such as recombination and mutation are applied to form new candidate solutions.
  4. Delete members of the existing population to make room for the new candidates.
  5. Evaluate the new chromosomes and insert them into the population.
  6. If a satisfactory solution has been achieved (or if some other stopping criteria has been met), stop; otherwise, go to step 3.

This approach to solving search problems may seem unusual at first consideration. However, GAs demonstrate at least three characteristics which allow them to perform efficiently in difficult search spaces. First, GAs consider a population of solutions simultaneously. Thus, they tend to maintain a global perspective due to their parallel consideration of solutions, whereas traditional search routines tend to perform local searches due to the point-by-point manner in which they traverse a search space. Second, GAs do not rely on derivative information. Thus, they tend not to get fooled in multi-modal search problems that perplex derivative-based techniques so popular in the field of optimization. Third, GAs do not depend on continuity of the search space. Thus, they have been used to solve problems that have stymied more traditional search routines which can break down when applied in discontinuous search spaces.

Although GAs have been used to solve a wide variety of problems, most GA applications fall into one of three categories: (1) optimization, (2) machine learning in the form of learning classifier systems, and (3) genetic programming. The optimization applications are characterized by evaluation functions that are indicative of some desired result. Classic examples of optimization problems are those in which some profit measure must be maximized or some error term must be minimized. However, GAs have expanded their horizons well beyond traditional optimization. A second use of GAs is in learning classifier systems which employ a GA for developing effective if-then rules for solving a particular machine learning problem. GAs are used in these systems as discovery and adaptive engines that drive a rule base toward an effective solution. A third use of GAs is genetic programming [8], an approach to problem solving in which a GA is used to discover entire computer programs. Candidate programs are represented as tree-like symbolic expressions (S-expressions), and a GA breeds existing programs to develop new, more effective programs. As always, the search for more efficient computer programs is driven by a fitness function.

GAs and evolutionary algorithms of all types can be quite fascinating and are growing in popularity. However, they are by no means some “fly-by-night” approach to problem solving; GAs are well grounded in theory, and empirical studies demonstrate that, in some problems, they consistently outperform more traditional search routines. Although GAs are a very young technology, their brief history is rich with success stories and peppered with researchers from diverse backgrounds. The next section provides a flavor of this rich history and mentions some of the researchers who have elevated GAs to their current status in the computational community.

Previous | Table of Contents | Next

Copyright © CRC Press LLC