Showing posts with label python. Show all posts
Showing posts with label python. Show all posts

Saturday, December 13, 2008

Genetic programming and stuff

So a few days ago, I was shown this page. It takes an image as input. Basic, but probably somewhat flawed explanation: the output starts out as a number of invisible polygons, and at each step of the algorithm a random attribute of a random polygon is randomly changed. If this looks more like the source image than does the last mutant image, this result is kept and more changes are made to it. This goes on and on and on. The results can be pretty amazing if you let it run for an hour or two.

Now, I suck at Python, and this implementation was written in Javascript, which I have little understanding of, so I can't learn all that much from the actual code. In a book I have on Ruby, Ruby by Example: Concepts and Code, though, I recalled a section on a somewhat similar evolutionary program that is meant to operate on strings. The concept is similar: a target string is given, and a candidate string of the same length is randomly generated.
In my implementation (which I'm currently working on), a mutation is made to a random character in the candidate string, and if that mutant's fitness (mathematically, 1 - (current difference between target and candidate) / (maximum difference)) the target is higher than that of the current candidate, we make that mutant the candidate. Eventually, depending on the length of the string and how my random number generator's feeling today, it will reach the target string. For observation's sake, we'll output the current candidate every X number of steps.

Now, I am not a computer science major nor have I read that much on it, so I'm not that up on terminology and concepts. This is an interesting concept to me, though. It's a decent analog of biological evolution, but it's a bit oversimplified. For one thing, in biological systems detrimental mutations do sometimes propogate. This model instead throws out every mutation that is not beneficial. Another thing is that this model forces mutations to occur at every step, whereas they're far less common in nature.
Also, this scheme only simulates asexual reproduction, in which only one parent is needed for reproduction. Most animals we're familiar with, though, use sexual reproduction, which involves two parents. In the former, you only get one set of DNA to mess around with. With the latter, though, genetic diversity (and thus chances of a better match) increases as you have two separate sets of genes being mixed and matched. This could be implemented in a way similar to that of the first string-evolution program, except we would start with two distinct random strings, and make mutations to each of those. At each stage of reproduction, however, instead of making changes, we force the two candidates to "breed": take the DNA of each, and randomly assign a weight of 1 to an attribute (in this case, letter) of one parrent and a weight of 0 to the corresponding attribute of the other parent. X number of offspring are produced, and a random mutation is made to each one. The two best mutant offspring are then mated and we continue the process.

Now, my idea of simulating sexual reproduction in this way might be a bit faulty, but if it is I'll find that out soon on my own. Also, it's a bit gross (and, if were we dealing with biological organisms with some recessive detrimental mutations, error-prone): since the offspring that mate are from the same parents, it's pretty much cyber-inbreeding.

Anyways, those are some of my ideas. Feel free to think they're stupid or to not understand them, but in the meantime, I'll try and finish up my implementation of the asexual string evolution.

Toodles for now.

Thursday, December 11, 2008

pybrain4.py - First release

Well, here it is. It can be imported into an interactive python session, or run from the command line with something like:
python pybrain4.py file.b

Additional documentation can be found by calling it with the '-h' or '--help' flags.
Among other things, I'll work on trying to speed it up a bit.

Also, this has only been tested on OS X Leopard with Python 2.6. Compatibility will almost surely be broken with 3.0, but should probably work in 2.5.
Let me know if you have any problems.



Some Brainfuck programs to try out:

Tuesday, December 9, 2008

I am a complete idiot and I suck at not being a complete idiot

Turns out the problem causing the infinite loop in the Brainfuck interpreter was, well, an infinite loop. I know, I know, it must've been hard for me to catch. Please hold the applause.

I had forgotten to implement the somewhat important part where, you know, the while loop actually works. I had forgotten to add a check to see if the current cell is 0, thus making the loop somewhat useless.

Now I'll go try some other code and probably find new bugs.
Oh boy.

About that interpreter...

Unsurprisingly, it's not working on its maiden voyage. Not unlike the Titanic, except that killed fewer people.

It worked on a small snippet of code, but not the 'hello world' script posted earlier. Rather than doing what it's supposed to, it's not. I expected about that much, though. At least it's going out in an infinite loop instead of some sissy syntax error.

More as this catastrophe develops further.

Hullo, I am Guff and I am bored and I have a Python installation.

And goddamnit, I'm going to use it.

Brainfuck is a very silly programming language. But I suppose that's to be expected when you set out with the intention of making a language that's as frustrating as possible to use. There are far more difficult esoteric languages out there (Esolang is a good resource), and Brainfuck is very easy to understand. The difficulty comes from actually getting it to do anything. For example, here's a 'hello world' program written in Brainfuck (from Wikipedia):
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++
..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
(the line break is not significant and should be ignored by most interpreters)

Simple, right?

Now, how does this all work (I'd recommend skipping this section if you're already familiar with Brainfuck)? Well, first off, the standard implementation only recognizes eight characters as Brainfuck operations: <>[]+-.,

Secondly, think of the Brainfuck environment as a contiguous series of cells. The size of cells can vary based on the implementation, but the most common would seem to be a single byte (meaning the maximum value a cell can hold is 255, assuming unsigned integers). The number of such cells also varies; the original implementation, I believe, used 30,000 cells. Now think of there as being a cursor that points to one of these cells. When your program starts, it will be pointing at the first cell.

Now, back to the operators. The <> operators move the cursor to the previous cell and the next cell, repsectively.
[ signifies the start of a loop, and ] marks the end. When the end of a loop is reached, if the current cell is not equal to 0, the program goes back to the corresponding [ operator.
+ and - increment and decrement the current cell, respectively.
Finally, . prints out the ASCII character corresponding to the value of the current cell, and , takes a character as input and sets the current cell's value to the ASCII value of the input (e.g. 'a' -> 97).

Okay, so now why am I rambling on about this? I dunno. I'm kind of bored and I've been learning Python for some time now and yet I still kind of suck at it. It's either this or a Lifetime movie about an evil baby or something. Also, I find Brainfuck's simplicity fascinating. It's a very interesting language, even if it's almost entirely useless and a pain to write in.
So my goal is to write an interpreter in Python. I'm currently just in the planning stage, but here's what I've got so far:

The basics:
  • Take a file or string as input
  • Get rid of every character that is not a Brainfuck instruction, to make things easier
  • Check the string to make sure the code is well-formed, i.e. the braces are paired up correctly
Now, that's not that hard. And actually implementing the instructions properly shouldn't be either. The problem is that Brainfuck is not a rigorously specified language. How should I implement it?
  • What should the cell size be? Well, I think I'll allow for user-definable cell sizes. By default, cells will store Python's int type, which would also automatically switch over to long when the value becomes too large for int to hold (Python 3.0 doesn't make such a distinction; ints can be arbitrarily large). If this is the case, negative values would also be allowed. At least, I can't think of a reason not to. If a maximum cell size is specified, however, overflow will reset the cell to zero, and decrementing a cell of value zero will set it to its maximum value.
  • How many cells? User-definable, or unlimited? The latter would automatically create new cells when the need arises, and I'm thinking this is the most sensible solution.

I think that's about it for now. I'll post again after I make some actual progress.