Objective: World Domination… I Mean A Randomized Swarm
Last time we built some simple object classes for holding particle and swarm information. The next logical step is to build some code that can use those classes to create an actual swarm filled with dozens of particles complete with starting locations and starting velocities. But how should we decide what our starting data should look like? Where do we put the particles? How do we choose their speed?
Well, the easiest way is to just randomly scatter the initial particles around the entire problem space and then randomly assign them all a velocity. You might think it would be better to try and carefully calculate an optimal starting formation for our swarm, but remember that swarm intelligences are usually used to optimize really complex problems. If we understood our problem well enough to purposefully choose good starting particles we probably wouldn’t need to use a swarm optimizer in the first place!
Now that we’re all on the same page we can start thinking about what sort of data our code is going to need in order to generate that random swarm. For starters it will obviously need to know many particles to generate. We could hard code this to be the same for every swarm, but I think it’s useful to be able to build swarms of different sizes. Sometimes you want more particles because that means more searching power. But more particles also means that each step of the algorithm will take longer to complete, so sometimes you want fewer particles. Keeping it flexible let’s us experiment and fit our swarm size to the problem we’re solving.
After we choose how many particles we want we’re going to need to know what general area to put them in. If we’re only interested in values less than 1 it doesn’t make any sense to generate particles with coordinates in the thousands. So for a 2D swarm where every particle has an x and y coordinate we will need a minimum x limit, a maximum x limit, a minimum y limit and a maximum y limit.
From that we can prototype a couple function something like this:
(defun generate-swarm-2d (particle-count x-min x-max y-min y-max) ;Code goes here ) (defun generate-particle-2d (x-min x-max y-min y-max) ;Code goes here )
As an example let’s imagine that we are trying to optimize a two variable equation where the x value (or temperature or pressure or something) has to be between -5 and 5 while the y value (which could be acidity or MPG or something) needs to be between 0 and 20. Let’s also imagine that we decide we want fifty particles. And while we’re at it let’s also imagine we own an SRT Viper because that is one cool car. In this case our swarm generating function call would look like this:
(generate-swarm-2d 50 -5 5 0 20)
And every particle in that swarm would be built like this:
(generate-particle-2d -5 5 0 20)
A Better Random
If we want to build a random swarm it should be pretty obvious that we’re going to be doing a lot of “pick a random starting X value between -10 and 5” along with plenty of “pick a random starting Y velocity between -3.5 and 3.5”.
Unfortunately Lisp’s built in random function only returns values between 0 and whatever limit you give it. So it can give us a number between 0 and 10 but not a number between -5 and 10.
But working around this limit isn’t very hard at all. Here is one possible solution. Spend a little time looking over it to practice your Lisp parenthesis and function nesting.
(defun ranged-random (min max) (+ min (random (float (- max min)))))
See what I’m doing here? I start by figuring out how many numbers are in the range between our desired maximum and our minimum by using (- max min). Then I choose a random number between zero and that range and add it to the minimum. So if our min and our max are 5 and 15 I would end up choosing a random number between 0 and 10 and then adding that to 5, which I hope you can see will give us a random number between 5 and 15 just like we wanted.
Besides all the Lisp parenthesis the only trick here is the call to float. Lisp’s random returns numbers of the same type as it’s input, so if you give it an integer it will only return integers. (random 10) can give you 3, 5 or 7 but never 2.5. For that you would need (random 10.0). By calling float on our calculated range we make sure we can get fractional numbers even if our range turns out to be a neat integer.
This is important for our swarm because we don’t want our starting locations and starting velocities limited to whole numbers; we want the flexibility to put them anywhere within bounds and to give them any sort of speed.
Anyways, let’s give it a test run:
[2]> (ranged-random -5 10)
9.227012
[3]> (ranged-random -5 10)
-4.449574
Looks more or less random to me.
Randomized Starting Location
Now that we have a function for choosing a nice random fraction somewhere between any two numbers randomizing our swarms’s starting locations will be a breeze.
(defun generate-particle-2d (x-min x-max y-min y-max)
(let ((new-particle (make-instance 'particle-2d)))
(setf (slot-value new-particle 'x-coord) (ranged-random x-min x-max))
(setf (slot-value new-particle 'y-coord) (ranged-random y-min y-max))
;Velocity code goes here
new-particle))
Look at that let form! Remember, we use let to create local variables and the first argument is a list of two-item lists holding variable names and starting values. This means that a let with a single variable will end up with a weird looking double parenthesis around a single two-item list, but you’ll get used to it.
Generating Random Velocity
Scattering particles throughout solution space like sprinkles on a mathematical cake is only the first half of building our swarm. Every particle also needs a starting velocity.
But what should our starting velocities look like? If we make them too small the particles won’t explore very many different options before deciding to all clump around the nearest good answer, but if we make the velocities too big the particles might skip past good solutions.
Once again randomness comes to the rescue. Giving each particle a random starting velocity will (usually) give us a good mix of fast particles, slow particles and average particles which can sort of balance out each other’s strength and weaknesses. All we need to do now is decide what random range to choose those velocities from.
Logically the slowest a particle can be moving is to not be moving at all; zero velocity in both the x and y direction. So that gives us the lower limit for our starting velocities.
On the other hand, the absolute fastest a particle can be moving is limited by how big our search space is. If we’re looking for an answer somewhere between 0 and 10 then our top speed should only be 10, which is fast enough to jump from one problem boundary to the other. If a particle went any faster than that we’d just have to yank it back to the nearest border anyways, so we can use the width and height of our problem space to determine the upper limit for our starting velocities.
But don’t forget that velocity can be negative! So we don’t just want to look for a starting velocity between 0 and our max, we also want to look between negative max and 0. And if you put those two ranges together: -max to 0 plus 0 to max = -max to max. What we really want for velocity is a random number somewhere between the negative fastest speed we can be going and the positive fastest speed we can be going.
Here is that is in Lisp form:
(defun generate-particle-2d (x-min x-max y-min y-max) (let ((new-particle (make-instance 'particle-2d)) (x-range (- x-max x-min)) (y-range (- y-max y-min))) (setf (slot-value new-particle 'x-coord) (ranged-random x-min x-max)) (setf (slot-value new-particle 'y-coord) (ranged-random y-min y-max)) (setf (slot-value new-particle 'x-vel) (ranged-random (- x-range) x-range)) (setf (slot-value new-particle 'y-vel) (ranged-random (- y-range) y-range)) new-particle))
Nothing too strange here. We declare two new variables at the beginning of our let and use them to keep track of how wide and tall our problem space is. Then we use those ranges to create some random starting velocities. And then we finish off the function with a reference to the particle we just created to make sure the function returns it.
Testing Our Particle Generator
Now that we’ve written all that code let’s give it a whirl and make sure it works. Which I guarantee it will because if it doesn’t I’ll rewrite this post before publishing it.
[19]> (print-particle-2d (generate-particle-2d -5 10 20 30))
x:8.757052
y:29.571583
x-vel:-2.2574558
y-vel:-0.53238964
NIL
[20]> (print-particle-2d (generate-particle-2d -5 10 20 30))
x:1.1677175
y:23.49154
x-vel:-10.902741
y-vel:3.1261635
NIL
Yeah, looking good! All the staring positions and velocities are in the right range and after running it a few dozen times I saw a good mix of big and small velocities. Perfect!
Building The Swarm
Now that we can generate random particles building the swarm is as easy as choosing some dummy values for best-x, best-y and best-answer and then calling the particle function a bunch of times in a row, which is easy enough to do with the power of the loop macro.
(defun generate-swarm-2d (particle-count x-min x-max y-min y-max) (let ((new-swarm (make-instance 'swarm-2d))) (setf (slot-value new-swarm 'best-x) x-min) (setf (slot-value new-swarm 'best-y) y-min) (setf (slot-value new-swarm 'best-answer) most-positive-long-float) (setf (slot-value new-swarm 'particle-list) (loop for i from 1 to particle-count collect (generate-particle-2d x-min x-max y-min y-max))) new-swarm))
It doesn’t really matter what we choose for the starting value of best-x and best-y because we’re going to replace them with real data the first time the first particle reports back to the swarm. We guarantee this by setting the starting best-answer to a number so big that it might as well be infinity compared to the problems we hope to solve. Remember, our swarm optimizer is a minimizer so an unbelievably big, positive number like most-positive-long-float will be considered worse than just about any normal number our optimizer might try.
If for some reason you plan to regularly work with numbers larger than your systems most-positive-long-float it might be better to start of by setting the best-answer to null. Then your particle update logic can specifically check for that null value, recognize that means no-one has found a best answer yet and replace it.
But I really don’t want to write a special use case just for the first particle of the swarm. By making best-answer start out as a really really unoptimal big number I can always use the same numeric logic whether it’s my first particle or my last.
Other than that there’s nothing to see here but the mighty loop macro, which is almost self explanatory. “loop for i from 1 to particle-count” is just an easy way to tell the loop how many times to run. The “collect” keyword tells it to grab some data every time through the loop and put it all into one big list. In this case the data we are collecting is one new randomly generated particle for each trip through the loop. This big list of random particles is then returned from the loop and slotted into our swarm.
Are We Sure This Is Working?
We now theoretically can generate random swarms but without some way to examine those swarms it’s hard to tell if it really works. I guess we could use the command line to create a swarm, save it to a variable and dissect it… but that sounds tedious. Instead let’s build some code to print the swarm all at once with one easy function call:
(defun one-line-print-particle-2d (particle) (format t "pos:<~a, ~a> vel:<~a, ~a>~%" (slot-value particle 'x-coord) (slot-value particle 'y-coord) (slot-value particle 'x-vel) (slot-value particle 'y-vel)))
(defun print-swarm-2d (swarm) (format t "Best input:<~a, ~a>~%Best answer:~a~%" (slot-value swarm 'best-x) (slot-value swarm 'best-y) (slot-value swarm 'best-answer)) (loop for particle in (slot-value swarm 'particle-list) do (one-line-print-particle-2d particle)))
Once again I’m leave all the hard work up to the format and loop macros. By this point you’ve probably figured out that “~a” is a keyword for grabbing a value and sticking into our output while “~%” is the keyword for printing a newline.
So all we’re doing here is printing out a two-line summary of the swarm’s current best answer and then looping through our swarm’s particle list printing out a one-line summary of every particle. You can see it in action here on a randomly generated 3 particle swarm:
[26]> (print-swarm-2d (generate-swarm-2d 3 -10 10 -5 5))
Best input:<-10, -5>
Best answer:8.8080652584198167656L646456992
pos:<-5.8058715, -3.4688406> vel:<18.249115, 4.2487574>
pos:<-6.365567, 2.238144> vel:<19.292294, -2.82722>
pos:<1.3002377, -4.8587823> vel:<-14.21917, -4.408451>
NIL
Success! Three random particles and a ridiculously huge default “best answer”. How ridiculously huge? Well, it’s written in scientific notation. See that ‘L’ in the output? That means the number is a long float and the digits after that point are exponents. So this number is basically eight times ten to the sixty-four millionth power.
By comparison scientists believe that the number of atoms in the known universe only comes in at ten to the eight-second power, so I think it’s safe to say that no matter what kind of problem we are trying to minimize even the worst real answer will be smaller than our default.
Time For Spring Cleaning
We can build swarms now, which is certainly an important step. But the code for doing it is ugly and takes up way too much space. I can’t say I’m happy about that, so for my next post I’m going to show you some Lisp object shortcuts that will let us cut our code down to size and make it easy to read again.
Or at least, as easy to read as Lisp ever is. Getting used to parenthesis yet?