Before I launch into today’s rendition of “How I Spent A Week Doing Something Essential To My Research That Someone In Industry Could Have Done In 5 Minutes”, I wanted to remark on how, lately, this post has been seeing a lot of traffic. It was interesting re-reading it and all the comments that followed. It was also evident that mcoville and I were talking past one another. Though my views have not changed, my desire to enter into such “discussions” most certainly has
Particle Swarm Optimization
Does anyone know anything about mathematical optimization? Sparing folks from gory details, it’s basically the super-complicated analog to “use calculus to find the maximum value of f(x)“. Remember that from high school / college? Given a function, you needed to take its derivative, set it equal to 0, and solve for x, which should give you either the maximum or minimum of the function.
Optimization is like that. Except instead of f(x), we have something like f(x,y,z…,a,b,c,d,e,f,g,h) and we can’t actually take its derivative. Oh, and we usually don’t even have an explicit equation for f. But we still want to know: what is the largest or smallest value (or set of values) that it takes? One such method to arrive at a close answer is particle swarm optimization (PSO).
Let me just say: every time I hear about PSO, I immediately think ZERG SWARM. And to be perfectly frank, it’s kind of like that, so I’m just going to run with that analogy.
As I’m a TA this semester, and my fellow TA was busy writing a paper and studying for an exam, I was in charge of running the lab this past Friday. And the lab was on PSO. Which was curious because I’d never once used or even studied PSO before.
I set out to figure out how the f PSO even worked. Turns out, it’s not all that complicated (one of the advantages of using PSO over other optimization methods): you have a bunch of particles (zerg) that “swarm” over your search space. Obviously the more particles/zerg you use, the better your results will be, but the more intensive your calculations become. The particles/zerg have a certain degree of randomness: they will converge upon areas of the space that are “better” (analogy: we found a protoss expansion!) but still allow for some random movement in case there’s an even “better” area just around the corner (analogy: holy crap, the protoss’ main base!)
In fact, PSO draws its ultimate inspiration from watching flocks of birds. Check this out:
That’s pretty much PSO in action. The nitty-gritty is that you have particles with position, velocity, and a certain amount of independence (“drunkenness”, I call it) and social cognition (“sheepness”, I call it), all of which work together to determine where a single particle will move to reveal properties of the area it’s searching. If you do it right, PSO can reveal the maximum/minimum you’re looking for in a fraction of the time it would take to do an exhaustive search.
If you’re at all interested, I posted the Python module I wrote for the occasion on github. “lab5.py” is the one you’ll have to fill in; “answer.py” contains the completed assignment. The PDF instructions tell you everything you’ll need to know. NOTE: You will need NumPy and Matplotlib installed in order to run this example.
Needless to say, I learned a lot about PSO, and optimization in general. Like how PSO really isn’t ideal for revealing mystery images, but it sure makes for a fun, gimmicky introduction to the overall idea.
I know this seems like a jarring segue, but the PSO implementation inspired me to do a little exercise in HTML5 canvas work to prime myself for the real HTML5 canvas work I needed to do for my research: figure out how to add, remove, and resize semi-transparent boxes on an actively-playing video in the browser, and then save the coordinates of these boxes in a database.
So, I created a particle simulation in which each particle has a certain gravitational attraction to all the other particles in the simulation. Seems straightforward enough, right? Eventually you should get a little ball of swarming particles, right?
Well, that was the initial implementation. But I wanted to spice things up a bit: wouldn’t it be cool, thought I, if there was some critical mass threshold at which the particles would suddenly explode outward? Sort of like what happens just before and during a supernova: matter is compressed and compressed and compressed, and eventually the repulsive forces overwhelm the gravitational ones, and everything goes KABOOM!
Turns out, this was pretty tricky to code up. It was particularly tricky to code up efficiently. The original task of simulating n particles requires O(n2) computations, as you need to compute the pairwise distance between particles to determine how the gravity from each particle affects the trajectories of all the others. Through a lot of thinking and whiteboard-ing, I settled on a simulation that was O(n2 + n).
Here is the code I posted in my github repository. Feel free to check it out, fork it, tweak it, maybe make it a bit more efficient, though I don’t think you can optimize it much further than that. Also, if you don’t really care about the code and just want to see the simulation in action, I created a public Dropbox link for that: it’s rather mesmerizing. I do eventually want to put in HTML buttons and switches so you can actively modulate things like number of particles, gravitational attraction, and the “critical” quantities required for an explosion to happen.
I also wanted to add some seizure-inducing features like having each individual particle flicker its color randomly and independently from all the other particles, but I figure I’ll wait on that one for the moment.
Which leads me, inexorably, to my research: trying to get an HTML5 canvas into Drupal. While this has, to a very limited extent, already been done before, my canvas requires quite a bit more functionality. I need to be able to play a video in a web browser, and as the video is playing, allow users to draw boxes around regions of interest in the video, effectively annotating the videos so I know which regions to pay attention to when I analyze the video as part of my research.
So anyway. As of today, I have the proof-of-concept up and running in a standalone script, which you can check out on github. The next step–which, arguably, may be even harder–is to convert that proof of concept into a viable Drupal module. Not exactly sure how that’s going to pan out yet.
Return of the Intrepid Traveler
All this is kind of in a rush to be completed by the end of this week, when I depart for eight long days to the country of Morocco! Yes folks, I am going to visit my sister for the entirety of spring break. I’ll be off the grid in the purest sense; I’m hoping to maintain occasional contact with the outside world but only in response to the most pressing matters…mainly that of maintaining contact with The Lady I’m looking at which passwords I can reset for my temporary overseas stay, and then reset again upon my return home. I would also like to maintain one ready SSH server for a SOCKS-proxy hookup as a way to maintain some semblance of privacy. But I’ll need to make sure that server doesn’t have anything sensitive on it. What an ordeal!
But yes, this is likely my final update here before I land on my fourth continent. I hope everyone has a lovely next few weeks, and a very happy St Patrick’s Day!