Summary

Get the entire book!

In this chapter you were introduced to genetic algorithms. Genetic algorithms are one of the ways that programs can find potential solutions to complex NP-hard problems. A NP-hard problem is a problem where 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 salesmen problem attempts to seek the shortest path that a salesman would travel if he needed to visit a certain number of cities. The number of possible paths that a program would have to search increases factorial 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 these 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". This mating process combines the genes of the 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 three splices are then used to build a new chromosome. The result of all of this will be two child chromosomes. Unfortunately the mating process does not introduce new genetic material. New genetic material is introduced by mutation.

Mutation is also introduced to help find a optimal solution. One problem that arises from using only mating is that the only genetic material that will be used is that which is already in the population. 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 and will be purged from memory. However, others can be used to move on an otherwise stagnated population.

Genetic algorithms will be used to optimize the weight matrixes of neural networks. In the next chapter you will learn another technique, to solve NP-hard problems, called simulated annealing. Finally, in Chapter 10 we will apply both genetic algorithms and simulated annealing to neural network optimization.