swarm optimization


Example The travelling salesman problem (TSP) ...

Image via Wikipedia

The conundrum of travelling salesman problem involves finding the shortest route that allows a travelling salesman to call at all the locations he has to visit. Computers solve the problem by comparing the length of all possible routes and choosing the one that is shortest.

What the bees do is to apply simple pattern matching: is this route shorter than the previous one? if so, then use this route. Ants do this too. They have effective “smell highways”. They smell the road ahead of them and determine how many other ants have travelled this road as well. Occassionally an ant will branch off, but if it finds food it will create a new route. Works brilliantly, except when they’re going in a circle. Also known as a death spiral.

bees do not use smell for this. They use the waggle dance to tell other bees in the hive the direction, distance and the quality of the food source. Further they have three kinds of bees, “elites” which represent the best sources found to which “onlookers” are sent to optimize the solution and “scouts” which are sent to random locations in case the team gets stuck in a local minimum.

Solving the Traveling Salesman Problem would mean having a generalized method (mathematical or not) that results in the shortest-path between the nodes. Bees have been found to efficiently find a good approximation of the solution, something that computers are fully capable of doing. Finding the shortest path every time would be extraordinary.

As far back as 1986 there were claims that bees have cognitive maps and since mice use these maps to create more efficient routes to food sources when tested in a lab setting (usually radial arm mazes) it is not such a surprise that bees do the same. It would be interesting, though, to measure whether they can differentiate and prioritize food sources. When “solving the travelling salesman problem” do they weigh the value of each flower equally or do they maximize their route based on space and value?

I learn about TSP back in college, it’s a very interesting subject. covering of how to visit all the node in a city with the least possible path, and also it has became such an extensive active area of research till now.

Advertisements

2 comments on “swarm optimization

  1. nn says:

    ni sih mata kuliah alin kali y..

  2. Jacobian says:

    yup tepat sekali.lebih tepatnya di matdis. 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s