Sequential and parallel implementations of the algorithm on the PARAM architecture
While a graph theoretical approach has been extensively tested on FAP in the
literature, a new approach is to use a randomized heuristic algorithm to
obtain good solutions in polynomial time. The ingenious ANTS heuristic,
adapted from the real life behavior of ants, is one such.
Each "artificial ant" is capable of finding a complete (but not
necessarily a good) solution
to the given combinatorial problem. When they work as a colony, the feedback
that each ant obtains from the other ants helps the colony to converge to
good solutions after a number of iterations. By rewarding good moves, we
strengthen their behavior to produce good solutions.
Last semester, I implemented the ANTS heuristic for FAP. I parallelized the execution of the algorithm, thereby achieving an increase in the speed of execution. The implementation was done using MPI programming on the PARAM 10000 supercomputer located in BITS, Pilani.
Go Back to Research Index.