Rosio Pavoris a blog

Controversy!

August 29th, 2009 at 8:47 pm in Creationism, Programming

If you follow these things at all, you’ve probably heard by now: creationists are once again inventing a controversy where there is none, this time by pretending that it matters at all whether Dawkins’ venerable Weasel program uses locking or not, and claiming that his “unwillingness” to dig up code written in the ’80s and release it means… well, something significant.
In case you’ve forgotten what the Weasel program is, here’s a video (using a different phrase, but the same concept):

If you’re a long-time reader and that looks familiar, it’s because I’ve talked about it twice before. The experiment is simple enough that any idiot can repeat it, but of course creationists are a very special kind of idiot.
So this time, let’s walk through writing our own Weasel program and settle this once again.

I’ll be doing this in a kind of “literate Python”, because everyone understands Python and it doesn’t require compilation, so even the most technologically inept don’t have any excuse not to follow along.
If you don’t have Python installed (or aren’t sure if you do), get it here. Get the 2.6.2 one (if you aren’t sure which you need, you’ll need this one). If that’s too hard already, you shouldn’t be on the Internet in the first place.

I’ll be preceding lines of Python code with > signs, façon literate Haskell. The Python interpreter doesn’t understand this style, so I’ll also be providing a link to the final script at the end.

To recap, we’ll start with a random string composed of symbols chosen from a specific alphabet, and a target string which we’re hoping to achieve.
For randomness, we’ll be using Python’s inbuilt random module, so let’s import it.

> import random

The genetic alphabet is just “CGTA” for DNA, but ours will be a bit longer:

> alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "

Note that that includes the space at the end. We could make it even longer by including minuscules and punctuation, but it really makes no difference to the principle of the thing.
And here’s our target string:

> target = "METHINKS IT IS LIKE A WEASEL"

Of course it’s important that all symbols in the target string are also in the genetic alphabet, or we’ll never find it.

At the heart of every genetic algorithm, there’s a fitness function. In our case, this is just something that compares our string of “DNA” with the target string symbol by symbol, and just says how many symbols match. Strings with more matching symbols are obviously more like the target string, and will be selected to breed for the next generation.

> def fitness(child):
>     fit = 0
>
>     for a, b in zip(child, target):
>         if a == b:
>             fit += 1
>
>     return fit

The built-in zip function pairs items in a given list, creating a pair of the first character in both the “organism” and the target string, then the second, then the third, and so on. For each pair, it’s then going to check if both members of the pair are the same symbol. If they are, the fitness value is incremented by one. At the end, it’s returned.
This should be obvious.

Equally important, of course, is the reproduction function. Dawkins’ Weasel strings reproduce asexually, so there’s only one parent for each child. The parent copies his entire “DNA”, and each locus has a small chance of mutating.
How high the mutation rate is isn’t that important, because the point of the Weasel program isn’t to simulate real-life life perfectly, but just to demonstrate that descent with modification is more effective than a random search. Let’s give our strings a mutation rate of 1 chance in 50 at each locus. If that seems too high, remember that our genome will be 28 loci in length, so there’ll already be a lot of generations where no mutation will happen at all.

> def reproduce(parent):
>     child = ""
>     for gene in parent:
>         child += random.choice(alphabet) if random.randint(1, 50) == 1 \
>                                          else gene
>     return child

Did you follow that? Our child starts off as an empty string, and then we iterate over the genes of the parent. There’s 1 chance in 50 that a mutation occurs, in which case we randomly select a gene from the alphabet to add to the genome. Otherwise, we use the parent’s gene.
At the end, the constructed child is returned, ready to have its fitness judged.

Now that we have those two important functions, the rest of the program is straightforward. First, we construct a completely random starting point:

> parent = [random.choice(alphabet) for _ in target]

Our Adam. Let’s put him and his fitness on display:

> generation = 1
> print "%d %s (%d)" % (generation, parent, fitness(parent))

The generation variable will keep track of how many generations have passed.
We’re just about ready to enter our reproduction cycle now. Every generation, our parent will have one child, and if this child is fitter than his parent, this child will be the next parent. Otherwise it is mercilessly discarded and the parent will parent the next generation as well.

> while True:
>     child = reproduce(parent)
>     generation += 1
>
>     child_fit, parent_fit = fitness(child), fitness(parent)
>
>     if child_fit > parent_fit:
>         parent, parent_fit = child, child_fit
>
>     print "%d %s (%d)" % (generation, parent, parent_fit)
>
>     if parent_fit == len(target):
>         break

As you can undoubtedly tell, this loop will exit once the fitness of the mutating string equals the length of the target; that is, when both strings are equal.
The string "METHINKS IT IS LIKE A WEASEL" is 28 symbols long. With a 27-symbol alphabet, a random search would take on average 27²⁸ / 2 generations to match it. That's 5,986,257,591,281,009,894,301,370,013,358,523,552,840 generations. Even if we're doing a trillion¹ generations a second, that would take 189 million trillion² years to finish.


Our little program will be doing a bit better than that. The final generation number will be displayed before the final generation genome, of course, but let's rub it in again just to be sure:
> print "Finished! Target reached in %d generations!" % generation
Running it a thousand times, I got an average of 8012.58 generations. Suck it, creationists. Descent with modification and selection really is faster. Just like the last time. And every other fucking time.

And as promised, the full code is here. Just save that somewhere and double-click it to run it (you'll need to chmod +x on sane platforms, but you know that).

And that really should be that. Dembski can wave giant-sleeve-clad arms about free lunches all he likes, but in the real world, not everyone is innumerate. It’s just sad that decent people have to waste time on his bullshit.
I doubt this will actually do much good (of course it won’t; even the creationists themselves (exceptionally dense specimens excepted, as usual) realise this time that there’s no controversy here, just a giant heap of time-wasting nonsense), but if nothing else, I hope I’ve demonstrated even an elementary school student could do this. If the original code is of any interest at all, it’s because of archaeological reasons, because old code is usually interesting, not because the algorithm is that fascinating or complicated.

¹ Short scale. 10¹².
² 10¹⁸. Yes, I know the proper name for that is a quintillion in the short scale and a trillion in the long scale.

Permalink 2 Comments

So my dad suffered cardiac arrest

August 20th, 2009 at 11:31 am in Personal

And then he fell down some stairs. He was at a hospital in Brussels when it happened (psychiatric hospital, strictly, but close enough), replacing smoke detectors (he’s a fire safety person), so they reached him pretty quickly. That was yesterday. He’s currently at said hospital, under induced hypothermia (and stable), until later today.

He’d been having heart problems for a while, and after his boss had to drive him back home after he collapsed on a company trip recently, he had a stent inserted into his heart and was on a ton of medication, but obviously he still smokes and he has very irregular sleeping patterns.
I don’t know what his prognosis is, but in general these things don’t tend to go well (though the fact that he survived this far means he’s already doing better than most people).

This left his car unattended in Elsene overnight, though, so obviously someone felt the need to smash the back passenger window. So right now, aforementioned boss is driving my mom and my sister to Brussels in her PT Cruiser to retrieve my dad’s personal possessions and the car, and I’m watching the dogs. Tonight, they’re taking the train back to visit him, because visiting hours are weird and at least he’d probably be awake then.
My grandfather, who’s a bit high-maintenance at the moment for various reasons, is being looked after by my aunt and uncle, who came over from Limburg for moral support.

Last night was also the hottest night in six years, and the whole week has been hot enough that I haven’t really slept at all, so fun times.
More on the story as it develops. I’d put this on Facebook, because that’s where everyone who might care about this is, but my mom’s there too, and she doesn’t need to see this again. I’m pretty sure she doesn’t read my blog.

Update: He was still asleep when they visited yesterday, though they’d stopped the hypothermia treatment. Now they’re beginning to reduce the medication used to keep him unconscious. No real news otherwise, though the prognosis is cautiously good. It’s now Friday morning, and it happened Wednesday afternoon.
My grandfather, who’s in the hospital for being old (nothing life-threatening), will be able to move straight from the hospital to the home where my grandmother is also staying, so that’s nice.

Too many curious people are calling. I’ve answered more phones today than in the rest of my life combined.

Update: Apparently after they cut off the medicine used to keep him asleep yesterday, he got “agitated” and they put him back on it. Now they’ve cut it again, and he should be waking up “within days or weeks”. Hospital drugs don’t fuck around.

Update: Saturday now. He’s still not awake. My uncle (who’s a radiologist) is on his way from Andorra, and an MRI has been scheduled for Monday.

Update: Sunday. My uncle arrived, and already talked to the hospital’s doctor over the phone and is optimistic. My other uncle and my mom are picking him up and driving him to the hospital itself. Apparently they’re going to try to get my dad moved to Gasthuisberg, in Leuven. His doctor there (the one who placed the stent) said the stent probably collapsed (“sheer bad luck”), but he’s in Sicily at the moment, so he can’t be sure.
Haskell is humping my aunt’s leg.

Update: They’re back. He’s breathing on his own and everything, and he reacted to my mom’s voice (but not my uncle’s), so my uncle is making her visit him every day from now on. The stent is fine, it was probably an infarction, and the move to Gasthuisberg isn’t happening for the moment. And apparently it takes five to seven days on average for a person to wake up, so when the nurse said “yes” when my mom asked if it was a bad sign that he wasn’t awake yet, she was wrong. Probably a language issue.
Basically everyone’s optimistic.

Update, Friday Aug 28: I went to visit him for the first time today, and he seems to be doing well. He’s been “awake” since Wednesday, and he was really responsive today. He seemed to recognise us, and when my mom asked him to squeeze my hand when I was holding his he did. He’s still very drugged up, but I think that if it wasn’t for the feeding tube they cut his throat for, he would have been able to at least say our names, if not hold up his end of the conversation.
Brussels is a filthy, filthy town.

Update, Monday Aug 31: He’s being moved to Leuven tomorrow.

Permalink 5 Comments

Lol Github

August 13th, 2009 at 6:27 am in Personal, Programming

I’ve never had much use for source control, but after that one thread broke /prog/scrape I realised it might be useful to have somewhere centralised to put the source code and recent diffs, instead of just having a possibly-up-to-date file hidden here somewhere and having people download that whenever their shit breaks without really knowing if I fixed it yet.
Github was an obvious choice, not least because bandwagons are awesome, but then I lost interest and forgot about it until now.

Incidentally, when you create a new repository on Github, it automatically generates a URL for you to push to, of the form git@github.com:username/projectname.git. The project name can’t have any characters outside [a-zA-Z0-9-], though, so when it does they’re replaced with dashes.
Whoever wrote that piece of code, though, forgot that project names apparently also can’t start with a dash, so when you try to push to it, it just gives you an unhelpful error message:

Invalid repository url. Make sure you include the .git, e.g. git@github.com:defunkt/ambition.git

And then it breaks the connection, which is particularly nice when your first experience with git involves pushing a project named -prog-scrape.
Anyway, easy enough to fix. I do like that it uses ssh, so I don’t have to type my password every time. I’ll probably be creating additional repos for my many, many other projects that people find useful.

tl;dr: http://github.com/Cairnarvon/progscrape/tree/master

Permalink 4 Comments

Rosio Pavoris a blog

Pages

Archives

Categories

Search

Meta

Valid Brainfuck code

Controversy!

So my dad suffered cardiac arrest

Lol Github