Let’s Program A Swarm Intelligence 3: All Your Max Are Min

A Closer Look At Optimization

 

We’ve got a problem and we’ve got a programming language. Anything else we need to get this Let’s Program going?

 

Well, we really probably should spend a little more time talking about exactly what it means to optimize an equation. Just saying that we want our swarm to find “better” answers, hopefully the “best” answer, doesn’t really tell us all that much. What does a better answer look like?

 

The definition of good and better answers actually depends a lot on the problem being solved. If you’re trying to optimize your company’s profits you probably want the biggest value you can find. A two million dollar profit is more optimal than a one million dollar profit.

 

On the other hand imagine you are trying to optimize a chemical factory that produces toxic waste. Toxic waste is expensive to dispose of so in this case the optimal answer is the smallest answer you can come up with. Producing one ton of waste per month is more optimal than producing ten tons.

 

Now let’s imagine that in order to minimize your toxic waste you figure out that you’re going to need exactly one thousand gallons of fresh Chemical X every hour. So you start developing a Chemical X production system. Optimizing this system means producing as close to one thousand gallons per hour as possible. Making too little Chemical X slows down your system. Making too much Chemical X wastes money. You have an exact target to hit.

 

Summary: The Three Types Of Optimization

 

All numeric optimization problems can be classified as one of the following three types:

 

Minimum: Optimizing towards the smallest result possible.

 

Maximum: Optimizing towards the biggest result possible.

 

Target: You already have a specific, ideal result in mind. Optimization is the process of finding out how close you can get to that desired result.

 

Quick example. After collecting some data you find five possible solutions with the following answers: 50, 75, 100, 120 and 160.

 

If you are optimizing towards a minimum then 50 is the most optimal answer of the five.

 

If you are optimizing towards a maximum then 160 is the most optimal answer of the five.

 

If you are optimizing towards a target of 90 then 100 is the most optimal answer. If your target was 130 instead then 120 would be the most optimal answer.

 

Three In One Optimization: Everything Is A Minimum

 

If there are three different kinds of optimization then you might think that means we need to write three different optimization algorithms. But with just a little cleverness you can get away with only one optimization function. This is because all three types of optimization can be reduced to different kinds of minimums.

 

Minimum’s can be treated as minimums because that’s what they actually are. That was easy.

 

A maximum can be turned into a minimum by multiplying all values by -1. So instead of looking for the max between 1, 2 and 3 (which would be 3) we look for the minimum between -1, -2 and -3 (answer is still the 3).

 

A target goal can be turned into a minimum by focusing not on the answers themselves but on the absolute difference between the answers you find and the result you want. If your target is 100 and your answers are 90, 105 and 115 then you would reduce them to differences of 10, 5 and 15. We minimize to find the smallest difference (5) which lets us know which value was closest to our target (105).

 

Conclusion: We Need To Focus On Minimums

 

Now that we know that every optimization we want to do can be modeled as a minimization problem we’re ready to jump into actual problem solving. Check back in a few days and I’ll start outlining my design approach and share my fist bits of skeleton code.

 

Note to readers from the future: You don’t have to check back in a few days. You can just click on the next post whenever you want. Aren’t you lucky?

Let’s Program A Swarm Intelligence 2: Learning To Love Lisp

Today’s Programming Language Of Choice Is…

 

Normally this is where I would launch into a long and tedious explanation of how important it is to choose the right language for your program. But this time I’m going to skip all that and just flat out tell you I’m going to use Lisp for our particle swarm optimizer.

 

You see, Lisp has become one of my favorite programming languages. But since my current job is focused entirely around PHP and Perl I don’t really have any professional opportunities to use it. So if I want to practice the language I have to do it on my own time. And, hey, this blog just happens to count as my own time.

 

Lips Is Actually A Good Choice For This Problem

 

The number one reason I plan on writing this swarm intelligence in Lisp is because I like Lisp. But even if I didn’t I would still have to admit that it’s a decent match for the problem being solved.

 

Remember, the basic idea behind an optimizer is to create a program that can be handed an arbitrary mathematical function and then find a really good solution to it. In computer terms this means we probably want to create a function that can accept other functions as an argument. And Lisp is famous for the way it lets you toss functions around like any other piece of data. No messing around with function pointers of weird memory tricks: Just grab a function and stuff it into a function call.

 

Of course, Lisp is hardly the only language to let you do this. In fact, most modern languages let you pass functions around like variables if you try hard enough. So if you really really don’t want to write in Lisp you could replicate everything I do here in a different language. In fact, that might be a good exercise for anybody wanting to practice their favorite language.

 

But why bother? Lisp is actually a pretty easy language to learn. It does have some super-advanced features that can be hard to wrap your head around but we don’t actually need any of those for this program. And the mere fact that you are willingly reading an article about AI programming suggests you are more than smart enough to learn basic Lisp in practically no-time at all.

 

Everything You Need To Know About Lisp In One Example

 

If you really want to learn Lisp you should probably read a book on the topic. I would personally recommend Practical Common Lisp, mostly because the author has been kind enough to post the entire text online for free.

 

But you don’t need an encyclopedic knowledge of Lisp just to follow along with my particle swarm code. All you really need is a basic understanding of some simple Lisp ideas.

 

With that in mind I will now attempt to create a single code example that will demonstrate enough Lisp syntax to explain the entire language to anyone who already understands at least one other programming language. I’d like to ask the audience to please be quiet as I attempt this daring feat:

 

(function-name argument1 (another-function another-argument) argument3)

 

Tada!

 

This single line of code shows off three very important aspects of the Lisp programming language:

  1. Almost everything in Lisp is made out of lists. Lists are just parenthesis with symbols inside them. You can include an entire list inside of another list.
  2. A function call is just a list where the first symbol is the name of a function and the rest of the symbols are arguments to that function. Ex: addition looks like this: (+ 1 2)
  3. If one of the arguments to your function is a function call it will be evaluated first and it’s return value will be passed as an argument. Ex: (+ 5 (* 2 6) ) becomes (+ 5 12).

 

That’s pretty much it. Lisp can be written 90% the same as any other programming language once you get used to the fact that you’ll be writing (doStuff A B) instead of doStuff(A, B);

 

Everything You Need To Know About Lisp In A Few Examples

 

So… Lisp is all about lists and putting the functional call inside the parenthesis instead of before them. Cool. Anything else we need to know?

 

I guess there are one or two other things you probably need to know before you can really start programming. So let’s jump into a few quick examples of the Lisp way to do common programming tasks.

 

Variables In Lisp

 

The most obvious programming task is creating variables and giving them values. In Lisp you create global variables like this:

 

(defparameter variable-name starting-value)

 

And you can change variables like this:

 

(setf variable-name new-value)

 

Please note that there was no equals sign in that code. In Lisp the equal sign is actually used to test for equality instead of doing assignments.

 

Lisp also supports local variables for those situations where you have a variable that should only exist inside of a certain function. It looks kind of like this:

 

(let ( variable/value pairs) your code)

 

A more thorough and accurate example would be something like this:

 

(let ((x 10)
      (y 20))
   (* x y))

 

Don’t sweat it if you’re having trouble keeping track of all those nested lists and parenthesis. It will come to you in time.

 

Functions In Lisp

 

The next question on everybody’s mind is probably “How do you define functions in Lisp?”. With the handy defun function of course!

 

(defun name-of-function (arguments for function)
   “Optional help string”
   body of function)

 

For a really quick (and stupid) example:

 

(defun add-two (number)
   “Adds two to a number”
   (+ 2 number))

 

You might be wondering, “Where’s the return statement in that function?” Doing some math isn’t very useful if we don’t actually return the answer.

 

Well, Lisp doesn’t have return statements. Instead it automatically returns whatever the result of the last line of code in the function happens to be. This is convenient because that’s usually what we wanted anyways. Of course, if it isn’t you can always mimic a return statement by making sure the variable you want is the last thing mentioned in the function.

 

(defun add-two-but-return-original (number)
   (+ 2 number)
   number)

 

Welcome To The REPL

 

So we can declare functions now, but how exactly do we run them?

 

Well, first off you’re going to need a Lisp interpreter/compiler. I personally use CLISP and can vouch that it works great on both Linux and Windows.

 

While you wait for that to download let’s talk a little bit about what exactly it is you’re about to install. CLISP isn’t just a compiler or interpreter, it’s an interactive tool known as a “Read Evaluate Print Loop”, or REPL.

 

Like the name suggests the REPL is just an endless loop that reads in programmer input, tries to evaluate that input as Lisp code and then prints the result of whatever it just evaluated. Not quite following me? Well then just boot up CLISP (it’s done downloading by now, right?) and follow along with these examples.

 

[1]> 7

7

 

We type in the number 7. The REPL reads the 7 and then evaluates it. 7 evaluates to… well… 7. Finally the REPL prints out that 7. Nothing interesting here.

 

[2]> (+ 7 5)

12

 

This time we type in the list (+ 7 5). The REPL reads the list in and tries to evaluate it as a function call. It succeeds and does some addition for us. Finally it prints the result of that addition, in this case 12.

 

[3]> (defun hello-world-printer () (print “Hello World”))

HELLO-WORLD -PRINTER

 

Now I’m defining a new function using the define function syntax I explained a few paragraphs ago. The REPL reads in my input, evaluates it as a function and then returns the function name. I can now run that function by typing in (hello-world-printer) into the REPL.

 

But sometimes you don’t want to type your functions straight into the REPL. Sometimes it’s easier to write your code in a text file that can be saved and shared. In fact, trying to write a serious program entirely through the REPL would be a nightmare. Fortunately you can do this instead:

 

[4]> (load “myprogram.lisp”)

 

That’s all it takes to get the Lisp REPL to act more like a normal compiler or interpreter. Just write your entire program and use the load function to process the whole thing all in one go. And with that last bit of advice we’re ready for the meat of this Let’s Program.

 

Is That Really All We Need To Know?

 

I think so. You know how to create variables, update variables and write functions. Hardly enough to be a professional Lisp programmer but more than enough to follow along with my code and understand it well enough to write your own version in whatever language you want.

 

So give yourself a pat on the back. You not only now know more about swarm intelligences than most people who ever set foot on this earth, you also now know more about Lisp. Learning new things is fun like that.

Let’s Program A Swarm Intelligence 1: Introducing Particle Swarm Optimizers

Welcome Back Dear Readers!

That last Let’s Program went pretty well. Built a nifty little chatbot and got some good reader feedback. So let’s give this a second go. Our topic this time? Swarm Intelligences!

What Is A Swarm Intelligence?

A swarm intelligence is a large-scale alien brain capable of controlling billions and billions of deadly warriors at one time. They grow stronger and smarter by absorbing the DNA and memories of other species. They are ruthless, efficient and unstoppable.

I’m Pretty Sure That Isn’t Right

Oh, sorry. Looks like my old Starcraft manual got mixed in with my research material. My bad. Good game though. I really ought to get around to buying the sequel. Rumor has it this one has 3D graphics and everything!

Anyways, let’s start over!

What Is A Swarm Intelligence?

The phrase “Swarm Intelligence” refers to a bunch of different problem solving algorithms that were all inspired by watching how real life animals make group decisions. Things like flocks of birds, schools of fish, colonies of ants and swarms of bees have all inspired their own types of swarm intelligence. While each swarm intelligence algorithm is different most are based around the idea of creating a large number of semi-independent problem solving programs that work together and share information. Why have just one AI working on your problem when you can have 100?

Of course, the fact that there are so many different kinds of swarm intelligences means we can’t really just program a generic “Swarm Intelligence”. We’re going to have to choose a specific kind. After a little research I decided that this Let’s Program is going to focus on a type of AI called a “Particle Swarm Optimizer”.

So for the rest of this series when I say “Swarm Intelligence” know that I’m probably referring to a “Particle Swarm Optimizer”. But always remember, there are lots of different kinds of swarm intelligence and they all work differently.

What Is A Particle Swarm Optimizer?

A “Particle Swarm Optimizer” is an optimizer that uses a particle swarm to do it’s optimizing.

That last sentence was very very accurate but it honestly wasn’t very useful. Let’s break it down a little further. First off let’s cover what an “Optimizer” is.

When we talk about “solving” a problem we usually think of finding one right answer. But not all problems have one right answer. Lots of real world problems actually have an infinite number of solutions that are all “right”. But even if they are all “right” some of those solutions will be better than others.

For example, imagine you run an oil refinery. By adjusting the refinery’s temperature and pressure you discover you can increase or decrease the amount of oil you refine per hour. Any temperature and pressure setting that refines enough oil to pay your bills is a “right” answer, but there are “better” settings that will refine more oil per hour and earn you enough cash to not just pay the bills but also give your employees a big bonus and buy yourself a Ferrari.

Obviously we aren’t going to settle for just any old “right” answer when there is a “better” answer and a Ferrari on the line. This process of trying to find better solutions even after finding one “right” answer is known as “Optimization” and there are lots of different ways to do it.

The “Particle Swarm Optimizer” approach to optimization is to basically make a whole bunch of random guesses at possible best solutions. You then look at which guess performed the best and use that information to adjust all of your guesses. You then see what the best solution from your adjusted guesses was and do the whole thing over again. After several thousand or million random guesses (depending on how much time you can spare) you should eventually have settled on one best guess.

But why is this called a “Particle Swarm Optimizer” and not an “Intelligent Mass Guessing Optimizer”? (Besides the obvious fact that the first name is much much cooler)

Well, let’s go back to our oil refinery example where we can adjust the temperature and pressure. Every guess we make will just be a temperate mixed with a pressure. Now let’s make a graph where the X axis is temperature and the Y axis is pressure. Now let’s mark down every guess we’ve made so far. You should end up with a big cloud of random dots.

Now every time we update our guess we also update our graph. The cloud of random dots will start to move around and eventually drift towards good answers. If you squint a little it will look like the dots are working together to explore new possible solutions. In fact, it will look like a big swarm of particles drifting through space and gathering around good solutions.

Hence “Particle Swarm Optimizer”.

The difference between a bunch of guesses and swarm of particles is just a matter of perspective

The difference between a bunch of guesses and swarm of particles is just a matter of perspective

Particle Swarm Weaknesses

Now that you know how particle swarm optimizers more or less work you can probably start to see a few potential problems.

First off, particle swarms only work in situations where you can make random guesses and get an answer back immediately. Making millions of guesses isn’t a good strategy if you have to wait several hours or days to find out which guesses did well and which flopped. Usually this means that you can only use a particle swarm to optimize problems that you understand well enough to program into your computer.

For instance, if there is a complex equation explaining how temperature and pressure influence your hypothetical oil refinery you could use a particle swarm to optimize that equation. On the other hand if you’re really not sure how your oil refinery works* particle swarm optimization would be a really bad idea. Every time your program made a new guess you would have to physically adjust the refinery, take some physical measurements and then type them into your computer. Yuck.

So particle swarms only work with complete equations or with automated testing equipment that can perform experiments and report results really really fast.

Also, because particle swarms operate by making intelligent guesses there is no actual guarantee that they will find the “best” solution available. There is always a risk that the swarm will drift past the “best” answer and instead get attached to a “good” answer. This is actually a common problem with lots of AI techniques though, not just particle swarms. And as you’ll see in a few paragraphs this is actually less of a problem for particle swarms than it is for many other algorithms.

Why Use A Particle Swarm Optimizer?

So why would we want to use an AI that requires a full mathematical description of the problem we want to solve, especially if it can’t even guarantee a truly optimal solution? If we’ve already managed to reduce our problem to an equation can’t we just use calculus to find the true best value?

Excellent question, clever reader. If you are just trying to optimize a two variable equation you probably are better off using calculus and just outright solving the thing. Not every problem needs an AI.

But lots of problems that are too complicated to solve with calculus, or at least too complicated to solve quickly. Using calculus to solve a seventeen variable equation is really really hard. If some of the variables are dependent on each other it gets even harder. We’re talking about the sort of problem that would be worth a PhD.

But the particle swarm’s guessing approach works just as well in seventeen dimensions** as it does in two. It doesn’t really care how hard it is to derive or integrate an equation because it never has to do either of those things. It just guesses, checks and adjusts.

So you could spend ten years trying to solve an impossible calculus problem… or you could just plug it into a swarm intelligence, wait an hour or two and get an answer that’s probably close enough to the true optimum for all practical purposes.

But what if you are really worried about missing out on the true optimum? Well, particle swarms are less likely to miss true optimums than many other types of AI. This is because the particles start out spread all over search space. This increases the chance that at least one particle will notice really good data and let the rest of the swarm know that they are looking in the wrong place. A less swarmy algorithm that starts looking in the wrong place is more likely to just get stuck there.

The particles help each other avoid getting stuck on a "merely good" answer

The particles help each other avoid getting stuck on a “merely good” answer

Finally, particle swarms are useful because of their ability to handle “rough” data. Imagine a step function where you use one equation when temperature is below 100 degrees and another equation when it is above 100 degrees. Lots of problem solving algorithms will throw a fit when they hit that gap between equations. But since the particle swarm is just guessing and checking as it flies through problem-space it doesn’t really care that the data does really weird things around 100 degrees. It just notes whether the end result is better or worse than before and keeps going.

The particle swarm has no problem with rough data that would destroy a calculus based AI

The particle swarm has no problem with rough data that would destroy a calculus based AI

Conclusion

Now you know what a swarm intelligence is and have been introduced to particle swarm optimization. Congratulations! You are now part of the less than 1% minority of the population that has ever bothered to study AI in any depth.

But why settle for that? Let’s take it to the next level by actually programming one, putting ourselves in the 1% of the 1% of the population that enjoys amateur AI programming. I have no idea if this is a particularly useful super-minority to be part of… but why let that stop us?

* Why did you buy an oil refinery if you didn’t understand how it worked? Invest more responsibly in the future!

** Have fun imagining a seventeen dimensional swarm of particles flying through seventeen dimensional space.