Genetic Algorithms

The first genetic algorithms were developed in the early 1970s by John Holland at the University of Michigan. Holland was impressed by the ease in which biological systems could perform tasks that eluded even the most powerful super-computers. For example, animals can flawlessly recognize objects, understand and translate sounds, and generally navigate through a dynamic environment almost instantaneously.

For decades, scientists have promised to replicate these capabilities in machines, but this has proved to be very difficult. Most scientists agree that any complex biological system that exhibits these qualities has evolved to get that way.

Evolution Theory

Evolution has produced systems with amazing capabilities through relatively simple, self-replicating building blocks that follow a few simple rules:

1. Evolution takes place at the level of the chromosome - The organism doesn’t evolve, but only serves as the vessel in which the genes are carried and passed along. It is the chromosomes that are dynamically changing with each re-arrangement of genes.
2. Nature tends to make more copies of chromosomes which produce a more “fit” organism - If an organism survives long enough, and is healthy, its genes are more likely to be passed along to a new generation of organisms through reproduction. This principle is often referred to as “survival of the fittest.” Remember that “fittest” is a relative term; an organism only needs to be fit in comparison to others in the current population to be “successful.”
3. Diversity must be maintained in the population - Seemingly random mutations occur frequently in nature, and these ensure variation in the organisms. These genetic mutations often result in a useful or even vital feature for a species’ survival. With a wider spectrum of possible combinations, a population is also less susceptible to a common weakness that could destroy them all (such as a virus) or other problems associated with inbreeding.

Once evolution is broken down into these fundamental building blocks, it becomes easier to apply these techniques to the computational world.

Holland began applying these properties of evolution to simple strings of numbers that represented chromosomes. He first encoded his problem into binary strings (rows of 1s and 0s) to represent the chromosomes, and then he had the computer generate many of these “bit” strings to form a whole population of them. A fitness function was programmed that could evaluate and rank each bit string, and those strings that were deemed most “fit” would exchange data with others through a “crossover” routine to create “offspring” bit strings. Holland even subjected his digital chromosomes to a “mutation” operator, which injected randomness into the resulting “offspring” chromosomes to retain diversity in the population. This fitness function replaced the role of death in the biological world to determine which strings were good enough to continue breeding and which would no longer be kept in memory.

The program kept a given number of these “chromosomes” in memory, and this entire “population” of strings continued to evolve until they maximized the fitness function. The result was then de-coded back to its original values to reveal the solution.

Holland’s original genetic algorithm was quite simple, yet remarkably robust in finding optimal solutions to a wide variety of problems. Many custom programs today solve very large and complex real-world problems using only slightly modified versions of this original genetic algorithm.

Modern Adaptations of Genetic Algorithms

As interest swelled in academic circles, as serious computational power began moving its way into mainstream desktop machines, standards like Microsoft Windows and Excel made design and maintenance of complex models easier. The use of real numbers rather than bit string representations eliminated the difficult task of encoding and decoding chromosomes.

The popularity of the genetic algorithm is now growing exponentially, with seminars, books, magazine articles, and knowledgeable consultants popping up everywhere. The International Conference of Genetic Algorithms is already focusing on practical applications, a sign of maturity that eludes other “artificial intelligence” technologies. Many Fortune 500 companies, from brokerage firms to power plants, phone companies, restaurant chains, automobile manufacturers and television networks, employ genetic algorithms regularly to solve real-world problems.