We’re Already Past The Hard Part

 

Like I’ve told you again and again a particle swarm optimizer is just a bunch of particles/numbers moving around and making guesses at how to optimize a problem until we feel like we’re reasonable close to the ‘true’ best answer to our problem.

 

Last time we wrote some code for moving one particle around, so now all we need is some code for moving lots of particles around. We can actually do this with just two loops: One big outer loop that keeps repeating until we have our final answer and a smaller inner loop that updates every particle in the swarm once for each step through the main loop.

 

With that in mind there are really only two questions left to answer: How big should our swarm be and how do we decide when we are done looking for better answers?

 

The simplest solution to both problems is to hard code some values. We will choose a specific number of particles for our swarm and we will also choose how many times we want the swarm to update those particles before deciding on a final answer.

 

This obviously isn’t the only, or best, way to do this. It might be smarter to decide when to stop by keeping track of how long it’s been since we’ve found a better answer. If we haven’t found on after a few dozen or hundred updates then we stop. This way we can leave it up to the swarm to decide when it is done and we don’t have to worry so much about accidentally cutting the swarm off while it’s still doing good work.

 

But that can get complicated. So for now let’s just stick with hard coding some values. Just pop them in some global variables so we can easily adjust them for each problem we try. We’ll keep our default values really small so it’s easy to debug:

 

(defparameter *swarm-size-2d* 5)
(defparameter *swarm-iterations* 5)

 

Now we just need to build a swarm of size *swarm-size* and loop through it *swarm-iterations* times. The update-swarm-particle-2d code from last post will do the rest of the work for us:

 

(defun swarm-minimize-2d (fn x-limits y-limits)
   "A particle swarm optimizer for two dimensional equations"
   (let ((swarm   (generate-swarm-2d *swarm-size*
                     (first x-limits) (second x-limits)
                     (first y-limits) (second y-limits))))
      (loop for i from 1 to *swarm-iterations* do
         (loop for particle in (particle-list swarm)
            do (update-swarm-particle-2d particle swarm fn x-limits y-limits)))
      (list (best-x swarm) (best-y swarm))))

 

Go Forth and Optimize, My Swarmy Minions!

 

That’s all our swarm needs in order to start solving problems, so let’s give it a spin. We’ll be feeding it our handy double-parabola test function and seeing how close it comes to the real answer. Remember that the true minimal optimum for a double parabola is (0, 0):

 

[34]> (swarm-minimize-2d #’double-parabola ‘(-10 10) ‘(-10 10))

(-2.5209198 3.1263676)

 

Ok… not so great. Kind of disappointing, actually.

 

But wait! We only had five particles making five guesses each. Of course they couldn’t find a good answer. Let’s give them a little more time to work and see if that improves anything:

 

[35]> (defparameter *swarm-iterations* 100)

*SWARM-ITERATIONS*

[36]> (swarm-minimize-2d #’double-parabola ‘(-10 10) ‘(-10 10))

(2.5831852E-5 -6.708622E-6)

 

Much much better! Almost perfect, in fact. We’re within a rounding error of (0,0). Our swarm intelligence has successfully done something intelligent! Congratulations, an AI programmer is you!

 

Record Keeping

 

Getting good answers is pretty cool, but back in the design phase we decided that we were also interested in seeing the path our particles took in order to find that answer. That’s why all of our particles have that “history” data slot. You remember, that one that we had to write that weird nested list append thing to keep updated.

 

Because every particle keeps track of its own history generating a swarm-wide history is as easy as running through the swarm’s particle list and gather up all the individual histories into one big list. Which is yet another problem that the loop macro can solve for us. Honestly I probably could have titled this series “Let’s Use The Loop Macro To Solve All Our Problems”.

 

Anyways, here’s a function for building a swarm history and here’s an updated swarm-optimizer that includes that history in it’s output:

 

(defun get-swarm-history-2d (swarm)
   (loop for particle in (particle-list swarm)
     collect (history particle)))

 

(defun swarm-minimize-2d (fn x-limits y-limits)
   "A particle swarm optimizer for two dimensional equations"
   (let ((swarm (generate-swarm-2d *swarm-size*
                   (first x-limits) (second x-limits)
                   (first y-limits) (second y-limits))))
      (loop for i from 1 to *swarm-iterations* do
         (loop for particle in (particle-list swarm)
            do (update-swarm-particle-2d particle swarm fn x-limits y-limits)))
      (list (list (best-x swarm) (best-y swarm)) (get-swarm-history-2d swarm))))

 

Now Let’s shrink our swarm size and our number of guesses back down and give the new code a test run.

 

[39]> (defparameter *swarm-size* 2)

*SWARM-SIZE*

[40]> (defparameter *swarm-iterations* 4)

*SWARM-ITERATIONS*

[41]> (swarm-minimize-2d #’double-parabola ‘(-10 10) ‘(-10 10))

((-0.11861801 -0.97045755)

(((8.618713 -8.651136) (10 -0.23300552) (10 6.501499) (8.640749 9.647516))

((-8.614849 -7.199463) (-0.11861801 -0.97045755) (6.678367 4.012747)

(10 6.5043488))))

 

That’s a lot of parenthesis to read through but I bet you can see what happened. The first pair of numbers drowning in those parenthesis is the best answer the swarm has found so far (which is pretty bad since we only ran the algorithm through four steps). After that you might be able to make out that the remaining pairs of numbers are split into two lists of four. Those are the histories of the paths our two particles took through their four step journey.

 

And with that our two dimensional particle swarm optimizer is done. It runs the algorithm, finds the answers and spits back all the data we wanted from it.

 

Complete 2D Particle Swarm Optimizer Code

 

Now that this part of our project is “done” I imagine you’ll be wanting another full code dump. I keep all the following code in a file called “swarm.lisp”:

 

;Helper Functions
(defun ranged-random (min max)
    (+ min (random (float (- max min)))))

;Particle Related Code
(defclass particle-2d ()
    ((x-coord
        :initarg :x-coord
        :accessor x-coord)
    (y-coord
        :initarg :y-coord
        :accessor y-coord)
    (x-vel
        :initarg :x-vel
        :accessor x-vel)
    (y-vel
        :initarg :y-vel
        :accessor y-vel)
    (history
        :accessor history
        :initform () )))

(defun generate-particle-2d (x-min x-max y-min y-max)
    (let ((x-range (- x-max x-min))
          (y-range (- y-max y-min)))
      (make-instance 'particle-2d
          :x-coord (ranged-random x-min x-max)
          :y-coord (ranged-random y-min y-max)
          :x-vel (ranged-random (- x-range) x-range)
          :y-vel (ranged-random (- y-range) y-range))))

(defun print-particle-2d (particle)
    (format t "x:~a~%y:~a~%x-vel:~a~%y-vel:~a"
        (x-coord particle)
        (y-coord particle)
        (x-vel particle)
        (y-vel particle)))

(defun one-line-print-particle-2d (particle)
    (format t "pos:<~a, ~a> vel:<~a, ~a>~%"
        (x-coord particle)
        (y-coord particle)
        (x-vel particle)
        (y-vel particle)))

;Swarm Related Code
(defclass swarm-2d ()
    ((best-x
      :initarg :best-x
      :accessor best-x
      :initform 0)
     (best-y
      :initarg :best-y
      :accessor best-y
      :initform 0)
     (best-answer
      :initarg :best-answer
      :accessor best-answer
      :initform most-positive-long-float)
     (particle-list
      :accessor particle-list)))

(defun generate-swarm-2d (particle-count x-min x-max y-min y-max)
    (let ((new-swarm (make-instance 'swarm-2d)))
      (setf (particle-list new-swarm) 
            (loop for i from 1 to particle-count 
               collect (generate-particle-2d x-min x-max y-min y-max)))
      new-swarm))

(defun print-swarm-2d (swarm)
    (format t "Best input:<~a, ~a>~%Best answer:~a~%"
        (best-x swarm)
        (best-y swarm)
        (best-answer swarm))
    (loop for particle in (particle-list swarm)
       do (one-line-print-particle-2d particle)))

;Swarm Optimization Code
(defparameter *swarm-size* 5)
(defparameter *swarm-iterations* 5)

(defun swarm-minimize-2d (fn x-limits y-limits)
   "A particle swarm optimizer for two dimensional equations"
   (let ((swarm (generate-swarm-2d *swarm-size*
                      (first x-limits) (second x-limits) 
                      (first y-limits) (second y-limits))))
       (loop for i from 1 to *swarm-iterations* do
        (loop for particle in (particle-list swarm)
           do (update-swarm-particle-2d particle swarm fn x-limits y-limits)))
           (list (list (best-x swarm) (best-y swarm)) (get-swarm-history-2d swarm))))

(defun update-swarm-particle-2d (particle swarm fn x-bounds y-bounds)
    (update-particle-history-2d particle)
    (let ((particle-answer (funcall fn (x-coord particle) (y-coord particle))))
        (when (< particle-answer (best-answer swarm))
            (setf (best-answer swarm) particle-answer)
            (setf (best-x swarm) (x-coord particle))
            (setf (best-y swarm) (y-coord particle))))
    (update-particle-velocity-2d particle (best-x swarm) (best-y swarm))
    (let ((updated-x (+ (x-coord particle) (x-vel particle)))
           (updated-y (+ (y-coord particle) (y-vel particle))))
       (setf (x-coord particle) (max (first x-bounds) (min (second x-bounds) updated-x)))
       (setf (y-coord particle) (max (first y-bounds) (min (second y-bounds) updated-y)))))

(defun update-particle-history-2d (particle)
    (setf 
      (history particle) 
      (append 
         (history particle) 
         (list (list (x-coord particle) (y-coord particle))))))

(defparameter *original-velocity-weight-2d* 0.8)
(defparameter *target-velocity-weight-2d* 0.3)

(defun update-particle-velocity-2d (particle target-x target-y)
    (let ((target-x-vel (- target-x (x-coord particle)))
          (target-y-vel (- target-y (y-coord particle))))
       (setf (x-vel particle) 
             (+ (* *target-velocity-weight-2d* target-x-vel) 
                (* *original-velocity-weight-2d* (x-vel particle))))
       (setf (y-vel particle) 
             (+ (* *target-velocity-weight-2d* target-y-vel) 
                (* *original-velocity-weight-2d* (y-vel particle))))))

(defun get-swarm-history-2d (swarm)
    (loop for particle in (particle-list swarm)
        collect (history particle)))

;Functions To Optimize
(defun double-parabola (x y)
    (+ (* x x) (* y y)))

 

More Done Than Done

 

With the 2D swarm finished you might think our next goal is to tackle the general swarm intelligence project, but I’m not quite ready to move beyond the second dimension just yet. I’d like to run a few more tests and play with some data first. So join me next time as we take a look at the wonderful world of data visualization!

An Extremely Easy Sample Optimization

 

Now that we have a swarm it’s time to teach it how to go out and conquer the stars… I mean teach it how to properly optimize a function. And for that we’re going to need a test function we can practice with.

 

We want our first testing function to be simple enough that we humans can double check the computer’s work without having to waste thirty minutes pecking numbers into our graphing calculators*. Later on we can come up with some complex tests to really give the swarm a run for its money but for now we want easy.

 

And what’s easier than a parabola? You just can’t beat good old x^2 when it comes to predictable equations with an obvious minimum. Everyone can see that the obvious minimum of x^2 is when x equals 0, right?

 

But this is a two dimensional swarm, and parabolas are only single variable problems. We want a two dimensional problem. So behold! The double parabola: x^2 + y^2

 

The optimized minimum of this two variable problem is just as obvious as the one variable version. When both x and y are 0 the final answer is also zero.

 

In Lisp terms our double parabola looks like this

 

(defun double-parabola (x y)
   (+ (* x x) (* y y)))

 

If we feed this function into our particle swarm it should ideally spit back an answer very close to (0, 0). And now that we know what we’re looking for we can start programming some swarm logic.

 

A Reminder Of How This Whole Thing Works

 

You’re probably getting bored of me explaining the basics of swarm intelligence over and over again, but if years of Sesame Street have taught me anything it’s that repetition is an important part of learning. So here we go, one last time, to make sure you’re 100% ready to actually program this thing.

 

Our goal is to take an equation with two variables and try to find the input that will give us the most optimal answer, defined here as the smallest answer possible (a minimum). So if we find two possible answers of 10 and 5 we consider the smaller number, 5, to be more optimal.

 

In order to try and find the most optimal, minimal answer for the entire equation we create a bunch of particles that all have a position and a velocity. The position represents a possible set of input values to the equation. The velocity represents how much we want to increase or decrease those inputs before making our next guess.

 

We run the swarm by looping through all the particles and feeding their position/input into the function we are trying to optimize. We keep track of what input has produced the most optimal guess so far. After each particle has made it’s guess we update their velocity to point a little bit more towards our best answer. Then we move all the particles based off of their velocity and repeat the process.

 

What this should do is create a bunch of random particles that make tons of random guesses. As time goes on the particles will start agreeing on a best answer and their velocity will begin to point towards it. This will cause the particles to get closer to each other so they can focus their guessing power around good answers. Eventually the particles will all be clumped together and stop finding new, better answers. At that point we grab the best answer so far and call it our best educated guess on what the true minimum must be.

 

Starting Small

 

This is a pretty complex problem, or at least pretty complex for a single blog post. So instead of jumping straight in and trying to write an algorithm for updating an entire swarm let’s take it easy and write an algorithm for updating a single particle. We’ll need that function for the bigger swarm algorithm anyways.

 

Updating a particle is a five step process:

1. Add the particle’s current position to its history.
2. Use the particle’s current position to generate an answer to the function we want to optimize.
3. Compare that answer to the current swarm best answer. If it is better, update the swarm best.
4. Update the particle’s velocity to point slightly more towards the swarm best.
5. Update the particle’s position based off of it’s velocity, but make sure it stays in the bounds of the problem.

 

In order to pull all that off we’re going to need the following pieces of information:

1. The particle we are updating
2. The swarm we are updating
3. The function we are optimizing
4. The boundaries of the problem.

 

Which leads us to this:

 

(defun update-swarm-particle-2d (particle swarm fn x-bounds y-bounds)
   ;Code goes here)

 

Turning A Function Variable Back Into A Function

 

One more bit of Lisp you’re going to need to know in order to construct this algorithm. You might remember that Lisp lets you create a function reference really easy with the #’function-name syntax, which will make it easy for us to toss our double-parabola around as #’double-parabola. But putting a function into a variable is only half the battle. We also need to get it back out.

 

This is as easy as using funcal. The first argument is a variable holding a function reference and then the rest of the arguments become data for that function. Ex:

 

[4]> (defparameter *test-fn* #’double-parabola)

*TEST-FN*

[5]> (funcall *test-fn* 2 5)

29

 

Would You Like To Save Your Data?

 

With that out of the way we can start going through the five steps of the algorithm. The first is to add the particle’s current position to its history, which is easy enough to do with the append function. This may not be the most efficient way to build the history data structure, but until we have real data on whether the algorithm is fast or slow there’s no point obsessing about this.

 

The trick to watch out for here is that append expects two lists. It then takes every item in the second list and puts it into a copy of the first list. So if we want to add a two item list to our history we can’t just pass the two item list; append will take it apart and put in the individual pieces. Instead we need to pass a list holding our two item list. append will take apart the outer list and leave the inner list alone.

 

(defun update-swarm-particle-2d (particle swarm fn x-bounds y-bounds)
   (setf
      (history particle)
      (append
         (history particle)
         (list (list (x-coord particle) (y-coord particle))))))

 

But that’s very ugly and takes up a lot of room. Let’s hide it in a function:

 

(defun update-swarm-particle-2d (particle swarm fn x-bounds y-bounds)
   (update-particle-history-2d particle))

(defun update-particle-history-2d (particle)
   (setf
      (history particle)
      (append
         (history particle)
         (list (list (x-coord particle) (y-coord particle))))))

 

Is That Your Final Answer?

 

With that little bit of record keeping code out of the way we can move on to the most important part of this entire algorithm: Checking whether or not the particle has a good answer in it. That’s the whole reason we programmed this swarm in the first place. The whole purpose of a particle is to test out new answers to see if they are better than the answer we’re currently using.

 

I can’t stress this enough! This is where the magic happens!

 

But just because it is important doesn’t mean it is hard. In fact, checking for answers is downright easy:

 

(defun update-swarm-particle-2d (particle swarm fn x-bounds y-bounds)
   (update-particle-history-2d particle)
   (let ((particle-answer (funcall fn (x-coord particle) (y-coord particle))))
      (when (< particle-answer (best-answer swarm))
         (setf (best-answer swarm) particle-answer)
         (setf (best-x swarm) (x-coord particle))
         (setf (best-y swarm) (y-coord particle)))))

 

We use funcall to feed the particle’s current x and y coordinates into whatever function has been passed into our optimizer. We store the answer in the local “particle-answer” variable and then compare it to the swarm’s current best answer. If the particle-answer is better we update the swam with a new best answer and new best coordinates. Pretty straightforward even with all the parenthesis.

 

A Little More To The Left…

 

We’re now halfway through our five item checklist for updating a particle. The next step is to adjust the particle’s velocity to point it slightly more towards our current best answer. There are lots of ways to do this, but for this Let’s Program I’m going to keep things really simple. This might make our swarm intelligence a little dumber than some of the more elegant algorithms, but it will make it much easier to blog about. If you’re interested in better swarms you can always use my code as a simple starting point to teach you enough of the basics to research and build your own, better optimizer.

 

For our simple velocity update what we want to do is calculate a target velocity that will send us hurtling straight towards the current swarm best answer. Then we want to take some fraction of that target velocity and add it to some fraction of the particle’s current velocity. Maybe something like 30% of the target velocity plus 80% of the current velocity (The two percentages don’t have to add up to 100%. We’re taking two fractions of two different things, not slicing one big thing into two pieces).

 

Deciding on exactly how much of each velocity to use has a big impact on your swarm. Large amounts of target velocity will focus your particles like a laser on whatever answer seems good at the time. Put more weight on current velocity and particles will lazily drift about exploring more data for a while before finally meeting up in the general vicinity of a good answer.

 

This is the sort of code that can get messy fast, so let’s put it into a function to avoid cluttering up update-swarm-particle-2d. All this function really needs to function is a particle to update and a target coordinate to point the particle at.

 

(defun update-swarm-particle-2d (particle swarm fn x-bounds y-bounds)
   (update-particle-history-2d particle)
   (let ((particle-answer (funcall fn (x-coord particle) (y-coord particle))))
      (when (< particle-answer (best-answer swarm))
         (setf (best-answer swarm) particle-answer)
         (setf (best-x swarm) (x-coord particle))
         (setf (best-y swarm) (y-coord particle))))
   (update-particle-velocity-2d particle (bext-x swarm) (best-y swarm)))

 

And now for the code itself:

 

(defun update-particle-velocity-2d (particle target-x target-y)
   (let ((target-x-vel (- target-x (x-coord particle)))
         (target-y-vel (- target-y (y-coord particle))))
      (setf (x-vel particle) (+ (* 0.3 target-x-vel) (* 0.8 (x-vel particle))))
      (setf (y-vel particle) (+ (* 0.3 target-y-vel) (* 0.8 (y-vel particle))))))

 

We figure out what the target x and y velocities should be by subtracting where we are from where we want to be, which will give us the speed we need to move at to hit our target in just one move. Example: The particle’s x position is five and the current best x is at two. Subtracting five from two gives us negative three (2-5=-3). So in order to reach the best x answer our particle needs to have a velocity of negative three units per update. Come up with a few more examples on your own if you’re having trouble following along.

 

Once we have target velocities it’s very easy to update the particle to a mix of 80% of it’s current velocity plus 30% of the best-answer seeking target velocity. Of course, it doesn’t have to be 80% and 30%. That’s just an example. We’ll probably have to run several tests to get a good feel for what values we should use. Let’s make that easier on ourselves by moving these magic numbers out of the code and into global variables.

 

(defparameter *original-velocity-weight-2d* 0.8)
(defparameter *target-velocity-weight-2d* 0.3)

(defun update-particle-velocity-2d (particle target-x target-y)
   (let ((target-x-vel (- target-x (x-coord particle)))
         (target-y-vel (- target-y (y-coord particle))))
      (setf (x-vel particle)
            (+ (* *target-velocity-weight-2d* target-x-vel)
               (* *original-velocity-weight-2d* (x-vel particle))))
       (setf (y-vel particle)
             (+ (* *target-velocity-weight-2d* target-y-vel)
                (* *original-velocity-weight-2d* (y-vel particle))))))

 

Much better.

 

But It Does Move!

 

Now that we’ve set the particle’s new velocity all that is left is to use that velocity to make the particle actually move. This is as simple as some basic addition and a couple quick checks to make sure the particles are in bounds.

 

(defun update-swarm-particle-2d (particle swarm fn x-bounds y-bounds)
    (update-particle-history-2d particle)
    (let ((particle-answer (funcall fn (x-coord particle) (y-coord particle))))
        (when (< particle-answer (best-answer swarm))
            (setf (best-answer swarm) particle-answer)
            (setf (best-x swarm) (x-coord particle))
            (setf (best-y swarm) (y-coord particle))))
    (update-particle-velocity-2d particle (best-x swarm) (best-y swarm))
    (let ((updated-x (+ (x-coord particle) (x-vel particle)))
           (updated-y (+ (y-coord particle) (y-vel particle))))
       (setf (x-coord particle) (max (first x-bounds) (min (second x-bounds) updated-x)))
       (setf (y-coord particle) (max (first y-bounds) (min (second y-bounds) updated-y)))))

 

 

I’m using a pretty cool trick here for keeping a number inside of bounds. Normally you would use two if statements to check if the number was bigger than the upper boundary or smaller than the lower boundary. Instead I keep it inside the upper boundary by just asking for the min value between our upper boundary and our given value. If our value is bigger than the upper boundary it will get discarded by the min. Then I do the same thing for the lower boundary with the max value. It lets you do boundary math in a single line of nested functions instead of needing conditional logic.

 

Not really a huge time saver, but I’ve always thought it was a nifty little pattern.

 

I Sure Hope This Works

 

Supposedly our code can now set particle history, update the swarm, change velocity and then move the particle. Time to see whether or not any of this code actually works, or if I’ll need to rewrite most of this before posting!

 

[1]> (load “swarm.lisp”)

;; Loading file swarm.lisp …

;; Loaded file swarm.lisp

T

[2]> (defparameter *test-swarm* (generate-swarm-2d 1 -10 10 -10 10))

*TEST-SWARM*

[3]> (defparameter *test-particle* (first (particle-list *test-swarm*)))

*TEST-PARTICLE*

[4]> (print-swarm-2d *test-swarm*)

Best input:<0, 0>

Best answer:8.8080652584198167656L646456992

pos:<0.40933418, -5.2009716> vel:<-6.6420603, -5.447151>

NIL

[5]> (update-swarm-particle-2d *test-particle* *test-swarm* #’double-parabola ‘(-10 10) ‘(-10 10))

-9.558693

[6]> (print-swarm-2d *test-swarm*)

Best input:<0.40933418, -5.2009716>

Best answer:27.21766

pos:<-4.904314, -9.558693> vel:<-5.313648, -4.357721>

NIL

 

Looks good. We build a swarm with exactly one particle and update that particle. You can see that before the update the swarm’s best answer is our ridiculously huge default. After the update the swarm’s best input has changed to the original position of the particle. We can also see that the particle’s velocity has shifted and that it updated it’s position successfully.

 

One Small Step For A Particle, Next A Giant Leap For Our Swarm

 

There was some pretty heavy code in this update, but that was expected. Updating particles is the heart of our entire algorithm. Now that that’s working the next post should be a breeze. All we have to do is upgrade from updating one particle once to updating an entire swarm of particles constantly… or at least until we get a workable answer.

 

 

 

* You’re reading an AI programming blog, of course you own a graphing calculator.

You’re Calling THAT Good Code!?

 

Last time we wrote a bunch of functions for randomly generating particle swarms. But it was very messy and verbose and filled with way too many calls to slot-value.

 

Now this isn’t a huge problem. The code works and having to type a few hundred extra ‘slot-value’ characters per program only wastes a few minutes of our life. From a time efficiency perspective cute cat videos are a much bigger risk to your productivity than wordy code.

 

But wordy, messy code has other downsides. More code means more places for bugs to hide and lets you fit less code on the screen at one time. Less code on the screen means lots of scrolling and lots of short-term memory abuse. It gets annoying fast.

 

So whenever possible we want to write clean, compact code that let’s us see multiple functions on one screen and leaves bugs with nowhere to hide.

 

Building Objects Using initargs Instead Of setf And slot-value

 

Remember our code for putting together a random particle? It was absolutely filled with repetitive calls to (setf (slot-value someobject someslot) somevalue). All those nearly identical lines are more than enough to make my head spin and my eyes grow all blurry.

 

So let’s get rid of them by using some of the extra features of the Lisp object system.

 

Remember that the last argument in defclass is a list of the data slots we want inside our object. Up until now we were just using simple names but we can give our classes an extra boost by wrapping those names into a list and gluing some extra keywords to them. Basically instead of just saying “I want an x-coord slot” we’re going to be saying “I want an x-coord slot with these special features”.

 

One of the more useful keywords is :initarg (don’t forget the colon, that’s Lisp keyword naming convention). :initarg let’s you create a new keyword that can be used inside of make-instance to assign a value to a data slot as soon as it is created without having to make a separate call to setf. You can name this new keyword whatever you want but it’s traditional to just name it after the data slot it’s linked to, but with a keyword colon glued to it.

 

It’s really easier to show you than to try and explain it:

 

(defclass particle-2d ()
   ((x-coord :initarg :x-coord )
    (y-coord :initarg :y-coord )
    (x-vel :initarg :x-vel )
    (y-vel :initarg :y-vel )
    history ))

 

As you can see I’ve replace our old list of data slot names with three item lists including, in order, the name of the data slot, the :initarg keyword and the new keyword I want to use in make-instance. This let’s me create a new particle with one or more data slot already filled in like this:

 

(make-instance 'particle-2d :x-coord 5 :y-coord 10 :x-vel -1.5 :y-vel 0.3)

 

Isn’t that much nicer than four separate calls to setf and slot-value?

 

Accessing Data Without slot-values

 

That little trick will already go a long way towards cleaning up generate-particle-2d and generate-swarm-2d. But that’s not the only place we have repetitive code. Take a look at print-particle-2d. The format function has four nested calls to slot-access one right after another. Not acceptable!

 

Once again Lisp already has a solution: another defclass keyword that we can use to add extra power to our particle and swarm classes. This time around we’re going to be using :accessor. The :accessor keyword has to be associated with a slot-name just like :init-args and is used to automatically create a simple function call that mimics slot-access. You can name the function whatever you want, but it usually makes the most sense to name it the same thing as the data value you want to access. Unlike with initarg this is a function, not a keyword, so we don’t want to glue a colon to it.

 

With that in mind let’s update our particle class definition again:

 

(defclass particle-2d ()
   ((x-coord
      :initarg :x-coord
      :accessor x-coord)
    (y-coord
      :initarg :y-coord
      :accessor y-coord)
    (x-vel
      :initarg :x-vel
      :accessor x-vel)
    (y-vel
      :initarg :y-vel
      :accessor y-vel)
    (history
      :accessor history )))

 

Now getting data out of a particle is as easy as (x-coord particle), which is easier to read and write than (slot-value particle ‘x-coord).

 

Default Values

 

There is one last trick that we can use to clean up our existing code and that is adding default values to some of our data slots. For example, we know that we want our swarms to always start out with a best-answer of most-positive-long-float and that we want some sort of numeric value in best-x and best-y. Doing this is as easy as slipping an :initform into our class definition:

 

(defclass swarm-2d ()
   ((best-x
      :initarg :best-x
      :accessor best-x
      :initform 0)
    (best-y
      :initarg :best-y
      :accessor best-y
      :initform 0)
    (best-answer
      :initarg :best-answer
      :accessor best-answer
      :initform most-positive-long-float)
    (particle-list
      :accessor particle-list)))

 

Now new swarms will roll off the assembly* line with their best-x, best-y and best-answer slots already filled with predictable dummy data (unless we use one of our initargs to overwrite them). That saves us a few more lines of code when generating our random swarm.

 

Code So Far

 

Now that our code is nice and tidy I think it’s time for this Let’s Program’s first complete code dump. Here are the current contents of my project file “swarm.lisp”

 

;Helper Functions
(defun ranged-random (min max)
    (+ min (random (float (- max min)))))

;Particle Related Code
(defclass particle-2d ()
    ((x-coord
        :initarg :x-coord
        :accessor x-coord)
    (y-coord
        :initarg :y-coord
        :accessor y-coord)
    (x-vel
        :initarg :x-vel
        :accessor x-vel)
    (y-vel
        :initarg :y-vel
        :accessor y-vel)
    (history
        :accessor history
        :initform () )))

(defun generate-particle-2d (x-min x-max y-min y-max)
    (let ((x-range (- x-max x-min))
          (y-range (- y-max y-min)))
      (make-instance 'particle-2d
          :x-coord (ranged-random x-min x-max)
          :y-coord (ranged-random y-min y-max)
          :x-vel (ranged-random (- x-range) x-range)
          :y-vel (ranged-random (- y-range) y-range))))

(defun print-particle-2d (particle)
    (format t "x:~a~%y:~a~%x-vel:~a~%y-vel:~a"
        (x-coord particle)
        (y-coord particle)
        (x-vel particle)
        (y-vel particle)))

(defun one-line-print-particle-2d (particle)
    (format t "pos:<~a, ~a> vel:<~a, ~a>~%"
        (x-coord particle)
        (y-coord particle)
        (x-vel particle)
        (y-vel particle)))

;Swarm Related Code
(defclass swarm-2d ()
    ((best-x
      :initarg :best-x
      :accessor best-x
      :initform 0)
     (best-y
      :initarg :best-y
      :accessor best-y
      :initform 0)
     (best-answer
      :initarg :best-answer
      :accessor best-answer
      :initform most-positive-long-float)
     (particle-list
      :accessor particle-list)))

(defun generate-swarm-2d (particle-count x-min x-max y-min y-max)
    (let ((new-swarm (make-instance 'swarm-2d)))
      (setf (particle-list new-swarm) 
            (loop for i from 1 to particle-count 
               collect (generate-particle-2d x-min x-max y-min y-max)))
      new-swarm))

(defun print-swarm-2d (swarm)
    (format t "Best input:<~a, ~a>~%Best answer:~a~%"
        (best-x swarm)
        (best-y swarm)
        (best-answer swarm))
    (loop for particle in (particle-list swarm)
       do (one-line-print-particle-2d particle)))

 

And here is a quick test showing off how everything works by generating a random four particle swarm with x-values between -10 and 10 and y values between -5 and 5:

 

[1]> (load “swarm.lisp”)

;; Loading file swarm.lisp …

;; Loaded file swarm.lisp

T

[2]> (print-swarm-2d (generate-swarm-2d 4 -10 10 -5 5))

Best input:<0, 0>

Best answer:8.8080652584198167656L646456992

pos:<-3.4808707, 0.3767519> vel:<-1.4654808, -3.5502791>

pos:<-2.8356638, 3.5513773> vel:<15.891026, 0.40564632>

pos:<-4.020668, -0.7705631> vel:<0.81866837, -5.2009716>

pos:<-3.3210301, -1.3617878> vel:<-16.749294, 4.1957817>

NIL

 

We’re Just Getting Started

 

Our code is clean, compact and we can generate an entire swarm with a single function call. That’s a pretty important milestone. From here we can finally start moving on to the fun stuff, like data visualization and the actual particle optimization algorithm.

 

 

* No pun intended, which is too bad because that would have been a great computer joke if I had thought of it on purpose.

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?