October 16, 2005

All in the chromosomes

To begin with, at least, my robot was a dodo. I had carefully constructed a rather limited environment for her: she was surrounded by trees and morsels of food. (For no clear reason, I thought of it as ras-malai). Once I turned her loose in it, she could do one of three different things: move in a random direction, bump into a tree, or swallow any food she found. That's all. So she bumbled around doing them, without any discernible method to her moves.

I watched her roam, wondering if she would learn some lessons. I was penalizing her every time she crashed into a tree, rewarding her when she found food. Would this carrot and stick treatment work? Would her movements become more purposeful than her initial clumsy meanderings across my screen?

Screen, yes. For this was a simulated robot, an "@" on my computer screen. She lived her strange little life among simulated trees and simulated food, also on my screen. She was the product of some amateurish dabbling I once did in an intriguing area of computer science: genetic algorithms.

Why "genetic"? Just as living organisms evolve to become better at their tasks, at the business of living itself, computer models based on genetic algorithms -- my robot, for example -- evolve to become better at doing things.

At least, that's the theory.

My "@" babe was, in essence, a collection of simulated chromosomes. In some ways, that mirrors us. Our chromosomes encode our physical and character traits. We differ from each other because the information in our chromosomes differs. That is, you're shorter and more intelligent than I am because your chromosomes are different from mine. A simplified view of things, no doubt, but there is a lot of truth in it.

So in my robot's collection of chromosomes, some were sensitive to food: they reacted when she found some. Others reacted to bumping into trees. The way she was programmed, the chromosomes influenced which direction she chose to move.

To begin with, of course, none of the chromosomes favoured any direction. But if the robot found that a particular direction tended to have more food, her food chromosomes would evolve to favour that direction. And if, while heading north for example, she kept running into trees, the tree chromosomes would evolve to favour directions other than north.

This was the interesting part of the exercise: that the chromosomes evolved. In my little model, they did so in different ways. One mechanism was crossover, in which two chromosomes exchanged parts of themselves, spreading their individual traits around. Another was mutation: a random change in a chromosome. Think of this as the effect of a sudden disease, or of introducing a totally new individual into a population.

A third mechanism was reproduction, in which two chromosomes joined to produce a new one. Preferred here were the fitter chromosomes: both for reproduction itself as well as for passing on traits. With the food chromosomes, this meant that it was chromosomes that showed a preference for some direction -- because the robot had found food in that direction -- that were generally chosen to reproduce. They also passed on that directional preference to their offspring, reinforcing the robot's
preference for that direction.

So you see, I was consciously choosing the better chromosomes and propagating their traits. Call it eugenics if you like, call it fascism. After all, she was my robot, on my computer.

Now trees and food were all over the screen. But some areas had more food, others had more trees. I set "@" down in the middle of this bleak landscape, blind. She started by picking a random direction. If it led to a tree, her chromosomes made it slightly less likely she would choose that direction again. If she found food instead, she would tend to favour that direction a bit more. Every two or three steps, all the chromosomes evolved using one or more of the mechanisms above. Also every two or three steps, she would stop and choose a direction again.

So did it work? Not at first. But after a long time, after much tweaking and experimenting, I found my jaunty little robot becoming noticeably better at avoiding trees and finding food.

You might say, she showed some intelligence in her movements.

So I switched off the computer and went off to get some real ras-malai. There's only so much intelligence I'm prepared to take from symbols on my screen.

6 comments:

kuffir said...

what else have you been consuming, apart from ras-malai ?

Anonymous said...

I do not like Genetic Algorithms. They give you no insight into the problem, and no one knows why they work when you tune the parameters.

Dilip D'Souza said...

kuffir, actually the ras-malai I refer to was from about 18 years ago, when I did this little robot experiment. So it's pretty rotten by now.

Vishnu, I wasn't looking for insights into the problem. I was just trying to see if I could write this programme from scratch and tune it to do interesting things -- well, I was looking for insights into what kind of tuning produced what kinds of results. Sort of like how fractals turn out so differently depending on the values you give the parameters. It was an interesting exercise in programming, really.

Anonymous said...

Interestingly Genetic Algorithms are now being used in the underlying technology of Supply Chain Management applications such as scheduling etc...

The Tobacconist said...

@Vishnu:

Genetic Algorithms are meant to minimize certain objective functions that you determine after observing the problem. So I am guessing you already have the insight necessary. The good thing about them is they are less likely to get stuck in local minima and more often than nought they end up providing a pretty nice solution where none existed.

In other words, start liking 'em. :)

@Dilip:
Never knew you had an interest in Genetic Algos. What did you end up doing after Pilani?

Dilip D'Souza said...

Nikhil, I'd be interested in finding out more about how GAs are applied in supply chain management. Any pointers?

Sanketh, at Pilani I did EEE (which you non-BITSians might justifiably think refers to my grades, but no); then I did CS. This dabbling in GAs happened when I worked at a place where I was supposedly doing research -- what it meant was, I had the time and inclination to experiment like with this little project. Delightful experience. There are few things as fascinating as programming just for the sake of programming, and best of all in Lisp.