## The Traveling Salesman Problem Using Quantum Inspired Annealing In C#

The Traveling Salesman Problem (TSP) is a standard combinatorial optimization problem. The goal is to find the best route that visits all cities, where best route usually means shortest distance.

Simulated annealing is one way to solve TSP. Quantum inspired annealing adds a twist called tunneling to simulated annealing. Quantum inspired annealing doesn’t use quantum computing — the term “quantum inspired” just means an idea loosely (very loosely) borrowed from quantum behavior.

I implemented quantum inspired annealing for TSP using the Python language for an article in Visual Studio Magazine. Here is a C# implementation of the VSM article program.

After I finished my undergrad school days at U.C. Irvine, and before I did my graduate school work, I was lucky to work as an assistant cruise director on the Royal Viking Line (now defunct). I got to visit many fascinating cities, without regards to optimizing the distance traveled. Three especially memorable cities were Cairo, Panama City, and Venice. Another memorable city I visited was Sydney, Australia — because I got briefly thrown in jail for not having my travel documents in order.

Demo C# code. Replace “lt” and “gt” with symbols — my blogging editor chokes on these symbols.

```using System;
namespace TSP_QuantumAnnealing
{
class TSP_QuantumProgram
{
static void Main(string[] args)
{
Console.WriteLine("\nBegin TSP simulated annealing C# ");

int nCities = 40;
// 40! = 815,915,283,247,897,734,345,611,269,596,
//        115,894,272,000,000,000
Console.WriteLine("\nSetting num_cities = " + nCities);
Console.WriteLine("\nOptimal solution is 0, 1, 2, . . " +
(nCities - 1));
Console.WriteLine("Optimal soln has total distance = " +
(nCities - 1));
Random rnd = new Random(41);
int maxIter = 20000;
double startTemperature = 100000.0;
double alpha = 0.9990;
double pctTunnel = 0.10;

Console.WriteLine("\nSettings: ");
Console.WriteLine("max_iter = " + maxIter);
Console.WriteLine("start_temperature = " +
startTemperature.ToString("F1"));
Console.WriteLine("alpha = " + alpha.ToString("F4"));
Console.WriteLine("pct_tunnel = " + pctTunnel.ToString("F2"));

Console.WriteLine("\nStarting solve() ");
int[] soln = Solve(nCities, rnd, maxIter,
startTemperature, alpha, pctTunnel);
Console.WriteLine("Finished solve() ");

Console.WriteLine("\nBest solution found: ");
ShowArray(soln);
double dist = TotalDist(soln);
Console.WriteLine("\nTotal distance = " +
dist.ToString("F1"));

Console.WriteLine("\nEnd demo ");
} // Main

static double TotalDist(int[] route)
{
double d = 0.0;  // total distance between cities
int n = route.Length;
for (int i = 0; i "lt" n - 1; ++i)
{
if (route[i] "lt" route[i + 1])
d += (route[i + 1] - route[i]) * 1.0;
else
d += (route[i] - route[i + 1]) * 1.5;
}
return d;
}

static double Error(int[] route)
{
int n = route.Length;
double d = TotalDist(route);
double minDist = n - 1;
return d - minDist;
}

static int[] Adjacent(int[] route, int numSwaps, Random rnd)
{
int n = route.Length;
int[] result = (int[])route.Clone();  // shallow is OK
for (int ns = 0; ns "lt" numSwaps; ++ns)
{
int i = rnd.Next(0, n); int j = rnd.Next(0, n);
int tmp = result[i];
result[i] = result[j]; result[j] = tmp;
}
return result;
}

static double KendallTau(int[] x, int[] y)
{
// difference between 2 permutations
// return normalized distance
int n = x.Length;
int[] indexOf = new int[n];  // lookup
for (int i = 0; i "lt" n; ++i)
{
int v = y[i];
indexOf[v] = i;
}

int d = 0;  // raw distance = number pair misorderings
for (int i = 0; i "lt" n; ++i)
{
for (int j = i + 1; j "lt" n; ++j)
{
if (indexOf[x[i]] "gt" indexOf[x[j]])  // out of order
{
d += 1;
}
}
}

double normer = n * (n - 1) / 2.0;
double nd = d / normer;  // normalized distance
return nd;
} // KendallTau()

static void Shuffle(int[] route, Random rnd)
{
// Fisher-Yates algorithm
int n = route.Length;
for (int i = 0; i "lt" n; ++i)
{
int rIndx = rnd.Next(i, n);
int tmp = route[rIndx];
route[rIndx] = route[i];
route[i] = tmp;
}
}

static void ShowArray(int[] arr)
{
int n = arr.Length;
Console.Write("[ ");
for (int i = 0; i "lt" n; ++i)
Console.WriteLine(" ]");
}

static int[] Solve(int nCities, Random rnd, int maxIter,
double startTemperature, double alpha, double pctTunnel)
{
double currTemperature = startTemperature;
int[] soln = new int[nCities];
for (int i = 0; i "lt" nCities; ++i) { soln[i] = i; }  // [0,1,2, . . ]
Shuffle(soln, rnd);
Console.WriteLine("Initial guess: ");
ShowArray(soln); Console.WriteLine("");

double err = Error(soln);
int iteration = 0;
int interval = (int)(maxIter / 10.0);
int numSwaps = nCities;

int[] bestSoln = new int[nCities];
Array.Copy(soln, bestSoln, nCities);
double bestErr = err;

while (iteration "lt" maxIter && err "gt" 0.0)
{
double pctItersLeft = (maxIter - iteration) / (maxIter * 1.0);
if (pctItersLeft "lt" 0.00001)
pctItersLeft = 0.00001;

double p = rnd.NextDouble();  // [0.0, 1.0)
if (p "lt" pctTunnel)  // tunnel
{
numSwaps = (int)(pctItersLeft * nCities);
if (numSwaps "lt" 1)
numSwaps = 1;
}
else  // no tunneling
numSwaps = 1;

// check if best ever
{
}

if (adjErr "lt" err)  // better route so accept
{
}
else  // worse route . . .
{
double acceptProb =
p = rnd.Next();
if (p "lt" acceptProb)  // accept anyway
{
}
}

// monitor progress
if (iteration % interval == 0)
{
double nd = KendallTau(soln, adjRoute);  // normalized distance
Console.Write("iter = " + iteration.ToString().PadLeft(6) + " | ");
Console.Write("dist curr to candidate = " + nd.ToString("F4") + " | ");
Console.Write("curr temp = " + currTemperature.ToString("F4").PadLeft(12) + " | ");
}

//  if iter % interval == 0:
//print("iter = %6d | " % iter, end = "")
//print("dist curr to candidate = %8.4f | " % nd, end = "")
//print("curr_temp = %12.4f | " % curr_temperature, end = "")
//print("error = %6.1f " % best_err)

if (currTemperature "lt" 0.00001)
currTemperature = 0.00001;
else
currTemperature *= alpha;
++iteration;
}  // while

return soln;
}  // Solve()

} // Program

} // ns
```
This entry was posted in Machine Learning. Bookmark the permalink.