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.

43 thoughts on “Genetic algorithms become programmers themselves

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

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

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

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

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

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

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

  2. 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…

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

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

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

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

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

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

  5. 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…

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

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

    1. 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…

      1. 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”

        1. I meant “Genertic programming did not provide very impressive results, but still much more impressive than that.”. Sorry.

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

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