8 Ant Colony Optimization Algorithm
This chapter covers
- Translating the biological foraging behavior of ant colonies into algorithm
- Calculating localized path probabilities using distance and pheromones
- Building the mandatory cycles of pheromone deposit and pheromone evaporation
In the previous chapter, we reviewed the 0/1 Knapsack algorithm and how dynamic programming guarantees an absolute global minimum. When you are dealing with a handful of capacity limits, dynamic programming shines. But what happens when your scale explodes? What happens when you aren't routing data between five nodes but fifty thousand? If we expect to have the perfect global minimum, then the algorithm will choke and the system will freeze. Recall the time and space complexity to fill a dynamic programming table is O(n.W), where n is the number of available items and W is the maximum capacity constant. With n = 10,000 and W = 100,000, resulting in 109 states. This will exhaust the server’s RAM, trigger Out-of-Memory crashes, and freeze the pipeline. In this chapter, we are going to learn to use biology, probability, and swarm intelligence to find the “good enough” answer in a fraction of time.