At the forefront of Artificial Intelligence

Artificial Intelligence Tour (Page 6)

Genetic Algorithms

Genetic algorithms are modeled after the process of natural selection in living organisms. In biology, species adapt to their environment over time through mutation and natural selection. In the same way, possible solutions (guesses) are adapted to problems over time in genetic algorithms. Genetic algorithms are usually implemented to search for answers to certain problems. This can include searches involving solving equations to finding the shortest path from city to city.

Symbolic AI vs Genetic Algorithms

Most symbolic AI systems are very static. Usually, these systems are designed to solve one specific problem. If the given problem were somehow changed, these systems could have a hard time adapting. The algorithm that would have originally led to the right solution could be either incorrect or less efficient. Genetic algorithms (or GA) were created to combat these problems. These systems are based on natural biological evolution. Their evolution-centered architecture allows them to perform searches much more efficiently then most symbolic AI systems.

Processes of Genetic Algorithms

A GA's first step is to generate a large set of random possible solutions sets to a given problem (this is analagous to chromosomes). It then evaluates each of those solutions, and then decides on a "fitness level" for each solution set (or chromosomes). The more "fitter" a certain chromosome is, the more likely it is to mate and reproduce. The theory behind this is based on natural selection. In biology, species that are more "fit" or adapted to their environment have a higher chance of surviving, and thus reproducing. When each pair of solution sets (chromosomes) reproduce, their offspring becomes a combination of the parent solution sets. The composition of the mother solution set is mixed in with the father solution set. The solution sets from the next generation then mutate and reproduce in the same fasion, just as their parents had. This cycle continues on and on, until one chromosome is found to have the desired solution set. This chromosome would have the most desirable fitness level.

General Algorithm for Genetic Algorithms

Create a Random Initial State
An initial population is created from a random selection of solutions (which are analagous to chromosomes). This is unlike the situation for Symbolic AI systems, where the initial state in a problem is already given instead.

Evaluate Fitness
A value for fitness is assigned to each solution (chromosome) depending on how close it actually is to solving the problem (thus arriving to the answer of the desired problem). (These "solutions" are not to be confused with "answers" to the problem, think of them as possible characteristics that the system would employ in order to reach the answer.)

Reproduce (& Children Mutate)
Those chromosomes with a higher fitness value are more likely to reproduce offspring (which can mutate after reproduction). The offspring is a product of the father and mother, whose composition consists of a combination of genes from them (this process is known as "crossing over".

Next Generation
If the new generation contains a solution that produces an output that is close enough or equal to the desired answer then the problem has been solved. If this is not the case, then the new generation will go through the same process as their parents did. This will continue until a solution is reached.

A GA Example
If you have a hard time understanding this essay, it may help to look at an example involving a diophantine equation.

Submitted: 10/12/1999

Article Toolbar

BibTeX entry