This might be a little open ended, but I heard an explanation of this talk on how GP could be used to fix bugs, and I wonder: How does this differ from the infinite monkey theorem?
Add a comment
|
4 Answers
GP relies on "evolution", whereas the Infinite Monkey Theorem is just random chance. In GP, you have one or more fitness indicators which are used to evaluate a generation of possible solutions to "breed" to create a new generation. Each one, more than likely, getting a better and better solution. IMT has more to do with enough candidates that eventually every combination will occur.
-
Got it, but still they have in common this trait of letting randomness take charge isn't ?– OscarRyzFeb 28, 2012 at 1:38
-
1At the very least, randomness takes second place to fitness in GP. One could theoretically seed a generation with non-random elements and breed with traits only from that population, thereby employing very little randomness. But certainly, it plays a role in both.– JoeFeb 28, 2012 at 2:08
-
@OscarRyz: Many quicksort implementations "let randomness take charge" to pick a pivot. "Using randomness" doesn't mean "guessing blindly"– nikieFeb 28, 2012 at 8:40
The thing about monkeys is most of them are terrible writers, which is why we would need an infinite number of them. Your infinite monkeys will indeed produce some great literary works (all of them in fact), however they will also produce an awful lot of crap (both literal and figurative). Using a genetic algorithm instead will hopefully let us produce some great literary works while keeping the crap to a minimum.
We first take a (relatively) large number of monkeys distributed among various traits (perhaps hair color, tail length, or how often they throw poop at you). Then we put them all in a cage so they can reproduce. Eventually they will reproduce so much that there are more offspring than you originally had. These new monkeys are each some random combination of monkeys from previous generations. We'll also expose the monkeys to some mild to moderate radiation to add a bit more randomness for good measure.
Now that we've got a new generation of monkeys it is time to put them to the test. Give each of them a pen and paper and tell them to write you a story. Once they've finished read through their stories and keep the monkeys who produced the "best" stories and sell the rest to the circus. Continue this breeding and pruning process for several million years and you should end up with a group of super monkeys that can consistently churn out literary classics without all the crap your infinite monkeys would produce.
There is a lot of randomness here (depending on how much radiation you used) but by selecting only the best monkeys to continue on at each generation the randomness will hopefully converge on the solution you are looking for without having to deal with an infinite amount of monkeys. It's true that an infinite amount of monkeys would give you the answer you want, but then you'd need an infinite amount of time to wade through their infinite amount of crap as well.
The infinite monkey theorem relies on the vastness of an infinite number of anything. An infinite number of monkeys bashing at keyboards randomly will instantaneously generate not only Shakespeare but every work ever written and every work ever to be written an infinite number of times. Including what the monkeys just typed. (How does a set contain itself you ask? It's infinite).
Genetic programming takes a large number of workers (far less than infinite) and selects the best candidates based on the fitness of their output. These workers are then mutated and allowed to run again the survivors of the next generation selected based on fitness.
Interestingly enough there is an IMT simulator that uses genetic programming to get better and better breeds of monkeys each generation. After running for 10k generations it could output the first 18 lines of Hamlet from what I remembered.
answered Feb 28, 2012 at 1:43
Another way of looking at it is in terms of probability. Say we have a space X of configurations and a function for evaluating how good those configurations are, f. To find good solutions, elements in X that have a high value f, we need to find a way of sampling X. Two strategies for sampling the space are the Infinite Monkey (IM) and Genetic Programming (GP).
The difference is in how X is sampled. In the IM strategy, the sampling is completely uniform. In Genetic Programming, an initial set of points are taken uniformly, but then the various hills and valleys of fitness (according to f) are explored from there.
