genetic
mighty biomorphin’ power rangers
It’s been a while since my last post, mainly because I’ve seen a lot of impressive work in various places and I’ve felt very small and insignificant in comparison. I also went on a training course recently which claimed that 80% of people achieve only 20% of their potential. As someone who likes to potter about and explore different things, I know that I fit into this category. Perhaps I ought to buckle down and concentrate on one particular thing. But the use of the word ‘ought’ is enough to put me off. Like most people, I’m not good at persevering at something I’m not been interested in.
I’d been feeling this despondency to such an extent that I was beginning to wonder whether I’d reached the end of my little experiment in genetic algorithms. For various reasons I’d not had a session with Ollie on Skype for several weeks until tonight , and I was starting to wonder whether it was worth chasing down every little aspect of code. I know now how to implement these algorithms, so perhaps it was time to move onto something else.
Well, how foolish was that thought? Very.
Tonight’s session was stimulating. Ollie suggested a technique to overcome a particular coding problem (showing me that I needed to convert in one place from an Integer object to a primitive int), as well as getting me to think of a way to speed up the routine that checks whether each fly has been trapped by a web. Those are both very useful for the sketch, but what really got me interested was the discussion afterwards about where we could take this next.
I was getting bogged down in the appearance of the sketch and in the limited number of characteristics included in the coding. So far I’ve been using ellipses as a quick and dirty representation of webs. These are both boring and limited, but because the webs are a class, it would be easy to replace the ellipses with something else, such as Richard Dawkins’ biomorphs. Rather than use human intervention to select which creatures breed, they could be ranked on their success in trapping flies. This opens up a lot of possibilities. If a fly successfully moves past the outer edge of the biomorph, then an inner arrangement would be useful to add another layer to trap it. This means that sheer size isn’t the only aspect of a successful predator.
The more successful webs could have more energy to use in the next generation, so some might evolve to require lots of energy but therefore need to trap a lot of flies, while others might need less, and therefore survive on very few flies. It would be possible to reach a point where some creatures have evolved so far from each other that they can’t breed with each other. The flies could evolve too. Very soon there could be enough complexity that it would be difficult to predict the results. Suddenly I’m very interested again in this exercise.
private functions
I’m on a roll now, with a second abstract class, this time to handle the breeding of creatures. I’ve kept it general, so it could be used for other genetic algorithm sketches.
One method, for the first generation, returns a string of random 1s and 0s, while another (still to be tested) accepts two ‘parents’ and breeds them, with an optional chance of mutation. I’ve also moved some functions, such as building the webs out of the DNA, into the web class and made them private so they can’t be accessed from outside. It’s all looking a lot more organised and controlled.
gray matter
Last night’s session with Ollie Glass in developing a genetic algorithm for spiders’ webs led to discussion of Gray code in place of binary numbers to represent characteristics of the webs. I’d never come across the concept before, but I can see the benefits for genetic algorithms. Two successive numbers only ever differ by one bit, so an arbitrary mutation of one bit won’t lead to a massive change in value. (The rest of the discussion on Wikipedia left me cold though.)
There won’t be a session next Monday, but I’ve got a lot of work to do to follow up the material we covered last night. This is where the algorithm starts…
and then there was one…
I’ve completed the next step in my genetic algorithm project: collision detection between flies and webs, based on the colour of the pixels.
It’s slowed the code right down, so as a first step in improving its efficiency, I changed it so that it only checks flies that haven’t already been trapped. Without any other improvements, it means that the remaining flies appear to move faster and faster, as though they’re trying to escape, until the last fly, alone in a dangerous world and surrounded by the corpses of its fellow creatures, desperately searches for salvation until it too is inevitably trapped and killed.
Empathy for a few pixels? What a ridiculous idea!
genetic algorithms for webs
I had the first Skype session with Ollie Glass last night, where we discussed the first stages of exploring the use of genetic algorithms to evolve spiders’ webs. It was very useful, and I learned a lot.
The first reveleation was a different technique for checking to see whether a web had trapped a spider. I’d assumed that we would have to check each strand of each web for every fly, and suggested that we ran a first-pass check to see whether a fly was within the outer edges of a web, and only if it was would we then run a more detailed check against each strand.
Ollie, however, suggested a cunning alternative: check the colour of the pixel that a fly was on, and if it was web-coloured then it would be trapped. The downside is that this technique wouldn’t identify which web had trapped the fly, which would be important if we were going to rank webs according to how many flies they succeeded in catching. Or would it? Each web could be a very slightly different colour, so the colour of the pixel the fly was on would, in fact, identify the successful web!
We then had a fascinating discussion on whether the detection routine should be a method for the ‘fly’ class or the ‘spider’ class. In the end, we agreed that although it might be more realistic for the web to detect the presence of a fly, it was a neater programming solution for the fly to check, since we would only have to check one pixel per fly, rather than every pixel of ever web. The fly would then send a signal to the environment (in the shape of the overall programme), which would in turn signal other parts of the environment.
Discussion turned to how we might develop the webs. Ollie was keen to advance in small increments, though keeping a note of ideas for fture stages, which makes sense, and is well suited to the approach of object oriented programming.
Immediately after the session I tried to write the code for checking the colour of pixels. We’d run a small sketch during the session to test it, and the principle worked fine, but my first attempt for the web simulation slowed the code to a crawl. I’ll try again, reducing the number of flies, and see if I can code it more efficiently.
what a tangled web we weave
I’ve started work on my first genetic algorithm, to see if I can evolve spiders’ webs. Ollie Glass in Brighton will be helping me via Skype, and our first session is scheduled for tomorrow evening. So far I’ve built a simple test, creating objects for the flies and the webs, to refresh my memory of Processing. I’m keen to see what we can achieve.
Sorry, no Tweets were found.