We Can Rebuild It, Better Than Before
If you remember, way back in the planning stages we split our program into a two-stage process:
- Design a 2D swarm intelligence that can optimize functions with two inputs
- Upgrade the 2D swarm to handle functions with any number of inputs, not just 2
We have already finished goal number 1 and solved most of the logic and math problems involved in running a swarm intelligence. Now all we need to do is modify our existing solutions so that their logic can handle more than two numbers at once.
Obviously this is going to require several changes, some big and some small. For instance, since we are no longer guaranteed to always be working with 2D swarms we are going to need to create a way to tell the swam how many dimensions to work with. We are also going to need to make our data structures more flexible. Just storing X and Y data won’t be enough if we’re trying to optimize a 5 dimensional equation.
So let’s start solving these problems!
Which Dimension Are We In?
It makes sense that one of the first steps in optimizing a problem is to identify how many variables you’re working with. The swarm needs to know how many dimensions to search, what kind of particles to build (2D? 3D? 11D?) and how many boundaries to expect. The whole program will crash if you try to feed a five variable equation into a swarm that is only generating four variable solutions.
The easiest way to let the swarm know how many variables it needs is to just tell it by passing some sort of dimension variable. Something like this:
(defun swarm-minimize (fn dimension boundaries) ; swarm code will go here)
Which we could then call like this:
; Minimizing a 3 variable equation
(swarm-minimize #’some-function 3 ‘((-5 5) (-10 3) (0 6)))
;Minimizing a 5 variable equation
(swarm-minimize #’another-function 5 ‘((-2 0) (3 6) (-3 3) (-5 -4) (0 100)))
Now if you look at those function calls you might have noticed that the dimension number always matches up to the number of pairs in the boundaries list. If you have three variables then you need to know what the min and max possible values for all three variables is. If you have five variables then you need five boundaries. And so on.
But if the dimension of the problem is always equal to the length of the boundary list… do we really need to keep track of dimension separately? Probably not. In fact, as I was working on this problem I found that I almost never needed the dimension of the problem as a number. It was much easier and faster to just loop over the boundary list, run some code for every pair in the list and then finish up when I had used them all once.
So the best way to keep track of the dimension of the problem is by making sure the boundary list is accurate. After that everything else falls into place. If we ever find out we really do need dimension as a number we can just retrieve the length of the boundary list. So our actual function definition will look something like this:
(defun swarm-minimize (fn boundaries) ; swarm code will go here)
; Minimizing a 3 variable equation
(swarm-minimize #’some-function ‘((-5 5) (-10 3) (0 6)))
;Minimizing a 5 variable equation
(swarm-minimize #’another-function ‘((-2 0) (3 6) (-3 3) (-5 -4) (0 100)))
More Than One Way To Skin An N-Dimensional Cat*
We just solved the issue of how to keep track of how many dimensions the swarm is working in. Next up is figuring out how to help the particles keep track of their locations/guesses in dimensions other than two. After all, if we are trying to optimize a function that requires five inputs then every guess is going to be made up of five numbers, represented as a single five dimensional particle.
In our two-dimensional swarm every particle object had specific data slots for its x position, y position, x velocity and y velocity. This worked really well because we knew we would always have exactly that much data. But now that we are trying to build a general swarm we’re going to need a much more flexible data structure, something that can hold a list with as many or as few coordinates as we need.
When I hear “list of coordinates” two data structures come to mind. The first one is, obviously, the list. The second one is the array. Both can be made whatever size we want and are perfect for holding the random numbers that make up a particle coordinate.
If we are working with a five dimensional swarm we need either a five item list or a five slot array. If we are working with a ten dimensional swarm we would need either a ten item list or a ten slot array. Here’s an example:
; The five dimensional point < 1, 2, -5, 2, 4 > as both a list and an array
(list 1 2 -5 2 4)
(make-array 5 :initial-contents ‘(1 2 -5 2 4))
So which one should we use? To be honest, I struggled with this decision. Both arrays and lists have strengths and weaknesses. Lists are very flexible and allow for interesting nested data structures, but arrays are much more efficient when it comes to reading random data out of the middle of a collection.
Of course, for something as simple as a coordinate or velocity we don’t really need fancy nested data structures, so clearly we don’t need lists and should go with the array so we can get the benefit of efficient random reads.
But wait! Do we actually need to random access to our data? Are there going to be any situations where we have a 100 dimensional particle and want to grab just the 63rd portion of its coordinate? It turns out the answer is no. In our swarm intelligence we always want to work with entire lists. For instance, when we update the position of a particle we update the entire coordinate list by referencing the entire velocity list.
So we will never say “Give me just the 32nd coordinate of this particle”. We will always say, in order, “Give me the first coordinate and first velocity of this particle. Now give me the second coordinate and second velocity. Now give me the third coordinate and third velocity…”
So which data structure is more efficient for reading an entire set of numbers all in a row: Lists of arrays? Honestly, there isn’t much difference. Just choose whatever is most convenient for you.
I’m going with lists.
Upgrading Particles – No Vespene Gas Required!
With those two major design decisions nailed down we have everything we need in order to build a generic handles-as-many-variables-as-you-need swarm particle. I wrote all of the following code by starting with a copy of our 2D swarm functions, removing the 2D from the name and then changing the code as needed.
First up is our new super-powered generic swarm particle, able to leap large dimensions in a single bound!
(defclass particle ()
((coordinates
:initarg :coordinates
:accessor coordinates)
(velocity
:initarg :velocity
:accessor velocity)
(history
:accessor history
:initform () )))
The jump to N-Dimensions has actually made the particle class simpler. Instead of having seperate data slots for x position, y position, x velocity and y velocity we just have two data slots, coordinates and velocity. These slots will eventually hold lists of data. For example, in a particle trying to solve a 4D equation coordinates might equal (1 2 2 5) and velocity might equal (-2 4 7 3).
Moving on, now that we have a new particle class we need a new function to help build particles. This is probably the most complicated code we’re writing today so put on your thinking cap and take a good look at it. If it just doesn’t click you might want to scroll down to the next section and see the example of how this function gets called.
(defun generate-particle (boundaries)
(let ((coordinates (list))
(velocity (list)))
(loop for boundary in boundaries
do (let* ((lower-bound (first boundary))
(upper-bound (second boundary))
(range (- upper-bound lower-bound)))
(push (ranged-random lower-bound upper-bound) coordinates)
(push (ranged-random (- range) range) velocity)))
(make-instance 'particle
:coordinates (reverse coordinates)
:velocity (reverse velocity))))
This might look completely different from good old generate-particle-2d, but if you look a little closer it actually does the exact same thing.
If you go back to generate-particle-2d (look here if you don’t have the code handy) you’ll notice that we’re using a pretty basic pattern:
- Get the X boundaries for the particle (from the function arguments)
- Calculate the range of possible X values using the X boundaries
- Use the X boundaries to generate a starting X position
- Use the range of possible X values to generate a starting X velocity.
- Do the same thing for Y
So the algorithm is clear. Find out the boundaries and range for one of our problem dimensions. Use that information to generate random starting positions and starting velocities. Repeat the process for every other variable in the problem.
That’s what the loop in our new function is doing. It goes through every boundary pair in the boundaries list and then uses those boundaries to generate a random starting location and starting velocity. So if we are trying to optimize a five variable function our loop will run five times and we’ll end up with coordinate and velocity lists with five starting numbers, just like we want.
A few Lisp tricks to look out for:
let* is just let but with the added bonus that you can define variables by referring to other variables from inside the same let, which you normally can’t do. To see what I mean try running these two functions and see what happens (spoiler, the normal let crashes):
(let ((x 1) (y (+ x 1))) (print y))
(let* ((x 1) (y (+ x 1))) (print y))
Also, up until now we’ve mostly just hard coded entire lists into our code. We haven’t had to build many on the spot. But now that we need to we can rely on push, which adds a new value to the beginning of an existing list through calls like (push new-value list).
Unfortunately, pushing values to the front of a list gives us the exact opposite order from what we wanted, which is why I call reverse before inserting the coordinate and velocity list into the new particle. All this reversing isn’t super efficient, but since we only do it once per particle it’s not a big deal.
Always Check Your Work
We can now build particles in as many dimensions as we want, but without an easy way to look at those functions its hard to tell how well our new particles work. So let’s finish up today with a new print-particle function to help us see what’s going on inside our particles:
(defun print-particle (particle)
(format t "coordinates: < ~{~a ~}>~%" (coordinates particle))
(format t "velocity: < ~{~a ~}>~%" (velocity particle)))
This deceptively short function actually packs quite a punch thanks to the fact that format has its own internal programming language that lets us do ridiculously complicated things like loop through a list to build complex strings.
The key to this bit of output magic is the ~{ ~} symbol. You use this special syntax by putting formating rules inside of the brackets and then passing the brackets a list. The bracket will then repeat it’s internal formatting rules as many times as is necessary to use up the entire list.
In this case the brackets are surrounding ~a, the classic “print one symbol” keyword. If we give the brackets a list with five numbers it will repeat the ~a five times and print them all. If we give the brackets a list of ten numbers it will repeat the ~a ten times and print them all.
Wrap this up with a couple angel brackets (< >) and a newline symbol (~%) and we have a pretty good looking geometric point, as you can see here:
[2]> (print-particle (generate-particle ‘((0 10) (0 10) (0 10))))
coordinates: < 3.952018 1.9228482 5.205475 >
velocity: < 4.249467 -0.7016258 1.7657127 >
NIL
[3]> (print-particle (generate-particle ‘((0 10) (0 10) (0 10))))
coordinates: < 5.9381933 5.0129404 9.165462 >
velocity: < -9.870724 9.138313 0.05269909 >
NIL
[4]> (print-particle (generate-particle ‘((-1 1) (-10 -5) (5 10) (0.1 0.3))) )
coordinates: < 0.82865 -7.275191 6.707388 0.2633261 >
velocity: < 1.720598 3.7108212 -2.178558 -0.03630188 >
NIL
Take a look at that, two nice 3D particles and a single 4D particle. Looks like our flexible particle system is up and running.
Sadly, our higher dimensional particles don’t actually do anything yet. We’ll save that for next time, when we update our swarm algorithms to start using the higher dimensional particles to optimize higher dimensional functions.
* Technically all cats are N-Dimensional, where N is usually 3.