The second operator, crossover, affords a means for strings to mix and match their desirable qualities through a random process. After reproduction, simple crossover proceeds in three steps. First, two strings are selected from the mating pool. Second, a position along the strings is selected at random. This is shown as follows, where two binary coded strings X and Y (strings number 1 and 2 in the mating pool) are selected for crossover:

Crossing site 3 has been selected in this particular example, although any of the other six positions could have been selected. The third step is to exchange all characters following the crossing site. The two new strings produced by this crossover are shown as X’ and Y’:

String X’ is made up of the first part of string X and the tail of string Y. Likewise, string Y’ is made up of the first part of string Y and the tail of string X. Crossover is an effective means of exchanging information and combining portions of high-quality solutions to obtain even better solutions. Although crossover has a random element, this operator does not result in a random search. Table 5.7 depicts the population after crossover has been applied.

The mechanics of the reproduction and crossover operations are quite simple; they involve nothing more than making copies of strings and exchanging portions of strings. However, reproduction and crossover together give GAs most of their power.

The third operator, mutation, protects the ability of the GA to find near-optimal solutions. Mutation is the occasional alteration of a bit at a randomly selected position in a string. It insures against the loss of a particular piece of information. Reproduction and crossover may together create a generation that is void of a particular character at a given string position. For example, a generation may arise that does not have a 1 in the third string position. Neither reproduction nor crossover will ever produce a 1 in this third position in subsequent generations. The mutation operator simply flips bits from 1 to 0, or 0 to 1 at random. Thus, mutation allows a 0 in the third position to be changed to a 1, thereby reinstating the critical piece of information into the population. Although mutation is a vital part of any GA, it occurs with a small probability (on the order of one mutation per thousand string positions). Since mutation is performed with such a small probability, in our example in which there are 5*8=40 bit positions, the random forces driving mutation did not change any bits in the first generation, so that the second generation is the same as that shown in Table 5.7 above.

At this point, we have developed a second generation of strings that contains better solutions to the search problem than existed in our initial, randomly generated population. We now go back to the beginning and decode our strings, evaluate their fitnesses, and apply the three operators again. We continue with this process of generating new populations until we decide to stop (and there are numerous stopping criteria including reaching a maximum number of generations, finding an acceptable fitness value, and running until some environmental factor dictates that we stop).

Figure 5.1 shows graphically the best solution found by the GA at selected generations to give the reader an indication of how this process proceeds through the search space. Each figure includes the optimum solution for comparison purposes. Notice that after only 10 generations, the GA has found a solution that is very close to the optimum. Additionally, Figure 5.2 shows the strings present in various generations. The values associated with the strings in various generations are plotted on an m-b axis system. The plotted points in a particular generation seem to be converging on the theoretical best solutions. The figures show the sampled points in the search space at selected generations. Notice that even though the GA continues to sample points throughout the search space defined by the parameters b and m, most points in later generations cluster about the best solution.

Figure 5.1  As the GA considers more and more alternatives, its “proposed” solutions move closer and closer to the optimum.

Figure 5.2  Notice that the population of points seem to converge to the correct solutions as the number of generations increases.

This has been a brief overview of a simple GA. For further details of the processing power and the convergence properties of GAs, refer to Goldberg (1989) or Davis (1991).