10 Jun Survival of the Fittest Knowledge

Genetic Algorithms in Search

I think we can safely assume that intelligent applications, including accurate language interpreters and translators, will possess large amounts of knowledge to be processed and searched. Genetic algorithms are great for searching for obscure data in massive search spaces.

The mechanism for association in computers can be defined as searching, just as humans describe their attempt to recollect a certain memory as “searching.” Because of the sheer amount of information required for any intelligent system, the efficiency of the search process becomes very important. If the search is not done prudently and efficiently, all the time could be spent searching, leaving no time for processing or associating or interpreting. Tanimoto defines good search mechanisms as “pruning to fight the combinatorial explosion” (1987).

Understanding Context Cross-Reference
Click on these Links to other posts and glossary/bibliography references

Section 7 #16

Table of Context

In “Genetic Algorithms in Search, Optimization and Machine Learning”, Goldberg draws this comparison between human and artificial systems: “Designers of artificial systems – both software and hardware, whether engineering systems, computer systems or business systems – can only marvel at the robustness, the efficiency and the flexibility of biological systems. Features of self-repair, self-guidance and reproduction are the rule in biological systems, whereas they barely exist in the most sophisticated artificial systems… Genetic algorithms are theoretically and empirically proven to provide robust search in complex spaces” (1989, p. 2).

Easter Eggs and Genetics

To illustrate the techniques you could use to develop a genetic search algorithm, consider the cruel Easter egg hunt analogy:

Five children are at Uncle Fred’s house in Kalamazoo for Easter. Uncle Fred, who has hidden 40 Easter eggs around the yard, sends the kids out to find them. They have to start from different places and see how quickly they can find the eggs. Since Uncle Fred is really mean, he is using genetic reasoning (survival of the fittest) to favor the kids who do the best. After five minutes, all the kids but Henry have found one or more eggs. He’s out of there! After ten minutes, Maddie and Horace are lagging behind Rebeccah and Abe, so they get cut. After fifteen minutes, Rebeccah is way out in the lead, so Abe goes to the bench to join his forlorn siblings. Since Rebeccah has proven her metal in the heat of the search, she gets to keep searching until she finds all the eggs.

Genetic algorithms keep track of which thread (child) is achieving greatest success in the search, and which search paths or constraints are yielding the best results. Rebeccah will remember that Uncle Fred likes to hide eggs behind trees. Genetic algorithms can be built to favor the stronger search approaches and remember the details or constraints that lead to the greatest likelihood of success.

It’s a good thing Uncle Fred doesn’t use genetic reasoning at the dinner table.

Here is a segment from a genetic algorithm tutorial on the AI Junkie:

At the beginning of a run of a genetic algorithm a large population of random chromosomes is created. Each one, when decoded will represent a different solution to the problem at hand. Let’s say there are N chromosomes in the initial population. Then, the following steps are repeated until a solution is found

• Test each chromosome to see how good it is at solving the problem at hand and assign a fitness score accordingly. The fitness score is a measure of how good that chromosome is at solving the problem to hand.

• Select two members from the current population. The chance of being selected is proportional to the chromosomes fitness. Roulette wheel selection is a commonly used method.

• Dependent on the crossover rate crossover the bits from each chosen chromosome at a randomly chosen point.

• Step through the chosen chromosomes bits and flip dependent on the mutation rate.

• Repeat step 2, 3, 4 until a new population of N members has been created.

A quick look at the rest of the tutorial will help you see how this works, and the author has even provided a genetic tiddlywinks game in both compiled and C++ code.

Besides search, I think there are possible machine learning applications using genetic methods in which, of all potential facts a system can adopt and add to the knowledge base, survival of the fittest knowledge defines the subset that is accepted. I’ll try to gin up a post on the subject. Until then, try to survive.

Click below to look in each Understanding Context section

Leave This Blank:Leave This Blank Too:Do Not Change This:

Your email: