Evolving Applications with Genetic Programming

I’ve written in the ability to test a program by giving it an input, and seeing what it does each step of execution (well, perhaps that’s misleading – 95% of that functionality is in schush from the get go; it just needs to be organized and tailored to the problem at hand). The programs I evolved last night all were successful, although they behaved in very different ways that I might have expected. One program, for example, took advantage of the instruction ‘integer.fromboolean’, which returns 1 if the top of the boolean stack is #t, and nothing otherwise. Remember, a virtual keypress value of #t means we want to add 3 to the input, and #f means we want to simply print the input. This successful program simply called integer.fromboolean three times and then added. If I were to switch which keypress does what, however, this whole method of operation would be rendered completely useless; the same would be true if I tried to add something no matter which key was pressed – say, add 1 if #f and 3 if #t.

Harshit and I have a meeting scheduled for tomorrow, where we’ll figure out what else we want to have in the code, and start divvying it up. Things should move much quicker now that the basics of schushGP are a little clearer.

As I write this schuschGP runs steadily in the background, recombining and mutating thousands of little programs. I’ve been playing with the program for a while now, but it’s taken a bit of time to really understand it, especially because the syntax of scheme still can throw me for a loop (plus Lee had to point out a few really obvious, glaring errors that I was skimming over).

Right now I’m trying to evolve a program which does a different mathematical function depending on what virtual key is pressed; in the current iteration, a virtual keypress of ‘k’ should simply print the input integer, while a keypress of ‘not k’ should produce the input plus 3.

It has yet to succeed, but it’s getting there. The very first functional run of the complete fitness function produced, after a few generations, this bit of code: (in integer.fromboolean integer.+ code.do*). It doesn’t look like much, but it has a few elements suggesting some degree of success – the instruction “in”, for example, is one which I added to the code generator which gets the keypress and adds it to the boolean stack, which is why seeing ‘fromboolean’ is also a good sign. Since then it’s only been improved.

A lot of previous missteps have been informative. For example, initially the two things the code was supposed to be able to do was either add or multiply. The problem is that multiplication produces larger and more varied values, while addition (for a set range of digits, of course), produces a smaller range of values. The success of the program is measured, primarily, by the difference between the correct result and the actual result; multiplication had more potential to produce a larger difference, and so addition was always favoured, and the programs would add but stalwartly refuse to multiply.

A better solution, it seemed, was to create something which, no matter which keypress was evaluated correctly, would have the same error value as the other keypress. Printing the input with a keypress of ‘k’ and subtracting 2 from the input on a keypress of ‘not k’. In most cases, this would produce a symmetrical error weighting, except in the case of the number 1. In a ‘not k’ case with this error function we perform 1 – 2 = -1. A a negative error value would imply a better answer than the right answer, however, so we have to take the absolute value of this number, producing a value of 1. In a ‘k’ case, we simply print 1. Because the answer to both is one, a false positive occurs. Any program which can print 1 in any way has the potential to succeed. The computer seemed to like taking the length of the code stack and calling it a day.

Similar missteps were abound (for a while I tried storing keypresses as integers, 0 being one button and 1 being another, until I realized it was extremely easy for a program to just print the keypress value and, if it was zero, immediately succeed. They’re Boolean now) but things are off the ground now.

-Nate

Hello,

The goal of this project is to evolve a functional, complete program using PushGP. Because this is a complex task that has (to our knowledge), never been completed, the program should be simple enough that it is possible to create; any program should be an impressive first. We have decided to work towards creating an address book. The interface and visual components of an address book can be very basic; it is essentially a fancified database. The program needs to store and retrieve information and link it (name, phone number, email, address, personal notes), as well as keep track of various states, such as whether it is in edit mode or not. The functions would include creating a new entry, editing an entry, deleting an entry, and a search function.

That is already everything an address book would need to perform to be considered ‘complete.’ The first step is to evolve some of the guts of this system, without worrying about actual user input or creating a GUI. Keypresses and other possible input are simulated.

This is where we are now; I have been trying to create fitness functions in schushGP which can discriminate between keypresses, with no direct success but ever-progressing comprehension of why it’s not succeeding.

-Nate

Welcome to i3ci. This is your first post. Edit or delete it, then start blogging about your cool Computer Science project!