Slashdot Mirror
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*?"
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.
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.
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.
Tired of free ipod spam sigs? Opt ou
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.
.sig
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.
;-)) with self-improving programs.
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
"Knowledge makes us accountable." - Che Guevara
If not, might I suggest getting out more?? :)
"They do not preach that their god will rouse them, a little before the Nuts work loose." Kipling, 'The Sons of Martha'
I've experimented with some of this myself during my free time. It was nothing incredibly complex, however I used the basic concepts of protein synthesis and enzyme function to operate on a 'DNA' code base that was dynamically mutated and generated.
While the 'enzymes' and 'proteins' were fixed during my experiments, they certainly could be mutated and evolved in more advanced versions of my programs.
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.
Anyhow, what I menat to get to was that a model like this could certainly be distributed much like Bovine or SETI. A central server distributes 'DNA' to the client machines as well as a series of environmental test suites to measure their development. The client machines would iterate the DNA code through the test environment and mutate (or even breed) successors to the original DNA so as to discover a more efficient GA. The result set as well as the DNA fragments would then be transmitted back to the Server for analysis, processing and ultimately re-distribution.
An additional benefit of this approach would be that if a single genome is sucessful on a large number of systems it would be relatively easy to identify.
While my inital experiments were written in C, I eventually migrated to C++ (which actually made it much more complex.) However for a distributed client, the use of java would likely be the most efficient, espesially for the distribution of the testing environments.
I'm done with sigs. Sigs are lame.
EE may not be your cake, but at least you knew it was EE. Broadly speaking, there are two kinds of digital logic: combinatorial and sequential. Sequential digital logic is basically combinatorial digital logic with some feedback wires. An RS flip-flop is a couple of digital logic gates with the outputs fed back as inputs. This means that the output of the RSFF depends not only on its current inputs, but its current outputs (i.e., its current state) as well. So, in its most basic sense, an RS flipflop is (maybe) the simplest implementation of a finite state machine. The GP page this post links to uses feedback in much the same manner - the synthesized mutation code and crossover code are fed back into the GP systems. Given that many systems considered for analysis are inherently non-linear, this is probably a good idea - are brains would not be the wonders that they are without feedback.
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.
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.
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.
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
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:p ?theisbn=3540606769&vm=p ?theisbn=155860605X&vm=
http://www1.fatbrain.com/asp/bookinfo/bookinfo.as
http://www1.fatbrain.com/asp/bookinfo/bookinfo.as
Carlos
This got me intrigued, so I hopped on to Google, and, lo and behold, this is what I found. Probably one of the more interesting works that I have read online in quite some time, although there were parts that I didn't understand since I haven't yet taken enough coursees in high math to properly comprehend them.
--sdem
Number of descendants that are _fit_ is the definition of fitness. :->
Having 20 children that all die before having children of their own doesn't make you fit.
My Journal
I've always been impressed by things like Tierra. You write an environment where self-replicating programs have to compete with each other for space and runtime. Factor in the occasional mutation and the ancestral program (70 or 80 commands) evolves, after several million generations, into a whole panolpy of organisms. There were simple ones that could replicate using only 30 commands, then there were parasites on those that could do it in 20, ones that could only replicate in the presence of a similar program, parasites on the parasites, all sorts of things.
Dyolf Knip