Genetic algorithm technology gives AI a boost
- By John McCormick
- Feb 10, 1997
It's an industry cliche that artificial intelligence has not fulfilled expectations.
But in fact, AI has succeeded as a technology buried inside other software.
Every time an AI tool turns practical, it's no longer considered to be AI. That
happened with speech and handwriting recognition, and even optical character recognition
was thought to be AI a decade ago.
Genetic algorithm (GA) technology, the latest outgrowth of AI research to hit the
big time, attempts to find answers to problems too complex for ordinary analysis. How does
it do this? By copying the reproduction and evolution mechanisms of living organisms.
So-called evolutionary programming is a related but separate programming technique
introduced 30 years ago, and many of the comments that follow apply to it as well.
GA has found real-world uses in finance, data warehousing and mechanical
engineering. The coding can be extremely complex, but it's easy to understand in theory
how genetic algorithms work.
You've probably heard the DNA protein chain described in terms of computer programs.
GA turns that analogy on its head, slicing and dicing "chromosomes" on a string
of bits representing a formula or physical object. One or more chromosomes constitute a
virtual organism, which is then "evolved" toward a solution.
In a financial model, the virtual organisms might represent different ways of
allocating personnel and funding, while the survival-of-the-fittest test applied by the GA
might be the cheapest or fastest allocations.
Once the initial conditions are specified, a GA embarks on a series of
approximations, testing each intermediate result to determine how close it comes to a
The algorithm "mates" the virtual organisms and applies the fitness test
to their offspring. It can "grade" the fitness of original and offspring
organisms and rebreed any that show signs of survival, instead of simply killing off all
but the best in each generation. This takes longer but develops permutations the
programmer could not imagine.
The GA combines the virtual organisms by a crossover method. The simplest method,
called single-point crossover, "cuts" the virtual genetic material in half and
recombines the two halves of different originals.
Mutations can be introduced and the resulting virtual organisms evaluated. In true
Darwinian fashion, the best, or fittest, eventually will dominate the population by
surviving the successive selections.
Other crossover methods are dual-point, which is similar to single-point, and
uniform crossover, which uses a more complicated screening and combination method.
The most sophisticated GA systems have variable crossover tools that make smaller
changes as a solution is approached, and evolving crossover tools that can be modified by
the results they achieve.
Evolving crossover also is called knowledge-based or learning crossover. This is
limited to the most difficult problems, because it requires significant user modification.
Other GA variations include ways of making "life" harder for the virtual
organisms to speed up their evolution.
During the growth process, a vast number of virtual organisms must be created and
tested for viability, and this part of the work is highly processor-intensive. The program
might run until it reaches an optimum degree of fit or terminate after a preset number of
It can be speeded up with evolution short cuts-comparisons of the fitness of
offspring against that of their parents and siblings. This quickly eliminates unsuitable
Schedules, timetables and engineering problems are good candidates for GA analysis. So
is photo interpretation, especially pattern searching and emulating the human ability to
compare and recognize faces. Design and management of complex LANs are other good GA
Data mining is a new GA application. Finding the golden nuggets hidden in computer
data collected by government agencies can involve billions of records, so the prospecting
must be automated.
Here are some products in this fledgling market:
GA is beginning to blend with computer-aided design in the integrated circuit world.
For more information, see a report posted at http://www.bioele.nuee.nagoya-u.ac.jp/wsc1.
Some genetic programmers are working to apply GA to what may be the biggest headache
of all: software creation.
Researchers at Stanford University have shown that GA programming might produce software
that functions better than human-coded programs.
But in the first such machine-generated program, the researcher was working with a
64-CPU PowerPC parallel processor platform. Such massive hardware requirements make GA
impractical for solving common problems. But it might be cost-effective if the general
solution applies to a whole category of problems, is the only solution for an important
task, or leads to optimized software that itself can work on many other problems.
Other GA resources:
Frequently asked questions are available by anonymous File Transfer Protocol at ftp
alife.santafe.edu or ftp rtfm.mit/edu.
John McCormick, a free-lance writer and computer consultant, has been working with
computers since the early 1960s.