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

Great..

[VFVTHUNTER]

Someone took a GP algorithm and superimposed it on the architecture of an RS Flip-Flop. On the plus side, with all of /.'s traffic, they probably won't have a hard time finding someone to fill that open position at the bottom of the page.

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.

GA Archive

[metlin]

Check out the GA Archive. Great collection of the more famous GA's and proceedings.

For those wishing to get an intro to GA, try The Hitchhiker's Guide to Evolutionary Computation.

Why genetic algorithms are powerful

[Alsee]

A common misconception is that genetic algorithms are based on mutations. For example someone here said:
random mutations used in genetic programming are about as efficient as real random mutations. They get the job done eventually, but require a lot of screw-ups to make one improvement.

Mutations are a red herring. Genetic algorithms produce results faster without mutations. The benefit of mutations is that they allow the search to go farther - potentially indefinitely - and produce better results.

The power of genetic algorithms comes from impicit parallelism. This can increase the search rate by a factor of over a billion. There is a complicated mathematical anaylsis, but here is a description:

one of a genetic algorithm's most important qualities is its ability to evaluate many possible solutions simultaneously. This ability, called implicit parallelism, is the cornerstone of the genetic algorithm's power. Implicit parallelism results from simultaneous evaluation of the numerous building blocks that comprise the string. Each string may contain millions of these building blocks, and the genetic algorithm assesses them all simultaneously each time it calculates the string's fitness. In effect, the algorithm selects for patterns inside the string that exhibit high worth and passes these building blocks on to the next generation.

That's called bloat

[carlossch]

An interesting side effect was that as a strain of 'DNA' evolved it became longer and longer. Upon tracing advanced mutations I found large sections of the genes to go completely unused.

The growth of the proportion of introns (genetic code which does not directly influence the fitness function) to exons ("relevant" genetic information) as the fitness of the individual grows is a reasonably well-documented phenomenon in GP communities, and is commonly called bloat. "Relevant" because, despite conclusive evidence, most researchers believe that the introns are also relevant to the individual, even if not directly.

For example, mutations can occur on introns without any direct change to the individual. As introns are comprised essentially of copies or parts of original genetic code, they probably provide a place where mutations to possibly beneficial (albeit inactive) genes can occur safely.

Besides that, as bloat increases, the active genetic code decreases in proportion, and as a result you get a kind of 'clustering' of active genes, which is a good thing, because the chances of a disrupting crossing-over go down.

A great book on the subject is Genetic Algorithms + Data Structures = Evolution Programs, by Zbigniew Michalewicz (but I'm not sure if he covers bloat in the text). I remember reading a paper on bloat in one of the Springer-Verlag Lecture Notes on Computer Science about Genetic Programming.

Now, to see some really wacky and interesting things, the book to read is Evolutionary Design by Computers, edited by Peter Bentley, with lots of nice papers to read (and a kickass foreword from THE MAN Richard Dawkins)

Links for the paranoid:
http://www1.fatbrain.com/asp/bookinfo/bookinfo.asp ?theisbn=3540606769&vm=
http://www1.fatbrain.com/asp/bookinfo/bookinfo.asp ?theisbn=155860605X&vm=

Carlos

Re:if only it were that simple

[Alsee]

Sorry, that is _not_ a fitness function for humans
In the context of evolution, number of decendants is the definition of fitness.

but having many kids does not make a person _fit_
In the context of evolution it does. Everyone dies. The genes of people with decendants survive.

Economic success may give a competitive/survival edge, but it tends to correlate with lower birth rate. Mental instability and drug abuse may threaten survival, but they tend to correlate with higher birth rates. Nature's finess function has nothing to do with rational judgment.