15.1 Evolutionary Process

< Day Day Up >

15.1 Evolutionary Process You can break down the implementation of genetic algorithms in games into four steps. Figure 15-3 illustrates this four-step process. Figure 15-3. Evolutionary process As Figure 15-3 shows, the first step involves creating the first generation. The entire population is seeded with a set of starting traits. Once the population starts interacting with its environment, we need a way to rank the individual members. This is the process of ranking fitness. This tells us which members of the population are the most successful. The process of ranking fitness aids us in the next step, which is selection. In the selection process we choose certain members of the population to create the next generation. We essentially use the most successful traits of the previous generation to create the next generation. The actual step of combining these traits to create a new, and hopefully fitter, generation is referred to as evolution. Genetic algorithms are essentially optimization processes in which we're trying to find the fittest set of traits�we're looking for the optimum solution to a specific problem. 15.2.1 First Generation Each individual in the first generation represents a possible solution to the problem at hand. One way to approach the creation of the first generation is to arrange the chromosomes randomly. In a game environment, however, randomly arranging chromosomes might not always be the best solution. If the game designer already knows which combinations of chromosomes are likely to produce a fit individual, a true random combination probably won't be necessary. However, it is still important to create an initial diverse population. If the individuals are too much alike, the genetic process will be less effective. Encoding is the process of storing the chromosomes in a structure that can be stored in a computer. This, of course, can be any type of structure the programmer chooses to use. Genetic algorithms frequently use strings of bits, but arrays, lists, and trees also commonly are used. Figure 15-4 shows an example of a first generation of flowers. These hypothetical flowers would include random chromosomes that would affect how well they thrive in their environments. Figure 15-4. First generation 15.2.2 Ranking Fitness This step in the evolutionary process involves evaluating each member of the population. This is where we attempt to identify the most successful members of the population, and typically we accomplish this using a fitness function. The purpose of the fitness function is to rank the individuals in the population. This tells us which individuals are best at solving the problem at hand. Figure 15-5 shows how the flowers would be ranked. We assume the flowers that grow the tallest are the fittest. Figure 15-5. Ranking fitness 15.2.3 Selection In the selection step we choose the individuals whose traits we want to instill in the next generation. In the selection process typically we call the fitness function to identify the individuals that we use to create the next generation. In the biological world, usually two parents contribute chromosomes to the offspring. Of course, in game development, we are free to use any combination of parents. For example, we are free to combine the traits of the top two, five, 10, or any other number of individuals. Figure 15-6 shows how we use rankings calculated by the fitness function to determine which individuals to use when creating the next generation. In this case, we selected the two tallest flowers. Figure 15-6. Flower selection 15.2.4 Evolution In the final step we create new individuals to place into the game environment. We do this by using individuals from the selection process. We take the individual chromosomes from the fittest members of the population and begin combining their chromosomes. At this point it is also important to introduce random mutations. Once the evolutionary process is complete, we return to the fitness ranking step. The evolutionary step is where crossover occurs. This is where we combine the chromosomes of the fittest individuals. In this case, we combine the chromosomes of the two tallest flowers to create a new flower. We also introduce two random mutations. This is illustrated in Figure 15-7. Figure 15-7. Flower evolution

< Day Day Up >