Chapter Summary

    In this chapter, you were introduced to genetic algorithms. Genetic algorithms provide one approach for finding potential solutions to complex NP-hard problems. An NP-hard problem is a problem for which the number of steps required to solve the problem increases at a very high rate as the number of units in the program increases.

    An example of an NP-hard problem, which was examined in this chapter, is the traveling salesman problem. The traveling salesman problem attempts to identify the shortest path for a salesman traveling to a certain number of cities. The number of possible paths that a program has to search increases factorially as the number of cities increases.

    To solve such a problem, a genetic algorithm is used. The genetic algorithm creates a population of chromosomes. Each of the chromosomes is one path through the cities. Each leg in that journey is a gene. The best chromosomes are determined and they are allowed to “mate.” The mating process combines the genes of two parents. The chromosomes that have longer, less desirable, paths are not allowed to mate. Because the population has a fixed size, the less desirable chromosomes are purged from memory. As the program continues, natural selection causes the better-suited chromosomes to mate and produce better and better solutions.

    The actual process of mating occurs by splitting the parent chromosomes into three splices. These splices are then used to build new chromosomes. The result of all of this will be two offspring chromosomes. Unfortunately, the mating process does not introduce new genetic material. New genetic material is introduced through mutation.

    Mutation randomly changes the genes of some of the newly created offspring. This introduces new traits. Many of these mutations will not be well suited for the particular problem and will be purged from memory. However, others can be used to advance an otherwise stagnated population. Mutation is also introduced to help find an optimal solution.

    Thus far in this book you have been shown how to train neural networks with backpropagation and genetic algorithms. Neural networks can also be trained by a technique that simulates the way a molten metal cools. This process is called simulated annealing. Simulated annealing will be covered in the next chapter.