Genetic algorithms become programmers themselves

AI

[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.

Comments

  1. Nico Nimleth says:

    Nice :D

  2. Andrew says:

    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.

    • MrX says:

      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.

      • draeath says:

        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.

        • adcurtin says:

          “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.

          • Guillaume says:

            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.

          • Dutado says:

            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.

      • Someone asdf says:

        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).

  3. xorpunk says:

    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…

  4. janek says:

    Genetic Programming is not exactly a new idea: http://en.wikipedia.org/wiki/Genetic_programming
    But using brainfuck is an amusing thought :)

  5. dur says:

    I find it duly fitting that the language chosen for GA-bred programs is called “brainfuck”.

  6. Nutrino says:

    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.

  7. T80 says:

    As a Fallout player; that looks easy to hack.

    …I’ll see my self out.

  8. robomonkey says:

    I welcome our new AI overlords.

  9. qwerty says:

    Now rewrite it using the Chef programming language and eradicate world hunger forever:)
    http://esolangs.org/wiki/Chef

  10. disappointed_dad says:

    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.

  11. Jon says:

    Tee hee . . . “Hello worldgaY”

  12. 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.

  13. derpa says:

    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…

  14. sam says:

    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.

  15. haltux says:

    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.

    • xorpunk says:

      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…

    • Ryan says:

      And where do you get the “without realizing that so many people have been before” bit?

      • haltux says:

        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”

  16. the5322 says:

    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.

  17. I think that the Spiral FFT package has a similar approach to making FFT code.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s