In this week's mini episode, Linhda and Kyle discuss Ant Colony Optimization - a numerical / stochastic optimization technique which models its search after the process ants employ in using random walks to find a goal (food) and then leaving a pheremone trail in their walk back to the nest. We even find some way of relating the city of San Francisco and running a restaurant into the discussion.
Data Skeptic
[MINI] Ant Colony Optimization
(upbeat music) - Welcome back to another edition of the Data Skeptic Podcast mini episodes. I'm here as always with my wife and co-host Linda. - Hello. - Thanks again for joining me. Our topic today is called Ant Colony Optimization. Do you know why I picked this topic? - Well, I'm not psychic, but I just wanted to tell the audience that we have been having an ant problem because it's been so hot lately. - I think you've been having it. I just happen to live here also. - What's the difference? (laughing) - Yeah, well, we put out some ant traps and the weather has cooled off a little bit. So I don't know what it's, I'm not an ant specialist. - Me either, but I do know one thing about a technique that was modeled off of the behavior of ants that we're gonna talk about. An ant colony optimization is a search and optimization technique. So before we can talk about it directly, I might have to define those things because even though people think that they intuitively know what search and optimization are, most people generally don't actually know what these things are. So in search and optimization, or as I'll often say numeric optimization, the problem consists of you having some large space of possible solutions or candidates or things like that. And you need to find, and you can't exhaustively go through everyone. So you need to find a way of looking through the space of possible solutions to find your answer in an easy and algorithmically driven way. So I thought a fun example might be to think about our sister city to the north San Francisco. To my understanding, it's made of like seven hills or something like that. Have you heard that? No, I'm not into geography. So it's a miracle. I know where it is. Much less seven hills. I know there are hills there. Sure. It's quite hilly. So even if I'm wrong about seven, although I think I'm right, we know it's a very hilly city. So what if I told you that I would like you to find the highest point in the whole city of San Francisco? How might you go about finding it? I don't know. I would Google highest point in San Francisco. So what if you were, had no cell reception at the time? Was I physically in San Francisco? Yes, you're physically in San Francisco. Ah, I guess I could just walk around and find the highest point and go up to it and then take a look around. There are some towers there that I forgot the name, but you have a pretty good view from some angles. Yeah, so you might say you could, from wherever you are, walk in whatever is the uphill direction until you can no longer go more uphill, which would mean you're at the top of the hill. And then you might look around and see are you at the top of the tallest hill? That is sort of an approach. Once you get through that process of arriving at the top of the hill, that is a point of optimization because you can get no higher. You are at the highest point around you. But we call that a local optima because it's not necessarily the global optima, which would be the most highest point in the whole city. But it is a highest point in your local little area. How do you define that in statistics? It's not actually a statistical principle per se. It's more of a numerical optimization principle or like I'm sure the operations research community would try and take claim for this because it's something they work with a lot. But basically, if you're in a position, and this is a crude definition, I didn't look this one up, but if you're in a place where the points around you are no better than where you currently are, then that's a local optima, such as the top of a hill. If you're at the very top of a hill, any direction you go is down. So if your goal is to be high, you have no place to go but where you are. Unless there's another hill somewhere else where you have to go down your hill and up the other hill. Maybe that hill itself is much taller than the one you're on. But for where you are locally, it's a local optima. - So it sounds relative. - Yeah, it's relative. In the case of San Francisco, there's a nice property in that it's essentially two-dimensional because even though we live in a 3D world, there's pretty much just one ground we walk on. So you get to the top of a hill, and then it also has a nice property that you can look around you and see, hey, do I see a taller point? And since San Francisco is not such a huge city, you might see, okay, I'm at the top of this hill, but I see a hill two miles south of here that's even taller. So you can go to that hill. So you have a luxury in your optimization problem. Of one, it's two-dimensional so you can easily visualize it. And two, you can see all the other points, presumably or relatively well from where you stand. But imagine this problem if it was in more than two-dimensional space. - So an example I like to give people sometimes is, let's say you owned a restaurant. Now, how many decisions do you think a restaurant owner has to make to optimize their business? - From beginning to end, to run a business? - Yeah. - To run a business or set it up or everything? - You have a business going. There is a restaurant, you have a menu and customers come in and eat your food, and the Board of Health has given you a passable grade. But you would like to optimize your business, which presumably for your domain means generating more revenue. - Right, so if they're gonna maximize revenue, there's a few different ways you could make the place smaller. - So probably lower rent. - Yeah. - But less tables. - And then you'd have less staff. - Less staff. - So I mean, if that's a sweet spot, I don't know if that's one direction. You could potentially expand, that could be another model. You'd have franchises, that's another model. - You could. - You could cut the menu. You could increase the menu. I mean, it really just depends. - Yeah, you're right, it depends. And you picked a good word. What did you say, a sweet spot. Sweet spot is a great phrase for understanding optimization a little bit. Every one of those points that that restaurant tour might have to think about is another dimension that you would have to explore. And since there are probably countless more beyond the ones we listed, it's really hard to decide how to optimize that business. And a lot of restaurants might be in local optimas already. For example, let's say you owned a Burger King. I don't think you can double your revenue in one year. You know, you maybe make little small tweaks and improvements and you get higher up your hill, but unless you wanna reinvent the company completely, you're probably just making small marginal gains from where you are. And that's another reason I like restaurants is my example, 'cause if we think about those hills that exist in multi-dimensional space, there are lots of different sweet spots, right? Like fast food versus high-end restaurant with Michelin stars. These are both restaurants, but they're both very different solutions to the same optimization problem. So how do you solve an optimization problem? Well, that's actually an interesting thing because not only is it an open area of research, but we have this nice result called the no free lunch theorem, which I won't get into here because it would go on a little bit too long. But basically, no free lunch theorem says that there isn't a single optimization procedure that dominates all others. So it won't be possible that some really bright guy one day comes out or girl and says, "Hey, I've got this great new optimization idea "and it beats every other type of optimization. "It beats gradient descent. "It beats lasso methods. "It beats ant colony optimizations the best. "That can't happen." So depending on your domain, there's a good reason to try and explore different optimization techniques. And one of them is ant colony optimization. So ants, the problem they're generally trying to solve is to find food and then find the shortest path between the food and the hive or the nest or whatever you call it. Do you know much about how the ants do it? How do they find the food? They sniff it. Sure, but they can't smell food from very far away. In fact, I'm not even sure how if their sense of smell is all that great. I think it's kind of weak. Really? Well then I thought they followed like pheromone trails. They do. So essentially what ants do is they wander about randomly until they find food and then they start releasing pheromones and trying to walk home. So along the way then, they leave a trail from the food to the home. Now if another ant who's wandering about randomly looking for food comes upon a pheromone trail, then they say, hey, I probably want to follow this trail. They don't do it for certain, but more likely than not, they will follow it. In which case, they will either arrive home or they will arrive at the food. And if they arrive at the food, they will take some and then start leaving their own pheromone trail. So it will kind of reinforce the other pheromone trail. And then of course it evaporates with time, but if more and more ants are following it, it gets stronger and stronger. And suddenly, all those ants that used to be wandering about randomly are now walking in a straight line, which we often can see, right? Yeah, it depends how many ants deep there are. How many ants deep before you get bothered? I don't know. Well, the problem I want to explain to the listeners is that sometimes we wipe up or kill or whatever to the ants to get rid of them. And then I swear, if there's a lot of them, they'll come back in like two minutes. Like it doesn't take them long to recover. I mean, other times it takes some days to get back and find the same trail. Well, that's actually a great example because probably what we failed to do was really disrupt their pheromone trails. So the first ant that found something in the house, maybe they left a trail back to the nest that wasn't a very good trail. It wandered about, it was inefficient. But then some other ant that comes along and starts following their trail might take a shortcut or wander off the trail but still be leaving pheromones. And over time, it'll converge to something akin to a straight path between the food and the nest, the shortest path. But yet there might also be these ancillary pheromone trails around it from earlier treks. So if we wipe up the main line, but there's some other pheromone trail, they might find that one again. And then over time, re-optimized to the shortest path. Or perhaps they follow the pheromone trail up until the point we cut it and then they start wandering randomly. So most of them won't find the food but as soon as one does or picks up on the other trail, they'll get to the food and then they just takes one ant to leave a new pheromone trail back to the nest. Others find that, others follow it and it gets stronger. So this is kind of a really efficient thing that evolution has given them. It's found this interesting way for them to solve this problem. And computer scientists, or maybe it was operations researchers, but smart people came along and said, "Hey, perhaps we can mimic nature and do this algorithmically." So. - Oh, is it organic? - No, it is not organic. - You're mimicking nature. - So nature, including ants, are made of carbon and anything made of carbon is organic. So, yes, those are organic but the computer simulation is entirely digital. In the computer then, you have this big search space and you have some goal state and you simulate the random movement of ants and if ants encounter food, they want to find their way home and they'll leave a trail. And if ants encounter another ant's trail, they have some likelihood but not 100% of following it. And this technique modeling nature has proven to be actually pretty effective in solving some search and optimization problems. - So the solution is to wander randomly? - For a certain number of ants, a large enough base colony to search randomly, look anywhere and everywhere for what they're after. In the real world, that happens to be food but maybe in our restaurant application, it's looking for an estimated high revenue point. Like the right balance of ingredients sourcing in number of customers per hour and this sort of thing. So as soon as one of these simulated ants finds a solution, it starts to leave a trail of how to get there. And maybe some other ant somewhere else in the search space has found a different solution. So there might be two trails but over time, the ants will follow the trails that, or one expects that there's some convergence to a pretty straight and optimized path from the source, the hive, to the best solutions that can be found. And this is a novel approach that models an aspect of nature in a computer in order to solve what are challenging multi-dimensional numerical optimization problems. - Great, it's an organic solution. - I really wish you wouldn't say it's organic. (laughs) - For those of you who don't know, Kyle does not like organic, the phrase. - So knowing this, do you find yourself more sympathetic to the ants and the wonderful display of optimization that they've performed in our kitchen? - So is it proven that they're wandering randomly? - Yes, I mean, I'm not an entomologist but I'm pretty confident that their initial movements are effectively random. But you didn't answer my question. - What was your question? - Now understanding this very impressive feat of numerical optimization that they were performing for us in our kitchen, do you feel more sympathetic to their presence? - No. - Not even a little bit? - I'm just shocked that they find the food at all. - Yeah. But you should be shocked anymore, I just told you how. - I don't know, I wanna witness it. - Okay, well go open that window and let's leave a cupcake on the counter. And we can put one of the security cameras up to take time series over it. - All right. I don't think they like cupcakes but we can try. (gentle music) (gentle music) [BLANK_AUDIO]