TSP problem is one of the most famous hard combinatorial optimization problems. It belongs to the class of NP-hard optimization problems. This means that no polynomial time algorithm is known to guarantee its global optimal solution. Consider a salesman who has to visit cities. The TSP problem consists of finding the shortest tour through all the cities such that no city is visited twice and the salesman returns back to the starting city at the end of the tour.
'f' is the cost function and 'd' is the distance between two nodes and p(i) is an array of paths by salesman
f = Σd(p(i))
delta = f1 -f2
SA algorithm is commonly said to be the oldest among the metaheuristics and surely one of the few algorithms that have explicit strategies to avoid local minima. The origins of SA are in statistical mechanics and it was first presented for combinatorial optimization problems. The fundamental idea is to accept moves resulting in solutions of worse quality than the current solution in order to escape from local minima. The probability of accepting such a move is decreased during the search through parameter temperature
Here 'p' is the probability of the move and 'T' is our temperature.
p = 1/(1 + e^(delta(f)/T))
we used the Greedy hybrid operator to move to the neighbouring node. We first choose randomly to index 'i' & 'j' and operator three operations viz inverse insert and swap and calculated the 'p' for each possible path and if it was greater than randomly generated probability 'r' we moved forward else we continued.
- Inverse operator : It reverses the subpath from path from indexes 'i' and 'j'.
- Insert operator : It cycles down the subpath from indexes 'i' and 'j'.
- swap operator : It swapes the path[i] and path[j] elements.
we used the classical geometric cooling schedule for simulated temperature cooling.
- Clone the above repo by
$ git clone https://github.com/abhijeet2096/tsp_sa - Spawn terminal in cloned folder.
- Compile using
$ make. - Run above program as
$ ./tsp < ./TestCases/euc_100 - Check stdout for output !
Results are displayed below in table.
| TestCase | Distance |
|---|---|
| euc_100 | 1497.217651 |
| euc_250 | 2516.678467 |
| euc_500 | 3554.416260 |
| noneuc_100 | 5216.49072 |
| noneuc_250 | 12799.088867 |
| noneuc_500 | 25380.828125 |
The Assignment's aim was to solve Travelling salesman problem. This Assignment was under Prof. Deepak Khemani.
- Github: http://github.com/abhijeet2096
- Email: sharma.abhijeet2096@gmail.com
- Mobile: +91-8629015433
- Github: http://github.com/swapsha96
- Email: swap.sha96@gmail.com
- Mobile: +91-8629015435