[Kory] has been experimenting with genetic algorithms. Normally we’d expect his experiments to deal with tuning the variables in a control system or something, but he’s doing something much cooler. [Kory] is using genetic algorithms to write computer programs, and in the process bringing us one step closer to the Singularity.
The first experiments with genetic algorithms generating applications did so in BASIC, C, and other human-readable languages. While these programs nearly worked, there were far too many limitations on what could be produced with a GA. A simpler language was needed, and after turning to assembly for a hot second, [Kory] ended up using brainfuck, an extremely minimal but still Turing-complete language.
The use of brainfuck for creating programs from a genetic algorithm may seem a bit strange, but there’s a method to [Kory]’s madness. It’s relatively simple to write an interpreter the GA’s fitness function can look into and come up with a score of which programs should breed and which should die. Also, the simplicity of brainfuck means a computer doesn’t have to learn much syntax and grammar at all.
Right now, [Kory]’s computer that can program itself only does so by creating simple ‘hello world’ programs. It should be possible, though, for this AI to create programs that take user input and generate an output, whatever that may be. Once [Kory] is able to have the computer generate its own fitness functions, though, the sky is the limit and the Singularity will be fast approaching.
45 thoughts on “Genetic Algorithms Become Programmers Themselves”
Interesting… The harder problem is deciding what the fitness function should do, i.e., what qualities should make one program more fit than another? And, letting the computer ‘decide’ still doesn’t provide an answer to the question because, even then, someone needs to decide what criteria the computer will use to determine the best fitness function.
You also have the infinite loop problem, how do you detect one? For a programmer it is obvious to detect when a computer stopped doing anything useful and is just looping over. For a computer being able to detect that, it is a entirely different story.
It should be possible for the system to look at what is changing, and check to see if that will reach any branches or break conditions in the future.
Eg, if it’s iterating until n = 10,000,000,000, and n is currently at 1235879 and increasing… it’s not really in infinite loop. This should be detectable.
“it should be possible”
heh. This is a huge problem in computer science. It’s called the halting problem: http://en.wikipedia.org/wiki/Halting_problem
basically it is impossible for a computer program to tell if it will or will not halt. If it can, then p=np, and a proof of that has a million dollar prize.
It is not simple by any means.
The halting problem has nothing to do with P=NP. The halting problem simply says that it is impossible to compute whether or not a program will halt, for all possible programs and all possible inputs. You can compute the answer for some of them, but not all of them.
P=NP has to do with the efficiency of algorithms, and whether or not certain problems are solvable in more efficient ways. It has nothing to do with computability.
If the piece of code did contain a infinite loop, how can that get evaluated? Just add a timer. Eliminate variants running for more than, maybe 10 seconds. I think we eventually “solve” the halting problem, of course it can’t be properly solved, but our nervous systems should have been doing that for thousands of years by now.
Isn’t it what watchdogs are for? If you have some counter (or any timeout circuit) and increase it permanently and let the program reset it periodically during the code, you can tell something went haywire when overflow of the counter happens.
You don’t really have an infinite loop problem. The point of a genetic algorithm is to evolve into a better solution.
If it finds any solution, then the genetic algorithm would discard any solutions that require more time (or other qualifications like memory, etc., whatever your fitness algorithm deems “fit”) — infinite loops would be out.
It may miss some solutions that “if it hung on for a few more iterations”, but that’s what your fitness algorithm would weed out (or include).
I did this one weekend a year ago and posted it on some botting forums, but I called it a macro generator, it generated web scrapers…
Genetic Programming is not exactly a new idea: http://en.wikipedia.org/wiki/Genetic_programming
But using brainfuck is an amusing thought :)
Yeah. “That’s an interesting square wheel you’ve invented there. You might want to have a look at the round ones others have been working on as well…”
I find it duly fitting that the language chosen for GA-bred programs is called “brainfuck”.
The fitness test for a generation should not be if it can compile something, but if what it compiles can compile something (the point being to make the program something like twistable DNA). You’ll need to compile twice (or more? I haven’t thought this through for more than a few minutes here) before you can make a determination to keep the grandparent around or not. And no, not trivial.
Indeed. Not only that, he also must program a “purpose” into the fitness function. Otherwise the generated programs will have no functional purpose despite being syntactically correct.
That’s almost a philosophical point, huh..
As a Fallout player; that looks easy to hack.
…I’ll see my self out.
If only. The fitness function for analyzing Fallout hacking minigame results is Mastermind.
I welcome our new AI overlords.
Now rewrite it using the Chef programming language and eradicate world hunger forever:)
You have got to be kidding. What a stupid name for a language. This project will never be more than a dorm room joke. No corporation will ever adopt it’s use. No professional programmer will ever include it on their resume.
Sir, I hope that you’re the one doing the kidding.
That’s kind of the point.
Brinf*ck is a joke. It’s mean to be funny, to be esoteric in a funny way, not to be actually used except for fun purposes.
Using it for genetic programming is kind of a joke as well, though it is not clear whether it is purposely a joke
If you can see no reason this was made beside profit-seeking or a genuine attempt to leave a lasting mark on the CS world then I don’t know what to tell you except that maybe you need to reflect on why you visit this site.
It’s the name of the product not the non-profit angle. Go ahead, put it on your resume, fortune 500 companies will not think it is funny. Say the name of the product to a group of women co-workers and you will be escorted out of the building.
And nobody here disputes that despite your posts. You’re arguing with the empty air at the moment.
Tee hee . . . “Hello worldgaY”
If you could generate the smallest programm that generates a long distinct number,you could probably win some serios money here: http://prize.hutter1.net/
Generate the shortest program that can calculate Pi to some million digits would be awsome-amazing-xxl start.
If the programmer allows the programs to write their own fitness function, wouldn’t the most successful program simply output extremely high fitness metrics irregardless of what the program is meant to do? Like the selfish gene theory…
Kind of like using exploits to get ludicrously high scores in a game, without actually completing the game objectives.
Well, you would need a fitness function for the fitness functions…
The fitness function is the generalised objective of what the program has to do. I’m no programmer though. All I know is genetic algorthms have already been done and worked well by real programmers. Generalised as far as I understand would be some meta principle of operation, contained in the problem to be addressed by the program generated. Correct me if this is inaccurate.
looking at the motivation for real evolution survival adding threats that the program must avoid to survive would force an increase in intelligence. running multiple at the same time with some kind of communications could lead to group behaviors. I don’t know how that would be implemented programmatic thought.
That’s called Genetic Programming, and it is a well establsihed CS field.
Plenty of systems are available, hundreds of scientific papers written, and there is a dedicated conference which has occured every year for 18 years.
It is incredible that someone could spend so much time on the topic without realizing that so many people have been there before.
If you point things like that out to people who didn’t get into computers and math until it was cool, you’re considered a troll…
This predates CS and transistors and delves into cybernetics. It’s also almost a three decade old CS topic, and used in a lot of games and compilers. It’s also one of the simplest concepts in algorithms…
And where do you get the “without realizing that so many people have been before” bit?
1) No reference to any prior work is done
2) The whole approach is so naïve that it is clear that its author had no background in the field.
3) These results would be interesting iff no one had done it before. Genertic programming did not provide much more impressive results, but still much impressive than that.
4) Conclusion is pretty explicit:
“This experiment was a proof-of-concept that an AI program could develop its own computer programs that perform a specific task”
I meant “Genertic programming did not provide very impressive results, but still much more impressive than that.”. Sorry.
Almost none of the literature involves trying to evolve something that can ouput a string rather than a single number, this blog post might actually be the oldest reference on the internet to anyone doing it.
Can you get this to work on an unix system? I’m currently trying to experiment with this, but I’ve trouble running it with mono.
I think that the Spiral FFT package has a similar approach to making FFT code.
Maybe later program can make other improvements too. Right now the program contains things that don’t make sense, such as empty loops, or a right bracket immediately after a left bracket, or mismatched brackets. Following a plus sign by a minus sign or vice versa also isn’t very sensible.
Please be kind and respectful to help make the comments section excellent. (Comment Policy)