Code viewer for World: GA (TSP)

See raw JS.

```// simple port of
// GA for Traveling Salesman Problem
// https://github.com/CodingTrain/website/tree/master/CodingChallenges/CC_035.4_TSP_GA/P5
// by Daniel Shiffman

// Daniel Shiffman
// The Coding Train
// Traveling Salesperson with Genetic Algorithm

// https://thecodingtrain.com/CodingChallenges/035.4-tsp.html
// https://youtu.be/M3KTWnTrU_c
// https://thecodingtrain.com/CodingChallenges/035.5-tsp.html
// https://youtu.be/hnxn6DtLYcY

// https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9

var totalCities =  AB.randomIntAtoB ( 5, 40 );
var possibleRoutes = factorial(totalCities-1);

var popSize = 500;

var backImage;
// 1606 map of Ireland
// https://digital.ucd.ie/view/ucdlib:22694

var gen = 1;
var routesLookedAt = 0;

var cities = [];
var population = [];
var fitness = [];

var recordDistance = Infinity;
var currentDistance;
var tempDistance;

var bestEver;
var currentBest;

var statusP;

function factorial (x)
// return x factorial
// assume only give it an integer 1,2,...
{
if (x == 1)   return ( 1 );
else          return ( x * factorial(x-1) );
}

// set fixed width run header

function setup()
{
backImage = loadImage ( backImageFile );

createCanvas (  800, 800   );     // think other code assumes square
var order = [];
for (var i = 0; i < totalCities; i++) {
var v = createVector(random(width), random(height / 2));
cities[i] = v;
order[i] = i;
}

for (var i = 0; i < popSize; i++) {
population[i] = shuffle(order);
}
statusP = createP('').style('font-size', '16pt');     // 32pt
}

function draw()
{
background('lightsalmon');
// background ( backImage );

// GA
calculateFitness();
normalizeFitness();
nextGeneration();

stroke('black');
strokeWeight(4);
noFill();
beginShape();
for (var i = 0; i < bestEver.length; i++)
{
var n = bestEver[i];
vertex(cities[n].x, cities[n].y);
ellipse(cities[n].x, cities[n].y, 8, 8);      // 16
}
endShape();

translate(0, height / 2);

stroke('darkred');
strokeWeight(4);
noFill();
beginShape();
for (var i = 0; i < currentBest.length; i++)
{
var n = currentBest[i];
vertex(cities[n].x, cities[n].y);
ellipse(cities[n].x, cities[n].y, 8, 8);
}
endShape();

var frac =  routesLookedAt / possibleRoutes ;

AB.msg ( "Number of cities: " + (totalCities) +
"<br> Number of possible routes: " + (totalCities-1) + "! = " + possibleRoutes.toFixed(0) );

// for small problems we actually can solve them exhaustively
if ( routesLookedAt >= possibleRoutes )
AB.msg ( "<br> Number of routes looked at: <b> All possible routes </b> " +
"<br> Routes looked at as fraction of possible routes: <b> 1 </b> ", 2 );
else
AB.msg ( "<br> Number of routes looked at: " + routesLookedAt +
"<br> Routes looked at as fraction of possible routes: " + frac.toFixed(20), 2 );

AB.msg ( "<p> Generation: " + gen +
"<br> Top: Best ever route. Length: " + recordDistance.toFixed(2) +
"<br> Bottom: Best route in this generation. Length: " + currentDistance.toFixed(2) +
"<br> Not shown: Testing new route. Length: " + tempDistance.toFixed(2), 3  );
}

// function shuffle(a, num) {
//   for (var i = 0; i < num; i++) {
//     var indexA = floor(random(a.length));
//     var indexB = floor(random(a.length));
//     swap(a, indexA, indexB);
//   }
// }

function swap(a, i, j)
{
var temp = a[i];
a[i] = a[j];
a[j] = temp;
}

function calcDistance(points, order)
{
var sum = 0;
for (var i = 0; i < order.length - 1; i++) {
var cityAIndex = order[i];
var cityA = points[cityAIndex];
var cityBIndex = order[i + 1];
var cityB = points[cityBIndex];
var d = dist(cityA.x, cityA.y, cityB.x, cityB.y);
sum += d;
}
return sum;
}

// Daniel Shiffman
// The Coding Train
// Traveling Salesperson with Genetic Algorithm

// https://thecodingtrain.com/CodingChallenges/035.4-tsp.html
// https://youtu.be/M3KTWnTrU_c
// https://thecodingtrain.com/CodingChallenges/035.5-tsp.html
// https://youtu.be/hnxn6DtLYcY

// https://editor.p5js.org/codingtrain/sketches/EGjTrkkf9

function calculateFitness()
{
var currentRecord = Infinity;
for (var i = 0; i < population.length; i++)
{
var d = calcDistance(cities, population[i]);
tempDistance = d;
routesLookedAt++;

if (d < recordDistance)
{
recordDistance = d;
bestEver = population[i];
}

if (d < currentRecord)
{
currentDistance = d;
currentRecord = d;
currentBest = population[i];
}

// This fitness function has been edited from the original video
// to improve performance, as discussed in The Nature of Code 9.6 video,
fitness[i] = 1 / (pow(d, 8) + 1);
}
}

function normalizeFitness()
{
var sum = 0;
for (var i = 0; i < fitness.length; i++)
sum += fitness[i];

for (var i = 0; i < fitness.length; i++)
fitness[i] = fitness[i] / sum;
}

function nextGeneration()
{
var newPopulation = [];
for (var i = 0; i < population.length; i++)
{
var orderA = pickOne(population, fitness);
var orderB = pickOne(population, fitness);
var order = crossOver(orderA, orderB);
mutate(order, 0.01);
newPopulation[i] = order;
}
population = newPopulation;
gen++;
}

function pickOne(list, prob)
{
var index = 0;
var r = random(1);

while (r > 0)
{
r = r - prob[index];
index++;
}
index--;
return list[index].slice();
}

function crossOver(orderA, orderB)
{
var start = floor(random(orderA.length));
var end = floor(random(start + 1, orderA.length));
var neworder = orderA.slice(start, end);
// var left = totalCities - neworder.length;

for (var i = 0; i < orderB.length; i++)
{
var city = orderB[i];
if (!neworder.includes(city))
neworder.push(city);
}
return neworder;
}

function mutate(order, mutationRate)
{
for (var i = 0; i < totalCities; i++)
{
if (random(1) < mutationRate)
{
var indexA = floor(random(order.length));
var indexB = (indexA + 1) % totalCities;
swap(order, indexA, indexB);
}
}
}

```
```
```