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 ");
      Console.ReadLine();
    } // 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.Write(arr[i].ToString().PadLeft(2) + " ");
      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;

        int[] adjRoute = Adjacent(soln, numSwaps, rnd);
        double adjErr = Error(adjRoute);
        // check if best ever
        if (adjErr "lt" bestErr)
        {
          Array.Copy(adjRoute, bestSoln, nCities);
          bestErr = adjErr;
        }

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

        // 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) + " | ");
          Console.WriteLine("error = " + bestErr.ToString("F1").PadLeft(6));
        }

      //  if iter % interval == 0:
      //(dist, nd) = my_kendall_tau_dist(soln, adj_route)
      //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