Genetic Algorithms

    Both genetic algorithms and simulated annealing are evolutionary processes that may be utilized to solve search space and optimization problems. However, genetic algorithms differ substantially from simulated annealing.

    Simulated annealing is based on a thermodynamic evolutionary process, whereas genetic algorithms are based on the principles of Darwin’s theory of evolution and the field of biology. Two features introduced by GAs, which distinguish them from simulated annealing, are the inclusion of a population and the use of a genetic operator called “crossover” or recombination. These features will be discussed in more detail later in this chapter.

    A key component of evolution is natural selection. Organisms poorly suited to their environment tend to die off, while organisms better suited to their current environment are more likely to survive. The surviving organisms produce offspring that have many of the better qualities possessed by their parents. As a result, these children tend to be “better suited” to their environment, and are more likely to survive, mate, and produce future generations. This process is analogous to Darwin’s “survival of the fittest” theory, an ongoing process of evolution in which life continues to improve over time. The same concepts that apply to natural selection apply to genetic algorithms as well.

    When discussing evolution, it is important to note that sometimes a distinction is made between microevolution and macroevolution. Microevolution refers to small changes that occur in the overall genetic makeup of a population over a relatively short period of time. These changes are generally small adaptations to an existing species, and not the introduction of a whole new species. Microevolution is caused by factors such as natural selection and mutation. Macroevolution refers to significant changes in a population over a long period of time. These changes may result in a new species. The concepts of genetic algorithms are consistent with microevolution.

Background of Genetic Algorithms

    John Holland, a professor at the University of Michigan, developed the concepts associated with genetic algorithms through research with his colleagues and students. In 1975, he published a book, Adaptation in Natural and Artificial Systems, in which he presents the theory behind genetic algorithms and explores their practical application. Holland is considered the father of genetic algorithms.

    Another significant contributor to the area of genetic algorithms is David Goldberg. Goldberg studied under Holland at the University of Michigan and has written a collection of books, including Genetic Algorithms in Search, Optimization, and Machine Learning (1989), and more recently, The Design of Innovation (2002).

Uses for Genetic Algorithms

    Genetic algorithms are adaptive search algorithms, which can be used for many purposes in many fields, such as science, business, engineering, and medicine. GAs are adept at searching large, nonlinear search spaces. A nonlinear search space problem has a large number of potential solutions and the optimal solution cannot be solved by conventional iterative means. GAs are most efficient and appropriate for situations in which:

• the search space is large, complex, or not easily understood;
• there is no programmatic method that can be used to narrow the search space;
• traditional optimization methods are inadequate.

    Table 6.1 lists some examples.

Table 6.1: Common Uses for Genetic Algorithms

    Many optimization problems are nonlinear in behavior and are too complex for traditional methods. The set of possible solutions for such a problem can be enormous (e.g., determining the optimum route for a traveling salesperson or determining the optimum design for an electrical circuit layout). A genetic algorithm possesses the ability to search large and complex search spaces to efficiently determine near optimal solutions in a reasonable time frame by simulating biological evolution. Now that you have been introduced to some of the uses for genetic algorithms, we must examine how to actually construct one.