Example: Finding F(x) = x^2

Encoding: to find the maximum F(x) = x^2 over the interval 0-31, we can represent each possible solution as a binary string of 5 bits.

Initialization: begin with a random population of (say) 4 strings, each with 5 bits (eg., 01101, 11000, 01000, 10011).

Evaluation: determine the fitness of each string x in the population by evaluating F(x)=x^2. In this case, the fitness values are 169, 576, 64, 361, with an average value of 293 and a maximum of 576.

Reproduction: sum the fitness functions (1170) and reproduce each string in the new population in proportion to its contribution to this sum (eg., 14.4%, 49.2%, 5.5%, 30.9%).

• Choose a random number r between 1 and 1000.
• If r <= 144 select 01101 elsif 145 <= r <= 636 select 11000
  elsif 637 <= r <= 692 select 01000 else select 10011.
• Repeat 4 times, or once for each individual in the population.

Crossover: choose two strings in the new population at random, choose a crossover point within the strings at random, and exchange the upper parts of the two strings.

At crossover point 4, strings 01101 and 11000 mate and produce 01100 and 11001. At crossover point 2, strings 11000 and 10011 mate and produce 11011 and 10000.

Mutation: with small probability (.001), on a bit-by-bit basis, change each bit in the new population. We expect 0.02 bits to change (20 bits * .001); none do in our example.

Evaluation: the fitness function for the new strings is 144, 625, 729, 256, with an average of 439 and a maximum of 729.

Observations

The previous example (find the maximum of F(x)=x^2) doesn't appear to be a search problem. We can compute the maximum easily, since we know the function F(x) is monotonically increasing. However, in the general case the fitness function isn't monotonic, and a simple computational approach doesn't work.

The encoding is often a simple matter of expressing integers in binary form. However, some problems require more complex encodings, as when the strings represent real numbers rather than integers, or when the function has more than one parameter.

• We can use a fixed point, scaled integer to represent a real number.
• We can encode multiple numbers within a single string by assigning some number of bits to each value (aka a concatenated, multiparameter, mapped, fixed-point coding).

Many people believe that mutation amounts to random search. In addition, mutation should be very infrequent, and therefore isn't likely to impact the search significantly. Thus, many genetic algorithm programs don't implement mutation.

The effectiveness of the search depends on the population size and the number of generations.

• The larger the population, the more likely that our initial population is representative of the search space, and the more likely that a probabilistic survival-of-the-fittest mechanism produces the expected outcomes.
• Each successive generation should improve the fitness of the result, so longer runs usually produce better solutions.

Why do Genetic Algorithms Work?

How does a GA differ from random search?

What information is contained in the strings and their fitness values, that allows us to direct the search towards improved solutions?

• Similarities among the strings with high fitness value suggest a relationship between those similarities and good solutions.
  • A schema is a similarity template describing a subset of strings with similarities at certain string positions.
  • Crossover leaves a schema unaffected if it doesn't cut the schema.
  • Mutation leaves a schema unaffected with high probability (since mutation has a low probability).
  • Highly-fit, short schema (called building blocks) are propagated from generation to generation with high probability.

• Competing schemata are replicated exponentially according to their fitness value.

• Good schemata rapidly dominate bad ones.