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

if only it were that simple

[rossjudson]

Please. Two notes on a page? Breakthrough? Hah. It's a hell of a lot tougher than it looks.
Read Koza's three tomes for extensive research on genetic programming (the art of developing programs through genetic-evolutionary techniques).
Read about particle swarms if you want to learn about an evolutionary technique that is quietly kicking the ass of most others wherever it is used.
From a theoretical point of view, this feels like it won't solve or do anything that can't be found within the solution space anyway, by another technique.

Re:if only it were that simple

[xmedar]

The main problem is what is not shown, i.e. the fitness function, for those that don't agree I challenge you to derive a fitness function for human beings, when you start finding that the fitness function is partially given by the humans themselves and the technologies and social organisations they adopt (i.e. humans are part of the problem space too) you suddenly find that what looked easy is actually not. The system described on the webpage is a "solution" in the same way that economics has a "solution" by specifying that supply/demand curves are given and not derivable and therefore misses the point. Certainly genetic algorithms are useful for well defined fitness criteria, unfortunately much of life is so intertwined that actually defining it is not possible.

Re:if only it were that simple

[shibboleth]

A fitness function should return maximum value on correct data, minimum value on random data, and intermediate values for data with varying amounts of random errors.

If you had code that could determine how correct your data is that's all the fitness function you need.

The problem of how to break down complex programming tasks into GA-buildable algorithms is often very difficult for a knowledgable and intelligent person much less a computer program. Therefore an automagic general case solution is in my opinion impossible until there is a general and flexible art. intelligence, something I believe no one has much of clue how to build. The good news: it's fun to try in the meantime.

It's the fitness function, stupid...

[Anonymous Coward]

The biggest problem with any genetic system is testing fitness. It has always been that way, and always will. The genetic system can only be as good (regardless of computing power) as the fitness function. Find a way to improve THAT automatically, then you will have true machine intelligence with infinite potential.

How do you define improvement?

[Fuzion]

The problem with self-improving programs using Genetic Programming, is that the problem inherent in the process of evolution are present in the programs. When species evolve, it's not always for the better, there have been cases where evolution has made things worser than before.

This might not be noticable for relatively simply programs, but on a very complex program, how do you tell if a certain modification introduced by the system, is actually an improvement? What if the modifications makes the program slightly faster, but introduces long-term problems?

I think this is one of the biggest problems (other than the programs becoming sentient, and taking over the world ;-)) with self-improving programs.

Re:Genetic Programming

[Some Dumbass...]

Which is why efforts at AI programming will continue to require human interaction for the foreseeable future.

No kidding. And in related news, educating humans will require human intervention in the forseeable future.

Obvious, eh? Almost as obvious as the idea that the 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.

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.

Re:My own experiments with evolved code

[Animats]

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.

That's not unusual. Any broad-front search (which includes genetic algorithms, simulated annealing, and neural nets) should be tested in this way. Both ends of the search spectrum - pure hill-climbing using a greedy algorithm, and random search, should be tried. Unless a more elaborate algorithm beats both of them, it's not accomplishing anything.

This is an embarassing truth which GA researchers hate to hear. But GA people need to do this validation or they waste time on problems for which GAs are unsuitable.

Re:Why genetic algorithms are powerful

[Alsee]

Most sorts based on divide-and-conquer are O (n log n), while most based on nested loops are O (n^2)). This isn't a matter of replacing a building block, but rather the whole algorithm!

This issue is well known and studied in the field. A genetic algorithm randomly searches for a solution. If it happens to focus on a nested loop method it will probably converge to an extremely efficent form of O(n^2). This is known as a local optimum. Depending upon how the genetic algorithm is set up it may or may not be able to discover an O(n log n) solution given time. For one thing, a larger population size helps.

The most common solution is to run the genetic algorithm from scratch a few times so that different random strategies get tested. Another technique is to co-evolve "parasites". First the sort programs converge on a solution and they all start to look alike. Then the parasites home in on the sorting programs. The sort programs start to diversify to escape the parasites. The "fleeing" sort programs explore for different algorithms to use.