GAs and Search Spaces

• Each gene is a state in a search space.
• This space can be really big. Just 10 cities is 10,000,000,000.
• What cross-over and mutation do is search through the space by making new members of the space.
• The system is searching for the gene that is best or at least some genes that are good (and good means the evaluation function gives it a good value).
• If you think of the space of 10 cities, it is 10 dimensional.
• If you mutate one gene, you move along one of the dimensions.
• If you combine two, rather different genes, with cross-over, you go to two really quite different places in the space.
• If you mutate each element of gene, you can go to any place in the space. (It's eventually an exhaustive search.) If you do it with a low probability, it still goes everywhere eventually.
• The key is that cross over needs to help you find good parts of the space, and that they combine sensibly.