Making Hard Problems Easier
When coding a difficult program it usually helps to try and split your problem into multiple, smaller problems that are individually much easier to solve. For example, you’d be crazy to try and build an entire 3D graphics engine all at once. It would be much smarter to start out by focusing just on drawing simple shapes. And then move on to calculating lighting. And then move on to adding color and texture. Eventually all the simple pieces come together to help create the big complicated program you wanted in the first place.
In this case, my eventual goal is to write a generic particle swarm optimizer that can handle equations with any number of variables. The swarm AI will be flexible enough to do equally well whether it’s trying to find the low point in a 2D graph or balance a chemical equation with twenty-seven different variables. Hardly cutting-edge research, but still a moderately challenging problem for a part-time blogger with limited free time. Finding some way to split this project into smaller more blog-able parts would be a big help!
Which is why I’m going to start by programming a simple swarm that can only handle two variable equations. This very specific goal will let me focus on the fundamental logic of our AI without worrying about the added complexity of trying to figure out how many variables we’re trying to optimize. We can take the easy way out and just hard-code all of our functions to always expect two variables. Only after the core AI logic is out of the way will I worry about the issue of flexibility.
By splitting the problem of “Build a generic particle swarm AI” into the two mini-problems “Build a 2D particle swarm” and “Upgrade a 2D particle swarm” I hope to save myself a lot of confusion and frustration.
But why start specifically with a 2D swarm? Why not a 3D or 4D or 11D swarm? Mostly because two dimensional equations are easy to visualize and hand-optimize, which will make this program much easier to test and debug. Focusing entirely on optimizing eleven variable equations would still let me start with a specific AI and then upgrade it later, but double checking my logic in eleven dimensions would be a lot more difficult and take a lot more time than with a 2D swarm.
Designing The Function Call
Now that we know that we’re going to be specifically building a function for optimizing two variable equations we can start thinking about what our function should look like. What do we want to call it? What information does it need? How do we want to pass it that information?
Well, an equation optimizer obviously needs a reference to the function representing the equation we want optimized. We also probably need to give the optimizer some boundaries to let it know what the biggest and smallest possible variables it should work with are. We might only want the swarm to consider positive numbers or maybe restrict it to x and y values between positive and negative ten.
Putting our wish list together here is a sample of what our function call might look like if we wanted to optimize another function called “reactor-output” and restrict our x inputs to between positive and negative one thousand while restricting our y input to somewhere between zero and fifty:
(swarm-minimize-2d #’reactor-output ‘(-1000 1000) ‘(0 50))
Two new bits of Lisp syntax to look out for here. First, the pound-apostrophe-function-name syntax of #’reactor-output. This is a lisp shortcut that says “this is a function reference”. That’s all it takes to pass a function around like data in Lisp.
The next thing you should notice is the apostrophe before the two lists. Normally when Lisp evaluates a list it tries to interpret the first symbol as a function and the rest of the list as arguments. Prefacing a list with a ‘ lets Lisp know that this particular list is actually a list and shouldn’t be evaluated.
Now that we have a sample of how we want to call our function let’s take a stab at actually defining it. We know we want to call it “swarm-minimize-2d” and that it has three arguments (a function reference, a set of x boundaries and a set of y boundaries).
(defun swarm-minimize-2d (fn x-limits y-limits) “A particle swarm optimizer for two dimensional equations” ;Optimization code will go here)
Good start!
Designing The Return Value
The next step ask ourselves what we want the output to look like. The most obvious and important piece of output will be the coordinates of the most optimal solution found by the swarm. For convenience we can just put this in a two item list. Ex: (4 7)
Honestly, the coordinates of the optimal solution are the only thing we need for a working solution. But I think it would also be interesting to get a report of how the swarm found that answer. So in addition to the solution let’s include a chronological record of every point searched by every particle in the swarm. We can implement this with a list of lists of coordinates structured something like this:
( ((1 2) (2 2) (3 2))
((-1 -4) (0 -3) (1 -2))
((5 4) (4 3) (3 2)))
Give your eyes a minute to adjust to the parenthesis. I’ll wait.
This sample list represents three particles that each tried three different locations. The first particle started at (1, 2), moved to (2, 2) and finished at (3, 2). The second particle started at (-1, -4), moved to (0, -3) and finished at (1, -2). I’ll leave it up to you to interpret what the third particle did.
… done yet?
If you came up with any answer other than “The third particle started at (5, 4), moved to (4, 3) and finished at (3, 2)” you need to go back and try again.
So we’ve got a good grasp on both the values we want to return from our function. But how do we go about returning multiple values from one function? Well, the most obvious answer would be to put both values into some sort of list or array and then return that. This is going to create an almost painfully nested data structure, but it will work fine. Lisp does have some other interesting ways to return multiple values but I think they are overkill for this particular situation.
So let’s update our function skeleton with a prototype return line. I’m also going to introduce the Lisp list function, a straightforward bit of code that just takes all of it’s arguments and builds a list out of them. We can use it for linking together our optimal solution and swarm history into a single output list.
(defun swarm-minimize-2d (fn x-limits y-limits) “A particle swarm optimizer for two dimensional equations” ;Optimization code will go here (list optimal-solution particle-history))
It’s important to note that this code is currently broken. If you type it into your REPL and try to run it you’ll probably get some sort of error like “SWARM-MINIMIZE-2D: variable OPTIMAL-SOLUTION has no value”. That’s OK for now. This function skeleton was mostly just a though experiment to help us get a handle on the real function we’re going to build starting next post.
So be sure to check back next time where I start writing some Lisp code you can actually run.