Non-submission - Importance Sampling with Von Mises-Fisher distribution

[kevinjzhang]

Joint work with @seanyang0813, while we didn't finish the challenge in time, we just wanted to share what we did.

Try it out: https://importance-sampling.vercel.app/ Code: https://github.com/kevinjzhang/importance-sampling Video demo: https://www.youtube.com/watch?v=f7zIO8mCG2Y

We used a sampling-based approach to this optimization. We use importance sampling - the idea is to randomly sample, and select the best samples and refine the sampling distribution using this. This method converges quite fast so this is good to run multiple times. We used the Von Mises Fisher distribution, similar to a Gaussian distribution except for the surface of a sphere. I used code from the answer here to help sample from the distribution.

We optimize to get the maximum for the minimum distance between any 2 points so that no 2 dragon balls are close together.

To handle land vs. sea, we create a table of granularity 3 degrees latitude/longitude from which we can lookup if the point is land or sea. Existing APIs seem quite slow so we bucket it like this.

Apologies if code is a bit messy, I personally haven't used javascript much and didn't get time to clean up afterwards either.

[vjeux]

This is really cool, thanks for sharing! I had never heard of Von Mises Fisher distribution before.

Also, don’t worry about the code being messy. The whole point of those challenges is to get something one off, doesn’t need to be pretty.

[mhelvens]

We optimize to get the maximum for the minimum distance between any 2 points so that no 2 dragon balls are close together.

That's the cleverer way to interpret the instructions! I just naively optimized on the sum of all distances. And that means the final solution often has two or even three dragon balls on the south pole, for example.

I'm gonna try to switch to the same objective, and see what that looks like.

Edit: Yeah, the dragon ball distribution looks much nicer, but it's much harder to get them to stay out of the Pacific Ocean. 😅 I'll have to penalize water quite harshly, and hope that a random mutation teleports them onto land. Because I'm also working with a binary "land vs sea" dataset, and there's no slope to gradually lead them to land.

Edit 2: It helps to place your initial dragon ball on French Polynesia or something. 😜