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%).

Using random numbers, we selected 01101, 11000, 11000, and 10011. The string 01000 perished.

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.

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.


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?