|
As we start to bring this series of articles to a conclusion we can draw on some of our shared experiences. Previous sections of this series focused on the use of randomness in the search process. The idea is that if there is no plan, there can be no predetermined result. The basic tenet of computers is that one step inevitably follows another. By introducing random elements we interfere with that tenet, which then allows us to go beyond it. We admit that we are really using pseudo-randomness that is algorithmically created, so it can, therefore, be repeated. But would our results have been any different if we had used real randomness instead? No. We could have, but it was more convenient to use a type of randomness that was computer generated. In the last part, we looked at Neural Networks. Although the technique was biologically inspired, it developed into a statistical optimization method instead. Yet, the neural network was useful to creating evaluations where human judgment might otherwise be employed. In this section, we look again to biology and evolution, to find inspiration. The concept of Genetic Algorithms was introduced by David E. Goldberg in his book of the same name in 1989. He and John Holland, at the University of Michigan, developed and promoted the concept that biological model or reproduction and evolution employing DNA could be used to solve problems with a digital computer. Every computer program, and all information for that matter, can be represented by a string of bits—ones and zeros. The approach of Goldberg and Holland is to represent something—an idea or a concept—as a string of bits, and then manipulate the string in such a way that the resulting final string is useful. The manipulations take their lead from models of biological reproduction. One manipulation is to combine two different strings by cutting them both in the middle somewhere and then swapping the pieces so that each consists of half of one string and half of the other. This is called “crossover” and is similar to sexual reproduction involving the merger of DNA from sperm and egg. The second manipulation, mutation, is the result of randomly changing bits in the string. This also exists biologically in asexual reproduction, but in the real world its use is limited to very simple organisms. A little reflection of this will suggest many reasons why this has to be. A third manipulation replicates individual strings in accordance with some measure of fitness, so that there are more of the better ones in the pool. This is similar to evolution. Statistical rules determine that the better strings will be selected more often in the reproduction process. Since 1989 these concepts have been expanded and improved upon to include what is now called “evolutionary computing.” A society exists to encourage and promote study in this area. The next Genetic and Evolutionary Computing Conference will be held in Washington D.C. at the L’Enfant Plaza Hotel from June 25 to June 29, 2005. I may attend. I have been to several of these conferences over the years, but I must say that I have not come away with much that I can hang my hat on. They are academic; the problems are narrow, focused on student projects, full of jargon, and with little commercial implication. Where there have been useful applications, they resulted more from users being inspired by the ideas being presented rather than actually using them. This is not to say that their efforts should be dismissed. One topic keeps coming up: the creation of new proteins. To accomplish this would have hugely important implications in medicine. Proteins, as you know, are the construction materials of life. They consist of very long molecules that fold into little balls—or rather, little ball-like objects—where their exact shapes determine their biological properties. The trick is to create an artificial protein molecule and then see into what shape it folds. The second, harder, trick is to define a shape and find the protein molecule that will fold into it. This is big stuff, and huge computers are presently being used. IBM created one called “Blue Gene” which is designed for that purpose. This is playing around at the very edge of life itself. We were doing the evolutionary thing with our poker game. Each player in the game had a “string” which was a set of numbers that determined a betting strategy. As the strategy played out, some players did better than the others, and their “strings” were modified, but not significantly. “Not significantly” is an important point. Each “new” string bore a resemblance to its “parent”, but was also somewhat different. Each new string was but a small step away from its predecessor. It was a limited form of mutation rather than bisexual reproduction. Steps which represented changes for the worse tended to disappear. Steps which represented changes for the better, tended to reappear. But nothing was certain. We were dealing with tendencies rather than certainties. Following in the lines of evolutionary computing, we should mention the famous monkey problem. It goes as follows: Given enough monkeys, sitting at typewriters typing random letters, over time they would eventually type all of the known works of Shakespeare as well as the Bible, the Koran, the works of Isaac Newton, Einstein, and every other written work including this one. Of course, this is absurd, so we therefore conclude that the idea of a creative computer is also absurd. What’s wrong with this? Beyond its impracticality, the proposed experiment assumes that the monkeys would never learn. All of their typing is random, and continues to be random, and therefore, the probability that a monkey could even put together a simple sonnet is too unlikely to be considered possible. But consider a slightly different experiment taken from our now shared experiences. Suppose one very fast monkey has an editor. Every time the monkey types a page, the editor looks at it and tells the monkey whether this page is better than the last. If it is better, the monkey makes some random changes in the paper and resubmits it. Again the editor comments, and again, the monkey saves the new one or throws it away depending upon the editor’s comments. Eventually, the editor says “Well I declare, Mr. Monkey, this is a beautiful sonnet: one that Shakespeare could have written if he had your talent.” So what is missing in the original statement of the monkey problem is the absence of an editor. Unfortunately, finding such an editor presents us with a new problem. Next Month: Wrap up. |
|
Richard Ten Dyke, a member of the Danbury Area Computer Society, has previously contributed to this newsletter on the topic of Digital Photography. He is retired from IBM and can be reached at tendyke@bedfordny.com. All opinions are his own, and he welcomes comments. |
|