Game Development Reference
Crossbreeding in a genetic algorithm involves how we select which parent pro-
vides each characteristic of the child. There are a number ways to make the
selection, but it is worth emphasizing that the process is selection, not averaging.
The child car will not have the toe angle set to the average of the two parents; it
will get the exact toe angle value from one of them.
Mutation calls for changing a value in a child randomly to something other than
the two values present in the parents. At first glance, it may seem that if the
starting population is diverse enough, there is no need for mutation. However,
the selection process will tend to suppress diversity as it emphasizes fit indivi-
duals who are likely to resemble each other. Diversity is required to keep the
algorithm from falsely converging early on a sub-optimal solution.
If we are to keep our population from growing without bound, we need to figure
out which individuals are not going to make it to the next run. An obvious
method is to replace the worst individuals. Another method would be to replace
the members who score closest to the new individuals. Doing selection this way
also helps keep a diverse population.
There are many reasons for stopping the algorithm. If the new generations have
stopped improving, then perhaps the optimal population has been found, and
there is no reason to continue. If the latest generation has individuals that are
''good enough,'' then it may be time to go on to other things. If each generation
takes a large amount of computation, time will be a limiting factor. And finally, if
the original population contains individuals thought to be optimal, a few gen-
erations may be all that is needed to confirm their status.
Genetic algorithms are good at getting close to an optimal solution, but they can
be very slow to converge on the most optimal solution. If the problem can be
expressed in terms of genes and fitness, the algorithm gives us a way to search
arbitrarily complex spaces. It does not need heuristics to guide it or any expertise
in the area searched. Our search speed will depend heavily on how expensive our
fitness function is to run.
Behavior trees made it on to the industry's radar in a big way with Damian Isla's
paper at the 2005 Game Developers Conference [Isla 2005]. The paper was about
managing complexity in the AI. Behavior trees bring welcome relief to that
problem area without introducing any new major problems of their own.