Basics of Swarm Intelligence.

Rajat Maheshwari
Jul 25, 2017 · 6 min read

It’s all about ants,bees & birds (but in computer’s sense)

Credits-Techrepublic.com

Wikipedia says- Swarm intelligence (SI) is the collective behavior of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence. The expression was introduced by Gerardo Beni and Jing Wang in 1989, in the context of cellular robotic systems.[1].

But I think it’s just learning from animals, how they find their food. So that we can also apply those techniques to find our food (or solution of a problem).

I’ll discuss one very common technique- Ant colony optimisation (ACO), there’s one other good technique namely, Particle Swarm Optimization (PSO), which I will discuss some other time.

#ANT COLONY OPTIMIZATION

Basic Idea- Have you ever seen that ants usually walk in a disciplined manner, in a line or something like that and how they always find a shortest (maybe not always) path between their nest and food source. So the ACO’s idea is pretty much similar. When searching for food, ants initially explore the area surrounding their nest in a random manner. Actually they also leave a magic portion & Ants can also smell that magic portion. When ants choose their way, they tend to choose, in probability, paths marked with strong smell. As soon as an ant finds a food source, it carries some of it back to nest. During the return trip, the quantity of magic portion ant leaves depends on the quality and quantity of food. So tasty and lots of food made them leave more portion. And this portion will guide the other ants. And that magic portion is Pheromone.

Now imagine, two and more ants find that good food source, and now each of them returning back to their home, those who follows a shorter path will be able to make more trips from food source and nest, and hence the quantity of pheromone on these paths will also be greater than other paths and in some time more ants will follow the same path and leave more pheromone. After some time all ants will follow the same path.

Now, let’s break down the process in computer’s sense and see how a computer algorithm can solve such problem.

Prerequisites before solving a problem using ACO (If you’re not able to understand these, read the remaining part and then revisit this section) -

  • Problem solution can be obtained from a finite set C of solution components- i.e you should be able to divide the problem’s solution into smaller solutions, and then we’ll combine some of these smaller solutions to get our main solution.
  • We need to define a pheromone model, this will be a probability function which will help us decide which solution component to pick depending on the pheromone values of these components.
  • And an update function which will have the pheromone evaporation and deposition quantity as a mathematical function or some heuristics.

Problem- We’ll work on a real life problem Travelling Salesman Problem (TSP) , you’ll have some cities and the cost of travelling from each city to every other city, your aim is to find the minimum cost such that the salesman can visit every city and returned back to the one from which he started.

  1. Converting into Graph- First, we’ll convert this problem, so that we can apply ACO on it. Let just assume each city is a node of a graph, and we have weighted (cost) edges from each node to every other node. Our aim is to find a closed path in graph G such that weight of all edges in our path is minimum.
  2. Constructing solution components- As the final solution is a sum of different edge weights, we can divide our solution into components and can treat each edge as a solution component.
  3. Some initializations- We will start by giving our ants some random starting points(in this case nodes) and we also need to set some initial pheromone values to each of the solution components (or edges).
  4. Defining a pheromone model-

e(i,j)- edge between nodes i & j
tau(i,j)- pheromone value of edge between nodes i & j
T- memory of an ant (list of already visited nodes/cities)
p (e(i,j)) — probability of an ant to pick edge between nodes i & j

this is a more general form of the probability function, here we also take into account the attractiveness of a solution component (ci), but we don’t need this for our problem, so just leave it for now. You can refer the paper I’ve attached in the footnotes to know more about this.

5. Defining an update Function-

We’ll use this for evaporation of pheromone, it’s simply just decreasing the pheromone at edge (i,j) by rho factor. Now, one would ask why we even need to evaporate pheromone, we could just deposit pheromone on components which give us good solution because Pheromone evaporation is needed to avoid too rapid convergence of the algorithm towards a sub-optimal region, think about it.

After creating a solution by an ant, let solution components set of this solution be s, we’ll calculate the target value of our set s or you could say the cost in this case. If a set s gives us bad value of f(s) i,e, more cost, the change in tau(i,j) will be less and vice versa in other case. So all of this will favour solution components who are part of good solutions.

This again , is a general form of update function, left part is for evaporation (same, no changes), interesting thing is right part which is for deposition. Here one can use many techniques like AS update, IB update, BS update rule, Rank based AS, MAX-MIN and other kind of rules. Just for your curiosity I’ll describe IB update rule, for others you can refer the paper (link in footnotes). In IB update (or iteration best update) we deposit pheromones only on the solution components which are part of the best solution in an iteration. After all the ants in an iteration have created solutions, we pick the best one and update pheromones only on those solution components which are part of this solution (i.e why iteration best).

Pseudo Code-

Initialise Pheromone values and other constants

1 Initialise pheromone values and other constants2 While (max_iterations) do

2.1 assign random starting positions to ants

2.2 For each ant do
build tour using pheromone model and roulette based
selection (see code for reference)
End

2.3 Calculate cost of each tour
2.4 Update solution components using evaporation and deposit
function
2.5 If you shorter tour is found update bestEndreturn best
https://github.com/tommytrash00/ACO_for_tsp

I’ve pasted one solution I got using this technique on 20 cities, for 50 or 100 cities check my Github link.

For reference, and other techniques, use this review paper-antcolonyopt
For code check my Github

Hope you liked this basic tutorial, I tried not to get into the depths of the topic but at the same time, good enough information so that you can work on some real problem.
This is my first such blog, I’m planning to add more blogs/tutorials related to artificial intelligence or other related topics or anything I found interesting.

P.S.- You can also use this technique to achieve the same, there’s also a video.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade