Friday, May 20, 2011

Genetic algz

[edit: guess I should make it more clear that I don't intend this to be an example of good practice, It is just the result of a game.

When I start a new project in Python, I often ask myself what features of Python could make this project better. A natural enough question if you are learning a language, and I think it is vital to try new things as often as possible in programming (unless you're programming in a production environment, then by all means steer clear).

"So", I asked myself, "what could Python possibly assist with in the implementation of a genetic algorithm?". Now using lists were an obvious choice: slices could take a bit of the load off of programming a cross-over function. Boring.

For the uniniated, "cross-over" is performed in a genetic algorithm when two or more organisms trade contiguous segments of their gene data. In simple enough terms, this is thought to preserve favorable segments of genes (those that contribute to fitness) instead of relying on the same favorable mutations to occur in multiple organisms.

One could easily use a list, or code their own structure that would accomodate this behavior. After all, it would be simple enough to iterate through a list and just exchange elements.  But I wanted to be more general, and to do something that would be a bit more difficult in most languages. So I used vars(). Leveraging the ability of dynamic typing and local variable lookup, we have the ability to perform cross-over on relatively arbitrary objects (no guarantee what is produced will work). Because python allows us to change function binding dynamically, we can also do this with functions (though I suspect this isn't as easy to make use of, perhaps with currying and large set of lambdas. one could find a way.)
        def meta_mate(self, matee,mater, rand_func = None):
                #uses pythons ability to get a dict of local variables in order to allow us to switch them without knowing anything about them
                child = organism(self)
                if not rand_func:
                        return
                for x in vars(matee).keys():
                        if x in vars(matee).keys() and x in vars(mater).keys():
                                if rand_func():
                                        vars(child)[x]=vars(matee)[x]
                                else:
                                        vars(child)[x] = vars(mater)[x]
                        elif x in vars(mater).keys():
                                vars(child)[x] = vars(mater)[x]
                        elif x in vars(matee).keys():
                                vars(child)[x] = vars(matee)[x]

                return child

(I realize I can do this with zip, if expressions and a lambda, but for blogging purposes I decided to do this in more than one line)
Iterating through the local variable lookup dict and switching items seems to be a nice way to achieve cross-over. Unfortunately I can't think of a very good way to implement a generic mutate() function like this, so this isn't as useful as I'd like. If anyone has any ideas, feel free to comment!

1 comment:

  1. I agree, python is the best way to implement genetic algorithms. The last month I wrote some genetic algorithm in Java and I missed a lot of features of python :)

    ReplyDelete