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!