The End Is Near
Last time we successfully upgraded our particle objects to be flexible enough to work in any number of dimensions so they can help us optimize problems with any number of variables. Now all we need to do is upgrade our old 2D swarm algorithms to use these new super-particles and we’ll have a complete, generalized particle swarm optimizer.
Fair warning: A lot of the code in this post looks really complicated. And I guess it kind of is. But remember that everything we are doing in this post is something we’ve already done successfully in two dimensions and that the basic logic is the same. Just remember the basics of swarm logic (make a lot of guesses, update your guesses, repeat) and you should be fine.
Also, we can’t really develop a general swarm optimizer without a few multi-variable problems to test it on. So behold, Multi-dimensional parabolas!
(defun triple-parabola (x y z) (+ (* x x) (* y y) (* z z))) (defun quadruple-parabola (x y z w) (+ (* x x) (* y y) (* z z) (* w w))
Once again the obvious minimum for both these problems is when all the inputs are set to 0. That’s (0, 0, 0) for the triple parabola and (0, 0, 0, 0) for the quadruple parabola. Hopefully the swarm will be able to figure that out too.
A More General Swarm Definition
The first step in upgrading our particles was to remove specific references to 2D ideas like X and Y and then replace them with flexible lists that can grow to whatever size the problem demands. Similarly the first step in upgrading the swarm itself is to remove specific 2D references and replace them with more flexible structures.
The big change here is that our 2D swarm used to keep track of the best X and Y coordinates any particle had found so far. We will now replace those with one “best-coordinates” variable that we will use to store a copy of the entire coordinates list of any particle that manages to find a good possible answer. This way we can have one variable that works no matter how long the coordinate list gets.
(defclass swarm ()
((best-coordinates
:accessor best-coordinates
:initform nil)
(best-answer
:initarg :best-answer
:accessor best-answer
:initform most-positive-long-float)
(particle-list
:accessor particle-list)))
Next up is creating a handy swarm generating function. Just like with the particle generator function the main focus of this upgrade will be to remove specific references to X and Y limits and replace them with a flexible “boundaries” list that will include a min and max pair for every variable in the problem we are minimizing.
(defun generate-swarm (particle-count boundaries)
(let ((new-swarm (make-instance 'swarm)))
(setf (particle-list new-swarm)
(loop for i from 1 to particle-count
collect (generate-particle boundaries)))
new-swarm))
Most of the hard “boundaries” work was already done inside of generate-particle so this upgrade was as easy as swapping out a few old variables for a new one and making sure that “new-swarm” is created as a swarm object instead of a swarm-2d object.
Same Logic, More Numbers
Upgrading the swam logic is pretty easy. We just replace the idea of x-limit and y-limits with a single boundary variable and then switch to the non-2D version of every function call.
(defun swarm-minimize (fn boundaries)
"A general particle swarm optimizer"
(let ((swarm (generate-swarm *swarm-size* boundaries)))
(loop for i from 1 to *swarm-iterations* do
(loop for particle in (particle-list swarm)
do (update-swarm-particle particle swarm fn boundaries)))
(list (best-coordinates swarm) (get-swarm-history swarm))))
Only problem is… not all of these functions exist yet. So before swarm-minimize can actually be used for anything we’re going to have to write our new generic update-swarm-particle. Watch out because this one is a doozy!
(defun update-swarm-particle (particle swarm fn boundaries)
(update-particle-history particle)
(let ((particle-answer (apply fn (coordinates particle))))
(when (< particle-answer (best-answer swarm))
(setf (best-answer swarm) particle-answer)
(setf (best-coordinates swarm) (coordinates particle))))
(update-particle-velocity particle (best-coordinates swarm))
(setf
(coordinates particle)
(loop
for position in (coordinates particle)
for velocity in (velocity particle)
for bounds in boundaries
collect (max (first bounds) (min (second bounds) (+ position velocity))))))
Let’s start with the easy changes. We switch from update-particle-history-2d and update-particle-velocity-2d to the more general versions that we’re about to write. We also switch from funcall to apply for generating the answer associated with a particular particle position. apply is basically a funcall that expects it’s input in a list instead of typed out as individually which works really great now that our input is all in a list.
Then comes the hard part: updating particle positions. We used to just manually update X and Y position based of of X and Y velocity and X and Y limits, but we need more flexibility than that now that our coordinates, velocity and limits are all stored in lists instead of predictable variables.
Once again we’re going to turn to the mighty loop macro to solve this list based problem. Our goal is to process an entire list of coordinates using an entire list of velocities and in order to do that we’re going to take advantage of a handy loop trick that lets us iterate over multiple collections at the same time. You just include more than one “for variable in collection” inside the start of your loop and then every time you go through the loop you get one item from every collection. The first time through the loop you get the first item from every collection, the second time you get the second item from every collection and so on.
This is great because in order to update a particle we need to be able to update the first coordinate by using the first part of velocity and then making sure the result is inside of the first boundaries. Then we need to update the second coordinate with the second part of velocity and the second set of boundaries. So on with the third and fourth and however many dimensions we have. It’s the perfect place for the multiple-collection-loop trick.
Anyways, the end result of all our looping is to calculate a set of new coordinates, collect them into a big list and then replace the old particle coordinate list with the updated one.
Of course, the above function won’t work without an update update-particle-velocity, so let’s tackle that next. Its upgrade requires the same sort of loop tricks so if you understood the last function this one will be even easier. If you didn’t understand the last function, carefully read through it again.
(defparameter *original-velocity-weight* 0.8)
(defparameter *target-velocity-weight* 0.3)
(defun update-particle-velocity (particle target-coordinates)
(setf
(velocity particle)
(loop
for original-velocity in (velocity particle)
for position in (coordinates particle)
for target in target-coordinates
collect (let ((target-velocity (- target position)))
(+ (* *target-velocity-weight* target-velocity)
(* *original-velocity-weight* original-velocity))))))
Let’s remember back to how the 2D version of this function worked. For both X and Y we compared where the particle currently was to where the swarm’s best answer so far was and used this to calculate a target-velocity that would lead the particle to the best answer. We then took some fraction of this target seeking velocity and added it to some fraction of the particle’s original velocity. This meant that over time particles would eventually gravitate towards the swarm best.
The generic version uses a loop to do the same thing. It grabs one component of its current velocity, one component of its current position and one component of the target swarm-best coordinate. It then calculates a target-velocity for just that one portion of the velocity, mixes it in with the current velocity and collects the whole thing into the new velocity list that we eventually set as the particles new velocity. In other words, if we were solving a 3D three variable problem the first trip through the loop would use X position, X velocity and X best-coordinates to calculate a new X velocity. Then the second loop would update the Y velocity and the third loop would update the Z velocity.
With that tricky function out of the way all that’s left are a couple useful history related helper functions:
(defun update-particle-history (particle)
(setf
(history particle)
(append
(history particle)
(list (coordinates particle)))))
(defun get-swarm-history (swarm)
(loop for particle in (particle-list swarm)
collect (history particle)))
The first is basically identical to the 2D versions. The second one IS identicle to the 2D version, but I’m defining it anyways because every other function has a 2D vs generic version and I’d hate for it to feel left out.
Testing The Swarm
That was a lot of fairly complicated code. Now it’s time to see if all our hard work paid off and the new code works just as well as the old.
[94]> (defparameter *swarm-iterations* 75)
*SWARM-ITERATIONS*
[95]> (defparameter *swarm-output* (swarm-minimize #’triple-parabola ‘((-10 10) (-10 10) (-10 10))))
*SWARM-OUTPUT*
[96]> (first *swarm-output*)
(-0.0012116772 -0.009321406 -0.013946425)
[97]> (defparameter *swarm-output* (swarm-minimize #’quadruple-parabola ‘((-10 10) (-10 10) (-10 10)(-10 10))) )
*SWARM-OUTPUT*
[98]> (first *swarm-output*)
(-0.067994416 -0.08707443 -0.026546227 0.037088722)
Success! Our swarm is within a rounding error of the true minimum on both the triple and quadruple parabola.
Didn’t You Forget Something?
Exceptionally observant readers might have noticed that there are two 2D functions that don’t have a general version yet: swarm-maximize and swarm-target. But this post is already getting pretty long so I’ll tackle that problem next time. See you then!