## Traveling Salesman Problem Combinatorial Optimization Using an Evolutionary Algorithm with C#

A combinatorial optimization problem is one where the goal is to place items in a correct order. The classic example is the Traveling Salesman Problem (TSP). Suppose you have n = 20 cities that are numbered 0 to 19. There is a distance between each pair of cities. You want to find the shortest path that visits all cities. For example, one possible solution might be [19, 5, 0, 2, 4, . . 11].

Combinatorial optimization problems are very difficult. There are 20! = 2,432,902,008,176,640,000 possible solutions if distance(A,B) != distance(B,A). This is a huge number and so you can’t try every permutation. The most common technique for combinatorial optimization is to use Simulated Annealing (SA). See https://jamesmccaffrey.wordpress.com/2021/12/01/the-traveling-salesman-problem-using-simulated-annealing-in-csharp/

I wondered if I could design a technique for combinatorial optimization that uses an evolutionary algorithm. After a lot of work, I got a demo up and running.

In very high level pseudo-code, an evolutionary algorithm looks like:

```create a population of random solutions
loop many times
pick two existing solutions
make a child solution
mutate the child
replace a poor solution with new child
end-loop
return best solution found
```

There were several rather tricky details. The most difficult sub-problem was finding a way to combine two permutation solutions to create a child solution.

I created a demo for the TSP with n = 20 cities. I set up a city distances mapping where distance(A, B) = 1 if A and B are adjacent and A is less than B, and distance(B, A) = 1.5 if A is greater than B. Therefore, the optimal permutation is [0, 1, 2, . . 19] with total distance of 1 + 1 + . . + 1 = 19.

I used a population size of 6 and looped for 1,000 iterations. The algorithm found a very good (but not optimal) solution of [0 1 2 5 14 4 3 6 8 18 19 16 17 15 13 12 11 10 9 7] with total distance of 1 + 1 + 3 + 9 + 15.0 + 1.5 + 3 + 2 + 10 + 1 + 4.5 + 1 + 3 + 3 + 1.5 + 1.5 + 1.5 + 1.5 + 3.0 = 67.0. Playing cards are all about permutations and combinatorial optimization. When I was a college student at UC Irvine, my roommate Ed Koolish and I often drove to Las Vegas to play Blackjack — we knew how to card-count. Here’s an image from a project that uses machine learning to recognize cards.

Demo code. Replace “lt”, “gt” with Boolean operator symbols.

```using System;
namespace TSP_Evolutionary
{
internal class TSP_EvoProgram
{
static void Main(string[] args)
{
Console.WriteLine("\nBegin evolutionary optimization ");
Console.WriteLine("Setting TSP n = 20 cities ");
Console.WriteLine("20! = 2,432,902,008,176,640,000 ");
Console.WriteLine("Optimal soln is 0 1 2 . . 19 dist = 19");

int numCities = 20;
int numPop = 6;

double[][] distances = GetDistances(numCities);

Solver solver = new Solver(numCities, numPop,
distances, seed: 99);
Console.WriteLine("\nInitial population: ");
solver.Show();

Console.WriteLine("\nBegin search ");
solver.Solve(1000);
Console.WriteLine("Done ");

Console.WriteLine("\nFinal population: ");
solver.Show();

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

static double[][] GetDistances(int n)
{
// in non-demo, these come from a file
double[][] result = new double[n][];
for (int i = 0; i "lt" n; ++i)
result[i] = new double[n];
for (int i = 0; i "lt" n; ++i)
for (int j = 0; j "lt" n; ++j)
if (i "lt" j) result[i][j] = (j - i) * 1.0;
else if (i "gt" j) result[i][j] = (i - j) * 1.5;
return result;
}
} // Program

class Solver
{
public Random rnd;
public int numCities;
public int numPop; // should be even

public double[][] distances;

public int[][] pop;  // array of solns[]
public double[] errs;

public int[] bestSoln;
public double bestErr;

public Solver(int numCities, int numPop,
double[][] distances, int seed)
{
this.rnd = new Random(seed);
this.numCities = numCities;
this.numPop = numPop;
this.bestErr = 0.0;
this.distances = distances;

this.pop = new int[numPop][];  // allocate
for (int i = 0; i "lt" numPop; ++i)
this.pop[i] = new int[numCities];
this.errs = new double[numPop];

for (int i = 0; i "lt" numPop; ++i)  // init
{
for (int j = 0; j "lt" numCities; ++j)
{
this.pop[i][j] = j;  // [0, 1, 2, . . ]
}
this.Shuffle(this.pop[i]);  //
this.errs[i] = this.ComputeError(this.pop[i]);
}

Array.Sort(this.errs, this.pop);

this.bestSoln = new int[numCities];
for (int j = 0; j "lt" this.numCities; ++j)
this.bestSoln[j] = this.pop[j];
this.bestErr = this.errs;
} // ctor

public void Show()
{
for (int i = 0; i "lt" this.numPop; ++i)
{
for (int j = 0; j "lt" this.numCities; ++j)
{
Console.Write(this.pop[i][j] + " ");
}
Console.WriteLine(" | " +
this.errs[i].ToString("F4"));
}

Console.WriteLine("-----");
for (int j = 0; j "lt" this.numCities; ++j)
Console.Write(this.bestSoln[j] + " ");
Console.WriteLine(" | " +
this.bestErr.ToString("F4"));
}

public void Shuffle(int[] soln)
{
// Fisher-Yates algorithm
int n = soln.Length;
for (int i = 0; i "lt" n; ++i)
{
int ri = this.rnd.Next(i, n);  // random index
int tmp = soln[ri];
soln[ri] = soln[i];
soln[i] = tmp;
}
}

public double ComputeError(int[] soln)
{
double d = 0.0;  // total distance between cities
int n = soln.Length;  // aka numCities
for (int i = 0; i "lt" n - 1; ++i)
{
int fromCity = soln[i];
int toCity = soln[i + 1];
d += this.distances[fromCity][toCity];
}
return d;
}

public int[] MakeChild(int idx1, int idx2)  // crossover
{
int[] parent1 = this.pop[idx1];
int[] parent2 = this.pop[idx2];
int[] result = new int[this.numCities];
int[] used = new int[this.numCities];
int[] candidates = new int[2 * this.numCities];

int k = 0;
for (int i = 0;
i "lt" this.numCities / 2; ++i)  // left parent1
{
candidates[k++] = parent1[i];
}

for (int i = this.numCities / 2;
i "lt" this.numCities; ++i)  // right parent2
{
candidates[k++] = parent2[i];
}

for (int i = 0;
i "lt" this.numCities / 2; ++i)  // left parent2
{
candidates[k++] = parent2[i];
}

for (int i = this.numCities / 2;
i "lt" this.numCities; ++i)  // right parent1
{
candidates[k++] = parent1[i];
}

k = 0;
for (int i = 0; i "lt" this.numCities; ++i)
{
while (used[candidates[k]] == 1)
k += 1;
result[i] = candidates[k];
used[candidates[k]] = 1;
}

return result;
} // MakeChild

public void Mutate(int[] soln)
{
int idx = this.rnd.Next(0, this.numCities - 1);
int tmp = soln[idx];
soln[idx] = soln[idx+1];
soln[idx+1] = tmp;
}

public void Solve(int maxGen)
{
for (int gen = 0; gen "lt" maxGen; ++gen)
{
// 1. pick parent indexes
int idx1, idx2;
int flip = this.rnd.Next(2);
if (flip == 0)
{

idx1 = this.rnd.Next(0, this.numPop / 2);
idx2 = this.rnd.Next(this.numPop / 2, this.numPop);
}
else
{
idx2 = this.rnd.Next(0, this.numPop / 2);
idx1 = this.rnd.Next(this.numPop / 2, this.numPop);
}

// 2. create a child
int[] child = MakeChild(idx1, idx2);

// 3. mutate
Mutate(child);
double childErr = this.ComputeError(child);

// 4. found new best?
if (childErr "lt" this.bestErr)
{
Console.WriteLine("New best soltn found at gen " +
gen);
for (int i = 0; i "lt" child.Length; ++i)
this.bestSoln[i] = child[i];
this.bestErr = childErr;
}

// 4. replace weak soln
int idx = this.rnd.Next(this.numPop / 2, this.numPop);
this.pop[idx] = child;
this.errs[idx] = childErr;

// 5. create an immigrant
int[] imm = new int[this.numCities];
for (int i = 0; i "lt" this.numCities; ++i)
imm[i] = i;
this.Shuffle(imm);
double immErr = this.ComputeError(imm);

// found new best?
if (immErr "lt" this.bestErr)
{
Console.WriteLine("New best (immigrant) at gen " +
gen);
for (int i = 0; i "lt" imm.Length; ++i)
this.bestSoln[i] = imm[i];
this.bestErr = immErr;
}

// 4. replace weak soln
idx = this.rnd.Next(this.numPop / 2, this.numPop);
this.pop[idx] = imm;
this.errs[idx] = immErr;

// 5. sort the new population
Array.Sort(this.errs, this.pop);

} // gen
} // Solve

} // Solver

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

### 4 Responses to Traveling Salesman Problem Combinatorial Optimization Using an Evolutionary Algorithm with C#

1. Thorsten Kleppe says:

The demo runs really well with .Net 7, however my first optimization attempts failed.^^

2. Mohamed Cisse says:

Hi
How can I add constraint to it .
Let’s say a driver is supposed to visit cities A,B,C,D.
He/she has a package to pick up from B and deliver to C .That mean he/she cannot visit C before B.
How to handle that situation ?

• jamesdmccaffrey says:

Mohamed, There is no easy way to add constraints to a combinatorial optimization problem. The usual approach is to add if..then to the logic that gives a penalty to illegal potential solutions.