Self-Improving Systems

Roland Olsson writes "A relatively easy way to construct "intelligent" systems that improve themselves practically ad infinitum is described at http://www-ia.hiof.no/~rolando/SIG/ Maybe Steven Spielberg's AI film is closer to reality than the general public knows *smile*?"

Comments

A framework for self-improving systems

[Black Acid]

ResearchIndex lists Theo: A framework for self-improving systems. Although The NECI Scientific Literature Digital Library: ResearchIndex itself does not carry the document, it lists several related ones. Heavy stuff. An excerpt from ResearchIndex summarizes Theo quite well:

For instance, the THEO system (Mitchell et al. 1989) uses a single knowledge base and a single set of axioms.

I'd suggest anyone seriously interested in self-improving systems check out Mitchell, T. M., J. Allen, P. Chalasani, J. Cheng, O. Etzioni, M. Ringuette, and J. C. Schlimmer's 1989 book, Theo: A Framework for Self-Improving Systems: National Science Foundation, published by DEC.

Genetic Programming

[nyjx]

... has been around since the mid 80's and although it works for toy problems it's very hard to get systems of a significant scale out of it. You're basically swapping sub branches of your program around to see what works - tranversing the space of all possible programs - it takes *a lot* of random attempts to do better than a human doing it analytically. Most AI researchers believe that you need at least a little bit of knowledge to guide your program's adaptation rather than blind mutation.

The Father of GP (John Koza) may disagree with me - he runs genetic-programming.org and more or less invented the field. He's also known for his vigorous defences of GP: anybody know of real applications?

A somewhat more complete description of GP can be found at Genetic-programming.com.

Re:Genetic Programming

[call -151]

There are some "real applications" where genetic algorithms are used to solve some difficult questions in abstract mathematics.

There are a number of difficult questions in the field of research in combinatorial group theory for which no reasonable-time (non-exponential or worse) algorithms are known. Genetic algorithms have proven to be surprisingly effective for some questions in this area; I am part of an open-source project (the Magnus project, an endeavor of the New York Group Theory Cooperative) which has implemented a number of genetic algorithms in our software for computations in combinatorial group theory. See this page for a descripition of some of the genetic algorithms implemented in our software. In particular, some difficult theoretical questions that had been studied for more than 20 years turned out to be answered quickly (less than 30 seconds on a 300 Mhz PII) via a genetic algorithm approach. (The most remarkable of them was the dismissal of a potential counterexample to the Andrews-Curtis conjecture which had been very resistant to theoretical and traditional computational approaches.)

I know of other successes of genetic algorithms in research mathematics in areas like control theory and modelling, but I am most familiar with algebraic applications. In the situations described above, there are good measures of `fitness' and a good notion of two reasonably-fit individuals combining and possibly mutating to make even-more-fit offspring. It is much more difficult to apply the techniques where there is not a good measure of fitness or of combination.

My own experiments with evolved code

[melquiades]

In college, I did a project in which I attempted to evolve programs for Core Wars, in which two programs running in a virtual machine language basically attempt to overwrite each other's memory space.

My algorithm started with random programs and pitted them against each other in the Core Wars arena. The fitness function was simple: programs that beat other programs got higher ratings. Top-rated programs would "breed", and all programs would mutate. The hope was that after time, successful warriors would evolve.

And, lo and behold, they did! My algorithm "evolved" some simple bombers -- not nearly as good as what a human would write, but amazing considering I put no knowledge about strategy into the algorithm, and started with random core wars code.

Ah, but (there's always a but) I found that there was no significant correlation between how successful a warrior was and how many generations of crossover went into it. In other words, the genetic algorithm did no better than an algorithm which simply selected lots of random programs and kept the ones that work. So actually, my result was not very impressive at all -- I was basically doing a brute force random search for programs, and happened to find a few.

Others might get much better results with different languages, because Core Wars machine code does not lend itself to crossover (i.e. it's had to merge two Core Wars programs into a better program). Functional languages do a bit better with this. But I really doubt that Genetic Algorithms will prove useful in the near future for generating any sort of code that wouldn't be trivially easy for a human to write.