Game Development Reference
In-Depth Information
A chromosome in a genetic algorithm is represented by a string of numbers.
Each chromosome is divided into a number of genes made up of one or more
of the numbers. The numbers are usually binary; however, they need not be
restricted to such.
Steps involved in a genetic algorithm are:
Create a population and determine the fitness
A genetic algorithm begins by specifying the length of a chromosome
and the size of the population. A 4-bit chromosome would look like 1100.
Each individual in the population is given a random 4-bit sequence. The
population is then allocated some task. How each individual performs
determines its fitness. For example, if the task is to walk away from a
starting location, then individuals who walk the farthest are the fittest.
Mate the fittest individuals
The population is sorted according to fitness and the top proportions
of the group are mated. This involves crossing their chromosomes to
create new individuals. The process of crossover involves slicing the
chromosomes and mixing and matching. For example, parents with
chromosomes 0011 and 1100 with their chromosomes sliced half-way
will produce offspring with chromosomes 0000 and 1111.
In nature, a rare event occurs in breeding called mutation . Here, an
apparently random gene change occurs. This may lead to improved
fitness or, unfortunately, a dramatically handicapped offspring. In
evolutionary computing, mutation can reintroduce possibly advantageous
gene sequences that may have been lost through population culling.
Introducing new randomly generated chromosomes into the population
or taking new offspring and flipping a gene or two randomly can achieve
mutation. For example, an individual with a chromosome 0101 could be
mutated by flipping the third gene. This would result in 0111.
Introducing the new population
The final step is to introduce the new population to the task at hand. Before
this occurs, the previous population is killed off. Once the new population's
fitness has been determined, they are again sorted and mated.
The process is a cycle that continues creating and testing new populations
until the fitness values converge at an optimal value. You can tell when this
has occurred as there will be very little change in the fitness values from
population to population.
An example of a working genetic algorithm can be found in the Unity project
available from the Web site as a download from Chapter Five/GeneticAlgorithms
.zip. In this project, NPCs are programmed to navigate a maze based on genetic