Solving Travelling Salesman Problem TSP

using Hill-climbing algorithm

Hill-climbing algorithm to solve TSP problem

Hill climbing is neither complete nor optimal. However, it gives a quick sub-optimal solution, which performed in a little amount of time and took constant memory space. Hill climbing, unlike A*, always provides a solution, which preferred in some application that requires a quick approximate (sub-optimal) solution.

Hill-climbing can be applied to solve TSP problem using the following steps:

Navigate through the permutations of the current state (current tour). One permutation is performed by changing the positions of two nodes in the current tour (or deleting two edges and adding two). The new and current tours are called 2-opt neighbors.
For each new tour, we compare the cost of the current and new tours. If the new tour has lower cost, we change the current tour by the new tour and loop again

Time and space complexities of hill-climbing algorithm

Hill climbing is neither complete nor optimal. Hill climbing performs local search that starts with a random initial solution, and then tries to find a better solution by gradually changing a single element. In travelling salesman problem TSP, we try to minimize the traveling distance by changing the positions of two nodes in the path. If the change produces a lower distance, the new solution becomes the current solution. We repeat until no further improvements can be found. Hill climbing has O(∞) time complexity because it may fail to reach the global maximum. However, it can give a good solution in reasonable time. The space complexity of Hill climbing is O(b), because it only move one single branch level, or b. Here in the TSP problem, the branching is equal to b= nC2=n(n-1)/2.

Pseudo-code

(MATLAB code can be downloaded from MATLAB File Exchange or GitHub)

Pseudo code

function solution = solveTSP_hillclimbing(TSPGraph) % returns a solution (path and cost)

curTour ← createInitialState(TSPGraph) % create an initial state (initial tour).

do loop

% get the next local solution

newTour ← getNextSolution(TSPGraph, curTour)

if the current solution does not change, return the current tour as a potential maxima

% (minimum cost).

if(newState.distance == curState.distance) return the curState as solution

curTour ← newTour

function solution = getNextSolution (TSPGraph, curTour) % return the next best local

do loop for all the permutations of the current state (current tour)

% get next nearest tour by changing the positions of two nodes in the current tour

% (or deleting two edges and adding two).

% The new and current tours are called 2-opt neighbours.

newTour ← Get next nearest tour

% compare the cost of the current and new tours. If the new tour has lower cost,

% then we change the current tour by the new tour.

if( newTour.distance < curTour.distance ) then

curTour ← newTour

return curTour % return the current tour as solution

Experiments results

Result of running Hill-climbing algorithm for att48 and a280 datasets

Fig.9 shows the convergence of TSP tour cost for att48 and a280 datasets from initial solution to the minimum cost for each iteration using Hill-climbing algorithm. Att48 dataset has 48 nodes, so it has branching factor b= 48C2 = 1128. This means that the objective function will search for the lowest cost between these 1128 permutations. In this experiment, hill climbing took 166 seconds and 5 iterations to give a solution for Att48 dataset with traveling distance equals to 15335. This solution is not optimal, the optimal solution equals 10628^[2], however, the search algorithm give us a fast solution which performed in little amount of time and took constant memory space (b=1128). For a280 dataset, which has branching factor b=280C2 = 39060, the objective function will search for the lowest cost between 39060 permutations for each iteration. This may take more time but the space will still be constant. If we need very fast solution, we can interrupt the search process according to our time requirements and took the best solution so far. In this experiment, we interrupted the search process for a280 database after 2 hour, and the result of convergence is shown in fig.9 b.

Matlab code

Matlab code:

% read the TSP graph from xml file and convert it to matlab graph object

[G, Gnodes] = loadTSPGraph("att48_.xml");

%[G, Gnodes] = loadTSPGraph("a280_.xml");

%[G, Gnodes] = loadTSPGraph("data2.xml");

tic

% create an initial state (initial tour)

curState = createInitialState(G);

% navigate through the permutations of the current state (current tour).

% one permutation is performed by changing the positions of two nodes

% in the current tour (or deleting two edges and adding two).

% The new and current tours are called 2-opt neighbours.

% For each new tour, we compare the cost of the current and new tours.

% If the new tour has lower cost, we change the current tour by the new tour and loop again

% disp( [curState.node , sum(curState.distance)]);

iterations = 0;

while(true)

disp( [num2str(iterations) , ' ', num2str(sum(curState.distance))]);

newState = getNextSolution(G, curState);

if(newState.distance == curState.distance)

break;

end

curState = newState;

iterations = iterations + 1;

end

toc

function curState = getNextSolution(G, curState)

iterations = 1;

for p1 = 1 : size(curState.node,2)-1

for p2 = p1+1 : size(curState.node,2)

newTour = curState.node;

tempNode = newTour(p1);

newTour(p1)= curState.node(p2);

newTour(p2)= tempNode;

newState = getTourState(G, newTour');

if( sum(newState.distance) < sum(curState.distance) )

curState = newState;

end

iterations = iterations + 1;

end

function initState = createInitialState(G)

tour = table2cell(G.Nodes);

initState = getTourState(G, tour);

end

function state = getTourState(G, tour)

for idx=1 : size(tour,1)

curNode = tour(idx);

if(idx == size(tour,1))

nextNode = cell2mat(tour(1));

else

nextNode = cell2mat(tour(idx+1));

end

state.node(idx) = curNode;

state.distance(idx) = G.Edges.Weight(findedge(G, curNode ,nextNode));

end

function [G, Gnodes]= loadTSPGraph(fileName)

% read the TSP graph from xml file and convert it to matlab structure

tsp = xml2struct(fileName);

% convert graph structure to graph matrix

nodeNo = size(tsp.graph.vertex, 2);

graphMat = zeros(nodeNo, nodeNo);

names = zeros(nodeNo,1);

for v=1 : nodeNo

names(v) = v;

vertex = tsp.graph.vertex(v);

diag = 0;

for e=1 : nodeNo-1

edge = vertex{1}.edge(e);

cost = str2double(edge{1}.Attributes.cost);

if(v==e)

diag = 1;

end

graphMat(v, e+diag) = cost;

end

% convert graph matrix to matlab graph object

Gnodes = cellstr(string(names));

G = graph(graphMat, Gnodes);

end

[1] S. Rassel and P. Norwig, “Artificial intelligence: a modern approach (AIMA).” Moscow: Wiliams, 2007.

[2] “Symmetric TSPs.” [Online]. Available: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html. [Accessed: 08-Apr-2020].

Contact
For any questions, feel free to contact:Hamdi Altaheri: haltaheri@ksu.edu.sa