Let’s Program A Swarm Intelligence 16: The Swarm Ate My Homework

The Freshman Math Challenge


After roaming around on the Internet for a while I found a website offering open source college material including a rather decent worksheet on multi-variable optimization, which you can find here http://ocw.capilanou.ca/mathematics-statistics/math-109-calculus-ii/optimization-problems.pdf/view?searchterm=optimization.


I’ll be using problems from this worksheet to test out the swarm. Let’s see if we’ve built a machine smart enough to pass an entry level calculus class.


Profit Optimization


First problem from the worksheet is pretty straightforward. There is a random desk company that sells both finished and unfinished desks, although I’m not actually sure what they mean by this. Are they talking about whether or not the wood on the desk is properly stained, or by unfinished do they mean that they literally sell desks that are still missing pieces? Is there a big market for three legged desks?


Anyways, whatever an “unfinished” desk is the company’s revenue looks like this:


revenue = 200*finished + 160*unfinished – 0.2*finished*unfinished – 0.2*finished^2 – 0.25*unfinished^2.


The company’s expenses look like this


expense = 100*finished + 70*unfinished + 4000


The company’s profit is equal to its revenue minus its expenses, which we can represent as this Lisp function:


;Revenue for a company which sells both finished and unfinished furniture
(defun company-profit (fin unfin)
   (let ((revenue (+ (* 200 fin) 
                     (* 160 unfin) 
                     (* -0.2 fin unfin) 
                     (* -0.2 fin fin) 
                     (* -0.25 unfin unfin)))
         (expense (+ (* 100 fin) (* 70 unfin) 4000)))
      (- revenue expense)))


Now we just have to decide on some boundaries for our swarm guesses. Since you can’t produce less than 0 units of furniture our minimum bound for both types of desks will be 0. When it comes to the upper bounds we’ll have to take a bit of a guess. The bigger the boundary the larger our swarm will need to be to explore it and the longer the search will take, so we want to aim for an upper boundary that is small enough to be efficient while still being large enough to capture the maximum number of desks a company can reasonably build in one week.


Let’s start out with an upper bound of 10,000. That’s a pretty large number of desks for a small company to produce in a single week, so we should be safe. On the other hand, if that number is too small we’ll probably get an optimal solution right on the edge of our boundaries. If that happens we’ll just increase the boundaries and try again.


Now it’s time to put that all into action:


[5]> (defparameter *swarm-iterations* 200)


[6]> (defparameter *swarm-size* 1000)


[7]> (defparameter *swarm-output* (swarm-maximize #’company-profit ‘((0 10000) (0 10000))))


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

(200.04425 100.01073)


So it looks like the swarm thinks we should build 200 finished desks and 100 unfinished desks. And if we scroll down to the answer key portion of the worksheet that turns out to the right answer. Good job swarm!


Minimize Distances


Now let’s jump down to problem 3. A power station is being planned and they want to figure out the best place to put it so it can efficiently serve three different communities. Apparently this means they want to minimize the sum of the squares of the distances to each of the three communities which are positioned at (-4, 4) (5, 2) and (-1, -3).


Writing a function to calculate the sum of squares isn’t too hard, especially if we use the expt function to square things and the sqrt function to take square roots. Just remember that distance can be calculated by taking the square root of the square of the X and Y distances between two points and the following function should make perfect sense.


;Calculate the sum of squares of distances between a given point and the three points (-4, 4) (5, 2) and (-1, -3)
(defun sum-of-squared-distances (x y)
   (let ( (distance1 (sqrt (+ (expt (- x -4) 2) (expt (- y 4) 2))))
          (distance2 (sqrt (+ (expt (- x 5) 2) (expt (- y 2) 2))))
          (distance3 (sqrt (+ (expt (- x -1) 2) (expt (- y -3) 2)))))
      (+ (expt distance1 2) (expt distance2 2) (expt distance3 2))))


Time to choose our boundaries. Since we want to minimize the distance between the plant and the communities the power plant should logically be somewhere in the middle of the three points. So by looking at our points this means our x boundary needs to be between -4 and 5 and our y boundary needs to be between -3 and 4.


Time to let the swarm loose.


[29]> (defparameter *swarm-size* 25)


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


[31]> (defparameter *swarm-output* (swarm-minimize #’sum-of-squared-distances ‘((-4 5) (-3 4))))


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

(-7.074524E-4 1.0000945)


According to the swarm the best place for the power plant is around (0, 1), which matches up with the answer key. Another victory for the swarm!


A Problem With Extra Requirements


Now let’s go back to problem 2. This one turned out to be rather tricky.


At first it looks like a pretty simple. We have a package with length, width and depth (like all 3D objects). We want to maximize the volume. Just a simple 3 variable maximization, right?


Except that postal regulations require that the length and girth of the box have to add up to less than 108 inches. Or as the worksheet is happy to summarize: 2x + 2y + z <= 108.


This is a problem because our swarm is designed to make completely random guesses for x, y and z. We can give it some general guidelines like “x has to be between 0 and 10” but we can’t give it a complex constraint like “x plus y plus z needs to be less than 100”.


So at first it seems like our swarm just isn’t smart enough for this problem. But maybe there is a clever way around this issue. Take a look a this function:


;Calculates the volume of a package that has to have a combined length and girth of less than 108
(defun postal-package-volume (x y z)
   (if (> (+ (* 2 x) (* 2 y) z) 108)
       (* x y z)))


If the user tries to calculate the volume of a package that’s too big to mail we return -1 instead of the volume. Not only is this a good way to let a human know that there is a problem with their input, it also works great with our swarm. Since we want to maximize volume an “error” value of -1 will always be considered less optimal than even the worst of “acceptable” answers, all of which are positive.


In other words, instead of trying to prevent the swarm from making unacceptable guesses we just make sure that unacceptable guesses are always less optimal than acceptable guesses.


Time to see if it works. Our boundaries are based off the fact that a box can’t have negative length and that the definition of girth means that 54 is the biggest x and y values possible and that 108 is the biggest possible z.


[44]> (defparameter *swarm-size* 25)


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


[46]> (defparameter *swarm-output* (swarm-maximize #’postal-package-volume ‘((0 54) (0 54) (0 108))))


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

(17.743437 18.024296 36.464497)


If we look at the answer key the true maximum is (18, 18, 36), which is pretty close to the swarm’s guess. Looks like our workaround for the input constraints worked!


Conclusion And Extra Challenges


That’s it. We wrote a general swarm optimizer smart enough to ace a freshman calculus assignment. So while our swarm isn’t anywhere near being a professional quality artificial intelligence I think it’s more than good enough to be considered a successful “Let’s Program”.


Of course, I’m sure there are plenty of you out in the audience who don’t want to stop here. If you want to forge on ahead on your own here are a few sample projects you might want to consider tackling next:


  • Find more complicated optimization problems that require more than 3 variables. Does the swarm find the right answer? If not, fix it until it does.
  • Improve particle behavior by giving them memory of their personal best answer and having them adjust their velocity based on a combination of current velocity, swarm best and personal best.
  • Create multiple types of particles, such as scout particles that don’t care so much about the swarm best and random particles that bounce around problem space even when the rest of the swarm has settled on a possible best answer. This would be a great place to practice object oriented programming.


And with these final suggestions I bid you adieu. All that’s left is the index page. Thanks for following along!