G e n e t i c A l g o r i t h m s O n
N e t a d e l i c a
Genetic algorithms (GAs) simulate the process of biological evolution on
a computer. They are used to find highly fit solutions to problems where
the possible solutions are too numerous to be evaluated individually.
You work with a population of individuals ("members"). Each member
comprises a set of genes (numbers of arbitrary base, often 2). The
process is roughly as follows:
- Create an initial population of randomly-generated individuals
- Evaluate each member's fitness ("fitness" depends entirely on the
task in hand; a member's fitness might be how many 1s its genes contain,
or how well it plays chess using its genes as "weights" for various
evaluation parameters)
- Kill the bottom x% (least fit) of the population (often 50%)
- Let the fittest members breed ("reproduction"):
- Choose two members for breeding ("selection") - lots of
variations here: e.g. either select two at random ("uniform"), or weight
the selection according to a member's fitness ("fitness-proportionate")
- Breed them ("crossover" - more options here: e.g., a child
can be formed by single-point crossover (the parents' genes are swapped
over at some random point along their chromosome), two-point crossover
(the parents' genes are swapped over at two random points), uniform
crossover (the parents' genes are selected bit-by-bit randomly), and
weighted crossover (the parents' genes are selected bit-by-bit randomly
but weighted according to each parents' fitness)
- Apply mutation - each gene of the child is subject to a small chance of
mutating to a different allele (an allele is a possible value for a
gene, in binary, the alleles are "0" and "1") - a common mutation rate
is 0.001
- The children form the new population of members
- Go to step 2 until you've evolved a suitably fit member or population
Back to the Netadelica GA home page
Back to the Netadelica home page