Bibliographic information:

Badros, Greg. 1995. Evolving Solutions: An Introduction to Genetic Algorithms. Vertices 10(2): 57-60.

One of the most fundamental problems in applied mathematics is that of optimization. Every student of calculus has been taught how to maximize and minimize simple functions. Consider as an example the function f(x) = 10-(x-2)^2. By differentiating f with respect to x, setting the derivative to 0, and solving for x, one can generate a list of possible local extrema for the function. While all optimization problems can be viewed as an extension of this simple problem, most unfortunately cannot be solved so easily. In more typical applications, the objective function (the one we would like to maximize or minimize) has more than one variable.

Although extra variables complicate matters, multivariable functions such as f(x,y) = sin(x)*cos(y) + cos(x)*sin(y) are still relatively easy to solve. So-called "hill-climbing" algorithms use partial derivatives to follow the path of steepest ascent or descent and find local extrema very efficiently. However, finding the global extrema can still be challenging: how do we choose from which point, or points, to begin our search? This question becomes even more important as we encounter functions with ten, fifty, or one hundred variables. Repeatedly applying the hill-climbing algorithm, or other similar optimization techniques, is computationally expensive.

Another complication is the fact that many functions are not so easily defined or differentiated. Not all functions can be written in terms of a mathematical expression, and many complex functions are difficult or impossible to differentiate. Such functions leave the hopeful scientist looking for another computational method. In an attempt to find other ways of solving these more realistic, less well-behaved optimization problems, other computational techniques have been investigated. One very popular method that shows some promise is the genetic algorithm.

The genetic algorithm (GA for short) is a combinatorial optimizer that is domain-independent; it is applicable to all functions that can be evaluated. Whereas hill-climbing and its relatives require domain-specific information (e.g., partial derivatives) to guide their searches, the genetic algorithm requires only two things: (1) a means of representing possible solutions and (2) an objective function evaluator--a function which maps a value from the domain of possible solutions to a scalar value. In the simplest terms, the genetic algorithm starts with a computer-created population of individuals each representing a point in the search space of a given function. Using an individual's objective function as a measure of how "fit" that individual is within its environment (the problem domain,) the genetic algorithm simulates nature's survival of the fittest, essentially forcing the evolution of an optimal creature. This optimal creature is then the solution to the corresponding optimization problem.

The genetic algorithm has been implemented in various forms since its introduction in the late 1960s. As its name suggests, the first research done on genetics-based algorithms was not motivated by unsolved optimization problems. Instead, these algorithms were designed as simulations of natural adaptive processes. Most researchers in the young field of adaptation-simulation used models with properties closely resembling natural phenomena. For example, the biological notions of diploid chromosomes and dominance were both frequently mimicked by early algorithms. John Holland, a professor at the University of Michigan, was one of the first researchers to carry out a substantial amount of work in the field. He recognized the broad applicability of genetics-based algorithms for optimization purposes, and this insight formed the basis for the modern notion of a genetic algorithm.

A simple analogy illustrates the similarity between nature's adaptive processes and an optimization problem. We can view nature's motivation in providing genetics, survival of the fittest, selective mating, reproduction, etc., as an attempt to create the most well-adapted species possible. In other words, nature needed to solve an optimization problem: what is the best-adapted species for a given environment? Nature's "genetic algorithm" was her solution. The computer scientist's genetic algorithm applies fundamentally the same approach to problems of interest to computer scientists, mathematicians, economists, engineers, and others.

The Classical Genetic Algorithm

Despite its power, the classical genetic algorithm is both elegant and simple. That such a simple, straightforward routine can accomplish so much is quite unexpected. The classic genetic algorithm contains only one main data structure: a population of individuals. Each individual, affectionately known as a critter, represents an element within the domain of the solution space of the optimization problem; i.e., each critter represents a possible solution to the problem. The issue of how to best represent a critter is very complex and has tremendous problem-solving implications. In the classical genetic algorithm, critters are simply strings of bits (binary digits - ones and zeros). Each string of ones and zeros is called a chromosome; the chromosome of a given critter is the only source for all the information about the corresponding solution. In biological terms, the chromosomal string is the genotype and the solution it represents the phenotype of a particular critter.

Associated with each individual is a fitness value. This value is a numerical quantification of how good of a solution to the optimization problem the individual is. Individuals with chromosomal strings representing better solutions have higher fitness values, while lower fitness values are attributed to those whose bit strings represent inferior solutions.

It is important to realize that only two elements of the classical genetic algorithm need to be changed in order to apply the algorithm to a new problem: the representation of the individuals and the objective functions. Consider, for example, one of the most basic problems the GA is applied to: One Max. The goal in One Max is to maximize the number of occurrences of the digit 1 in an arbitrarily long string of bits. As an example, let us assume that strings are eight bits long. The representation of an individual is thus a string of eight ones and zeros: 10110001, for example. Standard GA terminology refers to each bit position as a locus and to the values at the loci as alleles. The set of all symbols which an allele can assume is called the alphabet of the representation. In our example, the alphabet consists of 0 and 1.

Since the goal in One Max is to maximize the number of 1 bits, we need an objective function evaluator f which gives better ratings to individuals with more 1 bits. The obvious choice is the function which assigns as an individual's fitness value the number of ones in its representation; e.g., 10110001 has fitness four, while 00000000 has fitness zero. The goal, then, of our algorithm is to find the individual with fitness value eight: 11111111.

Now that we have a suitable representation and an appropriate objective function, the construction of our genetic algorithm is almost complete. One of the important parameters of any GA is population size - how many critters are maintained at any given time. In our One Max example, we will assume a population size of 4; populations are typically much larger, often 20 to 200. Since we intend to have four critters "alive" in the current population at any given time, the GA must create four individuals to form the initial population. In the classical genetic algorithm, these initial individuals are merely random bit strings. Thus our initial population might consist of the four individuals in table 1, where each Xi is a critter in the population (for now, the subscript simply distinguishes one critter from another).

Common sense tells us that some of the initial individuals are going to be better than others. That is, some bit strings will score higher fitness values, meaning they are better solutions to the One Max problem. Analogously, some of the critters in the initial population will be better adapted to their environment. In nature, those individuals that are better adapted survive longer and therefore yield more offspring. This survival of the fittest is mirrored in the genetic algorithm through reproduction, one of the three main genetic operators.

The classical GA thus creates a second generation of individuals. Since the population size must remain constant, however, each new individual must replace an old one. The classical GA creates a population of new individuals to replace the previous generation; in our example, the GA would create four new individuals. Each new individual will be identical to one of the individuals in the previous generation. The probability of a new critter being identical to a certain previous individual is proportional to that individual's fitness relative to the other individuals in that previous generation. Specifically, the probability of an individual Xk in the first generation reproducing is f(Xk) / … f(Xi).

We can thus list for each of the individuals in our initial population that individual's fitness value and the probability of it reproducing (Table 1). To continue with our One Max example, we will assume that X3 reproduces twice, that X1 and X2 each reproduce once, and that X4 -- the least fit individual -- fails to reproduce, thus yielding the new population shown in table 2.

The next step of the genetic algorithm distinguishes it from other domain-independent optimization techniques. In this step, the crossover operator--the second main genetic operator--is repeatedly applied to pairs of individuals. Suppose for example that critters one and three are chosen to mate (i.e., to be crossed.) This would leave critters two and four to be crossed. The process of crossing two individuals involves randomly selecting a locus and then swapping between the two individuals their genetic material following that locus. If in our example the crossover point selected for critters one and three were the fourth locus, the resulting strings would be 10111111 and 00101011 (above right). Likewise, if the sixth locus were selected as the crossover point for X2 and X4, the individuals 10111010 and 00111011 would be formed.

One crossover thus creates two new individuals, called offspring: one containing the beginning portion of the first individual followed by the ending portion of the second individual, and another containing the beginning portion of the second individual followed by the ending portion of the first individual (Table 3). After some portion of the population is crossed-over, we have a new population of individuals, each of which is either identical to an individual in the prior population or is the product of genetic recombination through crossover. Why bother with the crossover operator? As Holland explains, "the purpose of crossing strings in the genetic algorithm is to test new parts of target regions rather than testing the same string over and over again in successive generations." (Holland 1992:68)

Before evaluating the new population, one final genetic operator is applied: mutation. Mutation involves the flipping (switching 0 to 1 and vice versa) of alleles. A probability PM (which is usually rather low) is defined as the chance of any given allele being flipped. Each allele at each locus of each individual is a candidate for being flipped. In our One Max example, let us set PM=0.05. Since there are four individuals, each with eight loci, we would expect (4)(8)(PM)=1.6 mutations to occur. We will say that two occur, in locus two of X1 and in locus seven of X4. We thus have the resulting critters 11111111 and 00111001.

After mutation, our new population is in its final state (Table 4). The fitness values of the new individuals are evaluated by the objective function, and the new population is designated the current population, from which future generations will derive. As long as the completion criterion is not met, the three-step process of reproduction, crossover, and mutation is repeated. The completion criterion is generally either a perfect solution or a predetermined number of generations. In our rather simplistic One Max example, a fortunate sequence of events yielded a perfect solution after only one generation! In a more realistic application, it would not be unusual for the algorithm to continue for two hundred generations or more. When the algorithm does conclude, it gives as its solution to the optimization problem the individual in the final population with the highest fitness rating.

The repeated application of these three operators, each inspired by some aspect of natural selection, can thus solve some optimization problems. The reasons for the effectiveness of these operators are fairly clear. Building blocks (contiguous sequences of alleles) which are beneficial to an individual are recombined through crossover with other individuals' building blocks from different loci within the chromosomal string. Since more fit strings are selected more frequently for reproduction and crossover, the more fit building blocks will join to form better and better solutions. Mutation serves to reintroduce diversity into the population, thus insuring that no alleles are lost. In our One Max example, for instance, none of the original individuals contained a 1 at the second locus. Mutation of the second allele in some individual was therefore necessary before the perfect 11111111 chromosome could be produced.

The success we encountered in the One Max example is of course atypical. Nonetheless, variations of the genetic algorithm have been effectively applied to such diverse problems as game-evaluation, VLSI circuit design, classroom scheduling and natural gas pipeline control.

Problems with the Genetic Algorithm

While the genetic algorithm has achieved some definite success, it has its limitations. Things are not so simple that in order to solve any optimization problem, all we need to do is represent and evaluate individual solutions. Were this the case, we would in theory be able to mathematically discover the ultimate musical score: songs could be represented using MIDI (musical instrument digital interface, the standard computer protocol for musical data representation) data, and the objective function could be a panel of musicians; the fitness of an individual song could be the average of the panel's ratings. Our genetic algorithm would then be able to easily evolve a chart-busting hit!

Alas, songwriters will be safe for a while longer. The genetic algorithm has many limitations. The above example points to one: the computation of objective fitness values is non-trivial. It needs to be something a computer can do relatively quickly, since thousands--even millions--of individuals will need to be evaluated in the process of evolving better and better critters.

There are also many complications involved in the representation of individuals. If a representation is not chosen carefully, there could easily fail to be a one-to-one correspondence between genotypes and phenotypes; i.e., between representations of solutions to the problem and actual solutions. Careless representation schemes can also nullify the effectiveness of the crossover operator; it is possible that crossover would no longer serve to recombine useful parts of pairs of individuals, and even that crossover could create a chromosome which does not represent a legitimate solution.

Variations on the Genetic Algorithm

Numerous modifications have been made to the classical genetic algorithm, and certain variations appear to be more or less useful depending on the problem being optimized. One fairly common version of the GA which has several advantages over the classical model is called the steady-state GA (Figure 3). In this paradigm, only a single population of individuals is maintained at any given time, and the reproduction operator is replaced by a selection operator that chooses which individuals to crossover. The newly created critters are then returned to the single population by means of the replacement operator, which selects critters to be removed. The steady-state GA provides greater control over which individuals are removed from the population, and also requires substantially less computer memory to operate.

Figure 3. The Steady-State Genetic Algorithm

Another simple modification which has been made to the classical GA is the replacement of linear crossover with a cyclic crossover scheme. Instead of choosing a single locus and swapping the strings of alleles following that point, cyclic crossover treats the chromosome as circular, selects two loci, and swaps the alleles between those two positions (right).

Many other possibilities exist, and hundreds of variations of the standard genetic algorithm have been implemented. Much has been tried, but much can still be done. And, although it will probably never be able to serve as the perfect black-box function optimizer computer scientists long for, the genetic algorithm will most likely continue to evolve as a useful tool for the investigation of complex optimization problems.

Reference:

Holland, John H. 1992. Genetic Algorithms. Scientific American, July, pp.66-72.

At the time this article was written, Greg Badros was a Trinity College senior majoring in computer science and mathematics.

©1995 Duke University Undergraduate Publications. Reproduction, except for personal use, is strictly prohibited without prior written consent of the author(s) or Duke Undergraduate Publications. For more info...

Winter 1995 contents

Vertices web central