The other day I was working on a crossover function to be used by a genetic algorithm.
The idea is that you select two individuals in your population of possible solutions
as parents (or more - bits aren't predisposed to monogamy or
bisexual reproduction) with the idea
that you'll combine their "DNA" in hopes of producing a more fit individual.
The idea of the
crossover for my case was a single point, and it goes somewhat like this
(a slightly simplified version, for the sake of discussion):
- The parents look like this:
"-X--XX-X--X", where X is some character besides "-"
Left_side_of_child = select a random number of characters from the left side of one of the parents
Count the number of non-dashes in Left_side_of_child - that is the number of characters you need to
skip on the other parent.
Figure out where to start on the other parent. If that index is a dash, you can randomly select
any adjacent dash until you reach any other character.
Get the right side of the second parent and append it to the left_side_of_child to give birth to
your new baby string.
So the idea is that the X's in each parent are meaningful and they need to remain the same in number
and relative position to each other - but dashes
can be inserted between them.
It's not the most complicated algorithm in the world, so why did I spend several hours getting it to work?
Most of the time, I try to write (literally) just a couple of lines of code before testing it to ensure
what I just wrote is doing what I expected it to do.
If you write too many lines of code before exercising it, when you notice a problem you'll
have a harder time diagnosing which line caused it than if you had frequent feedback. Just check
that the variables have
the values you are expecting at each point in the algorithm as often as possible.
Lesson: Don't forget to take baby steps.
Like many programmers, I sometimes have this insane fear of throwing away code - even if it's crapcode.
The function that seemed so simple to begin with had ballooned to over 40 lines, and included
several attempts at fixing the data instead of fixing the logic. Magic numbers were sprinkled like
pixie dust throughout the algorithm. Each patch brought further complexity, making it harder and harder
to find the problem.
I kept telling myself, "This is retarded. Why is this seemingly simple function causing you so much
pain? Just throw it out and start over." I simply waited too long to do that. Eventually I came to
my senses, started from scratch, and rewrote it to be 15 lines in about 10 minutes.
Don't be afraid
to throw out your dirty diapers.
It's good to relearn these lessons from time to time. I expect I won't be forgetting these two now for quite
Hey! Why don't you make your life easier and subscribe to the full post
or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate
wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!
Leave a comment
There are no comments for this entry yet.
Leave a comment