Aug 30, 2011

Ant Colony Optimization for TSP Problems

Code can be found under (https://github.com/thomasjungblut/antcolonyopt)

Hi there,

I recently focused on playing around with ant colony AI (artificial intelligence) methods, as part of my second semester undergraduation project in Software Engineering.

Wikipedia's definition for Ant Colony Optimization is the following:
In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs.
Unlike previous posts, it is a multithreaded solution which runs best on a single machine and not in a cluster and this post is about TSP (Traveling Salesman Problem) and not about finding shortest paths in a graph.

The Input

At first, we have to decide which input we take. In my case, this task was a university assignment so I have to use the given one. It is the Berlin52 problem which should be solved with the less costly route along the 52 best known / famous places in Berlin.
You can download an euclidian 2D coordinate version of it here. Just look for the "berlin52.tsp.gz" file. There is also an already calculated optimal solution here.

Plotting the file is going to show a cool roundtrip:

GnuPlot of the Berlin 52 Tour


The file content looks quite like this:
1 565.0 575.0
2 25.0 185.0
3 345.0 750.0
4 945.0 685.0
On the leftmost side is the ID of the vertex, in the middle is the x-coordinate and on the rightmost side is the y-coordinate in the euclidian plane.

The Algorithm

This algorithm is a mimicry of the real-life behaviour of ants. As you might know, Ants are quite smart in finding their way between their colony and their food source. A lot of workers are walking through the proximate environment and if they find some food, they leave a pheromone trail.
Some of the other ants are still searching for other paths, but the most of them are following the pheromone trail- making this path even more attractive. But over time the pherome trail is starting to decay / evaporate, so it is losing its attractiveness. Due to the time component, a long way has a very low density of the pheromone, because the pherome trail along the longer path is evaporating faster. Thus a very short path has a higher density of pheromones and is more attractive to the workers converging onto an approximately optimal path for our TSP problem.

For the problem, we are dropping ants on random vertices in our graph. Each ant is going to evaluate the next best destination vertex based on this following formula:

Wikipedia.org
It is about the probabiliy "p" for an ant called "k" to move to the vertex described by "x" and "y".
The variable "Tau" is the amount of pheromone deposited on the edge between "xy". It gets raised by "alpha" which is a heuristic parameter describing how greedy the algorithm is in finding its path across the graph. This is going to be multiplied by our apriori knowledge of how "good" the edge is. In our case this is the inverted distance (1 / distance) between x and y. This gets raised by "beta" which is also a heuristic parameter, which describes how fast the ants are going to converge to a steady solution. To get a transition probability to a vertex, each gets divided by the sum of the numerator over all possible left destination vertices.

The next equation is about adjusting the pheromone matrix, which is described by the following formula:
Wikipedia.org
"Tau" is the amount of absolute pheromone which gets deposited for worker "k" on the "xy" edge. "Rho" is a factor between 0-1 which represents the decay of the pheromone. This gets multiplied by the current amount of pheromone deposited and we just add updated new pheromone to it (which is the delta "Tau"). Delta "Tau" is an equatation too:

Wikipedia.org
It is just "Q" by the accumulated distance of the path so far.

Finish! That is all we need to start the implementation!

The whole thing works like this:
  1. Initialize the best distance to infinity
  2. Choose a random vertex in the graph where to plant your ant
  3. Let the ant work their best paths using the formulas from above
    1. Let the ant update the pheromones on our graph
  4. If the worker returned with a new best distance update our currently best distance
  5. Start from 2. until we found our best path or we have reached our maximum amount of workers.
  6. Output the best distance
The single worker will now return with a path which he has taken and with a corresponding distance. Now you can decide if you are confident with the result, or going to let the worker calculate more of them.

So let's see how we can multithread this.

How to Multithread

In this case, multithreading is very easy. Each worker unit (in my repository called "Agent") is a single thread. In Java we have a cool thread pool construct called ExecutorService and a completion service which tells us when workers finished.

We are submitting a few workers for to the pool, they work on the same resources and once completed we get a reponse of the completion service.

Woot? Shared resources? Yes we need some sort of synchronization. In our case when writing to the pheromone matrix. In my latest implementation I used lock-free updates using Guava's AtomicDouble.

The whole algorithm is not going to change, we are just working in parallel.

The Result

After a lot of parameter testing you can find a very good solution:

Console output of my algorithm, finding a very close solution to the optimal distance for Berlin52

Parameter Testing

Because there are a hell lot of parameters (5) in there, we have to write an testing utility which calculates the best parameters for our problem (aka GridSearch).

We only care about the distance to the optimal solution:
In the grid search we only want to keep the lowest possible mean distance to the optimal solution (measured over multiple repetitions) and a very low variance.

For Berlin52, the best parameters using 200k agents I found are:

Alpha = 0.1
Beta = 9
Q = 1e-4
P = 0.8

So feel free to check out the code in the repository and let it run.
And please feel free to use this as a hint for your own implementation, or even improve it via a pull request.

Thanks for your interest and have fun :-)
Bye!

Repository https://github.com/thomasjungblut/antcolonyopt

35 comments:

  1. can u give me this program, i very necessity

    ReplyDelete
  2. Maybe you should read a bit more carefully and find the link to the code-project? :P

    ReplyDelete
  3. i see this link http://code.google.com/p/antcolonyopt/ but i can't see your program, in there only descriptions your program, I am sorry...

    ReplyDelete
  4. Hi, Thomas!
    One thing: we have an already calculated optimal solution (you gave a link), and if we calculate we will have the value 7544.36.. something like you obtained! Ok, but there http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html the optimal value for berlin52 is 7542. What do you think? Why it is 7542 (instead of 7544.36)?!! Is it a round-off error?

    ReplyDelete
  5. Hi cool that it works :D
    I'm pretty sure that it is somewhere in between a round-off error and a typo from the university of heidelberg.

    You can check by using their TSPLIB and input the berlin52 dataset and see whether they find the same solution with a lower distance or a better solution.

    ReplyDelete
  6. I'm not sure it's a typo, because their optimal values of lengths (from TSPLIB) for all datasets just are integer! (its strange,no?) I checked by using their TSPLIB and input the berlin52 dataset in my prog (not yours:)) and I obtained the value 7544.36... It means I used their optimal tour and calculated the length in my prog for this optimal tour and obtained just 7544.36 (instead of 7542). It's a problem for me, because there are the same problems for another datasets and sometimes I have a really big difference.

    ReplyDelete
  7. Ah I see. Yes it seems that they aren't using floating point arithmetics.

    ReplyDelete
  8. It seems yes :) And about your ALPHA. One of the main defect of ACO is dependence of parameters which are determined just in an experiments. Sometimes reseaches use the negative value of ALPHA like you. I set
    ALPHA = 0.1
    BETA = 2
    Q = 1.0
    P = 0.1
    It works perfect for berlin52 as well, but not for all instances from TSPLIB

    ReplyDelete
  9. sir,
    i am an student.. i am applying ACO for all pair shortest path problem in java... i have made code for this... but its processing time is too large.. can you help me...can u give me guideline.
    my email:meenakshi.miet@gmail.com
    name: meenakshi

    ReplyDelete
  10. Hi,

    We are trying to parallelize ACO over Hadoop MapReduce but can't find a way to share the pheromone matrix among the mappers. How can we do that? is it possible?

    ReplyDelete
  11. Hi cool stuff, it is depending how large it is. But since it needs continous updates NoSQL might be your solution, Hbase for example.

    HBase is a column oriented "database" which can express matrices very well, especially sparse matrices.

    Can I point you to Apache Hama? It provides messaging capabilities between the tasks and if you have enough memory to store your matrix, you can split it among the tasks.
    Maybe it better suits your needs, I would help you with that.
    If you're interested in Hama, then come to the mailing list and I will guide you.

    Thanks for reading ;)

    ReplyDelete
  12. Hey,
    i don't get how can the ant moveback if all the neighboor nodes are already visited.
    e.g if sum == 0 even if there is some nodes that are not visited yet (in other part of the grap).

    line 52-53 in Agent.java

    if (sum == 0.0d)
    return danglingUnvisited;
    For me this will always return a node that have no direct link with our current node (y).

    ReplyDelete
  13. The Ant never walks back. A single agent is considered to walk a single weighted round trip by visiting all nodes. If no nodes are to visit anymore, it has obviously finished a roundtrip so the sum will remain 0.0, a similar check would be if all booleans in visited are true, which takes linear time instead of constant time to check the sum.

    In your case, you seem to have a graph where not every node is connected with each other (a not complete graph). This is not supported by my work.

    ReplyDelete
  14. please check the link of source code it's not working

    ReplyDelete
  15. The link is still valid:

    http://code.google.com/p/antcolonyopt/

    ReplyDelete
  16. please i want to know
    the final result is in mile or Kilo meter??
    and
    how i can calculate the number of iteration for each trip example:
    data set brlin52 has 5307 iteration to complete
    thanks a lot....

    ReplyDelete
  17. Hey Thomas I have made a code to solve TSP using a single ant implementation of ACO but i am not pretty sure whether I have done it keeping it true to the Algorithm.There are parts i am a bit confused regarding this.The code is at http://code.google.com/p/simple-aco-pso/source/browse/ under the head "simpleaco". Please review it and send me a note please.
    Thanking you,
    Sourav Banik
    (contactsouravbanik@gmail.com)

    ReplyDelete
  18. hi sir , i m working on ant colony optimization to solve travelling salesman problem.. the source code u hav provided is no availbale in that link ..can u provide the valid link with source code ...

    ReplyDelete
  19. Why? It is there:

    https://code.google.com/p/antcolonyopt/source/browse/#svn%2Ftrunk%2Fantcolony

    ReplyDelete
  20. tanks sir ..actully its my project on which m working.. its a great help..

    ReplyDelete
  21. Hello Thomas Jungblut.Your article is very good. I'm learning about Ant Colony Optization. Can you share me the program luongthiha.89 @ gmail.com

    ReplyDelete
  22. Helo sir this is basavaraju. I am working on Image processing ...Here in this iam using bit-sequential method to store the image then i am generating peano-count tree to represent class labels for any new images so that i can identify the portions of image quickly...like hill area, water area etc.then i have to use fuzzy logic to identity the new images so that i will get better performance for the classification of any image so please give me java code for this or help that where i can get it. or send me mat lab code.

    ReplyDelete
  23. Hi thomas, i have to contact with you with a big doubt. i am in the field of image watermarking, now i have to add ant colony optimization process with my project to find the optimal parameter values for my project, whether it is possible,. if it is how the process can be, please reply me thomas, it is very crucial time for me, answer me as soon as possible.

    ReplyDelete
  24. hi bro.
    how can I use ACO for a problem of minimizing an objective function with constrains.
    like min C=f(p1,p2,....pn)
    and U know what, p1 - pn are not discrete .
    I don't know what is the colony or edge hear?
    how to move ants & ....
    totally , I'm confused.
    If u could , mail me some help.
    tnx

    fereshte_sabahi@yahoo.com

    ReplyDelete
  25. sir,
    In solution writer you have given integer values for array initialization why? can we give float or double values and what will be functions to use the array elements of double type

    ReplyDelete
  26. in continuation of the previous question what could be used for float or double type
    for (int j = 0; j < arr.length; j++) { int i = arr[j];
    writer.write(records.get(i).x + " " + records.get(i).y + "\n");
    }
    writer.write(records.get(arr[0]).x + " " + records.get(arr[0]).y + "\n");

    ReplyDelete
  27. Where did I use integer values? For the coordinates, double values are used. This is just a conversion class from a record index mapping (because the algorithm uses indices instead of the real coordinates) to their real coordinates, so you can make plots like in the screenshot above.

    ReplyDelete
  28. sir
    in solution writer the array of integers is declared as
    int[] arr = new int[] { 29, 22, 19, 49, 28, 15, 45, 43, 33, 34, 35, 38, 39, 37, 36, 47, 23, 4, 14, 5, 3, 24, 11, 27, 26, 25, 46, 13, 12, 51, 10, 50, 32, 42, 9, 8, 7, 40, 18,44, 31, 48, 0, 21, 30, 17, 2, 16, 20, 41, 6, 1 };
    what do these values indicate? can we give floating or double values. and how can we access the floating point array.

    ReplyDelete
  29. Thanks for the nice and efficient code. However, your solutions may end up violating the convex hull constraint. Best way to check is by generating an ordered grid of cities. This way you can tell how far a solution is from the (known) optimal solution. A solution which is not a convex hull or doesn't put the starting and ending ends of the tour in a nearest neighbor proximity should be penalized -- it's not a proper Hamiltonian cycle. The shortest path is a subset of 'legal' solutions! It gets tough for your ACO to solve a 9x9 layout... but an order of magnitude faster than a GA. Also, prime candidate for GPU programming which with a GA suffers from saturation of the population size. Cheers!

    ReplyDelete
  30. Hi ! Great code really enjoyed reading it :D Just one question, where is the main method please as I can not see the output of the screenshot you have above ? Thanks and awaiting your reply :)

    ReplyDelete
    Replies
    1. Right there:
      https://github.com/thomasjungblut/antcolonyopt/blob/master/src/de/jungblut/antcolony/AntColonyOptimization.java#L104

      Delete
  31. hello Thomas, I m researching on Load balancing using ACO Algorithm and i used cloudsim in java with eclipse for implmentation.so i need to ask you,is your code ruon on eclipse. and tell me about the package which u include in code. plz its necessary for me.
    i need your help sharmaayushi508@gmail.com

    ReplyDelete