Code viewer for World: GA (TSP) (clone by Michael...

// Cloned by Michael Ryan on 24 Nov 2019 from World "GA (TSP)" by "Coding Train" project 
// Please leave this clone trail here.
 

// 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 randomRoute = [];

var totalCities =  AB.randomIntAtoB ( 10, 18 ); 

// This is wrong, should be factorial(totalCities)
// Causes a bug when fixed
var possibleRoutes = factorial(totalCities - 1);

// Using my own one to avoid breaking existing code
var totalRoutes = factorial(totalCities);

var popSize = 500;

var backImageFile = "/uploads/codingtrain/map.ireland.800.jpg";
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 bestRandomDistance = Infinity;
var bestExhaustiveDistance = Infinity;

var randomRoutesCounted = 0;

var currentRandomRouteDistance = Number.MAX_VALUE;
var currentExhaustiveRouteDistance = Number.MAX_VALUE;

var currentPermuteIndex = 0;

var currentDistance;
var tempDistance;

var bestEver;
var currentBest;

var bestExhaustive;
var exhaustiveRoute;


var statusP;
var cityOrder = [];

var height;
var width;

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) );
}

// Code to Permute An Array
// https://stackoverflow.com/a/34238979/985012
function array_nth_permutation(a, n) {
    var b = a.slice();  // copy of the set
    var len = a.length; // length of the set
    var res;            // return value, undefined
    var i, f;

    // compute f = factorial(len)
    for (f = i = 1; i <= len; i++)
        f *= i;

    // if the permutation number is within range
    if (n >= 0 && n < f) {
        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            // determine the next element:
            // there are f/len subsets for each possible element,
            f /= len;
            // a simple division gives the leading element index
            i = Math.floor(n / f);
            // alternately: i = (n - n % f) / f;
            res.push(b.splice(i, 1)[0]);
            // reduce n for the remaining subset:
            // compute the remainder of the above division
            n %= f;
            // extract the i-th element from b and push it at the end of res
        }
    }
    // return the permutated set or undefined if n is out of range
    return res;
}


// set fixed width run header 
AB.headerWidth ( 1600 );
    
    

function setup() 
{
  backImage = loadImage ( backImageFile );
  
  height = window.innerHeight;
  width = window.innerWidth;

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

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

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

function draw() 
{
   background('lightsalmon');
  // background ( backImage );
  
   // Get random route
   randomRoute = [];
   for (var i = 0; i < totalCities; i++)
   {
        randomRoute[i] = i; 
   }
   randomRoute = shuffle(randomRoute);
  
  // GA
  calculateFitness();
  normalizeFitness();
  nextGeneration();
  
  // Exhaustive
  //Draw Ex

  //BEST GA SEEN
  drawRoute('black', bestEver);
  
  // Current Best GA
  translate(width / 2, 0);
  drawRoute('darkred', currentBest);

  // Best Random Seen
  translate(0 - width / 2 , height / 3);
  drawRoute('blue', bestRandom);
  //translate(width / 2, height / 2 );
      
  // Current Random
  translate(width / 2, 0);
  drawRoute('green', randomRoute);

  // Best Exhaustive
  translate(0 - width / 2, height / 3);
  drawRoute('yellow', bestExhaustive);
  
  // Current Exhaustive
  translate(width / 2, 0);
  drawRoute('white', exhaustiveRoute);

  
  
  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 / Random Routes Tried: " + gen + 
    "<br><br> BLACK: Best ever GA route. Length: " + recordDistance.toFixed(2) +
    "<br> RED: Best Current GA Route. Length: " + currentDistance.toFixed(2) +
    "<br> BLUE: Best Random Route. Length: " + bestRandomDistance.toFixed(2) + 
    "<br> Green: Current Random Route. Length: " + currentRandomRouteDistance.toFixed(2) +
    "<br> Yellow: Best Exhaustive Route. Length: " + bestExhaustiveDistance.toFixed(2) + 
    "<br> White: Current Exhaustive Route. Length: " + currentExhaustiveRouteDistance.toFixed(2) + 
    "<br><br>Exhaustive Routes:<br>" + currentPermuteIndex + "/" + totalRoutes);
}




// 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,
    // available here: https://www.youtube.com/watch?v=HzaLIO9dLbA
    fitness[i] = 1 / (pow(d, 8) + 1);
  }
  
  // Random
  currentRandomRouteDistance = calcDistance(cities, randomRoute);
  if (currentRandomRouteDistance < bestRandomDistance)
  {
    bestRandom = randomRoute;
    bestRandomDistance = currentRandomRouteDistance;
  }
  
  // Exhaustive
  if (currentPermuteIndex < totalRoutes)
  {
    exhaustiveRoute = array_nth_permutation(cityOrder, currentPermuteIndex);
    currentPermuteIndex++;
    
    currentExhaustiveRouteDistance = calcDistance(cities, exhaustiveRoute);
    if (currentExhaustiveRouteDistance < bestExhaustiveDistance)
    {
        bestExhaustive = exhaustiveRoute;
        bestExhaustiveDistance = currentExhaustiveRouteDistance;
    }
  }
}


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);
    }
  }
}