Marlin’s Gottahack
– 1998 Oct 05 – PREV HOME NEXT
Junkies
-------
For all of you
gottahackers who were looking forward to your monday night fix, I have no
apology for being half a day late. Read the license agreement. These things
come out when I get around to it.
I read a book this
last week, Goa Freaks: My Hippie Years in India. I thought it was going to be
about india. Surprise, it was about snorting cocaine, smoking heroin, and the
hassels of smuggling kilos of the stuff in past US customs so that you can get
enough money to go back to india to support your 2 gram a day habit.
The book was
interesting because it presents such an alien world with alien thought
processes. For example, at one point the author's boyfriend who disapproves of
her addiction to heroin steals her 1 pound stash of heroin and dumps it in the
ocean. She is pissed off by this and decides to have the guy killed so she goes
to one of the local gangsters and pay him to kill her boyfriend, or seriously
cripple him. All this related without the least sense of remorse, without the
least sense of proportion. Tres wierd!
By the way, the
gangster just took her money and did nothing, figuring that she was just a
pissed off junkie and she'd chill out in a few days. He never did give her her
money back.
Well, enough chit
chat, on with the show.
GA lite - A modest
space and runtime improvement for GAs
--------------------------------------------------------
As I am sure you
all know, Genetic Algorithms are a search technique. What you are searching for
is the x (number or vector of numbers) that optimizes (min or max) some
function F(x). The search technique basically involves generating new x values
mostly at random based on previous x values that had good evaluations of the
function. if you consider the x value as just one long bit stream, you breed a
new value from a pair of old values by using crossover (copy from one parent
for a while then randomly switch to copying from the other parent for a while)
and mutation (randomly flip a few of the bits during copy)
Some day I'll go
into a long diatribe about how genetic algorithms have been oversold (the new
magical cure all, the only search method you'll ever need, works great because
it is the same procees that discovered you! Gak!), but then again maybe I won't
cause life's too short to spend whining about ignorant advertising. The fact is
that for a large class of problems GAs are the way to go and they are basically
very simple to implement.
While hacking on
the Counterpoint GA I came up with this simple trick that takes half of the
space that the tradational algorithm takes and typically runs a little faster
as well. The really surprising thing is that this little hack actually takes
less code than the traditional algorithm. Proof positive that you shouldn't let
biologists design computer algorithms! What could be better - Great taste AND
less filling!
The traditional
description of a Genetic Algorithm goes something like this:
Allocate one array
to hold a population of 2N individuals
(Consider the array
as two buffers, top half and bot half)
Start with the top half
filled with N random individuals, and evaluate them.
LOOP forever doing
the following
Breed the
individuals in the top half filling the bot half.
Run the evaluation
function for each individual in bot half.
Sort the entire
array using the value of the evaluation function
(This moves desired
individuals into the top half)
Throw out
individuals in the bot half
ENDLOOP
The following
simple modification using a HEAP data structure will cut the space requirements
in half, and while it has the same theoretical run time, in practice it is
faster and will never be slower. First the pseudo code explaining it for those
that know what heaps are. Then the description for why it is faster. Lastly a
description of what a heap is for those not familiar with this very useful data
structure.
Allocate one array
to hold a population of N individuals
Heap Order the
array leaving the worst individual at the top (the desireable dudes are in the
leaves of the heap)
LOOP forever doing
the following
Breed two random
individuals in the array to create a single Newcomer
Run the evaluation
function on the Newcomer.
IF the Newcomer is
Superior to the worst old timer (top of the heap)
Replace the old
timer with the Newcomer
Ripple the Newcomer
down to preserve the Heap property
ENDIF
ENDLOOP
What this method
does is change the process from a bulk process:
<Breed an entire
generation, Sort them, & Kill off half of them>
into a continuous
process:
<Breed one new
guy and keep him if he is better than the worst>.
In both algorithms,
the total population that is being bred is N but you have reduced the array
from 2N down to N. The runtime cost for each new individual in the traditional
method is the cost to breed the individual plus the cost of running the
evaluation function plus log (N) (the cost of doing the sort is N log(N) and
you pay this once every time you breed N individuals, so it is a total cost of
log(N) assigned to each individual bred)
In the second
algorithm the runtime per individual bred is identical, cost of breeding plus
cost of evaluation function plus log(N) to ripple the individual into the heap.
However, this log(N) cost is shortcut every time the Newcomer was inferior and
in practice that happens a lot, particularly after the GA has mostly converged
on a solution and the heap is full of healthy specimens.
Thus this new
algorithm requires half the space of the traditional algorithm and runs faster
as well. As a side benefit, being a continuous process it has a shorter cycle
time through the main loop and it is easier to count how long it has been since
you have found a Newcomer that wasn't a dud.
In the counterpoint
algorithm I kept a counter going for every pass through the main loop. I would
reset the counter everytime some new individual made it into the heap. By watching
that counter slow down it was easy to determine when the whole search process
had mostly converged. It would be a little more work to do that for the
traditional algorithm.
How Heaps Work
--------------
For those unfamiliar
with Heaps, a Heap is an efficient structure that keeps a block of data halfway
sorted. What this means is that the maximum element is the first one in the
array. This makes finding the maximum element trivial. The structure on the
rest of the array makes it possible to quickly (in log(N) time) find the next
to maximum element. This second property allows one to remove the old maximum
element, insert a new element, and bring the maximum element in this new array
up to the top all in a single quick log(N) operation.
The mechanics of
the heap are this: Any element in the heap, H(i), is considered to have up to
two children being H(2*i) and H(2*i + 1). Thus H(1) has two children, H(2) and
H(3), Likewise H(2) has children H(4) and H(5) while H(3) has children H(6) and
H(7). When the index gets greater than N, then obviously there is no child at
that index. Notice that we have packed a binary tree of elements into an array
and the pointers are implicit in the math and so are the flags indicating when a
node is a leaf. Because of the special shape of a heap, we get to keep only the
data and have none of the "overhead" that would normally be required
to keep a binary tree.
The required
"Heap" property that makes the heap a halfway sorted and very useful
structure is in the ordering between a parent, H(i) and that parent's two
children H(2*i) and H(2*i + 1). The requirement is that an element in the heap
must be greater than or equal to his two children. Thus H(i) > H(2*i) and
H(i) > H(2*i+1). Since every element in the heap except for H(1), who is at
the top of the heap so to speak, has a parent and that parent is the greater
element, this propagates the greatest element in the entire heap up to position
1, H(1)
To preserve the
heap property when you throw out the old H(1) and put in a newcomer is quite
simple. If the newcomer is greater than or equal to both of his children, than
you are done. If not, find out which of the two children is larger and swap the
newcomer with that largest child (you don't want to promote the lesser of the
two children because then that lesser child has a child, his former sibling,
that is greater thus violating the heap property). Simply follow the newcomer
down, swapping him with his greatest child whenever he has a child that is
greater than him. Eventually (in at most log(N) steps) he comes to rest,
possibly at the bottom of the heap where he has no children.
The operation just
described of rippling an element down through the heap starting from position
H(1) has an analogous operation that works from the other end, rippling an
element up through the heap starting at position H(N). This operation is even
easier. H(N)'s parent is at H(N/2) (truncate non integers) for all elements
except H(1). Simply compare the Newcomer with his parent and swap him up
whenever the Newcomer is greater than his parent.
Ripple up is
necessary in order to build the heap in the first place. Put the first element
at H(1) and ripple him up (trivial because 1 has no parents). Put the next
element in H(2) and ripple him up. Continue this process until you have a heap
of N elements.
For more on heaps
read any decent textbook on algorithms. e.g. Sedgewick.
Math Puzzle #2
---------------
This is one that I
got from a microsoft puzzle alias. I don't think I will give anything away if I
mention that I used dynamic programming to solve the puzzle. I pass it on
because it will give me an excuse to get into dynamic programming in a future
gottahack news letter.
You have an endless
supply of Brozz eggs. These eggs are wonderful when perfectly cooked and
absolutely terrible raw or overcooked. The cooking is trivial, just put in
boiling water and cook for the correct number of minutes. They are extremely
sensitive to cooking time. One minute too long and it is overcooked. One minute
under is not enough. Unfortunately, there is no way from the outside for you to
determine if the egg is properly cooked the only way to know is to crack it
open and take a look and once you open it you can't put it back if it needs
more cooking. Fortunately, they all take exactly the same number of minutes for
proper cooking. Once you can find that number, you will be able to cook eggs
perfectly every single time.
Your mission, is to
find the correct cooking time for the eggs. You are to do this in the minimum
amount of time. All you know is that the time is somewhere between 1 minute and
60 minutes.
That is the whole
problem, however at the risk of offending those who object to hints, I will
point out that the correct answer is NOT binary search. It is very similar to
binary search but not exactly I.e. you do NOT first cook one egg for 30
minutes, break it open and see if it is undercooked or over cooked and then
press on. The problem is that you spent 30 minutes determineing which half it is
in and if it is in the lower half the cooking times are all less than 30
minutes and you will quickly find the correct answer, but if it is greater than
30 minutes, you must now spend at least half an hour on every new test of the
egg time. Your job is to minimize the TOTAL expected time including all the
time spent cooking those test eggs until you have the solution, the correct
cooking time.
Neural Net
Motocross
--------------------
To end this weeks
fair as randomly as I started I flashed on this idea this week. As you know,
one of the first major successes of Neural Nets was in broom balanceing. You
build a little platform that the computer can slide around with two degrees of
freedom. You build some kind of tilt sensor on the broom so that you can see
which was it is falling and you teach the thing to balance the broom.
Reportedly it works so well that you stand the broom on it and the broom does
not move. It makes little micro corrections so fast that it looks like the
broom has been bolted to the platform. Rumor has it that in order to make the
demo look better the folks that built it injected some randomness into the
controller so that you could see the broom wobble around a little bit while it
is doing its job.
One of my buddies
at the soft years ago used to describe all neural net research as broom
balancing research. e.g. he wanted to learn more about neural nets cause he had
a lot of brooms in his house that were just standing unused in the broom
closet.
Anyway the idea I
had was this. Driving a motorcycle, like balancing a broom, is really just
another 2 degrees of freedom problem. You can turn the handle bars and you can
rev the throttle (yeah, I know, what about the clutch, the breaks, the
gearshift. Just wire the throttle to the break so that you have a continuous
variable from positive to negative acceleration.) You have the same basic
sensor, the tilt meter on the bike. It should be a piece of cake to teach a NN
to drive a motorcycle in circles in a parking lot. If you throw in one more
sensor to indicate where you want the thing to go, I have no doubt that you
could get the thing to drive from place to place in a level parking lot.
Now balancing a
broom in the lab is one thing but imagine how much cooler it would look to go
strap your PC onto your hog with bungie cords, hook the little robot hand to
the serial port, clip it to the throttle and let her rip!
I figure since you
really do not want to have your PC out crashing your hog while it is trying to
figure out how to drive you would actually just hop on the bike yourself, drive
around and collect all the data on what driving looks like, figure 8's,
doughnuts, popping wheelies, etc and you let your PC watch and learn. As it
figures it out, you more and more let it steer. Once you come to a trust
situation (if you get that far!) you start giving it some challenges. You shift
your weight from side to side. You stand up on the seat and jump up and down
while it is driving. I mean, hey, it's your bike, it's your PC, it's your skin.
Go nuts!
Pretty soon you'll
be going to the next step. You'll be hooking it up to video cameras. You'll be
out driving it on rocky terrain and gravel. You'll be jumping ditches, hill
climbing, jumping cars lined up in Las Vegas! Soon you'll be entering motocross
events and just trying to hang on while your PC pounds around the course.
Why? You want to
know why? Simple. This is the first step to planetary exploration. Just think
of it. Next time we send some little remote video camera off to Mars to do some
exploration we should be sending a dirt bike. Just think, Harelys on the Moon,
choppers on Mars.
Enjoy!