Let’s Program A Swarm Intelligence 11: Turning Your World Upside Down

Maxing Our Mins

 

Our current AI is pretty good at minimizing equations, but what if you want big numbers instead of small numbers? For example, what if you want to find the maximum for the equation -1 * (x^2 + y^2)? Or as we say in Lisp:

 

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

 

This is the opposite of our normal double parabola. This time the bigger x and y get the more negative and small our answer becomes. So the origin (x=0, y=0) will give us the biggest possible answer instead of the smallest possible answer.

 

a parabola and an inverse parabola

A badly drawn sketch of the difference between a parabola and an inverse parabola

Now how are we going to go about building a maximizer for this problem? Well, hopefully you remember back in part three where we showed that you can turn a minimizer into a maximizer just by multiplying all your results by -1 before passing them to the minimizer. That’s enough to turn big answers into small answers so our minimizer can track them down.

 

Our next task is clear then: We need to create a new function that accepts a maximizable function, creates an inverse version of it and then feeds that inverse function into the minimizer we already have.

 

Lambda: Kind Of A Big Deal

 

Since it looks like we need to build new functions on the fly I think it’s about time to introduce the mighty lambda. This powerful Lisp feature allows us to create new anonymous functions right on the spot and then immediately assign them to a variable or pass them to a function.

 

Explaining anonymous functions and how they differ from named functions can be a little tricky, so let’s just jump to some examples. The basic syntax is:

 

(lambda (argument names) (code that uses argument names here))

 

For example, here is a lambda function for multiplying a number by 3:

 

(lambda (x) (* 3 x))

 

And here it is an example of using lambda to assign an anonymous function to a variable and call it later:

 

[1]> (defparameter *test-fn* (lambda (x) (* 3 x)))

*TEST-FN*

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

27

 

For a second example let’s look at something from our swarm intelligence code. Here is how we normally minimize a double parabola, by passing a reference to a pre-existing doube-parabola function:

 

(swarm-minimize-2d #'double-parabola '(-10 10) '(-10 10))

 

But we could also use lambda to just define a double parabola function right on the spot:

 

(swarm-minimize-2d (lambda (x y) (+ (* x x) (* y y))) '(-10 10) '(-10 10))

 

This syntax is going to be very important in just a few seconds!

 

Lambda Maximizer To The Max!

 

Now we can talk about how to use Lisp to invert the results of a function call. First, I’m sure you remember that when we have a function inside of a variable named “fn” we can call that function and pass it two variables like this:

 

(funcall fn x y)

 

And if we know that the function is going to have numeric output we can invert it like this:

 

(* -1 (funcall fn x y))

 

Now here comes the tricky part. If we have a function inside a variable like “fn” we can use lambda to create a new function that accepts two variables, passes them to “fn” and then inverts the result. We can then pass this entire anonymous inverse function to swarm-minimize.

 

(defun swarm-maximize-2d (fn x-limits y-limits)
   (swarm-minimize-2d (lambda (x y) (* -1 (funcall fn x y))) x-limits y-limits))

 

If you understand this one-line function then you’ve mastered a lot of what makes Lisp so powerful.

 

And here it is in action:

 

[7]> (defparameter *swarm-iterations* 75)

*SWARM-ITERATIONS*

[8]> (defparameter *swarm-output* (swarm-maximize-2d #’inverse-double-parabola ‘(-10 10) ‘(-10 10)) )

*SWARM-OUTPUT*

[9]> (first *swarm-output*)

(-5.1605515E-5 -0.0015050085)

 

What do you know, that’s more or less the maximum for a double inverse parabola.

 

Stay On Target

 

Back in part three we also talked about how you could use a minimizer to help you hit a specific goal by minimizing the distance between your target and your results. We can pull this off as another one line function thanks to lambda:

 

(defun swarm-target-2d (fn target x-limits y-limits)
   (swarm-minimize-2d (lambda (x y) (abs (- target (funcall fn x y)))) x-limits y-limits))

 

[10]> (defparameter *swarm-output* (swarm-target-2d #’double-parabola 3 ‘(-10 10) ‘(-10 10)))

*SWARM-OUTPUT*

[11]> (first *swarm-output*)

(-1.5764234 -0.7178333)

[12]> (double-parabola -1.5764234 -0.7178333)

3.0003953

 

In this test I loaded up our classic double parabola and gave it a target of ‘3’. Seventy five iterations later the swarm comes up with (-1.6, -0.7) as a possible input and when we plug that in we get very close to the 3 we were hoping for. Success!

 

Conclusion

 

We covered one of the stranger but more powerful features of the Lisp programming language and used it to magically transform our particle swarm minimizer into a particle swarm maximizer and a particle swarm goal seeking machine. I’d say that’s a pretty good day’s work.

 

Join me next time as I take our three swarm optimization functions and then do everything in my power to stump them with hard to optimize inputs and strange function patterns.