The Power of Life

text: Scott Robert Ladd

drawings: Maria Alvarado Ladd

---

Computer programs tend to be static-they begin at point A and go to point B, mindlessly following a specific path. As the basis of most software, that deterministic algorithms have proven their efficacy. Yet something is missing from software, something fundamental: adaptability. Simply put, the vast majority of applications are fixed entities that cannot adjust to situations unforeseen by their programmers. Furthermore, some problems (which I'll introduce later in this book) cannot be easily solved by deterministic programs.

If you're looking for a paradigm of adaptability, look no further than biology. Living things, based on a set of simple underlying chemical principles, have shown remarkable flexibility and adaptability throughout billions of years of changing environments. Implementing biological concepts creates software that evolves solutions. In some cases, a biological algorithm might find solutions that its programmer never envisioned -- and that concept allows software to go beyond its human creator's vision.

What makes life a good model for software? The answer to that question lies in understanding the basic principle of biological evolution.

Biological Evolution

In the mid-nineteenth century, Charles Darwin reasoned that immutable species would become increasingly incompatible with their restless environment. The resemblance of offspring to their parents suggested to him that traits pass from one generation to the next; he also noticed slight differences between siblings, which provide a species with a pool of unique individuals who compete for food and mates.

From those observations, Darwin concluded that, as the environment changed, organisms best-suited to the new conditions would bear offspring reflecting their successful traits. Darwin named this process "natural selection", and he believed that it was the central mechanism by which species evolved.

Modern science recognizes evolution as the mechanism that creates biological organization. While evolutionary theory has been refined in the century since Charles Darwin's death, the core concepts remain intact. We can see evolution operating today and in the fossil record of past species; we can see how organisms change to survive in an ever-changing world.

A tiny English moth provides a classic example of natural selection in action. Before the Industrial Revolution, light-colored pepper moths blended with the white lichen on trees, hiding them from predaceous birds; dark-colored moths contrasted with the lichen and often became avian meals. But when smoke from England's new coal-fired factories killed the lichens and coated the trees with soot, the light-colored moths became visible targets for birds, while dark-colored moths blended into the new environment. Within a few years the peppered moth population was nearly all dark-colored, having adapted to its new environment through natural selection.

While the survival of individuals determines the characteristics of the next generation, it is the reproductive success of a population as a whole that determines the evolution of a species. Natural selection is limited by the characteristics of a population; while it is often called survival of the fittest, natural selection really operates through the survival of the best available organisms. An organism's "fitness" is relative to a changing ecosystem, other species, and other members of its population. What is "best" today (light-colored moths on lichen) may not be "best" tomorrow (dark-colored moths on soot).

Darwin didn't know how characteristics were passed from parent to offspring; he simply saw it happening. The missing element was beyond the science of his time, and nearly a century passed before someone identified the mysterious agents behind evolution. In 1951, biologists Francis Crick and James Watson first described the deoxyribonucleic acid (DNA) molecule -- a tiny corkscrew built from surprisingly simple chemicals. DNA encodes the chemical recipes for life's proteins and enzymes, and it packs an amazing amount of information into an incredibly tiny space; if the DNA in a single human cell were straightened out, it would be nearly two feet long.

Biologists are still exploring this most fundamental piece of life's mystery; the Human Genome Project is perhaps the greatest undertaking in biology, an attempt to map and understand the meaning of the human genetic code. A daunting task, indeed: Each tightly coiled strand of DNA contains genes that define individual parts of an organism's blueprint. Human DNA includes more than 200,000 genes that are responsible for controlling everything from eye color to the potential for developing certain illnesses.

Offspring inherit characteristics through genes received from a parent. Simple organisms such as fungi and bacteria reproduce asexually by duplicating themselves. A single-celled amoeba, for instance, creates offspring by splitting into two new organisms that contain identical DNA. Thus, asexual reproduction produces new organisms that differ little from each other or their progenitor.

Most complex organisms reproduce sexually by combining genes from two parents in their offspring. By mixing and matching DNA from two organisms, sexual reproduction increases the variation within a species. The possibilities are almost endless; for example, a human couple can produce more than seven trillion different blueprints for a person.

The collective genetic information in a population constitutes a gene pool. Large gene pools are healthier than small ones by allowing a greater number of genetic combinations. Greater variability means that a larger gene pool is more adaptable and less prone to recessive genetic disorders. A small gene pool leads to inbreeding, increasing the chance that recessive genes will manifest themselves in the offspring of closely-related organisms.

Natural selection changes the frequencies of genes in a population, but it doesn't produce new genes. The first life forms began as self-replicating chemicals that bound to each other in mutual cooperation. The first complete organisms resembled an amoeba -- and an amoeba clearly does not contain the genes required to evolve it into a human being. New characteristics must somehow arise; otherwise, the simple original life forms would never have evolved into the millions of species on Earth today.

A mutation is a random change in an organism's genes. It is highly unlikely that a random genetic change will improve a complex organism that is well-adapted to its environment; most manifest mutations disappear from the population through natural selection. Fortunately, the vast majority of mutations have no affect. Studies of human DNA have found long sequences of "junk genes" that serve no explicit purpose; mutations in junk genes are likely to be meaningless. And sometimes, cells can repair damaged DNA, eliminating many mutations before they are passed along to new cells or offspring.

Natural selection mixes and sifts gene pools, acting on variations produced by reproduction and mutation. Sometimes a gene pool evolves in a straight line, carrying a species from one form to another, as in the earlier example of the peppered moth. In other cases, forces act to divide a gene pool, and natural selection works on the now-separate populations to produce new species.

If a species encounters several open niches, it may quickly diversify in a process known as adaptive radiation. When the dinosaurs vanished 65 million years ago, they left unoccupied niches that were exploited by mammals. Through adaptive radiation, a few shrew-like species blossomed into thousands of types ranging from bears to people to whales.

In the 1980s, biologists Niles Eldredge and Stephen Jay Gould introduced a substantial modification in evolutionary theory. Traditionally, evolution has been seen through the gradualist's eye as a steady process, moving in smooth continuity from species to species. Eldredge and Gould came to a different conclusion after considering the fossil record; what they saw were species that remained relatively static until environmental factors forced rapid evolution into new forms. Known as punctuated equilibrium, this new idea has been hotly debated; it brings catastrophism back into the evolutionary fold, suggesting that evolution is driven by the need for change. Experiments in theoretical biology suggest that Eldredge and Gould may be on the right track.

As you can see, evolution is itself evolving, as new ideas and discoveries enter the mix and scientists stir the pot of scientific discovery.

Evolving Software

The quest to apply evolution to software is not new. The University of Michigan's John Holland defined the concept of genetic algorithms in a 1975 paper titled Adaptation in Natural and Artificial Systems. Reasoning that the robustness of life stemmed from evolution by natural selection, Holland concluded that biology could provide a metaphor for artificial systems. Holland began by codifying the precise mechanisms of biological evolution; he then applied those principles to the development of software.

Computer scientists still debate the precise definition of a genetic algorithm (or GA). In the broadest sense, a GA creates a set of solutions that reproduce based on their fitness in a given environment. The process follows this pattern:

• An initial population of random solutions is created.
• Each member of the population is assigned a fitness value based on its evaluation against the current problem.
• Solutions with a higher fitness value are most likely to parent new solutions during reproduction.
• The new solution set replaces the old, a generation is complete, and the process continues by returning to step 2.

That sequence implements, in a most simplistic way, the concept of survival of the fittest. The reproductive success of a solution is directly tied to the fitness value it is given during evaluation. In this stochastic process, the least-fit solution has a small chance at reproduction while the most-fit solution may not reproduce at all. The outcome of a genetic algorithm is based on probabilities, just as biological success is grounded in chance.

So how can a random process possibly reach any sort of definitive answer to a question? Look to biology for your answer; living things evolved flight, complex senses, intricate societies, and millions of other adaptations specific to various niches and environments. Computer programs operate in an environment that is several orders of magnitude simpler than the biological world; the powerful tools of nature should have no trouble finding solutions to relatively trivial problems.

The standard model for a GA solution is an anonymous bit string - called a chromosome after its biological counterpart - that must be decoded during evaluation. Where DNA uses a base-4 alphabet, binary string uses ones and zeros to encode information. During reproduction, the chromosomes of parent solutions combine and undergo mutation in creating the next generation. In the highly-idealized universe of silicon, we have fine control over this process.

Let's develop a genetic algorithm for a simple problem, and see how these techniques become reality in C++ code.

Defining a Genetic Algorithm

We'll begin with a "black box" that returns a single output value for every input value. No one knows what is going on inside the box, but we do know the following facts:

• Input to the box is a 32-bit signed integer.
• Output from the box is a 32-bit signed integer with a value between 0 and 32.
• Only one, unknown input value generates an output of 32.
• Output values less than 32 may be produced by several different inputs.
• There is no obvious correspondence between input values and their outputs. For example, an input of 32 generates an output of zero, while an input of ten produces an output of four.
• The box cannot be opened or otherwise investigated, other than by feeding it values and examining the associated output.

The task at hand is finding the input value that produces an output of 32; in other words, we want to maximize then output of the black box. For the purposes of this example, I define a BlackBox function with the following prototype:

long BlackBox(long x);

You have no idea how BlackBox is implemented; it could, for instance, be defined in a module for which the source code is missing or lost. A brute force approach would test all 4,294,967,296 possible long values; assuming that we have our facts correct, the bruite force approach will find the one input value that obtains an answer of 32. Where brute force falls on its face is in how long it might take to find an answer; it might find the "magic" value after a few loops, or after billions of iterations. Clearly, a more intelligent solution is desired.

Populations

Let's build a genetic algorithm to maximize the output from BlackBox. The first task is to define our solution set, or population. Since the input to BlackBox is a long, our population will consist of an array of longs to be tested against the function. Our chromosome, then, is a 32-bit string. We're looking for the largest value returned from BlackBox for a given member of our population; therefore, we'll define a second array of longs, the same size as the population array, to hold corresponding output values from BlackBox. In other words, element five of the fitness array holds the value returned by BlackBox when it is given the input value stored in the fifth element of the population array.

Selection by Chance

Assuming that we haven't found the input that produces 32, we now need to produce a new population from the old, using the fitness values to determine reproductive success. The simplest way of accomplishing this is to use a roulette wheel. You've probably seen a standard gambler's roulette wheel, a spinning circle divided into thirty?seven or thirty?eight equal?sized, pie?shaped sections. The croupier sets the wheel spinning and at the same time tosses an marble into the bowl in the direction opposite to that in which the wheel is moving; when the motion of the wheel ceases, the ball comes to rest in one of the numbered sections.

In the case of a genetic algorithm, a roulette wheel selects the chromosomes used in reproduction. The wheel is the fitness array, and the marble is a random integer less than the sum of all fitnesses in the population. To find the chromosome associated with the marble's landing place, the algorithm iterates through the fitness array; if the marble value is less than the current fitness element, the corresponding chromosome becomes a parent. Otherwise, the algorithm subtracts the current fitness value from the marble, and then repeats the process with the next element in the fitness array. Thus the largest fitness values tend to be the most likely resting places for the marble, since they use a larger area of the abstract wheel.

Table 1: A Small Population

To clarify, lets look at a small example with a hypothetical population of five. Table 1 shows the population and its corresponding fitness values. The total fitness of this population is 60. This simple pie chart shows the relative sizes of pie slices as assigned by fitness.

Figure 1: Relative Fitness

In other words, the chromosome 10110110 has a 34% chance of being selected as a parent, whereas 10000000 has only an 8% chance of generating a new chromosome. Selecting five parents requires the algorithm to generate five random numbers, as shown in Figure 2-3.

Table 2: Selection by Fitness

The chromosome with the highest fitness, 10110110, parents two members of the new population; even the chromosome with the lowest fitness will be a parent once. However, the second most fit chromosome did not reproduce -- an example of the random nature of roulette wheel selection.

Crossover

Crossover is a central feature of genetic algorithms that creates a new chromosome from two parents. Corresponding to biological crossover, the software version combines a pair of parents by randomly selecting a point at which pieces of the parents' bit strings are swapped. Figure 2-4 shows four examples of crossover. The vertical bar in the child chromosome indicates the point of crossover.

Table 3: Crossover in Action

Crossover allows the mixing of attributes from different chromosomes. In association with crossover, Holland developed the theory of schema: sets of bits that provide building blocks for high-fitness chromosomes. Holland determined that crossover mixes schemata from the chromosomes with the highest fitness values, thus increasing the frequency of valuable schema within a population. Some computer scientists characterize genetic algorithms as manipulators of schemata within chromosomes.

Mutation

The final step in reproduction is mutation, which involves the random change of one or more bits in each chromosome of the new population. The primary purpose of mutation is to increase variation into a population; mutation is most important in populations where the initial population may be a small subset of all possible solutions. It is possible, for example, that every instance of an essential bit might be zero in the initial population. In such a case, crossover could never set that bit to one, and the correct solution would not be found without mutation's ability to set that bit "randomly."

Different programmers implement various ways of mutating chromosomes. A common system sets a probability that any given bit will be changed; a test is performed for each bit to see if its value should be changed. Such a system requires the generation of many random numbers, which can degrade program performance. For example, in a population of fifty long chromosomes would use 1600 random values during mutation.

I prefer a simpler solution, defining a probability that a bit - any bit - in a chromosome will be randomly changed. This requires the generation of one or two random numbers -- the first to decide if mutation will take place, and the second to determine the bit that changes. To allow for multiple bit changes within a chromosome, I sometimes implement a looping system such as:

while random_value < mutation_chance
    mutate(chromosome);

Rules of Thumb

Mutation and crossover are known as reproduction operators. Holland also defined another reproduction operator, inversion, which reverses a segment of bits within a chromosome. Few researchers have examined inversion seriously, and those that have suggest the use of inversion only when the chromosome size is "large." For now, I'll ignore inversion; it will come up again in later chapters, when I describe more sophisticated problems and solutions.

Even if you don't use inversion, you should still keep chromosome length in mind when implementing crossover and mutation. In a four-bit chromosome, only sixteen possibilities exist; crossover probably won't create any new chromosomes in such an environment because all possibilities are likely represented in even a small population. Mutation, in turn, has less effect in longer chromosomes; changing one bit in a 256?bit string has less influence than would flipping a bit in a 16?bit chromosome.

Another thing to keep in mind is the population size of a solution set. The larger the population, the longer it will take to process. Smaller populations, however, lack a robust selection of chromosomes. In designing a genetic algorithm, you need to balance the size of the population against the number of generations required for finding a solution. A population of a hundred chromosomes may find the solution in only ten generations, but each evaluation cycle may take four times as long as it would for a population of twenty chromosomes who find the solution in twenty generations.

Population size has another influence on genetic algorithms: it dilutes the influence of high fitness values on reproductive success. In a population of ten chromosomes, in which one has a fitness of nine and the others a fitness of one, half of all parents will probably be selected from the nine relatively-unfit chromosomes, even though the best chromosome is nine times more fit.

Evaluating chromosomes and calculating fitness is the most time-consuming component of a genetic algorithm. Your goal should be to reduce the number of fitness evaluations, either by reducing the size of the population or by decreasing the number of generations required for finding the solution.

Before getting into the development of code, I'll bring up two more techniques that can enhance the performance of a genetic algorithm. Elitist selection always copies the most?fit chromosome into the next generation, guaranteeing that the best solution survives so that a population doesn't "lose ground" in terms of fitness.

Another enhancement is fitness scaling. As a population converges on a definitive solution, the difference between fitness values may become very small. That produces a roulette wheel with nearly-equal sections, preventing the best solutions from having a significant advantage in reproductive selection. Fitness scaling solves this problem by adjusting the fitness values to the advantage of the most-fit chromosomes.

Windowing is the simplest form of fitness scaling. To implement windowing, begin by computing fitness values as usual, keeping track of the smallest fitness value. Then, subtract the minimum value from all fitness values, thus adjusting the fitness array to a zero base. You might also want to subtract a number slightly smaller than the minimum fitness, just to ensure that all chromosomes have a chance at reproduction.

Programming genetic algorithms is often a matter of "feel." You need to see what works, and how, to understand exactly which factors produce the fastest results in a given situation. To aid your exploration, I've defined a set of parameters for solving this chapter's problems. You can set those parameters to a variety of values, learning how different combinations of options affect performance.

An Implementation

For now, I'll keep the implementation of BlackBox a secret; while you may have guessed by now what it is doing, I don't want to give away the optimum solution until you've seen how the genetic algorithm performs. I suggest downloading one of the three source files -- C++, Java, or Fortran -- and printing it out so you can follow along.

In each of the three programs, an Optimize function has six arguments that define how the genetic algorithm works: population size, the number of generations to run, the chance of crossover, the rate of mutation, and Boolean values for turning on and off elitist selection and fitness scaling. The algorithm begins by verifying the parameters, replacing any invalid or nonsensical values with defaults. Next, I define working variables. Then the code allocates arrays to hold the population, its children, and fitness values. The last stage of initialization is the creation of an starting population of random chromosome values.

Each generation cycle begins by calling BlackBox for each chromosome, storing the calculated fitness. The highest fitness is tracked for reporting purposes, while the least fitness is recorded for the purpose of fitness scaling. In the extremely unlikely event that the population has a total fitness of zero, the routine stops, since you can't optimize a population that has no potential. (I could make comments on certain segments of human society, but I guess I'll be polite... ;)

After calculating the average fitness of the population and reporting statistics for the current generation, the algorithm performs fitness scaling (assuming it was selected). To adjust the fitness values, I subtract the minimum fitness value, add one, and square the result. Adding one (1) gives every chromosome a chance of reproduction, and squaring the fitness value strengthens the reproductive chances of the most fit chromosomes.

A third loop implements reproduction. Using the roulette wheel technique, the algorithm selects one or two parents (depending on whether or not crossover is enabled). I use one shifted bit mask to implement crossover, and another bit mask in mutating a child chromosome. If elitism is enabled, the algorithm automatically copies the best chromosome of the parent generation into the first element of the new population. Then I copy the new population over the old, and proceed to the next generation.

Once all generations have run, the routine ends by cleaning up after itself (if required by the language at hand).

The output of the C++ program looks like this, using the default configuration (other languages produce similar displays):

BlackBox Optimization
---------------------
population size: 100
# of generations: 50
crossover rate: 100%
mutation rate: 10%
scaling enabled: true
elitism enabled: true

0 best: 0x00003842, fitness = 22, average fitness = 16.43
1 best: 0x0000384a, fitness = 23, average fitness = 18.36
2 best: 0x0000384a, fitness = 23, average fitness = 20.42
3 best: 0x000c3842, fitness = 24, average fitness = 21.69
4 best: 0x0008784a, fitness = 25, average fitness = 22.76
5 best: 0x1018784a, fitness = 27, average fitness = 25.04
6 best: 0x1018784a, fitness = 27, average fitness = 25.28
7 best: 0x118c784a, fitness = 29, average fitness = 27.45
8 best: 0x118c784a, fitness = 29, average fitness = 27.91
9 best: 0x119c784a, fitness = 30, average fitness = 28.14
10 best: 0x119e784a, fitness = 31, average fitness = 29.39
11 best: 0x119e784a, fitness = 31, average fitness = 29.89
12 best: 0x11de784a, fitness = 32, average fitness = 30.41
** Optimization complete!

A genetic algorithm is a stochastic process that exhibits variable performance. You can run the program a million times, a probably never see the same output twice - but you will see the correct result generated in every run. Well, maybe not every run; it is very remotely possible that the algorithm could fail to find the correct answer after fifty (or even a million) generations. Think of it this way: It is possible to flip a coin and get "heads" a million times in a row, without ever seeing "tails" -- but the likelihood of such is so infinitesimally small that we needn't worry about it.

Language notes

I've implemented "BlackBox optimization" in three programming languages: C++, Java, and Fortran-95. Writing the same algorithm in different languages is a mind-opening experience, for it shows strengths and weakness of different languages, throwing different concepts into sharp contrast. Given time, I'll write a version of this in Python, and perhaps in other languages as the opportunity presents itself.

C++

The Standard C/C++ function rand only returns an integer value; I use a small inline function, getRandomFloat, to generate a random floating-point value between 0 and 1. This is not a good way to generate "random" floating-point values. However, this simple technique suffices for now --  and in a forthcoming Algorithmic Conjurings column, I'll describe something called a uniform deviate generator that is most useful for stochastic computing.

Java

Nothing special caused me trouble with the Java version of the program. I successfully ran the code with several VMs under both Windows 2000 and Linux, including Sun's JDK 1.3.1, Kaffe, and IBM's excellent implementation. The code compiles into executable form on Linux with the GNU gcj compiler, version 3.0.1. Remember to use the --main=BlackBox option when compiling with gcj, so the compiler knows where to find the program entry point.

Fortran

I've never written a stochastic application in Fortran before, and so I had no experience with the intrinsic functions RANDOM_NUMBER and RANDOM_SEED. My first experience with the Fortran 90/95 random number generator was not good.

According to the Fortran 95 standard, calling RANDOM_SEED without arguments will assign a "processor dependent" value to the "seed" for the random number generator. With Intel's Linux compiler, this appears to be the same seed for every run! I looked in various newsgroup archives, and found several examples of allocating an array of seeds and "putting" it with RANDOM_SEED -- and that didn't work well at all, giving me the same real value every time I called RANDOM_NUMBER!

Yuck...

I tried a number of ! techniques for setting the "seed" value, but the RANDOM_NUMBER algorithm doesn't produce a "random" set of real values. Reading the forums, I found many people who don't like Fortran's "random number generator". It looks like my next article here is going to describe implementing a uniform deviate generator (see my C++ and Java books) for Fortran 95.

As it is, the example program initializes the generator with a no-argument call to RANDOM_SEED; the program always outputs the same result when compiled with Intel's Fortran for Linux, but perhaps it will work better with another compiler... let me know if you have any success or insights.

A Bit of Analysis

After studying many runs of this program, you can see how the various factors affect performance. If the mutation rate is too small or zero, the algorithm runs poorly; if you set the mutation rate very high (say, above 50%), mutations obscure useful combinations of genes created by crossover.

Enabling elitist selection increases the speed of the algorithm. Combining a low mutation rate with elitist selection further enhances the algorithm's speed. However, the most dramatic increase in performance comes when fitness scaling is employed with mutation and crossover. The reason for faster convergence lies with the nature of the problem being solved. Fitness values returned by BlackBox fall into a relatively narrow range, leaving little distinction between different chromosomes. This is known as the close race phenomena. The inclusion of fitness scaling adjusts reproductive success in favor of the chromosomes with the highest fitness.

You should also note a relationship between mutation rate and fitness scaling. Without scaling, a low mutation rate is advantageous; once fitness testing skews reproductive success, however, a higher mutation rate proves most useful by increasing variety in the population.

In case you were wondering, the BlackBox function compares the input value x to a constant named secret, returning the number of bits that match between the two values. Only one value can match all 32 bits in secret.

The genetic algorithm was looking for a single solution among more than four billion - and it succeeded in only a few seconds, by testing, on average, only a few thousand values.

Onward

In optimizing the output of BlackBox, I've demonstrated only the basic principles of genetic algorithms. Now it's time to elaborate and extend these concepts; and so my next goal is to build a set of reusable components for GA development.