Back to Basics: Genetic Algorithms
|
Back to Basics: Genetic Algorithms
|
 |
Using a biological process metaphor to derive solutions to tough computing problems.
|
|
|
|
|
|
|
Elsewhere on the Web
|
• NEC Research Index: Genetic Algorithms
• GA Archives
|
|
|
| |
|
Many interesting problems from the real world do not have an appropriate mathematical description. There is a term computer scientists often use, NP-completeness (NP comes from "Nondeterministic Polynomial"), that describes problems with too many solutions to try them all in a reasonable amount of time. Such cases are characterized by complex and contradictory constraints that must be satisfied simultaneously. John Holland from the University of Michigan formally introduced genetic algorithms (GA) in the 1970s to optimize such "ill-behaved" functions. This approach uses a biological process metaphor to derive solutions, and is particularly suited to various optimization problems. Such problems arise frequently, making genetic algorithms useful for a wide variety of real world tasks. GA's can be computationally expensive, but the continuing price/performance improvements of modern computational systems have made them attractive even for the beginners.
Natural evolution is driven by survival of the fittest: the weakest individuals in the population will probably die before reproducing, while the stronger ones will bear offspring, passing their genetic material to the next generation. By applying this "selective pressure" - throwing away the worst solutions and keeping the best ones - the original population keeps improving as a whole. Of course, the details of biological evolution are still not completely understood, but some points are supported by strong experimental evidence and can be used for various optimization problems. The beauty of the whole concept is that we don't have to actually calculate a solution to the problem at hand: we just have to select and encourage the best individuals. No need to discover how to solve various difficult tasks. Just write a proper fitness function and evaluate the solutions generated by genetic algorithm!
In virtually every optimization problem, we'll have to maximize or minimize an objective function over a given space of arbitrary dimension, comprising all possible solutions to the problem at hand. The problem state will have to be encoded into a string, encoding a possible solution in a given problem space. The symbol alphabet is often binary, though other representations have also been used: character-based and real-valued encodings, for example. Think of these 0s and 1s as genetic "chromosomes" that, like they biological equivalents, form a complete genetic description of an individual. The objective function takes the encoded string as input and produces a "fitness" score, describing how well the solution represented by the particular chromosome performed. The strings (chromosomes) which are most fit are randomly selected to survive and reproduce to form the next generation. Again, two biological metaphors are used to modify the selected strings.
Mutation performs random changes in the chromosome of an individual. In the simple case of binary encoded strings, all you have to do is to randomly flip a few bits. Although simple, mutations are a crucial part of the algorithm as they allow creation of radically new solutions. Another key process, crossover, is performed by selecting two particularly fit individuals and combining their genetic material. Two chromosomes are usually combined to form a new one using a single point crossover. The process starts when a random point in the chromosome is picked. The information from the first parent is copied from the start up to the crossover point, and the information from the second parent is copied from the crossover point to the end of the chromosome. Variations exist which use more than one crossover point, or combine information from parents in other ways. The rationale for this operation is simple and intuitive: if we have two fit parents, the chances are good that their offspring will introduce repeated improvements in the population. This way, GAs typically provide a heuristic search of the input space for optimal solution. Alternative, brute force methods that would examine every possible solution are clearly infeasible for the most interesting tasks.
Genetic programming (GP) is another popular extension of the genetic model of learning. This is an entire different area I plan to describe in one of the future articles. The main difference between GA's and GP techniques is that individuals in the former case are represented as a parse trees, rather than fixed-length strings. Trees are easily implemented in LISP, making it one of the most popular languages for genetic programming.
It is usually difficult to direct people to one site when they want to start from scratch and quickly learn a lot about particular AI-related technology. This time I'll make an exception, simply because "The Hitch-Hiker's Guide to Evolutionary Computation" - FAQ for USENET newsgroup comp.ai.genetic - is one of the best GA-related resources I'm aware of. Here you'll find all about GA's, Evolutionary Programming, Evolution Strategies, Classifier Systems and Genetic Programming. Their list of free, shareware and commercial software packages will give you a good head start in this area without investing a lot of time and money to pick the right product.
PMSI is another site that gives a brief description of how the genetic algorithms work and some of their applications. Similar resource, mentioning other interesting areas like cellular programming, is Moshe Sipper's "Brief Introduction To Genetic Algorithms". "Genetic Algorithm Classifiers" project describes GA's applications in event classification and feature selection, further illustrated by a Java applet. The GA Playground is a good general GA toolkit implemented in Java, for experimenting with genetic algorithms and handling optimization problems. Programmers will like various development tools like NeuroDimension's Genetic Server 1.0 and Genetic Library 1.0. Both of these new products provide a general purpose API for genetic algorithm design. Genetic Server is an ActiveX component that can be used to easily build a custom genetic application in Visual Basic. Genetic Library is a C++ library that can be used for building custom genetic applications in C++. Business users will find plenty of Excel add-ins like Palisade Evolver, using GA technology to quickly solve complex optimization problems in finance, distribution, scheduling, resource allocation, manufacturing, budgeting and engineering.